BaseTools/Source/C/Common/TianoCompress.c

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