1 /*---------------------------------------------------------------------------*
2 Project: compress/uncompress library
3 File: CXCompression.h
4 Programmer: Makoto Takano
5
6 Copyright 2006 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 $Log: CXCompression.c,v $
15 Revision 1.9 07/05/2006 13:06:42 takano_makoto
16 revised indents
17
18 Revision 1.8 07/05/2006 10:38:39 takano_makoto
19 fixed a bug when a 1-byte over-access could occur when compression fails
20
21 Revision 1.7 07/05/2006 09:31:05 takano_makoto
22 separated HuffConvertData() into another function
23 Added ASSERT.
24
25 Revision 1.6 07/05/2006 08:12:20 takano_makoto
26 minor comment revisions
27
28 Revision 1.5 07/05/2006 05:54:29 takano_makoto
29 fixed a bug for the scope of Huffman table initialization
30
31 Revision 1.4 07/04/2006 13:18:55 takano_makoto
32 changed LZ compressed to a high-speed version using the work buffer
33 revised to void use of static variables in Huffman compression
34
35 $NoKeywords: $
36 *---------------------------------------------------------------------------*/
37
38
39 #include <dolphin/types.h>
40 #include <revolution/os.h>
41 #include <revolution/cx/CXUncompression.h>
42 #include <revolution/cx/CXCompression.h>
43 #include "CXUtil.h"
44
45
46 //===========================================================================
47 // LZ Encoding
48 //===========================================================================
49
50 // Temporary information for LZ high-speed encoding
51 typedef struct
52 {
53 u16 windowPos; // Initial position of the history window.
54 u16 windowLen; // Length of the history window.
55
56 s16 *LZOffsetTable; // Offset buffer of the history window.
57 s16 *LZByteTable; // Pointer to the most recent character history
58 s16 *LZEndTable; // Pointer to the oldest character history
59 }
60 LZCompressInfo;
61
62 static void LZInitTable( LZCompressInfo * info, void *work );
63 static u8 SearchLZ ( LZCompressInfo * info, const u8 *nextp, u32 remainSize, u16 *offset );
64 static void SlideByte ( LZCompressInfo * info, const u8 *srcp );
65 static inline void LZSlide ( LZCompressInfo * info, const u8 *srcp, u32 n );
66
67
68 /*---------------------------------------------------------------------------*
69 Name: CXCompressLZFast
70
71 Description: Function that performs LZ77 compression
72
73 Arguments: srcp Pointer to compression source data
74 size Size of compression source data
75 dstp Pointer to destination for compressed data
76 Buffer must be larger than size of compression source data.
77 work Temporary buffer for comprerssion
78 A region for the size of CX_LZ_FAST_COMPRESS_WORK_SIZE is necessary.
79
80 Returns: The data size after compression.
81 If compressed data is larger than original data, compression is terminated and 0 gets returned.
82 *---------------------------------------------------------------------------*/
CXCompressLZ(const u8 * srcp,u32 size,u8 * dstp,void * work)83 u32 CXCompressLZ(const u8 *srcp, u32 size, u8 *dstp, void *work)
84 {
85 u32 LZDstCount; // Number of bytes of compressed data
86 u8 LZCompFlags; // Flag series indicating whether there is a compression
87 u8 *LZCompFlagsp; // Point to memory regions storing LZCompFlags
88 u16 lastOffset; // Offset to matching data (the longest matching data at the time)
89 u8 lastLength; // Length of matching data (the longest matching data at the time)
90 u8 i;
91 u32 dstMax;
92 LZCompressInfo info; // Temporary LZ compression information
93
94 ASSERT( ((u32)srcp & 0x1) == 0 );
95 ASSERT( work != NULL );
96 ASSERT( size > 4 );
97
98 *(u32 *)dstp = CXiConvertEndian_( size << 8 | CX_COMPRESSION_LZ ); // data header
99 dstp += 4;
100 LZDstCount = 4;
101 dstMax = size;
102 LZInitTable(&info, work);
103
104 while ( size > 0 )
105 {
106 LZCompFlags = 0;
107 LZCompFlagsp = dstp++; // Designation for storing flag series
108 LZDstCount++;
109
110 // Since flag series is stored as 8-bit data, loop eight times
111 for ( i = 0; i < 8; i++ )
112 {
113 LZCompFlags <<= 1; // No meaning for the first time (i=0)
114 if (size <= 0)
115 {
116 // When reached the end, quit after shifting flag to the end.
117 continue;
118 }
119
120 if ((lastLength = SearchLZ( &info, srcp, size, &lastOffset)) != 0 )
121 {
122 // Enabled Flag if compression is possible
123 LZCompFlags |= 0x1;
124
125 if (LZDstCount + 2 >= dstMax) // Quit on error if size becomes larger than source
126 {
127 return 0;
128 }
129 // Divide offset into upper 4 bits and lower 8 bits and store
130 *dstp++ = (u8)((lastLength - 3) << 4 | (lastOffset - 1) >> 8);
131 *dstp++ = (u8)((lastOffset - 1) & 0xff);
132 LZDstCount += 2;
133 LZSlide(&info, srcp, lastLength);
134 srcp += lastLength;
135 size -= lastLength;
136 }
137 else
138 {
139 // No compression
140 if (LZDstCount + 1 >= dstMax) // Quit on error if size becomes larger than source
141 {
142 return 0;
143 }
144 LZSlide(&info, srcp, 1);
145 *dstp++ = *srcp++;
146 size--;
147 LZDstCount++;
148 }
149 } // Complete eight loops
150 *LZCompFlagsp = LZCompFlags; // Store flag series
151 }
152
153 // Align to 4-byte boundary
154 // Does not include Data0 used for alignment as data size
155 i = 0;
156 while ( (LZDstCount + i) & 0x3 )
157 {
158 *dstp++ = 0;
159 i++;
160 }
161
162 return LZDstCount;
163 }
164
165 //--------------------------------------------------------
166 // Searches for the longest matching string from the slide window with LZ77 Compression.
167 // Arguments: startp Pointer to starting position of data
168 // nextp Pointer to data where search will start
169 // remainSize Size of remaining data
170 // offset Pointer to region storing matched offset
171 // Return : TRUE if matching string is found.
172 // FALSE if not found.
173 //--------------------------------------------------------
SearchLZ(LZCompressInfo * info,const u8 * nextp,u32 remainSize,u16 * offset)174 static u8 SearchLZ( LZCompressInfo * info, const u8 *nextp, u32 remainSize, u16 *offset )
175 {
176 const u8 *searchp;
177 const u8 *headp, *searchHeadp;
178 u16 maxOffset;
179 u8 maxLength = 2;
180 u8 tmpLength;
181 s32 w_offset;
182 s16 *const LZOffsetTable = info->LZOffsetTable;
183 const u16 windowPos = info->windowPos;
184 const u16 windowLen = info->windowLen;
185
186 if (remainSize < 3)
187 {
188 return 0;
189 }
190
191 w_offset = info->LZByteTable[*nextp];
192
193 while (w_offset != -1)
194 {
195 if (w_offset < windowPos)
196 {
197 searchp = nextp - windowPos + w_offset;
198 }
199 else
200 {
201 searchp = nextp - windowLen - windowPos + w_offset;
202 }
203
204 /* This isn't needed, but it seems to make it a little faster.*/
205 if (*(searchp + 1) != *(nextp + 1) || *(searchp + 2) != *(nextp + 2))
206 {
207 w_offset = LZOffsetTable[w_offset];
208 continue;
209 }
210
211 if (nextp - searchp < 2)
212 {
213 // VRAM is accessed in units of 2 bytes (since sometimes data is read from VRAM),
214 // so the search must start 2 bytes prior to the search target.
215 //
216 // Since the offset is stored in 12 bits, the value is 4096 or less
217 break;
218 }
219 tmpLength = 3;
220 searchHeadp = searchp + 3;
221 headp = nextp + 3;
222
223 // Increments the compression size until the data ends or different data is encountered.
224 while (((u32)(headp - nextp) < remainSize) && (*headp == *searchHeadp))
225 {
226 headp++;
227 searchHeadp++;
228 tmpLength++;
229
230 // Since the data length is stored in 4 bits, the value is 18 or less (3 is added)
231 if (tmpLength == (0xF + 3))
232 {
233 break;
234 }
235 }
236
237 if (tmpLength > maxLength)
238 {
239 // Update the maximum-length offset
240 maxLength = tmpLength;
241 maxOffset = (u16)(nextp - searchp);
242 if (maxLength == (0xF + 3))
243 {
244 // This is the largest matching length, so end search.
245 break;
246 }
247 }
248 w_offset = LZOffsetTable[w_offset];
249 }
250
251 if (maxLength < 3)
252 {
253 return 0;
254 }
255 *offset = maxOffset;
256 return maxLength;
257 }
258
259 //--------------------------------------------------------
260 // Initializes the dictionary index
261 //--------------------------------------------------------
LZInitTable(LZCompressInfo * info,void * work)262 static void LZInitTable(LZCompressInfo * info, void *work)
263 {
264 u16 i;
265
266 info->LZOffsetTable = (s16*)work;
267 info->LZByteTable = (s16*)( (u32)work + 4096 * sizeof(s16) );
268 info->LZEndTable = (s16*)( (u32)work + (4096 + 256) * sizeof(s16) );
269
270 for ( i = 0; i < 256; i++ )
271 {
272 info->LZByteTable[i] = -1;
273 info->LZEndTable [i] = -1;
274 }
275 info->windowPos = 0;
276 info->windowLen = 0;
277 }
278
279 //--------------------------------------------------------
280 // Slides the dictionary 1 byte
281 //--------------------------------------------------------
SlideByte(LZCompressInfo * info,const u8 * srcp)282 static void SlideByte(LZCompressInfo * info, const u8 *srcp)
283 {
284 s16 offset;
285 u8 in_data = *srcp;
286 u16 insert_offset;
287
288 s16 *const LZByteTable = info->LZByteTable;
289 s16 *const LZOffsetTable = info->LZOffsetTable;
290 s16 *const LZEndTable = info->LZEndTable;
291 const u16 windowPos = info->windowPos;
292 const u16 windowLen = info->windowLen;
293
294 if (windowLen == 4096)
295 {
296 u8 out_data = *(srcp - 4096);
297 if ((LZByteTable[out_data] = LZOffsetTable[LZByteTable[out_data]]) == -1)
298 {
299 LZEndTable[out_data] = -1;
300 }
301 insert_offset = windowPos;
302 }
303 else
304 {
305 insert_offset = windowLen;
306 }
307
308 offset = LZEndTable[in_data];
309 if (offset == -1)
310 {
311 LZByteTable[in_data] = (s16)insert_offset;
312 }
313 else
314 {
315 LZOffsetTable[offset] = (s16)insert_offset;
316 }
317 LZEndTable[in_data] = (s16)insert_offset;
318 LZOffsetTable[insert_offset] = -1;
319
320 if (windowLen == 4096)
321 {
322 info->windowPos = (u16)((windowPos + 1) % 0x1000);
323 }
324 else
325 {
326 info->windowLen++;
327 }
328 }
329
330 //--------------------------------------------------------
331 // Slides the dictionary n bytes
332 //--------------------------------------------------------
LZSlide(LZCompressInfo * info,const u8 * srcp,u32 n)333 static inline void LZSlide(LZCompressInfo * info, const u8 *srcp, u32 n)
334 {
335 u32 i;
336
337 for (i = 0; i < n; i++)
338 {
339 SlideByte(info, srcp++);
340 }
341 }
342
343
344 //===========================================================================
345 // Run Length Encoding
346 //===========================================================================
347
348 /*---------------------------------------------------------------------------*
349 Name: CXCompressRL
350
351 Description: Function that performs runlength compression
352
353 Arguments: srcp Pointer to compression source data
354 size Size of compression source data
355 dstp Pointer to destination for compressed data
356 Buffer must be larger than size of compression source data.
357
358 Returns: The data size after compression.
359 If compressed data is larger than original data, compression is terminated and 0 gets returned.
360 *---------------------------------------------------------------------------*/
CXCompressRL(const u8 * srcp,u32 size,u8 * dstp)361 u32 CXCompressRL(const u8 *srcp, u32 size, u8 *dstp)
362 {
363 u32 RLDstCount; // Number of bytes of compressed data
364 u32 RLSrcCount; // Processed data volume of the compression target data (in bytes)
365 u8 RLCompFlag; // 1 if performing run length encoding
366 u8 runLength; // Run length
367 u8 rawDataLength; // Length of data not run
368 u32 i;
369
370 const u8 *startp; // Point to the start of compression target data for each process loop
371
372 ASSERT( srcp != NULL );
373 ASSERT( dstp != NULL );
374 ASSERT( size > 4 );
375
376 // Data header (The size after decompression)
377 // Because the same output data as for Nitro is created, an endian strategy is implemented.
378 *(u32 *)dstp = CXiConvertEndian_(size << 8 | CX_COMPRESSION_RL); // data header
379 RLDstCount = 4;
380
381 RLSrcCount = 0;
382 rawDataLength = 0;
383 RLCompFlag = 0;
384
385 while (RLSrcCount < size)
386 {
387 startp = &srcp[RLSrcCount]; // Set compression target data
388
389 for (i = 0; i < 128; i++) // Data volume that can be expressed in 7 bits is 0 to 127
390 {
391 // Reach the end of the compression target data
392 if (RLSrcCount + rawDataLength >= size)
393 {
394 rawDataLength = (u8)(size - RLSrcCount);
395 break;
396 }
397
398 if (RLSrcCount + rawDataLength + 2 < size)
399 {
400 if (startp[i] == startp[i + 1] && startp[i] == startp[i + 2])
401 {
402 RLCompFlag = 1;
403 break;
404 }
405 }
406 rawDataLength++;
407 }
408
409 // Store data that is not encoded
410 // If the 8th bit of the data length storage byte is 0, the data series that is not encoded.
411 // The data length is x - 1, so 0-127 becomes 1-128.
412 if (rawDataLength)
413 {
414 if (RLDstCount + rawDataLength + 1 >= size) // Quit on error if size becomes larger than source
415 {
416 return 0;
417 }
418 dstp[RLDstCount++] = (u8)(rawDataLength - 1); // Store "data length - 1" (7 bits)
419 for (i = 0; i < rawDataLength; i++)
420 {
421 dstp[RLDstCount++] = srcp[RLSrcCount++];
422 }
423 rawDataLength = 0;
424 }
425
426 // Run Length Encoding
427 if (RLCompFlag)
428 {
429 runLength = 3;
430 for (i = 3; i < 128 + 2; i++)
431 {
432 // Reach the end of the data for compression
433 if (RLSrcCount + runLength >= size)
434 {
435 runLength = (u8)(size - RLSrcCount);
436 break;
437 }
438
439 // If run is interrupted
440 if (srcp[RLSrcCount] != srcp[RLSrcCount + runLength])
441 {
442 break;
443 }
444 // Run continues
445 runLength++;
446 }
447
448 // If the 8th bit of the data length storage byte is 1, the data series that is encoded.
449 if (RLDstCount + 2 >= size) // Quit on error if size becomes larger than source
450 {
451 return 0;
452 }
453 dstp[RLDstCount++] = (u8)(0x80 | (runLength - 3)); // Add 3, and store 3 to 130
454 dstp[RLDstCount++] = srcp[RLSrcCount];
455 RLSrcCount += runLength;
456 RLCompFlag = 0;
457 }
458 }
459
460 // Align to 4-byte boundary
461 // Does not include Data0 used for alignment as data size
462 i = 0;
463 while ((RLDstCount + i) & 0x3)
464 {
465 dstp[RLDstCount + i] = 0;
466 i++;
467 }
468 return RLDstCount;
469 }
470
471
472 //===========================================================================
473 // Huffman encoding
474 //===========================================================================
475 #define HUFF_END_L 0x80
476 #define HUFF_END_R 0x40
477
478 typedef struct
479 {
480 u32 Freq; // Frequency of occurrence
481 u16 No; // Data No.
482 s16 PaNo; // Parent No.
483 s16 ChNo[2]; // Child No (0: left side, 1: right side)
484 u16 PaDepth; // Parent node depth
485 u16 LeafDepth; // Depth to leaf
486 u32 HuffCode; // Huffman code
487 u8 Bit; // Node's bit data
488 u8 _padding;
489 u16 HWord; // For each intermediate node, the amount of memory needed to store the subtree that has the node as its root in HuffTree
490 }
491 HuffData; // Total of 24 bytes
492
493 typedef struct
494 {
495 u8 leftOffsetNeed; // 1 if offset to left child node is required
496 u8 rightOffsetNeed; // 1 if offset to right child node is required
497 u16 leftNodeNo; // The left child node No.
498 u16 rightNodeNo; // Right child node no.
499 }
500 HuffTreeCtrlData; // Total of 6 bytes
501
502 // Structure of the Huffman work buffer
503 typedef struct
504 {
505 HuffData *huffTable; // huffTable[ 512 ]; 12288B
506 u8 *huffTree; // huffTree[ 256 * 2 ]; 512B
507 HuffTreeCtrlData *huffTreeCtrl; // huffTreeCtrl[ 256 ]; 1536B
508 u8 huffTreeTop; //
509 u8 padding_[3]; //
510 }
511 HuffCompressionInfo; // Total is 14340B
512
513 static void HuffInitTable( HuffCompressionInfo* info, void* work, u16 dataNum );
514 static void HuffCountData( HuffData* table, const u8 *srcp, u32 size, u8 bitSize );
515 static u16 HuffConstructTree( HuffData* table, u32 dataNum );
516 static u32 HuffConvertData( const HuffData *table, const u8* srcp, u8* dstp, u32 srcSize, u32 maxSize, u8 bitSize );
517
518 static void HuffAddParentDepthToTable( HuffData *table, u16 leftNo, u16 rightNo );
519 static void HuffAddCodeToTable ( HuffData *table, u16 nodeNo, u32 paHuffCode );
520 static u8 HuffAddCountHWordToTable ( HuffData *table, u16 nodeNo );
521
522 static void HuffMakeHuffTree ( HuffCompressionInfo* info, u16 rootNo );
523 static void HuffMakeSubsetHuffTree ( HuffCompressionInfo* info, u16 huffTreeNo, u8 rightNodeFlag );
524 static u8 HuffRemainingNodeCanSetOffset( HuffCompressionInfo* info, u8 costHWord );
525 static void HuffSetOneNodeOffset ( HuffCompressionInfo* info, u16 huffTreeNo, u8 rightNodeFlag );
526
527
528 /*---------------------------------------------------------------------------*
529 Name: CXCompressHuffman
530
531 Description: Function that performs Huffman compression
532
533 Arguments: srcp Pointer to compression source data
534 size Size of compression source data
535 dstp Pointer to destination for compressed data
536 Buffer must be larger than size of compression source data.
537 huffBitSize The number of bits to encode
538 work Work buffer for Huffman compression
539
540 Returns: The data size after compression.
541 If compressed data is larger than original data, compression is terminated and 0 gets returned.
542 *---------------------------------------------------------------------------*/
CXCompressHuffman(const u8 * srcp,u32 size,u8 * dstp,u8 huffBitSize,void * work)543 u32 CXCompressHuffman( const u8 *srcp, u32 size, u8 *dstp, u8 huffBitSize, void *work )
544 {
545 u32 huffDstCount; // Number of bytes of compressed data
546 s32 i;
547 u16 rootNo; // Binary tree's root No.
548 u16 huffDataNum = (u16)(1 << huffBitSize); // 8->256, 4->16
549 HuffCompressionInfo info;
550
551 ASSERT( srcp != NULL );
552 ASSERT( dstp != NULL );
553 ASSERT( huffBitSize == 4 || huffBitSize == 8 );
554 ASSERT( work != NULL );
555 ASSERT( ((u32)work & 0x3) == 0 );
556 ASSERT( size > 4 );
557
558 // Initialize table
559 HuffInitTable( &info, work, huffDataNum );
560
561 // Check frequency of occurrence
562 HuffCountData( info.huffTable, srcp, size, huffBitSize );
563
564 // Create tree table
565 rootNo = HuffConstructTree( info.huffTable, huffDataNum );
566
567 // Create HuffTree
568 HuffMakeHuffTree( &info, rootNo );
569 info.huffTree[0] = --info.huffTreeTop;
570
571 // data header
572 // Because the same compression data as for Nitro is created, an endian strategy is implemented.
573 *(u32 *)dstp = CXiConvertEndian_(size << 8 | CX_COMPRESSION_HUFFMAN | huffBitSize);
574 huffDstCount = 4;
575
576 if ( huffDstCount + (info.huffTreeTop + 1) * 2 >= size ) // Quit on error if size becomes larger than source
577 {
578 return 0;
579 }
580
581 for ( i = 0; i < (u16)( (info.huffTreeTop + 1) * 2 ); i++ ) // Tree table
582 {
583 dstp[ huffDstCount++ ] = ((u8*)info.huffTree)[ i ];
584 }
585
586 // Align to 4-byte boundary
587 // Data0 used for alignment is included in data size (as per the decoder algorithm)
588 while ( huffDstCount & 0x3 )
589 {
590 if ( huffDstCount & 0x1 )
591 {
592 info.huffTreeTop++;
593 dstp[ 4 ]++;
594 }
595 dstp[ huffDstCount++ ] = 0;
596 }
597
598 // data conversion via the Huffman table
599 {
600 u32 convSize = HuffConvertData( info.huffTable, srcp, &dstp[ huffDstCount ], size, size - huffDstCount, huffBitSize );
601 if ( convSize == 0 )
602 {
603 // compression fails because the compressed data is larger than the source
604 return 0;
605 }
606 huffDstCount += convSize;
607 }
608
609 return huffDstCount;
610 }
611
612
613 /*---------------------------------------------------------------------------*
614 Name: HuffInitTable
615 Description: Initializes the Huffman table.
616 Arguments: table
617 size
618 Returns: None.
619 *---------------------------------------------------------------------------*/
HuffInitTable(HuffCompressionInfo * info,void * work,u16 dataNum)620 static void HuffInitTable( HuffCompressionInfo* info, void* work, u16 dataNum )
621 {
622 u32 i;
623 info->huffTable = (HuffData*)(work);
624 info->huffTree = (u8*)( (u32)work + sizeof(HuffData) * 512 );
625 info->huffTreeCtrl = (HuffTreeCtrlData*)( (u32)info->huffTree + sizeof(u8) * 512 );
626 info->huffTreeTop = 1;
627
628 // initialize huffTable
629 {
630 HuffData* table = info->huffTable;
631
632 const HuffData HUFF_TABLE_INIT_DATA = { 0, 0, 0, {-1, -1}, 0, 0, 0, 0, 0 };
633 for ( i = 0; i < dataNum * 2U; i++ )
634 {
635 table[ i ] = HUFF_TABLE_INIT_DATA;
636 table[ i ].No = (u16)i;
637 }
638 }
639
640 // initialize huffTree and huffTreeCtrl
641 {
642 const HuffTreeCtrlData HUFF_TREE_CTRL_INIT_DATA = { 1, 1, 0, 0 };
643 u8* huffTree = info->huffTree;
644 HuffTreeCtrlData* huffTreeCtrl = info->huffTreeCtrl;
645
646 for ( i = 0; i < 256; i++ )
647 {
648 huffTree[ i * 2 ] = 0;
649 huffTree[ i * 2 + 1 ] = 0;
650 huffTreeCtrl[ i ] = HUFF_TREE_CTRL_INIT_DATA;
651 }
652 }
653 }
654
655
656 /*---------------------------------------------------------------------------*
657 Name: HuffCountData
658 Description: Count of appearances.
659 Arguments: table
660 *srcp
661 size
662 bitSize
663 Returns: None.
664 *---------------------------------------------------------------------------*/
HuffCountData(HuffData * table,const u8 * srcp,u32 size,u8 bitSize)665 static void HuffCountData( HuffData* table, const u8 *srcp, u32 size, u8 bitSize )
666 {
667 u32 i;
668 u8 tmp;
669
670 if ( bitSize == 8 )
671 {
672 for ( i = 0; i < size; i++ )
673 {
674 table[ srcp[ i ] ].Freq++; // 8-bit encoding
675 }
676 }
677 else
678 {
679 for ( i = 0; i < size; i++ ) // 4-bit encoding
680 {
681 tmp = (u8)( (srcp[ i ] & 0xf0) >> 4 );
682 table[ tmp ].Freq++; // Store from upper 4 bits forward // Either is OK
683 tmp = (u8)( srcp[ i ] & 0x0f );
684 table[ tmp ].Freq++; // The problem is the encoding
685 }
686 }
687 }
688
689
690 /*---------------------------------------------------------------------------*
691 Name: HuffConstructTree
692 Description: Constructs a Huffman tree.
693 Arguments: *table
694 dataNum
695 Returns: None.
696 *---------------------------------------------------------------------------*/
HuffConstructTree(HuffData * table,u32 dataNum)697 static u16 HuffConstructTree( HuffData *table, u32 dataNum )
698 {
699 s32 i;
700 s32 leftNo, rightNo; // Node number for creating binary tree
701 u16 tableTop = (u16)dataNum; // When creating table, the table top No.
702 u16 rootNo; // Binary tree's root No.
703 u16 nodeNum; // Number of valid nodes
704
705 leftNo = -1;
706 rightNo = -1;
707 while ( 1 )
708 {
709 // Search for two subtree nodes with low Freq value. At least one should be found.
710 // Search child node (left)
711 for ( i = 0; i < tableTop; i++ )
712 {
713 if ( ( table[i].Freq == 0 ) ||
714 ( table[i].PaNo != 0 ) )
715 {
716 continue;
717 }
718
719 if ( leftNo < 0 )
720 {
721 leftNo = i;
722 }
723 else if ( table[i].Freq < table[ leftNo ].Freq )
724 {
725 leftNo = i;
726 }
727 }
728
729 // Search child node (right)
730 for ( i = 0; i < tableTop; i++ )
731 {
732 if ( ( table[i].Freq == 0 ) ||
733 ( table[i].PaNo != 0 ) ||
734 ( i == leftNo ) )
735 {
736 continue;
737 }
738
739 if ( rightNo < 0 )
740 {
741 rightNo = i;
742 }
743 else if ( table[i].Freq < table[rightNo].Freq )
744 {
745 rightNo = i;
746 }
747 }
748
749 // If only one, then end table creation
750 if ( rightNo < 0 )
751 {
752 // When only one type of value exists, then create one node that takes the same value for both 0 and 1.
753 if ( tableTop == dataNum )
754 {
755 table[ tableTop ].Freq = table[ leftNo ].Freq;
756 table[ tableTop ].ChNo[0] = (s16)leftNo;
757 table[ tableTop ].ChNo[1] = (s16)leftNo;
758 table[ tableTop ].LeafDepth = 1;
759 table[ leftNo ].PaNo = (s16)tableTop;
760 table[ leftNo ].Bit = 0;
761 table[ leftNo ].PaDepth = 1;
762 }
763 else
764 {
765 tableTop--;
766 }
767 rootNo = tableTop;
768 nodeNum = (u16)( (rootNo - dataNum + 1) * 2 + 1 );
769 break;
770 }
771
772 // Create vertex that combines left subtree and right subtree
773 table[ tableTop ].Freq = table[ leftNo ].Freq + table[ rightNo ].Freq;
774 table[ tableTop ].ChNo[0] = (s16)leftNo;
775 table[ tableTop ].ChNo[1] = (s16)rightNo;
776 if ( table[ leftNo ].LeafDepth > table[ rightNo ].LeafDepth )
777 {
778 table[ tableTop ].LeafDepth = (u16)( table[ leftNo ].LeafDepth + 1 );
779 }
780 else
781 {
782 table[ tableTop ].LeafDepth = (u16)( table[ rightNo ].LeafDepth + 1 );
783 }
784
785 table[ leftNo ].PaNo = table[ rightNo ].PaNo = (s16)(tableTop);
786 table[ leftNo ].Bit = 0;
787 table[ rightNo ].Bit = 1;
788
789 HuffAddParentDepthToTable( table, (u16)leftNo, (u16)rightNo );
790
791 tableTop++;
792 leftNo = rightNo = -1;
793 }
794
795 // Generate Huffman code (In Table[i].HuffCode)
796 HuffAddCodeToTable( table, rootNo, 0x00 ); // The Huffman code is the code with HuffCode's lower bit masked for PaDepth bits
797
798 // For each intermediate node, calculate the amount of memory needed to store the subtree that has this node as the root in HuffTree.
799 HuffAddCountHWordToTable( table, rootNo );
800
801 return rootNo;
802 }
803
804 //-----------------------------------------------------------------------
805 // When creating binary tree and when combining subtrees, add 1 to the depth of every node in the subtree.
806 //-----------------------------------------------------------------------
HuffAddParentDepthToTable(HuffData * table,u16 leftNo,u16 rightNo)807 static void HuffAddParentDepthToTable( HuffData *table, u16 leftNo, u16 rightNo )
808 {
809 table[ leftNo ].PaDepth++;
810 table[ rightNo ].PaDepth++;
811
812 if ( table[ leftNo ].LeafDepth != 0 )
813 {
814 HuffAddParentDepthToTable( table, (u16)table[ leftNo ].ChNo[0], (u16)table[ leftNo ].ChNo[1] );
815 }
816 if ( table[ rightNo ].LeafDepth != 0 )
817 {
818 HuffAddParentDepthToTable( table, (u16)table[ rightNo ].ChNo[0], (u16)table[ rightNo ].ChNo[1] );
819 }
820 }
821
822 //-----------------------------------------------------------------------
823 // Create Huffman code
824 //-----------------------------------------------------------------------
HuffAddCodeToTable(HuffData * table,u16 nodeNo,u32 paHuffCode)825 static void HuffAddCodeToTable( HuffData* table, u16 nodeNo, u32 paHuffCode )
826 {
827 table[ nodeNo ].HuffCode = (paHuffCode << 1) | table[ nodeNo ].Bit;
828
829 if ( table[ nodeNo ].LeafDepth != 0 )
830 {
831 HuffAddCodeToTable( table, (u16)table[ nodeNo ].ChNo[0], (u16)table[ nodeNo ].HuffCode );
832 HuffAddCodeToTable( table, (u16)table[ nodeNo ].ChNo[1], (u16)table[ nodeNo ].HuffCode );
833 }
834 }
835
836
837 //-----------------------------------------------------------------------
838 // Data volume required of intermediate node to create HuffTree
839 //-----------------------------------------------------------------------
HuffAddCountHWordToTable(HuffData * table,u16 nodeNo)840 static u8 HuffAddCountHWordToTable( HuffData *table, u16 nodeNo)
841 {
842 u8 leftHWord, rightHWord;
843
844 switch ( table[ nodeNo ].LeafDepth )
845 {
846 case 0:
847 return 0;
848 case 1:
849 leftHWord = rightHWord = 0;
850 break;
851 default:
852 leftHWord = HuffAddCountHWordToTable( table, (u16)table[nodeNo].ChNo[0] );
853 rightHWord = HuffAddCountHWordToTable( table, (u16)table[nodeNo].ChNo[1] );
854 break;
855 }
856
857 table[ nodeNo ].HWord = (u16)( leftHWord + rightHWord + 1 );
858 return (u8)( leftHWord + rightHWord + 1 );
859 }
860
861
862 //-----------------------------------------------------------------------
863 // Creating table of Huffman Code
864 //-----------------------------------------------------------------------
HuffMakeHuffTree(HuffCompressionInfo * info,u16 rootNo)865 static void HuffMakeHuffTree( HuffCompressionInfo* info, u16 rootNo )
866 {
867 s16 i;
868 s16 costHWord, tmpCostHWord; // Make subtree code table for most-costly node when subtree code table has not been created.
869 s16 costOffsetNeed, tmpCostOffsetNeed;
870 s16 costMaxKey, costMaxRightFlag; // Information for specifying the least costly node from HuffTree
871 u8 offsetNeedNum;
872 u8 tmpKey, tmpRightFlag;
873
874 info->huffTreeTop = 1;
875 costOffsetNeed = 0;
876
877 info->huffTreeCtrl[0].leftOffsetNeed = 0; // Do not use (used as table size)
878 info->huffTreeCtrl[0].rightNodeNo = rootNo;
879
880 while ( 1 ) // Until return
881 {
882 // Calculate the number of nodes required for setting offset
883 offsetNeedNum = 0;
884 for ( i = 0; i < info->huffTreeTop; i++ )
885 {
886 if ( info->huffTreeCtrl[ i ].leftOffsetNeed )
887 {
888 offsetNeedNum++;
889 }
890 if ( info->huffTreeCtrl[ i ].rightOffsetNeed )
891 {
892 offsetNeedNum++;
893 }
894 }
895
896 // Search for node with greatest cost
897 costHWord = -1;
898 costMaxKey = -1;
899 tmpKey = 0;
900 tmpRightFlag = 0;
901
902 for ( i = 0; i < info->huffTreeTop; i++ )
903 {
904 tmpCostOffsetNeed = (u8)( info->huffTreeTop - i );
905
906 // Evaluate cost of left child node
907 if (info->huffTreeCtrl[i].leftOffsetNeed)
908 {
909 tmpCostHWord = (s16)info->huffTable[ info->huffTreeCtrl[i].leftNodeNo ].HWord;
910
911 if ( (tmpCostHWord + offsetNeedNum) > 64 )
912 {
913 goto leftCostEvaluationEnd;
914 }
915 if ( ! HuffRemainingNodeCanSetOffset( info, (u8)tmpCostHWord ) )
916 {
917 goto leftCostEvaluationEnd;
918 }
919 if ( tmpCostHWord > costHWord )
920 {
921 costMaxKey = i;
922 costMaxRightFlag = 0;
923 }
924 else if ( (tmpCostHWord == costHWord) && (tmpCostOffsetNeed > costOffsetNeed) )
925 {
926 costMaxKey = i;
927 costMaxRightFlag = 0;
928 }
929 }
930 leftCostEvaluationEnd:{}
931
932 // Evaluate cost of right child node
933 if ( info->huffTreeCtrl[i].rightOffsetNeed)
934 {
935 tmpCostHWord = (s16)info->huffTable[info->huffTreeCtrl[i].rightNodeNo].HWord;
936
937 if ( (tmpCostHWord + offsetNeedNum) > 64 )
938 {
939 goto rightCostEvaluationEnd;
940 }
941 if ( ! HuffRemainingNodeCanSetOffset( info, (u8)tmpCostHWord ) )
942 {
943 goto rightCostEvaluationEnd;
944 }
945 if ( tmpCostHWord > costHWord )
946 {
947 costMaxKey = i;
948 costMaxRightFlag = 1;
949 }
950 else if ( (tmpCostHWord == costHWord) && (tmpCostOffsetNeed > costOffsetNeed) )
951 {
952 costMaxKey = i;
953 costMaxRightFlag = 1;
954 }
955 }
956 rightCostEvaluationEnd:{}
957 }
958
959 // Store entire subtree in HuffTree
960 if ( costMaxKey >= 0 )
961 {
962 HuffMakeSubsetHuffTree( info, (u8)costMaxKey, (u8)costMaxRightFlag);
963 goto nextTreeMaking;
964 }
965 else
966 {
967 // Search for largest node with required offset
968 for ( i = 0; i < info->huffTreeTop; i++ )
969 {
970 u16 tmp = 0;
971 tmpRightFlag = 0;
972 if (info->huffTreeCtrl[i].leftOffsetNeed)
973 {
974 tmp = info->huffTable[ info->huffTreeCtrl[i].leftNodeNo ].HWord;
975 }
976 if (info->huffTreeCtrl[i].rightOffsetNeed)
977 {
978 if ( info->huffTable[info->huffTreeCtrl[i].rightNodeNo ].HWord > tmp )
979 {
980 tmpRightFlag = 1;
981 }
982 }
983 if ( (tmp != 0) || (tmpRightFlag) )
984 {
985 HuffSetOneNodeOffset( info, (u8)i, tmpRightFlag);
986 goto nextTreeMaking;
987 }
988 }
989 }
990 return;
991 nextTreeMaking:{}
992 }
993 }
994
995 //-----------------------------------------------------------------------
996 // Store entire subtree in HuffTree
997 //-----------------------------------------------------------------------
HuffMakeSubsetHuffTree(HuffCompressionInfo * info,u16 huffTreeNo,u8 rightNodeFlag)998 static void HuffMakeSubsetHuffTree( HuffCompressionInfo* info, u16 huffTreeNo, u8 rightNodeFlag )
999 {
1000 u8 i;
1001
1002 i = info->huffTreeTop;
1003 HuffSetOneNodeOffset( info, huffTreeNo, rightNodeFlag);
1004
1005 if ( rightNodeFlag )
1006 {
1007 info->huffTreeCtrl[ huffTreeNo ].rightOffsetNeed = 0;
1008 }
1009 else
1010 {
1011 info->huffTreeCtrl[ huffTreeNo ].leftOffsetNeed = 0;
1012 }
1013
1014 while ( i < info->huffTreeTop )
1015 {
1016 if ( info->huffTreeCtrl[ i ].leftOffsetNeed )
1017 {
1018 HuffSetOneNodeOffset( info, i, 0);
1019 info->huffTreeCtrl[ i ].leftOffsetNeed = 0;
1020 }
1021 if ( info->huffTreeCtrl[ i ].rightOffsetNeed )
1022 {
1023 HuffSetOneNodeOffset( info, i, 1);
1024 info->huffTreeCtrl[ i ].rightOffsetNeed = 0;
1025 }
1026 i++;
1027 }
1028 }
1029
1030 //-----------------------------------------------------------------------
1031 // Check if there is any problems with huffTree construction if subtree of obtained data size is decompressed.
1032 //-----------------------------------------------------------------------
HuffRemainingNodeCanSetOffset(HuffCompressionInfo * info,u8 costHWord)1033 static u8 HuffRemainingNodeCanSetOffset( HuffCompressionInfo* info, u8 costHWord )
1034 {
1035 u8 i;
1036 s16 capacity;
1037
1038 capacity = (s16)( 64 - costHWord );
1039
1040 // The offset value is larger for smaller values of i, so you should calculate without sorting, with i=0 -> huffTreeTop
1041 for ( i = 0; i < info->huffTreeTop; i++ )
1042 {
1043 if ( info->huffTreeCtrl[i].leftOffsetNeed )
1044 {
1045 if ( (info->huffTreeTop - i) <= capacity )
1046 {
1047 capacity--;
1048 }
1049 else
1050 {
1051 return 0;
1052 }
1053 }
1054 if ( info->huffTreeCtrl[i].rightOffsetNeed )
1055 {
1056 if ( (info->huffTreeTop - i) <= capacity )
1057 {
1058 capacity--;
1059 }
1060 else
1061 {
1062 return 0;
1063 }
1064 }
1065 }
1066
1067 return 1;
1068 }
1069
1070 /*---------------------------------------------------------------------------*
1071 Name: HuffSetOneNodeOffset
1072 Description: Create Huffman code table for one node
1073 Arguments: *info a pointer to data for constructing a Huffman tree
1074 huffTreeNo
1075 rightNodeFlag flag for whether node is at right
1076 Returns: None.
1077 *---------------------------------------------------------------------------*/
HuffSetOneNodeOffset(HuffCompressionInfo * info,u16 huffTreeNo,u8 rightNodeFlag)1078 static void HuffSetOneNodeOffset( HuffCompressionInfo* info, u16 huffTreeNo, u8 rightNodeFlag )
1079 {
1080 u16 nodeNo;
1081 u8 offsetData = 0;
1082
1083 HuffData* huffTable = info->huffTable;
1084 u8* huffTree = info->huffTree;
1085 HuffTreeCtrlData* huffTreeCtrl = info->huffTreeCtrl;
1086 u8 huffTreeTop = info->huffTreeTop;
1087
1088 if (rightNodeFlag)
1089 {
1090 nodeNo = huffTreeCtrl[ huffTreeNo ].rightNodeNo;
1091 huffTreeCtrl[ huffTreeNo ].rightOffsetNeed = 0;
1092 }
1093 else
1094 {
1095 nodeNo = huffTreeCtrl[ huffTreeNo ].leftNodeNo;
1096 huffTreeCtrl [huffTreeNo ].leftOffsetNeed = 0;
1097 }
1098
1099 // Left child node
1100 if ( huffTable[ huffTable[nodeNo].ChNo[0] ].LeafDepth == 0)
1101 {
1102 offsetData |= 0x80;
1103 huffTree[ huffTreeTop * 2 + 0 ] = (u8)huffTable[ nodeNo ].ChNo[0];
1104 huffTreeCtrl[ huffTreeTop ].leftNodeNo = (u8)huffTable[ nodeNo ].ChNo[0];
1105 huffTreeCtrl[ huffTreeTop ].leftOffsetNeed = 0; // Offset no longer required
1106 }
1107 else
1108 {
1109 huffTreeCtrl[ huffTreeTop ].leftNodeNo = (u16)huffTable[ nodeNo ].ChNo[0]; // Offset required
1110 }
1111
1112 // Right child node
1113 if ( huffTable[ huffTable[ nodeNo ].ChNo[1] ].LeafDepth == 0 )
1114 {
1115 offsetData |= 0x40;
1116 huffTree[ huffTreeTop * 2 + 1 ] = (u8)huffTable[nodeNo].ChNo[1];
1117 huffTreeCtrl[ huffTreeTop ].rightNodeNo = (u8)huffTable[ nodeNo ].ChNo[1];
1118 huffTreeCtrl[ huffTreeTop ].rightOffsetNeed = 0; // Offset no longer required
1119 }
1120 else
1121 {
1122 huffTreeCtrl[ huffTreeTop ].rightNodeNo = (u16)huffTable[ nodeNo ].ChNo[1]; // Offset required
1123 }
1124
1125 offsetData |= (u8)( huffTreeTop - huffTreeNo - 1 );
1126 huffTree[ huffTreeNo * 2 + rightNodeFlag ] = offsetData;
1127
1128 info->huffTreeTop++;
1129 }
1130
1131
1132 /*---------------------------------------------------------------------------*
1133 Name: HuffConvertData
1134 Description: Data conversion based on Huffman table.
1135 Arguments: *table
1136 srcp
1137 dstp
1138 srcSize
1139 bitSize
1140 Returns: None.
1141 *---------------------------------------------------------------------------*/
HuffConvertData(const HuffData * table,const u8 * srcp,u8 * dstp,u32 srcSize,u32 maxSize,u8 bitSize)1142 static u32 HuffConvertData( const HuffData *table, const u8* srcp, u8* dstp, u32 srcSize, u32 maxSize, u8 bitSize )
1143 {
1144 u32 i, ii, iii;
1145 u8 srcTmp;
1146 u32 bitStream = 0;
1147 u32 streamLength = 0;
1148 u32 dstSize = 0;
1149
1150 // Huffman encoding
1151 for ( i = 0; i < srcSize; i++ )
1152 { // Data compression
1153 if ( bitSize == 8 )
1154 { // 8-bit Huffman
1155 bitStream = (bitStream << table[ srcp[i] ].PaDepth) | table[ srcp[i] ].HuffCode;
1156 streamLength += table[ srcp[i] ].PaDepth;
1157
1158 if ( dstSize + (streamLength / 8) >= maxSize )
1159 {
1160 // error if size becomes larger than source
1161 return 0;
1162 }
1163
1164 for ( ii = 0; ii < streamLength / 8; ii++ )
1165 {
1166 dstp[ dstSize++ ] = (u8)(bitStream >> (streamLength - (ii + 1) * 8));
1167 }
1168 streamLength %= 8;
1169 }
1170 else // 4-bit Huffman
1171 {
1172 for ( ii = 0; ii < 2; ii++ )
1173 {
1174 if ( ii )
1175 {
1176 srcTmp = (u8)( srcp[ i ] >> 4 ); // first four bits come later
1177 }
1178 else
1179 {
1180 srcTmp = (u8)( srcp[ i ] & 0x0F ); // last four bits come first (because the decoder accesses in a little-endian method)
1181 }
1182 bitStream = (bitStream << table[ srcTmp ].PaDepth) | table[ srcTmp ].HuffCode;
1183 streamLength += table[ srcTmp ].PaDepth;
1184 if ( dstSize + (streamLength / 8) >= maxSize )
1185 {
1186 // error if size becomes larger than source
1187 return 0;
1188 }
1189 for ( iii = 0; iii < streamLength / 8; iii++ )
1190 {
1191 dstp[ dstSize++ ] = (u8)(bitStream >> (streamLength - (iii + 1) * 8));
1192 }
1193 streamLength %= 8;
1194 }
1195 }
1196 }
1197
1198 if ( streamLength != 0 )
1199 {
1200 if ( dstSize + 1 >= maxSize )
1201 {
1202 // error if size becomes larger than source
1203 return 0;
1204 }
1205 dstp[ dstSize++ ] = (u8)( bitStream << (8 - streamLength) );
1206 }
1207
1208 // Align to 4-byte boundary
1209 // Data0 for alignment is included in data size
1210 // This is special to Huffman encoding! Data is stored after the alignment-boundary data in order to convert to little-endian.
1211 while ( dstSize & 0x3 )
1212 {
1213 dstp[ dstSize++ ] = 0;
1214 }
1215
1216 // Little endian conversion
1217 for ( i = 0; i < dstSize / 4; i++ )
1218 {
1219 u8 tmp;
1220 tmp = dstp[i * 4 + 0];
1221 dstp[i * 4 + 0] = dstp[i * 4 + 3];
1222 dstp[i * 4 + 3] = tmp; // Swap
1223 tmp = dstp[i * 4 + 1];
1224 dstp[i * 4 + 1] = dstp[i * 4 + 2];
1225 dstp[i * 4 + 2] = tmp; // Swap
1226 }
1227 return dstSize;
1228 }
1229
1230