ShellPkg/Library/UefiShellDebug1CommandsLib/Compress.c

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