BaseTools/Source/C/Common/EfiCompress.c

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