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