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