huffman.cpp

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