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 <revolution/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 expansion
34 *---------------------------------------------------------------------------*/
CXGetUncompressedSize(const void * srcp)35 u32 CXGetUncompressedSize( const void *srcp )
36 {
37 #if defined( CX_PLATFORM_IS_BIGENDIAN )
38 return CXiConvertEndian_( *(u32*)srcp ) >> 8;
39 #else
40 return ( *(u32*)srcp >> 8 );
41 #endif
42 }
43
44
45 /*---------------------------------------------------------------------------*
46 Name: CXUncompressAny
47
48 Description: Determines the compression type from the data header and
49 runs the appropriate decompression process.
50 As all the decompression for compression types are linked,
51 it would be good to run this function for each compression type unless
52 a special compression format is used.
53
54 Arguments: srcp source address
55 destp destination address
56
57 Returns: None.
58 *---------------------------------------------------------------------------*/
CXUncompressAny(const void * srcp,void * destp)59 void CXUncompressAny( const void* srcp, void* destp )
60 {
61 switch ( CXGetCompressionType( srcp ) )
62 {
63 // Run-length compressed data
64 case CX_COMPRESSION_RL:
65 CXUncompressRL( srcp, destp );
66 break;
67 // LZ77 compressed data
68 case CX_COMPRESSION_LZ:
69 CXUncompressLZ( srcp, destp );
70 break;
71 // Huffman compressed data
72 case CX_COMPRESSION_HUFFMAN:
73 CXUncompressHuffman( srcp, destp );
74 break;
75 // Difference filter
76 case CX_COMPRESSION_DIFF:
77 CXUnfilterDiff( srcp, destp );
78 break;
79 default:
80 ASSERTMSG( 0, "Unknown compressed format" );
81 }
82 }
83
84
85 /*---------------------------------------------------------------------------*
86 Name: CXUncompressRL
87
88 Description: 8-bit expanding runlength compressed data
89
90 * Expands runlength compressed data, and writes in 8-bit units.
91 - Align source address to a 4-byte boundary.
92
93 * Data header
94 u32 :4 reserved
95 compType:4 compression type ( = 3)
96 destSize:24 Data size after decoding
97
98 * Flag data format
99 u8 length:7 Expansion data length - 1 (When not compressed)
100 Expansion data length - 3 (Only compress when the contiguous length is 3-bytes or greater)
101 flag:1 (0, 1) = (not compressed, compressed)
102
103 Arguments: *srcp source address
104 *destp destination address
105
106 Returns: None.
107 *---------------------------------------------------------------------------*/
CXUncompressRL(const void * srcp,void * destp)108 void CXUncompressRL( const void *srcp, void *destp )
109 {
110 const u8 *pSrc = srcp;
111 u8 *pDst = destp;
112 u32 destCount = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
113
114 pSrc += 4;
115 while ( destCount > 0 )
116 {
117 u8 flags = *pSrc++;
118 s32 length = flags & 0x7f;
119 if ( !(flags & 0x80) )
120 {
121 length++;
122 destCount -= length;
123 do
124 {
125 *pDst++ = *pSrc++;
126 } while ( --length > 0 );
127 }
128 else
129 {
130 u8 srcTmp;
131
132 length += 3;
133 destCount -= length;
134 srcTmp = *pSrc++;
135 do
136 {
137 *pDst++ = srcTmp;
138 } while ( --length > 0 );
139 }
140 }
141 }
142
143
144 /*---------------------------------------------------------------------------*
145 Name: CXUncompressLZ
146
147 Description: 8-bit expanding LZ77 compressed data
148
149 * Expands LZ77 compressed data, and writes in 8-bit units.
150 - Align source address to a 4-byte boundary.
151
152 * Data header
153 u32 :4 reserved
154 compType:4 compression type ( = 1)
155 destSize:24 Data size after decoding
156
157 * Flag data format
158 u8 flags compression/no compression flag
159 (0, 1) = (not compressed, compressed)
160 * Code data format (Big Endian)
161 u16 length:4 Expansion data length - 3(Only compress when the match length is 3-bytes or greater)
162 offset:12 match data offset - 1
163
164 Arguments: *srcp source address
165 *destp destination address
166
167 Returns: None.
168 *---------------------------------------------------------------------------*/
CXUncompressLZ(const void * srcp,void * destp)169 void CXUncompressLZ( const void *srcp, void *destp )
170 {
171 const u8* pSrc = srcp;
172 u8* pDst = destp;
173 u32 destCount = CXiConvertEndian_( *(u32 *)pSrc ) >> 8;
174
175 pSrc += 4;
176 while ( destCount > 0 )
177 {
178 u32 i;
179 u32 flags = *pSrc++;
180 for ( i = 0; i < 8; ++i )
181 {
182 if ( !(flags & 0x80) )
183 {
184 *pDst++ = *pSrc++;
185 destCount--;
186 }
187 else
188 {
189 s32 length = (*pSrc >> 4) + 3;
190 s32 offset = (*pSrc++ & 0x0f) << 8;
191 offset = (offset | *pSrc++) + 1;
192 destCount -= length;
193 do
194 {
195 *pDst++ = pDst[ -offset ];
196 } while ( --length > 0);
197 }
198 if ( destCount <= 0 )
199 {
200 break;
201 }
202 flags <<= 1;
203 }
204 }
205 }
206
207
208 /*---------------------------------------------------------------------------*
209 Name: CXUncompressHuffman
210
211 Description: Expanding Huffman compressed data
212
213 * Expands Huffman compressed data, and writes in 32-bit units.
214 - Align source address to a 4-byte boundary.
215 - Align the destination address to a four byte boundary.
216 - The compression buffer size must be prepared in 4-byte multiples.
217
218 * Data header
219 u32 bitSize:4 1 data bit size (Normally 4|8)
220 compType:4 compression type ( = 2)
221 destSize:24 Data size after decoding
222
223 * Tree table
224 u8 treeSize tree table size/2 - 1
225 TreeNodeData nodeRoot root node
226
227 TreeNodeData nodeLeft root left node
228 TreeNodeData nodeRight root right node
229
230 TreeNodeData nodeLeftLeft left left node
231 TreeNodeData nodeLeftRight left ride node
232
233 TreeNodeData nodeRightLeft right left node
234 TreeNodeData nodeRightRight right right node
235
236 �E
237 �E
238
239 The compress data structure follows
240
241 * TreeNodeData structure
242 u8 nodeNextOffset:6 Offset to the next node data - 1 (2-byte units)
243 rightEndFlag:1 right node end flag
244 leftEndzflag:1 Left node end flag
245 when end flag is set
246 there is data in next node
247
248 Arguments: *srcp source address
249 *destp destination address
250
251 Returns: None.
252 *---------------------------------------------------------------------------*/
CXUncompressHuffman(const void * srcp,void * destp)253 void CXUncompressHuffman( const void *srcp, void *destp )
254 {
255 #define TREE_END 0x80
256 const u32 *pSrc = srcp;
257 u32 *pDst = destp;
258 u8 *treep = (u8 *)pSrc + 4;
259 u8 *treeStartp = treep + 1;
260 u32 dataBit = *(u8*)pSrc & 0x0FU;
261 u32 destTmp = 0;
262 u32 destTmpCount = 0;
263 u32 destTmpDataNum = 4 + ( dataBit & 0x7 );
264 s32 destCount = (s32)( CXiConvertEndian_( *pSrc ) >> 8 );
265
266 pSrc = (u32*)( treep + ((*treep + 1) << 1) );
267 treep = treeStartp;
268
269 while ( destCount > 0 )
270 {
271 s32 srcCount = 32;
272 u32 srcTmp = CXiConvertEndian_( *pSrc++ ); // endian strategy
273 while ( --srcCount >= 0 )
274 {
275 u32 treeShift = (srcTmp >> 31) & 0x1;
276 u32 treeCheck = *treep;
277 treeCheck <<= treeShift;
278 treep = (u8*)( (((u32)treep >> 1) << 1) + (((*treep & 0x3f) + 1) << 1) + treeShift );
279 if ( treeCheck & TREE_END )
280 {
281 destTmp >>= dataBit;
282 destTmp |= *treep << (32 - dataBit);
283 treep = treeStartp;
284 if ( ++destTmpCount == destTmpDataNum )
285 {
286 // over-access until the end of the decompression buffer is 4-byte aligned
287 *pDst++ = CXiConvertEndian_(destTmp); // endian strategy
288 destCount -= 4;
289 destTmpCount = 0;
290 }
291 }
292 if ( destCount <= 0 )
293 {
294 break;
295 }
296 srcTmp <<= 1;
297 }
298 }
299 }
300
301
302 /*---------------------------------------------------------------------------*
303 Name: CXUnfilterDiff
304
305 Description: Decode differential filter conversion. Use 8-bit decoding.
306
307 - Decodes a differential filter. Writes in 8-bit units.
308 - Align source address to a 4-byte boundary.
309
310 Arguments: *srcp source address
311 *destp destination address
312
313 Returns: None.
314 *---------------------------------------------------------------------------*/
CXUnfilterDiff(register const void * srcp,register void * destp)315 void CXUnfilterDiff( register const void *srcp, register void *destp )
316 {
317 const u8* pSrc = srcp;
318 u8* pDst = destp;
319 u32 bitSize = *pSrc & 0xFU;
320 s32 destCount = (s32)( CXiConvertEndian_( *(u32*)pSrc ) >> 8 );
321 u32 sum = 0;
322
323 pSrc += 4;
324
325 if ( bitSize != 1 )
326 {
327 // diff calculation in units of 8 bits
328 do
329 {
330 u8 tmp = *(pSrc++);
331 destCount--;
332 sum += tmp;
333 *(pDst++) = (u8)sum;
334 } while ( destCount > 0 );
335 }
336 else
337 {
338 // diff calculation in units of 16 bits
339 do
340 {
341 u16 tmp = CXiConvertEndian16_( *(u16*)pSrc );
342 pSrc += 2;
343 destCount -= 2;
344 sum += tmp;
345 *(u16*)pDst = CXiConvertEndian16_( (u16)sum );
346 pDst += 2;
347 } while ( destCount > 0 );
348 }
349 }
350
351
352 /*---------------------------------------------------------------------------*
353 Name: CXGetCompressionHeader
354
355 Description: Gets header information from the first four bytes in the compression data
356
357 Arguments: data a pointer to the first four bytes of data in the compressed data
358
359 Returns: None.
360 *---------------------------------------------------------------------------*/
CXGetCompressionHeader(const void * data)361 CXCompressionHeader CXGetCompressionHeader( const void* data )
362 {
363 #if defined( CX_PLATFORM_IS_BIGENDIAN )
364 CXCompressionHeader ret;
365
366 ret.compType = (*(u8*)data & 0xF0) >> 4;
367 ret.compParam = *(u8*)data & 0x0F;
368 ret.destSize = CXiConvertEndian_( *(u32*)data ) >> 8;
369 return ret;
370 #else
371 return *(CXCompressionHeader*)data;
372 #endif
373 }
374
375