1 /*---------------------------------------------------------------------------*
2 Project: Compress/uncompress library
3 File: CXStreamingUncompression.c
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 <revolution/cx/CXUncompression.h>
16 #include <revolution/cx/CXStreamingUncompression.h>
17 #include <revolution/cx/CXSecureUncompression.h>
18 #include "CXUtil.h"
19
20
21 /*---------------------------------------------------------------------------*
22 Name : CXInitUncompContextRL
23
24 Description : Initializes the streaming decompression context for run-length compressed data.
25
26
27 Arguments : context Pointer to the run-length uncompressed context
28 dest Destination address for uncompressed data
29
30 Returns : Can get the data size after decompression.
31
32 *---------------------------------------------------------------------------*/
CXInitUncompContextRL(CXUncompContextRL * context,void * dest)33 void CXInitUncompContextRL( CXUncompContextRL *context, void* dest )
34 {
35 context->destp = (u8*)dest;
36 context->destCount = 0;
37 context->flags = 0;
38 context->length = 0;
39 context->headerSize = 8;
40 context->forceDestCount = 0;
41 }
42
43
44 /*---------------------------------------------------------------------------*
45 Name : CXInitUncompContextLZ
46
47 Description : Initializes the streaming decompression context for LZ compressed data.
48
49 Arguments : context Pointer to the LZ uncompressed context
50 dest Destination address for uncompressed data
51 header Pointer to the start data for the compressed data
52
53 *---------------------------------------------------------------------------*/
CXInitUncompContextLZ(CXUncompContextLZ * context,void * dest)54 void CXInitUncompContextLZ( CXUncompContextLZ *context, void* dest )
55 {
56 context->destp = (u8*)dest;
57 context->destCount = 0;
58 context->flags = 0;
59 context->flagIndex = 0;
60 context->length = 0;
61 context->lengthFlg = 3;
62 context->headerSize = 8;
63 context->exFormat = 0;
64 context->forceDestCount = 0;
65 }
66
67
68 /*---------------------------------------------------------------------------*
69 Name : CXInitUncompContextHuffman
70
71 Description : Initializes the streaming decompression context for Huffman compressed data.
72
73 Arguments : context Pointer to the Huffman uncompressed context
74 dest Destination address for uncompressed data
75 header Pointer to the start data for the compressed data
76
77 *---------------------------------------------------------------------------*/
CXInitUncompContextHuffman(CXUncompContextHuffman * context,void * dest)78 void CXInitUncompContextHuffman( CXUncompContextHuffman *context, void* dest )
79 {
80 context->destp = (u8*)dest;
81 context->destCount = 0;
82 context->bitSize = 0;
83 context->treeSize = -1;
84 context->treep = &context->tree[ 0 ];
85 context->destTmp = 0;
86 context->destTmpCnt = 0;
87 context->srcTmp = 0;
88 context->srcTmpCnt = 0;
89 context->headerSize = 8;
90 context->forceDestCount = 0;
91 }
92
93 /*---------------------------------------------------------------------------*
94 Name: CXiReadHeader
95
96 Description: Header analysis
97
98 Arguments: headerSize Pointer to the remaining size of the header to be read
99 *destCount Pointer to the uncompressed data size
100 srcp Pointer to a buffer containing the header information
101 srcSize Pointer to the size of the buffer containing the header information
102 forceDestSize Uncompressed data size (if 0, use the binary header information as is)
103
104 Returns: The size of the source data read
105 *---------------------------------------------------------------------------*/
CXiReadHeader(u8 * headerSize,s32 * destCount,const u8 * srcp,u32 srcSize,s32 forceDestSize)106 static inline u32 CXiReadHeader( u8* headerSize, s32 *destCount, const u8* srcp, u32 srcSize, s32 forceDestSize )
107 {
108 u32 readLen = 0;
109 while ( *headerSize > 0 )
110 {
111 --(*headerSize);
112 if ( *headerSize <= 3 )
113 {
114 *destCount |= (*srcp << ((3 - *headerSize) * 8));
115 }
116 else if ( *headerSize <= 6 )
117 {
118 *destCount |= (*srcp << ((6 - *headerSize) * 8));
119 }
120 ++srcp;
121 ++readLen;
122 if ( *headerSize == 4 && *destCount > 0 )
123 {
124 *headerSize = 0;
125 }
126 if ( --srcSize == 0 && *headerSize > 0 )
127 {
128 return readLen;
129 }
130 }
131
132 if ( ( forceDestSize > 0 ) &&
133 ( forceDestSize < *destCount ) )
134 {
135 *destCount = forceDestSize;
136 }
137 return readLen;
138 }
139
140
141 /*---------------------------------------------------------------------------*
142 Name : CXReadUncompRL
143
144 Description : This function performs streaming decompression of run-length compressed data.
145 Data is written in units of 8 bits. Data cannot be directly uncompressed to VRAM.
146
147 Arguments : context Pointer to the run-length uncompressed context
148 data Pointer to the next data
149 len Data size
150
151 Returns : Size of remaining uncompressed data.
152 Returns a negative error code if failed.
153
154 *---------------------------------------------------------------------------*/
CXReadUncompRL(CXUncompContextRL * context,const void * data,u32 len)155 s32 CXReadUncompRL( CXUncompContextRL *context, const void* data, u32 len )
156 {
157 const u8* srcp = (const u8*)data;
158 u8 srcTmp;
159
160 // Header analysis
161 if ( context->headerSize > 0 )
162 {
163 u32 read_len;
164 if ( context->headerSize == 8 )
165 {
166 if ( (*srcp & CX_COMPRESSION_TYPE_MASK) != CX_COMPRESSION_RL )
167 {
168 return CX_ERR_UNSUPPORTED;
169 }
170 if ( (*srcp & 0x0F ) != 0 )
171 {
172 return CX_ERR_UNSUPPORTED;
173 }
174 }
175 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
176 srcp += read_len;
177 len -= read_len;
178 if ( len == 0 )
179 {
180 return (context->headerSize == 0)? context->destCount : -1;
181 }
182 }
183
184 while ( context->destCount > 0 )
185 {
186 // Process when length is greater than 0.
187 if ( ! (context->flags & 0x80) )
188 // Uncompressed data has a length not equal to 0
189 {
190 while ( context->length > 0 )
191 {
192 *context->destp++ = *srcp++;
193 context->length--;
194 context->destCount--;
195 len--;
196 // End when the prepared buffer has been read in full
197 if ( len == 0 )
198 {
199 return context->destCount;
200 }
201 }
202 }
203 else if ( context->length > 0 )
204 // Compressed data has a length not equal to 0
205 {
206 srcTmp = *srcp++;
207 len--;
208 while ( context->length > 0 )
209 {
210 *context->destp++ = srcTmp;
211 context->length--;
212 context->destCount--;
213 }
214 if ( len == 0 )
215 {
216 return context->destCount;
217 }
218 }
219
220 // Reading the flag byte
221 context->flags = *srcp++;
222 len--;
223 context->length = (u16)(context->flags & 0x7F);
224 if ( context->flags & 0x80 )
225 {
226 context->length += 3;
227 }
228 else
229 {
230 context->length += 1;
231 }
232
233 if ( context->length > context->destCount )
234 // Measures for buffer overrun when invalid data is decompressed.
235 {
236 if ( context->forceDestCount == 0 )
237 {
238 return CX_ERR_DEST_OVERRUN;
239 }
240 context->length = (u16)context->destCount;
241 }
242 if ( len == 0 )
243 {
244 return context->destCount;
245 }
246 }
247
248 // Processing to perform in the event that (context->destCount == 0)
249 if ( (context->forceDestCount == 0) && (len > 32) )
250 {
251 return CX_ERR_SRC_REMAINDER;
252 }
253 return 0;
254 }
255
256
257 /*---------------------------------------------------------------------------*
258 Name : CXReadUncompLZ
259
260 Description : This function performs streaming decompression of LZ compressed data.
261 Data is written in units of 8 bits. Data cannot be directly uncompressed to VRAM.
262
263 Arguments : context Pointer to the LZ uncompressed context
264 data Pointer to the next data
265 len Data size
266
267 Returns : Size of remaining uncompressed data.
268 Returns a negative error code if failed.
269
270 *---------------------------------------------------------------------------*/
CXReadUncompLZ(CXUncompContextLZ * context,const void * data,u32 len)271 s32 CXReadUncompLZ( CXUncompContextLZ *context, const void* data, u32 len )
272 {
273 const u8* srcp = (const u8*)data;
274 s32 offset;
275
276 // Header analysis
277 if ( context->headerSize > 0 )
278 {
279 u32 read_len;
280 // Process the first byte
281 if ( context->headerSize == 8 )
282 {
283 if ( ( *srcp & CX_COMPRESSION_TYPE_MASK ) != CX_COMPRESSION_LZ )
284 {
285 return CX_ERR_UNSUPPORTED;
286 }
287 // Record as an LZ compression parameter
288 context->exFormat = (u8)( *srcp & 0x0F );
289 if ( (context->exFormat != 0x0) && (context->exFormat != 0x1) )
290 {
291 return CX_ERR_UNSUPPORTED;
292 }
293 }
294 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
295 srcp += read_len;
296 len -= read_len;
297 if ( len == 0 )
298 {
299 return (context->headerSize == 0)? context->destCount : -1;
300 }
301 }
302
303 while ( context->destCount > 0 )
304 {
305 while ( context->flagIndex > 0 )
306 {
307 if ( len == 0 )
308 {
309 return context->destCount;
310 }
311
312 if ( ! (context->flags & 0x80) )
313 // Process for non-compressed data
314 {
315 *context->destp++ = *srcp++;
316 context->destCount--;
317 len--;
318 }
319 else
320 // Process for compressed data
321 {
322 while ( context->lengthFlg > 0 )
323 {
324 --context->lengthFlg;
325 if ( ! context->exFormat )
326 {
327 context->length = *srcp++;
328 context->length += (3 << 4);
329 context->lengthFlg = 0;
330 }
331 else
332 {
333 switch ( context->lengthFlg )
334 {
335 case 2:
336 {
337 context->length = *srcp++;
338 if ( (context->length >> 4) == 1 )
339 {
340 // Read two more bytes
341 context->length = (context->length & 0x0F) << 16;
342 context->length += ( (0xFF + 0xF + 3) << 4 );
343 }
344 else if ( (context->length >> 4) == 0 )
345 {
346 // Read one more byte
347 context->length = (context->length & 0x0F) << 8;
348 context->length += ( (0xF + 2) << 4 );
349 context->lengthFlg = 1;
350 }
351 else
352 {
353 context->length += (1 << 4);
354 context->lengthFlg = 0;
355 }
356 }
357 break;
358 case 1:
359 {
360 context->length += (*srcp++ << 8);
361 }
362 break;
363 case 0:
364 {
365 context->length += *srcp++;
366 }
367 break;
368 }
369 }
370 if ( --len == 0 )
371 {
372 return context->destCount;
373 }
374 }
375
376 offset = (context->length & 0xF) << 8;
377 context->length = context->length >> 4;
378 offset = (offset | *srcp++) + 1;
379 len--;
380 context->lengthFlg = 3;
381
382 // Measures for buffer overrun when invalid data is decompressed.
383 if ( context->length > context->destCount )
384 {
385 if ( context->forceDestCount == 0 )
386 {
387 return CX_ERR_DEST_OVERRUN;
388 }
389 context->length = context->destCount;
390 }
391 // Copy a length amount of data located at the offset position
392 while ( context->length > 0 )
393 {
394 *context->destp = context->destp[ -offset ];
395 context->destp++;
396 context->destCount--;
397 context->length--;
398 }
399 }
400
401 if ( context->destCount == 0 )
402 {
403 goto out;
404 }
405 context->flags <<= 1;
406 context->flagIndex--;
407 }
408
409 if ( len == 0 )
410 {
411 return context->destCount;
412 }
413 // Read a new flag
414 context->flags = *srcp++;
415 context->flagIndex = 8;
416 len--;
417 }
418
419 out:
420 // Processing to perform in the event that (context->destCount == 0)
421 if ( (context->forceDestCount == 0) && (len > 32) )
422 {
423 return CX_ERR_SRC_REMAINDER;
424 }
425 return 0;
426 }
427
428
429 // Get the next node in the Huffman signed table
GetNextNode(const u8 * pTree,u32 select)430 static inline u8* GetNextNode( const u8* pTree, u32 select )
431 {
432 return (u8*)( ((u32)pTree & ~0x1) + ( ( (*pTree & 0x3F) + 1 ) * 2 ) + select );
433 }
434
435 extern BOOL CXiVerifyHuffmanTable_( const void* pTable, u8 bit );
436
437 /*---------------------------------------------------------------------------*
438 Name : CXReadUncompHuffman
439
440 Description : This function performs streaming decompression of Huffman compressed data.
441 Returns a negative error code if failed.
442
443 Arguments : context Pointer to the Huffman uncompressed context
444 data Pointer to the next data
445 len Data size
446
447 Returns : Size of remaining uncompressed data.
448 Returns a negative error code if failed.
449
450 *---------------------------------------------------------------------------*/
CXReadUncompHuffman(CXUncompContextHuffman * context,const void * data,u32 len)451 s32 CXReadUncompHuffman( CXUncompContextHuffman *context, const void* data, u32 len )
452 {
453 #define TREE_END_MASK 0x80U
454 const u8* srcp = (const u8*)data;
455 u32 select;
456 u32 endFlag;
457
458 // Header analysis
459 if ( context->headerSize > 0 )
460 {
461 u32 read_len;
462 // Process the first byte
463 if ( context->headerSize == 8 )
464 {
465 context->bitSize = (u8)(*srcp & 0xF);
466
467 if ( ( *srcp & CX_COMPRESSION_TYPE_MASK ) != CX_COMPRESSION_HUFFMAN )
468 {
469 return CX_ERR_UNSUPPORTED;
470 }
471 if ( (context->bitSize != 4) && (context->bitSize != 8) )
472 {
473 return CX_ERR_UNSUPPORTED;
474 }
475 }
476 read_len = CXiReadHeader( &context->headerSize, &context->destCount, srcp, len, context->forceDestCount );
477 srcp += read_len;
478 len -= read_len;
479 if ( len == 0 )
480 {
481 return (context->headerSize == 0)? context->destCount : -1;
482 }
483 }
484
485 // treeSize is set to -1 in CXInitUncompContextHuffman.
486 // When context->treeSize is negative, the data's beginning is used.
487 if ( context->treeSize < 0 )
488 {
489 context->treeSize = (s16)( ( *srcp + 1 ) * 2 - 1 );
490 *context->treep++ = *srcp++;
491 len--;
492 }
493
494 // Load the Huffman signed table
495 while ( context->treeSize > 0 )
496 {
497 if ( len == 0 )
498 {
499 return context->destCount;
500 }
501 *context->treep++ = *srcp++;
502 context->treeSize--;
503 len--;
504 if ( context->treeSize == 0 )
505 {
506 context->treep = &context->tree[ 1 ];
507 if ( ! CXiVerifyHuffmanTable_( &context->tree[ 0 ], context->bitSize ) )
508 {
509 return CX_ERR_ILLEGAL_TABLE;
510 }
511 }
512 }
513
514 // Decoding process
515 while ( context->destCount > 0 )
516 {
517 // src data is read in 4-byte units
518 while ( context->srcTmpCnt < 32 )
519 {
520 if ( len == 0 )
521 {
522 return context->destCount;
523 }
524 context->srcTmp |= (*srcp++) << context->srcTmpCnt;
525 len--;
526 context->srcTmpCnt += 8;
527 }
528
529 // The loaded 32 bits are decoded. After those 32 bits are processed, the next 4 bytes are read.
530 while ( context->srcTmpCnt > 0 )
531 {
532 select = context->srcTmp >> 31;
533 endFlag = (*context->treep << select) & TREE_END_MASK;
534 context->treep = GetNextNode( context->treep, select );
535 context->srcTmp <<= 1;
536 context->srcTmpCnt--;
537
538 if ( ! endFlag )
539 {
540 continue;
541 }
542
543 // When the Huffman tree's terminal flag is set, data is stored at the end of the offset
544 //
545 context->destTmp >>= context->bitSize;
546 context->destTmp |= *context->treep << ( 32 - context->bitSize );
547 context->treep = &context->tree[ 1 ];
548 context->destTmpCnt += context->bitSize;
549
550 if ( context->destCount <= (context->destTmpCnt / 8) )
551 {
552 context->destTmp >>= (32 - context->destTmpCnt);
553 context->destTmpCnt = 32;
554 }
555
556 // Write in 4 byte units
557 if ( context->destTmpCnt == 32 )
558 {
559 *(u32*)context->destp = CXiConvertEndian_( context->destTmp );
560 context->destp += 4;
561 context->destCount -= 4;
562 context->destTmpCnt = 0;
563 if ( context->destCount <= 0 )
564 {
565 goto out;
566 }
567 }
568 }
569 }
570
571 out:
572 // Processing to perform in the event that (context->destCount == 0)
573 if ( (context->forceDestCount == 0) && (len > 32) )
574 {
575 return CX_ERR_SRC_REMAINDER;
576 }
577 return 0;
578 }
579
580
581