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