← Back to branch summary

~jeanfrancois.roy/mpqkit/1.0b2

« back to all changes in this revision

Viewing changes to stormlib2/huffman/huff.cpp

  • Committer: bahamut
  • Date: 2007-10-04 12:33:42 UTC
  • Revision ID: svn-v4:08a27de9-96f8-0310-9aec-cd9f9b5b01a8:tags/1.0b2:206
Tags: 1.0b2
- Tag that could not be restored.

Show diffs side-by-side

added added

removed removed

Lines of Context:
stormlib2/huffman/huff.cpp
 
1
/*****************************************************************************/
 
2
/* huffman.cpp                       Copyright (c) Ladislav Zezula 1998-2003 */
 
3
/*---------------------------------------------------------------------------*/
 
4
/* This module contains Huffman (de)compression methods                     */
 
5
/*                                                                           */
 
6
/* Authors : Ladislav Zezula (ladik.zezula.net)                              */
 
7
/*           ShadowFlare     (BlakFlare@hotmail.com)                         */
 
8
/*                                                                           */
 
9
/*---------------------------------------------------------------------------*/
 
10
/*   Date    Ver   Who  Comment                                              */
 
11
/* --------  ----  ---  -------                                              */
 
12
/* xx.xx.xx  1.00  Lad  The first version of dcmp.cpp                        */
 
13
/* 03.05.03  1.00  Lad  Added compression methods                            */
 
14
/* 19.11.03  1.01  Dan  Big endian handling                                  */
 
15
/* 08.12.03  2.01  Dan  High-memory handling (> 0x80000000)                  */
 
16
/*****************************************************************************/
 
17
 
 
18
#include <assert.h>
 
19
#include <string.h>
 
20
#include <CoreFoundation/CFByteOrder.h>
 
21
 
 
22
#include "huff.h"
 
23
 
 
24
#define PTR_NOT(ptr)                (THTreeItem *)(~(uintptr_t)(ptr))
 
25
#define PTR_PTR(ptr)                ((THTreeItem *)(ptr))
 
26
#define PTR_INT(ptr)                (intptr_t)(ptr)
 
27
#define PTR_VALID(ptr)              (((intptr_t)(ptr) * addr_multiplier) > 0)
 
28
#define PTR_INVALID(ptr)            (((intptr_t)(ptr) * addr_multiplier) < 0)
 
29
#define PTR_INVALID_OR_NULL(ptr)    (((intptr_t)(ptr) * addr_multiplier) < 0)
 
30
 
 
31
#define INSERT_ITEM 1                   
 
32
#define SWITCH_ITEMS 2 // Switch the item1 and item2
 
33
 
 
34
//-----------------------------------------------------------------------------
 
35
// Methods of the THTreeItem struct
 
36
 
 
37
// 1501DB70
 
38
THTreeItem * THTreeItem::Call1501DB70(THTreeItem * pLast)
 
39
{
 
40
    if(pLast == 0)
 
41
        pLast = this + 1;
 
42
    return pLast;
 
43
}
 
44
 
 
45
// Gets previous Huffman tree item (?)
 
46
THTreeItem * THTreeItem::GetPrevItem(intptr_t value)
 
47
{
 
48
    if(PTR_INVALID(prev))
 
49
        return PTR_NOT(prev);
 
50
    
 
51
    if(value == -1 || PTR_INVALID(value))
 
52
        value = (intptr_t)(this - next->prev);
 
53
    return prev + value;
 
54
}
 
55
 
 
56
// 1500F5E0
 
57
void THTreeItem::ClearItemLinks()
 
58
{
 
59
    next = prev = 0;
 
60
}
 
61
 
 
62
// 1500BC90
 
63
void THTreeItem::RemoveItem()
 
64
{
 
65
    THTreeItem * pTemp;                // EDX
 
66
 
 
67
    if(next != 0)
 
68
    {
 
69
        pTemp = prev;
 
70
       
 
71
        if(PTR_INVALID_OR_NULL(pTemp))
 
72
            pTemp = PTR_NOT(pTemp);
 
73
        else
 
74
            pTemp += (this - next->prev);
 
75
 
 
76
        pTemp->next = next;
 
77
        next->prev  = prev;
 
78
        next = prev = 0;
 
79
    }
 
80
}
 
81
 
 
82
//-----------------------------------------------------------------------------
 
83
// TOutputStream functions
 
84
 
 
85
void TOutputStream::PutBits(uint32_t dwBuff, uint32_t nPutBits)
 
86
{
 
87
    dwBitBuff |= (dwBuff << nBits);
 
88
    nBits     += nPutBits;
 
89
 
 
90
    // Flush completed bytes
 
91
    while(nBits >= 8)
 
92
    {
 
93
        if(dwOutSize != 0)
 
94
        {
 
95
            *pbOutPos++ = (uint8_t)dwBitBuff;
 
96
            dwOutSize--;
 
97
        }
 
98
 
 
99
        dwBitBuff >>= 8;
 
100
        nBits      -= 8;
 
101
    }
 
102
}
 
103
 
 
104
//-----------------------------------------------------------------------------
 
105
// TInputStream functions
 
106
 
 
107
// Gets one bit from input stream
 
108
uint32_t TInputStream::GetBit() {
 
109
//      printf("GetBit >> buffer_bit_size: %llu, bit_count: %u\n", buffer_bit_size, bit_count);
 
110
//      fflush(stdout);
 
111
    assert(buffer_bit_size + bit_count >= 1);
 
112
    
 
113
    if(bit_count == 0) {
 
114
        // The bucket is empty!
 
115
        assert(buffer_bit_size >= 8);
 
116
        
 
117
        if (buffer_bit_size >= 32) {
 
118
            bit_bucket = CFSwapInt32LittleToHost(*(uint32_t *)buffer);
 
119
            bit_count = 32;
 
120
            
 
121
            buffer += 4;
 
122
            buffer_bit_size -= 32;
 
123
        } else {
 
124
            bit_bucket = (uint32_t)*buffer;
 
125
            bit_count = 8;
 
126
            
 
127
            buffer++;
 
128
            buffer_bit_size -= 8;
 
129
        }
 
130
    }
 
131
    
 
132
    uint32_t bit = (bit_bucket & 1);
 
133
    bit_bucket >>= 1;
 
134
    bit_count--;
 
135
    
 
136
    return bit;
 
137
}
 
138
 
 
139
// Gets the whole byte from the input stream.
 
140
uint32_t TInputStream::Get8Bits() {
 
141
//      printf("Get8Bits >> buffer_bit_size: %llu, bit_count: %u\n", buffer_bit_size, bit_count);
 
142
//      fflush(stdout);
 
143
    assert(buffer_bit_size + bit_count >= 8);
 
144
    
 
145
    if(bit_count <= 8) {
 
146
        assert(buffer_bit_size >= 8);
 
147
        
 
148
        if (buffer_bit_size >= 16) {
 
149
            bit_bucket |= ((uint32_t)CFSwapInt16LittleToHost(*(uint16_t *)buffer)) << bit_count;
 
150
            bit_count += 16;
 
151
            
 
152
            buffer += 2;
 
153
            buffer_bit_size -= 16;
 
154
        } else {
 
155
            bit_bucket |= ((uint32_t)*buffer) << bit_count;
 
156
            bit_count += 8;
 
157
            
 
158
            buffer++;
 
159
            buffer_bit_size -= 8;
 
160
        }
 
161
    }
 
162
    
 
163
    uint32_t byte = (bit_bucket & 0xFF);
 
164
    bit_bucket >>= 8;
 
165
    bit_count -= 8;
 
166
    
 
167
    return byte;
 
168
}
 
169
 
 
170
// Peek 7 bits from the stream
 
171
uint32_t TInputStream::Peek7Bits() {
 
172
//      printf("Peek7Bits >> buffer_bit_size: %llu, bit_count: %u\n", buffer_bit_size, bit_count);
 
173
//      fflush(stdout);
 
174
    assert(buffer_bit_size + bit_count >= 7);
 
175
    
 
176
    if(bit_count < 7) {
 
177
        assert(buffer_bit_size >= 8);
 
178
        
 
179
        if (buffer_bit_size >= 16) {
 
180
            bit_bucket |= ((uint32_t)CFSwapInt16LittleToHost(*(uint16_t *)buffer)) << bit_count;
 
181
            bit_count += 16;
 
182
            
 
183
            buffer += 2;
 
184
            buffer_bit_size -= 16;
 
185
        } else {
 
186
            bit_bucket |= ((uint32_t)*buffer) << bit_count;
 
187
            bit_count += 8;
 
188
            
 
189
            buffer++;
 
190
            buffer_bit_size -= 8;
 
191
        }
 
192
    }
 
193
 
 
194
    // Get 7 bits from input stream
 
195
    return (bit_bucket & 0x7F);
 
196
}
 
197
 
 
198
void TInputStream::ConsumeBits(uint32_t count) {
 
199
//      printf("ConsumeBits(%u) >> buffer_bit_size: %llu, bit_count: %u\n", count, buffer_bit_size, bit_count);
 
200
//      fflush(stdout);
 
201
        assert(buffer_bit_size + bit_count >= count);
 
202
    
 
203
    if (count <= bit_count) {
 
204
        bit_bucket >>= count;
 
205
        bit_count -= count;
 
206
    } else {
 
207
        // Drain the bit bucket
 
208
        count -= bit_count;
 
209
        bit_count = 0;
 
210
        buffer = 0;
 
211
        
 
212
        // Consume as many bytes out of the buffer
 
213
        uint32_t byte_count = count / 8;
 
214
        uint32_t extra_bits = count - (byte_count * 8);
 
215
        
 
216
        assert(buffer_bit_size >= byte_count * 8);
 
217
        buffer += byte_count;
 
218
        buffer_bit_size -= byte_count * 8U;
 
219
        
 
220
        // If there are extra bits, consume an extra byte out of the buffer and consume the bits
 
221
        if (extra_bits > 0) {
 
222
            assert(buffer_bit_size >= 8);
 
223
 
 
224
            bit_bucket = ((uint32_t)*buffer) >> extra_bits;
 
225
            bit_count = 8 - extra_bits;
 
226
            
 
227
            buffer++;
 
228
            buffer_bit_size -= 8;
 
229
        }
 
230
    }
 
231
}
 
232
 
 
233
//-----------------------------------------------------------------------------
 
234
// Functions for huffmann tree items
 
235
 
 
236
// Inserts item into the tree (?)
 
237
static void InsertItem(THTreeItem ** itemPtr, THTreeItem * item, uint32_t where, THTreeItem * item2)
 
238
{
 
239
    THTreeItem * next = item->next;             // EDI - next to the first item
 
240
    THTreeItem * prev = item->prev;             // ESI - prev to the first item
 
241
    THTreeItem * prev2;                         // Pointer to previous item
 
242
    intptr_t     next2;                         // Pointer to the next item
 
243
    intptr_t     addr_multiplier = item->addr_multiplier;
 
244
   
 
245
    // The same code like in RemoveItem(item);
 
246
    if(next != 0)                               // If the first item already has next one
 
247
    {
 
248
        if(PTR_INVALID(prev))
 
249
            prev = PTR_NOT(prev);
 
250
        else
 
251
            prev += (item - next->prev);
 
252
 
 
253
        // 150083C1
 
254
        // Remove the item from the tree
 
255
        prev->next = next;
 
256
        next->prev = prev;
 
257
 
 
258
        // Invalidate 'prev' and 'next' pointer
 
259
        item->next = 0;
 
260
        item->prev = 0;
 
261
    }
 
262
 
 
263
    if(item2 == 0)                              // EDX - If the second item is not entered,
 
264
        item2 = PTR_PTR(&itemPtr[1]);           // take the first tree item
 
265
 
 
266
    switch(where)
 
267
    {
 
268
        case SWITCH_ITEMS :                     // Switch the two items
 
269
            item->next  = item2->next;          // item2->next (Pointer to pointer to first)
 
270
            item->prev  = item2->next->prev;
 
271
            item2->next->prev = item;
 
272
            item2->next = item;                 // Set the first item
 
273
            return;
 
274
       
 
275
        case INSERT_ITEM:                       // Insert as the last item
 
276
            item->next = item2;                 // Set next item (or pointer to pointer to first item)
 
277
            item->prev = item2->prev;           // Set prev item (or last item in the tree)
 
278
 
 
279
            next2 = PTR_INT(itemPtr[0]);        // Usually 0
 
280
            prev2 = item2->prev;                // Prev item to the second (or last tree item)
 
281
           
 
282
            if(PTR_INVALID(prev2))
 
283
            {
 
284
                prev2 = PTR_NOT(prev);
 
285
 
 
286
                prev2->next = item;
 
287
                item2->prev = item;             // Next after last item
 
288
                return;
 
289
            }
 
290
 
 
291
            if(PTR_INVALID(next2))
 
292
                next2 = (intptr_t)(item2 - item2->next->prev);
 
293
//              next2 = (THTreeItem *)(unsigned long)((unsigned char *)item2 - (unsigned char *)(item2->next->prev));
 
294
 
 
295
//          prev2 = (THTreeItem *)((char *)prev2 + (unsigned long)next2);// ???
 
296
            prev2 += next2;
 
297
            prev2->next = item;
 
298
            item2->prev = item;                 // Set the next/last item
 
299
            return;
 
300
 
 
301
        default:
 
302
            return;
 
303
    }
 
304
}
 
305
 
 
306
//-----------------------------------------------------------------------------
 
307
// THuffmanTree class functions
 
308
 
 
309
THuffmanTree* THuffmanTree::AllocateTree() {
 
310
    THuffmanTree* instance = new THuffmanTree();
 
311
    if ((intptr_t)instance > 0 && (intptr_t)(instance + 1) < 0) {
 
312
        THuffmanTree* instance2 = new THuffmanTree();
 
313
        assert(!((intptr_t)instance2 > 0 && (intptr_t)(instance2 + 1) < 0));
 
314
        delete instance;
 
315
        instance = instance2;
 
316
    }
 
317
    return instance;
 
318
}
 
319
 
 
320
THuffmanTree::THuffmanTree()
 
321
{
 
322
    addr_multiplier = ((intptr_t)this < 0) ? -1 : 1;
 
323
}
 
324
 
 
325
void THuffmanTree::InitTree(bool bCompression)
 
326
{
 
327
    THTreeItem * pItem;
 
328
    uint32_t     nCount;
 
329
 
 
330
    // Clear links for all the items in the tree
 
331
    for(pItem = items0008, nCount = 0x203; nCount != 0; pItem++, nCount--)
 
332
    {
 
333
        pItem->ClearItemLinks();
 
334
        pItem->addr_multiplier = addr_multiplier;
 
335
    }
 
336
 
 
337
    pItem3050 = 0;
 
338
    pItem3054 = PTR_PTR(&pItem3054);
 
339
    pItem3058 = PTR_NOT(pItem3054);
 
340
   
 
341
    pItem305C = 0;
 
342
    pFirst    = PTR_PTR(&pFirst);
 
343
    pLast     = PTR_NOT(pFirst);
 
344
 
 
345
    offs0004  = 1;
 
346
    nItems    = 0;
 
347
 
 
348
    // Clear all TQDecompress items. Do this only if preparing for decompression
 
349
    if(bCompression == false)
 
350
    {
 
351
        for(nCount = 0; nCount < sizeof(qd3474) / sizeof(TQDecompress); nCount++)
 
352
            qd3474[nCount].offs00 = 0;
 
353
    }
 
354
}
 
355
 
 
356
// Builds Huffman tree. Called with the first 8 bits loaded from input stream
 
357
void THuffmanTree::BuildTree(uint32_t nCmpType)
 
358
{
 
359
    uint32_t        maxByte;                            // [ESP+10] - The greatest character found in table
 
360
    THTreeItem   ** itemPtr;                            // [ESP+14] - Pointer to Huffman tree item pointer array
 
361
    uint8_t       * byteArray;                          // [ESP+1C] - Pointer to unsigned char in Table1502A630
 
362
    THTreeItem    * child1;
 
363
    uint32_t        i;                                  // egcs in linux doesn't like multiple for loops without an explicit i
 
364
 
 
365
    // Loop while pointer has a valid value
 
366
    while(PTR_VALID(pLast))                             // ESI - Last entry
 
367
    {
 
368
        THTreeItem * temp;                              // EAX
 
369
 
 
370
        if(pLast->next != 0)                            // ESI->next
 
371
            pLast->RemoveItem();
 
372
                                                        // EDI = &offs3054
 
373
        pItem3058   = PTR_PTR(&pItem3054);              // [EDI+4]
 
374
        pLast->prev = pItem3058;                        // EAX
 
375
 
 
376
        temp = PTR_PTR(&pItem3054)->GetPrevItem(PTR_INT(&pItem3050));
 
377
 
 
378
        temp->next = pLast;
 
379
        pItem3054  = pLast;
 
380
    }
 
381
 
 
382
    // Clear all pointers in HTree item array
 
383
    memset(items306C, 0, sizeof(items306C));
 
384
 
 
385
    maxByte = 0;                                        // Greatest character found init to zero.
 
386
    itemPtr = (THTreeItem **)&items306C;                // Pointer to current entry in HTree item pointer array
 
387
 
 
388
    // Ensure we have low 8 bits only
 
389
    nCmpType &= 0xFF;
 
390
    byteArray  = Table1502A630 + nCmpType * 258;        // EDI also
 
391
 
 
392
    for(i = 0; i < 0x100; i++, itemPtr++)
 
393
    {
 
394
        THTreeItem * item   = pItem3058;                // Item to be created
 
395
        THTreeItem * pItem3 = pItem3058;
 
396
        uint8_t     oneByte = byteArray[i];
 
397
 
 
398
        // Skip all the bytes which are zero.
 
399
        if(byteArray[i] == 0)
 
400
            continue;
 
401
 
 
402
        // If not valid pointer, take the first available item in the array
 
403
        if(PTR_INVALID_OR_NULL(item))
 
404
            item = &items0008[nItems++];
 
405
 
 
406
        // Insert this item as the top of the tree
 
407
        InsertItem(&pItem305C, item, SWITCH_ITEMS, 0);
 
408
 
 
409
        item->parent    = 0;                            // Invalidate child and parent
 
410
        item->child     = 0;
 
411
        *itemPtr        = item;                         // Store pointer into pointer array
 
412
 
 
413
        item->dcmpByte  = i;                            // Store counter
 
414
        item->byteValue = oneByte;                      // Store byte value
 
415
        if(oneByte >= maxByte)
 
416
        {
 
417
            maxByte = oneByte;
 
418
            continue;
 
419
        }
 
420
 
 
421
        // Find the first item which has byte value greater than current one byte
 
422
        if(PTR_VALID(pItem3 = pLast))                   // EDI - Pointer to the last item
 
423
        {
 
424
            // 15006AF7
 
425
            if(pItem3 != 0)
 
426
            {
 
427
                do  // 15006AFB
 
428
                {
 
429
                    if(pItem3->byteValue >= oneByte)
 
430
                        goto _15006B09;
 
431
                    pItem3 = pItem3->prev;
 
432
                }
 
433
                while(PTR_VALID(pItem3));
 
434
            }
 
435
        }
 
436
        pItem3 = 0;
 
437
 
 
438
        // 15006B09
 
439
        _15006B09:
 
440
        if(item->next != 0)
 
441
            item->RemoveItem();
 
442
 
 
443
        // 15006B15
 
444
        if(pItem3 == 0)
 
445
            pItem3 = PTR_PTR(&pFirst);
 
446
 
 
447
        // 15006B1F
 
448
        item->next = pItem3->next;
 
449
        item->prev = pItem3->next->prev;
 
450
        pItem3->next->prev = item;
 
451
        pItem3->next = item;
 
452
    }
 
453
 
 
454
    // 15006B4A
 
455
    for(; i < 0x102; i++)
 
456
    {
 
457
        THTreeItem ** itemPtr = &items306C[i];          // EDI
 
458
 
 
459
        // 15006B59
 
460
        THTreeItem * item = pItem3058;                  // ESI
 
461
        if(PTR_INVALID_OR_NULL(item))
 
462
            item = &items0008[nItems++];
 
463
 
 
464
        InsertItem(&pItem305C, item, INSERT_ITEM, 0);
 
465
 
 
466
        // 15006B89
 
467
        item->dcmpByte   = i;
 
468
        item->byteValue  = 1;
 
469
        item->parent     = 0;
 
470
        item->child      = 0;
 
471
        *itemPtr++ = item;
 
472
    }
 
473
 
 
474
    // 15006BAA
 
475
    if(PTR_VALID(child1 = pLast))                       // EDI - last item (first child to item
 
476
    {
 
477
        THTreeItem * child2;                            // EBP
 
478
        THTreeItem * item;                              // ESI
 
479
 
 
480
        // 15006BB8
 
481
        while(PTR_VALID(child2 = child1->prev))
 
482
        {
 
483
            if(PTR_INVALID_OR_NULL(item = pItem3058))
 
484
                item = &items0008[nItems++];
 
485
 
 
486
            // 15006BE3
 
487
            InsertItem(&pItem305C, item, SWITCH_ITEMS, 0);
 
488
 
 
489
            // 15006BF3
 
490
            item->parent = 0;
 
491
            item->child  = 0;
 
492
 
 
493
            //EDX = child2->byteValue + child1->byteValue;
 
494
            //EAX = child1->byteValue;
 
495
            //ECX = maxByte;                                            // The greatest character (0xFF usually)
 
496
 
 
497
            item->byteValue = child1->byteValue + child2->byteValue;    // 0x02
 
498
            item->child     = child1;                                   // Prev item in the
 
499
            child1->parent  = item;
 
500
            child2->parent  = item;
 
501
 
 
502
            // EAX = item->byteValue;
 
503
            if(item->byteValue >= maxByte)
 
504
                maxByte = item->byteValue;
 
505
            else
 
506
            {
 
507
                THTreeItem * pItem2 = child2->prev;                     // EDI
 
508
 
 
509
                // 15006C2D
 
510
                while(PTR_VALID(pItem2))
 
511
                {
 
512
                    if(pItem2->byteValue >= item->byteValue)
 
513
                        goto _15006C3B;
 
514
                    pItem2 = pItem2->prev;
 
515
                }
 
516
                pItem2 = 0;
 
517
 
 
518
                _15006C3B:
 
519
                if(item->next != 0)
 
520
                {
 
521
                    THTreeItem * temp4 = item->GetPrevItem(-1);
 
522
                                                                   
 
523
                    temp4->next      = item->next;                      // The first item changed
 
524
                    item->next->prev = item->prev;                      // First->prev changed to negative value
 
525
                    item->next = 0;
 
526
                    item->prev = 0;
 
527
                }
 
528
 
 
529
                // 15006C62
 
530
                if(pItem2 == 0)
 
531
                    pItem2 = PTR_PTR(&pFirst);
 
532
 
 
533
                item->next = pItem2->next;                              // Set item with 0x100 byte value
 
534
                item->prev = pItem2->next->prev;                        // Set item with 0x17 byte value
 
535
                pItem2->next->prev = item;                              // Changed prev of item with
 
536
                pItem2->next = item;
 
537
            }
 
538
 
 
539
            // 15006C7B
 
540
            if(PTR_INVALID_OR_NULL(child1 = child2->prev))
 
541
                break;
 
542
        }
 
543
    }
 
544
    // 15006C88
 
545
    offs0004 = 1;
 
546
}
 
547
 
 
548
THTreeItem * THuffmanTree::Call1500E740(uint32_t nValue)
 
549
{
 
550
    THTreeItem * pItem1 = pItem3058;    // EDX
 
551
    THTreeItem * pItem2;                // EAX
 
552
    THTreeItem * pNext;
 
553
    THTreeItem * pPrev;
 
554
    THTreeItem ** ppItem;
 
555
 
 
556
    if(PTR_INVALID_OR_NULL(pItem1) || (pItem2 = pItem1) == 0)
 
557
    {
 
558
        if((pItem2 = &items0008[nItems++]) != 0)
 
559
            pItem1 = pItem2;
 
560
        else
 
561
            pItem1 = pFirst;
 
562
    }
 
563
    else
 
564
        pItem1 = pItem2;
 
565
 
 
566
    pNext = pItem1->next;
 
567
    if(pNext != 0)
 
568
    {
 
569
        pPrev = pItem1->prev;
 
570
        if(PTR_INVALID_OR_NULL(pPrev))
 
571
            pPrev = PTR_NOT(pPrev);
 
572
        else
 
573
            pPrev += (pItem1 - pItem1->next->prev);
 
574
 
 
575
        pPrev->next = pNext;
 
576
        pNext->prev = pPrev;
 
577
        pItem1->next = 0;
 
578
        pItem1->prev = 0;
 
579
    }
 
580
 
 
581
    ppItem = &pFirst;       // esi
 
582
    if(nValue > 1)
 
583
    {
 
584
        // ecx = pFirst->next;
 
585
        pItem1->next = *ppItem;
 
586
        pItem1->prev = (*ppItem)->prev;
 
587
 
 
588
        (*ppItem)->prev = pItem2;
 
589
        *ppItem = pItem1;
 
590
 
 
591
        pItem2->parent = 0;
 
592
        pItem2->child  = 0;
 
593
    }
 
594
    else
 
595
    {
 
596
        pItem1->next = (THTreeItem *)ppItem;
 
597
        pItem1->prev = ppItem[1];
 
598
        // edi = pItem305C;
 
599
        pPrev = ppItem[1];      // ecx
 
600
        if(PTR_INVALID_OR_NULL(pPrev))
 
601
        {
 
602
            pPrev = PTR_NOT(pPrev);
 
603
            pPrev->next = pItem1;
 
604
            pPrev->prev = pItem2;
 
605
 
 
606
            pItem2->parent = 0;
 
607
            pItem2->child  = 0;
 
608
        }
 
609
        else
 
610
        {
 
611
            if(PTR_INVALID(pItem305C))
 
612
                pPrev += (THTreeItem *)ppItem - (*ppItem)->prev;
 
613
            else
 
614
                pPrev += PTR_INT(pItem305C);
 
615
 
 
616
            pPrev->next    = pItem1;
 
617
            ppItem[1]      = pItem2;
 
618
            pItem2->parent = 0;
 
619
            pItem2->child  = 0;
 
620
        }
 
621
    }
 
622
    return pItem2;
 
623
}
 
624
 
 
625
void THuffmanTree::Call1500E820(THTreeItem * pItem)
 
626
{
 
627
    THTreeItem * pItem1;                // edi
 
628
    THTreeItem * pItem2 = 0;            // eax
 
629
    THTreeItem * pItem3;                // edx
 
630
    THTreeItem * pPrev;                 // ebx
 
631
 
 
632
    for(; pItem != 0; pItem = pItem->parent)
 
633
    {
 
634
        pItem->byteValue++;
 
635
       
 
636
        for(pItem1 = pItem; ; pItem1 = pPrev)
 
637
        {
 
638
            pPrev = pItem1->prev;
 
639
            if(PTR_INVALID_OR_NULL(pPrev))
 
640
            {
 
641
                pPrev = 0;
 
642
                break;
 
643
            }
 
644
 
 
645
            if(pPrev->byteValue >= pItem->byteValue)
 
646
                break;
 
647
        }
 
648
 
 
649
        if(pItem1 == pItem)
 
650
            continue;
 
651
 
 
652
        if(pItem1->next != 0)
 
653
        {
 
654
            pItem2 = pItem1->GetPrevItem(-1);
 
655
            pItem2->next = pItem1->next;
 
656
            pItem1->next->prev = pItem1->prev;
 
657
            pItem1->next = 0;
 
658
            pItem1->prev = 0;
 
659
        }
 
660
 
 
661
        pItem2 = pItem->next;
 
662
        pItem1->next = pItem2;
 
663
        pItem1->prev = pItem2->prev;
 
664
        pItem2->prev = pItem1;
 
665
        pItem->next = pItem1;
 
666
        if((pItem2 = pItem1) != 0)
 
667
        {
 
668
            pItem2 = pItem->GetPrevItem(-1);
 
669
            pItem2->next = pItem->next;
 
670
            pItem->next->prev = pItem->prev;
 
671
            pItem->next = 0;
 
672
            pItem->prev = 0;
 
673
        }
 
674
 
 
675
        if(pPrev == 0)
 
676
            pPrev = PTR_PTR(&pFirst);
 
677
 
 
678
        pItem2       = pPrev->next;
 
679
        pItem->next  = pItem2;
 
680
        pItem->prev  = pItem2->prev;
 
681
        pItem2->prev = pItem;
 
682
        pPrev->next  = pItem;
 
683
 
 
684
        pItem3 = pItem1->parent->child;
 
685
        pItem2 = pItem->parent;
 
686
        if(pItem2->child == pItem)
 
687
            pItem2->child = pItem1;
 
688
        if(pItem3 == pItem1)
 
689
            pItem1->parent->child = pItem;
 
690
 
 
691
        pItem2 = pItem->parent;
 
692
        pItem->parent  = pItem1->parent;
 
693
        pItem1->parent = pItem2;
 
694
        offs0004++;
 
695
    }
 
696
}
 
697
 
 
698
// 1500E920
 
699
uint32_t THuffmanTree::DoCompression(TOutputStream *os, uint8_t *pbInBuffer, int32_t nInLength, int32_t nCmpType)
 
700
{
 
701
    THTreeItem * pItem1;
 
702
    THTreeItem * pItem2;
 
703
    THTreeItem * pItem3;
 
704
    THTreeItem * pTemp;
 
705
    uint32_t     dwBitBuff;
 
706
    uint32_t     nBits;
 
707
    uint32_t     nBit;
 
708
        
 
709
    BuildTree(nCmpType);
 
710
    bIsCmp0 = (nCmpType == 0);
 
711
 
 
712
    // Store the compression type into output buffer
 
713
    os->dwBitBuff |= (nCmpType << os->nBits);
 
714
    os->nBits     += 8;
 
715
 
 
716
    // Flush completed bytes
 
717
    while(os->nBits >= 8)
 
718
    {
 
719
        if(os->dwOutSize != 0)
 
720
        {
 
721
            *os->pbOutPos++ = (uint8_t)os->dwBitBuff;
 
722
            os->dwOutSize--;
 
723
        }
 
724
 
 
725
        os->dwBitBuff >>= 8;
 
726
        os->nBits      -= 8;
 
727
    }
 
728
 
 
729
    for(; nInLength != 0; nInLength--)
 
730
    {
 
731
        uint8_t bOneByte = *pbInBuffer++;
 
732
 
 
733
        if((pItem1 = items306C[bOneByte]) == 0)
 
734
        {
 
735
            pItem2    = items306C[0x101];  // ecx
 
736
            pItem3    = pItem2->parent;    // eax
 
737
            dwBitBuff = 0;
 
738
            nBits     = 0;
 
739
 
 
740
            for(; pItem3 != 0; pItem3 = pItem3->parent)
 
741
            {
 
742
                nBit      = (pItem3->child != pItem2) ? 1 : 0;
 
743
                dwBitBuff = (dwBitBuff << 1) | nBit;
 
744
                nBits++;
 
745
                pItem2  = pItem3;
 
746
            }
 
747
            os->PutBits(dwBitBuff, nBits);
 
748
 
 
749
            // Store the loaded byte into output stream
 
750
            os->dwBitBuff |= (bOneByte << os->nBits);
 
751
            os->nBits     += 8;
 
752
 
 
753
            // Flush the whole byte(s)
 
754
            while(os->nBits >= 8)
 
755
            {
 
756
                if(os->dwOutSize != 0)
 
757
                {
 
758
                    *os->pbOutPos++ = (uint8_t)os->dwBitBuff;
 
759
                    os->dwOutSize--;
 
760
                }
 
761
                os->dwBitBuff >>= 8;
 
762
                os->nBits -= 8;
 
763
            }
 
764
 
 
765
            pItem1 = (PTR_INVALID_OR_NULL(pLast)) ? 0 : pLast;
 
766
            pItem2 = Call1500E740(1);
 
767
            pItem2->dcmpByte  = pItem1->dcmpByte;
 
768
            pItem2->byteValue = pItem1->byteValue;
 
769
            pItem2->parent    = pItem1;
 
770
            items306C[pItem2->dcmpByte] = pItem2;
 
771
 
 
772
            pItem2 = Call1500E740(1);
 
773
            pItem2->dcmpByte  = bOneByte;
 
774
            pItem2->byteValue = 0;
 
775
            pItem2->parent    = pItem1;
 
776
            items306C[pItem2->dcmpByte] = pItem2;
 
777
            pItem1->child = pItem2;
 
778
 
 
779
            Call1500E820(pItem2);
 
780
 
 
781
            if(bIsCmp0 != 0)
 
782
            {
 
783
                Call1500E820(items306C[bOneByte]);
 
784
                continue;
 
785
            }
 
786
 
 
787
            for(pItem1 = items306C[bOneByte]; pItem1 != 0; pItem1 = pItem1->parent)
 
788
            {
 
789
                pItem1->byteValue++;
 
790
                pItem2 = pItem1;
 
791
 
 
792
                for(;;)
 
793
                {
 
794
                    pItem3 = pItem2->prev;
 
795
                    if(PTR_INVALID_OR_NULL(pItem3))
 
796
                    {
 
797
                        pItem3 = 0;
 
798
                        break;
 
799
                    }
 
800
                    if(pItem3->byteValue >= pItem1->byteValue)
 
801
                        break;
 
802
                    pItem2 = pItem3;
 
803
                }
 
804
 
 
805
                if(pItem2 != pItem1)
 
806
                {
 
807
                    InsertItem(&pItem305C, pItem2, SWITCH_ITEMS, pItem1);
 
808
                    InsertItem(&pItem305C, pItem1, SWITCH_ITEMS, pItem3);
 
809
 
 
810
                    pItem3 = pItem2->parent->child;
 
811
                    if(pItem1->parent->child == pItem1)
 
812
                        pItem1->parent->child = pItem2;
 
813
 
 
814
                    if(pItem3 == pItem2)
 
815
                        pItem2->parent->child = pItem1;
 
816
 
 
817
                    pTemp = pItem1->parent;
 
818
                    pItem1->parent = pItem2->parent;
 
819
                    pItem2->parent = pTemp;
 
820
                    offs0004++;
 
821
                }
 
822
            }
 
823
        }
 
824
// 1500EB62
 
825
        else
 
826
        {
 
827
            dwBitBuff = 0;
 
828
            nBits = 0;
 
829
            for(pItem2 = pItem1->parent; pItem2 != 0; pItem2 = pItem2->parent)
 
830
            {
 
831
                nBit      = (pItem2->child != pItem1) ? 1 : 0;
 
832
                dwBitBuff = (dwBitBuff << 1) | nBit;
 
833
                nBits++;
 
834
                pItem1    = pItem2;
 
835
            }
 
836
            os->PutBits(dwBitBuff, nBits);
 
837
        }
 
838
 
 
839
// 1500EB98
 
840
        if(bIsCmp0 != 0)
 
841
            Call1500E820(items306C[bOneByte]);  // 1500EB9D
 
842
// 1500EBAF
 
843
    } // for(; nInLength != 0; nInLength--)
 
844
 
 
845
// 1500EBB8
 
846
    pItem1 = items306C[0x100];
 
847
    dwBitBuff = 0;
 
848
    nBits = 0;
 
849
    for(pItem2 = pItem1->parent; pItem2 != 0; pItem2 = pItem2->parent)
 
850
    {
 
851
        nBit      = (pItem2->child != pItem1) ? 1 : 0;
 
852
        dwBitBuff = (dwBitBuff << 1) | nBit;
 
853
        nBits++;
 
854
        pItem1    = pItem2;
 
855
    }
 
856
 
 
857
// 1500EBE6
 
858
    os->PutBits(dwBitBuff, nBits);
 
859
 
 
860
// 1500EBEF
 
861
    // Flush the remaining bits
 
862
    while(os->nBits != 0)
 
863
    {
 
864
        if(os->dwOutSize != 0)
 
865
        {
 
866
            *os->pbOutPos++ = (uint8_t)os->dwBitBuff;
 
867
            os->dwOutSize--;
 
868
        }
 
869
        os->dwBitBuff >>= 8;
 
870
        os->nBits -= ((os->nBits > 8) ? 8 : os->nBits);
 
871
    }
 
872
 
 
873
    return (uint32_t)(os->pbOutPos - os->pbOutBuffer);
 
874
}
 
875
 
 
876
// Decompression using Huffman tree (1500E450)
 
877
uint32_t THuffmanTree::DoDecompression(uint8_t *pbOutBuffer, uint32_t dwOutLength, TInputStream *is)
 
878
{
 
879
    TQDecompress  * qd;
 
880
    THTreeItem    * pItem1;
 
881
    THTreeItem    * pItem2;
 
882
    uint8_t       * pbOutPos = pbOutBuffer;
 
883
    uint32_t        nBitCount;
 
884
    uint32_t        nDcmpByte = 0;
 
885
    uint32_t        n8Bits;                // 8 bits loaded from input stream
 
886
    uint32_t        n7Bits;                // 7 bits loaded from input stream
 
887
    bool            bHasQdEntry;
 
888
   
 
889
    // Test the output length. Must not be 0.
 
890
    if(dwOutLength == 0)
 
891
        return 0;
 
892
                
 
893
        // If the input size is 0, we're done
 
894
        if (is->GetBufferBitSize() == 0) return 0;
 
895
 
 
896
    // Get the compression type from the input stream
 
897
    n8Bits = is->Get8Bits();
 
898
 
 
899
    // Build the Huffman tree
 
900
    BuildTree(n8Bits);    
 
901
    bIsCmp0 = (n8Bits == 0) ? 1 : 0;
 
902
 
 
903
    for(;;)
 
904
    {
 
905
        n7Bits = is->Peek7Bits();            // Get 7 bits from input stream
 
906
 
 
907
        // Try to use quick decompression. Check TQDecompress array for corresponding item.
 
908
        // If found, ise the result byte instead.
 
909
        qd = &qd3474[n7Bits];
 
910
 
 
911
        // If there is a quick-pass possible (ebx)
 
912
        bHasQdEntry = (qd->offs00 >= offs0004) ? true : false;
 
913
 
 
914
        // If we can use quick decompress, use it.
 
915
        if(bHasQdEntry)
 
916
        {
 
917
            if(qd->nBits > 7)
 
918
            {
 
919
                is->ConsumeBits(7);
 
920
                pItem1 = qd->pItem;
 
921
                goto _1500E549;
 
922
            }
 
923
            is->ConsumeBits(qd->nBits);
 
924
            nDcmpByte = qd->dcmpByte;
 
925
        }
 
926
        else
 
927
        {
 
928
            pItem1 = pFirst->next->prev;
 
929
            if(PTR_INVALID_OR_NULL(pItem1))
 
930
                pItem1 = 0;
 
931
_1500E549:           
 
932
            nBitCount = 0;
 
933
            pItem2 = 0;
 
934
 
 
935
            do
 
936
            {
 
937
                pItem1 = pItem1->child;     // Move down by one level
 
938
                if(is->GetBit())            // If current bit is set, move to previous
 
939
                    pItem1 = pItem1->prev;
 
940
 
 
941
                if(++nBitCount == 7)        // If we are at 7th bit, save current HTree item.
 
942
                    pItem2 = pItem1;
 
943
            }
 
944
            while(pItem1->child != 0);   // Walk until tree has no deeper level
 
945
 
 
946
            if(bHasQdEntry == false)
 
947
            {
 
948
                if(nBitCount > 7)
 
949
                {
 
950
                    qd->offs00 = offs0004;
 
951
                    qd->nBits  = nBitCount;
 
952
                    qd->pItem  = pItem2;
 
953
                }
 
954
                else
 
955
                {
 
956
                    uint32_t nIndex = n7Bits & (0xFFFFFFFF >> (32 - nBitCount));
 
957
                    uint32_t nAdd   = (1 << nBitCount);
 
958
                   
 
959
                    for(qd = &qd3474[nIndex]; nIndex <= 0x7F; nIndex += nAdd, qd += nAdd)
 
960
                    {
 
961
                        qd->offs00   = offs0004;
 
962
                        qd->nBits    = nBitCount;
 
963
                        qd->dcmpByte = pItem1->dcmpByte;
 
964
                    }
 
965
                }
 
966
            }
 
967
            nDcmpByte = pItem1->dcmpByte;
 
968
        }
 
969
 
 
970
        if(nDcmpByte == 0x101)          // Huffman tree needs to be modified
 
971
        {
 
972
            n8Bits = is->Get8Bits();
 
973
            pItem1 = (PTR_INVALID_OR_NULL(pLast)) ? 0 : pLast;
 
974
 
 
975
            pItem2 = Call1500E740(1);
 
976
            pItem2->parent    = pItem1;
 
977
            pItem2->dcmpByte  = pItem1->dcmpByte;
 
978
            pItem2->byteValue = pItem1->byteValue;
 
979
            items306C[pItem2->dcmpByte] = pItem2;
 
980
 
 
981
            pItem2 = Call1500E740(1);
 
982
            pItem2->parent    = pItem1;
 
983
            pItem2->dcmpByte  = n8Bits;
 
984
            pItem2->byteValue = 0;
 
985
            items306C[pItem2->dcmpByte] = pItem2;
 
986
 
 
987
            pItem1->child = pItem2;
 
988
            Call1500E820(pItem2);
 
989
            if(bIsCmp0 == 0)
 
990
                Call1500E820(items306C[n8Bits]);
 
991
 
 
992
            nDcmpByte = n8Bits;
 
993
        }
 
994
 
 
995
        if(nDcmpByte == 0x100)
 
996
            break;
 
997
 
 
998
        *pbOutPos++ = (uint8_t)nDcmpByte;
 
999
        if(--dwOutLength == 0)
 
1000
            break;
 
1001
 
 
1002
        if(bIsCmp0)
 
1003
            Call1500E820(items306C[nDcmpByte]);
 
1004
    }
 
1005
 
 
1006
    return (uint32_t)(pbOutPos - pbOutBuffer);
 
1007
}
 
1008
 
 
1009
// Table for (de)compression. Every compression type has 258 entries
 
1010
uint8_t THuffmanTree::Table1502A630[] =
 
1011
{
 
1012
    // Data for compression type 0x00
 
1013
    0x0A, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1014
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1015
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1016
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1017
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1018
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1019
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1020
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1021
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1022
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1023
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1024
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1025
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1026
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1027
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1028
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02,
 
1029
    0x00, 0x00,
 
1030
   
 
1031
    // Data for compression type 0x01
 
1032
    0x54, 0x16, 0x16, 0x0D, 0x0C, 0x08, 0x06, 0x05, 0x06, 0x05, 0x06, 0x03, 0x04, 0x04, 0x03, 0x05,
 
1033
    0x0E, 0x0B, 0x14, 0x13, 0x13, 0x09, 0x0B, 0x06, 0x05, 0x04, 0x03, 0x02, 0x03, 0x02, 0x02, 0x02,
 
1034
    0x0D, 0x07, 0x09, 0x06, 0x06, 0x04, 0x03, 0x02, 0x04, 0x03, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02,
 
1035
    0x09, 0x06, 0x04, 0x04, 0x04, 0x04, 0x03, 0x02, 0x03, 0x02, 0x02, 0x02, 0x02, 0x03, 0x02, 0x04,
 
1036
    0x08, 0x03, 0x04, 0x07, 0x09, 0x05, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02, 0x02, 0x03, 0x02, 0x02,
 
1037
    0x03, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02,
 
1038
    0x06, 0x0A, 0x08, 0x08, 0x06, 0x07, 0x04, 0x03, 0x04, 0x04, 0x02, 0x02, 0x04, 0x02, 0x03, 0x03,
 
1039
    0x04, 0x03, 0x07, 0x07, 0x09, 0x06, 0x04, 0x03, 0x03, 0x02, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02,
 
1040
    0x0A, 0x02, 0x02, 0x03, 0x02, 0x02, 0x01, 0x01, 0x02, 0x02, 0x02, 0x06, 0x03, 0x05, 0x02, 0x03,
 
1041
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x03, 0x01, 0x01, 0x01,
 
1042
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x04, 0x04, 0x04, 0x07, 0x09, 0x08, 0x0C, 0x02,
 
1043
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x03,
 
1044
    0x04, 0x01, 0x02, 0x04, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
 
1045
    0x04, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1046
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1047
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x01, 0x01, 0x02, 0x02, 0x02, 0x06, 0x4B,
 
1048
    0x00, 0x00,
 
1049
   
 
1050
    // Data for compression type 0x02
 
1051
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x27, 0x00, 0x00, 0x23, 0x00, 0x00,
 
1052
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1053
    0xFF, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x01, 0x01, 0x06, 0x0E, 0x10, 0x04,
 
1054
    0x06, 0x08, 0x05, 0x04, 0x04, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03, 0x01, 0x01, 0x02, 0x01, 0x01,
 
1055
    0x01, 0x04, 0x02, 0x04, 0x02, 0x02, 0x02, 0x01, 0x01, 0x04, 0x01, 0x01, 0x02, 0x03, 0x03, 0x02,
 
1056
    0x03, 0x01, 0x03, 0x06, 0x04, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x01, 0x01,
 
1057
    0x01, 0x29, 0x07, 0x16, 0x12, 0x40, 0x0A, 0x0A, 0x11, 0x25, 0x01, 0x03, 0x17, 0x10, 0x26, 0x2A,
 
1058
    0x10, 0x01, 0x23, 0x23, 0x2F, 0x10, 0x06, 0x07, 0x02, 0x09, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00,
 
1059
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1060
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1061
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1062
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1063
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1064
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1065
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1066
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1067
    0x00, 0x00,
 
1068
   
 
1069
    // Data for compression type 0x03
 
1070
    0xFF, 0x0B, 0x07, 0x05, 0x0B, 0x02, 0x02, 0x02, 0x06, 0x02, 0x02, 0x01, 0x04, 0x02, 0x01, 0x03,
 
1071
    0x09, 0x01, 0x01, 0x01, 0x03, 0x04, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
 
1072
    0x05, 0x01, 0x01, 0x01, 0x0D, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1073
    0x02, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01,
 
1074
    0x0A, 0x04, 0x02, 0x01, 0x06, 0x03, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01,
 
1075
    0x05, 0x02, 0x03, 0x04, 0x03, 0x03, 0x03, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x03, 0x03,
 
1076
    0x01, 0x03, 0x01, 0x01, 0x02, 0x05, 0x01, 0x01, 0x04, 0x03, 0x05, 0x01, 0x03, 0x01, 0x03, 0x03,
 
1077
    0x02, 0x01, 0x04, 0x03, 0x0A, 0x06, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1078
    0x02, 0x02, 0x01, 0x0A, 0x02, 0x05, 0x01, 0x01, 0x02, 0x07, 0x02, 0x17, 0x01, 0x05, 0x01, 0x01,
 
1079
    0x0E, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1080
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1081
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1082
    0x06, 0x02, 0x01, 0x04, 0x05, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
 
1083
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
 
1084
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x07, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01,
 
1085
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x11,
 
1086
    0x00, 0x00,
 
1087
   
 
1088
    // Data for compression type 0x04
 
1089
    0xFF, 0xFB, 0x98, 0x9A, 0x84, 0x85, 0x63, 0x64, 0x3E, 0x3E, 0x22, 0x22, 0x13, 0x13, 0x18, 0x17,
 
1090
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1091
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1092
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1093
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1094
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1095
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1096
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1097
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1098
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1099
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1100
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1101
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1102
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1103
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1104
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1105
    0x00, 0x00,
 
1106
   
 
1107
    // Data for compression type 0x05
 
1108
    0xFF, 0xF1, 0x9D, 0x9E, 0x9A, 0x9B, 0x9A, 0x97, 0x93, 0x93, 0x8C, 0x8E, 0x86, 0x88, 0x80, 0x82,
 
1109
    0x7C, 0x7C, 0x72, 0x73, 0x69, 0x6B, 0x5F, 0x60, 0x55, 0x56, 0x4A, 0x4B, 0x40, 0x41, 0x37, 0x37,
 
1110
    0x2F, 0x2F, 0x27, 0x27, 0x21, 0x21, 0x1B, 0x1C, 0x17, 0x17, 0x13, 0x13, 0x10, 0x10, 0x0D, 0x0D,
 
1111
    0x0B, 0x0B, 0x09, 0x09, 0x08, 0x08, 0x07, 0x07, 0x06, 0x05, 0x05, 0x04, 0x04, 0x04, 0x19, 0x18,
 
1112
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1113
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1114
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1115
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1116
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1117
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1118
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1119
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1120
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1121
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1122
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1123
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1124
    0x00, 0x00,
 
1125
   
 
1126
    // Data for compression type 0x06
 
1127
    0xC3, 0xCB, 0xF5, 0x41, 0xFF, 0x7B, 0xF7, 0x21, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1128
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1129
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1130
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1131
    0xBF, 0xCC, 0xF2, 0x40, 0xFD, 0x7C, 0xF7, 0x22, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1132
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1133
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1134
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1135
    0x7A, 0x46, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1136
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1137
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1138
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1139
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1140
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1141
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1142
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1143
    0x00, 0x00,
 
1144
   
 
1145
    // Data for compression type 0x07
 
1146
    0xC3, 0xD9, 0xEF, 0x3D, 0xF9, 0x7C, 0xE9, 0x1E, 0xFD, 0xAB, 0xF1, 0x2C, 0xFC, 0x5B, 0xFE, 0x17,
 
1147
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1148
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1149
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1150
    0xBD, 0xD9, 0xEC, 0x3D, 0xF5, 0x7D, 0xE8, 0x1D, 0xFB, 0xAE, 0xF0, 0x2C, 0xFB, 0x5C, 0xFF, 0x18,
 
1151
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1152
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1153
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1154
    0x70, 0x6C, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1155
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1156
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1157
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1158
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1159
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1160
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1161
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1162
    0x00, 0x00,
 
1163
   
 
1164
    // Data for compression type 0x08
 
1165
    0xBA, 0xC5, 0xDA, 0x33, 0xE3, 0x6D, 0xD8, 0x18, 0xE5, 0x94, 0xDA, 0x23, 0xDF, 0x4A, 0xD1, 0x10,
 
1166
    0xEE, 0xAF, 0xE4, 0x2C, 0xEA, 0x5A, 0xDE, 0x15, 0xF4, 0x87, 0xE9, 0x21, 0xF6, 0x43, 0xFC, 0x12,
 
1167
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1168
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1169
    0xB0, 0xC7, 0xD8, 0x33, 0xE3, 0x6B, 0xD6, 0x18, 0xE7, 0x95, 0xD8, 0x23, 0xDB, 0x49, 0xD0, 0x11,
 
1170
    0xE9, 0xB2, 0xE2, 0x2B, 0xE8, 0x5C, 0xDD, 0x15, 0xF1, 0x87, 0xE7, 0x20, 0xF7, 0x44, 0xFF, 0x13,
 
1171
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1172
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1173
    0x5F, 0x9E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1174
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1175
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1176
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1177
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1178
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1179
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1180
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
1181
    0x00, 0x00
 
1182
};