1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: cx_Uncompression.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/assert.h>
18 #include <nn/math.h>
19 #include <nn/cx/cx_Uncompression.h>
20 #include "cx_Utility.h"
21
22 namespace nn {
23 namespace cx {
24
25 //======================================================================
26 // Expanding compressed data
27 //======================================================================
28
29 /* Please see man pages for details
30
31 */
GetUncompressedSize(const void * pData)32 u32 GetUncompressedSize(const void* pData)
33 {
34 NN_TASSERT_(pData);
35
36 const u8* p = static_cast<const u8*>(pData);
37
38 u32 size = internal::Read32Le(p) >> 8;
39 if (size == 0)
40 {
41 size = internal::Read32Le(p + 4);
42 }
43 return size;
44 }
45
46
47 /*---------------------------------------------------------------------------*
48 Name: UncompressAny
49
50 Description:
51 The compression type is determined from the data header, and the appropriate decompression process is executed.
52 Links to decompression processes for all compression types are included, but if you are not using special compression formats, it might be better to execute functions specific to the compression type.
53
54
55
56 Arguments: srcp Source address
57 destp Destination address
58
59 Returns: None.
60 *---------------------------------------------------------------------------*/
UncompressAny(const void * srcp,void * destp)61 void UncompressAny( const void* srcp, void* destp )
62 {
63 NN_NULL_TASSERT_(srcp);
64
65 switch ( GetCompressionType( srcp ) )
66 {
67 // Run-length compressed data
68 case COMPRESSION_RL:
69 UncompressRL( srcp, destp );
70 break;
71 // LZ77-compressed data
72 case COMPRESSION_LZ:
73 UncompressLZ( srcp, destp );
74 break;
75 // Huffman-compressed data
76 case COMPRESSION_HUFFMAN:
77 UncompressHuffman( srcp, destp );
78 break;
79 // Difference filter
80 case COMPRESSION_DIFF:
81 UnfilterDiff( srcp, destp );
82 break;
83 default:
84 NN_ASSERTMSG( 0, "Unknown compressed format" );
85 }
86 }
87
88
89 /*---------------------------------------------------------------------------*
90 Name: UncompressRL
91
92 Description: 8-bit decompression of run-length compressed data
93
94 - Decompresses run-length compressed data, writing in 8 bit units.
95 - Use 4 byte alignment for the source address.
96
97 - Data header
98 u32 :4 : Reserved
99 compType:4 Compression type( = 3)
100 destSize:24 Data size after decompression
101
102 - Flag data format
103 u8 length:7 Decompressed data length - 1 (When not compressed)
104 Decompressed data length - 3 (only compress when the contiguous length is 3 bytes or greater)
105 flag:1 (0, 1) = (not compressed, compressed)
106
107 Arguments: *srcp Source address
108 *destp Destination address
109
110 Returns: None.
111 *---------------------------------------------------------------------------*/
UncompressRL(const void * srcp,void * destp)112 void UncompressRL( const void *srcp, void *destp )
113 {
114 NN_NULL_TASSERT_(srcp);
115 NN_NULL_TASSERT_(destp);
116
117 const u8 *pSrc = static_cast<const u8*>(srcp);
118 u8 *pDst = static_cast<u8*>(destp);
119 u32 destCount = internal::Read32Le(pSrc) >> 8;
120 pSrc += 4;
121
122 if ( destCount == 0 )
123 {
124 destCount = internal::Read32Le(pSrc);
125 pSrc += 4;
126 }
127
128 while ( destCount > 0 )
129 {
130 u8 flags = *pSrc++;
131 u32 length = flags & 0x7fU;
132 if ( !(flags & 0x80) )
133 {
134 length++;
135 if ( length > destCount )
136 // Measures for buffer overrun when invalid data is decompressed.
137 {
138 length = destCount;
139 }
140
141 destCount -= length;
142 do
143 {
144 *pDst++ = *pSrc++;
145 } while ( --length > 0 );
146 }
147 else
148 {
149 u8 srcTmp;
150
151 length += 3;
152 if ( length > destCount )
153 // Measures for buffer overrun when invalid data is decompressed.
154 {
155 length = destCount;
156 }
157
158 destCount -= length;
159 srcTmp = *pSrc++;
160 do
161 {
162 *pDst++ = srcTmp;
163 } while ( --length > 0 );
164 }
165 }
166 }
167
168
169 /*---------------------------------------------------------------------------*
170 Name: UncompressLZ
171
172 Description: 8-bit decompression of LZ77 compressed data
173
174 * Expands LZ77-compressed data and writes it in 8-bit units.
175 - Use 4 byte alignment for the source address.
176
177 - Data header
178 u32 :4 : Reserved
179 compType:4 Compression type( = 1)
180 destSize:24 Data size after decompression
181
182 - Flag data format
183 u8 flags Compression/no compression flag
184 (0, 1) = (not compressed, compressed)
185 - Code data format (Big Endian)
186 u16 length:4 Decompressed data length - 3 (only compress when the match length is 3 bytes or greater)
187 offset:12 Match data offset - 1
188
189 Arguments: *srcp Source address
190 *destp Destination address
191
192 Returns: None.
193 *---------------------------------------------------------------------------*/
UncompressLZ(const void * srcp,void * destp)194 void UncompressLZ( const void *srcp, void *destp )
195 {
196 NN_NULL_TASSERT_(srcp);
197 NN_NULL_TASSERT_(destp);
198
199 const u8* pSrc = static_cast<const u8*>(srcp);
200 u8* pDst = static_cast<u8*>(destp);
201 u32 destCount = internal::Read32Le(pSrc) >> 8;
202 bool exFormat = (*pSrc & 0x0F)? true : false;
203
204 pSrc += 4;
205
206 if ( destCount == 0 )
207 {
208 destCount = internal::Read32Le(pSrc);
209 pSrc += 4;
210 }
211
212 while ( destCount > 0 )
213 {
214 u32 flags = *pSrc++;
215 for ( int i = 0; i < 8; ++i )
216 {
217 if ( !(flags & 0x80) )
218 {
219 *pDst++ = *pSrc++;
220 destCount--;
221 }
222 else
223 {
224 u32 length = (*pSrc >> 4);
225 s32 offset;
226
227 if ( ! exFormat )
228 {
229 length += 3;
230 }
231 else
232 {
233 // LZ77 extended format
234 if ( length == 1 )
235 {
236 length = (*pSrc++ & 0x0F) << 12;
237 length |= (*pSrc++) << 4;
238 length |= (*pSrc >> 4);
239 length += 0xFF + 0xF + 3;
240 }
241 else if ( length == 0 )
242 {
243 length = (*pSrc++ & 0x0F) << 4;
244 length |= (*pSrc >> 4);
245 length += 0xF + 2;
246 }
247 else
248 {
249 length += 1;
250 }
251 }
252 offset = (*pSrc++ & 0x0f) << 8;
253 offset = (offset | *pSrc++) + 1;
254 // Measures for buffer overrun when invalid data is decompressed.
255 length = nn::math::Min(length, destCount);
256 destCount -= length;
257 u8* pTmp = pDst - offset;
258 for (int j = 0; j < length; j++)
259 {
260 *pDst++ = *pTmp++;
261 }
262 }
263 if ( destCount <= 0 )
264 {
265 break;
266 }
267 flags <<= 1;
268 }
269 }
270 }
271
272
273 /*---------------------------------------------------------------------------*
274 Name: UncompressHuffman
275
276 Description: Decompression of Huffman compressed data
277
278 - Decompresses Huffman compressed data, writing in 32 bit units.
279 - Use 4 byte alignment for the source address.
280 - Use 4-byte alignment for the destination address.
281 - The target decompression buffer size must be prepared in 4-byte multiples.
282
283 - Data header
284 u32 bitSize:4 1 data bit size (Normally 4|8)
285 compType:4 Compression type( = 2)
286 destSize:24 Data size after decompression
287
288 - Tree table
289 u8 treeSize Tree table size/2 - 1
290 TreeNodeData nodeRoot Root node
291
292 TreeNodeData nodeLeft Root left node
293 TreeNodeData nodeRight Root right node
294
295 TreeNodeData nodeLeftLeft Left left node
296 TreeNodeData nodeLeftRight Left right node
297
298 TreeNodeData nodeRightLeft Right left node
299 TreeNodeData nodeRightRight Right right node
300
301 .
302 .
303
304 The compressed data itself follows
305
306 - TreeNodeData structure
307 u8 nodeNextOffset:6 : Offset to the next node data - 1 (2 byte units)
308 rightEndFlag:1 Right node end flag
309 leftEndzflag:1 Left node end flag
310 When the end flag is set
311 There is data in next node
312
313 Arguments: *srcp Source address
314 *destp Destination address
315
316 Returns: None.
317 *---------------------------------------------------------------------------*/
UncompressHuffman(const void * srcp,void * destp)318 void UncompressHuffman( const void *srcp, void *destp )
319 {
320 NN_NULL_TASSERT_(srcp);
321 NN_NULL_TASSERT_(destp);
322 NN_CX_CHECK_ALIGN(srcp, sizeof(u32));
323 NN_CX_CHECK_ALIGN(destp, sizeof(u32));
324
325 #define TREE_END 0x80
326 const u32 *pSrc = static_cast<const u32*>(srcp);
327 u32 *pDst = static_cast<u32*>(destp);
328 s32 destCount = (s32)( internal::ConvertEndian( *pSrc ) >> 8 );
329 u8 *treep = (destCount != 0)? ((u8*)pSrc + 4) : ((u8*)pSrc + 8);
330 u8 *treeStartp = treep + 1;
331 u32 dataBit = *(u8*)pSrc & 0x0FU;
332 u32 destTmp = 0;
333 u32 destTmpCount = 0;
334 u32 destTmpDataNum = 4 + ( dataBit & 0x7 );
335
336 if ( destCount == 0 )
337 {
338 destCount = (s32)( internal::ConvertEndian( *(pSrc + 1) ) );
339 }
340
341 pSrc = (u32*)( treep + ((*treep + 1) << 1) );
342 treep = treeStartp;
343
344 while ( destCount > 0 )
345 {
346 s32 srcCount = 32;
347 u32 srcTmp = internal::ConvertEndian( *pSrc++ ); // Endian strategy
348 while ( --srcCount >= 0 )
349 {
350 u32 treeShift = (srcTmp >> 31) & 0x1;
351 u32 treeCheck = *treep;
352 treeCheck <<= treeShift;
353 treep = (u8*)( (((u32)treep >> 1) << 1) + (((*treep & 0x3f) + 1) << 1) + treeShift );
354 if ( treeCheck & TREE_END )
355 {
356 destTmp >>= dataBit;
357 destTmp |= *treep << (32 - dataBit);
358 treep = treeStartp;
359 if ( ++destTmpCount == destTmpDataNum )
360 {
361 // Over-access until the last 4-byte alignment of the decompression buffer
362 *pDst++ = internal::ConvertEndian(destTmp); // Endian strategy
363 destCount -= 4;
364 destTmpCount = 0;
365 }
366 }
367 if ( destCount <= 0 )
368 {
369 break;
370 }
371 srcTmp <<= 1;
372 }
373 }
374 }
375
376
377 namespace {
378
379 /*---------------------------------------------------------------------------*
380 Name: HuffImportTree
381
382 Description: Expands the Huffman table.
383
384 Arguments: pTable
385 srcp
386 bitSize
387
388 Returns:
389 *---------------------------------------------------------------------------*/
390 u32
HuffImportTree(u16 * pTable,const u8 * srcp,u8 bitSize)391 HuffImportTree( u16* pTable, const u8* srcp, u8 bitSize )
392 {
393 u32 tableSize;
394 u32 idx = 1;
395 u32 data = 0;
396 u32 bitNum = 0;
397 u32 bitMask = (1 << bitSize) - 1U;
398 u32 srcCnt = 0;
399 const u32 MAX_IDX = (u32)( (1 << bitSize) * 2 );
400
401 if ( bitSize > 8 )
402 {
403 tableSize = internal::ConvertEndian16( *(u16*)srcp );
404 srcp += 2;
405 srcCnt += 2;
406 }
407 else
408 {
409 tableSize = *srcp;
410 srcp += 1;
411 srcCnt += 1;
412 }
413 tableSize = (tableSize + 1) * 4;
414
415 while ( srcCnt < tableSize || bitSize <= bitNum )
416 {
417 while ( bitNum < bitSize )
418 {
419 data <<= 8;
420 data |= *srcp++;
421 ++srcCnt;
422 bitNum += 8;
423 }
424
425 if ( idx < MAX_IDX )
426 {
427 pTable[ idx++ ] = (u16)( ( data >> (bitNum - bitSize) ) & bitMask );
428 }
429 bitNum -= bitSize;
430 }
431 return tableSize;
432 }
433
434 struct BitReader
435 {
436 const u8* srcp;
437 u32 cnt;
438 u32 stream;
439 u32 stream_len;
440 };
441
442 inline void
BitReader_Init(BitReader * context,const u8 * srcp)443 BitReader_Init( BitReader* context, const u8* srcp )
444 {
445 context->srcp = srcp;
446 context->cnt = 0;
447 context->stream = 0;
448 context->stream_len = 0;
449 }
450
451 u8
BitReader_Read(BitReader * context)452 BitReader_Read( BitReader* context )
453 {
454 u8 bit;
455 if ( context->stream_len == 0 )
456 {
457 context->stream = context->srcp[context->cnt++];
458 context->stream_len = 8;
459 }
460 bit = (u8)( (context->stream >> (context->stream_len - 1)) & 0x1 );
461 context->stream_len--;
462 return bit;
463 }
464
465 } // Namespace
466
467 #define ENC_OFFSET_WIDTH
468
469 /*---------------------------------------------------------------------------*
470 Name: UncompressLH
471
472 Description: Decompress LZ-Huffman (combined) compression.
473
474 Arguments: *srcp Source address
475 *destp Destination address
476 *work Working buffer
477 The required size is UNCOMPRESS_LH_WORK_SIZE (18 KB)
478
479 Returns: None.
480 *---------------------------------------------------------------------------*/
481 void
UncompressLH(const u8 * srcp,u8 * dstp,void * work)482 UncompressLH( const u8* srcp, u8* dstp, void* work )
483 {
484 NN_NULL_TASSERT_(srcp);
485 NN_NULL_TASSERT_(dstp);
486 NN_NULL_TASSERT_(work);
487 NN_CX_CHECK_ALIGN(srcp, sizeof(u32));
488 NN_CX_CHECK_ALIGN(work, sizeof(u16));
489
490 #define LENGTH_BITS 9
491 #if defined(ENC_OFFSET_WIDTH)
492 #define OFFSET_BITS 5
493 #define OFFSET_MASK 0x07
494 #define LEAF_FLAG 0x10
495 u16 offset_bit;
496 #else
497 #define OFFSET_BITS 12
498 #define OFFSET_MASK 0x3FF
499 #define LEAF_FLAG 0x800
500 #endif
501 u32 dstSize;
502 u32 dstCnt = 0;
503 const u8 *pSrc = srcp;
504 BitReader stream;
505 u16* huffTable9;
506 u16* huffTable12;
507
508 huffTable9 = static_cast<u16*>(work);
509 huffTable12 = (u16*)work + (1 << LENGTH_BITS) * 2;
510
511 // load the header
512 dstSize = internal::Read32Le(pSrc) >> 8;
513 pSrc += 4;
514 if ( dstSize == 0 )
515 {
516 dstSize = internal::Read32Le(pSrc);
517 pSrc += 4;
518 }
519
520 // read the Huffman table
521 pSrc += HuffImportTree( huffTable9, pSrc, LENGTH_BITS );
522 pSrc += HuffImportTree( huffTable12, pSrc, OFFSET_BITS );
523
524 BitReader_Init( &stream, pSrc );
525
526 while ( dstCnt < dstSize )
527 {
528 u16 val;
529 {
530 u16* nodep = huffTable9 + 1;
531 do
532 {
533 u8 bit = BitReader_Read( &stream );
534 u32 offset = (((*nodep & 0x7F) + 1U) << 1) + bit;
535
536 if ( *nodep & (0x100 >> bit) )
537 {
538 nodep = (u16*)((u32)nodep & ~0x3);
539 val = *(nodep + offset);
540 break;
541 }
542 else
543 {
544 nodep = (u16*)((u32)nodep & ~0x3);
545 nodep += offset;
546 }
547 } while ( 1 );
548 }
549
550 if ( val < 0x100 )
551 // uncompressed data
552 {
553 dstp[dstCnt++] = (u8)val;
554 }
555 else
556 // compressed data
557 {
558 u16 length = (u16)( (val & 0xFF) + 3 );
559 u16* nodep = huffTable12 + 1;
560 do
561 {
562 u8 bit = BitReader_Read( &stream );
563 u32 offset = (((*nodep & OFFSET_MASK) + 1U) << 1) + bit;
564
565 if ( *nodep & (LEAF_FLAG >> bit) )
566 {
567 nodep = (u16*)((u32)nodep & ~0x3);
568 val = *(nodep + offset);
569 break;
570 }
571 else
572 {
573 nodep = (u16*)((u32)nodep & ~0x3);
574 nodep += offset;
575 }
576 } while ( 1 );
577
578 #if defined(ENC_OFFSET_WIDTH)
579 offset_bit = val;
580 val = 0;
581 if ( offset_bit > 0 )
582 {
583 val = 1;
584 while ( --offset_bit > 0 )
585 {
586 val <<= 1;
587 val |= BitReader_Read( &stream );
588 }
589 }
590 #endif
591 val += 1;
592 // Measures for buffer overrun when invalid data is decompressed.
593 if ( dstCnt + length > dstSize )
594 {
595 length = (u16)( dstSize - dstCnt );
596 }
597
598 while ( length-- > 0 )
599 {
600 dstp[dstCnt] = dstp[dstCnt - val];
601 ++dstCnt;
602 }
603 }
604 }
605 #undef LENGTH_BITS
606 #undef OFFSET_BITS
607 #undef OFFSET_MASK
608 #undef LEAF_FLAG
609 }
610
611 namespace {
612
613 // Structure for the range coder state
614 struct RCState
615 {
616 u32 low;
617 u32 range;
618 u32 code; // only used during decompression
619 u8 carry; // only used during compression
620 u8 padding_[3];
621 u32 carry_cnt; // only used during compression
622 };
623
624 // Range coder structure
625 struct RCCompressionInfo
626 {
627 u32 *freq; // Table for occurrence frequency: (1 << bitSize) * sizeof(u32) bytes
628 u32 *low_cnt; // Table for the LOW border value: (1 << bitSize) * sizeof(u32) bytes
629 u32 total; // Total: 4 bytes
630 u8 bitSize; // Bit size: 1 byte
631 u8 padding_[3]; //
632 };
633
634 #define RC_MAX_RANGE 0x80000000
635
636
637 /*---------------------------------------------------------------------------*
638 Name: RCInitState_
639
640 Description: Initializes the RC state.
641
642 Arguments: state: Pointer to an RC state structure
643
644 Returns: None.
645 *---------------------------------------------------------------------------*/
646 inline void
RCInitState_(RCState * state)647 RCInitState_( RCState* state )
648 {
649 state->low = 0;
650 state->range = RC_MAX_RANGE;
651 state->code = 0;
652 state->carry = 0;
653 state->carry_cnt = 0;
654 }
655
656 /*---------------------------------------------------------------------------*
657 Name: RCInitInfo_
658
659 Description: Initialize the table for the adaptive range coder.
660 All occurrence frequencies are initialized to 1.
661
662 Arguments: info: Pointer to an RC table information structure
663
664 Returns: None.
665 *---------------------------------------------------------------------------*/
666 inline void
RCInitInfo_(RCCompressionInfo * info,u8 bitSize,void * work)667 RCInitInfo_( RCCompressionInfo* info, u8 bitSize, void* work )
668 {
669 u32 tableSize = (u32)(1 << bitSize);
670 u32 i;
671
672 info->bitSize = bitSize;
673 info->freq = (u32*)work;
674 info->low_cnt = (u32*)( (u32)work + tableSize * sizeof(u32) );
675
676 for ( i = 0; i < tableSize; i++ )
677 {
678 info->freq[ i ] = 1;
679 info->low_cnt[ i ] = i;
680 }
681 info->total = tableSize;
682 }
683
684 /*---------------------------------------------------------------------------*
685 Name: RCAAddCount_
686
687 Description: Updates the frequency table for an adaptive range coder.
688
689 Arguments: info: Table information for a range coder
690 val: Value to add
691
692 Returns: None.
693 *---------------------------------------------------------------------------*/
694 void
RCAddCount_(RCCompressionInfo * info,u16 val)695 RCAddCount_( RCCompressionInfo* info, u16 val )
696 {
697 u32 i;
698 u32 tableSize = (u32)(1 << info->bitSize);
699
700 info->freq[ val ]++;
701 info->total++;
702 for ( i = (u32)(val + 1); i < tableSize; i++ )
703 {
704 info->low_cnt[ i ]++;
705 }
706
707 // Reconstruct if the total exceeds the maximum value.
708 if ( info->total >= 0x00010000 )
709 {
710 if ( info->freq[ 0 ] > 1 )
711 {
712 info->freq[ 0 ] = info->freq[ 0 ] / 2;
713 }
714 info->low_cnt[ 0 ] = 0;
715 info->total = info->freq[ 0 ];
716
717 for ( i = 1; i < tableSize; i++ )
718 {
719 if ( info->freq[ i ] > 1 )
720 {
721 info->freq[ i ] >>= 1;
722 }
723 info->low_cnt[ i ] = info->low_cnt[ i - 1 ] + info->freq[ i - 1 ];
724 info->total += info->freq[ i ];
725 }
726 }
727 }
728
729
730 /*---------------------------------------------------------------------------*
731 Name: RCSearch_
732
733 Description: Searches for the value that must be obtained next from the code, range, and low values.
734
735 Arguments: info: Table information for a range coder
736 code: Current code value
737 range: Current Range value
738 low: Current Low value
739
740 Returns:
741 *---------------------------------------------------------------------------*/
742 u16
RCSearch_(RCCompressionInfo * info,u32 code,u32 range,u32 low)743 RCSearch_( RCCompressionInfo* info, u32 code, u32 range, u32 low )
744 {
745 u32 tableSize = (u32)(1 << info->bitSize);
746 u32 codeVal = code - low;
747 u32 i;
748 u32 temp = range / info->total;
749 u32 tempVal = codeVal / temp;
750
751 // binary search
752 u32 left = 0;
753 u32 right = tableSize - 1;
754
755 while ( left < right )
756 {
757 i = (left + right) / 2;
758
759 if ( info->low_cnt[ i ] > tempVal )
760 {
761 right = i;
762 }
763 else
764 {
765 left = i + 1;
766 }
767 }
768
769 i = left;
770 while ( info->low_cnt[ i ] > tempVal )
771 {
772 --i;
773 }
774 return (u16)i;
775 }
776
777
778 /*---------------------------------------------------------------------------*
779 Name: RCGetData_
780
781 Description: Gets the next value from the state in RCState, then updates the state.
782
783 Arguments: stream
784 info
785 state
786 adaptive
787
788 Returns:
789 *---------------------------------------------------------------------------*/
790 u16
RCGetData_(const u8 * srcp,RCCompressionInfo * info,RCState * state,u32 * pSrcCnt)791 RCGetData_( const u8* srcp, RCCompressionInfo* info, RCState* state, u32* pSrcCnt )
792 {
793 #define MIN_RANGE 0x01000000
794 u16 val = RCSearch_( info, state->code, state->range, state->low );
795 u32 cnt = 0;
796
797 {
798 u32 tmp;
799 tmp = state->range / info->total;
800 state->low += info->low_cnt[ val ] * tmp;
801 state->range = info->freq[ val ] * tmp;
802 }
803
804 // Update the table for occurrence frequency
805 RCAddCount_( info, val );
806
807 while ( state->range < MIN_RANGE )
808 {
809 state->code <<= 8;
810 state->code += srcp[ cnt++ ];
811 state->range <<= 8;
812 state->low <<= 8;
813 }
814 *pSrcCnt = cnt;
815
816 return val;
817 #undef MIN_RANGE
818 }
819
820 } // Namespace
821
822 /*---------------------------------------------------------------------------*
823 Name: UncompressLRC
824
825 Description: LZ/Range Coder combined compression
826
827 Arguments: srcp
828 dstp
829 work
830
831 Returns: None.
832 *---------------------------------------------------------------------------*/
833 void
UncompressLRC(const u8 * srcp,u8 * dstp,void * work)834 UncompressLRC( const u8* srcp, u8* dstp, void* work )
835 {
836 NN_NULL_TASSERT_(srcp);
837 NN_NULL_TASSERT_(dstp);
838 NN_NULL_TASSERT_(work);
839 NN_CX_CHECK_ALIGN(srcp, sizeof(u32));
840 NN_CX_CHECK_ALIGN(work, sizeof(u32));
841
842 #define LENGTH_BITS 9
843 #define OFFSET_BITS 12
844 RCCompressionInfo infoVal;
845 RCCompressionInfo infoOfs;
846 RCState rcState;
847 const u8* pSrc = srcp;
848 u32 dstCnt = 0;
849 u32 dstSize = 0;
850
851 RCInitInfo_( &infoVal, LENGTH_BITS, work );
852 RCInitInfo_( &infoOfs, OFFSET_BITS, (u8*)work + (1 << LENGTH_BITS) * sizeof(u32) * 2 );
853 RCInitState_( &rcState );
854
855 // load the header
856 dstSize = internal::Read32Le(pSrc) >> 8;
857 pSrc += 4;
858 if ( dstSize == 0 )
859 {
860 dstSize = internal::Read32Le(pSrc);
861 pSrc += 4;
862 }
863
864 // load the initial code
865 rcState.code = (u32)( (*pSrc << 24) |
866 (*(pSrc + 1) << 16) |
867 (*(pSrc + 2) << 8) |
868 (*(pSrc + 3) ) );
869 pSrc += 4;
870
871 // continue to get values from the range coder and perform LZ decompression
872 while ( dstCnt < dstSize )
873 {
874 u32 cnt;
875 u16 val = (u16)( RCGetData_( pSrc, &infoVal, &rcState, &cnt ) );
876 pSrc += cnt;
877
878 if ( val < 0x100 )
879 // uncompressed data
880 {
881 dstp[ dstCnt++ ] = (u8)val;
882 }
883 else
884 // compressed data
885 {
886 u16 length = (u16)( (val & 0xFF) + 3 );
887 val = (u16)( RCGetData_( pSrc, &infoOfs, &rcState, &cnt ) + 1 );
888 pSrc += cnt;
889
890 // check for a buffer overrun
891 if ( dstCnt + length > dstSize )
892 {
893 return;
894 }
895 if ( dstCnt < val )
896 {
897 return;
898 }
899
900 while ( length-- > 0 )
901 {
902 dstp[ dstCnt ] = dstp[ dstCnt - val ];
903 ++dstCnt;
904 }
905 }
906 }
907 #undef LENGTH_BITS
908 #undef OFFSET_BITS
909 }
910
911
912
913 /*---------------------------------------------------------------------------*
914 Name: UnfilterDiff
915
916 Description: 8-bit decompression to restore differential filter conversion.
917
918 - Restores a differential filter, writing in 8 bit units.
919 - Use 4 byte alignment for the source address.
920
921 Arguments: *srcp Source address
922 *destp Destination address
923
924 Returns: None.
925 *---------------------------------------------------------------------------*/
UnfilterDiff(const void * srcp,void * destp)926 void UnfilterDiff( const void *srcp, void *destp )
927 {
928 NN_NULL_TASSERT_(srcp);
929 NN_NULL_TASSERT_(destp);
930
931 const u8* pSrc = reinterpret_cast<const u8*>(srcp);
932 u8* pDst = reinterpret_cast<u8*>(destp);
933 u32 bitSize = *pSrc & 0xFU;
934 s32 destCount = (s32)( internal::Read32Le(pSrc) >> 8 );
935 u32 sum = 0;
936
937 pSrc += 4;
938
939 if ( bitSize == 1 )
940 {
941 // Difference calculation in units of 8 bits
942 do
943 {
944 u8 tmp = *(pSrc++);
945 destCount--;
946 sum += tmp;
947 *(pDst++) = (u8)sum;
948 } while ( destCount > 0 );
949 }
950 else
951 {
952 NN_CX_CHECK_ALIGN(srcp, sizeof(u16));
953 NN_CX_CHECK_ALIGN(destp, sizeof(u16));
954
955 // Difference calculation in units of 16 bits
956 do
957 {
958 u16 tmp = internal::ConvertEndian16( *(u16*)pSrc );
959 pSrc += 2;
960 destCount -= 2;
961 sum += tmp;
962 *(u16*)pDst = internal::ConvertEndian16( (u16)sum );
963 pDst += 2;
964 } while ( destCount > 0 );
965 }
966 }
967
968 /* Please see man pages for details
969
970 */
GetCompressionHeader(const void * pData)971 CompressionHeader GetCompressionHeader(const void* pData)
972 {
973 NN_TASSERT_(pData);
974
975 CompressionHeader ret;
976 const u8* p = static_cast<const u8*>(pData);
977
978 ret.compType = (*p & 0xF0) >> 4;
979 ret.compParam = (*p & 0x0F) >> 0;
980 ret.destSize = GetUncompressedSize(pData);
981
982 return ret;
983 }
984
985 /*
986
987
988
989
990 */
UncompressBLZ(void * pData,size_t dataSize,size_t bufferSize)991 void UncompressBLZ(void* pData, size_t dataSize, size_t bufferSize)
992 {
993 NN_NULL_TASSERT_(pData);
994 NN_MIN_TASSERT_(dataSize, 8); // TORIAEZU: Is 8 really OK??
995
996 u8* pBottom = reinterpret_cast<u8*>(pData) + dataSize;
997
998 // Checks whether the compressed data is BLZ (if the footer seems correct, it is determined to be BLZ)
999 // Check bufferTop
1000 u32 offsetInTop = (pBottom[-6] << 16) | (pBottom[-7] << 8) | pBottom[-8];
1001 NN_TASSERT_(offsetInTop <= dataSize);
1002 if (offsetInTop > dataSize)
1003 {
1004 return; // TORIAEZU
1005 }
1006 // Check compressBottom
1007 u32 offsetInBtm = pBottom[-5];
1008 NN_TASSERT_(offsetInBtm >= 0x08 || offsetInBtm <= 0x0B);
1009 if (offsetInBtm < 0x08 && offsetInBtm > 0x0B)
1010 {
1011 return; // TORIAEZU
1012 }
1013 // Size check
1014 u32 offsetOut = (pBottom[-1] << 24) | (pBottom[-2] << 16) |
1015 (pBottom[-3] << 8) | (pBottom[-4] << 0);
1016 NN_TASSERT_((offsetOut + dataSize <= bufferSize));
1017 if (offsetOut + dataSize > bufferSize)
1018 {
1019 return; // TORIAEZU
1020 }
1021
1022 u8* pOut = pBottom + offsetOut;
1023 u8* pInBtm = pBottom - offsetInBtm;
1024 u8* pInTop = pBottom - offsetInTop;
1025
1026 while (pInTop < pInBtm)
1027 {
1028 u8 flag = *--pInBtm;
1029 for (int i = 0; i < 8; ++i)
1030 {
1031 if (!(flag & 0x80))
1032 {
1033 *--pOut = *--pInBtm;
1034 }
1035 else
1036 {
1037 u32 length = *--pInBtm;
1038 u32 offset = (((length & 0xf) << 8) | (*--pInBtm)) + 3;
1039 length = (length >> 4) + 3;
1040
1041 u8* pTmp = pOut + offset;
1042
1043 for (int j = 0; j < length; ++j)
1044 {
1045 *--pOut = *--pTmp;
1046 }
1047 }
1048 flag <<= 1;
1049 if (pInBtm <= pInTop)
1050 {
1051 break;
1052 }
1053 }
1054 }
1055 }
1056
1057 } // namespace cx
1058 } // namespace nn
1059
1060
1061 #include "zutil.h"
1062 #include "inftrees.h"
1063 #include "inflate.h"
1064 #include "zlib.h"
1065
1066 namespace nn {
1067 namespace cx {
1068
1069 namespace
1070 {
1071 void ZlibStaticAssert() NN_IS_UNUSED_VAR;
ZlibStaticAssert()1072 void ZlibStaticAssert()
1073 {
1074 NN_STATIC_ASSERT( sizeof(inflate_state) == UNCOMPRESS_GZIP_WORK_SIZE );
1075 }
1076
UncompressDeflateCommon(void * pDest,size_t destSize,const void * pSrc,size_t srcSize,void * pWork,int wbits)1077 s32 UncompressDeflateCommon(void* pDest, size_t destSize, const void* pSrc, size_t srcSize, void* pWork, int wbits )
1078 {
1079 NN_POINTER_TASSERT_(pDest);
1080 NN_POINTER_TASSERT_(pSrc);
1081 NN_POINTER_TASSERT_(pWork);
1082
1083 detail::ZlibAllocator za(pWork, UNCOMPRESS_GZIP_WORK_SIZE);
1084
1085 z_stream s;
1086 int err;
1087
1088 s.next_in = reinterpret_cast<nncxZlib_Bytef*>(const_cast<void*>(pSrc));
1089 s.avail_in = srcSize;
1090 s.next_out = reinterpret_cast<nncxZlib_Bytef*>(pDest);
1091 s.avail_out = destSize;
1092
1093 s.zalloc = detail::ZlibAllocator::Allocate;
1094 s.zfree = detail::ZlibAllocator::Free;
1095 s.opaque = &za;
1096
1097 err = inflateInit2(&s, wbits);
1098 if (err != Z_OK)
1099 {
1100 return detail::ConvertZlibReturnCode(err);
1101 }
1102
1103 err = nncxZlib_inflate(&s, Z_FINISH);
1104 if (err != Z_STREAM_END)
1105 {
1106 nncxZlib_inflateEnd(&s);
1107 return detail::ConvertZlibReturnCode(err);
1108 }
1109
1110 size_t ret = s.total_out;
1111
1112 err = nncxZlib_inflateEnd(&s);
1113 if (err != Z_OK)
1114 {
1115 return detail::ConvertZlibReturnCode(err);
1116 }
1117
1118 return ret;
1119 }
1120 }
1121
GetGzipUncompressedSize(const void * pSrc,size_t srcSize)1122 size_t GetGzipUncompressedSize(const void* pSrc, size_t srcSize)
1123 {
1124 return *reinterpret_cast<NN_PACKED size_t*>(reinterpret_cast<uptr>(pSrc) + srcSize - 4);
1125 }
1126
UncompressGzip(void * pDest,size_t destSize,const void * pSrc,size_t srcSize,void * pWork)1127 s32 UncompressGzip(void* pDest, size_t destSize, const void* pSrc, size_t srcSize, void* pWork )
1128 {
1129 NN_POINTER_TASSERT_(pDest);
1130 NN_POINTER_TASSERT_(pSrc);
1131 NN_POINTER_TASSERT_(pWork);
1132
1133 const int wbits = MAX_WBITS + 16; // Specify +16 = gzip format
1134 return UncompressDeflateCommon(pDest, destSize, pSrc, srcSize, pWork, wbits);
1135 }
1136
UncompressZlib(void * pDest,size_t destSize,const void * pSrc,size_t srcSize,void * pWork)1137 s32 UncompressZlib(void* pDest, size_t destSize, const void* pSrc, size_t srcSize, void* pWork )
1138 {
1139 NN_POINTER_TASSERT_(pDest);
1140 NN_POINTER_TASSERT_(pSrc);
1141 NN_POINTER_TASSERT_(pWork);
1142
1143 return UncompressDeflateCommon(pDest, destSize, pSrc, srcSize, pWork, MAX_WBITS);
1144 }
1145
UncompressDeflate(void * pDest,size_t destSize,const void * pSrc,size_t srcSize,void * pWork)1146 s32 UncompressDeflate(void* pDest, size_t destSize, const void* pSrc, size_t srcSize, void* pWork )
1147 {
1148 NN_POINTER_TASSERT_(pDest);
1149 NN_POINTER_TASSERT_(pSrc);
1150 NN_POINTER_TASSERT_(pWork);
1151
1152 int headerSize = ((GetUncompressedSize(pSrc) >> 24) == 0) ? 4: 8;
1153 const void* pDeflate = reinterpret_cast<const bit8*>(pSrc) + headerSize;
1154
1155
1156 const int wbits = - MAX_WBITS; // Specify - = raw deflate format
1157 return UncompressDeflateCommon(pDest, destSize, pDeflate, srcSize - headerSize, pWork, wbits);
1158 }
1159
1160 } // namespace cx
1161 } // namespace nn
1162