BaseTools/Source/C/Common/TianoCompress.c

   1 /** @file
   2 Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
   3 coding. LZ77 transforms the source data into a sequence of Original Characters
   4 and Pointers to repeated strings. This sequence is further divided into Blocks
   5 and Huffman codings are applied to each Block.
   6
   7 Copyright (c) 2006 - 2014, Intel Corporation. All rights reserved.<BR>
   8 This program and the accompanying materials
   9 are licensed and made available under the terms and conditions of the BSD License
  10 which accompanies this distribution.  The full text of the license may be found at
  11 http://opensource.org/licenses/bsd-license.php
  12
  13 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  14 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  15
  16 **/
  17
  18 #include "Compress.h"
  19
  20 //
  21 // Macro Definitions
  22 //
  23 #undef  UINT8_MAX
  24 typedef INT32 NODE;
  25 #define UINT8_MAX     0xff
  26 #define UINT8_BIT     8
  27 #define THRESHOLD     3
  28 #define INIT_CRC      0
  29 #define WNDBIT        19
  30 #define WNDSIZ        (1U << WNDBIT)
  31 #define MAXMATCH      256
  32 #define BLKSIZ        (1U << 14)  // 16 * 1024U
  33 #define PERC_FLAG     0x80000000U
  34 #define CODE_BIT      16
  35 #define NIL           0
  36 #define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
  37 #define HASH(p, c)    ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
  38 #define CRCPOLY       0xA001
  39 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
  40
  41 //
  42 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
  43 //
  44 #define NC    (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
  45 #define CBIT  9
  46 #define NP    (WNDBIT + 1)
  47 #define PBIT  5
  48 #define NT    (CODE_BIT + 3)
  49 #define TBIT  5
  50 #if NT > NP
  51 #define NPT NT
  52 #else
  53 #define NPT NP
  54 #endif
  55 //
  56 // Function Prototypes
  57 //
  58
  59 STATIC
  60 VOID
  61 PutDword(
  62   IN UINT32 Data
  63   );
  64
  65 STATIC
  66 EFI_STATUS
  67 AllocateMemory (
  68   VOID
  69   );
  70
  71 STATIC
  72 VOID
  73 FreeMemory (
  74   VOID
  75   );
  76
  77 STATIC
  78 VOID
  79 InitSlide (
  80   VOID
  81   );
  82
  83 STATIC
  84 NODE
  85 Child (
  86   IN NODE   NodeQ,
  87   IN UINT8  CharC
  88   );
  89
  90 STATIC
  91 VOID
  92 MakeChild (
  93   IN NODE  NodeQ,
  94   IN UINT8 CharC,
  95   IN NODE  NodeR
  96   );
  97
  98 STATIC
  99 VOID
 100 Split (
 101   IN NODE Old
 102   );
 103
 104 STATIC
 105 VOID
 106 InsertNode (
 107   VOID
 108   );
 109
 110 STATIC
 111 VOID
 112 DeleteNode (
 113   VOID
 114   );
 115
 116 STATIC
 117 VOID
 118 GetNextMatch (
 119   VOID
 120   );
 121
 122 STATIC
 123 EFI_STATUS
 124 Encode (
 125   VOID
 126   );
 127
 128 STATIC
 129 VOID
 130 CountTFreq (
 131   VOID
 132   );
 133
 134 STATIC
 135 VOID
 136 WritePTLen (
 137   IN INT32 Number,
 138   IN INT32 nbit,
 139   IN INT32 Special
 140   );
 141
 142 STATIC
 143 VOID
 144 WriteCLen (
 145   VOID
 146   );
 147
 148 STATIC
 149 VOID
 150 EncodeC (
 151   IN INT32 Value
 152   );
 153
 154 STATIC
 155 VOID
 156 EncodeP (
 157   IN UINT32 Value
 158   );
 159
 160 STATIC
 161 VOID
 162 SendBlock (
 163   VOID
 164   );
 165
 166 STATIC
 167 VOID
 168 Output (
 169   IN UINT32 c,
 170   IN UINT32 p
 171   );
 172
 173 STATIC
 174 VOID
 175 HufEncodeStart (
 176   VOID
 177   );
 178
 179 STATIC
 180 VOID
 181 HufEncodeEnd (
 182   VOID
 183   );
 184
 185 STATIC
 186 VOID
 187 MakeCrcTable (
 188   VOID
 189   );
 190
 191 STATIC
 192 VOID
 193 PutBits (
 194   IN INT32  Number,
 195   IN UINT32 Value
 196   );
 197
 198 STATIC
 199 INT32
 200 FreadCrc (
 201   OUT UINT8 *Pointer,
 202   IN  INT32 Number
 203   );
 204
 205 STATIC
 206 VOID
 207 InitPutBits (
 208   VOID
 209   );
 210
 211 STATIC
 212 VOID
 213 CountLen (
 214   IN INT32 Index
 215   );
 216
 217 STATIC
 218 VOID
 219 MakeLen (
 220   IN INT32 Root
 221   );
 222
 223 STATIC
 224 VOID
 225 DownHeap (
 226   IN INT32 Index
 227   );
 228
 229 STATIC
 230 VOID
 231 MakeCode (
 232   IN  INT32       Number,
 233   IN  UINT8 Len[  ],
 234   OUT UINT16 Code[]
 235   );
 236
 237 STATIC
 238 INT32
 239 MakeTree (
 240   IN  INT32            NParm,
 241   IN  UINT16  FreqParm[],
 242   OUT UINT8   LenParm[ ],
 243   OUT UINT16  CodeParm[]
 244   );
 245
 246 //
 247 //  Global Variables
 248 //
 249 STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
 250
 251 STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
 252 STATIC INT16  mHeap[NC + 1];
 253 STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
 254 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
 255 STATIC UINT32 mCompSize, mOrigSize;
 256
 257 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
 258   mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
 259
 260 STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
 261
 262 //
 263 // functions
 264 //
 265 EFI_STATUS
 266 TianoCompress (
 267   IN      UINT8   *SrcBuffer,
 268   IN      UINT32  SrcSize,
 269   IN      UINT8   *DstBuffer,
 270   IN OUT  UINT32  *DstSize
 271   )
 272 /*++
 273
 274 Routine Description:
 275
 276   The internal implementation of [Efi/Tiano]Compress().
 277
 278 Arguments:
 279
 280   SrcBuffer   - The buffer storing the source data
 281   SrcSize     - The size of source data
 282   DstBuffer   - The buffer to store the compressed data
 283   DstSize     - On input, the size of DstBuffer; On output,
 284                 the size of the actual compressed data.
 285   Version     - The version of de/compression algorithm.
 286                 Version 1 for UEFI 2.0 de/compression algorithm.
 287                 Version 2 for Tiano de/compression algorithm.
 288
 289 Returns:
 290
 291   EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,
 292                 DstSize contains the size needed.
 293   EFI_SUCCESS           - Compression is successful.
 294   EFI_OUT_OF_RESOURCES  - No resource to complete function.
 295   EFI_INVALID_PARAMETER - Parameter supplied is wrong.
 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 }