Source/C/TianoCompress/TianoCompress.c

   1 /*++\r
   2 \r
   3 Copyright (c) 2007, Intel Corporation                                              \r
   4 All rights reserved. This program and the accompanying materials                          \r
   5 are licensed and made available under the terms and conditions of the BSD License         \r
   6 which accompanies this distribution.  The full text of the license may be found at        \r
   7 http://opensource.org/licenses/bsd-license.php                                            \r
   8                                                                                           \r
   9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,                     \r
  10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.             \r
  11 \r
  12 Module Name:\r
  13 \r
  14   TianoCompress.c\r
  15 \r
  16 Abstract:\r
  17 \r
  18   Compression routine. The compression algorithm is a mixture of\r
  19   LZ77 and Huffman coding. LZ77 transforms the source data into a\r
  20   sequence of Original Characters and Pointers to repeated strings.\r
  21   This sequence is further divided into Blocks and Huffman codings\r
  22   are applied to each Block.\r
  23 \r
  24 --*/\r
  25 \r
  26 #include "Compress.h"\r
  27 #include "TianoCompress.h"\r
  28 #include <stdio.h>\r
  29 #include "assert.h"\r
  30 \r
  31 //\r
  32 // Macro Definitions\r
  33 //\r
  34 static BOOLEAN VerboseMode = FALSE;\r
  35 static BOOLEAN QuietMode = FALSE;\r
  36 #define UINT8_MAX     0xff\r
  37 #define UINT8_BIT     8\r
  38 #define THRESHOLD     3\r
  39 #define INIT_CRC      0\r
  40 #define WNDBIT        19\r
  41 #define WNDSIZ        (1U << WNDBIT)\r
  42 #define MAXMATCH      256\r
  43 #define BLKSIZ        (1U << 14)  // 16 * 1024U\r
  44 #define PERC_FLAG     0x80000000U\r
  45 #define CODE_BIT      16\r
  46 #define NIL           0\r
  47 #define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
  48 #define HASH(p, c)    ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)\r
  49 #define CRCPOLY       0xA001\r
  50 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)\r
  51 \r
  52 //\r
  53 // C: the Char&Len Set; P: the Position Set; T: the exTra Set\r
  54 //\r
  55 //#define NC    (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)\r
  56 #define CBIT  9\r
  57 #define NP    (WNDBIT + 1)\r
  58 #define PBIT  5\r
  59 //#define NT    (CODE_BIT + 3)\r
  60 //#define TBIT  5\r
  61 //#if NT > NP\r
  62 //#define NPT NT\r
  63 //#else\r
  64 //#define NPT NP\r
  65 //#endif\r
  66 \r
  67 //\r
  68 //  Global Variables\r
  69 //\r
  70 STATIC BOOLEAN ENCODE = FALSE;\r
  71 STATIC BOOLEAN DECODE = FALSE;\r
  72 STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
  73 STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;\r
  74 STATIC INT16  mHeap[NC + 1];\r
  75 STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;\r
  76 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;\r
  77 STATIC UINT32 mCompSize, mOrigSize;\r
  78 \r
  79 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],\r
  80   mCFreq[2 * NC - 1], mCTable[4096], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];\r
  81 \r
  82 STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;\r
  83 \r
  84 static  UINTN      DebugLevel;\r
  85 static  BOOLEAN    DebugMode;\r
  86 //\r
  87 // functions\r
  88 //\r
  89 EFI_STATUS\r
  90 TianoCompress (\r
  91   IN      UINT8   *SrcBuffer,\r
  92   IN      UINT32  SrcSize,\r
  93   IN      UINT8   *DstBuffer,\r
  94   IN OUT  UINT32  *DstSize\r
  95   )\r
  96 /*++\r
  97 \r
  98 Routine Description:\r
  99 \r
 100   The internal implementation of [Efi/Tiano]Compress().\r
 101 \r
 102 Arguments:\r
 103 \r
 104   SrcBuffer   - The buffer storing the source data\r
 105   SrcSize     - The size of source data\r
 106   DstBuffer   - The buffer to store the compressed data\r
 107   \r
 108   Version     - The version of de/compression algorithm.\r
 109                 Version 1 for EFI 1.1 de/compression algorithm.\r
 110                 Version 2 for Tiano de/compression algorithm.\r
 111 \r
 112 Returns:\r
 113 \r
 114   EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,\r
 115                 DstSize contains the size needed.\r
 116   EFI_SUCCESS           - Compression is successful.\r
 117   EFI_OUT_OF_RESOURCES  - No resource to complete function.\r
 118   EFI_INVALID_PARAMETER - Parameter supplied is wrong.\r
 119 \r
 120 --*/\r
 121 {\r
 122   EFI_STATUS  Status;\r
 123 \r
 124   //\r
 125   // Initializations\r
 126   //\r
 127   mBufSiz         = 0;\r
 128   mBuf            = NULL;\r
 129   mText           = NULL;\r
 130   mLevel          = NULL;\r
 131   mChildCount     = NULL;\r
 132   mPosition       = NULL;\r
 133   mParent         = NULL;\r
 134   mPrev           = NULL;\r
 135   mNext           = NULL;\r
 136 \r
 137 \r
 138   mSrc            = SrcBuffer;\r
 139   mSrcUpperLimit  = mSrc + SrcSize;\r
 140   mDst            = DstBuffer;\r
 141   mDstUpperLimit  = mDst +*DstSize;\r
 142     \r
 143   PutDword (0L);\r
 144   PutDword (0L);\r
 145   \r
 146   MakeCrcTable ();\r
 147   \r
 148   mOrigSize             = mCompSize = 0;\r
 149   mCrc                  = INIT_CRC;\r
 150 \r
 151   //\r
 152   // Compress it\r
 153   //\r
 154   Status = Encode ();\r
 155   if (EFI_ERROR (Status)) {\r
 156     return EFI_OUT_OF_RESOURCES;\r
 157   }\r
 158   \r
 159   //\r
 160   // Null terminate the compressed data\r
 161   //\r
 162 \r
 163   if (mDst < mDstUpperLimit) {\r
 164     *mDst++ = 0;\r
 165   }\r
 166 \r
 167   //\r
 168   // Fill in compressed size and original size\r
 169   //\r
 170   mDst = DstBuffer; \r
 171  \r
 172   PutDword (mCompSize + 1);\r
 173   PutDword (mOrigSize);\r
 174   //\r
 175   // Return\r
 176   //\r
 177 \r
 178   if (mCompSize + 1 + 8 > *DstSize) {\r
 179     *DstSize = mCompSize + 1 + 8;    \r
 180        return EFI_BUFFER_TOO_SMALL;\r
 181     } else {\r
 182     *DstSize = mCompSize + 1 + 8;   \r
 183       return EFI_SUCCESS;\r
 184    }\r
 185   return EFI_SUCCESS;\r
 186 }\r
 187 \r
 188 STATIC\r
 189 VOID\r
 190 PutDword (\r
 191   IN UINT32 Data\r
 192   )\r
 193 /*++\r
 194 \r
 195 Routine Description:\r
 196 \r
 197   Put a dword to output stream\r
 198   \r
 199 Arguments:\r
 200 \r
 201   Data    - the dword to put\r
 202   \r
 203 Returns: (VOID)\r
 204   \r
 205 --*/\r
 206 {\r
 207   if (mDst < mDstUpperLimit) {\r
 208     *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);\r
 209   }\r
 210 \r
 211   if (mDst < mDstUpperLimit) {\r
 212     *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);\r
 213   }\r
 214 \r
 215   if (mDst < mDstUpperLimit) {\r
 216     *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);\r
 217   }\r
 218 \r
 219   if (mDst < mDstUpperLimit) {\r
 220     *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);\r
 221   }\r
 222 }\r
 223 \r
 224 STATIC\r
 225 EFI_STATUS\r
 226 AllocateMemory (\r
 227   VOID\r
 228   )\r
 229 /*++\r
 230 \r
 231 Routine Description:\r
 232 \r
 233   Allocate memory spaces for data structures used in compression process\r
 234   \r
 235 Argements: \r
 236   VOID\r
 237 \r
 238 Returns:\r
 239 \r
 240   EFI_SUCCESS           - Memory is allocated successfully\r
 241   EFI_OUT_OF_RESOURCES  - Allocation fails\r
 242 \r
 243 --*/\r
 244 {\r
 245   UINT32  Index;\r
 246 \r
 247   mText = malloc (WNDSIZ * 2 + MAXMATCH);\r
 248   for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {\r
 249     mText[Index] = 0;\r
 250   }\r
 251 \r
 252   mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));\r
 253   mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));\r
 254   mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));\r
 255   mParent     = malloc (WNDSIZ * 2 * sizeof (*mParent));\r
 256   mPrev       = malloc (WNDSIZ * 2 * sizeof (*mPrev));\r
 257   mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));\r
 258 \r
 259   mBufSiz     = BLKSIZ;\r
 260   mBuf        = malloc (mBufSiz);\r
 261   while (mBuf == NULL) {\r
 262     mBufSiz = (mBufSiz / 10U) * 9U;\r
 263     if (mBufSiz < 4 * 1024U) {\r
 264       return EFI_OUT_OF_RESOURCES;\r
 265     }\r
 266 \r
 267     mBuf = malloc (mBufSiz);\r
 268   }\r
 269 \r
 270   mBuf[0] = 0;\r
 271 \r
 272   return EFI_SUCCESS;\r
 273 }\r
 274 \r
 275 VOID\r
 276 FreeMemory (\r
 277   VOID\r
 278   )\r
 279 /*++\r
 280 \r
 281 Routine Description:\r
 282 \r
 283   Called when compression is completed to free memory previously allocated.\r
 284   \r
 285 Arguments: (VOID)\r
 286 \r
 287 Returns: (VOID)\r
 288 \r
 289 --*/\r
 290 {\r
 291   if (mText != NULL) {\r
 292     free (mText);\r
 293   }\r
 294 \r
 295   if (mLevel != NULL) {\r
 296     free (mLevel);\r
 297   }\r
 298 \r
 299   if (mChildCount != NULL) {\r
 300     free (mChildCount);\r
 301   }\r
 302 \r
 303   if (mPosition != NULL) {\r
 304     free (mPosition);\r
 305   }\r
 306 \r
 307   if (mParent != NULL) {\r
 308     free (mParent);\r
 309   }\r
 310 \r
 311   if (mPrev != NULL) {\r
 312     free (mPrev);\r
 313   }\r
 314 \r
 315   if (mNext != NULL) {\r
 316     free (mNext);\r
 317   }\r
 318 \r
 319   if (mBuf != NULL) {\r
 320     free (mBuf);\r
 321   }\r
 322 \r
 323   return ;\r
 324 }\r
 325 \r
 326 STATIC\r
 327 VOID\r
 328 InitSlide (\r
 329   VOID\r
 330   )\r
 331 /*++\r
 332 \r
 333 Routine Description:\r
 334 \r
 335   Initialize String Info Log data structures\r
 336   \r
 337 Arguments: (VOID)\r
 338 \r
 339 Returns: (VOID)\r
 340 \r
 341 --*/\r
 342 {\r
 343   NODE  Index;\r
 344 \r
 345   for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {\r
 346     mLevel[Index]     = 1;\r
 347     mPosition[Index]  = NIL;  // sentinel\r
 348   }\r
 349 \r
 350   for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {\r
 351     mParent[Index] = NIL;\r
 352   }\r
 353 \r
 354   mAvail = 1;\r
 355   for (Index = 1; Index < WNDSIZ - 1; Index++) {\r
 356     mNext[Index] = (NODE) (Index + 1);\r
 357   }\r
 358 \r
 359   mNext[WNDSIZ - 1] = NIL;\r
 360   for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {\r
 361     mNext[Index] = NIL;\r
 362   }\r
 363 }\r
 364 \r
 365 STATIC\r
 366 NODE\r
 367 Child (\r
 368   IN NODE  NodeQ,\r
 369   IN UINT8 CharC\r
 370   )\r
 371 /*++\r
 372 \r
 373 Routine Description:\r
 374 \r
 375   Find child node given the parent node and the edge character\r
 376   \r
 377 Arguments:\r
 378 \r
 379   NodeQ       - the parent node\r
 380   CharC       - the edge character\r
 381   \r
 382 Returns:\r
 383 \r
 384   The child node (NIL if not found)  \r
 385   \r
 386 --*/\r
 387 {\r
 388   NODE  NodeR;\r
 389 \r
 390   NodeR = mNext[HASH (NodeQ, CharC)];\r
 391   //\r
 392   // sentinel\r
 393   //\r
 394   mParent[NIL] = NodeQ;\r
 395   while (mParent[NodeR] != NodeQ) {\r
 396     NodeR = mNext[NodeR];\r
 397   }\r
 398 \r
 399   return NodeR;\r
 400 }\r
 401 \r
 402 STATIC\r
 403 VOID\r
 404 MakeChild (\r
 405   IN NODE  Parent,\r
 406   IN UINT8 CharC,\r
 407   IN NODE  Child\r
 408   )\r
 409 /*++\r
 410 \r
 411 Routine Description:\r
 412 \r
 413   Create a new child for a given parent node.\r
 414   \r
 415 Arguments:\r
 416 \r
 417   Parent       - the parent node\r
 418   CharC   - the edge character\r
 419   Child       - the child node\r
 420   \r
 421 Returns: (VOID)\r
 422 \r
 423 --*/\r
 424 {\r
 425   NODE  Node1;\r
 426   NODE  Node2;\r
 427 \r
 428   Node1           = (NODE) HASH (Parent, CharC);\r
 429   Node2           = mNext[Node1];\r
 430   mNext[Node1]    = Child;\r
 431   mNext[Child]    = Node2;\r
 432   mPrev[Node2]    = Child;\r
 433   mPrev[Child]    = Node1;\r
 434   mParent[Child]  = Parent;\r
 435   mChildCount[Parent]++;\r
 436 }\r
 437 \r
 438 STATIC\r
 439 VOID\r
 440 Split (\r
 441   NODE Old\r
 442   )\r
 443 /*++\r
 444 \r
 445 Routine Description:\r
 446 \r
 447   Split a node.\r
 448   \r
 449 Arguments:\r
 450 \r
 451   Old     - the node to split\r
 452   \r
 453 Returns: (VOID)\r
 454 \r
 455 --*/\r
 456 {\r
 457   NODE  New;\r
 458   NODE  TempNode;\r
 459 \r
 460   New               = mAvail;\r
 461   mAvail            = mNext[New];\r
 462   mChildCount[New]  = 0;\r
 463   TempNode          = mPrev[Old];\r
 464   mPrev[New]        = TempNode;\r
 465   mNext[TempNode]   = New;\r
 466   TempNode          = mNext[Old];\r
 467   mNext[New]        = TempNode;\r
 468   mPrev[TempNode]   = New;\r
 469   mParent[New]      = mParent[Old];\r
 470   mLevel[New]       = (UINT8) mMatchLen;\r
 471   mPosition[New]    = mPos;\r
 472   MakeChild (New, mText[mMatchPos + mMatchLen], Old);\r
 473   MakeChild (New, mText[mPos + mMatchLen], mPos);\r
 474 }\r
 475 \r
 476 STATIC\r
 477 VOID\r
 478 InsertNode (\r
 479   VOID\r
 480   )\r
 481 /*++\r
 482 \r
 483 Routine Description:\r
 484 \r
 485   Insert string info for current position into the String Info Log\r
 486   \r
 487 Arguments: (VOID)\r
 488 \r
 489 Returns: (VOID)\r
 490 \r
 491 --*/\r
 492 {\r
 493   NODE  NodeQ;\r
 494   NODE  NodeR;\r
 495   NODE  Index2;\r
 496   NODE  NodeT;\r
 497   UINT8 CharC;\r
 498   UINT8 *t1;\r
 499   UINT8 *t2;\r
 500 \r
 501   if (mMatchLen >= 4) {\r
 502     //\r
 503     // We have just got a long match, the target tree\r
 504     // can be located by MatchPos + 1. Travese the tree\r
 505     // from bottom up to get to a proper starting point.\r
 506     // The usage of PERC_FLAG ensures proper node deletion\r
 507     // in DeleteNode() later.\r
 508     //\r
 509     mMatchLen--;\r
 510     NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);\r
 511     NodeQ = mParent[NodeR];\r
 512     while (NodeQ == NIL) {\r
 513       NodeR = mNext[NodeR];\r
 514       NodeQ = mParent[NodeR];\r
 515     }\r
 516 \r
 517     while (mLevel[NodeQ] >= mMatchLen) {\r
 518       NodeR = NodeQ;\r
 519       NodeQ = mParent[NodeQ];\r
 520     }\r
 521 \r
 522     NodeT = NodeQ;\r
 523     while (mPosition[NodeT] < 0) {\r
 524       mPosition[NodeT]  = mPos;\r
 525       NodeT             = mParent[NodeT];\r
 526     }\r
 527 \r
 528     if (NodeT < WNDSIZ) {\r
 529       mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);\r
 530     }\r
 531   } else {\r
 532     //\r
 533     // Locate the target tree\r
 534     //\r
 535     NodeQ = (NODE) (mText[mPos] + WNDSIZ);\r
 536     CharC = mText[mPos + 1];\r
 537     NodeR = Child (NodeQ, CharC);\r
 538     if (NodeR == NIL) {\r
 539       MakeChild (NodeQ, CharC, mPos);\r
 540       mMatchLen = 1;\r
 541       return ;\r
 542     }\r
 543 \r
 544     mMatchLen = 2;\r
 545   }\r
 546   //\r
 547   // Traverse down the tree to find a match.\r
 548   // Update Position value along the route.\r
 549   // Node split or creation is involved.\r
 550   //\r
 551   for (;;) {\r
 552     if (NodeR >= WNDSIZ) {\r
 553       Index2    = MAXMATCH;\r
 554       mMatchPos = NodeR;\r
 555     } else {\r
 556       Index2    = mLevel[NodeR];\r
 557       mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);\r
 558     }\r
 559 \r
 560     if (mMatchPos >= mPos) {\r
 561       mMatchPos -= WNDSIZ;\r
 562     }\r
 563 \r
 564     t1  = &mText[mPos + mMatchLen];\r
 565     t2  = &mText[mMatchPos + mMatchLen];\r
 566     while (mMatchLen < Index2) {\r
 567       if (*t1 != *t2) {\r
 568         Split (NodeR);\r
 569         return ;\r
 570       }\r
 571 \r
 572       mMatchLen++;\r
 573       t1++;\r
 574       t2++;\r
 575     }\r
 576 \r
 577     if (mMatchLen >= MAXMATCH) {\r
 578       break;\r
 579     }\r
 580 \r
 581     mPosition[NodeR]  = mPos;\r
 582     NodeQ             = NodeR;\r
 583     NodeR             = Child (NodeQ, *t1);\r
 584     if (NodeR == NIL) {\r
 585       MakeChild (NodeQ, *t1, mPos);\r
 586       return ;\r
 587     }\r
 588 \r
 589     mMatchLen++;\r
 590   }\r
 591 \r
 592   NodeT           = mPrev[NodeR];\r
 593   mPrev[mPos]     = NodeT;\r
 594   mNext[NodeT]    = mPos;\r
 595   NodeT           = mNext[NodeR];\r
 596   mNext[mPos]     = NodeT;\r
 597   mPrev[NodeT]    = mPos;\r
 598   mParent[mPos]   = NodeQ;\r
 599   mParent[NodeR]  = NIL;\r
 600 \r
 601   //\r
 602   // Special usage of 'next'\r
 603   //\r
 604   mNext[NodeR] = mPos;\r
 605 \r
 606 }\r
 607 \r
 608 STATIC\r
 609 VOID\r
 610 DeleteNode (\r
 611   VOID\r
 612   )\r
 613 /*++\r
 614 \r
 615 Routine Description:\r
 616 \r
 617   Delete outdated string info. (The Usage of PERC_FLAG\r
 618   ensures a clean deletion)\r
 619   \r
 620 Arguments: (VOID)\r
 621 \r
 622 Returns: (VOID)\r
 623 \r
 624 --*/\r
 625 {\r
 626   NODE  NodeQ;\r
 627   NODE  NodeR;\r
 628   NODE  NodeS;\r
 629   NODE  NodeT;\r
 630   NODE  NodeU;\r
 631 \r
 632   if (mParent[mPos] == NIL) {\r
 633     return ;\r
 634   }\r
 635 \r
 636   NodeR         = mPrev[mPos];\r
 637   NodeS         = mNext[mPos];\r
 638   mNext[NodeR]  = NodeS;\r
 639   mPrev[NodeS]  = NodeR;\r
 640   NodeR         = mParent[mPos];\r
 641   mParent[mPos] = NIL;\r
 642   if (NodeR >= WNDSIZ) {\r
 643     return ;\r
 644   }\r
 645 \r
 646   mChildCount[NodeR]--;\r
 647   if (mChildCount[NodeR] > 1) {\r
 648     return ;\r
 649   }\r
 650 \r
 651   NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);\r
 652   if (NodeT >= mPos) {\r
 653     NodeT -= WNDSIZ;\r
 654   }\r
 655 \r
 656   NodeS = NodeT;\r
 657   NodeQ = mParent[NodeR];\r
 658   NodeU = mPosition[NodeQ];\r
 659   while (NodeU & (UINT32) PERC_FLAG) {\r
 660     NodeU &= (UINT32)~PERC_FLAG;\r
 661     if (NodeU >= mPos) {\r
 662       NodeU -= WNDSIZ;\r
 663     }\r
 664 \r
 665     if (NodeU > NodeS) {\r
 666       NodeS = NodeU;\r
 667     }\r
 668 \r
 669     mPosition[NodeQ]  = (NODE) (NodeS | WNDSIZ);\r
 670     NodeQ             = mParent[NodeQ];\r
 671     NodeU             = mPosition[NodeQ];\r
 672   }\r
 673 \r
 674   if (NodeQ < WNDSIZ) {\r
 675     if (NodeU >= mPos) {\r
 676       NodeU -= WNDSIZ;\r
 677     }\r
 678 \r
 679     if (NodeU > NodeS) {\r
 680       NodeS = NodeU;\r
 681     }\r
 682 \r
 683     mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);\r
 684   }\r
 685 \r
 686   NodeS           = Child (NodeR, mText[NodeT + mLevel[NodeR]]);\r
 687   NodeT           = mPrev[NodeS];\r
 688   NodeU           = mNext[NodeS];\r
 689   mNext[NodeT]    = NodeU;\r
 690   mPrev[NodeU]    = NodeT;\r
 691   NodeT           = mPrev[NodeR];\r
 692   mNext[NodeT]    = NodeS;\r
 693   mPrev[NodeS]    = NodeT;\r
 694   NodeT           = mNext[NodeR];\r
 695   mPrev[NodeT]    = NodeS;\r
 696   mNext[NodeS]    = NodeT;\r
 697   mParent[NodeS]  = mParent[NodeR];\r
 698   mParent[NodeR]  = NIL;\r
 699   mNext[NodeR]    = mAvail;\r
 700   mAvail          = NodeR;\r
 701 }\r
 702 \r
 703 STATIC\r
 704 VOID\r
 705 GetNextMatch (\r
 706   VOID\r
 707   )\r
 708 /*++\r
 709 \r
 710 Routine Description:\r
 711 \r
 712   Advance the current position (read in new data if needed).\r
 713   Delete outdated string info. Find a match string for current position.\r
 714 \r
 715 Arguments: (VOID)\r
 716 \r
 717 Returns: (VOID)\r
 718 \r
 719 --*/\r
 720 {\r
 721   INT32 Number;\r
 722 \r
 723   mRemainder--;\r
 724   mPos++;\r
 725   if (mPos == WNDSIZ * 2) {\r
 726     memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
 727     Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);\r
 728     mRemainder += Number;\r
 729     mPos = WNDSIZ;\r
 730   }\r
 731 \r
 732   DeleteNode ();\r
 733   InsertNode ();\r
 734 }\r
 735 \r
 736 STATIC\r
 737 EFI_STATUS\r
 738 Encode (\r
 739   VOID\r
 740   )\r
 741 /*++\r
 742 \r
 743 Routine Description:\r
 744 \r
 745   The main controlling routine for compression process.\r
 746 \r
 747 Arguments: (VOID)\r
 748 \r
 749 Returns:\r
 750   \r
 751   EFI_SUCCESS           - The compression is successful\r
 752   EFI_OUT_0F_RESOURCES  - Not enough memory for compression process\r
 753 \r
 754 --*/\r
 755 {\r
 756   EFI_STATUS  Status;\r
 757   INT32       LastMatchLen;\r
 758   NODE        LastMatchPos;\r
 759 \r
 760   Status = AllocateMemory ();\r
 761   if (EFI_ERROR (Status)) {\r
 762     FreeMemory ();\r
 763     return Status;\r
 764   }\r
 765 \r
 766   InitSlide ();\r
 767 \r
 768   HufEncodeStart ();\r
 769 \r
 770   mRemainder  = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
 771 \r
 772   mMatchLen   = 0;\r
 773   mPos        = WNDSIZ;\r
 774   InsertNode ();\r
 775   if (mMatchLen > mRemainder) {\r
 776     mMatchLen = mRemainder;\r
 777   }\r
 778 \r
 779   while (mRemainder > 0) {\r
 780     LastMatchLen  = mMatchLen;\r
 781     LastMatchPos  = mMatchPos;\r
 782     GetNextMatch ();\r
 783     if (mMatchLen > mRemainder) {\r
 784       mMatchLen = mRemainder;\r
 785     }\r
 786 \r
 787     if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {\r
 788       //\r
 789       // Not enough benefits are gained by outputting a pointer,\r
 790       // so just output the original character\r
 791       //\r
 792       Output (mText[mPos - 1], 0);\r
 793 \r
 794     } else {\r
 795 \r
 796       if (LastMatchLen == THRESHOLD) {\r
 797         if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {\r
 798           Output (mText[mPos - 1], 0);\r
 799           continue;\r
 800         }\r
 801       }\r
 802       //\r
 803       // Outputting a pointer is beneficial enough, do it.\r
 804       //\r
 805       Output (\r
 806         LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),\r
 807         (mPos - LastMatchPos - 2) & (WNDSIZ - 1)\r
 808         );\r
 809       LastMatchLen--;\r
 810       while (LastMatchLen > 0) {\r
 811         GetNextMatch ();\r
 812         LastMatchLen--;\r
 813       }\r
 814 \r
 815       if (mMatchLen > mRemainder) {\r
 816         mMatchLen = mRemainder;\r
 817       }\r
 818     }\r
 819   }\r
 820 \r
 821   HufEncodeEnd ();\r
 822   FreeMemory ();\r
 823   return EFI_SUCCESS;\r
 824 }\r
 825 \r
 826 STATIC\r
 827 VOID\r
 828 CountTFreq (\r
 829   VOID\r
 830   )\r
 831 /*++\r
 832 \r
 833 Routine Description:\r
 834 \r
 835   Count the frequencies for the Extra Set\r
 836   \r
 837 Arguments: (VOID)\r
 838 \r
 839 Returns: (VOID)\r
 840 \r
 841 --*/\r
 842 {\r
 843   INT32 Index;\r
 844   INT32 Index3;\r
 845   INT32 Number;\r
 846   INT32 Count;\r
 847 \r
 848   for (Index = 0; Index < NT; Index++) {\r
 849     mTFreq[Index] = 0;\r
 850   }\r
 851 \r
 852   Number = NC;\r
 853   while (Number > 0 && mCLen[Number - 1] == 0) {\r
 854     Number--;\r
 855   }\r
 856 \r
 857   Index = 0;\r
 858   while (Index < Number) {\r
 859     Index3 = mCLen[Index++];\r
 860     if (Index3 == 0) {\r
 861       Count = 1;\r
 862       while (Index < Number && mCLen[Index] == 0) {\r
 863         Index++;\r
 864         Count++;\r
 865       }\r
 866 \r
 867       if (Count <= 2) {\r
 868         mTFreq[0] = (UINT16) (mTFreq[0] + Count);\r
 869       } else if (Count <= 18) {\r
 870         mTFreq[1]++;\r
 871       } else if (Count == 19) {\r
 872         mTFreq[0]++;\r
 873         mTFreq[1]++;\r
 874       } else {\r
 875         mTFreq[2]++;\r
 876       }\r
 877     } else {\r
 878       mTFreq[Index3 + 2]++;\r
 879     }\r
 880   }\r
 881 }\r
 882 \r
 883 STATIC\r
 884 VOID\r
 885 WritePTLen (\r
 886   IN INT32 Number,\r
 887   IN INT32 nbit,\r
 888   IN INT32 Special\r
 889   )\r
 890 /*++\r
 891 \r
 892 Routine Description:\r
 893 \r
 894   Outputs the code length array for the Extra Set or the Position Set.\r
 895   \r
 896 Arguments:\r
 897 \r
 898   Number       - the number of symbols\r
 899   nbit    - the number of bits needed to represent 'n'\r
 900   Special - the special symbol that needs to be take care of\r
 901   \r
 902 Returns: (VOID)\r
 903 \r
 904 --*/\r
 905 {\r
 906   INT32 Index;\r
 907   INT32 Index3;\r
 908 \r
 909   while (Number > 0 && mPTLen[Number - 1] == 0) {\r
 910     Number--;\r
 911   }\r
 912 \r
 913   PutBits (nbit, Number);\r
 914   Index = 0;\r
 915   while (Index < Number) {\r
 916     Index3 = mPTLen[Index++];\r
 917     if (Index3 <= 6) {\r
 918       PutBits (3, Index3);\r
 919     } else {\r
 920       PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);\r
 921     }\r
 922 \r
 923     if (Index == Special) {\r
 924       while (Index < 6 && mPTLen[Index] == 0) {\r
 925         Index++;\r
 926       }\r
 927 \r
 928       PutBits (2, (Index - 3) & 3);\r
 929     }\r
 930   }\r
 931 }\r
 932 \r
 933 STATIC\r
 934 VOID\r
 935 WriteCLen (\r
 936   VOID\r
 937   )\r
 938 /*++\r
 939 \r
 940 Routine Description:\r
 941 \r
 942   Outputs the code length array for Char&Length Set\r
 943   \r
 944 Arguments: (VOID)\r
 945 \r
 946 Returns: (VOID)\r
 947 \r
 948 --*/\r
 949 {\r
 950   INT32 Index;\r
 951   INT32 Index3;\r
 952   INT32 Number;\r
 953   INT32 Count;\r
 954 \r
 955   Number = NC;\r
 956   while (Number > 0 && mCLen[Number - 1] == 0) {\r
 957     Number--;\r
 958   }\r
 959 \r
 960   PutBits (CBIT, Number);\r
 961   Index = 0;\r
 962   while (Index < Number) {\r
 963     Index3 = mCLen[Index++];\r
 964     if (Index3 == 0) {\r
 965       Count = 1;\r
 966       while (Index < Number && mCLen[Index] == 0) {\r
 967         Index++;\r
 968         Count++;\r
 969       }\r
 970 \r
 971       if (Count <= 2) {\r
 972         for (Index3 = 0; Index3 < Count; Index3++) {\r
 973           PutBits (mPTLen[0], mPTCode[0]);\r
 974         }\r
 975       } else if (Count <= 18) {\r
 976         PutBits (mPTLen[1], mPTCode[1]);\r
 977         PutBits (4, Count - 3);\r
 978       } else if (Count == 19) {\r
 979         PutBits (mPTLen[0], mPTCode[0]);\r
 980         PutBits (mPTLen[1], mPTCode[1]);\r
 981         PutBits (4, 15);\r
 982       } else {\r
 983         PutBits (mPTLen[2], mPTCode[2]);\r
 984         PutBits (CBIT, Count - 20);\r
 985       }\r
 986     } else {\r
 987       PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);\r
 988     }\r
 989   }\r
 990 }\r
 991 \r
 992 STATIC\r
 993 VOID\r
 994 EncodeC (\r
 995   IN INT32 Value\r
 996   )\r
 997 {\r
 998   PutBits (mCLen[Value], mCCode[Value]);\r
 999 }\r
1000 \r
1001 STATIC\r
1002 VOID\r
1003 EncodeP (\r
1004   IN UINT32 Value\r
1005   )\r
1006 {\r
1007   UINT32  Index;\r
1008   UINT32  NodeQ;\r
1009 \r
1010   Index = 0;\r
1011   NodeQ = Value;\r
1012   while (NodeQ) {\r
1013     NodeQ >>= 1;\r
1014     Index++;\r
1015   }\r
1016 \r
1017   PutBits (mPTLen[Index], mPTCode[Index]);\r
1018   if (Index > 1) {\r
1019     PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));\r
1020   }\r
1021 }\r
1022 \r
1023 STATIC\r
1024 VOID\r
1025 SendBlock (\r
1026   VOID\r
1027   )\r
1028 /*++\r
1029 \r
1030 Routine Description:\r
1031 \r
1032   Huffman code the block and output it.\r
1033   \r
1034 Arguments: \r
1035   (VOID)\r
1036 \r
1037 Returns: \r
1038   (VOID)\r
1039 \r
1040 --*/\r
1041 {\r
1042   UINT32  Index;\r
1043   UINT32  Index2;\r
1044   UINT32  Index3;\r
1045   UINT32  Flags;\r
1046   UINT32  Root;\r
1047   UINT32  Pos;\r
1048   UINT32  Size;\r
1049   Flags = 0;\r
1050 \r
1051   Root  = MakeTree (NC, mCFreq, mCLen, mCCode);\r
1052   Size  = mCFreq[Root];\r
1053 \r
1054   PutBits (16, Size);\r
1055   if (Root >= NC) {\r
1056     CountTFreq ();\r
1057     Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);\r
1058     if (Root >= NT) {\r
1059       WritePTLen (NT, TBIT, 3);\r
1060     } else {\r
1061       PutBits (TBIT, 0);\r
1062       PutBits (TBIT, Root);\r
1063     }\r
1064 \r
1065     WriteCLen ();\r
1066   } else {\r
1067     PutBits (TBIT, 0);\r
1068     PutBits (TBIT, 0);\r
1069     PutBits (CBIT, 0);\r
1070     PutBits (CBIT, Root);\r
1071   }\r
1072 \r
1073   Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);\r
1074   if (Root >= NP) {\r
1075     WritePTLen (NP, PBIT, -1);\r
1076   } else {\r
1077     PutBits (PBIT, 0);\r
1078     PutBits (PBIT, Root);\r
1079   }\r
1080 \r
1081   Pos = 0;\r
1082   for (Index = 0; Index < Size; Index++) {\r
1083     if (Index % UINT8_BIT == 0) {\r
1084       Flags = mBuf[Pos++];\r
1085     } else {\r
1086       Flags <<= 1;\r
1087     }\r
1088 \r
1089     if (Flags & (1U << (UINT8_BIT - 1))) {\r
1090       EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));\r
1091       Index3 = mBuf[Pos++];\r
1092       for (Index2 = 0; Index2 < 3; Index2++) {\r
1093         Index3 <<= UINT8_BIT;\r
1094         Index3 += mBuf[Pos++];\r
1095       }\r
1096 \r
1097       EncodeP (Index3);\r
1098     } else {\r
1099       EncodeC (mBuf[Pos++]);\r
1100     }\r
1101   }\r
1102 \r
1103   for (Index = 0; Index < NC; Index++) {\r
1104     mCFreq[Index] = 0;\r
1105   }\r
1106 \r
1107   for (Index = 0; Index < NP; Index++) {\r
1108     mPFreq[Index] = 0;\r
1109   }\r
1110 }\r
1111 \r
1112 STATIC\r
1113 VOID\r
1114 Output (\r
1115   IN UINT32 CharC,\r
1116   IN UINT32 Pos\r
1117   )\r
1118 /*++\r
1119 \r
1120 Routine Description:\r
1121 \r
1122   Outputs an Original Character or a Pointer\r
1123 \r
1124 Arguments:\r
1125 \r
1126   CharC     - The original character or the 'String Length' element of a Pointer\r
1127   Pos     - The 'Position' field of a Pointer\r
1128 \r
1129 Returns: (VOID)\r
1130 \r
1131 --*/\r
1132 {\r
1133   STATIC UINT32 CPos;\r
1134 \r
1135   if ((mOutputMask >>= 1) == 0) {\r
1136     mOutputMask = 1U << (UINT8_BIT - 1);\r
1137     //\r
1138     // Check the buffer overflow per outputing UINT8_BIT symbols\r
1139     // which is an Original Character or a Pointer. The biggest\r
1140     // symbol is a Pointer which occupies 5 bytes.\r
1141     //\r
1142     if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {\r
1143       SendBlock ();\r
1144       mOutputPos = 0;\r
1145     }\r
1146 \r
1147     CPos        = mOutputPos++;\r
1148     mBuf[CPos]  = 0;\r
1149   }\r
1150 \r
1151   mBuf[mOutputPos++] = (UINT8) CharC;\r
1152   mCFreq[CharC]++;\r
1153   if (CharC >= (1U << UINT8_BIT)) {\r
1154     mBuf[CPos] |= mOutputMask;\r
1155     mBuf[mOutputPos++]  = (UINT8) (Pos >> 24);\r
1156     mBuf[mOutputPos++]  = (UINT8) (Pos >> 16);\r
1157     mBuf[mOutputPos++]  = (UINT8) (Pos >> (UINT8_BIT));\r
1158     mBuf[mOutputPos++]  = (UINT8) Pos;\r
1159     CharC               = 0;\r
1160     while (Pos) {\r
1161       Pos >>= 1;\r
1162       CharC++;\r
1163     }\r
1164 \r
1165     mPFreq[CharC]++;\r
1166   }\r
1167 }\r
1168 \r
1169 STATIC\r
1170 VOID\r
1171 HufEncodeStart (\r
1172   VOID\r
1173   )\r
1174 {\r
1175   INT32 Index;\r
1176 \r
1177   for (Index = 0; Index < NC; Index++) {\r
1178     mCFreq[Index] = 0;\r
1179   }\r
1180 \r
1181   for (Index = 0; Index < NP; Index++) {\r
1182     mPFreq[Index] = 0;\r
1183   }\r
1184 \r
1185   mOutputPos = mOutputMask = 0;\r
1186   InitPutBits ();\r
1187   return ;\r
1188 }\r
1189 \r
1190 STATIC\r
1191 VOID\r
1192 HufEncodeEnd (\r
1193   VOID\r
1194   )\r
1195 {\r
1196   SendBlock ();\r
1197 \r
1198   //\r
1199   // Flush remaining bits\r
1200   //\r
1201   PutBits (UINT8_BIT - 1, 0);\r
1202 \r
1203   return ;\r
1204 }\r
1205 \r
1206 STATIC\r
1207 VOID\r
1208 MakeCrcTable (\r
1209   VOID\r
1210   )\r
1211 {\r
1212   UINT32  Index;\r
1213   UINT32  Index2;\r
1214   UINT32  Temp;\r
1215 \r
1216   for (Index = 0; Index <= UINT8_MAX; Index++) {\r
1217     Temp = Index;\r
1218     for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {\r
1219       if (Temp & 1) {\r
1220         Temp = (Temp >> 1) ^ CRCPOLY;\r
1221       } else {\r
1222         Temp >>= 1;\r
1223       }\r
1224     }\r
1225 \r
1226     mCrcTable[Index] = (UINT16) Temp;\r
1227   }\r
1228 }\r
1229 \r
1230 STATIC\r
1231 VOID\r
1232 PutBits (\r
1233   IN INT32  Number,\r
1234   IN UINT32 Value\r
1235   )\r
1236 /*++\r
1237 \r
1238 Routine Description:\r
1239 \r
1240   Outputs rightmost n bits of x\r
1241 \r
1242 Arguments:\r
1243 \r
1244   Number   - the rightmost n bits of the data is used\r
1245   x   - the data \r
1246 \r
1247 Returns: (VOID)\r
1248 \r
1249 --*/\r
1250 {\r
1251   UINT8 Temp;\r
1252 \r
1253   while (Number >= mBitCount) {\r
1254     //\r
1255     // Number -= mBitCount should never equal to 32\r
1256     //\r
1257     Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));\r
1258 \r
1259     if (mDst < mDstUpperLimit) {\r
1260       *mDst++ = Temp;\r
1261     }\r
1262 \r
1263     mCompSize++;\r
1264     mSubBitBuf  = 0;\r
1265     mBitCount   = UINT8_BIT;\r
1266   }\r
1267 \r
1268   mSubBitBuf |= Value << (mBitCount -= Number);\r
1269 }\r
1270 \r
1271 STATIC\r
1272 INT32\r
1273 FreadCrc (\r
1274   OUT UINT8 *Pointer,\r
1275   IN  INT32 Number\r
1276   )\r
1277 /*++\r
1278 \r
1279 Routine Description:\r
1280 \r
1281   Read in source data\r
1282   \r
1283 Arguments:\r
1284 \r
1285   Pointer   - the buffer to hold the data\r
1286   Number   - number of bytes to read\r
1287 \r
1288 Returns:\r
1289 \r
1290   number of bytes actually read\r
1291   \r
1292 --*/\r
1293 {\r
1294   INT32 Index;\r
1295 \r
1296   for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {\r
1297     *Pointer++ = *mSrc++;\r
1298   }\r
1299 \r
1300   Number = Index;\r
1301 \r
1302   Pointer -= Number;\r
1303   mOrigSize += Number;\r
1304 \r
1305   Index--;\r
1306   while (Index >= 0) {\r
1307     UPDATE_CRC (*Pointer++);\r
1308     Index--;\r
1309   }\r
1310 \r
1311   return Number;\r
1312 }\r
1313 \r
1314 STATIC\r
1315 VOID\r
1316 InitPutBits (\r
1317   VOID\r
1318   )\r
1319 {\r
1320   mBitCount   = UINT8_BIT;\r
1321   mSubBitBuf  = 0;\r
1322 }\r
1323 \r
1324 STATIC\r
1325 VOID\r
1326 CountLen (\r
1327   IN INT32 Index\r
1328   )\r
1329 /*++\r
1330 \r
1331 Routine Description:\r
1332 \r
1333   Count the number of each code length for a Huffman tree.\r
1334   \r
1335 Arguments:\r
1336 \r
1337   Index   - the top node\r
1338   \r
1339 Returns: (VOID)\r
1340 \r
1341 --*/\r
1342 {\r
1343   STATIC INT32  Depth = 0;\r
1344 \r
1345   if (Index < mN) {\r
1346     mLenCnt[(Depth < 16) ? Depth : 16]++;\r
1347   } else {\r
1348     Depth++;\r
1349     CountLen (mLeft[Index]);\r
1350     CountLen (mRight[Index]);\r
1351     Depth--;\r
1352   }\r
1353 }\r
1354 \r
1355 STATIC\r
1356 VOID\r
1357 MakeLen (\r
1358   IN INT32 Root\r
1359   )\r
1360 /*++\r
1361 \r
1362 Routine Description:\r
1363 \r
1364   Create code length array for a Huffman tree\r
1365   \r
1366 Arguments:\r
1367 \r
1368   Root   - the root of the tree\r
1369   \r
1370 Returns:\r
1371 \r
1372   VOID\r
1373 \r
1374 --*/\r
1375 {\r
1376   INT32   Index;\r
1377   INT32   Index3;\r
1378   UINT32  Cum;\r
1379 \r
1380   for (Index = 0; Index <= 16; Index++) {\r
1381     mLenCnt[Index] = 0;\r
1382   }\r
1383 \r
1384   CountLen (Root);\r
1385 \r
1386   //\r
1387   // Adjust the length count array so that\r
1388   // no code will be generated longer than its designated length\r
1389   //\r
1390   Cum = 0;\r
1391   for (Index = 16; Index > 0; Index--) {\r
1392     Cum += mLenCnt[Index] << (16 - Index);\r
1393   }\r
1394 \r
1395   while (Cum != (1U << 16)) {\r
1396     mLenCnt[16]--;\r
1397     for (Index = 15; Index > 0; Index--) {\r
1398       if (mLenCnt[Index] != 0) {\r
1399         mLenCnt[Index]--;\r
1400         mLenCnt[Index + 1] += 2;\r
1401         break;\r
1402       }\r
1403     }\r
1404 \r
1405     Cum--;\r
1406   }\r
1407 \r
1408   for (Index = 16; Index > 0; Index--) {\r
1409     Index3 = mLenCnt[Index];\r
1410     Index3--;\r
1411     while (Index3 >= 0) {\r
1412       mLen[*mSortPtr++] = (UINT8) Index;\r
1413       Index3--;\r
1414     }\r
1415   }\r
1416 }\r
1417 \r
1418 STATIC\r
1419 VOID\r
1420 DownHeap (\r
1421   IN INT32 Index\r
1422   )\r
1423 {\r
1424   INT32 Index2;\r
1425   INT32 Index3;\r
1426 \r
1427   //\r
1428   // priority queue: send Index-th entry down heap\r
1429   //\r
1430   Index3  = mHeap[Index];\r
1431   Index2  = 2 * Index;\r
1432   while (Index2 <= mHeapSize) {\r
1433     if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {\r
1434       Index2++;\r
1435     }\r
1436 \r
1437     if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {\r
1438       break;\r
1439     }\r
1440 \r
1441     mHeap[Index]  = mHeap[Index2];\r
1442     Index         = Index2;\r
1443     Index2        = 2 * Index;\r
1444   }\r
1445 \r
1446   mHeap[Index] = (INT16) Index3;\r
1447 }\r
1448 \r
1449 STATIC\r
1450 VOID\r
1451 MakeCode (\r
1452   IN  INT32       Number,\r
1453   IN  UINT8 Len[  ],\r
1454   OUT UINT16 Code[]\r
1455   )\r
1456 /*++\r
1457 \r
1458 Routine Description:\r
1459 \r
1460   Assign code to each symbol based on the code length array\r
1461   \r
1462 Arguments:\r
1463 \r
1464   Number     - number of symbols\r
1465   Len   - the code length array\r
1466   Code  - stores codes for each symbol\r
1467 \r
1468 Returns: (VOID)\r
1469 \r
1470 --*/\r
1471 {\r
1472   INT32   Index;\r
1473   UINT16  Start[18];\r
1474 \r
1475   Start[1] = 0;\r
1476   for (Index = 1; Index <= 16; Index++) {\r
1477     Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);\r
1478   }\r
1479 \r
1480   for (Index = 0; Index < Number; Index++) {\r
1481     Code[Index] = Start[Len[Index]]++;\r
1482   }\r
1483 }\r
1484 \r
1485 STATIC\r
1486 INT32\r
1487 MakeTree (\r
1488   IN  INT32            NParm,\r
1489   IN  UINT16  FreqParm[],\r
1490   OUT UINT8   LenParm[ ],\r
1491   OUT UINT16  CodeParm[]\r
1492   )\r
1493 /*++\r
1494 \r
1495 Routine Description:\r
1496 \r
1497   Generates Huffman codes given a frequency distribution of symbols\r
1498   \r
1499 Arguments:\r
1500 \r
1501   NParm    - number of symbols\r
1502   FreqParm - frequency of each symbol\r
1503   LenParm  - code length for each symbol\r
1504   CodeParm - code for each symbol\r
1505   \r
1506 Returns:\r
1507 \r
1508   Root of the Huffman tree.\r
1509   \r
1510 --*/\r
1511 {\r
1512   INT32 Index;\r
1513   INT32 Index2;\r
1514   INT32 Index3;\r
1515   INT32 Avail;\r
1516 \r
1517   //\r
1518   // make tree, calculate len[], return root\r
1519   //\r
1520   mN        = NParm;\r
1521   mFreq     = FreqParm;\r
1522   mLen      = LenParm;\r
1523   Avail     = mN;\r
1524   mHeapSize = 0;\r
1525   mHeap[1]  = 0;\r
1526   for (Index = 0; Index < mN; Index++) {\r
1527     mLen[Index] = 0;\r
1528     if (mFreq[Index]) {\r
1529       mHeapSize++;\r
1530       mHeap[mHeapSize] = (INT16) Index;\r
1531     }\r
1532   }\r
1533 \r
1534   if (mHeapSize < 2) {\r
1535     CodeParm[mHeap[1]] = 0;\r
1536     return mHeap[1];\r
1537   }\r
1538 \r
1539   for (Index = mHeapSize / 2; Index >= 1; Index--) {\r
1540     //\r
1541     // make priority queue\r
1542     //\r
1543     DownHeap (Index);\r
1544   }\r
1545 \r
1546   mSortPtr = CodeParm;\r
1547   do {\r
1548     Index = mHeap[1];\r
1549     if (Index < mN) {\r
1550       *mSortPtr++ = (UINT16) Index;\r
1551     }\r
1552 \r
1553     mHeap[1] = mHeap[mHeapSize--];\r
1554     DownHeap (1);\r
1555     Index2 = mHeap[1];\r
1556     if (Index2 < mN) {\r
1557       *mSortPtr++ = (UINT16) Index2;\r
1558     }\r
1559 \r
1560     Index3        = Avail++;\r
1561     mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);\r
1562     mHeap[1]      = (INT16) Index3;\r
1563     DownHeap (1);\r
1564     mLeft[Index3]   = (UINT16) Index;\r
1565     mRight[Index3]  = (UINT16) Index2;\r
1566   } while (mHeapSize > 1);\r
1567 \r
1568   mSortPtr = CodeParm;\r
1569   MakeLen (Index3);\r
1570   MakeCode (NParm, LenParm, CodeParm);\r
1571 \r
1572   //\r
1573   // return root\r
1574   //\r
1575   return Index3;\r
1576 }\r
1577 \r
1578 EFI_STATUS\r
1579 GetFileContents (\r
1580   IN char    *InputFileName,\r
1581   OUT UINT8   *FileBuffer,\r
1582   OUT UINT32  *BufferLength\r
1583   )\r
1584 /*++\r
1585         \r
1586 Routine Description:\r
1587            \r
1588   Get the contents of file specified in InputFileName\r
1589   into FileBuffer.\r
1590             \r
1591 Arguments:\r
1592                \r
1593   InputFileName  - Name of the input file.\r
1594                 \r
1595   FileBuffer     - Output buffer to contain data\r
1596 \r
1597   BufferLength   - Actual length of the data \r
1598 \r
1599 Returns:\r
1600                        \r
1601   EFI_SUCCESS on successful return\r
1602   EFI_ABORTED if unable to open input file.\r
1603 \r
1604 --*/\r
1605 {\r
1606   UINTN   Size;\r
1607   UINTN   FileSize;\r
1608   INTN    Index;\r
1609   FILE    *InputFile;\r
1610 \r
1611   Size = 0;\r
1612   //\r
1613   // Copy the file contents to the output buffer.\r
1614   //\r
1615   InputFile = fopen (InputFileName, "rb");\r
1616     if (InputFile == NULL) {\r
1617       Error(NULL, 0, 0001, "Error opening file: %s", InputFileName);\r
1618       return EFI_ABORTED;\r
1619     }\r
1620   \r
1621   fseek (InputFile, 0, SEEK_END);\r
1622   FileSize = ftell (InputFile);\r
1623   fseek (InputFile, 0, SEEK_SET);\r
1624     //\r
1625     // Now read the contents of the file into the buffer\r
1626     // \r
1627     if (FileSize > 0 && FileBuffer != NULL) {\r
1628       if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {\r
1629         Error(NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);\r
1630         fclose (InputFile);\r
1631         return EFI_ABORTED;\r
1632       }\r
1633     }\r
1634 \r
1635   fclose (InputFile);\r
1636   Size += (UINTN) FileSize;\r
1637   *BufferLength = Size;\r
1638   \r
1639   if (FileBuffer != NULL) {\r
1640     return EFI_SUCCESS;\r
1641   } else {\r
1642     return EFI_BUFFER_TOO_SMALL;\r
1643   }\r
1644 }\r
1645 \r
1646 VOID\r
1647 Version (\r
1648   VOID\r
1649   )\r
1650 /*++\r
1651 \r
1652 Routine Description:\r
1653 \r
1654   Displays the standard utility information to SDTOUT\r
1655 \r
1656 Arguments:\r
1657 \r
1658   None\r
1659 \r
1660 Returns:\r
1661 \r
1662   None\r
1663 \r
1664 --*/\r
1665 {\r
1666   fprintf (stdout, "%s Version %d.%d\n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION);\r
1667 }\r
1668 \r
1669 VOID\r
1670 Usage (\r
1671   VOID\r
1672   )\r
1673 /*++\r
1674 \r
1675 Routine Description:\r
1676 \r
1677   Displays the utility usage syntax to STDOUT\r
1678 \r
1679 Arguments:\r
1680 \r
1681   None\r
1682 \r
1683 Returns:\r
1684 \r
1685   None\r
1686 \r
1687 --*/\r
1688 {\r
1689   //\r
1690   // Summary usage\r
1691   //\r
1692   fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);\r
1693   \r
1694   //\r
1695   // Copyright declaration\r
1696   // \r
1697   fprintf (stdout, "Copyright (c) 2007, Intel Corporation. All rights reserved.\n\n");\r
1698 \r
1699   //\r
1700   // Details Option\r
1701   //\r
1702   fprintf (stdout, "Options:\n");\r
1703   fprintf (stdout, "  -o FileName, --output FileName\n\\r
1704             File will be created to store the ouput content.\n");\r
1705   fprintf (stdout, "  -v, --verbose\n\\r
1706             Turn on verbose output with informational messages.\n");\r
1707   fprintf (stdout, "  --version\n\\r
1708             Show program's version number and exit.\n");\r
1709   fprintf (stdout, "  -h, --help\n\\r
1710             Show this help message and exit.\n");\r
1711   fprintf (stdout, "  -q, --quiet\n\\r
1712          Disable all messages except FATAL ERRORS.\n");\r
1713   fprintf (stdout, "  -d, --debug [#]\n\\r
1714          Enable debug messages at level #.\n");  \r
1715 }\r
1716 \r
1717 \r
1718 int\r
1719 main (\r
1720   int  argc,\r
1721   char *argv[]\r
1722   )\r
1723 /*++\r
1724 \r
1725 Routine Description:\r
1726 \r
1727   Main\r
1728 \r
1729 Arguments:\r
1730 \r
1731   command line parameters\r
1732 \r
1733 Returns:\r
1734 \r
1735   EFI_SUCCESS    Section header successfully generated and section concatenated.\r
1736   EFI_ABORTED    Could not generate the section\r
1737   EFI_OUT_OF_RESOURCES  No resource to complete the operation.\r
1738 \r
1739 --*/  \r
1740 {\r
1741   FILE       *OutputFile;\r
1742   char       *OutputFileName;\r
1743   char       *InputFileName;\r
1744   FILE       *InputFile;\r
1745   EFI_STATUS Status;\r
1746   UINT8      *FileBuffer;\r
1747   UINT8      *OutBuffer;\r
1748   UINT32     InputLength;\r
1749   UINT32     DstSize;\r
1750   SCRATCH_DATA      *Scratch;\r
1751   UINT8      *Src;\r
1752   UINT32     OrigSize;\r
1753 \r
1754   SetUtilityName(UTILITY_NAME);\r
1755   \r
1756   FileBuffer = NULL;\r
1757   Src = NULL;\r
1758   OutBuffer = NULL;\r
1759   OrigSize = 0;\r
1760   InputLength = 0;\r
1761   InputFileName = NULL;\r
1762   OutputFileName = NULL;\r
1763   DstSize=0;\r
1764   DebugLevel = 0;\r
1765   DebugMode = FALSE;\r
1766 \r
1767   //\r
1768   // Verify the correct number of arguments\r
1769   //\r
1770   if (argc == 1) {\r
1771     Usage();\r
1772     return 0;\r
1773   }\r
1774   \r
1775   if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0) || \r
1776       (strcmp(argv[1], "-?") == 0) || (strcmp(argv[1], "/?") == 0)) {\r
1777     Usage();\r
1778     return 0;\r
1779   }\r
1780   \r
1781   if ( (strcmp(argv[1], "--version") == 0)) {\r
1782     Version();\r
1783     return 0;\r
1784   }\r
1785 \r
1786   argc--;\r
1787   argv++;\r
1788   if (strcmp(argv[0],"-e") == 0) {\r
1789   //\r
1790   // encode the input file\r
1791   //\r
1792   ENCODE = TRUE;\r
1793   argc--;\r
1794   argv++;\r
1795   }\r
1796   else if (strcmp(argv[0], "-d") == 0) {\r
1797   //\r
1798   // decode the input file\r
1799   //\r
1800   DECODE = TRUE;\r
1801   argc--;\r
1802   argv++;\r
1803   }\r
1804   else {\r
1805   //\r
1806   // Error command line\r
1807   //\r
1808   Usage();\r
1809   return 1;\r
1810   }\r
1811 \r
1812   while (argc > 0) {\r
1813    if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {\r
1814     VerboseMode = TRUE;\r
1815     argc--;\r
1816     argv++;\r
1817     continue;\r
1818   }\r
1819    if ((stricmp (argv[0], "-d") == 0) || (stricmp (argv[0], "--debug") == 0)) {\r
1820      argc-=2;\r
1821      argv++;\r
1822      Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);\r
1823      if (DebugLevel > 9 || DebugLevel < 0) {\r
1824        Error(NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);\r
1825        goto ERROR;\r
1826      }\r
1827      if (DebugLevel>=5 && DebugLevel <=9){\r
1828        DebugMode = TRUE;\r
1829      } else {\r
1830        DebugMode = FALSE;\r
1831      }\r
1832      argv++;\r
1833      continue;\r
1834    }\r
1835    if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--debug") == 0)) {\r
1836      QuietMode = TRUE;\r
1837      argc--;\r
1838      argv++;\r
1839      continue;\r
1840    }\r
1841    if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {\r
1842     argc-=2;\r
1843     argv++;\r
1844     OutputFileName = argv[0];\r
1845     argv++;\r
1846     continue; \r
1847     }\r
1848    if (argv[0][0]!='-') {\r
1849    InputFileName = argv[0];\r
1850    argc--;\r
1851    argv++;\r
1852    continue;\r
1853    }\r
1854     Error (NULL, 0, 1000, "Unknown option", argv[0]);\r
1855     goto ERROR;     \r
1856   }\r
1857 \r
1858   if (InputFileName == NULL) {\r
1859     Error(NULL, 0, 2000, " Invalid parameter");\r
1860     Usage();\r
1861     return 1;    \r
1862   }\r
1863 \r
1864 //\r
1865 // All Parameters has been parsed\r
1866 // \r
1867   if (VerboseMode) {\r
1868     fprintf (stdout, "%s tool start.\n", UTILITY_NAME);\r
1869    }\r
1870   Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));\r
1871   if (Scratch == NULL) {\r
1872     Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1873     //return 1;\r
1874     goto ERROR;\r
1875   }\r
1876     \r
1877   InputFile = fopen (InputFileName, "rb");\r
1878   if (InputFile == NULL) {\r
1879     Error(NULL, 0, 0001, "Error opening input file", InputFileName);\r
1880     //return 1;\r
1881     goto ERROR;\r
1882   }\r
1883         \r
1884   Status = GetFileContents(\r
1885             InputFileName,\r
1886             FileBuffer,\r
1887             &InputLength);\r
1888 \r
1889   if (Status == EFI_BUFFER_TOO_SMALL) {\r
1890     FileBuffer = (UINT8 *) malloc (InputLength);\r
1891     if (FileBuffer == NULL) {\r
1892       Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1893       return EFI_OUT_OF_RESOURCES;\r
1894     }\r
1895 \r
1896     Status = GetFileContents (\r
1897               InputFileName,\r
1898               FileBuffer,\r
1899               &InputLength\r
1900               );\r
1901   }\r
1902 \r
1903   if (EFI_ERROR(Status)) {\r
1904     free(FileBuffer);\r
1905     return 1;\r
1906   }\r
1907    \r
1908   if (OutputFileName != NULL) {\r
1909     OutputFile = fopen (OutputFileName, "wb");\r
1910     if (OutputFile == NULL) {\r
1911       Error(NULL, 0, 0001, "Error opening output file for writing", OutputFileName);\r
1912     if (InputFile != NULL) {\r
1913       fclose (InputFile);\r
1914       }\r
1915       //return EFI_ABORTED;\r
1916       goto ERROR;\r
1917       }\r
1918     }\r
1919     \r
1920   if (ENCODE) {\r
1921   //\r
1922   // First call TianoCompress to get DstSize\r
1923   //\r
1924   if (DebugMode) {\r
1925     fprintf(stdout, "Encoding\n");\r
1926   }\r
1927   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
1928   \r
1929   if (Status == EFI_BUFFER_TOO_SMALL) {\r
1930     OutBuffer = (UINT8 *) malloc (DstSize);\r
1931     if (OutBuffer == NULL) {\r
1932       Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1933       goto ERROR;\r
1934     }\r
1935   }\r
1936   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
1937   if (Status != EFI_SUCCESS) {\r
1938     Error(NULL, 0, 0007, "Error compressing file");\r
1939     goto ERROR;\r
1940   }\r
1941 \r
1942   fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);\r
1943   free(FileBuffer);\r
1944   free(OutBuffer);\r
1945 \r
1946   if (DebugMode) {\r
1947     fprintf(stdout, "Encoding successful\n");\r
1948   }\r
1949   return 0;  \r
1950   }\r
1951   else if (DECODE) {\r
1952   if (DebugMode) {\r
1953     fprintf(stdout, "Decoding\n");\r
1954   }\r
1955   //\r
1956   // Get Compressed file original size\r
1957   // \r
1958   Src     = (UINT8 *)FileBuffer;                     \r
1959   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);  \r
1960   \r
1961   //\r
1962   // Allocate OutputBuffer\r
1963   //\r
1964   OutBuffer = (UINT8 *)malloc(OrigSize);\r
1965   if (OutBuffer == NULL) {\r
1966     Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1967     goto ERROR;\r
1968    }  \r
1969 \r
1970   Status = Decompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);\r
1971   if (Status != EFI_SUCCESS) {\r
1972     //Error(NULL, 0, 0008, "Error decompressing file: %s", InputFileName);\r
1973    goto ERROR;  \r
1974   }\r
1975 \r
1976   fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);\r
1977   free(Scratch);\r
1978   free(FileBuffer);\r
1979   free(OutBuffer);\r
1980 \r
1981   if (DebugMode) {\r
1982     fprintf(stdout, "Decoding successful\n");\r
1983   }\r
1984   return 0;\r
1985   }\r
1986   \r
1987 ERROR:\r
1988   if (DebugMode) {\r
1989     if (ENCODE) {\r
1990       fprintf(stdout, "Encoding Error\n");\r
1991     } else if (DECODE) {\r
1992       fprintf(stdout, "Decoding Error\n");\r
1993     }\r
1994   }\r
1995   free(Scratch);\r
1996   free(FileBuffer);\r
1997   free(OutBuffer);\r
1998   if (VerboseMode) {\r
1999     fprintf (stdout, "%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());  \r
2000   }\r
2001   return GetUtilityStatus ();\r
2002 }\r
2003 \r
2004 VOID\r
2005 FillBuf (\r
2006   IN  SCRATCH_DATA  *Sd,\r
2007   IN  UINT16        NumOfBits\r
2008   )\r
2009 /*++\r
2010 \r
2011 Routine Description:\r
2012 \r
2013   Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.\r
2014 \r
2015 Arguments:\r
2016 \r
2017   Sd        - The global scratch data\r
2018   NumOfBits  - The number of bits to shift and read.\r
2019 \r
2020 Returns: (VOID)\r
2021 \r
2022 --*/\r
2023 {\r
2024   Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);\r
2025 \r
2026   while (NumOfBits > Sd->mBitCount) {\r
2027 \r
2028     Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));\r
2029 \r
2030     if (Sd->mCompSize > 0) {\r
2031       //\r
2032       // Get 1 byte into SubBitBuf\r
2033       //\r
2034       Sd->mCompSize--;\r
2035       Sd->mSubBitBuf  = 0;\r
2036       Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];\r
2037       Sd->mBitCount   = 8;\r
2038 \r
2039     } else {\r
2040       //\r
2041       // No more bits from the source, just pad zero bit.\r
2042       //\r
2043       Sd->mSubBitBuf  = 0;\r
2044       Sd->mBitCount   = 8;\r
2045 \r
2046     }\r
2047   }\r
2048 \r
2049   Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);\r
2050   Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;\r
2051 }\r
2052 \r
2053 UINT32\r
2054 GetBits (\r
2055   IN  SCRATCH_DATA  *Sd,\r
2056   IN  UINT16        NumOfBits\r
2057   )\r
2058 /*++\r
2059 \r
2060 Routine Description:\r
2061 \r
2062   Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent \r
2063   NumOfBits of bits from source. Returns NumOfBits of bits that are \r
2064   popped out.\r
2065 \r
2066 Arguments:\r
2067 \r
2068   Sd            - The global scratch data.\r
2069   NumOfBits     - The number of bits to pop and read.\r
2070 \r
2071 Returns:\r
2072 \r
2073   The bits that are popped out.\r
2074 \r
2075 --*/\r
2076 {\r
2077   UINT32  OutBits;\r
2078 \r
2079   OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));\r
2080 \r
2081   FillBuf (Sd, NumOfBits);\r
2082 \r
2083   return OutBits;\r
2084 }\r
2085 \r
2086 UINT16\r
2087 MakeTable (\r
2088   IN  SCRATCH_DATA  *Sd,\r
2089   IN  UINT16        NumOfChar,\r
2090   IN  UINT8         *BitLen,\r
2091   IN  UINT16        TableBits,\r
2092   OUT UINT16        *Table\r
2093   )\r
2094 /*++\r
2095 \r
2096 Routine Description:\r
2097 \r
2098   Creates Huffman Code mapping table according to code length array.\r
2099 \r
2100 Arguments:\r
2101 \r
2102   Sd        - The global scratch data\r
2103   NumOfChar - Number of symbols in the symbol set\r
2104   BitLen    - Code length array\r
2105   TableBits - The width of the mapping table\r
2106   Table     - The table\r
2107   \r
2108 Returns:\r
2109   \r
2110   0         - OK.\r
2111   BAD_TABLE - The table is corrupted.\r
2112 \r
2113 --*/\r
2114 {\r
2115   UINT16  Count[17];\r
2116   UINT16  Weight[17];\r
2117   UINT16  Start[18];\r
2118   UINT16  *Pointer;\r
2119   UINT16  Index3;\r
2120   volatile UINT16  Index;\r
2121   UINT16  Len;\r
2122   UINT16  Char;\r
2123   UINT16  JuBits;\r
2124   UINT16  Avail;\r
2125   UINT16  NextCode;\r
2126   UINT16  Mask;\r
2127   UINT16  WordOfStart;\r
2128   UINT16  WordOfCount;\r
2129 \r
2130   for (Index = 1; Index <= 16; Index++) {\r
2131     Count[Index] = 0;\r
2132   }\r
2133 \r
2134   for (Index = 0; Index < NumOfChar; Index++) {\r
2135     Count[BitLen[Index]]++;\r
2136   }\r
2137 \r
2138   Start[1] = 0;\r
2139 \r
2140   for (Index = 1; Index <= 16; Index++) {\r
2141     WordOfStart = Start[Index];\r
2142     WordOfCount = Count[Index];\r
2143     Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));\r
2144   }\r
2145 \r
2146   if (Start[17] != 0) {\r
2147     //\r
2148     //(1U << 16)\r
2149     //\r
2150     return (UINT16) BAD_TABLE;\r
2151   }\r
2152 \r
2153   JuBits = (UINT16) (16 - TableBits);\r
2154 \r
2155   for (Index = 1; Index <= TableBits; Index++) {\r
2156     Start[Index] >>= JuBits;\r
2157     Weight[Index] = (UINT16) (1U << (TableBits - Index));\r
2158   }\r
2159 \r
2160   while (Index <= 16) {\r
2161     Weight[Index] = (UINT16) (1U << (16 - Index));\r
2162     Index++;\r
2163   }\r
2164 \r
2165   Index = (UINT16) (Start[TableBits + 1] >> JuBits);\r
2166 \r
2167   if (Index != 0) {\r
2168     Index3 = (UINT16) (1U << TableBits);\r
2169     while (Index != Index3) {\r
2170       Table[Index++] = 0;\r
2171     }\r
2172   }\r
2173 \r
2174   Avail = NumOfChar;\r
2175   Mask  = (UINT16) (1U << (15 - TableBits));\r
2176 \r
2177   for (Char = 0; Char < NumOfChar; Char++) {\r
2178 \r
2179     Len = BitLen[Char];\r
2180     if (Len == 0) {\r
2181       continue;\r
2182     }\r
2183 \r
2184     NextCode = (UINT16) (Start[Len] + Weight[Len]);\r
2185 \r
2186     if (Len <= TableBits) {\r
2187 \r
2188       for (Index = Start[Len]; Index < NextCode; Index++) {\r
2189         Table[Index] = Char;\r
2190       }\r
2191 \r
2192     } else {\r
2193 \r
2194       Index3  = Start[Len];\r
2195       Pointer = &Table[Index3 >> JuBits];\r
2196       Index   = (UINT16) (Len - TableBits);\r
2197 \r
2198       while (Index != 0) {\r
2199         if (*Pointer == 0) {\r
2200           Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;\r
2201           *Pointer = Avail++;\r
2202         }\r
2203 \r
2204         if (Index3 & Mask) {\r
2205           Pointer = &Sd->mRight[*Pointer];\r
2206         } else {\r
2207           Pointer = &Sd->mLeft[*Pointer];\r
2208         }\r
2209 \r
2210         Index3 <<= 1;\r
2211         Index--;\r
2212       }\r
2213 \r
2214       *Pointer = Char;\r
2215 \r
2216     }\r
2217 \r
2218     Start[Len] = NextCode;\r
2219   }\r
2220   //\r
2221   // Succeeds\r
2222   //\r
2223   return 0;\r
2224 }\r
2225 \r
2226 UINT32\r
2227 DecodeP (\r
2228   IN  SCRATCH_DATA  *Sd\r
2229   )\r
2230 /*++\r
2231 \r
2232 Routine Description:\r
2233 \r
2234   Decodes a position value.\r
2235 \r
2236 Arguments:\r
2237 \r
2238   Sd      - the global scratch data\r
2239 \r
2240 Returns:\r
2241 \r
2242   The position value decoded.\r
2243 \r
2244 --*/\r
2245 {\r
2246   UINT16  Val;\r
2247   UINT32  Mask;\r
2248   UINT32  Pos;\r
2249 \r
2250   Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
2251 \r
2252   if (Val >= MAXNP) {\r
2253     Mask = 1U << (BITBUFSIZ - 1 - 8);\r
2254 \r
2255     do {\r
2256 \r
2257       if (Sd->mBitBuf & Mask) {\r
2258         Val = Sd->mRight[Val];\r
2259       } else {\r
2260         Val = Sd->mLeft[Val];\r
2261       }\r
2262 \r
2263       Mask >>= 1;\r
2264     } while (Val >= MAXNP);\r
2265   }\r
2266   //\r
2267   // Advance what we have read\r
2268   //\r
2269   FillBuf (Sd, Sd->mPTLen[Val]);\r
2270 \r
2271   Pos = Val;\r
2272   if (Val > 1) {\r
2273     Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));\r
2274   }\r
2275 \r
2276   return Pos;\r
2277 }\r
2278 \r
2279 UINT16\r
2280 ReadPTLen (\r
2281   IN  SCRATCH_DATA  *Sd,\r
2282   IN  UINT16        nn,\r
2283   IN  UINT16        nbit,\r
2284   IN  UINT16        Special\r
2285   )\r
2286 /*++\r
2287 \r
2288 Routine Description:\r
2289 \r
2290   Reads code lengths for the Extra Set or the Position Set\r
2291 \r
2292 Arguments:\r
2293 \r
2294   Sd        - The global scratch data\r
2295   nn        - Number of symbols\r
2296   nbit      - Number of bits needed to represent nn\r
2297   Special   - The special symbol that needs to be taken care of \r
2298 \r
2299 Returns:\r
2300 \r
2301   0         - OK.\r
2302   BAD_TABLE - Table is corrupted.\r
2303 \r
2304 --*/\r
2305 {\r
2306   UINT16  Number;\r
2307   UINT16  CharC;\r
2308   volatile UINT16  Index;\r
2309   UINT32  Mask;\r
2310 \r
2311   Number = (UINT16) GetBits (Sd, nbit);\r
2312 \r
2313   if (Number == 0) {\r
2314     CharC = (UINT16) GetBits (Sd, nbit);\r
2315 \r
2316     for (Index = 0; Index < 256; Index++) {\r
2317       Sd->mPTTable[Index] = CharC;\r
2318     }\r
2319 \r
2320     for (Index = 0; Index < nn; Index++) {\r
2321       Sd->mPTLen[Index] = 0;\r
2322     }\r
2323 \r
2324     return 0;\r
2325   }\r
2326 \r
2327   Index = 0;\r
2328 \r
2329   while (Index < Number) {\r
2330 \r
2331     CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));\r
2332 \r
2333     if (CharC == 7) {\r
2334       Mask = 1U << (BITBUFSIZ - 1 - 3);\r
2335       while (Mask & Sd->mBitBuf) {\r
2336         Mask >>= 1;\r
2337         CharC += 1;\r
2338       }\r
2339     }\r
2340 \r
2341     FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));\r
2342 \r
2343     Sd->mPTLen[Index++] = (UINT8) CharC;\r
2344 \r
2345     if (Index == Special) {\r
2346       CharC = (UINT16) GetBits (Sd, 2);\r
2347       while ((INT16) (--CharC) >= 0) {\r
2348         Sd->mPTLen[Index++] = 0;\r
2349       }\r
2350     }\r
2351   }\r
2352 \r
2353   while (Index < nn) {\r
2354     Sd->mPTLen[Index++] = 0;\r
2355   }\r
2356 \r
2357   return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);\r
2358 }\r
2359 \r
2360 VOID\r
2361 ReadCLen (\r
2362   SCRATCH_DATA  *Sd\r
2363   )\r
2364 /*++\r
2365 \r
2366 Routine Description:\r
2367 \r
2368   Reads code lengths for Char&Len Set.\r
2369 \r
2370 Arguments:\r
2371 \r
2372   Sd    - the global scratch data\r
2373 \r
2374 Returns: (VOID)\r
2375 \r
2376 --*/\r
2377 {\r
2378   UINT16  Number;\r
2379   UINT16  CharC;\r
2380   volatile UINT16  Index;\r
2381   UINT32  Mask;\r
2382 \r
2383   Number = (UINT16) GetBits (Sd, CBIT);\r
2384 \r
2385   if (Number == 0) {\r
2386     CharC = (UINT16) GetBits (Sd, CBIT);\r
2387 \r
2388     for (Index = 0; Index < NC; Index++) {\r
2389       Sd->mCLen[Index] = 0;\r
2390     }\r
2391 \r
2392     for (Index = 0; Index < 4096; Index++) {\r
2393       Sd->mCTable[Index] = CharC;\r
2394     }\r
2395 \r
2396     return ;\r
2397   }\r
2398 \r
2399   Index = 0;\r
2400   while (Index < Number) {\r
2401 \r
2402     CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
2403     if (CharC >= NT) {\r
2404       Mask = 1U << (BITBUFSIZ - 1 - 8);\r
2405 \r
2406       do {\r
2407 \r
2408         if (Mask & Sd->mBitBuf) {\r
2409           CharC = Sd->mRight[CharC];\r
2410         } else {\r
2411           CharC = Sd->mLeft[CharC];\r
2412         }\r
2413 \r
2414         Mask >>= 1;\r
2415 \r
2416       } while (CharC >= NT);\r
2417     }\r
2418     //\r
2419     // Advance what we have read\r
2420     //\r
2421     FillBuf (Sd, Sd->mPTLen[CharC]);\r
2422 \r
2423     if (CharC <= 2) {\r
2424 \r
2425       if (CharC == 0) {\r
2426         CharC = 1;\r
2427       } else if (CharC == 1) {\r
2428         CharC = (UINT16) (GetBits (Sd, 4) + 3);\r
2429       } else if (CharC == 2) {\r
2430         CharC = (UINT16) (GetBits (Sd, CBIT) + 20);\r
2431       }\r
2432 \r
2433       while ((INT16) (--CharC) >= 0) {\r
2434         Sd->mCLen[Index++] = 0;\r
2435       }\r
2436 \r
2437     } else {\r
2438 \r
2439       Sd->mCLen[Index++] = (UINT8) (CharC - 2);\r
2440 \r
2441     }\r
2442   }\r
2443 \r
2444   while (Index < NC) {\r
2445     Sd->mCLen[Index++] = 0;\r
2446   }\r
2447 \r
2448   MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);\r
2449 \r
2450   return ;\r
2451 }\r
2452 \r
2453 UINT16\r
2454 DecodeC (\r
2455   SCRATCH_DATA  *Sd\r
2456   )\r
2457 /*++\r
2458 \r
2459 Routine Description:\r
2460 \r
2461   Decode a character/length value.\r
2462 \r
2463 Arguments:\r
2464 \r
2465   Sd    - The global scratch data.\r
2466 \r
2467 Returns:\r
2468 \r
2469   The value decoded.\r
2470 \r
2471 --*/\r
2472 {\r
2473   UINT16  Index2;\r
2474   UINT32  Mask;\r
2475 \r
2476   if (Sd->mBlockSize == 0) {\r
2477     //\r
2478     // Starting a new block\r
2479     //\r
2480     Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);\r
2481     Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);\r
2482     if (Sd->mBadTableFlag != 0) {\r
2483       return 0;\r
2484     }\r
2485 \r
2486     ReadCLen (Sd);\r
2487 \r
2488     Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));\r
2489     if (Sd->mBadTableFlag != 0) {\r
2490       return 0;\r
2491     }\r
2492   }\r
2493 \r
2494   Sd->mBlockSize--;\r
2495   Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];\r
2496 \r
2497   if (Index2 >= NC) {\r
2498     Mask = 1U << (BITBUFSIZ - 1 - 12);\r
2499 \r
2500     do {\r
2501       if (Sd->mBitBuf & Mask) {\r
2502         Index2 = Sd->mRight[Index2];\r
2503       } else {\r
2504         Index2 = Sd->mLeft[Index2];\r
2505       }\r
2506 \r
2507       Mask >>= 1;\r
2508     } while (Index2 >= NC);\r
2509   }\r
2510   //\r
2511   // Advance what we have read\r
2512   //\r
2513   FillBuf (Sd, Sd->mCLen[Index2]);\r
2514 \r
2515   return Index2;\r
2516 }\r
2517 \r
2518 VOID\r
2519 Decode (\r
2520   SCRATCH_DATA  *Sd\r
2521   )\r
2522 /*++\r
2523 \r
2524 Routine Description:\r
2525 \r
2526   Decode the source data and put the resulting data into the destination buffer.\r
2527 \r
2528 Arguments:\r
2529 \r
2530   Sd            - The global scratch data\r
2531 \r
2532 Returns: (VOID)\r
2533 \r
2534  --*/\r
2535 {\r
2536   UINT16  BytesRemain;\r
2537   UINT32  DataIdx;\r
2538   UINT16  CharC;\r
2539 \r
2540   BytesRemain = (UINT16) (-1);\r
2541 \r
2542   DataIdx     = 0;\r
2543 \r
2544   for (;;) {\r
2545     CharC = DecodeC (Sd);\r
2546     if (Sd->mBadTableFlag != 0) {\r
2547       goto Done ;\r
2548     }\r
2549 \r
2550     if (CharC < 256) {\r
2551       //\r
2552       // Process an Original character\r
2553       //\r
2554       if (Sd->mOutBuf >= Sd->mOrigSize) {\r
2555         goto Done ;\r
2556       } else {\r
2557         Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;\r
2558       }\r
2559 \r
2560     } else {\r
2561       //\r
2562       // Process a Pointer\r
2563       //\r
2564       CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));\r
2565 \r
2566       BytesRemain = CharC;\r
2567 \r
2568       DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;\r
2569 \r
2570       BytesRemain--;\r
2571       while ((INT16) (BytesRemain) >= 0) {\r
2572         Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];\r
2573         if (Sd->mOutBuf >= Sd->mOrigSize) {\r
2574           goto Done ;\r
2575         }\r
2576 \r
2577         BytesRemain--;\r
2578       }\r
2579     }\r
2580   }\r
2581 \r
2582 Done:\r
2583   return ;\r
2584 }\r
2585 \r
2586 RETURN_STATUS\r
2587 EFIAPI\r
2588 Decompress (\r
2589   IN VOID  *Source,\r
2590   IN OUT VOID    *Destination,\r
2591   IN OUT VOID    *Scratch,\r
2592   IN UINT32      Version\r
2593   )\r
2594 /*++\r
2595 \r
2596 Routine Description:\r
2597 \r
2598   The internal implementation of Decompress().\r
2599 \r
2600 Arguments:\r
2601 \r
2602   Source          - The source buffer containing the compressed data.\r
2603   Destination     - The destination buffer to store the decompressed data\r
2604   Scratch         - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.\r
2605   Version         - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm\r
2606 \r
2607 Returns:\r
2608 \r
2609   RETURN_SUCCESS           - Decompression is successfull\r
2610   RETURN_INVALID_PARAMETER - The source data is corrupted\r
2611 \r
2612 --*/\r
2613 {\r
2614   volatile UINT32  Index;\r
2615   UINT32           CompSize;\r
2616   UINT32           OrigSize;\r
2617   SCRATCH_DATA     *Sd;\r
2618   CONST UINT8      *Src;\r
2619   UINT8            *Dst;\r
2620 \r
2621   //\r
2622   // Verify input is not NULL\r
2623   //\r
2624   assert(Source);\r
2625 //  assert(Destination);\r
2626   assert(Scratch);\r
2627   \r
2628   Src     = (UINT8 *)Source;\r
2629   Dst     = (UINT8 *)Destination;\r
2630 \r
2631   Sd      = (SCRATCH_DATA *) Scratch;\r
2632   CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);\r
2633   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);\r
2634   \r
2635   //\r
2636   // If compressed file size is 0, return\r
2637   //\r
2638   if (OrigSize == 0) {\r
2639     return RETURN_SUCCESS;\r
2640   }\r
2641 \r
2642   Src = Src + 8;\r
2643 \r
2644   for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {\r
2645     ((UINT8 *) Sd)[Index] = 0;\r
2646   }\r
2647   //\r
2648   // The length of the field 'Position Set Code Length Array Size' in Block Header.\r
2649   // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4\r
2650   // For Tiano de/compression algorithm(Version 2), mPBit = 5\r
2651   //\r
2652   switch (Version) {\r
2653     case 1 :\r
2654       Sd->mPBit = 4;\r
2655       break;\r
2656     case 2 :\r
2657       Sd->mPBit = 5;\r
2658       break;\r
2659     default:\r
2660       assert(FALSE);\r
2661   }\r
2662   Sd->mSrcBase  = (UINT8 *)Src;\r
2663   Sd->mDstBase  = Dst;\r
2664   Sd->mCompSize = CompSize;\r
2665   Sd->mOrigSize = OrigSize;\r
2666 \r
2667   //\r
2668   // Fill the first BITBUFSIZ bits\r
2669   //\r
2670   FillBuf (Sd, BITBUFSIZ);\r
2671 \r
2672   //\r
2673   // Decompress it\r
2674   //\r
2675   \r
2676   Decode (Sd);\r
2677   \r
2678   if (Sd->mBadTableFlag != 0) {\r
2679     //\r
2680     // Something wrong with the source\r
2681     //\r
2682     return RETURN_INVALID_PARAMETER;\r
2683   }\r
2684 \r
2685   return RETURN_SUCCESS;\r
2686 }\r
2687 \r