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