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 "CXUtil.h"
19
20
21 //======================================================================
22 // Expanding compressed data
23 //======================================================================
24
25 /*---------------------------------------------------------------------------*
26 Name: CXGetUncompressedSize
27
28 Description: Gets the data size after decompression.
29 This function can be used for data in all compression formats handled by CX.
30
31 Arguments: srcp : Starting address of the compressed data
32
33 Returns: Data size after decompression
34 *---------------------------------------------------------------------------*/
CXGetUncompressedSize(const void * srcp)35 u32 CXGetUncompressedSize( const void *srcp )
36 {
37 u32 size = CXiConvertEndian_( *(u32*)srcp ) >> 8;
38 if ( size == 0 )
39 {
40 size = CXiConvertEndian_( *((u32*)srcp + 1) );
41 }
42 return size;
43 }
44
45
46 /*---------------------------------------------------------------------------*
47 Name: CXUncompressAny
48
49 Description: Determines the compression type from the data header and performs the appropriate decompression.
50
51 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.
52
53
54
55 Arguments: srcp Source address
56 destp Destination address
57
58 Returns: None.
59 *---------------------------------------------------------------------------*/
CXUncompressAny(const void * srcp,void * destp)60 void CXUncompressAny( const void* srcp, void* destp )
61 {
62 switch ( CXGetCompressionType( srcp ) )
63 {
64 // Run-length compressed data
65 case CX_COMPRESSION_RL:
66 CXUncompressRL( srcp, destp );
67 break;
68 // LZ77 compressed data
69 case CX_COMPRESSION_LZ:
70 CXUncompressLZ( srcp, destp );
71 break;
72 // Huffman compressed data
73 case CX_COMPRESSION_HUFFMAN:
74 CXUncompressHuffman( srcp, destp );
75 break;
76 // Difference filter
77 case CX_COMPRESSION_DIFF:
78 CXUnfilterDiff( srcp, destp );
79 break;
80 default:
81 ASSERTMSG( 0, "Unknown compressed format" );
82 }
83 }
84
85
86 /*---------------------------------------------------------------------------*
87 Name: CXUncompressRL
88
89 Description: 8-bit decompression of run-length compressed data
90
91 - Decompresses run-length compressed data, writing in 8 bit units.
92 - Use 4 byte alignment for the source address.
93
94 - Data header
95 u32 :4 Reserved
96 compType:4 Compression type( = 3)
97 destSize:24 Data size after decompression
98
99 - Flag data format
100 u8 length:7 Decompressed data length - 1 (When not compressed)
101 Decompressed data length - 3 (only compress when the contiguous length is 3 bytes or greater)
102 flag:1 (0, 1) = (not compressed, compressed)
103
104 Arguments: *srcp Source address
105 *destp Destination address
106
107 Returns: None.
108 *---------------------------------------------------------------------------*/
CXUncompressRL(const void * srcp,void * destp)109 void CXUncompressRL( const void *srcp, void *destp )
110 {
111 const u8 *pSrc = srcp;
112 u8 *pDst = destp;
113 u32 destCount = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
114 pSrc += 4;
115
116 if ( destCount == 0 )
117 {
118 destCount = CXiConvertEndian_( *(u32*)pSrc );
119 pSrc += 4;
120 }
121
122 while ( destCount > 0 )
123 {
124 u8 flags = *pSrc++;
125 u32 length = flags & 0x7fU;
126 if ( !(flags & 0x80) )
127 {
128 length++;
129 if ( length > destCount )
130 // Measures for buffer overrun when invalid data is decompressed.
131 {
132 length = destCount;
133 }
134
135 destCount -= length;
136 do
137 {
138 *pDst++ = *pSrc++;
139 } while ( --length > 0 );
140 }
141 else
142 {
143 u8 srcTmp;
144
145 length += 3;
146 if ( length > destCount )
147 // Measures for buffer overrun when invalid data is decompressed.
148 {
149 length = destCount;
150 }
151
152 destCount -= length;
153 srcTmp = *pSrc++;
154 do
155 {
156 *pDst++ = srcTmp;
157 } while ( --length > 0 );
158 }
159 }
160 }
161
162
163 /*---------------------------------------------------------------------------*
164 Name: CXUncompressLZ
165
166 Description: 8-bit decompression of LZ77 compressed data
167
168 - Decompresses LZ77 compressed data, writing in 8 bit units.
169 - Use 4 byte alignment for the source address.
170
171 - Data header
172 u32 :4 Reserved
173 compType:4 Compression type( = 1)
174 destSize:24 Data size after decompression
175
176 - Flag data format
177 u8 flags Compression/no compression flag
178 (0, 1) = (not compressed, compressed)
179 - Code data format (Big Endian)
180 u16 length:4 Decompressed data length - 3 (only compress when the match length is 3 bytes or greater)
181 offset:12 Match data offset - 1
182
183 Arguments: *srcp Source address
184 *destp Destination address
185
186 Returns: None.
187 *---------------------------------------------------------------------------*/
CXUncompressLZ(const void * srcp,void * destp)188 void CXUncompressLZ( const void *srcp, void *destp )
189 {
190 const u8* pSrc = srcp;
191 u8* pDst = destp;
192 u32 destCount = CXiConvertEndian_( *(u32 *)pSrc ) >> 8;
193 BOOL exFormat = (*pSrc & 0x0F)? TRUE : FALSE;
194
195 pSrc += 4;
196
197 if ( destCount == 0 )
198 {
199 destCount = CXiConvertEndian_( *(u32*)pSrc );
200 pSrc += 4;
201 }
202
203 while ( destCount > 0 )
204 {
205 u32 i;
206 u32 flags = *pSrc++;
207 for ( i = 0; i < 8; ++i )
208 {
209 if ( !(flags & 0x80) )
210 {
211 *pDst++ = *pSrc++;
212 destCount--;
213 }
214 else
215 {
216 s32 length = (*pSrc >> 4);
217 s32 offset;
218
219 if ( ! exFormat )
220 {
221 length += 3;
222 }
223 else
224 {
225 // LZ77 extended format
226 if ( length == 1 )
227 {
228 length = (*pSrc++ & 0x0F) << 12;
229 length |= (*pSrc++) << 4;
230 length |= (*pSrc >> 4);
231 length += 0xFF + 0xF + 3;
232 }
233 else if ( length == 0 )
234 {
235 length = (*pSrc++ & 0x0F) << 4;
236 length |= (*pSrc >> 4);
237 length += 0xF + 2;
238 }
239 else
240 {
241 length += 1;
242 }
243 }
244 offset = (*pSrc++ & 0x0f) << 8;
245 offset = (offset | *pSrc++) + 1;
246 if ( length > destCount )
247 // Measures for buffer overrun when invalid data is decompressed.
248 {
249 length = (s32)destCount;
250 }
251 destCount -= length;
252 do
253 {
254 *pDst++ = pDst[ -offset ];
255 } while ( --length > 0 );
256 }
257 if ( destCount <= 0 )
258 {
259 break;
260 }
261 flags <<= 1;
262 }
263 }
264 }
265
266
267 /*---------------------------------------------------------------------------*
268 Name: CXUncompressHuffman
269
270 Description: Decompression of Huffman compressed data
271
272 - Decompresses Huffman compressed data, writing in 32 bit units.
273 - Use 4 byte alignment for the source address.
274 - Use 4 byte alignment for the destination address.
275 - The target decompression buffer size must be prepared in 4 byte multiples.
276
277 - Data header
278 u32 bitSize:4 1 data bit size (Normally 4|8)
279 compType:4 Compression type( = 2)
280 destSize:24 Data size after decompression
281
282 - Tree table
283 u8 treeSize Tree table size/2 - 1
284 TreeNodeData nodeRoot Root node
285
286 TreeNodeData nodeLeft Root left node
287 TreeNodeData nodeRight Root right node
288
289 TreeNodeData nodeLeftLeft Left left node
290 TreeNodeData nodeLeftRight Left right node
291
292 TreeNodeData nodeRightLeft Right left node
293 TreeNodeData nodeRightRight Right right node
294
295 .
296 .
297
298 The compressed data itself follows
299
300 - TreeNodeData structure
301 u8 nodeNextOffset:6 Offset to the next node data - 1 (2 byte units)
302 rightEndFlag:1 Right node end flag
303 leftEndzflag:1 Left node end flag
304 When end flag is set
305 There is data in next node
306
307 Arguments: *srcp Source address
308 *destp Destination address
309
310 Returns: None.
311 *---------------------------------------------------------------------------*/
CXUncompressHuffman(const void * srcp,void * destp)312 void CXUncompressHuffman( const void *srcp, void *destp )
313 {
314 #define TREE_END 0x80
315 const u32 *pSrc = srcp;
316 u32 *pDst = destp;
317 s32 destCount = (s32)( CXiConvertEndian_( *pSrc ) >> 8 );
318 u8 *treep = (destCount != 0)? ((u8*)pSrc + 4) : ((u8*)pSrc + 8);
319 u8 *treeStartp = treep + 1;
320 u32 dataBit = *(u8*)pSrc & 0x0FU;
321 u32 destTmp = 0;
322 u32 destTmpCount = 0;
323 u32 destTmpDataNum = 4 + ( dataBit & 0x7 );
324
325 if ( destCount == 0 )
326 {
327 destCount = (s32)( CXiConvertEndian_( *(pSrc + 1) ) );
328 }
329
330 pSrc = (u32*)( treep + ((*treep + 1) << 1) );
331 treep = treeStartp;
332
333 while ( destCount > 0 )
334 {
335 s32 srcCount = 32;
336 u32 srcTmp = CXiConvertEndian_( *pSrc++ ); // Endian strategy
337 while ( --srcCount >= 0 )
338 {
339 u32 treeShift = (srcTmp >> 31) & 0x1;
340 u32 treeCheck = *treep;
341 treeCheck <<= treeShift;
342 treep = (u8*)( (((u32)treep >> 1) << 1) + (((*treep & 0x3f) + 1) << 1) + treeShift );
343 if ( treeCheck & TREE_END )
344 {
345 destTmp >>= dataBit;
346 destTmp |= *treep << (32 - dataBit);
347 treep = treeStartp;
348 if ( ++destTmpCount == destTmpDataNum )
349 {
350 // Over-access until the last 4-byte alignment of the decompression buffer
351 *pDst++ = CXiConvertEndian_(destTmp); // Endian strategy
352 destCount -= 4;
353 destTmpCount = 0;
354 }
355 }
356 if ( destCount <= 0 )
357 {
358 break;
359 }
360 srcTmp <<= 1;
361 }
362 }
363 }
364
365
366 /*---------------------------------------------------------------------------*
367 Name: CXUnfilterDiff
368
369 Description: 8-bit decompression to restore differential filter conversion.
370
371 - Restores a differential filter, writing in 8 bit units.
372 - Use 4 byte alignment for the source address.
373
374 Arguments: *srcp Source address
375 *destp Destination address
376
377 Returns: None.
378 *---------------------------------------------------------------------------*/
CXUnfilterDiff(register const void * srcp,register void * destp)379 void CXUnfilterDiff( register const void *srcp, register void *destp )
380 {
381 const u8* pSrc = srcp;
382 u8* pDst = destp;
383 u32 bitSize = *pSrc & 0xFU;
384 s32 destCount = (s32)( CXiConvertEndian_( *(u32*)pSrc ) >> 8 );
385 u32 sum = 0;
386
387 pSrc += 4;
388
389 if ( bitSize != 1 )
390 {
391 // Difference calculation in units of 8 bits
392 do
393 {
394 u8 tmp = *(pSrc++);
395 destCount--;
396 sum += tmp;
397 *(pDst++) = (u8)sum;
398 } while ( destCount > 0 );
399 }
400 else
401 {
402 // Difference calculation in units of 16 bits
403 do
404 {
405 u16 tmp = CXiConvertEndian16_( *(u16*)pSrc );
406 pSrc += 2;
407 destCount -= 2;
408 sum += tmp;
409 *(u16*)pDst = CXiConvertEndian16_( (u16)sum );
410 pDst += 2;
411 } while ( destCount > 0 );
412 }
413 }
414
415
416 /*---------------------------------------------------------------------------*
417 Name: CXGetCompressionHeader
418
419 Description: Gets header information from the first four bytes in the compression data.
420
421 Arguments: data First 8 bytes of compressed data
422 *---------------------------------------------------------------------------*/
CXGetCompressionHeader(const void * data)423 CXCompressionHeader CXGetCompressionHeader( const void* data )
424 {
425 CXCompressionHeader ret;
426
427 ret.compType = (u8)( (*(u8*)data & 0xF0) >> 4 );
428 ret.compParam = (u8)( *(u8*)data & 0x0F );
429
430 ret.destSize = CXiConvertEndian_( *(u32*)data ) >> 8;
431 if ( ret.destSize == 0 )
432 {
433 ret.destSize = CXiConvertEndian_( *((u32*)data + 1) );
434 }
435 return ret;
436 }
437
438
439