1 /*---------------------------------------------------------------------------*
2 Project: Compress/uncompress library
3 File: CXStreamingUncompression.c
4 Programmer: Makoto Takano
5
6 Copyright 2005 Nintendo. All rights reserved.
7
8 These coded instructions, statements, and computer programs contain
9 proprietary information of Nintendo of America Inc. and/or Nintendo
10 Company Ltd., and are protected by Federal copyright law. They may
11 not be disclosed to third parties or copied or duplicated in any form,
12 in whole or in part, without the prior written consent of Nintendo.
13 *---------------------------------------------------------------------------*/
14
15 #include <revolution/cx/CXUncompression.h>
16 #include <revolution/cx/CXStreamingUncompression.h>
17 #include <revolution/cx/CXSecureUncompression.h>
18 #include "CXUtil.h"
19
20
21 /*---------------------------------------------------------------------------*
22 Name : CXInitUncompContextRL
23
24 Description : Initializes the streaming decompression context for run-length compressed data.
25
26
27 Arguments : context: Pointer to the run-length uncompressed context
28 dest: Destination address for uncompressed data
29
30 Returns : Can get the data size after decompression.
31
32 *---------------------------------------------------------------------------*/
CXInitUncompContextRL(CXUncompContextRL * context,void * dest)33 void CXInitUncompContextRL( CXUncompContextRL *context, void* dest )
34 {
35 context->destp = (u8*)dest;
36 context->destCount = 0;
37 context->flags = 0;
38 context->length = 0;
39 context->headerSize = 8;
40 context->forceDestCount = 0;
41 }
42
43
44 /*---------------------------------------------------------------------------*
45 Name : CXInitUncompContextLZ
46
47 Description : Initializes the streaming decompression context for LZ-compressed data.
48
49 Arguments : context: Pointer to the LZ-uncompressed context
50 dest: Destination address for uncompressed data
51 header: Pointer to the start data for the compressed data
52
53 *---------------------------------------------------------------------------*/
CXInitUncompContextLZ(CXUncompContextLZ * context,void * dest)54 void CXInitUncompContextLZ( CXUncompContextLZ *context, void* dest )
55 {
56 context->destp = (u8*)dest;
57 context->destCount = 0;
58 context->flags = 0;
59 context->flagIndex = 0;
60 context->length = 0;
61 context->lengthFlg = 3;
62 context->headerSize = 8;
63 context->exFormat = 0;
64 context->forceDestCount = 0;
65 }
66
67
68 /*---------------------------------------------------------------------------*
69 Name : CXInitUncompContextHuffman
70
71 Description : Initializes the streaming decompression context for Huffman-compressed data.
72
73 Arguments : context: Pointer to the Huffman-uncompressed context
74 dest: Destination address for uncompressed data
75 header: Pointer to the start data for the compressed data
76
77 *---------------------------------------------------------------------------*/
CXInitUncompContextHuffman(CXUncompContextHuffman * context,void * dest)78 void CXInitUncompContextHuffman( CXUncompContextHuffman *context, void* dest )
79 {
80 context->destp = (u8*)dest;
81 context->destCount = 0;
82 context->bitSize = 0;
83 context->treeSize = -1;
84 context->treep = &context->tree[ 0 ];
85 context->destTmp = 0;
86 context->destTmpCnt = 0;
87 context->srcTmp = 0;
88 context->srcTmpCnt = 0;
89 context->headerSize = 8;
90 context->forceDestCount = 0;
91 }
92
93 /*---------------------------------------------------------------------------*
94 Name: CXiReadHeader
95
96 Description: Header parsing
97
98 Arguments: headerSize Pointer to the remaining size of the header to be read
99 *destCount Pointer to the uncompressed data size
100 srcp Pointer to a buffer containing the header information
101 srcSize Pointer to the size of the buffer containing the header information
102 forceDestSize Uncompressed data size (if 0, use the binary header information as is)
103
104 Returns: Size of the loaded source data
105 *---------------------------------------------------------------------------*/
CXiReadHeader(u8 * headerSize,s32 * destCount,const u8 * srcp,u32 srcSize,s32 forceDestSize)106 static inline u32 CXiReadHeader( u8* headerSize, s32 *destCount, const u8* srcp, u32 srcSize, s32 forceDestSize )
107 {
108 u32 readLen = 0;
109 while ( *headerSize > 0 )
110 {
111 --(*headerSize);
112 if ( *headerSize <= 3 )
113 {
114 *destCount |= (*srcp << ((3 - *headerSize) * 8));
115 }
116 else if ( *headerSize <= 6 )
117 {
118 *destCount |= (*srcp << ((6 - *headerSize) * 8));
119 }
120 ++srcp;
121 ++readLen;
122 if ( *headerSize == 4 && *destCount > 0 )
123 {
124 *headerSize = 0;
125 }
126 if ( --srcSize == 0 && *headerSize > 0 )
127 {
128 return readLen;
129 }
130 }
131
132 if ( ( forceDestSize > 0 ) &&
133 ( forceDestSize < *destCount ) )
134 {
135 *destCount = forceDestSize;
136 }
137 return readLen;
138 }
139
140
141 /*---------------------------------------------------------------------------*
142 Name : CXReadUncompRL
143
144 Description : This function performs streaming decompression of run-length compressed data.
145 Data is written in units of 8 bits. Data cannot be directly uncompressed to VRAM.
146
147 Arguments : context: Pointer to the run-length uncompressed context
148 data: Pointer to the next data
149 len: Data size
150
151 Returns : Size of remaining uncompressed data.
152 Returns a negative error code if failed.
153
154 *---------------------------------------------------------------------------*/
CXReadUncompRL(CXUncompContextRL * context,const void * data,u32 len)155 s32 CXReadUncompRL( CXUncompContextRL *context, const void* data, u32 len )
156 {
157 const u8* srcp = (const u8*)data;
158 u8 srcTmp;
159
160 // Header parsing
161 if ( context->headerSize > 0 )
162 {
163 u32 read_len;
164 if ( context->headerSize == 8 )
165 {
166 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_RL )
167 {
168 return CX_ERR_UNSUPPORTED;
169 }
170 if ( (*srcp & 0x0F ) != 0 )
171 {
172 return CX_ERR_UNSUPPORTED;
173 }
174 }
175 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
176 srcp += read_len;
177 len -= read_len;
178 if ( len == 0 )
179 {
180 return (context->headerSize == 0)? context->destCount : -1;
181 }
182 }
183
184 while ( context->destCount > 0 )
185 {
186 // Process if length > 0.
187 if ( ! (context->flags & 0x80) )
188 // Uncompressed data has a length not equal to 0
189 {
190 while ( context->length > 0 )
191 {
192 *context->destp++ = *srcp++;
193 context->length--;
194 context->destCount--;
195 len--;
196 // End when the prepared buffer has been read in full
197 if ( len == 0 )
198 {
199 return context->destCount;
200 }
201 }
202 }
203 else if ( context->length > 0 )
204 // Compressed data has a length not equal to 0
205 {
206 srcTmp = *srcp++;
207 len--;
208 while ( context->length > 0 )
209 {
210 *context->destp++ = srcTmp;
211 context->length--;
212 context->destCount--;
213 }
214 if ( len == 0 )
215 {
216 return context->destCount;
217 }
218 }
219
220 // Reading the flag byte
221 context->flags = *srcp++;
222 len--;
223 context->length = (u16)(context->flags & 0x7F);
224 if ( context->flags & 0x80 )
225 {
226 context->length += 3;
227 }
228 else
229 {
230 context->length += 1;
231 }
232
233 if ( context->length > context->destCount )
234 // A buffer overrun handler for when invalid data is decompressed.
235 {
236 if ( context->forceDestCount == 0 )
237 {
238 return CX_ERR_DEST_OVERRUN;
239 }
240 context->length = (u16)context->destCount;
241 }
242 if ( len == 0 )
243 {
244 return context->destCount;
245 }
246 }
247
248 // Processing to perform in the event that context->destCount == 0
249 if ( (context->forceDestCount == 0) && (len > 32) )
250 {
251 return CX_ERR_SRC_REMAINDER;
252 }
253 return 0;
254 }
255
256
257 /*---------------------------------------------------------------------------*
258 Name : CXReadUncompLZ
259
260 Description : This function performs streaming decompression of LZ-compressed data.
261 Data is written in units of 8 bits. Data cannot be directly uncompressed to VRAM.
262
263 Arguments : context: Pointer to the LZ-uncompressed context
264 data: Pointer to the next data
265 len: Data size
266
267 Returns : Size of remaining uncompressed data.
268 Returns a negative error code if failed.
269
270 *---------------------------------------------------------------------------*/
CXReadUncompLZ(CXUncompContextLZ * context,const void * data,u32 len)271 s32 CXReadUncompLZ( CXUncompContextLZ *context, const void* data, u32 len )
272 {
273 const u8* srcp = (const u8*)data;
274 s32 offset;
275
276 // Header parsing
277 if ( context->headerSize > 0 )
278 {
279 u32 read_len;
280 // Process the first byte
281 if ( context->headerSize == 8 )
282 {
283 if ( ( *srcp & CX_COMPRESSION_TYPE_MASK ) != CX_COMPRESSION_LZ )
284 {
285 return CX_ERR_UNSUPPORTED;
286 }
287 // Record as an LZ compression parameter
288 context->exFormat = (u8)( *srcp & 0x0F );
289 if ( (context->exFormat != 0x0) && (context->exFormat != 0x1) )
290 {
291 return CX_ERR_UNSUPPORTED;
292 }
293 }
294 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
295 srcp += read_len;
296 len -= read_len;
297 if ( len == 0 )
298 {
299 return (context->headerSize == 0)? context->destCount : -1;
300 }
301 }
302
303 while ( context->destCount > 0 )
304 {
305 while ( context->flagIndex > 0 )
306 {
307 if ( len == 0 )
308 {
309 return context->destCount;
310 }
311
312 if ( ! (context->flags & 0x80) )
313 // Process for non-compressed data
314 {
315 *context->destp++ = *srcp++;
316 context->destCount--;
317 len--;
318 }
319 else
320 // Process for compressed data
321 {
322 while ( context->lengthFlg > 0 )
323 {
324 --context->lengthFlg;
325 if ( ! context->exFormat )
326 {
327 context->length = *srcp++;
328 context->length += (3 << 4);
329 context->lengthFlg = 0;
330 }
331 else
332 {
333 switch ( context->lengthFlg )
334 {
335 case 2:
336 {
337 context->length = *srcp++;
338 if ( (context->length >> 4) == 1 )
339 {
340 // Read two more bytes
341 context->length = (context->length & 0x0F) << 16;
342 context->length += ( (0xFF + 0xF + 3) << 4 );
343 }
344 else if ( (context->length >> 4) == 0 )
345 {
346 // Read one more byte
347 context->length = (context->length & 0x0F) << 8;
348 context->length += ( (0xF + 2) << 4 );
349 context->lengthFlg = 1;
350 }
351 else
352 {
353 context->length += (1 << 4);
354 context->lengthFlg = 0;
355 }
356 }
357 break;
358 case 1:
359 {
360 context->length += (*srcp++ << 8);
361 }
362 break;
363 case 0:
364 {
365 context->length += *srcp++;
366 }
367 break;
368 }
369 }
370 if ( --len == 0 )
371 {
372 return context->destCount;
373 }
374 }
375
376 offset = (context->length & 0xF) << 8;
377 context->length = context->length >> 4;
378 offset = (offset | *srcp++) + 1;
379 len--;
380 context->lengthFlg = 3;
381
382 // A buffer overrun handler for when invalid data is decompressed.
383 if ( context->length > context->destCount )
384 {
385 if ( context->forceDestCount == 0 )
386 {
387 return CX_ERR_DEST_OVERRUN;
388 }
389 context->length = context->destCount;
390 }
391 // Copy a length amount of data located at the offset position
392 while ( context->length > 0 )
393 {
394 *context->destp = context->destp[ -offset ];
395 context->destp++;
396 context->destCount--;
397 context->length--;
398 }
399 }
400
401 if ( context->destCount == 0 )
402 {
403 goto out;
404 }
405 context->flags <<= 1;
406 context->flagIndex--;
407 }
408
409 if ( len == 0 )
410 {
411 return context->destCount;
412 }
413 // Read a new flag
414 context->flags = *srcp++;
415 context->flagIndex = 8;
416 len--;
417 }
418
419 out:
420 // Processing to perform in the event that context->destCount == 0
421 if ( (context->forceDestCount == 0) && (len > 32) )
422 {
423 return CX_ERR_SRC_REMAINDER;
424 }
425 return 0;
426 }
427
428
429 // Get the next node in the Huffman signed table
GetNextNode(const u8 * pTree,u32 select)430 static inline u8* GetNextNode( const u8* pTree, u32 select )
431 {
432 return (u8*)( ((u32)pTree & ~0x1) + ( ( (*pTree & 0x3F) + 1 ) * 2 ) + select );
433 }
434
435 extern BOOL CXiVerifyHuffmanTable_( const void* pTable, u8 bit );
436
437 /*---------------------------------------------------------------------------*
438 Name : CXReadUncompHuffman
439
440 Description : This function performs streaming decompression of Huffman-compressed data.
441 Returns a negative error code if failed.
442
443 Arguments : context: Pointer to the Huffman-uncompressed context
444 data: Pointer to the next data
445 len: Data size
446
447 Returns : Size of remaining uncompressed data.
448 Returns a negative error code if failed.
449
450 *---------------------------------------------------------------------------*/
CXReadUncompHuffman(CXUncompContextHuffman * context,const void * data,u32 len)451 s32 CXReadUncompHuffman( CXUncompContextHuffman *context, const void* data, u32 len )
452 {
453 #define TREE_END_MASK 0x80U
454 const u8* srcp = (const u8*)data;
455 u32 select;
456 u32 endFlag;
457
458 // Header parsing
459 if ( context->headerSize > 0 )
460 {
461 u32 read_len;
462 // Process the first byte
463 if ( context->headerSize == 8 )
464 {
465 context->bitSize = (u8)(*srcp & 0xF);
466
467 if ( ( *srcp & CX_COMPRESSION_TYPE_MASK ) != CX_COMPRESSION_HUFFMAN )
468 {
469 return CX_ERR_UNSUPPORTED;
470 }
471 if ( (context->bitSize != 4) && (context->bitSize != 8) )
472 {
473 return CX_ERR_UNSUPPORTED;
474 }
475 }
476 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
477 srcp += read_len;
478 len -= read_len;
479 if ( len == 0 )
480 {
481 return (context->headerSize == 0)? context->destCount : -1;
482 }
483 }
484
485 // treeSize is set to -1 in CXInitUncompContextHuffman.
486 // When context->treeSize is negative, the data's beginning is used.
487 if ( context->treeSize < 0 )
488 {
489 context->treeSize = (s16)( ( *srcp + 1 ) * 2 - 1 );
490 *context->treep++ = *srcp++;
491 len--;
492 }
493
494 // Load the Huffman signed table
495 while ( context->treeSize > 0 )
496 {
497 if ( len == 0 )
498 {
499 return context->destCount;
500 }
501 *context->treep++ = *srcp++;
502 context->treeSize--;
503 len--;
504 if ( context->treeSize == 0 )
505 {
506 context->treep = &context->tree[ 1 ];
507 if ( ! CXiVerifyHuffmanTable_( &context->tree[ 0 ], context->bitSize ) )
508 {
509 return CX_ERR_ILLEGAL_TABLE;
510 }
511 }
512 }
513
514 // Decoding process
515 while ( context->destCount > 0 )
516 {
517 // src data is read in 4-byte units
518 while ( context->srcTmpCnt < 32 )
519 {
520 if ( len == 0 )
521 {
522 return context->destCount;
523 }
524 context->srcTmp |= (*srcp++) << context->srcTmpCnt;
525 len--;
526 context->srcTmpCnt += 8;
527 }
528
529 // Decode the 32 bits that were loaded. After those 32 bits are processed, the next 4 bytes are read.
530 while ( context->srcTmpCnt > 0 )
531 {
532 select = context->srcTmp >> 31;
533 endFlag = (*context->treep << select) & TREE_END_MASK;
534 context->treep = GetNextNode( context->treep, select );
535 context->srcTmp <<= 1;
536 context->srcTmpCnt--;
537
538 if ( ! endFlag )
539 {
540 continue;
541 }
542
543 // When the Huffman tree's terminal flag is set, data is stored at the end of the offset.
544 //
545 context->destTmp >>= context->bitSize;
546 context->destTmp |= *context->treep << ( 32 - context->bitSize );
547 context->treep = &context->tree[ 1 ];
548 context->destTmpCnt += context->bitSize;
549
550 if ( context->destCount <= (context->destTmpCnt / 8) )
551 {
552 context->destTmp >>= (32 - context->destTmpCnt);
553 context->destTmpCnt = 32;
554 }
555
556 // Write in 4-byte units
557 if ( context->destTmpCnt == 32 )
558 {
559 *(u32*)context->destp = CXiConvertEndian_( context->destTmp );
560 context->destp += 4;
561 context->destCount -= 4;
562 context->destTmpCnt = 0;
563 if ( context->destCount <= 0 )
564 {
565 goto out;
566 }
567 }
568 }
569 }
570
571 out:
572 // Processing to perform in the event that context->destCount == 0
573 if ( (context->forceDestCount == 0) && (len > 32) )
574 {
575 return CX_ERR_SRC_REMAINDER;
576 }
577 return 0;
578 }
579
580
581
582 typedef struct
583 {
584 const u8* srcp;
585 u32 cnt;
586 u32 stream;
587 u32 stream_len;
588 }
589 BitReader;
590
591
592 static inline s32
BitReader_Read(BitReader * context,u8 bits)593 BitReader_Read( BitReader* context, u8 bits )
594 {
595 s32 value;
596
597 while ( context->stream_len < bits )
598 {
599 if ( context->cnt == 0 )
600 {
601 return -1;
602 }
603 context->stream <<= 8;
604 context->stream += *context->srcp;
605 context->srcp++;
606 context->cnt--;
607 context->stream_len += 8;
608 }
609
610 value = (s32)( (context->stream >> (context->stream_len - bits)) & ((1 << bits) - 1) );
611 context->stream_len -= bits;
612 return value;
613 }
614
615 static inline s64
BitReader_ReadEx(BitReader * context,u8 bits)616 BitReader_ReadEx( BitReader* context, u8 bits )
617 {
618 s64 value;
619 u8 stock = 0;
620
621 while ( context->stream_len < bits )
622 {
623 if ( context->cnt == 0 )
624 {
625 return -1;
626 }
627 if ( context->stream_len > 24 )
628 {
629 stock = (u8)( context->stream >> 24 );
630 }
631 context->stream <<= 8;
632 context->stream += *context->srcp;
633 context->srcp++;
634 context->cnt--;
635 context->stream_len += 8;
636 }
637 value = context->stream;
638 value |= (s64)stock << 32;
639 value = (s64)( (value >> (context->stream_len - bits)) & ((1 << bits) - 1) );
640 context->stream_len -= bits;
641
642 return value;
643 }
644
645 #define ENC_OFFSET_WIDTH
646
647 /*---------------------------------------------------------------------------*
648 Name: CXInitUncompContextLH
649
650 Description:
651
652
653 Arguments: context
654 dest
655
656 Returns: None.
657 *---------------------------------------------------------------------------*/
658 void
CXInitUncompContextLH(CXUncompContextLH * context,void * dest)659 CXInitUncompContextLH( CXUncompContextLH * context, void* dest )
660 {
661 context->destp = dest;
662 context->destCount = -1;
663 context->nodep = context->huffTable9 + 1;
664 context->tableSize9 = -1;
665 context->tableSize12 = -1;
666 context->headerSize = 8;
667 context->length = 0;
668 context->stream = 0;
669 context->stream_len = 0;
670 context->offset_bits = -1;
671 context->forceDestCount = 0;
672 }
673
674 extern BOOL CXiLHVerifyTable( const void* pTable, u8 bit );
675
676 /*---------------------------------------------------------------------------*
677 Name: CXReadUncompLH
678
679 Description: This function performs streaming decompression of LZ-Huffman (combined) compressed data.
680
681 Arguments: *context: Pointer to the decompressed context
682 data: Data pointer
683 len: Data size
684
685 Returns: Size of remaining uncompressed data
686 Returns a negative error code if failed.
687 *---------------------------------------------------------------------------*/
688 s32
CXReadUncompLH(CXUncompContextLH * context,const void * data,u32 len)689 CXReadUncompLH( CXUncompContextLH *context, const void* data, u32 len )
690 {
691 #define LENGTH_BITS 9
692 #if defined(ENC_OFFSET_WIDTH)
693 #define OFFSET_BITS 5
694 #define OFFSET_MASK 0x07
695 #define LEAF_FLAG 0x10
696 #else
697 #define OFFSET_BITS 12
698 #define OFFSET_MASK 0x3FF
699 #define LEAF_FLAG 0x800
700 #endif
701
702 const u8* srcp = (const u8*)data;
703 BitReader stream;
704 s32 val;
705 u16* nodep;
706 u16 length;
707
708 stream.srcp = srcp;
709 stream.cnt = len;
710 stream.stream = context->stream;
711 stream.stream_len = context->stream_len;
712
713 // Header parsing
714 while ( context->headerSize > 0 )
715 {
716 s64 val32 = BitReader_ReadEx( &stream, 32 );
717 if ( val32 < 0 )
718 {
719 goto out;
720 }
721 context->headerSize -= 4;
722 if ( context->headerSize == 4 )
723 {
724 u32 headerVal = CXiConvertEndian_( (u32)val32 );
725 if ( (headerVal & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LH )
726 {
727 return CX_ERR_UNSUPPORTED;
728 }
729 context->destCount = (s32)( headerVal >> 8 );
730
731 if ( context->destCount == 0 )
732 {
733 context->headerSize = 4;
734 context->destCount = -1;
735 }
736 else
737 {
738 context->headerSize = 0;
739 }
740 }
741 else // if ( context->headerSize == 0 )
742 {
743 context->destCount = (s32)CXiConvertEndian_( (u32)val32 );
744 }
745 if ( context->headerSize == 0 )
746 {
747 if ( ( context->forceDestCount > 0 ) && ( context->forceDestCount < context->destCount ) )
748 {
749 context->destCount = context->forceDestCount;
750 }
751 }
752 }
753
754 // load the Huffman table
755 {
756 if ( context->tableSize9 < 0 )
757 {
758 if ( ( val = BitReader_Read( &stream, 16 ) ) < 0 )
759 {
760 goto out;
761 }
762 context->tableSize9 = (CXiConvertEndian16_( (u16)val ) + 1) * 4 * 8; // shown with the bit count
763 context->tableIdx = 1;
764 context->tableSize9 -= 16;
765 }
766 while ( context->tableSize9 >= LENGTH_BITS )
767 {
768 if ( ( val = BitReader_Read( &stream, LENGTH_BITS ) ) < 0 )
769 {
770 goto out;
771 }
772 context->huffTable9[ context->tableIdx++ ] = (u16)val;
773 context->tableSize9 -= LENGTH_BITS;
774 }
775 while ( context->tableSize9 > 0 )
776 {
777 if ( ( val = BitReader_Read( &stream, (u8)context->tableSize9 ) ) < 0 )
778 {
779 goto out;
780 }
781 context->tableSize9 = 0;
782 }
783 // verify the table
784 if ( ! CXiLHVerifyTable( context->huffTable9, LENGTH_BITS ) )
785 {
786 return CX_ERR_ILLEGAL_TABLE;
787 }
788 }
789 {
790 if ( context->tableSize12 < 0 )
791 {
792 if ( ( val = BitReader_Read( &stream, (OFFSET_BITS > 8)? 16 : 8 ) ) < 0 )
793 {
794 goto out;
795 }
796 #if ( OFFSET_BITS > 8 )
797 context->tableSize12 = (CXiConvertEndian16_( (u16)val ) + 1) * 4 * 8;
798 #else // ( OFFSET_BITS <= 8 )
799 context->tableSize12 = ((u16)val + 1) * 4 * 8;
800 #endif
801 context->tableIdx = 1;
802 context->tableSize12 -= (OFFSET_BITS > 8)? 16 : 8;
803 }
804
805 while ( context->tableSize12 >= OFFSET_BITS )
806 {
807 if ( ( val = BitReader_Read( &stream, OFFSET_BITS ) ) < 0 )
808 {
809 goto out;
810 }
811 context->huffTable12[ context->tableIdx++ ] = (u16)val;
812 context->tableSize12 -= OFFSET_BITS;
813 }
814 while ( context->tableSize12 > 0 )
815 {
816 if ( ( val = BitReader_Read( &stream, (u8)context->tableSize12 ) ) < 0 )
817 {
818 goto out;
819 }
820 context->tableSize12 = 0;
821 }
822 // verify the table
823 if ( ! CXiLHVerifyTable( context->huffTable12, OFFSET_BITS ) )
824 {
825 return CX_ERR_ILLEGAL_TABLE;
826 }
827 }
828
829 nodep = context->nodep;
830 length = context->length;
831
832 // Data conversion
833 while ( context->destCount > 0 )
834 {
835 // get length data
836 if ( length == 0 )
837 {
838 do
839 {
840 u8 bit;
841 u32 offset;
842 if ( ( val = BitReader_Read( &stream, 1 ) ) < 0 )
843 {
844 context->nodep = nodep;
845 context->length = length;
846 goto out;
847 }
848 bit = (u8)( val & 1 );
849 offset = (((*nodep & 0x7F) + 1U) << 1) + bit;
850
851 if ( *nodep & (0x100 >> bit) )
852 {
853 nodep = (u16*)((u32)nodep & ~0x3);
854 length = *(nodep + offset);
855 nodep = context->huffTable12 + 1;
856 break;
857 }
858 else
859 {
860 nodep = (u16*)((u32)nodep & ~0x3);
861 nodep += offset;
862 }
863 } while ( 1 );
864 }
865
866 if ( length < 0x100 )
867 // uncompressed data
868 {
869 *context->destp++ = (u8)length;
870 context->destCount--;
871 nodep = context->huffTable9 + 1;
872 length = 0;
873 }
874 else
875 // compressed data
876 {
877 u16 lzOffset;
878 u16 lzLength = (u16)( (length & 0xFF) + 3 );
879
880 #if defined(ENC_OFFSET_WIDTH)
881 if ( context->offset_bits < 0 )
882 {
883 #endif
884 do
885 {
886 u8 bit;
887 u32 offset;
888
889 if ( ( val = BitReader_Read( &stream, 1 ) ) < 0 )
890 {
891 context->nodep = nodep;
892 context->length = length;
893 goto out;
894 }
895 bit = (u8)( val & 1 );
896 offset = (((*nodep & OFFSET_MASK) + 1U) << 1) + bit;
897
898 if ( *nodep & (LEAF_FLAG >> bit) )
899 {
900 nodep = (u16*)((u32)nodep & ~0x3);
901 #if defined(ENC_OFFSET_WIDTH)
902 context->offset_bits = (s8)( *(nodep + offset) );
903 #else
904 lzOffset = (u16)( *(nodep + offset) + 1 );
905 #endif
906 break;
907 }
908 else
909 {
910 nodep = (u16*)((u32)nodep & ~0x3);
911 nodep += offset;
912 }
913 } while ( 1 );
914 #if defined(ENC_OFFSET_WIDTH)
915 }
916 #endif
917
918 #if defined(ENC_OFFSET_WIDTH)
919 if ( context->offset_bits <= 1 )
920 {
921 val = context->offset_bits;
922 }
923 else if ( ( val = BitReader_Read( &stream, (u8)(context->offset_bits - 1) ) ) < 0 )
924 {
925 context->nodep = nodep;
926 context->length = length;
927 goto out;
928 }
929 if ( context->offset_bits >= 2 )
930 {
931 val |= (1 << (context->offset_bits - 1));
932 }
933
934 context->offset_bits = -1;
935 lzOffset = (u16)(val + 1);
936 #endif
937
938 if ( context->destCount < lzLength )
939 // A buffer overrun handler for when invalid data is decompressed.
940 {
941 if ( context->forceDestCount == 0 )
942 {
943 return CX_ERR_DEST_OVERRUN;
944 }
945 lzLength = (u16)context->destCount;
946 }
947
948 context->destCount -= lzLength;
949 while ( lzLength-- )
950 {
951 *context->destp = *(context->destp - lzOffset);
952 ++context->destp;
953 }
954 length = 0;
955 nodep = context->huffTable9 + 1;
956 }
957 }
958
959 out:
960 context->stream = stream.stream;
961 context->stream_len = stream.stream_len;
962
963
964 // After decompression, remaining source data will be treated as an error
965 if ( (context->destCount == 0) &&
966 (context->forceDestCount == 0) &&
967 (len > 32) )
968 {
969 return CX_ERR_SRC_REMAINDER;
970 }
971
972 return context->destCount;
973
974 #undef OFFSET_BITS
975 #undef OFFSET_MASK
976 #undef LEAF_FLAG
977 }
978
979
980 // Structure for the range coder state
981 typedef struct
982 {
983 u32 low;
984 u32 range;
985 u32 code; // only used during decompression
986 u8 carry; // only used during compression
987 u32 carry_cnt; // only used during compression
988 }
989 RCState;
990
991 // Range coder structure
992 typedef struct
993 {
994 u32 *freq; // Table for occurrence frequency: (1 << bitSize) * sizeof(u32) bytes
995 u32 *low_cnt; // Table for the LOW border value: (1 << bitSize) * sizeof(u32) bytes
996 u32 total; // Total: 4 bytes
997 u8 bitSize; // Bit size: 1 byte
998 u8 padding_[1]; //
999 }
1000 RCCompressionInfo;
1001
1002 #define RC_MAX_RANGE 0x80000000
1003
1004 /*---------------------------------------------------------------------------*
1005 Name: LRCIntro_
1006
1007 Description: Processing to set up streaming loads
1008
1009 Arguments: context
1010 info8
1011 info9
1012 state
1013
1014 Returns: None.
1015 *---------------------------------------------------------------------------*/
1016 static inline void
LRCIntro_(CXUncompContextLRC * context,RCCompressionInfo * info9,RCCompressionInfo * info12,RCState * state)1017 LRCIntro_(
1018 CXUncompContextLRC *context,
1019 RCCompressionInfo *info9,
1020 RCCompressionInfo *info12,
1021 RCState *state )
1022 {
1023 info9->freq = context->freq9;
1024 info9->low_cnt = context->low_cnt9;
1025 info9->total = context->total9;
1026 info9->bitSize = 9;
1027
1028 info12->freq = context->freq12;
1029 info12->low_cnt = context->low_cnt12;
1030 info12->total = context->total12;
1031 info12->bitSize = 12;
1032
1033 state->low = context->low;
1034 state->range = context->range;
1035 state->code = context->code;
1036 state->carry = context->carry;
1037 state->carry_cnt = context->carry_cnt;
1038 }
1039
1040
1041 /*---------------------------------------------------------------------------*
1042 Name: LRCFin_
1043
1044 Description: Processing to stop streaming loads
1045
1046 Arguments: *context
1047 *info9
1048 *info12
1049 *state
1050
1051 Returns: None.
1052 *---------------------------------------------------------------------------*/
1053 static inline void
LRCFin_(CXUncompContextLRC * context,const RCCompressionInfo * info9,const RCCompressionInfo * info12,const RCState * state)1054 LRCFin_(
1055 CXUncompContextLRC *context,
1056 const RCCompressionInfo *info9,
1057 const RCCompressionInfo *info12,
1058 const RCState *state )
1059 {
1060 context->total9 = info9->total;
1061 context->total12 = info12->total;
1062
1063 context->low = state->low;
1064 context->range = state->range;
1065 context->code = state->code;
1066 context->carry = state->carry;
1067 context->carry_cnt = state->carry_cnt;
1068 }
1069
1070 /*---------------------------------------------------------------------------*
1071 Name: RCInitState_
1072
1073 Description: Initializes the RC state.
1074
1075 Arguments: state: Pointer to an RC state structure
1076
1077 Returns: None.
1078 *---------------------------------------------------------------------------*/
1079 static inline void
RCInitState_(RCState * state)1080 RCInitState_( RCState* state )
1081 {
1082 state->low = 0;
1083 state->range = RC_MAX_RANGE;
1084 state->code = 0;
1085 state->carry = 0;
1086 state->carry_cnt = 0;
1087 }
1088
1089 /*---------------------------------------------------------------------------*
1090 Name: RCInitInfo_
1091
1092 Description: Initialize the table for the adaptive range coder.
1093 All occurrence frequencies are initialized to 1.
1094
1095 Arguments: info: Pointer to an RC table information structure
1096
1097 Returns: None.
1098 *---------------------------------------------------------------------------*/
1099 static inline void
RCInitInfo_(RCCompressionInfo * info,u8 bitSize)1100 RCInitInfo_( RCCompressionInfo* info, u8 bitSize )
1101 {
1102 u32 tableSize = (u32)(1 << bitSize);
1103 u32 i;
1104
1105 info->bitSize = bitSize;
1106
1107 for ( i = 0; i < tableSize; i++ )
1108 {
1109 info->freq[ i ] = 1;
1110 info->low_cnt[ i ] = i;
1111 }
1112 info->total = tableSize;
1113 }
1114
1115
1116 /*---------------------------------------------------------------------------*
1117 Name: RCAAddCount_
1118
1119 Description: Updates the frequency table for an adaptive range coder.
1120
1121 Arguments: info: Table information for a range coder
1122 val: Value to add
1123
1124 Returns: None.
1125 *---------------------------------------------------------------------------*/
1126 static void
RCAddCount_(RCCompressionInfo * info,u16 val)1127 RCAddCount_( RCCompressionInfo* info, u16 val )
1128 {
1129 u32 i;
1130 u32 tableSize = (u32)(1 << info->bitSize);
1131
1132 info->freq[ val ]++;
1133 info->total++;
1134 for ( i = (u32)(val + 1); i < tableSize; i++ )
1135 {
1136 info->low_cnt[ i ]++;
1137 }
1138
1139 // Reconstruct if the total exceeds the maximum value.
1140 if ( info->total >= 0x00010000 )
1141 {
1142 if ( info->freq[ 0 ] > 1 )
1143 {
1144 info->freq[ 0 ] = info->freq[ 0 ] / 2;
1145 }
1146 info->low_cnt[ 0 ] = 0;
1147 info->total = info->freq[ 0 ];
1148
1149 for ( i = 1; i < tableSize; i++ )
1150 {
1151 if ( info->freq[ i ] > 1 )
1152 {
1153 info->freq[ i ] >>= 1;
1154 }
1155 info->low_cnt[ i ] = info->low_cnt[ i - 1 ] + info->freq[ i - 1 ];
1156 info->total += info->freq[ i ];
1157 }
1158 }
1159 }
1160
1161
1162 /*---------------------------------------------------------------------------*
1163 Name: RCSearch_
1164
1165 Description: Searches for the value that must be obtained next from the code, range, and low values.
1166
1167 Arguments: info: Table information for a range coder
1168 code: Current code value
1169 range: Current Range value
1170 low: Current Low value
1171
1172 Returns:
1173
1174 *---------------------------------------------------------------------------*/
1175 static u16
RCSearch_(RCCompressionInfo * info,u32 code,u32 range,u32 low)1176 RCSearch_( RCCompressionInfo* info, u32 code, u32 range, u32 low )
1177 {
1178 u32 tableSize = (u32)(1 << info->bitSize);
1179 u32 codeVal = code - low;
1180 u32 i;
1181 u32 temp = range / info->total;
1182 u32 tempVal = codeVal / temp;
1183
1184 // binary search
1185 u32 left = 0;
1186 u32 right = tableSize - 1;
1187
1188 while ( left < right )
1189 {
1190 i = (left + right) / 2;
1191
1192 if ( info->low_cnt[ i ] > tempVal )
1193 {
1194 right = i;
1195 }
1196 else
1197 {
1198 left = i + 1;
1199 }
1200 }
1201
1202 i = left;
1203 while ( info->low_cnt[ i ] > tempVal )
1204 {
1205 --i;
1206 }
1207 return (u16)i;
1208 }
1209
1210
1211 /*---------------------------------------------------------------------------*
1212 Name: RCGetData_
1213
1214 Description: Gets the next value from the state in RCState, then updates the state.
1215
1216 Arguments: stream
1217 info
1218 state
1219 adaptive
1220
1221 Returns:
1222
1223 *---------------------------------------------------------------------------*/
1224 static u16
RCGetData_(const u8 * srcp,RCCompressionInfo * info,RCState * state,u32 srcCnt,s32 * pReadCnt)1225 RCGetData_( const u8* srcp, RCCompressionInfo* info, RCState* state, u32 srcCnt, s32* pReadCnt )
1226 {
1227 #define MIN_RANGE 0x01000000
1228 u16 val = RCSearch_( info, state->code, state->range, state->low );
1229 s32 cnt = 0;
1230
1231 {
1232 u32 tmp;
1233 tmp = state->range / info->total;
1234 state->low += info->low_cnt[ val ] * tmp;
1235 state->range = info->freq[ val ] * tmp;
1236 }
1237
1238 // Update the table for occurrence frequency
1239 RCAddCount_( info, val );
1240
1241 while ( state->range < MIN_RANGE )
1242 {
1243 if ( srcCnt == 0 )
1244 {
1245 cnt = (cnt < 0 )? ( cnt - 1 ) : ( -1 );
1246 }
1247 else
1248 {
1249 state->code <<= 8;
1250 state->code += srcp[ cnt++ ];
1251 --srcCnt;
1252 }
1253 state->range <<= 8;
1254 state->low <<= 8;
1255 }
1256 *pReadCnt = cnt;
1257
1258 return val;
1259 #undef MIN_RANGE
1260 }
1261
1262
1263 /*---------------------------------------------------------------------------*
1264 Name: CXInitUncompContextLRC
1265
1266 Description: Initializes the streaming decompression context for LZ/Range Coder (combined) compressed data.
1267
1268 Arguments: context: Pointer to the decompressed context
1269 dest: Destination address for uncompressed data
1270
1271 Returns: None.
1272 *---------------------------------------------------------------------------*/
1273 void
CXInitUncompContextLRC(CXUncompContextLRC * context,void * dest)1274 CXInitUncompContextLRC( CXUncompContextLRC * context, void* dest )
1275 {
1276 #define LENGTH_BITS 9
1277 #define OFFSET_BITS 12
1278 RCCompressionInfo info9;
1279 RCCompressionInfo info12;
1280 RCState rcState;
1281
1282 // Set up processing
1283 LRCIntro_( context, &info9, &info12, &rcState );
1284
1285 context->destp = dest;
1286 context->destCount = 0;
1287 context->headerSize = 8;
1288 context->length = 0;
1289 context->forceDestCount = 0;
1290
1291 context->codeLen = 4;
1292
1293 RCInitInfo_( &info9, LENGTH_BITS );
1294 RCInitInfo_( &info12, OFFSET_BITS );
1295
1296 RCInitState_( &rcState );
1297
1298 // Stop processing
1299 LRCFin_( context, &info9, &info12, &rcState );
1300
1301 #undef LENGTH_BITS
1302 #undef OFFSET_BITS
1303 }
1304
1305
1306 /*---------------------------------------------------------------------------*
1307 Name: CXReadUncompLRC
1308
1309 Description: This function performs streaming decompression of LZ/Range Coder (combined) compressed data.
1310
1311 Arguments: *context: Pointer to the decompressed context
1312 data: Data pointer
1313 len: Data size
1314
1315 Returns: Size of remaining uncompressed data
1316 Returns a negative error code if failed.
1317 *---------------------------------------------------------------------------*/
1318 s32
CXReadUncompLRC(CXUncompContextLRC * context,const void * data,u32 len)1319 CXReadUncompLRC( CXUncompContextLRC *context, const void* data, u32 len )
1320 {
1321 RCCompressionInfo info9;
1322 RCCompressionInfo info12;
1323 RCState rcState;
1324 const u8* srcp = (const u8*)data;
1325
1326 // Set up processing
1327 LRCIntro_( context, &info9, &info12, &rcState );
1328
1329 // Header parsing
1330 if ( context->headerSize > 0 )
1331 {
1332 u32 read_len;
1333 if ( context->headerSize == 8 )
1334 {
1335 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LRC )
1336 {
1337 return CX_ERR_UNSUPPORTED;
1338 }
1339 if ( (*srcp & 0x0F) != 0 )
1340 {
1341 return CX_ERR_UNSUPPORTED;
1342 }
1343 }
1344
1345 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
1346 srcp += read_len;
1347 len -= read_len;
1348 if ( len == 0 )
1349 {
1350 return (context->headerSize == 0)? context->destCount : -1;
1351 }
1352 }
1353
1354 // load the code
1355 while ( context->codeLen > 0 )
1356 {
1357 if ( len == 0 )
1358 {
1359 goto out;
1360 }
1361 rcState.code <<= 8;
1362 rcState.code += *srcp;
1363 ++srcp;
1364 --len;
1365 --context->codeLen;
1366 }
1367
1368 while ( context->destCount > 0 )
1369 {
1370 // get the value for length
1371 if ( context->length == 0 )
1372 {
1373 s32 cnt;
1374 u16 val = RCGetData_( srcp, &info9, &rcState, len, &cnt );
1375
1376 if ( val < 0x100 )
1377 // uncompressed data
1378 {
1379 *context->destp++ = (u8)val;
1380 context->destCount--;
1381 }
1382 else
1383 // compressed data
1384 {
1385 context->length = (u16)( (val & 0xFF) + 3 );
1386 }
1387
1388 // prepare to read the next data
1389 if ( cnt < 0 )
1390 {
1391 context->codeLen = (u8)( -cnt );
1392 goto out;
1393 }
1394 srcp += cnt;
1395 len -= cnt;
1396 }
1397
1398 // Expanding compressed data
1399 if ( context->length > 0 )
1400 {
1401 s32 cnt;
1402 u16 val = (u16)( RCGetData_( srcp, &info12, &rcState, len, &cnt ) + 1 );
1403
1404 // A buffer overrun handler for when invalid data is decompressed.
1405 if ( context->length > context->destCount )
1406 {
1407 if ( context->forceDestCount == 0 )
1408 {
1409 return CX_ERR_DEST_OVERRUN;
1410 }
1411 context->length = (u16)( context->destCount );
1412 }
1413
1414 while ( context->length > 0 )
1415 {
1416 *context->destp = context->destp[ -val ];
1417 context->destp++;
1418 context->destCount--;
1419 context->length--;
1420 }
1421 // advance the load position
1422 if ( cnt < 0 )
1423 {
1424 context->codeLen = (u8)( -cnt );
1425 goto out;
1426 }
1427 srcp += cnt;
1428 len -= cnt;
1429 }
1430 }
1431 out:
1432 // Stop processing
1433 LRCFin_( context, &info9, &info12, &rcState );
1434
1435 // After decompression, remaining source data will be treated as an error
1436 if ( (context->destCount == 0) &&
1437 (context->forceDestCount == 0) &&
1438 (len > 32) )
1439 {
1440 return CX_ERR_SRC_REMAINDER;
1441 }
1442
1443 return context->destCount;
1444 }
1445
1446