EdkCompatibilityPkg/Sample/Tools/Source/Common/EfiCompress.c

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