EdkCompatibilityPkg/Sample/Tools/Source/Common/TianoCompress.c

   1 /*++
   2
   3 Copyright (c) 2006, Intel Corporation. All rights reserved.<BR>
   4 This program and the accompanying materials
   5 are licensed and made available under the terms and conditions of the BSD License
   6 which accompanies this distribution.  The full text of the license may be found at
   7 http://opensource.org/licenses/bsd-license.php
   8
   9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  11
  12 Module Name:
  13
  14   TianoCompress.c
  15
  16 Abstract:
  17
  18   Compression routine. The compression algorithm is a mixture of
  19   LZ77 and Huffman coding. LZ77 transforms the source data into a
  20   sequence of Original Characters and Pointers to repeated strings.
  21   This sequence is further divided into Blocks and Huffman codings
  22   are applied to each Block.
  23
  24 --*/
  25
  26 #include <string.h>
  27 #include <stdlib.h>
  28 #include "TianoCommon.h"
  29 #include "Compress.h"
  30
  31 //
  32 // Macro Definitions
  33 //
  34 typedef INT32 NODE;
  35 #define UINT8_MAX     0xff
  36 #define UINT8_BIT     8
  37 #define THRESHOLD     3
  38 #define INIT_CRC      0
  39 #define WNDBIT        19
  40 #define WNDSIZ        (1U << WNDBIT)
  41 #define MAXMATCH      256
  42 #define BLKSIZ        (1U << 14)  // 16 * 1024U
  43 #define PERC_FLAG     0x80000000U
  44 #define CODE_BIT      16
  45 #define NIL           0
  46 #define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
  47 #define HASH(p, c)    ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
  48 #define CRCPOLY       0xA001
  49 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
  50
  51 //
  52 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
  53 //
  54 #define NC    (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
  55 #define CBIT  9
  56 #define NP    (WNDBIT + 1)
  57 #define PBIT  5
  58 #define NT    (CODE_BIT + 3)
  59 #define TBIT  5
  60 #if NT > NP
  61 #define NPT   NT
  62 #else
  63 #define NPT   NP
  64 #endif
  65 //
  66 // Function Prototypes
  67 //
  68 STATIC
  69 EFI_STATUS
  70 Compress (
  71   IN      UINT8   *SrcBuffer,
  72   IN      UINT32  SrcSize,
  73   IN      UINT8   *DstBuffer,
  74   IN OUT  UINT32  *DstSize,
  75   IN      UINT8   Version
  76   );
  77
  78 STATIC
  79 VOID
  80 PutDword(
  81   IN UINT32 Data
  82   );
  83
  84 STATIC
  85 EFI_STATUS
  86 AllocateMemory (
  87   VOID
  88   );
  89
  90 STATIC
  91 VOID
  92 FreeMemory (
  93   VOID
  94   );
  95
  96 STATIC
  97 VOID
  98 InitSlide (
  99   VOID
 100   );
 101
 102 STATIC
 103 NODE
 104 Child (
 105   IN NODE   NodeQ,
 106   IN UINT8  CharC
 107   );
 108
 109 STATIC
 110 VOID
 111 MakeChild (
 112   IN NODE  NodeQ,
 113   IN UINT8 CharC,
 114   IN NODE  NodeR
 115   );
 116
 117 STATIC
 118 VOID
 119 Split (
 120   IN NODE Old
 121   );
 122
 123 STATIC
 124 VOID
 125 InsertNode (
 126   VOID
 127   );
 128
 129 STATIC
 130 VOID
 131 DeleteNode (
 132   VOID
 133   );
 134
 135 STATIC
 136 VOID
 137 GetNextMatch (
 138   VOID
 139   );
 140
 141 STATIC
 142 EFI_STATUS
 143 Encode (
 144   VOID
 145   );
 146
 147 STATIC
 148 VOID
 149 CountTFreq (
 150   VOID
 151   );
 152
 153 STATIC
 154 VOID
 155 WritePTLen (
 156   IN INT32 Number,
 157   IN INT32 nbit,
 158   IN INT32 Special
 159   );
 160
 161 STATIC
 162 VOID
 163 WriteCLen (
 164   VOID
 165   );
 166
 167 STATIC
 168 VOID
 169 EncodeC (
 170   IN INT32 Value
 171   );
 172
 173 STATIC
 174 VOID
 175 EncodeP (
 176   IN UINT32 Value
 177   );
 178
 179 STATIC
 180 VOID
 181 SendBlock (
 182   VOID
 183   );
 184
 185 STATIC
 186 VOID
 187 Output (
 188   IN UINT32 c,
 189   IN UINT32 p
 190   );
 191
 192 STATIC
 193 VOID
 194 HufEncodeStart (
 195   VOID
 196   );
 197
 198 STATIC
 199 VOID
 200 HufEncodeEnd (
 201   VOID
 202   );
 203
 204 STATIC
 205 VOID
 206 MakeCrcTable (
 207   VOID
 208   );
 209
 210 STATIC
 211 VOID
 212 PutBits (
 213   IN INT32  Number,
 214   IN UINT32 Value
 215   );
 216
 217 STATIC
 218 INT32
 219 FreadCrc (
 220   OUT UINT8 *Pointer,
 221   IN  INT32 Number
 222   );
 223
 224 STATIC
 225 VOID
 226 InitPutBits (
 227   VOID
 228   );
 229
 230 STATIC
 231 VOID
 232 CountLen (
 233   IN INT32 Index
 234   );
 235
 236 STATIC
 237 VOID
 238 MakeLen (
 239   IN INT32 Root
 240   );
 241
 242 STATIC
 243 VOID
 244 DownHeap (
 245   IN INT32 Index
 246   );
 247
 248 STATIC
 249 VOID
 250 MakeCode (
 251   IN  INT32       Number,
 252   IN  UINT8 Len[  ],
 253   OUT UINT16 Code[]
 254   );
 255
 256 STATIC
 257 INT32
 258 MakeTree (
 259   IN  INT32            NParm,
 260   IN  UINT16  FreqParm[],
 261   OUT UINT8   LenParm[ ],
 262   OUT UINT16  CodeParm[]
 263   );
 264
 265 //
 266 //  Global Variables
 267 //
 268 STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
 269
 270 STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
 271 STATIC INT16  mHeap[NC + 1];
 272 STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
 273 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
 274 STATIC UINT32 mCompSize, mOrigSize;
 275
 276 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
 277   mCFreq[2 * NC - 1], mCTable[4096], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
 278
 279 STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
 280
 281 //
 282 // functions
 283 //
 284
 285 EFI_STATUS
 286 TianoCompress (
 287   IN      UINT8   *SrcBuffer,
 288   IN      UINT32  SrcSize,
 289   IN      UINT8   *DstBuffer,
 290   IN OUT  UINT32  *DstSize
 291   )
 292 /*++
 293
 294 Routine Description:
 295
 296   The internal implementation of [Efi/Tiano]Compress().
 297
 298 Arguments:
 299
 300   SrcBuffer   - The buffer storing the source data
 301   SrcSize     - The size of source data
 302   DstBuffer   - The buffer to store the compressed data
 303   DstSize     - On input, the size of DstBuffer; On output,
 304                 the size of the actual compressed data.
 305   Version     - The version of de/compression algorithm.
 306                 Version 1 for EFI 1.1 de/compression algorithm.
 307                 Version 2 for Tiano de/compression algorithm.
 308
 309 Returns:
 310
 311   EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,
 312                 DstSize contains the size needed.
 313   EFI_SUCCESS           - Compression is successful.
 314   EFI_OUT_OF_RESOURCES  - No resource to complete function.
 315   EFI_INVALID_PARAMETER - Parameter supplied is wrong.
 316
 317 --*/
 318 {
 319   EFI_STATUS  Status;
 320
 321   //
 322   // Initializations
 323   //
 324   mBufSiz         = 0;
 325   mBuf            = NULL;
 326   mText           = NULL;
 327   mLevel          = NULL;
 328   mChildCount     = NULL;
 329   mPosition       = NULL;
 330   mParent         = NULL;
 331   mPrev           = NULL;
 332   mNext           = NULL;
 333
 334   mSrc            = SrcBuffer;
 335   mSrcUpperLimit  = mSrc + SrcSize;
 336   mDst            = DstBuffer;
 337   mDstUpperLimit  = mDst + *DstSize;
 338
 339   PutDword (0L);
 340   PutDword (0L);
 341
 342   MakeCrcTable ();
 343
 344   mOrigSize             = mCompSize = 0;
 345   mCrc                  = INIT_CRC;
 346
 347   //
 348   // Compress it
 349   //
 350   Status = Encode ();
 351   if (EFI_ERROR (Status)) {
 352     return EFI_OUT_OF_RESOURCES;
 353   }
 354   //
 355   // Null terminate the compressed data
 356   //
 357   if (mDst < mDstUpperLimit) {
 358     *mDst++ = 0;
 359   }
 360   //
 361   // Fill in compressed size and original size
 362   //
 363   mDst = DstBuffer;
 364   PutDword (mCompSize + 1);
 365   PutDword (mOrigSize);
 366
 367   //
 368   // Return
 369   //
 370   if (mCompSize + 1 + 8 > *DstSize) {
 371     *DstSize = mCompSize + 1 + 8;
 372     return EFI_BUFFER_TOO_SMALL;
 373   } else {
 374     *DstSize = mCompSize + 1 + 8;
 375     return EFI_SUCCESS;
 376   }
 377
 378 }
 379
 380 STATIC
 381 VOID
 382 PutDword (
 383   IN UINT32 Data
 384   )
 385 /*++
 386
 387 Routine Description:
 388
 389   Put a dword to output stream
 390
 391 Arguments:
 392
 393   Data    - the dword to put
 394
 395 Returns: (VOID)
 396
 397 --*/
 398 {
 399   if (mDst < mDstUpperLimit) {
 400     *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
 401   }
 402
 403   if (mDst < mDstUpperLimit) {
 404     *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
 405   }
 406
 407   if (mDst < mDstUpperLimit) {
 408     *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
 409   }
 410
 411   if (mDst < mDstUpperLimit) {
 412     *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
 413   }
 414 }
 415
 416 STATIC
 417 EFI_STATUS
 418 AllocateMemory (
 419   VOID
 420   )
 421 /*++
 422
 423 Routine Description:
 424
 425   Allocate memory spaces for data structures used in compression process
 426
 427 Argements:
 428   VOID
 429
 430 Returns:
 431
 432   EFI_SUCCESS           - Memory is allocated successfully
 433   EFI_OUT_OF_RESOURCES  - Allocation fails
 434
 435 --*/
 436 {
 437   UINT32  Index;
 438
 439   mText = malloc (WNDSIZ * 2 + MAXMATCH);
 440   for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {
 441     mText[Index] = 0;
 442   }
 443
 444   mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
 445   mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
 446   mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
 447   mParent     = malloc (WNDSIZ * 2 * sizeof (*mParent));
 448   mPrev       = malloc (WNDSIZ * 2 * sizeof (*mPrev));
 449   mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));
 450
 451   mBufSiz     = BLKSIZ;
 452   mBuf        = malloc (mBufSiz);
 453   while (mBuf == NULL) {
 454     mBufSiz = (mBufSiz / 10U) * 9U;
 455     if (mBufSiz < 4 * 1024U) {
 456       return EFI_OUT_OF_RESOURCES;
 457     }
 458
 459     mBuf = malloc (mBufSiz);
 460   }
 461
 462   mBuf[0] = 0;
 463
 464   return EFI_SUCCESS;
 465 }
 466
 467 VOID
 468 FreeMemory (
 469   VOID
 470   )
 471 /*++
 472
 473 Routine Description:
 474
 475   Called when compression is completed to free memory previously allocated.
 476
 477 Arguments: (VOID)
 478
 479 Returns: (VOID)
 480
 481 --*/
 482 {
 483   if (mText != NULL) {
 484     free (mText);
 485   }
 486
 487   if (mLevel != NULL) {
 488     free (mLevel);
 489   }
 490
 491   if (mChildCount != NULL) {
 492     free (mChildCount);
 493   }
 494
 495   if (mPosition != NULL) {
 496     free (mPosition);
 497   }
 498
 499   if (mParent != NULL) {
 500     free (mParent);
 501   }
 502
 503   if (mPrev != NULL) {
 504     free (mPrev);
 505   }
 506
 507   if (mNext != NULL) {
 508     free (mNext);
 509   }
 510
 511   if (mBuf != NULL) {
 512     free (mBuf);
 513   }
 514
 515   return ;
 516 }
 517
 518 STATIC
 519 VOID
 520 InitSlide (
 521   VOID
 522   )
 523 /*++
 524
 525 Routine Description:
 526
 527   Initialize String Info Log data structures
 528
 529 Arguments: (VOID)
 530
 531 Returns: (VOID)
 532
 533 --*/
 534 {
 535   NODE  Index;
 536
 537   for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {
 538     mLevel[Index]     = 1;
 539     mPosition[Index]  = NIL;  /* sentinel */
 540   }
 541
 542   for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {
 543     mParent[Index] = NIL;
 544   }
 545
 546   mAvail = 1;
 547   for (Index = 1; Index < WNDSIZ - 1; Index++) {
 548     mNext[Index] = (NODE) (Index + 1);
 549   }
 550
 551   mNext[WNDSIZ - 1] = NIL;
 552   for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {
 553     mNext[Index] = NIL;
 554   }
 555 }
 556
 557 STATIC
 558 NODE
 559 Child (
 560   IN NODE  NodeQ,
 561   IN UINT8 CharC
 562   )
 563 /*++
 564
 565 Routine Description:
 566
 567   Find child node given the parent node and the edge character
 568
 569 Arguments:
 570
 571   NodeQ       - the parent node
 572   CharC       - the edge character
 573
 574 Returns:
 575
 576   The child node (NIL if not found)
 577
 578 --*/
 579 {
 580   NODE  NodeR;
 581
 582   NodeR = mNext[HASH (NodeQ, CharC)];
 583   //
 584   // sentinel
 585   //
 586   mParent[NIL] = NodeQ;
 587   while (mParent[NodeR] != NodeQ) {
 588     NodeR = mNext[NodeR];
 589   }
 590
 591   return NodeR;
 592 }
 593
 594 STATIC
 595 VOID
 596 MakeChild (
 597   IN NODE  Parent,
 598   IN UINT8 CharC,
 599   IN NODE  Child
 600   )
 601 /*++
 602
 603 Routine Description:
 604
 605   Create a new child for a given parent node.
 606
 607 Arguments:
 608
 609   Parent       - the parent node
 610   CharC   - the edge character
 611   Child       - the child node
 612
 613 Returns: (VOID)
 614
 615 --*/
 616 {
 617   NODE  Node1;
 618   NODE  Node2;
 619
 620   Node1           = (NODE) HASH (Parent, CharC);
 621   Node2           = mNext[Node1];
 622   mNext[Node1]    = Child;
 623   mNext[Child]    = Node2;
 624   mPrev[Node2]    = Child;
 625   mPrev[Child]    = Node1;
 626   mParent[Child]  = Parent;
 627   mChildCount[Parent]++;
 628 }
 629
 630 STATIC
 631 VOID
 632 Split (
 633   NODE Old
 634   )
 635 /*++
 636
 637 Routine Description:
 638
 639   Split a node.
 640
 641 Arguments:
 642
 643   Old     - the node to split
 644
 645 Returns: (VOID)
 646
 647 --*/
 648 {
 649   NODE  New;
 650   NODE  TempNode;
 651
 652   New               = mAvail;
 653   mAvail            = mNext[New];
 654   mChildCount[New]  = 0;
 655   TempNode          = mPrev[Old];
 656   mPrev[New]        = TempNode;
 657   mNext[TempNode]   = New;
 658   TempNode          = mNext[Old];
 659   mNext[New]        = TempNode;
 660   mPrev[TempNode]   = New;
 661   mParent[New]      = mParent[Old];
 662   mLevel[New]       = (UINT8) mMatchLen;
 663   mPosition[New]    = mPos;
 664   MakeChild (New, mText[mMatchPos + mMatchLen], Old);
 665   MakeChild (New, mText[mPos + mMatchLen], mPos);
 666 }
 667
 668 STATIC
 669 VOID
 670 InsertNode (
 671   VOID
 672   )
 673 /*++
 674
 675 Routine Description:
 676
 677   Insert string info for current position into the String Info Log
 678
 679 Arguments: (VOID)
 680
 681 Returns: (VOID)
 682
 683 --*/
 684 {
 685   NODE  NodeQ;
 686   NODE  NodeR;
 687   NODE  Index2;
 688   NODE  NodeT;
 689   UINT8 CharC;
 690   UINT8 *t1;
 691   UINT8 *t2;
 692
 693   if (mMatchLen >= 4) {
 694     //
 695     // We have just got a long match, the target tree
 696     // can be located by MatchPos + 1. Travese the tree
 697     // from bottom up to get to a proper starting point.
 698     // The usage of PERC_FLAG ensures proper node deletion
 699     // in DeleteNode() later.
 700     //
 701     mMatchLen--;
 702     NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);
 703     NodeQ = mParent[NodeR];
 704     while (NodeQ == NIL) {
 705       NodeR = mNext[NodeR];
 706       NodeQ = mParent[NodeR];
 707     }
 708
 709     while (mLevel[NodeQ] >= mMatchLen) {
 710       NodeR = NodeQ;
 711       NodeQ = mParent[NodeQ];
 712     }
 713
 714     NodeT = NodeQ;
 715     while (mPosition[NodeT] < 0) {
 716       mPosition[NodeT]  = mPos;
 717       NodeT             = mParent[NodeT];
 718     }
 719
 720     if (NodeT < WNDSIZ) {
 721       mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);
 722     }
 723   } else {
 724     //
 725     // Locate the target tree
 726     //
 727     NodeQ = (NODE) (mText[mPos] + WNDSIZ);
 728     CharC = mText[mPos + 1];
 729     NodeR = Child (NodeQ, CharC);
 730     if (NodeR == NIL) {
 731       MakeChild (NodeQ, CharC, mPos);
 732       mMatchLen = 1;
 733       return ;
 734     }
 735
 736     mMatchLen = 2;
 737   }
 738   //
 739   // Traverse down the tree to find a match.
 740   // Update Position value along the route.
 741   // Node split or creation is involved.
 742   //
 743   for (;;) {
 744     if (NodeR >= WNDSIZ) {
 745       Index2    = MAXMATCH;
 746       mMatchPos = NodeR;
 747     } else {
 748       Index2    = mLevel[NodeR];
 749       mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
 750     }
 751
 752     if (mMatchPos >= mPos) {
 753       mMatchPos -= WNDSIZ;
 754     }
 755
 756     t1  = &mText[mPos + mMatchLen];
 757     t2  = &mText[mMatchPos + mMatchLen];
 758     while (mMatchLen < Index2) {
 759       if (*t1 != *t2) {
 760         Split (NodeR);
 761         return ;
 762       }
 763
 764       mMatchLen++;
 765       t1++;
 766       t2++;
 767     }
 768
 769     if (mMatchLen >= MAXMATCH) {
 770       break;
 771     }
 772
 773     mPosition[NodeR]  = mPos;
 774     NodeQ             = NodeR;
 775     NodeR             = Child (NodeQ, *t1);
 776     if (NodeR == NIL) {
 777       MakeChild (NodeQ, *t1, mPos);
 778       return ;
 779     }
 780
 781     mMatchLen++;
 782   }
 783
 784   NodeT           = mPrev[NodeR];
 785   mPrev[mPos]     = NodeT;
 786   mNext[NodeT]    = mPos;
 787   NodeT           = mNext[NodeR];
 788   mNext[mPos]     = NodeT;
 789   mPrev[NodeT]    = mPos;
 790   mParent[mPos]   = NodeQ;
 791   mParent[NodeR]  = NIL;
 792
 793   //
 794   // Special usage of 'next'
 795   //
 796   mNext[NodeR] = mPos;
 797
 798 }
 799
 800 STATIC
 801 VOID
 802 DeleteNode (
 803   VOID
 804   )
 805 /*++
 806
 807 Routine Description:
 808
 809   Delete outdated string info. (The Usage of PERC_FLAG
 810   ensures a clean deletion)
 811
 812 Arguments: (VOID)
 813
 814 Returns: (VOID)
 815
 816 --*/
 817 {
 818   NODE  NodeQ;
 819   NODE  NodeR;
 820   NODE  NodeS;
 821   NODE  NodeT;
 822   NODE  NodeU;
 823
 824   if (mParent[mPos] == NIL) {
 825     return ;
 826   }
 827
 828   NodeR         = mPrev[mPos];
 829   NodeS         = mNext[mPos];
 830   mNext[NodeR]  = NodeS;
 831   mPrev[NodeS]  = NodeR;
 832   NodeR         = mParent[mPos];
 833   mParent[mPos] = NIL;
 834   if (NodeR >= WNDSIZ) {
 835     return ;
 836   }
 837
 838   mChildCount[NodeR]--;
 839   if (mChildCount[NodeR] > 1) {
 840     return ;
 841   }
 842
 843   NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
 844   if (NodeT >= mPos) {
 845     NodeT -= WNDSIZ;
 846   }
 847
 848   NodeS = NodeT;
 849   NodeQ = mParent[NodeR];
 850   NodeU = mPosition[NodeQ];
 851   while (NodeU & (UINT32) PERC_FLAG) {
 852     NodeU &= (UINT32)~PERC_FLAG;
 853     if (NodeU >= mPos) {
 854       NodeU -= WNDSIZ;
 855     }
 856
 857     if (NodeU > NodeS) {
 858       NodeS = NodeU;
 859     }
 860
 861     mPosition[NodeQ]  = (NODE) (NodeS | WNDSIZ);
 862     NodeQ             = mParent[NodeQ];
 863     NodeU             = mPosition[NodeQ];
 864   }
 865
 866   if (NodeQ < WNDSIZ) {
 867     if (NodeU >= mPos) {
 868       NodeU -= WNDSIZ;
 869     }
 870
 871     if (NodeU > NodeS) {
 872       NodeS = NodeU;
 873     }
 874
 875     mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);
 876   }
 877
 878   NodeS           = Child (NodeR, mText[NodeT + mLevel[NodeR]]);
 879   NodeT           = mPrev[NodeS];
 880   NodeU           = mNext[NodeS];
 881   mNext[NodeT]    = NodeU;
 882   mPrev[NodeU]    = NodeT;
 883   NodeT           = mPrev[NodeR];
 884   mNext[NodeT]    = NodeS;
 885   mPrev[NodeS]    = NodeT;
 886   NodeT           = mNext[NodeR];
 887   mPrev[NodeT]    = NodeS;
 888   mNext[NodeS]    = NodeT;
 889   mParent[NodeS]  = mParent[NodeR];
 890   mParent[NodeR]  = NIL;
 891   mNext[NodeR]    = mAvail;
 892   mAvail          = NodeR;
 893 }
 894
 895 STATIC
 896 VOID
 897 GetNextMatch (
 898   VOID
 899   )
 900 /*++
 901
 902 Routine Description:
 903
 904   Advance the current position (read in new data if needed).
 905   Delete outdated string info. Find a match string for current position.
 906
 907 Arguments: (VOID)
 908
 909 Returns: (VOID)
 910
 911 --*/
 912 {
 913   INT32 Number;
 914
 915   mRemainder--;
 916   mPos++;
 917   if (mPos == WNDSIZ * 2) {
 918     memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
 919     Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
 920     mRemainder += Number;
 921     mPos = WNDSIZ;
 922   }
 923
 924   DeleteNode ();
 925   InsertNode ();
 926 }
 927
 928 STATIC
 929 EFI_STATUS
 930 Encode (
 931   VOID
 932   )
 933 /*++
 934
 935 Routine Description:
 936
 937   The main controlling routine for compression process.
 938
 939 Arguments: (VOID)
 940
 941 Returns:
 942
 943   EFI_SUCCESS           - The compression is successful
 944   EFI_OUT_0F_RESOURCES  - Not enough memory for compression process
 945
 946 --*/
 947 {
 948   EFI_STATUS  Status;
 949   INT32       LastMatchLen;
 950   NODE        LastMatchPos;
 951
 952   Status = AllocateMemory ();
 953   if (EFI_ERROR (Status)) {
 954     FreeMemory ();
 955     return Status;
 956   }
 957
 958   InitSlide ();
 959
 960   HufEncodeStart ();
 961
 962   mRemainder  = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
 963
 964   mMatchLen   = 0;
 965   mPos        = WNDSIZ;
 966   InsertNode ();
 967   if (mMatchLen > mRemainder) {
 968     mMatchLen = mRemainder;
 969   }
 970
 971   while (mRemainder > 0) {
 972     LastMatchLen  = mMatchLen;
 973     LastMatchPos  = mMatchPos;
 974     GetNextMatch ();
 975     if (mMatchLen > mRemainder) {
 976       mMatchLen = mRemainder;
 977     }
 978
 979     if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
 980       //
 981       // Not enough benefits are gained by outputting a pointer,
 982       // so just output the original character
 983       //
 984       Output (mText[mPos - 1], 0);
 985
 986     } else {
 987
 988       if (LastMatchLen == THRESHOLD) {
 989         if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {
 990           Output (mText[mPos - 1], 0);
 991           continue;
 992         }
 993       }
 994       //
 995       // Outputting a pointer is beneficial enough, do it.
 996       //
 997       Output (
 998         LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
 999         (mPos - LastMatchPos - 2) & (WNDSIZ - 1)
1000         );
1001       LastMatchLen--;
1002       while (LastMatchLen > 0) {
1003         GetNextMatch ();
1004         LastMatchLen--;
1005       }
1006
1007       if (mMatchLen > mRemainder) {
1008         mMatchLen = mRemainder;
1009       }
1010     }
1011   }
1012
1013   HufEncodeEnd ();
1014   FreeMemory ();
1015   return EFI_SUCCESS;
1016 }
1017
1018 STATIC
1019 VOID
1020 CountTFreq (
1021   VOID
1022   )
1023 /*++
1024
1025 Routine Description:
1026
1027   Count the frequencies for the Extra Set
1028
1029 Arguments: (VOID)
1030
1031 Returns: (VOID)
1032
1033 --*/
1034 {
1035   INT32 Index;
1036   INT32 Index3;
1037   INT32 Number;
1038   INT32 Count;
1039
1040   for (Index = 0; Index < NT; Index++) {
1041     mTFreq[Index] = 0;
1042   }
1043
1044   Number = NC;
1045   while (Number > 0 && mCLen[Number - 1] == 0) {
1046     Number--;
1047   }
1048
1049   Index = 0;
1050   while (Index < Number) {
1051     Index3 = mCLen[Index++];
1052     if (Index3 == 0) {
1053       Count = 1;
1054       while (Index < Number && mCLen[Index] == 0) {
1055         Index++;
1056         Count++;
1057       }
1058
1059       if (Count <= 2) {
1060         mTFreq[0] = (UINT16) (mTFreq[0] + Count);
1061       } else if (Count <= 18) {
1062         mTFreq[1]++;
1063       } else if (Count == 19) {
1064         mTFreq[0]++;
1065         mTFreq[1]++;
1066       } else {
1067         mTFreq[2]++;
1068       }
1069     } else {
1070       mTFreq[Index3 + 2]++;
1071     }
1072   }
1073 }
1074
1075 STATIC
1076 VOID
1077 WritePTLen (
1078   IN INT32 Number,
1079   IN INT32 nbit,
1080   IN INT32 Special
1081   )
1082 /*++
1083
1084 Routine Description:
1085
1086   Outputs the code length array for the Extra Set or the Position Set.
1087
1088 Arguments:
1089
1090   Number       - the number of symbols
1091   nbit    - the number of bits needed to represent 'n'
1092   Special - the special symbol that needs to be take care of
1093
1094 Returns: (VOID)
1095
1096 --*/
1097 {
1098   INT32 Index;
1099   INT32 Index3;
1100
1101   while (Number > 0 && mPTLen[Number - 1] == 0) {
1102     Number--;
1103   }
1104
1105   PutBits (nbit, Number);
1106   Index = 0;
1107   while (Index < Number) {
1108     Index3 = mPTLen[Index++];
1109     if (Index3 <= 6) {
1110       PutBits (3, Index3);
1111     } else {
1112       PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);
1113     }
1114
1115     if (Index == Special) {
1116       while (Index < 6 && mPTLen[Index] == 0) {
1117         Index++;
1118       }
1119
1120       PutBits (2, (Index - 3) & 3);
1121     }
1122   }
1123 }
1124
1125 STATIC
1126 VOID
1127 WriteCLen (
1128   VOID
1129   )
1130 /*++
1131
1132 Routine Description:
1133
1134   Outputs the code length array for Char&Length Set
1135
1136 Arguments: (VOID)
1137
1138 Returns: (VOID)
1139
1140 --*/
1141 {
1142   INT32 Index;
1143   INT32 Index3;
1144   INT32 Number;
1145   INT32 Count;
1146
1147   Number = NC;
1148   while (Number > 0 && mCLen[Number - 1] == 0) {
1149     Number--;
1150   }
1151
1152   PutBits (CBIT, Number);
1153   Index = 0;
1154   while (Index < Number) {
1155     Index3 = mCLen[Index++];
1156     if (Index3 == 0) {
1157       Count = 1;
1158       while (Index < Number && mCLen[Index] == 0) {
1159         Index++;
1160         Count++;
1161       }
1162
1163       if (Count <= 2) {
1164         for (Index3 = 0; Index3 < Count; Index3++) {
1165           PutBits (mPTLen[0], mPTCode[0]);
1166         }
1167       } else if (Count <= 18) {
1168         PutBits (mPTLen[1], mPTCode[1]);
1169         PutBits (4, Count - 3);
1170       } else if (Count == 19) {
1171         PutBits (mPTLen[0], mPTCode[0]);
1172         PutBits (mPTLen[1], mPTCode[1]);
1173         PutBits (4, 15);
1174       } else {
1175         PutBits (mPTLen[2], mPTCode[2]);
1176         PutBits (CBIT, Count - 20);
1177       }
1178     } else {
1179       PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);
1180     }
1181   }
1182 }
1183
1184 STATIC
1185 VOID
1186 EncodeC (
1187   IN INT32 Value
1188   )
1189 {
1190   PutBits (mCLen[Value], mCCode[Value]);
1191 }
1192
1193 STATIC
1194 VOID
1195 EncodeP (
1196   IN UINT32 Value
1197   )
1198 {
1199   UINT32  Index;
1200   UINT32  NodeQ;
1201
1202   Index = 0;
1203   NodeQ = Value;
1204   while (NodeQ) {
1205     NodeQ >>= 1;
1206     Index++;
1207   }
1208
1209   PutBits (mPTLen[Index], mPTCode[Index]);
1210   if (Index > 1) {
1211     PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));
1212   }
1213 }
1214
1215 STATIC
1216 VOID
1217 SendBlock (
1218   VOID
1219   )
1220 /*++
1221
1222 Routine Description:
1223
1224   Huffman code the block and output it.
1225
1226 Arguments:
1227   (VOID)
1228
1229 Returns:
1230   (VOID)
1231
1232 --*/
1233 {
1234   UINT32  Index;
1235   UINT32  Index2;
1236   UINT32  Index3;
1237   UINT32  Flags;
1238   UINT32  Root;
1239   UINT32  Pos;
1240   UINT32  Size;
1241   Flags = 0;
1242
1243   Root  = MakeTree (NC, mCFreq, mCLen, mCCode);
1244   Size  = mCFreq[Root];
1245   PutBits (16, Size);
1246   if (Root >= NC) {
1247     CountTFreq ();
1248     Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
1249     if (Root >= NT) {
1250       WritePTLen (NT, TBIT, 3);
1251     } else {
1252       PutBits (TBIT, 0);
1253       PutBits (TBIT, Root);
1254     }
1255
1256     WriteCLen ();
1257   } else {
1258     PutBits (TBIT, 0);
1259     PutBits (TBIT, 0);
1260     PutBits (CBIT, 0);
1261     PutBits (CBIT, Root);
1262   }
1263
1264   Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
1265   if (Root >= NP) {
1266     WritePTLen (NP, PBIT, -1);
1267   } else {
1268     PutBits (PBIT, 0);
1269     PutBits (PBIT, Root);
1270   }
1271
1272   Pos = 0;
1273   for (Index = 0; Index < Size; Index++) {
1274     if (Index % UINT8_BIT == 0) {
1275       Flags = mBuf[Pos++];
1276     } else {
1277       Flags <<= 1;
1278     }
1279
1280     if (Flags & (1U << (UINT8_BIT - 1))) {
1281       EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));
1282       Index3 = mBuf[Pos++];
1283       for (Index2 = 0; Index2 < 3; Index2++) {
1284         Index3 <<= UINT8_BIT;
1285         Index3 += mBuf[Pos++];
1286       }
1287
1288       EncodeP (Index3);
1289     } else {
1290       EncodeC (mBuf[Pos++]);
1291     }
1292   }
1293
1294   for (Index = 0; Index < NC; Index++) {
1295     mCFreq[Index] = 0;
1296   }
1297
1298   for (Index = 0; Index < NP; Index++) {
1299     mPFreq[Index] = 0;
1300   }
1301 }
1302
1303 STATIC
1304 VOID
1305 Output (
1306   IN UINT32 CharC,
1307   IN UINT32 Pos
1308   )
1309 /*++
1310
1311 Routine Description:
1312
1313   Outputs an Original Character or a Pointer
1314
1315 Arguments:
1316
1317   CharC     - The original character or the 'String Length' element of a Pointer
1318   Pos     - The 'Position' field of a Pointer
1319
1320 Returns: (VOID)
1321
1322 --*/
1323 {
1324   STATIC UINT32 CPos;
1325
1326   if ((mOutputMask >>= 1) == 0) {
1327     mOutputMask = 1U << (UINT8_BIT - 1);
1328     //
1329     // Check the buffer overflow per outputing UINT8_BIT symbols
1330     // which is an Original Character or a Pointer. The biggest
1331     // symbol is a Pointer which occupies 5 bytes.
1332     //
1333     if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {
1334       SendBlock ();
1335       mOutputPos = 0;
1336     }
1337
1338     CPos        = mOutputPos++;
1339     mBuf[CPos]  = 0;
1340   }
1341
1342   mBuf[mOutputPos++] = (UINT8) CharC;
1343   mCFreq[CharC]++;
1344   if (CharC >= (1U << UINT8_BIT)) {
1345     mBuf[CPos] |= mOutputMask;
1346     mBuf[mOutputPos++]  = (UINT8) (Pos >> 24);
1347     mBuf[mOutputPos++]  = (UINT8) (Pos >> 16);
1348     mBuf[mOutputPos++]  = (UINT8) (Pos >> (UINT8_BIT));
1349     mBuf[mOutputPos++]  = (UINT8) Pos;
1350     CharC               = 0;
1351     while (Pos) {
1352       Pos >>= 1;
1353       CharC++;
1354     }
1355
1356     mPFreq[CharC]++;
1357   }
1358 }
1359
1360 STATIC
1361 VOID
1362 HufEncodeStart (
1363   VOID
1364   )
1365 {
1366   INT32 Index;
1367
1368   for (Index = 0; Index < NC; Index++) {
1369     mCFreq[Index] = 0;
1370   }
1371
1372   for (Index = 0; Index < NP; Index++) {
1373     mPFreq[Index] = 0;
1374   }
1375
1376   mOutputPos = mOutputMask = 0;
1377   InitPutBits ();
1378   return ;
1379 }
1380
1381 STATIC
1382 VOID
1383 HufEncodeEnd (
1384   VOID
1385   )
1386 {
1387   SendBlock ();
1388
1389   //
1390   // Flush remaining bits
1391   //
1392   PutBits (UINT8_BIT - 1, 0);
1393
1394   return ;
1395 }
1396
1397 STATIC
1398 VOID
1399 MakeCrcTable (
1400   VOID
1401   )
1402 {
1403   UINT32  Index;
1404   UINT32  Index2;
1405   UINT32  Temp;
1406
1407   for (Index = 0; Index <= UINT8_MAX; Index++) {
1408     Temp = Index;
1409     for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {
1410       if (Temp & 1) {
1411         Temp = (Temp >> 1) ^ CRCPOLY;
1412       } else {
1413         Temp >>= 1;
1414       }
1415     }
1416
1417     mCrcTable[Index] = (UINT16) Temp;
1418   }
1419 }
1420
1421 STATIC
1422 VOID
1423 PutBits (
1424   IN INT32  Number,
1425   IN UINT32 Value
1426   )
1427 /*++
1428
1429 Routine Description:
1430
1431   Outputs rightmost n bits of x
1432
1433 Arguments:
1434
1435   Number   - the rightmost n bits of the data is used
1436   x   - the data
1437
1438 Returns: (VOID)
1439
1440 --*/
1441 {
1442   UINT8 Temp;
1443
1444   while (Number >= mBitCount) {
1445     //
1446     // Number -= mBitCount should never equal to 32
1447     //
1448     Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));
1449     if (mDst < mDstUpperLimit) {
1450       *mDst++ = Temp;
1451     }
1452
1453     mCompSize++;
1454     mSubBitBuf  = 0;
1455     mBitCount   = UINT8_BIT;
1456   }
1457
1458   mSubBitBuf |= Value << (mBitCount -= Number);
1459 }
1460
1461 STATIC
1462 INT32
1463 FreadCrc (
1464   OUT UINT8 *Pointer,
1465   IN  INT32 Number
1466   )
1467 /*++
1468
1469 Routine Description:
1470
1471   Read in source data
1472
1473 Arguments:
1474
1475   Pointer   - the buffer to hold the data
1476   Number   - number of bytes to read
1477
1478 Returns:
1479
1480   number of bytes actually read
1481
1482 --*/
1483 {
1484   INT32 Index;
1485
1486   for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {
1487     *Pointer++ = *mSrc++;
1488   }
1489
1490   Number = Index;
1491
1492   Pointer -= Number;
1493   mOrigSize += Number;
1494   Index--;
1495   while (Index >= 0) {
1496     UPDATE_CRC (*Pointer++);
1497     Index--;
1498   }
1499
1500   return Number;
1501 }
1502
1503 STATIC
1504 VOID
1505 InitPutBits (
1506   VOID
1507   )
1508 {
1509   mBitCount   = UINT8_BIT;
1510   mSubBitBuf  = 0;
1511 }
1512
1513 STATIC
1514 VOID
1515 CountLen (
1516   IN INT32 Index
1517   )
1518 /*++
1519
1520 Routine Description:
1521
1522   Count the number of each code length for a Huffman tree.
1523
1524 Arguments:
1525
1526   Index   - the top node
1527
1528 Returns: (VOID)
1529
1530 --*/
1531 {
1532   STATIC INT32  Depth = 0;
1533
1534   if (Index < mN) {
1535     mLenCnt[(Depth < 16) ? Depth : 16]++;
1536   } else {
1537     Depth++;
1538     CountLen (mLeft[Index]);
1539     CountLen (mRight[Index]);
1540     Depth--;
1541   }
1542 }
1543
1544 STATIC
1545 VOID
1546 MakeLen (
1547   IN INT32 Root
1548   )
1549 /*++
1550
1551 Routine Description:
1552
1553   Create code length array for a Huffman tree
1554
1555 Arguments:
1556
1557   Root   - the root of the tree
1558
1559 Returns:
1560
1561   VOID
1562
1563 --*/
1564 {
1565   INT32   Index;
1566   INT32   Index3;
1567   UINT32  Cum;
1568
1569   for (Index = 0; Index <= 16; Index++) {
1570     mLenCnt[Index] = 0;
1571   }
1572
1573   CountLen (Root);
1574
1575   //
1576   // Adjust the length count array so that
1577   // no code will be generated longer than its designated length
1578   //
1579   Cum = 0;
1580   for (Index = 16; Index > 0; Index--) {
1581     Cum += mLenCnt[Index] << (16 - Index);
1582   }
1583
1584   while (Cum != (1U << 16)) {
1585     mLenCnt[16]--;
1586     for (Index = 15; Index > 0; Index--) {
1587       if (mLenCnt[Index] != 0) {
1588         mLenCnt[Index]--;
1589         mLenCnt[Index + 1] += 2;
1590         break;
1591       }
1592     }
1593
1594     Cum--;
1595   }
1596
1597   for (Index = 16; Index > 0; Index--) {
1598     Index3 = mLenCnt[Index];
1599     Index3--;
1600     while (Index3 >= 0) {
1601       mLen[*mSortPtr++] = (UINT8) Index;
1602       Index3--;
1603     }
1604   }
1605 }
1606
1607 STATIC
1608 VOID
1609 DownHeap (
1610   IN INT32 Index
1611   )
1612 {
1613   INT32 Index2;
1614   INT32 Index3;
1615
1616   //
1617   // priority queue: send Index-th entry down heap
1618   //
1619   Index3  = mHeap[Index];
1620   Index2  = 2 * Index;
1621   while (Index2 <= mHeapSize) {
1622     if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {
1623       Index2++;
1624     }
1625
1626     if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {
1627       break;
1628     }
1629
1630     mHeap[Index]  = mHeap[Index2];
1631     Index         = Index2;
1632     Index2        = 2 * Index;
1633   }
1634
1635   mHeap[Index] = (INT16) Index3;
1636 }
1637
1638 STATIC
1639 VOID
1640 MakeCode (
1641   IN  INT32       Number,
1642   IN  UINT8 Len[  ],
1643   OUT UINT16 Code[]
1644   )
1645 /*++
1646
1647 Routine Description:
1648
1649   Assign code to each symbol based on the code length array
1650
1651 Arguments:
1652
1653   Number     - number of symbols
1654   Len   - the code length array
1655   Code  - stores codes for each symbol
1656
1657 Returns: (VOID)
1658
1659 --*/
1660 {
1661   INT32   Index;
1662   UINT16  Start[18];
1663
1664   Start[1] = 0;
1665   for (Index = 1; Index <= 16; Index++) {
1666     Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);
1667   }
1668
1669   for (Index = 0; Index < Number; Index++) {
1670     Code[Index] = Start[Len[Index]]++;
1671   }
1672 }
1673
1674 STATIC
1675 INT32
1676 MakeTree (
1677   IN  INT32            NParm,
1678   IN  UINT16  FreqParm[],
1679   OUT UINT8   LenParm[ ],
1680   OUT UINT16  CodeParm[]
1681   )
1682 /*++
1683
1684 Routine Description:
1685
1686   Generates Huffman codes given a frequency distribution of symbols
1687
1688 Arguments:
1689
1690   NParm    - number of symbols
1691   FreqParm - frequency of each symbol
1692   LenParm  - code length for each symbol
1693   CodeParm - code for each symbol
1694
1695 Returns:
1696
1697   Root of the Huffman tree.
1698
1699 --*/
1700 {
1701   INT32 Index;
1702   INT32 Index2;
1703   INT32 Index3;
1704   INT32 Avail;
1705
1706   //
1707   // make tree, calculate len[], return root
1708   //
1709   mN        = NParm;
1710   mFreq     = FreqParm;
1711   mLen      = LenParm;
1712   Avail     = mN;
1713   mHeapSize = 0;
1714   mHeap[1]  = 0;
1715   for (Index = 0; Index < mN; Index++) {
1716     mLen[Index] = 0;
1717     if (mFreq[Index]) {
1718       mHeapSize++;
1719       mHeap[mHeapSize] = (INT16) Index;
1720     }
1721   }
1722
1723   if (mHeapSize < 2) {
1724     CodeParm[mHeap[1]] = 0;
1725     return mHeap[1];
1726   }
1727
1728   for (Index = mHeapSize / 2; Index >= 1; Index--) {
1729     //
1730     // make priority queue
1731     //
1732     DownHeap (Index);
1733   }
1734
1735   mSortPtr = CodeParm;
1736   do {
1737     Index = mHeap[1];
1738     if (Index < mN) {
1739       *mSortPtr++ = (UINT16) Index;
1740     }
1741
1742     mHeap[1] = mHeap[mHeapSize--];
1743     DownHeap (1);
1744     Index2 = mHeap[1];
1745     if (Index2 < mN) {
1746       *mSortPtr++ = (UINT16) Index2;
1747     }
1748
1749     Index3        = Avail++;
1750     mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);
1751     mHeap[1]      = (INT16) Index3;
1752     DownHeap (1);
1753     mLeft[Index3]   = (UINT16) Index;
1754     mRight[Index3]  = (UINT16) Index2;
1755   } while (mHeapSize > 1);
1756
1757   mSortPtr = CodeParm;
1758   MakeLen (Index3);
1759   MakeCode (NParm, LenParm, CodeParm);
1760
1761   //
1762   // return root
1763   //
1764   return Index3;
1765 }