Tools/CCode/Source/Common/TianoCompress.c

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