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 "CXUtil.h"
18
19
20 /*---------------------------------------------------------------------------*
21 Name: CXInitUncompContextRL
22
23 Description: Initializes the streaming uncompression context for run-length
24 compressed data
25
26 Arguments: context Pointer to the run-length uncompressed context
27 dest Destination address for uncompressed data
28
29 Returns: Can get the data size after decompression.
30
31 *---------------------------------------------------------------------------*/
CXInitUncompContextRL(CXUncompContextRL * context,void * dest)32 void CXInitUncompContextRL( CXUncompContextRL *context, void* dest )
33 {
34 context->destp = (u8*)dest;
35 context->destCount = 0;
36 context->flags = 0;
37 context->length = 0;
38 context->headerSize = 4;
39 }
40
41
42 /*---------------------------------------------------------------------------*
43 Name: CXInitUncompContextLZ
44
45 Description: Initializes the streaming uncompression context for LZ compressed data.
46
47 Arguments: context Pointer to the LZ uncompressed context
48 dest Destination address for uncompressed data
49 header a pointer to the leading data for the compressed data
50
51 *---------------------------------------------------------------------------*/
CXInitUncompContextLZ(CXUncompContextLZ * context,void * dest)52 void CXInitUncompContextLZ( CXUncompContextLZ *context, void* dest )
53 {
54 context->destp = (u8*)dest;
55 context->destCount = 0;
56 context->flags = 0;
57 context->flagIndex = 0;
58 context->length = 0;
59 context->lengthFlg = 0;
60 context->headerSize = 4;
61 }
62
63
64 /*---------------------------------------------------------------------------*
65 Name: CXInitUncompContextHuffman
66
67 Description: Initializes the streaming uncompression context for Huffman compressed data.
68
69 Arguments: context Pointer to the Huffman uncompressed context
70 dest Destination address for uncompressed data
71 header a pointer to the leading data for the compressed data
72
73 *---------------------------------------------------------------------------*/
CXInitUncompContextHuffman(CXUncompContextHuffman * context,void * dest)74 void CXInitUncompContextHuffman( CXUncompContextHuffman *context, void* dest )
75 {
76 context->destp = (u8*)dest;
77 context->destCount = 0;
78 context->bitSize = 0;
79 context->treeSize = -1;
80 context->treep = &context->tree[ 0 ];
81 context->destTmp = 0;
82 context->destTmpCnt = 0;
83 context->srcTmp = 0;
84 context->srcTmpCnt = 0;
85 context->headerSize = 4;
86 }
87
88
89 /*---------------------------------------------------------------------------*
90 Name: CXReadUncompRL
91
92 Description: This function performs streaming uncompression of run-length compressed data.
93 Data is written in units of 8bits. Data cannot be directly uncompressed to VRAM.
94
95 Arguments: context Pointer to the run-length uncompressed context
96 data Pointer to the next data
97 len Data size
98
99 Returns: Size of remaining uncompressed data.
100
101 *---------------------------------------------------------------------------*/
CXReadUncompRL(CXUncompContextRL * context,const void * data,u32 len)102 s32 CXReadUncompRL( CXUncompContextRL *context, const void* data, u32 len )
103 {
104 const u8* srcp = (const u8*)data;
105 u8 srcTmp;
106
107 // Header analysis
108 while ( context->headerSize > 0 )
109 {
110 if ( --context->headerSize <= 2 )
111 {
112 context->destCount |= (*srcp << ((2 - context->headerSize) * 8));
113 }
114 ++srcp;
115 if ( --len == 0 )
116 {
117 return (context->headerSize == 0)? context->destCount : -1;
118 }
119 }
120
121 while ( context->destCount > 0 )
122 {
123 // process when length is greater than 0
124 if ( ! (context->flags & 0x80) )
125 // compressed data has a length not equal to 0
126 {
127 while ( context->length > 0 )
128 {
129 *context->destp++ = *srcp++;
130 context->length--;
131 context->destCount--;
132 len--;
133 // end when the prepared buffer has been read in full
134 if ( len == 0 )
135 {
136 return context->destCount;
137 }
138 }
139 }
140 else if ( context->length > 0 )
141 // compressed data has a length not equal to 0
142 {
143 srcTmp = *srcp++;
144 len--;
145 while ( context->length > 0 )
146 {
147 *context->destp++ = srcTmp;
148 context->length--;
149 context->destCount--;
150 }
151 if ( len == 0 )
152 {
153 return context->destCount;
154 }
155 }
156
157 // reading the flag byte
158 context->flags = *srcp++;
159 len--;
160 context->length = (u16)(context->flags & 0x7F);
161 if ( context->flags & 0x80 )
162 {
163 context->length += 3;
164 }
165 else
166 {
167 context->length += 1;
168 }
169
170 if ( len == 0 )
171 {
172 return context->destCount;
173 }
174 }
175 return context->destCount;
176 }
177
178
179 /*---------------------------------------------------------------------------*
180 Name: CXReadUncompLZ
181
182 Description: This function performs streaming uncompression of LZ compressed data.
183 Data is written in units of 8bits. Data cannot be directly uncompressed to VRAM.
184
185 Arguments: context Pointer to the LZ uncompressed context
186 data Pointer to the next data
187 len Data size
188
189 Returns: Size of remaining uncompressed data.
190
191 *---------------------------------------------------------------------------*/
CXReadUncompLZ(CXUncompContextLZ * context,const void * data,u32 len)192 s32 CXReadUncompLZ( CXUncompContextLZ *context, const void* data, u32 len )
193 {
194 const u8* srcp = (const u8*)data;
195 s32 offset;
196
197 // Header analysis
198 while ( context->headerSize > 0 )
199 {
200 if ( --context->headerSize <= 2 )
201 {
202 context->destCount |= (*srcp << ((2 - context->headerSize) * 8));
203 }
204 ++srcp;
205 if ( --len == 0 )
206 {
207 return (context->headerSize == 0)? context->destCount : -1;
208 }
209 }
210
211 while ( context->destCount > 0 )
212 {
213 while ( context->flagIndex > 0 )
214 {
215 if ( len == 0 )
216 {
217 return context->destCount;
218 }
219
220 if ( ! (context->flags & 0x80) )
221 // process for non-compressed data
222 {
223 *context->destp++ = *srcp++;
224 context->destCount--;
225 len--;
226 }
227 else
228 // process for compressed data
229 {
230 if ( context->lengthFlg == 0 )
231 {
232 context->length = *srcp++;
233 context->lengthFlg = 1;
234 len--;
235 }
236
237 if ( len == 0 )
238 {
239 return context->destCount;
240 }
241
242 offset = (context->length & 0xF) << 8;
243 context->length = (u8)( (context->length >> 4) + 3 );
244 offset = (offset | *srcp++) + 1;
245 len--;
246 context->lengthFlg = 0;
247
248 // copy a length amount of data at the offset position
249 while ( context->length > 0 )
250 {
251 *context->destp = context->destp[ -offset ];
252 context->destp++;
253 context->destCount--;
254 context->length--;
255 }
256 }
257
258 if ( context->destCount == 0 )
259 {
260 return context->destCount;
261 }
262 context->flags <<= 1;
263 context->flagIndex--;
264 }
265
266 if ( len == 0 )
267 {
268 return context->destCount;
269 }
270 // read a new flag
271 context->flags = *srcp++;
272 context->flagIndex = 8;
273 len--;
274 }
275 return context->destCount;
276 }
277
278
279 // get the next node in the Huffman signed table
GetNextNode(const u8 * pTree,u32 select)280 static inline u8* GetNextNode( const u8* pTree, u32 select )
281 {
282 return (u8*)( ((u32)pTree & ~0x1) + ( ( (*pTree & 0x3F) + 1 ) * 2 ) + select );
283 }
284
285
286 /*---------------------------------------------------------------------------*
287 Name: CXReadUncompHuffman
288
289 Description: This function performs streaming uncompression of Huffman compressed data.
290
291 Arguments: context Pointer to the Huffman uncompressed context
292 data Pointer to the next data
293 len Data size
294
295 Returns: Size of remaining uncompressed data.
296
297 *---------------------------------------------------------------------------*/
CXReadUncompHuffman(CXUncompContextHuffman * context,const void * data,u32 len)298 s32 CXReadUncompHuffman( CXUncompContextHuffman *context, const void* data, u32 len )
299 {
300 #define TREE_END_MASK 0x80U
301 const u8* srcp = (const u8*)data;
302 u32 select;
303 u32 endFlag;
304
305 while ( context->headerSize > 0 )
306 {
307 if ( --context->headerSize <= 2 )
308 {
309 context->destCount |= (*srcp << ((2 - context->headerSize) * 8));
310 }
311 else
312 {
313 context->bitSize = (u8)(*srcp & 0xF);
314 }
315 ++srcp;
316 if ( --len == 0 )
317 {
318 return (context->headerSize == 0)? context->destCount : -1;
319 }
320 }
321
322 // treeSize is set to -1 in CXInitUncompContextHuffman
323 // when context->treeSize is negative, the data's beginning is used
324 if ( context->treeSize < 0 )
325 {
326 context->treeSize = (s16)( ( *srcp + 1 ) * 2 - 1);
327 *context->treep++ = *srcp++;
328 len--;
329 }
330
331 // load the Huffman signed table
332 while ( context->treeSize > 0 )
333 {
334 if ( len == 0 )
335 {
336 return context->destCount;
337 }
338 *context->treep++ = *srcp++;
339 context->treeSize--;
340 len--;
341 if ( context->treeSize == 0 )
342 {
343 context->treep = &context->tree[ 1 ];
344 }
345 }
346
347 // decoding process
348 while ( context->destCount > 0 )
349 {
350 // src data is read in 4-byte units
351 while ( context->srcTmpCnt < 32 )
352 {
353 if ( len == 0 )
354 {
355 return context->destCount;
356 }
357 context->srcTmp |= (*srcp++) << context->srcTmpCnt;
358 len--;
359 context->srcTmpCnt += 8;
360 }
361
362 // the loaded 32 bits are decoded After those 32 bits are processed, the next 4 bytes are read.
363 while ( context->srcTmpCnt > 0 )
364 {
365 select = context->srcTmp >> 31;
366 endFlag = (*context->treep << select) & TREE_END_MASK;
367 context->treep = GetNextNode( context->treep, select );
368 context->srcTmp <<= 1;
369 context->srcTmpCnt--;
370
371 if ( ! endFlag )
372 {
373 continue;
374 }
375
376 // When the Huffman tree's terminal flag is set, data is stored
377 // at the end of the offset
378 context->destTmp >>= context->bitSize;
379 context->destTmp |= *context->treep << ( 32 - context->bitSize );
380 context->treep = &context->tree[ 1 ];
381 context->destTmpCnt += context->bitSize;
382 // write in 4 byte units
383 if ( context->destTmpCnt == 32 )
384 {
385 *(u32*)context->destp = CXiConvertEndian_( context->destTmp );
386 context->destp += 4;
387 context->destCount -= 4;
388 context->destTmpCnt = 0;
389 if ( context->destCount <= 0 )
390 {
391 return 0;
392 }
393 }
394 }
395 }
396
397 return 0;
398 }
399
400