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 // The number of Huffman table elements is in srcp.
595 // When bitSize is 8 or less, the range is from 0 to 255 and can therefore fit within 1 byte.
596 // Beyond that, the size information is stored across 2 bytes.
597 if ( bitSize > 8 )
598 {
599 tableSize = CXiConvertEndian16_( *(u16*)srcp );
600 srcp += 2;
601 srcCnt += 2;
602 }
603 else
604 {
605 tableSize = *srcp;
606 srcp += 1;
607 srcCnt += 1;
608 }
609
610 // The actual number of table bytes is sizeof(u16) * 2
611 tableSize = (tableSize + 1) * 4;
612
613 if ( srcRemainSize < tableSize )
614 {
615 return tableSize;
616 }
617
618 while ( srcCnt < tableSize )
619 {
620 while ( bitNum < bitSize )
621 {
622 data <<= 8;
623 data |= *srcp++;
624 ++srcCnt;
625 bitNum += 8;
626 }
627 if ( idx < MAX_IDX )
628 {
629 pTable[ idx++ ] = (u16)( ( data >> (bitNum - bitSize) ) & bitMask );
630 }
631 bitNum -= bitSize;
632 }
633
634 pTable[0] = (u16)idx;
635
636 return tableSize;
637 }
638
639
640 /*---------------------------------------------------------------------------*
641 Name: CXSecureUnfilterDiff
642
643 Description: 8-bit decompression to restore differential filter conversion.
644
645 - Decompresses a differential filter, writing in 8-bit units.
646 - Use 4-byte alignment for the source address.
647
648 Arguments: *srcp Source address
649 *destp Destination address
650
651 Returns: Returns 0 when conversion succeeds
652 Returns a negative error code if failed
653 *---------------------------------------------------------------------------*/
CXSecureUnfilterDiff(register const void * srcp,u32 srcSize,register void * destp)654 s32 CXSecureUnfilterDiff( register const void *srcp, u32 srcSize, register void *destp )
655 {
656 const u8* pSrc = srcp;
657 u8* pDst = destp;
658 u32 bitSize = *pSrc & 0xFU;
659 u8 compType = (u8)( CXiConvertEndian_( *(u32*)pSrc ) & 0xFF );
660 s32 destCount = (s32)( CXiConvertEndian_( *(u32*)pSrc ) >> 8 );
661 u32 sum = 0;
662 s32 srcCount = (s32)srcSize;
663
664 if ( (compType & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_DIFF )
665 {
666 return CX_ERR_UNSUPPORTED;
667 }
668 if ( (bitSize != 0) && (bitSize != 1) )
669 {
670 return CX_ERR_UNSUPPORTED;
671 }
672 if ( srcSize <= 4 )
673 {
674 return CX_ERR_SRC_SHORTAGE;
675 }
676
677 pSrc += 4;
678 srcCount -= 4;
679
680 if ( bitSize != 1 )
681 {
682 // Difference calculation in units of 8 bits
683 do
684 {
685 u8 tmp = *(pSrc++);
686 if ( --srcCount < 0 )
687 {
688 return CX_ERR_SRC_SHORTAGE;
689 }
690 destCount--;
691 sum += tmp;
692 *(pDst++) = (u8)sum;
693 } while ( destCount > 0 );
694 }
695 else
696 {
697 // Difference calculation in units of 16 bits
698 do
699 {
700 u16 tmp = CXiConvertEndian16_( *(u16*)pSrc );
701 pSrc += 2;
702 srcCount -= 2;
703 if ( srcCount < 0 )
704 {
705 return CX_ERR_SRC_SHORTAGE;
706 }
707 destCount -= 2;
708 sum += tmp;
709 *(u16*)pDst = CXiConvertEndian16_( (u16)sum );
710 pDst += 2;
711 } while ( destCount > 0 );
712 }
713 if ( srcCount > 32 )
714 {
715 return CX_ERR_SRC_REMAINDER;
716 }
717
718 return CX_ERR_SUCCESS;
719 }
720
721
722 typedef struct
723 {
724 const u8* srcp;
725 u32 cnt;
726 u32 stream;
727 u32 stream_len;
728 u32 srcSize;
729 }
730 BitReader;
731
732 static inline void
BitReader_Init(BitReader * context,const u8 * srcp,u32 srcSize)733 BitReader_Init( BitReader* context, const u8* srcp, u32 srcSize )
734 {
735 context->srcp = srcp;
736 context->cnt = 0;
737 context->stream = 0;
738 context->stream_len = 0;
739 context->srcSize = srcSize;
740 }
741
742 static s8
BitReader_Read(BitReader * context)743 BitReader_Read( BitReader* context )
744 {
745 s8 bit;
746 if ( context->stream_len == 0 )
747 {
748 if ( context->cnt > context->srcSize )
749 {
750 return -1;
751 }
752
753 context->stream = context->srcp[context->cnt++];
754 context->stream_len = 8;
755 }
756 bit = (s8)( (context->stream >> (context->stream_len - 1)) & 0x1 );
757 context->stream_len--;
758 return bit;
759 }
760
761 #define ENC_OFFSET_WIDTH
762
763 extern BOOL CXiLHVerifyTable( const void* pTable, u8 bit );
764 /*---------------------------------------------------------------------------*
765 Name: CXiLHVerifyTable
766
767 Description: Huffman table integrity check
768
769 Arguments: pTable: Pointer to the Huffman table
770 bit: Number of bits used by the Huffman coding
771
772 Returns: TRUE when the table is valid
773 FALSE when the table is invalid
774 *---------------------------------------------------------------------------*/
775 BOOL
CXiLHVerifyTable(const void * pTable,u8 bit)776 CXiLHVerifyTable( const void* pTable, u8 bit )
777 {
778 #if !defined(ENC_OFFSET_WIDTH)
779 enum { FLAGS_ARRAY_NUM = 8192 / 8 }; /* 1024 bytes */
780 static u8 end_flags[ FLAGS_ARRAY_NUM ];
781 #else
782 enum { FLAGS_ARRAY_NUM = 1024 / 8 }; /* 128 bytes */
783 u8 end_flags[ FLAGS_ARRAY_NUM ];
784 #endif
785 u16* treep = (u16*)pTable;
786 u16* treeStartp = treep + 1;
787 u32 treeSize = *treep;
788 u16* treeEndp = (u16*)pTable + treeSize;
789 u32 i;
790 u32 idx;
791 const u16 ofs_mask = (u16)( (1 << (bit - 2)) - 1 );
792 const u16 l_mask = (u16)( 1 << (bit - 1) );
793 const u16 r_mask = (u16)( 1 << (bit - 2) );
794
795 for ( i = 0; i < FLAGS_ARRAY_NUM; i++ )
796 {
797 end_flags[ i ] = 0;
798 }
799
800 if ( treeSize > (1U << (bit + 1)) )
801 {
802 return FALSE;
803 }
804
805 idx = 1;
806 treep = treeStartp;
807 while ( treep < treeEndp )
808 {
809 if ( (end_flags[ idx / 8 ] & (1 << (idx % 8) )) == 0 )
810 {
811 u32 offset = (u32)( ( (*treep & ofs_mask) + 1 ) << 1 );
812 u16* nodep = (u16*)((u32)treep & ~0x3) + offset;
813
814 // Skip data added at the end for alignment.
815 if ( *treep == 0 && idx >= treeSize - 4 )
816 {
817 goto next;
818 }
819 if ( nodep >= treeEndp )
820 {
821 return FALSE;
822 }
823 if ( *treep & l_mask )
824 {
825 u32 left = (idx & ~0x1) + offset;
826 end_flags[ left / 8 ] |= (u8)( 1 << (left % 8) );
827 }
828 if ( *treep & r_mask )
829 {
830 u32 right = (idx & ~0x1) + offset + 1;
831 end_flags[ right / 8 ] |= (u8)( 1 << (right % 8) );
832 }
833 }
834 next:
835 ++idx;
836 ++treep;
837 }
838 return TRUE;
839 }
840
841
842 /*---------------------------------------------------------------------------*
843 Name: CXUncompressLH
844
845 Description: Decompress LZ-Huffman (combined) compression.
846
847 Arguments: *srcp Source address
848 srcSize Source size
849 *destp Destination address
850 *work Working buffer
851 The required size is CX_UNCOMPRESS_LH_WORK_SIZE (18 KB)
852
853 Returns: Returns 0 when conversion succeeds
854 Returns a negative error code if failed
855 *---------------------------------------------------------------------------*/
856 s32
CXSecureUncompressLH(const u8 * srcp,u32 srcSize,u8 * dstp,void * work)857 CXSecureUncompressLH( const u8* srcp, u32 srcSize, u8* dstp, void* work )
858 {
859 #define LENGTH_BITS 9
860 #if defined(ENC_OFFSET_WIDTH)
861 #define OFFSET_BITS 5
862 #define OFFSET_MASK 0x07
863 #define LEAF_FLAG 0x10
864 u16 offset_bit;
865 #else
866 #define OFFSET_BITS 12
867 #define OFFSET_MASK 0x3FF
868 #define LEAF_FLAG 0x800
869 #endif
870 u32 dstSize;
871 u32 dstCnt = 0;
872 const u8 *pSrc = srcp;
873 BitReader stream;
874 u16* huffTable9; // Huffman table for length
875 u16* huffTable12; // Huffman table for offset
876 u8* verify_work; // For checking out-of-bounds accesses in the Huffman table (TODO: Not yet used)
877
878 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LH )
879 {
880 return CX_ERR_UNSUPPORTED;
881 }
882 if ( srcSize <= 4 )
883 {
884 return CX_ERR_SRC_SHORTAGE;
885 }
886
887 huffTable9 = work;
888 huffTable12 = (u16*)work + (1 << LENGTH_BITS) * 2;
889 verify_work = (u8*)work + CX_UNCOMPRESS_LH_WORK_SIZE;
890
891 // load the header
892 dstSize = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
893 pSrc += 4;
894 if ( dstSize == 0 )
895 {
896 dstSize = CXiConvertEndian_( *(u32*)pSrc );
897 pSrc += 4;
898 if ( srcSize < 8 )
899 {
900 return CX_ERR_SRC_SHORTAGE;
901 }
902 }
903
904 // read the Huffman table
905 pSrc += CXiHuffImportTree( huffTable9, pSrc, LENGTH_BITS, srcSize - ((u32)pSrc - (u32)srcp) );
906 if ( pSrc > srcp + srcSize )
907 {
908 return CX_ERR_SRC_SHORTAGE;
909 }
910 if ( ! CXiLHVerifyTable( huffTable9, LENGTH_BITS ) )
911 {
912 return CX_ERR_ILLEGAL_TABLE;
913 }
914 pSrc += CXiHuffImportTree( huffTable12, pSrc, OFFSET_BITS, srcSize - ((u32)pSrc - (u32)srcp) );
915 if ( pSrc > srcp + srcSize )
916 {
917 return CX_ERR_SRC_SHORTAGE;
918 }
919 if ( ! CXiLHVerifyTable( huffTable12, OFFSET_BITS ) )
920 {
921 return CX_ERR_ILLEGAL_TABLE;
922 }
923
924 BitReader_Init( &stream, pSrc, srcSize - ((u32)pSrc - (u32)srcp) );
925
926 while ( dstCnt < dstSize )
927 {
928 u16* nodep = huffTable9 + 1;
929 u16 val;
930 do
931 {
932 s8 bit = BitReader_Read( &stream );
933 u32 offset = (((*nodep & 0x7F) + 1U) << 1) + bit;
934 if ( bit < 0 )
935 {
936 return CX_ERR_SRC_SHORTAGE;
937 }
938
939 if ( *nodep & (0x100 >> bit) )
940 {
941 nodep = (u16*)((u32)nodep & ~0x3);
942 val = *(nodep + offset);
943 break;
944 }
945 else
946 {
947 nodep = (u16*)((u32)nodep & ~0x3);
948 nodep += offset;
949 }
950 } while ( 1 );
951
952 if ( val < 0x100 )
953 // uncompressed data
954 {
955 dstp[dstCnt++] = (u8)val;
956 }
957 else
958 // compressed data
959 {
960 u16 length = (u16)( (val & 0xFF) + 3 );
961 u16* nodep = huffTable12 + 1;
962 do
963 {
964 s8 bit = BitReader_Read( &stream );
965 u32 offset = (((*nodep & OFFSET_MASK) + 1U) << 1) + bit;
966
967 if ( bit < 0 )
968 {
969 return CX_ERR_SRC_SHORTAGE;
970 }
971
972 if ( *nodep & (LEAF_FLAG >> bit) )
973 {
974 nodep = (u16*)((u32)nodep & ~0x3);
975 val = *(nodep + offset);
976 break;
977 }
978 else
979 {
980 nodep = (u16*)((u32)nodep & ~0x3);
981 nodep += offset;
982 }
983 } while ( 1 );
984
985 #if defined(ENC_OFFSET_WIDTH)
986 offset_bit = val;
987 val = 0;
988 if ( offset_bit > 0 )
989 {
990 val = 1;
991 while ( --offset_bit > 0 )
992 {
993 val <<= 1;
994 val |= BitReader_Read( &stream );
995 }
996 }
997 #endif
998 val += 1;
999
1000 if ( dstCnt < val )
1001 {
1002 return CX_ERR_DEST_OVERRUN;
1003 }
1004 if ( dstCnt + length > dstSize )
1005 {
1006 return CX_ERR_DEST_OVERRUN;
1007 }
1008
1009 while ( length-- > 0 )
1010 {
1011 dstp[dstCnt] = dstp[dstCnt - val];
1012 ++dstCnt;
1013 }
1014 }
1015 }
1016
1017 if ( stream.srcSize - stream.cnt > 32 )
1018 {
1019 return CX_ERR_SRC_REMAINDER;
1020 }
1021
1022 return CX_ERR_SUCCESS;
1023
1024 #undef OFFSET_BITS
1025 #undef OFFSET_MASK
1026 #undef LEAF_FLAG
1027 }
1028
1029
1030
1031
1032 // Structure for the range coder state
1033 typedef struct
1034 {
1035 u32 low;
1036 u32 range;
1037 u32 code; // only used during decompression
1038 u8 carry; // only used during compression
1039 u32 carry_cnt; // only used during compression
1040 }
1041 RCState;
1042
1043 // Range coder structure
1044 typedef struct
1045 {
1046 u32 *freq; // Table for occurrence frequency: (1 << bitSize) * sizeof(u32) bytes
1047 u32 *low_cnt; // Table for the LOW border value: (1 << bitSize) * sizeof(u32) bytes
1048 u32 total; // Total: 4 bytes
1049 u8 bitSize; // Bit size: 1 byte
1050 u8 padding_[1]; //
1051 }
1052 RCCompressionInfo;
1053
1054 #define RC_MAX_RANGE 0x80000000
1055
1056
1057 /*---------------------------------------------------------------------------*
1058 Name: RCInitState_
1059
1060 Description: Initializes the RC state.
1061
1062 Arguments: state: Pointer to an RC state structure
1063
1064 Returns: None.
1065 *---------------------------------------------------------------------------*/
1066 static inline void
RCInitState_(RCState * state)1067 RCInitState_( RCState* state )
1068 {
1069 // The starting range is 0x80000000, so a carry will not suddenly occur the first time
1070 state->low = 0;
1071 state->range = RC_MAX_RANGE;
1072 state->code = 0;
1073 state->carry = 0;
1074 state->carry_cnt = 0;
1075 }
1076
1077 /*---------------------------------------------------------------------------*
1078 Name: RCInitInfo_
1079
1080 Description: Initialize the table for the adaptive range coder.
1081 All occurrence frequencies are initialized to 1.
1082
1083 Arguments: info: Pointer to an RC table information structure
1084
1085 Returns: None.
1086 *---------------------------------------------------------------------------*/
1087 static inline void
RCInitInfo_(RCCompressionInfo * info,u8 bitSize,void * work)1088 RCInitInfo_( RCCompressionInfo* info, u8 bitSize, void* work )
1089 {
1090 u32 tableSize = (u32)(1 << bitSize);
1091 u32 i;
1092
1093 info->bitSize = bitSize;
1094 info->freq = (u32*)work;
1095 info->low_cnt = (u32*)( (u32)work + tableSize * sizeof(u32) );
1096
1097 for ( i = 0; i < tableSize; i++ )
1098 {
1099 info->freq[ i ] = 1;
1100 info->low_cnt[ i ] = i;
1101 }
1102 info->total = tableSize;
1103 }
1104
1105 /*---------------------------------------------------------------------------*
1106 Name: RCAAddCount_
1107
1108 Description: Updates the frequency table for an adaptive range coder.
1109
1110 Arguments: info: Table information for a range coder
1111 val: Value to add
1112
1113 Returns: None.
1114 *---------------------------------------------------------------------------*/
1115 static void
RCAddCount_(RCCompressionInfo * info,u16 val)1116 RCAddCount_( RCCompressionInfo* info, u16 val )
1117 {
1118 u32 i;
1119 u32 tableSize = (u32)(1 << info->bitSize);
1120
1121 info->freq[ val ]++;
1122 info->total++;
1123 for ( i = (u32)(val + 1); i < tableSize; i++ )
1124 {
1125 info->low_cnt[ i ]++;
1126 }
1127
1128 // Reconstruct if the total exceeds the maximum value.
1129 if ( info->total >= 0x00010000 )
1130 {
1131 if ( info->freq[ 0 ] > 1 )
1132 {
1133 info->freq[ 0 ] = info->freq[ 0 ] / 2;
1134 }
1135 info->low_cnt[ 0 ] = 0;
1136 info->total = info->freq[ 0 ];
1137
1138 for ( i = 1; i < tableSize; i++ )
1139 {
1140 if ( info->freq[ i ] > 1 )
1141 {
1142 info->freq[ i ] >>= 1;
1143 }
1144 info->low_cnt[ i ] = info->low_cnt[ i - 1 ] + info->freq[ i - 1 ];
1145 info->total += info->freq[ i ];
1146 }
1147 }
1148 }
1149
1150
1151 /*---------------------------------------------------------------------------*
1152 Name: RCSearch_
1153
1154 Description: Searches for the value that must be obtained next from the code, range, and low values.
1155
1156 Arguments: info: Table information for a range coder
1157 code: Current code value
1158 range: Current Range value
1159 low: Current Low value
1160
1161 Returns:
1162 *---------------------------------------------------------------------------*/
1163 static u16
RCSearch_(RCCompressionInfo * info,u32 code,u32 range,u32 low)1164 RCSearch_( RCCompressionInfo* info, u32 code, u32 range, u32 low )
1165 {
1166 u32 tableSize = (u32)(1 << info->bitSize);
1167 u32 codeVal = code - low;
1168 u32 i;
1169 u32 temp = range / info->total;
1170 u32 tempVal = codeVal / temp;
1171
1172 // binary search
1173 u32 left = 0;
1174 u32 right = tableSize - 1;
1175
1176 while ( left < right )
1177 {
1178 i = (left + right) / 2;
1179
1180 if ( info->low_cnt[ i ] > tempVal )
1181 {
1182 right = i;
1183 }
1184 else
1185 {
1186 left = i + 1;
1187 }
1188 }
1189
1190 i = left;
1191 while ( info->low_cnt[ i ] > tempVal )
1192 {
1193 --i;
1194 }
1195 return (u16)i;
1196 }
1197
1198
1199 /*---------------------------------------------------------------------------*
1200 Name: RCGetData_
1201
1202 Description: Gets the next value from the state in RCState, then updates the state.
1203
1204 Arguments: stream
1205 info
1206 state
1207 adaptive
1208
1209 Returns:
1210 *---------------------------------------------------------------------------*/
1211 static u16
RCGetData_(const u8 * srcp,RCCompressionInfo * info,RCState * state,u32 * pSrcCnt)1212 RCGetData_( const u8* srcp, RCCompressionInfo* info, RCState* state, u32* pSrcCnt )
1213 {
1214 #define MIN_RANGE 0x01000000
1215 u16 val = RCSearch_( info, state->code, state->range, state->low );
1216 u32 cnt = 0;
1217
1218 {
1219 u32 tmp;
1220 tmp = state->range / info->total;
1221 state->low += info->low_cnt[ val ] * tmp;
1222 state->range = info->freq[ val ] * tmp;
1223 }
1224
1225 // Update the table for occurrence frequency
1226 RCAddCount_( info, val );
1227
1228 while ( state->range < MIN_RANGE )
1229 {
1230 state->code <<= 8;
1231 state->code += srcp[ cnt++ ];
1232 state->range <<= 8;
1233 state->low <<= 8;
1234 }
1235 *pSrcCnt = cnt;
1236
1237 return val;
1238 #undef MIN_RANGE
1239 }
1240
1241
1242 /*---------------------------------------------------------------------------*
1243 Name: CXSecureUncompressLRC
1244
1245 Description: LZ/Range Coder combined compression
1246
1247 Arguments: srcp
1248 dstp
1249 work
1250
1251 Returns: None.
1252 *---------------------------------------------------------------------------*/
1253 s32
CXSecureUncompressLRC(const u8 * srcp,u32 srcSize,u8 * dstp,void * work)1254 CXSecureUncompressLRC( const u8* srcp, u32 srcSize, u8* dstp, void* work )
1255 {
1256 #define LENGTH_BITS 9
1257 #define OFFSET_BITS 12
1258 RCCompressionInfo infoVal;
1259 RCCompressionInfo infoOfs;
1260 RCState rcState;
1261 const u8* pSrc = srcp;
1262 u32 dstCnt = 0;
1263 u32 dstSize = 0;
1264
1265 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_LRC )
1266 {
1267 return CX_ERR_UNSUPPORTED;
1268 }
1269 if ( srcSize <= 4 )
1270 {
1271 return CX_ERR_SRC_SHORTAGE;
1272 }
1273
1274 RCInitInfo_( &infoVal, LENGTH_BITS, work );
1275 RCInitInfo_( &infoOfs, OFFSET_BITS, (u8*)work + (1 << LENGTH_BITS) * sizeof(u32) * 2 );
1276 RCInitState_( &rcState );
1277
1278 // load the header
1279 dstSize = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
1280 pSrc += 4;
1281 if ( dstSize == 0 )
1282 {
1283 dstSize = CXiConvertEndian_( *(u32*)pSrc );
1284 pSrc += 4;
1285 if ( srcSize < 8 )
1286 {
1287 return CX_ERR_SRC_SHORTAGE;
1288 }
1289 }
1290
1291 // load the initial code
1292 if ( srcSize - ((u32)pSrc - (u32)srcp) < 4 )
1293 {
1294 return CX_ERR_SRC_SHORTAGE;
1295 }
1296 rcState.code = (u32)( (*pSrc << 24) |
1297 (*(pSrc + 1) << 16) |
1298 (*(pSrc + 2) << 8) |
1299 (*(pSrc + 3) ) );
1300 pSrc += 4;
1301
1302 // continue to get values from the range coder and perform LZ decompression
1303 while ( dstCnt < dstSize )
1304 {
1305 u32 cnt;
1306 u16 val = (u16)( RCGetData_( pSrc, &infoVal, &rcState, &cnt ) );
1307 pSrc += cnt;
1308
1309 if ( val < 0x100 )
1310 // uncompressed data
1311 {
1312 dstp[ dstCnt++ ] = (u8)val;
1313 }
1314 else
1315 // compressed data
1316 {
1317 u16 length = (u16)( (val & 0xFF) + 3 );
1318 val = (u16)( RCGetData_( pSrc, &infoOfs, &rcState, &cnt ) + 1 );
1319 pSrc += cnt;
1320
1321 // check for a buffer overrun
1322 if ( dstCnt + length > dstSize )
1323 {
1324 return CX_ERR_DEST_OVERRUN;
1325 }
1326 if ( dstCnt < val )
1327 {
1328 return CX_ERR_DEST_OVERRUN;
1329 }
1330 if ( ((u32)pSrc - (u32)srcp) > srcSize )
1331 {
1332 return CX_ERR_SRC_SHORTAGE;
1333 }
1334
1335 while ( length-- > 0 )
1336 {
1337 dstp[ dstCnt ] = dstp[ dstCnt - val ];
1338 ++dstCnt;
1339 }
1340 }
1341 }
1342 return CX_ERR_SUCCESS;
1343 #undef LENGTH_BITS
1344 #undef OFFSET_BITS
1345 }
1346