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 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   if (mText == NULL) {
 412     return EFI_OUT_OF_RESOURCES;
 413   }
 414   for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
 415     mText[i] = 0;
 416   }
 417
 418   mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
 419   mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
 420   mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
 421   mParent     = malloc (WNDSIZ * 2 * sizeof(*mParent));
 422   mPrev       = malloc (WNDSIZ * 2 * sizeof(*mPrev));
 423   mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
 424   if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
 425     mParent == NULL || mPrev == NULL || mNext == NULL) {
 426     return EFI_OUT_OF_RESOURCES;
 427   }
 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