1 /*---------------------------------------------------------------------------*
2 Project: Compress/uncompress library
3 File: CXUncompression.h
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 <dolphin/types.h>
16 #include <dolphin/os.h>
17 #include <revolution/cx/CXUncompression.h>
18 #include <revolution/cx/CXSecureUncompression.h>
19 #include "CXUtil.h"
20
21
22 //======================================================================
23 // Expanding compressed data
24 //======================================================================
25
26 /*---------------------------------------------------------------------------*
27 Name: CXSecureUncompressAny
28
29 Description: Determines the compression type from the data header and performs the appropriate decompression.
30
31 The decompression processes for all of the compression types are linked in this function. Therefore, unless some special kind of compression is being used, it is perhaps more effective to execute the compression-type-specific function instead.
32
33
34
35 Arguments: srcp Source address
36 srcSize Source size
37 destp Destination address
38
39 Returns: Returns 0 when conversion succeeds
40 Returns a negative error code if failed
41 *---------------------------------------------------------------------------*/
CXSecureUncompressAny(const void * srcp,u32 srcSize,void * destp)42 s32 CXSecureUncompressAny( const void* srcp, u32 srcSize, void* destp )
43 {
44 switch ( CXGetCompressionType( srcp ) )
45 {
46 // Run-length compressed data
47 case CX_COMPRESSION_RL:
48 return CXSecureUncompressRL( srcp, srcSize, destp );
49 // LZ77-compressed data
50 case CX_COMPRESSION_LZ:
51 return CXSecureUncompressLZ( srcp, srcSize, destp );
52 // Huffman-compressed data
53 case CX_COMPRESSION_HUFFMAN:
54 return CXSecureUncompressHuffman( srcp, srcSize, destp );
55 // Difference filter
56 case CX_COMPRESSION_DIFF:
57 return CXSecureUnfilterDiff( srcp, srcSize, destp );
58 default:
59 return CX_ERR_UNSUPPORTED;
60 }
61 }
62
63
64 /*---------------------------------------------------------------------------*
65 Name: CXSecureUncompressRL
66
67 Description: 8-bit decompression of run-length compressed data
68
69 - Decompresses run-length compressed data, writing in 8-bit units.
70 - Use 4 byte alignment for the source address.
71
72 - Data header
73 u32 :4 : Reserved
74 compType:4 : Compression type( = 3)
75 destSize:24 : Data size after decompression
76
77 - Flag data format
78 u8 length:7 : Decompressed data length - 1 (when not compressed)
79 Decompressed data length - 3 (only compress when the contiguous length is 3 bytes or greater)
80 flag:1 : (0, 1) = (not compressed, compressed)
81
82 Arguments: *srcp Source address
83 srcSize Source size
84 *destp Destination address
85
86 Returns: Returns 0 when conversion succeeds
87 Returns a negative error code if failed
88 *---------------------------------------------------------------------------*/
CXSecureUncompressRL(const void * srcp,u32 srcSize,void * destp)89 s32 CXSecureUncompressRL( const void *srcp, u32 srcSize, void *destp )
90 {
91 const u8 *pSrc = srcp;
92 u8 *pDst = destp;
93 u8 compType = (u8)( CXiConvertEndian_( *(u32*)pSrc ) & 0xFF );
94 u32 destCount = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
95 s32 srcCount = (s32)srcSize;
96
97 if ( (compType & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_RL )
98 {
99 return CX_ERR_UNSUPPORTED;
100 }
101 if ( (compType & 0xF) != 0 )
102 {
103 return CX_ERR_UNSUPPORTED;
104 }
105 if ( srcSize <= 4 )
106 {
107 return CX_ERR_SRC_SHORTAGE;
108 }
109
110 pSrc += 4;
111 srcCount -= 4;
112
113 if ( destCount == 0 )
114 {
115 if ( srcCount < 4 )
116 {
117 return CX_ERR_SRC_SHORTAGE;
118 }
119 destCount = CXiConvertEndian_( *(u32*)pSrc );
120 pSrc += 4;
121 srcCount -= 4;
122 }
123
124 while ( destCount > 0 )
125 {
126 u8 flags = *pSrc++;
127 s32 length = flags & 0x7f;
128 if ( --srcCount < 0 )
129 {
130 return CX_ERR_SRC_SHORTAGE;
131 }
132
133 if ( !(flags & 0x80) )
134 {
135 length++;
136 if ( length > destCount )
137 // A buffer overrun handler for when invalid data is decompressed.
138 {
139 return CX_ERR_DEST_OVERRUN;
140 }
141 srcCount -= length;
142 if ( srcCount < 0 )
143 {
144 return CX_ERR_SRC_SHORTAGE;
145 }
146
147 destCount -= length;
148 do
149 {
150 *pDst++ = *pSrc++;
151 } while ( --length > 0 );
152 }
153 else
154 {
155 u8 srcTmp;
156
157 length += 3;
158 if ( length > destCount )
159 // A buffer overrun handler for when invalid data is decompressed.
160 {
161 return CX_ERR_DEST_OVERRUN;
162 }
163
164 destCount -= length;
165 srcTmp = *pSrc++;
166 if ( --srcCount < 0 )
167 {
168 return CX_ERR_SRC_SHORTAGE;
169 }
170 do
171 {
172 *pDst++ = srcTmp;
173 } while ( --length > 0 );
174 }
175 }
176
177 if ( srcCount > 32 )
178 {
179 return CX_ERR_SRC_REMAINDER;
180 }
181
182 return CX_ERR_SUCCESS;
183 }
184
185
186 /*---------------------------------------------------------------------------*
187 Name: CXSecureUncompressLZ
188
189 Description: 8-bit decompression of LZ77-compressed data
190
191 * Expands LZ77-compressed data and writes it in 8-bit units.
192 - Use 4-byte alignment for the source address.
193
194 - Data header
195 u32 :4 : Reserved
196 compType:4 : Compression type( = 1)
197 destSize:24 : Data size after decompression
198
199 - Flag data format
200 u8 flags : Compression/no compression flag
201 (0, 1) = (not compressed, compressed)
202 - Code data format (Big Endian)
203 u16 length:4 : Decompressed data length - 3 (only compress when the match length is 3 bytes or greater)
204 offset:12 : Match data offset - 1
205
206 Arguments: *srcp Source address
207 srcSize Source size
208 *destp Destination address
209
210 Returns: Returns 0 when conversion succeeds
211 Returns a negative error code if failed
212 *---------------------------------------------------------------------------*/
CXSecureUncompressLZ(const void * srcp,u32 srcSize,void * destp)213 s32 CXSecureUncompressLZ( const void *srcp, u32 srcSize, void *destp )
214 {
215 const u8* pSrc = srcp;
216 u8* pDst = destp;
217 u8 compType = (u8)( CXiConvertEndian_( *(u32*)pSrc ) & 0xFF );
218 u32 destCount = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
219 s32 srcCount = (s32)srcSize;
220 BOOL exFormat = (*pSrc & 0x0F)? TRUE : FALSE;
221
222 if ( (compType & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LZ )
223 {
224 return CX_ERR_UNSUPPORTED;
225 }
226 if ( ((compType & 0xF) != 0x0) && ((compType & 0xF) != 0x1) )
227 {
228 return CX_ERR_UNSUPPORTED;
229 }
230 if ( srcSize <= 4 )
231 {
232 return CX_ERR_SRC_SHORTAGE;
233 }
234
235 pSrc += 4;
236 srcCount -= 4;
237
238 if ( destCount == 0 )
239 {
240 if ( srcCount < 4 )
241 {
242 return CX_ERR_SRC_SHORTAGE;
243 }
244
245 destCount = CXiConvertEndian_( *(u32*)pSrc );
246 pSrc += 4;
247 srcCount -= 4;
248 }
249
250 while ( destCount > 0 )
251 {
252 u32 i;
253 u32 flags = *pSrc++;
254 if ( --srcCount < 0 )
255 {
256 return CX_ERR_SRC_SHORTAGE;
257 }
258
259 for ( i = 0; i < 8; ++i )
260 {
261 if ( !(flags & 0x80) )
262 {
263 *pDst++ = *pSrc++;
264 if ( --srcCount < 0 )
265 {
266 return CX_ERR_SRC_SHORTAGE;
267 }
268 destCount--;
269 }
270 else
271 {
272 s32 length = (*pSrc >> 4);
273 s32 offset;
274
275 if ( ! exFormat )
276 {
277 length += 3;
278 }
279 else
280 {
281 // LZ77 extended format
282 if ( length == 1 )
283 {
284 length = (*pSrc++ & 0x0F) << 12;
285 length |= (*pSrc++) << 4;
286 length |= (*pSrc >> 4);
287 length += 0xFF + 0xF + 3;
288 srcCount -= 2;
289 }
290 else if ( length == 0 )
291 {
292 length = (*pSrc++ & 0x0F) << 4;
293 length |= (*pSrc >> 4);
294 length += 0xF + 2;
295 srcCount -= 1;
296 }
297 else
298 {
299 length += 1;
300 }
301 }
302 offset = (*pSrc++ & 0x0f) << 8;
303 offset = (offset | *pSrc++) + 1;
304
305 srcCount -= 2;
306 if ( srcCount < 0 )
307 {
308 return CX_ERR_SRC_SHORTAGE;
309 }
310
311 // A buffer overrun handler for when invalid data is decompressed.
312 if ( length > destCount )
313 {
314 return CX_ERR_DEST_OVERRUN;
315 }
316 if ( &pDst[ -offset ] < destp )
317 {
318 return CX_ERR_DEST_OVERRUN;
319 }
320
321 destCount -= length;
322 do
323 {
324 *pDst++ = pDst[ -offset ];
325 } while ( --length > 0 );
326 }
327 if ( destCount <= 0 )
328 {
329 break;
330 }
331 flags <<= 1;
332 }
333 }
334
335 if ( srcCount > 32 )
336 {
337 return CX_ERR_SRC_REMAINDER;
338 }
339
340 return CX_ERR_SUCCESS;
341 }
342
343
344 extern BOOL CXiVerifyHuffmanTable_( const void* pTable, u8 bit );
345 /*---------------------------------------------------------------------------*
346 Name: CXiVerifyHuffmanTable_
347
348 Description: Huffman table integrity check
349
350 Arguments: Pointer to the Huffman table
351
352 Returns: TRUE when the table is valid
353 FALSE when the table is invalid
354 *---------------------------------------------------------------------------*/
355 BOOL
CXiVerifyHuffmanTable_(const void * pTable,u8 bit)356 CXiVerifyHuffmanTable_( const void* pTable, u8 bit )
357 {
358 const u32 FLAGS_ARRAY_NUM = 512 / 8; /* 64 byte */
359 u8* treep = (u8*)pTable;
360 u8* treeStartp = treep + 1;
361 u32 treeSize = *treep;
362 u8* treeEndp = (u8*)pTable + (treeSize + 1) * 2;
363 u32 i;
364 u8 end_flags[ FLAGS_ARRAY_NUM ];
365 u32 idx;
366
367 for ( i = 0; i < FLAGS_ARRAY_NUM; i++ )
368 {
369 end_flags[ i ] = 0;
370 }
371
372 if ( bit == 4 )
373 {
374 if ( treeSize >= 0x10 )
375 {
376 return FALSE;
377 }
378 }
379
380 idx = 1;
381 treep = treeStartp;
382 while ( treep < treeEndp )
383 {
384 if ( (end_flags[ idx / 8 ] & (1 << (idx % 8) )) == 0 )
385 {
386 u32 offset = (u32)( ( (*treep & 0x3F) + 1 ) << 1);
387 u8* nodep = (u8*)( (((u32)treep >> 1) << 1) + offset );
388
389 // Skip data added at the end for alignment.
390 if ( *treep == 0 && idx >= (treeSize * 2) )
391 {
392 goto next;
393 }
394
395 if ( nodep >= treeEndp )
396 {
397 return FALSE;
398 }
399 if ( *treep & 0x80 )
400 {
401 u32 left = (idx & ~0x1) + offset;
402 end_flags[ left / 8 ] |= (u8)( 1 << (left % 8) );
403 }
404 if ( *treep & 0x40 )
405 {
406 u32 right = (idx & ~0x1) + offset + 1;
407 end_flags[ right / 8 ] |= (u8)( 1 << (right % 8) );
408 }
409 }
410 next:
411 ++idx;
412 ++treep;
413 }
414 return TRUE;
415 }
416
417
418 /*---------------------------------------------------------------------------*
419 Name: CXSecureUncompressHuffman
420
421 Description: Decompression of Huffman-compressed data
422
423 * Decompresses Huffman-compressed data, writing in 32-bit units.
424 - Use 4-byte alignment for the source address.
425 - Use 4-byte alignment for the destination address.
426 - The target decompression buffer size must be prepared in 4-byte multiples.
427
428 - Data header
429 u32 bitSize:4 : Bit size of 1 data (normally 4|8)
430 compType:4 : Compression type( = 2)
431 destSize:24 : Data size after decompression
432
433 - Tree table
434 u8 treeSize : Tree table size/2 - 1
435 TreeNodeData nodeRoot : Root node
436
437 TreeNodeData nodeLeft : Root left node
438 TreeNodeData nodeRight : Root right node
439
440 TreeNodeData nodeLeftLeft : Left left node
441 TreeNodeData nodeLeftRight : Left right node
442
443 TreeNodeData nodeRightLeft : Right left node
444 TreeNodeData nodeRightRight : Right right node
445
446 .
447 .
448
449 The compressed data itself follows
450
451 - TreeNodeData structure
452 u8 nodeNextOffset:6 : Offset to the next node data - 1 (2 byte units)
453 rightEndFlag:1 : Right node end flag
454 leftEndzflag:1 : Left node end flag
455 When the end flag is set
456 There is data in next node
457
458 Arguments: *srcp Source address
459 srcSize Source size
460 *destp Destination address
461
462 Returns: Returns 0 when conversion succeeds
463 Returns a negative error code if failed
464 *---------------------------------------------------------------------------*/
CXSecureUncompressHuffman(const void * srcp,u32 srcSize,void * destp)465 s32 CXSecureUncompressHuffman( const void *srcp, u32 srcSize, void *destp )
466 {
467 #define TREE_END 0x80
468 const u32 *pSrc = srcp;
469 u32 *pDst = destp;
470 u8 compType = (u8)( CXiConvertEndian_( *(u32*)pSrc ) & 0xFF );
471 s32 destCount = (s32)( CXiConvertEndian_( *pSrc ) >> 8 );
472 u8 *treep = (destCount != 0)? ((u8*)pSrc + 4) : ((u8*)pSrc + 8);
473 u8 *treeStartp = treep + 1;
474 u32 dataBit = *(u8*)pSrc & 0x0FU;
475 u32 destTmp = 0;
476 u32 destTmpCount = 0;
477 u32 destTmpDataNum = 4 + ( dataBit & 0x7 );
478 s32 srcCount = (s32)srcSize;
479 u32 treeSize = (u32)( (*treep + 1) << 1 );
480
481 if ( (compType & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_HUFFMAN )
482 {
483 return CX_ERR_UNSUPPORTED;
484 }
485 if ( (dataBit != 4) && (dataBit != 8) )
486 {
487 return CX_ERR_UNSUPPORTED;
488 }
489
490 if ( destCount == 0 )
491 {
492 if ( srcSize < 8 + treeSize )
493 {
494 return CX_ERR_SRC_SHORTAGE;
495 }
496 destCount = (s32)( CXiConvertEndian_( *(pSrc + 1) ) );
497 }
498 else if ( srcSize < 4 + treeSize )
499 {
500 return CX_ERR_SRC_SHORTAGE;
501 }
502
503 if ( ! CXiVerifyHuffmanTable_(treep, (u8)dataBit) )
504 {
505 return CX_ERR_ILLEGAL_TABLE;
506 }
507
508 pSrc = (u32*)( treep + treeSize );
509 srcCount -= ( (u32)pSrc - (u32)srcp );
510
511 if ( srcCount < 0 )
512 {
513 return CX_ERR_SRC_SHORTAGE;
514 }
515
516 treep = treeStartp;
517
518 while ( destCount > 0 )
519 {
520 s32 srcTmpCount = 32;
521 u32 srcTmp = CXiConvertEndian_( *pSrc++ ); // Endian strategy
522 srcCount -= 4;
523 if ( srcCount < 0 )
524 {
525 return CX_ERR_SRC_SHORTAGE;
526 }
527
528 while ( --srcTmpCount >= 0 )
529 {
530 u32 treeShift = (srcTmp >> 31) & 0x1;
531 u32 treeCheck = *treep;
532 treeCheck <<= treeShift;
533 treep = (u8*)( (((u32)treep >> 1) << 1) + (((*treep & 0x3f) + 1) << 1) + treeShift );
534 if ( treeCheck & TREE_END )
535 {
536 destTmp >>= dataBit;
537 destTmp |= *treep << (32 - dataBit);
538 treep = treeStartp;
539 ++destTmpCount;
540
541 if ( destCount <= (destTmpCount * dataBit) / 8 )
542 {
543 destTmp >>= (destTmpDataNum - destTmpCount) * dataBit;
544 destTmpCount = destTmpDataNum;
545 }
546
547 if ( destTmpCount == destTmpDataNum )
548 {
549 // Over-access until the last 4-byte alignment of the decompression buffer
550 *pDst++ = CXiConvertEndian_(destTmp); // Endian strategy
551 destCount -= 4;
552 destTmpCount = 0;
553 }
554 }
555 if ( destCount <= 0 )
556 {
557 break;
558 }
559 srcTmp <<= 1;
560 }
561 }
562 if ( srcCount > 32 )
563 {
564 return CX_ERR_SRC_REMAINDER;
565 }
566
567 return CX_ERR_SUCCESS;
568 }
569
570
571 /*---------------------------------------------------------------------------*
572 Name: CXiHuffImportTree
573
574 Description: Decompresses a resource's Huffman table into the work buffer.
575
576 Arguments: pTable: Pointer to a buffer for decompressing the Huffman table
577 srcp: Pointer to the resource data
578 bitSize: Size (in bits) of the Huffman table elements
579 srcRemainSize: Valid remaining data size contained in srcp
580
581 Returns: Returns the actual data size loaded from the resource.
582 *---------------------------------------------------------------------------*/
583 static u32
CXiHuffImportTree(u16 * pTable,const u8 * srcp,u8 bitSize,u32 srcRemainSize)584 CXiHuffImportTree( u16* pTable, const u8* srcp, u8 bitSize, u32 srcRemainSize )
585 {
586 u32 tableSize;
587 u32 idx = 1;
588 u32 data = 0;
589 u32 bitNum = 0;
590 u32 bitMask = (1 << bitSize) - 1U;
591 u32 srcCnt = 0;
592 const u32 MAX_IDX = (u32)( (1 << bitSize) * 2 );
593
594 if ( bitSize > 8 )
595 {
596 tableSize = CXiConvertEndian16_( *(u16*)srcp );
597 srcp += 2;
598 srcCnt += 2;
599 }
600 else
601 {
602 tableSize = *srcp;
603 srcp += 1;
604 srcCnt += 1;
605 }
606 tableSize = (tableSize + 1) * 4;
607 if ( srcRemainSize < tableSize )
608 {
609 return tableSize;
610 }
611
612 while ( srcCnt < tableSize )
613 {
614 while ( bitNum < bitSize )
615 {
616 data <<= 8;
617 data |= *srcp++;
618 ++srcCnt;
619 bitNum += 8;
620 }
621 if ( idx < MAX_IDX )
622 {
623 pTable[ idx++ ] = (u16)( ( data >> (bitNum - bitSize) ) & bitMask );
624 }
625 bitNum -= bitSize;
626 }
627 return tableSize;
628 }
629
630
631 /*---------------------------------------------------------------------------*
632 Name: CXSecureUnfilterDiff
633
634 Description: 8-bit decompression to restore differential filter conversion.
635
636 - Decompresses a differential filter, writing in 8-bit units.
637 - Use 4-byte alignment for the source address.
638
639 Arguments: *srcp Source address
640 *destp Destination address
641
642 Returns: Returns 0 when conversion succeeds
643 Returns a negative error code if failed
644 *---------------------------------------------------------------------------*/
CXSecureUnfilterDiff(register const void * srcp,u32 srcSize,register void * destp)645 s32 CXSecureUnfilterDiff( register const void *srcp, u32 srcSize, register void *destp )
646 {
647 const u8* pSrc = srcp;
648 u8* pDst = destp;
649 u32 bitSize = *pSrc & 0xFU;
650 u8 compType = (u8)( CXiConvertEndian_( *(u32*)pSrc ) & 0xFF );
651 s32 destCount = (s32)( CXiConvertEndian_( *(u32*)pSrc ) >> 8 );
652 u32 sum = 0;
653 s32 srcCount = (s32)srcSize;
654
655 if ( (compType & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_DIFF )
656 {
657 return CX_ERR_UNSUPPORTED;
658 }
659 if ( (bitSize != 0) && (bitSize != 1) )
660 {
661 return CX_ERR_UNSUPPORTED;
662 }
663 if ( srcSize <= 4 )
664 {
665 return CX_ERR_SRC_SHORTAGE;
666 }
667
668 pSrc += 4;
669 srcCount -= 4;
670
671 if ( bitSize != 1 )
672 {
673 // Difference calculation in units of 8 bits
674 do
675 {
676 u8 tmp = *(pSrc++);
677 if ( --srcCount < 0 )
678 {
679 return CX_ERR_SRC_SHORTAGE;
680 }
681 destCount--;
682 sum += tmp;
683 *(pDst++) = (u8)sum;
684 } while ( destCount > 0 );
685 }
686 else
687 {
688 // Difference calculation in units of 16 bits
689 do
690 {
691 u16 tmp = CXiConvertEndian16_( *(u16*)pSrc );
692 pSrc += 2;
693 srcCount -= 2;
694 if ( srcCount < 0 )
695 {
696 return CX_ERR_SRC_SHORTAGE;
697 }
698 destCount -= 2;
699 sum += tmp;
700 *(u16*)pDst = CXiConvertEndian16_( (u16)sum );
701 pDst += 2;
702 } while ( destCount > 0 );
703 }
704 if ( srcCount > 32 )
705 {
706 return CX_ERR_SRC_REMAINDER;
707 }
708
709 return CX_ERR_SUCCESS;
710 }
711
712
713 typedef struct
714 {
715 const u8* srcp;
716 u32 cnt;
717 u32 stream;
718 u32 stream_len;
719 u32 srcSize;
720 }
721 BitReader;
722
723 static inline void
BitReader_Init(BitReader * context,const u8 * srcp,u32 srcSize)724 BitReader_Init( BitReader* context, const u8* srcp, u32 srcSize )
725 {
726 context->srcp = srcp;
727 context->cnt = 0;
728 context->stream = 0;
729 context->stream_len = 0;
730 context->srcSize = srcSize;
731 }
732
733 static s8
BitReader_Read(BitReader * context)734 BitReader_Read( BitReader* context )
735 {
736 s8 bit;
737 if ( context->stream_len == 0 )
738 {
739 if ( context->cnt > context->srcSize )
740 {
741 return -1;
742 }
743
744 context->stream = context->srcp[context->cnt++];
745 context->stream_len = 8;
746 }
747 bit = (s8)( (context->stream >> (context->stream_len - 1)) & 0x1 );
748 context->stream_len--;
749 return bit;
750 }
751
752 #define ENC_OFFSET_WIDTH
753
754 extern BOOL CXiLHVerifyTable( const void* pTable, u8 bit );
755 /*---------------------------------------------------------------------------*
756 Name: CXiLHVerifyTable
757
758 Description: Huffman table integrity check
759
760 Arguments: pTable: Pointer to the Huffman table
761 bit: Number of bits used by the Huffman coding
762
763 Returns: TRUE when the table is valid
764 FALSE when the table is invalid
765 *---------------------------------------------------------------------------*/
766 BOOL
CXiLHVerifyTable(const void * pTable,u8 bit)767 CXiLHVerifyTable( const void* pTable, u8 bit )
768 {
769 #if !defined(ENC_OFFSET_WIDTH)
770 enum { FLAGS_ARRAY_NUM = 8192 / 8 }; /* 1024 bytes */
771 static u8 end_flags[ FLAGS_ARRAY_NUM ];
772 #else
773 enum { FLAGS_ARRAY_NUM = 1024 / 8 }; /* 128 bytes */
774 u8 end_flags[ FLAGS_ARRAY_NUM ];
775 #endif
776 u16* treep = (u16*)pTable;
777 u16* treeStartp = treep + 1;
778 u32 treeSize = *treep;
779 u16* treeEndp = (u16*)pTable + treeSize;
780 u32 i;
781 u32 idx;
782 const u16 ofs_mask = (u16)( (1 << (bit - 2)) - 1 );
783 const u16 l_mask = (u16)( 1 << (bit - 1) );
784 const u16 r_mask = (u16)( 1 << (bit - 2) );
785
786 for ( i = 0; i < FLAGS_ARRAY_NUM; i++ )
787 {
788 end_flags[ i ] = 0;
789 }
790
791 if ( treeSize > (1U << (bit + 1)) )
792 {
793 return FALSE;
794 }
795
796 idx = 1;
797 treep = treeStartp;
798 while ( treep < treeEndp )
799 {
800 if ( (end_flags[ idx / 8 ] & (1 << (idx % 8) )) == 0 )
801 {
802 u32 offset = (u32)( ( (*treep & ofs_mask) + 1 ) << 1 );
803 u16* nodep = (u16*)((u32)treep & ~0x3) + offset;
804
805 // Skip data added at the end for alignment.
806 if ( *treep == 0 && idx >= treeSize - 4 )
807 {
808 goto next;
809 }
810 if ( nodep >= treeEndp )
811 {
812 return FALSE;
813 }
814 if ( *treep & l_mask )
815 {
816 u32 left = (idx & ~0x1) + offset;
817 end_flags[ left / 8 ] |= (u8)( 1 << (left % 8) );
818 }
819 if ( *treep & r_mask )
820 {
821 u32 right = (idx & ~0x1) + offset + 1;
822 end_flags[ right / 8 ] |= (u8)( 1 << (right % 8) );
823 }
824 }
825 next:
826 ++idx;
827 ++treep;
828 }
829 return TRUE;
830 }
831
832
833 /*---------------------------------------------------------------------------*
834 Name: CXUncompressLH
835
836 Description: Decompress LZ-Huffman (combined) compression.
837
838 Arguments: *srcp Source address
839 srcSize Source size
840 *destp Destination address
841 *work Working buffer
842 The required size is CX_UNCOMPRESS_LH_WORK_SIZE (18 KB)
843
844 Returns: Returns 0 when conversion succeeds
845 Returns a negative error code if failed
846 *---------------------------------------------------------------------------*/
847 s32
CXSecureUncompressLH(const u8 * srcp,u32 srcSize,u8 * dstp,void * work)848 CXSecureUncompressLH( const u8* srcp, u32 srcSize, u8* dstp, void* work )
849 {
850 #define LENGTH_BITS 9
851 #if defined(ENC_OFFSET_WIDTH)
852 #define OFFSET_BITS 5
853 #define OFFSET_MASK 0x07
854 #define LEAF_FLAG 0x10
855 u16 offset_bit;
856 #else
857 #define OFFSET_BITS 12
858 #define OFFSET_MASK 0x3FF
859 #define LEAF_FLAG 0x800
860 #endif
861 u32 dstSize;
862 u32 dstCnt = 0;
863 const u8 *pSrc = srcp;
864 BitReader stream;
865 u16* huffTable9; // Huffman table for length
866 u16* huffTable12; // Huffman table for offset
867 u8* verify_work; // For checking out-of-bounds accesses in the Huffman table (TODO: Not yet used)
868
869 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LH )
870 {
871 return CX_ERR_UNSUPPORTED;
872 }
873 if ( srcSize <= 4 )
874 {
875 return CX_ERR_SRC_SHORTAGE;
876 }
877
878 huffTable9 = work;
879 huffTable12 = (u16*)work + (1 << LENGTH_BITS) * 2;
880 verify_work = (u8*)work + CX_UNCOMPRESS_LH_WORK_SIZE;
881
882 // load the header
883 dstSize = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
884 pSrc += 4;
885 if ( dstSize == 0 )
886 {
887 dstSize = CXiConvertEndian_( *(u32*)pSrc );
888 pSrc += 4;
889 if ( srcSize < 8 )
890 {
891 return CX_ERR_SRC_SHORTAGE;
892 }
893 }
894
895 // read the Huffman table
896 pSrc += CXiHuffImportTree( huffTable9, pSrc, LENGTH_BITS, srcSize - ((u32)pSrc - (u32)srcp) );
897 if ( pSrc > srcp + srcSize )
898 {
899 return CX_ERR_SRC_SHORTAGE;
900 }
901 if ( ! CXiLHVerifyTable( huffTable9, LENGTH_BITS ) )
902 {
903 return CX_ERR_ILLEGAL_TABLE;
904 }
905 pSrc += CXiHuffImportTree( huffTable12, pSrc, OFFSET_BITS, srcSize - ((u32)pSrc - (u32)srcp) );
906 if ( pSrc > srcp + srcSize )
907 {
908 return CX_ERR_SRC_SHORTAGE;
909 }
910 if ( ! CXiLHVerifyTable( huffTable12, OFFSET_BITS ) )
911 {
912 return CX_ERR_ILLEGAL_TABLE;
913 }
914
915 BitReader_Init( &stream, pSrc, srcSize - ((u32)pSrc - (u32)srcp) );
916
917 while ( dstCnt < dstSize )
918 {
919 u16* nodep = huffTable9 + 1;
920 u16 val;
921 do
922 {
923 s8 bit = BitReader_Read( &stream );
924 u32 offset = (((*nodep & 0x7F) + 1U) << 1) + bit;
925 if ( bit < 0 )
926 {
927 return CX_ERR_SRC_SHORTAGE;
928 }
929
930 if ( *nodep & (0x100 >> bit) )
931 {
932 nodep = (u16*)((u32)nodep & ~0x3);
933 val = *(nodep + offset);
934 break;
935 }
936 else
937 {
938 nodep = (u16*)((u32)nodep & ~0x3);
939 nodep += offset;
940 }
941 } while ( 1 );
942
943 if ( val < 0x100 )
944 // uncompressed data
945 {
946 dstp[dstCnt++] = (u8)val;
947 }
948 else
949 // compressed data
950 {
951 u16 length = (u16)( (val & 0xFF) + 3 );
952 u16* nodep = huffTable12 + 1;
953 do
954 {
955 s8 bit = BitReader_Read( &stream );
956 u32 offset = (((*nodep & OFFSET_MASK) + 1U) << 1) + bit;
957
958 if ( bit < 0 )
959 {
960 return CX_ERR_SRC_SHORTAGE;
961 }
962
963 if ( *nodep & (LEAF_FLAG >> bit) )
964 {
965 nodep = (u16*)((u32)nodep & ~0x3);
966 val = *(nodep + offset);
967 break;
968 }
969 else
970 {
971 nodep = (u16*)((u32)nodep & ~0x3);
972 nodep += offset;
973 }
974 } while ( 1 );
975
976 #if defined(ENC_OFFSET_WIDTH)
977 offset_bit = val;
978 val = 0;
979 if ( offset_bit > 0 )
980 {
981 val = 1;
982 while ( --offset_bit > 0 )
983 {
984 val <<= 1;
985 val |= BitReader_Read( &stream );
986 }
987 }
988 #endif
989 val += 1;
990
991 if ( dstCnt - val < 0 )
992 {
993 return CX_ERR_DEST_OVERRUN;
994 }
995 if ( dstCnt + length > dstSize )
996 {
997 return CX_ERR_DEST_OVERRUN;
998 }
999
1000 while ( length-- > 0 )
1001 {
1002 dstp[dstCnt] = dstp[dstCnt - val];
1003 ++dstCnt;
1004 }
1005 }
1006 }
1007
1008 if ( stream.srcSize - stream.cnt > 32 )
1009 {
1010 return CX_ERR_SRC_REMAINDER;
1011 }
1012
1013 return CX_ERR_SUCCESS;
1014
1015 #undef OFFSET_BITS
1016 #undef OFFSET_MASK
1017 #undef LEAF_FLAG
1018 }
1019
1020
1021
1022
1023 // Structure for the range coder state
1024 typedef struct
1025 {
1026 u32 low;
1027 u32 range;
1028 u32 code; // only used during decompression
1029 u8 carry; // only used during compression
1030 u32 carry_cnt; // only used during compression
1031 }
1032 RCState;
1033
1034 // Range coder structure
1035 typedef struct
1036 {
1037 u32 *freq; // Table for occurrence frequency: (1 << bitSize) * sizeof(u32) bytes
1038 u32 *low_cnt; // Table for the LOW border value: (1 << bitSize) * sizeof(u32) bytes
1039 u32 total; // Total: 4 bytes
1040 u8 bitSize; // Bit size: 1 byte
1041 u8 padding_[1]; //
1042 }
1043 RCCompressionInfo;
1044
1045 #define RC_MAX_RANGE 0x80000000
1046
1047
1048 /*---------------------------------------------------------------------------*
1049 Name: RCInitState_
1050
1051 Description: Initializes the RC state.
1052
1053 Arguments: state: Pointer to an RC state structure
1054
1055 Returns: None.
1056 *---------------------------------------------------------------------------*/
1057 static inline void
RCInitState_(RCState * state)1058 RCInitState_( RCState* state )
1059 {
1060 // The starting range is 0x80000000, so a carry will not suddenly occur the first time
1061 state->low = 0;
1062 state->range = RC_MAX_RANGE;
1063 state->code = 0;
1064 state->carry = 0;
1065 state->carry_cnt = 0;
1066 }
1067
1068 /*---------------------------------------------------------------------------*
1069 Name: RCInitInfo_
1070
1071 Description: Initialize the table for the adaptive range coder.
1072 All occurrence frequencies are initialized to 1.
1073
1074 Arguments: info: Pointer to an RC table information structure
1075
1076 Returns: None.
1077 *---------------------------------------------------------------------------*/
1078 static inline void
RCInitInfo_(RCCompressionInfo * info,u8 bitSize,void * work)1079 RCInitInfo_( RCCompressionInfo* info, u8 bitSize, void* work )
1080 {
1081 u32 tableSize = (u32)(1 << bitSize);
1082 u32 i;
1083
1084 info->bitSize = bitSize;
1085 info->freq = (u32*)work;
1086 info->low_cnt = (u32*)( (u32)work + tableSize * sizeof(u32) );
1087
1088 for ( i = 0; i < tableSize; i++ )
1089 {
1090 info->freq[ i ] = 1;
1091 info->low_cnt[ i ] = i;
1092 }
1093 info->total = tableSize;
1094 }
1095
1096 /*---------------------------------------------------------------------------*
1097 Name: RCAAddCount_
1098
1099 Description: Updates the frequency table for an adaptive range coder.
1100
1101 Arguments: info: Table information for a range coder
1102 val: Value to add
1103
1104 Returns: None.
1105 *---------------------------------------------------------------------------*/
1106 static void
RCAddCount_(RCCompressionInfo * info,u16 val)1107 RCAddCount_( RCCompressionInfo* info, u16 val )
1108 {
1109 u32 i;
1110 u32 tableSize = (u32)(1 << info->bitSize);
1111
1112 info->freq[ val ]++;
1113 info->total++;
1114 for ( i = (u32)(val + 1); i < tableSize; i++ )
1115 {
1116 info->low_cnt[ i ]++;
1117 }
1118
1119 // Reconstruct if the total exceeds the maximum value.
1120 if ( info->total >= 0x00010000 )
1121 {
1122 if ( info->freq[ 0 ] > 1 )
1123 {
1124 info->freq[ 0 ] = info->freq[ 0 ] / 2;
1125 }
1126 info->low_cnt[ 0 ] = 0;
1127 info->total = info->freq[ 0 ];
1128
1129 for ( i = 1; i < tableSize; i++ )
1130 {
1131 if ( info->freq[ i ] > 1 )
1132 {
1133 info->freq[ i ] >>= 1;
1134 }
1135 info->low_cnt[ i ] = info->low_cnt[ i - 1 ] + info->freq[ i - 1 ];
1136 info->total += info->freq[ i ];
1137 }
1138 }
1139 }
1140
1141
1142 /*---------------------------------------------------------------------------*
1143 Name: RCSearch_
1144
1145 Description: Searches for the value that must be obtained next from the code, range, and low values.
1146
1147 Arguments: info: Table information for a range coder
1148 code: Current code value
1149 range: Current Range value
1150 low: Current Low value
1151
1152 Returns:
1153
1154 *---------------------------------------------------------------------------*/
1155 static u16
RCSearch_(RCCompressionInfo * info,u32 code,u32 range,u32 low)1156 RCSearch_( RCCompressionInfo* info, u32 code, u32 range, u32 low )
1157 {
1158 u32 tableSize = (u32)(1 << info->bitSize);
1159 u32 codeVal = code - low;
1160 u32 i;
1161 u32 temp = range / info->total;
1162 u32 tempVal = codeVal / temp;
1163
1164 // binary search
1165 u32 left = 0;
1166 u32 right = tableSize - 1;
1167
1168 while ( left < right )
1169 {
1170 i = (left + right) / 2;
1171
1172 if ( info->low_cnt[ i ] > tempVal )
1173 {
1174 right = i;
1175 }
1176 else
1177 {
1178 left = i + 1;
1179 }
1180 }
1181
1182 i = left;
1183 while ( info->low_cnt[ i ] > tempVal )
1184 {
1185 --i;
1186 }
1187 return (u16)i;
1188 }
1189
1190
1191 /*---------------------------------------------------------------------------*
1192 Name: RCGetData_
1193
1194 Description: Gets the next value from the state in RCState, then updates the state.
1195
1196 Arguments: stream
1197 info
1198 state
1199 adaptive
1200
1201 Returns:
1202
1203 *---------------------------------------------------------------------------*/
1204 static u16
RCGetData_(const u8 * srcp,RCCompressionInfo * info,RCState * state,u32 * pSrcCnt)1205 RCGetData_( const u8* srcp, RCCompressionInfo* info, RCState* state, u32* pSrcCnt )
1206 {
1207 #define MIN_RANGE 0x01000000
1208 u16 val = RCSearch_( info, state->code, state->range, state->low );
1209 u32 cnt = 0;
1210
1211 {
1212 u32 tmp;
1213 tmp = state->range / info->total;
1214 state->low += info->low_cnt[ val ] * tmp;
1215 state->range = info->freq[ val ] * tmp;
1216 }
1217
1218 // Update the table for occurrence frequency
1219 RCAddCount_( info, val );
1220
1221 while ( state->range < MIN_RANGE )
1222 {
1223 state->code <<= 8;
1224 state->code += srcp[ cnt++ ];
1225 state->range <<= 8;
1226 state->low <<= 8;
1227 }
1228 *pSrcCnt = cnt;
1229
1230 return val;
1231 #undef MIN_RANGE
1232 }
1233
1234
1235 /*---------------------------------------------------------------------------*
1236 Name: CXSecureUncompressLRC
1237
1238 Description: LZ/Range Coder combined compression
1239
1240 Arguments: srcp
1241 dstp
1242 work
1243
1244 Returns: None.
1245 *---------------------------------------------------------------------------*/
1246 s32
CXSecureUncompressLRC(const u8 * srcp,u32 srcSize,u8 * dstp,void * work)1247 CXSecureUncompressLRC( const u8* srcp, u32 srcSize, u8* dstp, void* work )
1248 {
1249 #define LENGTH_BITS 9
1250 #define OFFSET_BITS 12
1251 RCCompressionInfo infoVal;
1252 RCCompressionInfo infoOfs;
1253 RCState rcState;
1254 const u8* pSrc = srcp;
1255 u32 dstCnt = 0;
1256 u32 dstSize = 0;
1257
1258 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LRC )
1259 {
1260 return CX_ERR_UNSUPPORTED;
1261 }
1262 if ( srcSize <= 4 )
1263 {
1264 return CX_ERR_SRC_SHORTAGE;
1265 }
1266
1267 RCInitInfo_( &infoVal, LENGTH_BITS, work );
1268 RCInitInfo_( &infoOfs, OFFSET_BITS, (u8*)work + (1 << LENGTH_BITS) * sizeof(u32) * 2 );
1269 RCInitState_( &rcState );
1270
1271 // load the header
1272 dstSize = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
1273 pSrc += 4;
1274 if ( dstSize == 0 )
1275 {
1276 dstSize = CXiConvertEndian_( *(u32*)pSrc );
1277 pSrc += 4;
1278 if ( srcSize < 8 )
1279 {
1280 return CX_ERR_SRC_SHORTAGE;
1281 }
1282 }
1283
1284 // load the initial code
1285 if ( srcSize - ((u32)pSrc - (u32)srcp) < 4 )
1286 {
1287 return CX_ERR_SRC_SHORTAGE;
1288 }
1289 rcState.code = (u32)( (*pSrc << 24) |
1290 (*(pSrc + 1) << 16) |
1291 (*(pSrc + 2) << 8) |
1292 (*(pSrc + 3) ) );
1293 pSrc += 4;
1294
1295 // continue to get values from the range coder and perform LZ decompression
1296 while ( dstCnt < dstSize )
1297 {
1298 u32 cnt;
1299 u16 val = (u16)( RCGetData_( pSrc, &infoVal, &rcState, &cnt ) );
1300 pSrc += cnt;
1301
1302 if ( val < 0x100 )
1303 // uncompressed data
1304 {
1305 dstp[ dstCnt++ ] = (u8)val;
1306 }
1307 else
1308 // compressed data
1309 {
1310 u16 length = (u16)( (val & 0xFF) + 3 );
1311 val = (u16)( RCGetData_( pSrc, &infoOfs, &rcState, &cnt ) + 1 );
1312 pSrc += cnt;
1313
1314 // check for a buffer overrun
1315 if ( dstCnt + length > dstSize )
1316 {
1317 return CX_ERR_DEST_OVERRUN;
1318 }
1319 if ( dstCnt < val )
1320 {
1321 return CX_ERR_DEST_OVERRUN;
1322 }
1323 if ( ((u32)pSrc - (u32)srcp) > srcSize )
1324 {
1325 return CX_ERR_SRC_SHORTAGE;
1326 }
1327
1328 while ( length-- > 0 )
1329 {
1330 dstp[ dstCnt ] = dstp[ dstCnt - val ];
1331 ++dstCnt;
1332 }
1333 }
1334 }
1335 return CX_ERR_SUCCESS;
1336 #undef LENGTH_BITS
1337 #undef OFFSET_BITS
1338 }
1339