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