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 Since decompression processes for all types of compression are linked, it may be better to execute separate functions for each for each compression type when not using formats other than the specific compression formats.
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 // Measures for buffer overrun 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 // Measures for buffer overrun 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 - Decompresses LZ77 compressed data, writing 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 // Measures for buffer overrun 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 1 data bit size (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 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: CXSecureUnfilterDiff
573
574 Description: 8-bit decompression to restore differential filter conversion.
575
576 - Restores a differential filter, writing in 8 bit units.
577 - Use 4 byte alignment for the source address.
578
579 Arguments: *srcp Source address
580 *destp Destination address
581
582 Returns: Returns 0 when conversion succeeds
583 Returns a negative error code if failed.
584 *---------------------------------------------------------------------------*/
CXSecureUnfilterDiff(register const void * srcp,u32 srcSize,register void * destp)585 s32 CXSecureUnfilterDiff( register const void *srcp, u32 srcSize, register void *destp )
586 {
587 const u8* pSrc = srcp;
588 u8* pDst = destp;
589 u32 bitSize = *pSrc & 0xFU;
590 u8 compType = (u8)( CXiConvertEndian_( *(u32*)pSrc ) & 0xFF );
591 s32 destCount = (s32)( CXiConvertEndian_( *(u32*)pSrc ) >> 8 );
592 u32 sum = 0;
593 s32 srcCount = (s32)srcSize;
594
595 if ( (compType & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_DIFF )
596 {
597 return CX_ERR_UNSUPPORTED;
598 }
599 if ( (bitSize != 0) && (bitSize != 1) )
600 {
601 return CX_ERR_UNSUPPORTED;
602 }
603 if ( srcSize <= 4 )
604 {
605 return CX_ERR_SRC_SHORTAGE;
606 }
607
608 pSrc += 4;
609 srcCount -= 4;
610
611 if ( bitSize != 1 )
612 {
613 // Difference calculation in units of 8 bits
614 do
615 {
616 u8 tmp = *(pSrc++);
617 if ( --srcCount < 0 )
618 {
619 return CX_ERR_SRC_SHORTAGE;
620 }
621 destCount--;
622 sum += tmp;
623 *(pDst++) = (u8)sum;
624 } while ( destCount > 0 );
625 }
626 else
627 {
628 // Difference calculation in units of 16 bits
629 do
630 {
631 u16 tmp = CXiConvertEndian16_( *(u16*)pSrc );
632 pSrc += 2;
633 srcCount -= 2;
634 if ( srcCount < 0 )
635 {
636 return CX_ERR_SRC_SHORTAGE;
637 }
638 destCount -= 2;
639 sum += tmp;
640 *(u16*)pDst = CXiConvertEndian16_( (u16)sum );
641 pDst += 2;
642 } while ( destCount > 0 );
643 }
644 if ( srcCount > 32 )
645 {
646 return CX_ERR_SRC_REMAINDER;
647 }
648
649 return CX_ERR_SUCCESS;
650 }
651
652