Tools/Source/TianoTools/Common/EfiCompress.c

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