MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c

   1 /** @file
   2   UEFI Decompress Library.
   3
   4   Copyright (c) 2006, Intel Corporation
   5   All rights reserved. This program and the accompanying materials
   6   are licensed and made available under the terms and conditions of the BSD License
   7   which accompanies this distribution.  The full text of the license may be found at
   8   http://opensource.org/licenses/bsd-license.php
   9
  10   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  11   WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  12
  13   Module Name:  UefiDecompressLib.c
  14
  15 **/
  16
  17 //
  18 // Decompression algorithm begins here
  19 //
  20 #define BITBUFSIZ 32
  21 #define MAXMATCH  256
  22 #define THRESHOLD 3
  23 #define CODE_BIT  16
  24 #define BAD_TABLE - 1
  25
  26 //
  27 // C: Char&Len Set; P: Position Set; T: exTra Set
  28 //
  29 #define NC      (0xff + MAXMATCH + 2 - THRESHOLD)
  30 #define CBIT    9
  31 #define MAXPBIT 5
  32 #define TBIT    5
  33 #define MAXNP   ((1U << MAXPBIT) - 1)
  34 #define NT      (CODE_BIT + 3)
  35 #if NT > MAXNP
  36 #define NPT NT
  37 #else
  38 #define NPT MAXNP
  39 #endif
  40
  41 typedef struct {
  42   UINT8   *mSrcBase;  ///< Starting address of compressed data
  43   UINT8   *mDstBase;  ///< Starting address of decompressed data
  44   UINT32  mOutBuf;
  45   UINT32  mInBuf;
  46
  47   UINT16  mBitCount;
  48   UINT32  mBitBuf;
  49   UINT32  mSubBitBuf;
  50   UINT16  mBlockSize;
  51   UINT32  mCompSize;
  52   UINT32  mOrigSize;
  53
  54   UINT16  mBadTableFlag;
  55
  56   UINT16  mLeft[2 * NC - 1];
  57   UINT16  mRight[2 * NC - 1];
  58   UINT8   mCLen[NC];
  59   UINT8   mPTLen[NPT];
  60   UINT16  mCTable[4096];
  61   UINT16  mPTTable[256];
  62
  63   ///
  64   /// The length of the field 'Position Set Code Length Array Size' in Block Header.
  65   /// For EFI 1.1 de/compression algorithm, mPBit = 4
  66   /// For Tiano de/compression algorithm, mPBit = 5
  67   ///
  68   UINT8   mPBit;
  69 } SCRATCH_DATA;
  70
  71 /**
  72   Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
  73
  74   @param  Sd The global scratch data
  75   @param  NumOfBits The number of bits to shift and read.
  76
  77 **/
  78 VOID
  79 FillBuf (
  80   IN  SCRATCH_DATA  *Sd,
  81   IN  UINT16        NumOfBits
  82   )
  83 {
  84   Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
  85
  86   while (NumOfBits > Sd->mBitCount) {
  87
  88     Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
  89
  90     if (Sd->mCompSize > 0) {
  91       //
  92       // Get 1 byte into SubBitBuf
  93       //
  94       Sd->mCompSize--;
  95       Sd->mSubBitBuf  = 0;
  96       Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];
  97       Sd->mBitCount   = 8;
  98
  99     } else {
 100       //
 101       // No more bits from the source, just pad zero bit.
 102       //
 103       Sd->mSubBitBuf  = 0;
 104       Sd->mBitCount   = 8;
 105
 106     }
 107   }
 108
 109   Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
 110   Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
 111 }
 112
 113 /**
 114   Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
 115   NumOfBits of bits from source. Returns NumOfBits of bits that are
 116   popped out.
 117
 118   @param  Sd The global scratch data.
 119   @param  NumOfBits The number of bits to pop and read.
 120
 121   @return The bits that are popped out.
 122
 123 **/
 124 UINT32
 125 GetBits (
 126   IN  SCRATCH_DATA  *Sd,
 127   IN  UINT16        NumOfBits
 128   )
 129 {
 130   UINT32  OutBits;
 131
 132   OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
 133
 134   FillBuf (Sd, NumOfBits);
 135
 136   return OutBits;
 137 }
 138
 139 /**
 140   Creates Huffman Code mapping table according to code length array.
 141
 142   @param  Sd The global scratch data
 143   @param  NumOfChar Number of symbols in the symbol set
 144   @param  BitLen Code length array
 145   @param  TableBits The width of the mapping table
 146   @param  Table The table
 147
 148   @retval  0 OK.
 149   @retval  BAD_TABLE The table is corrupted.
 150
 151 **/
 152 UINT16
 153 MakeTable (
 154   IN  SCRATCH_DATA  *Sd,
 155   IN  UINT16        NumOfChar,
 156   IN  UINT8         *BitLen,
 157   IN  UINT16        TableBits,
 158   OUT UINT16        *Table
 159   )
 160 {
 161   UINT16  Count[17];
 162   UINT16  Weight[17];
 163   UINT16  Start[18];
 164   UINT16  *Pointer;
 165   UINT16  Index3;
 166   volatile UINT16  Index;
 167   UINT16  Len;
 168   UINT16  Char;
 169   UINT16  JuBits;
 170   UINT16  Avail;
 171   UINT16  NextCode;
 172   UINT16  Mask;
 173
 174   for (Index = 1; Index <= 16; Index++) {
 175     Count[Index] = 0;
 176   }
 177
 178   for (Index = 0; Index < NumOfChar; Index++) {
 179     Count[BitLen[Index]]++;
 180   }
 181
 182   Start[1] = 0;
 183
 184   for (Index = 1; Index <= 16; Index++) {
 185     Start[Index + 1] = (UINT16) (Start[Index] + (Count[Index] << (16 - Index)));
 186   }
 187
 188   if (Start[17] != 0) {
 189     /*(1U << 16)*/
 190     return (UINT16) BAD_TABLE;
 191   }
 192
 193   JuBits = (UINT16) (16 - TableBits);
 194
 195   for (Index = 1; Index <= TableBits; Index++) {
 196     Start[Index] >>= JuBits;
 197     Weight[Index] = (UINT16) (1U << (TableBits - Index));
 198   }
 199
 200   while (Index <= 16) {
 201     Weight[Index] = (UINT16) (1U << (16 - Index));
 202     Index++;
 203   }
 204
 205   Index = (UINT16) (Start[TableBits + 1] >> JuBits);
 206
 207   if (Index != 0) {
 208     Index3 = (UINT16) (1U << TableBits);
 209     while (Index != Index3) {
 210       Table[Index++] = 0;
 211     }
 212   }
 213
 214   Avail = NumOfChar;
 215   Mask  = (UINT16) (1U << (15 - TableBits));
 216
 217   for (Char = 0; Char < NumOfChar; Char++) {
 218
 219     Len = BitLen[Char];
 220     if (Len == 0) {
 221       continue;
 222     }
 223
 224     NextCode = (UINT16) (Start[Len] + Weight[Len]);
 225
 226     if (Len <= TableBits) {
 227
 228       for (Index = Start[Len]; Index < NextCode; Index++) {
 229         Table[Index] = Char;
 230       }
 231
 232     } else {
 233
 234       Index3  = Start[Len];
 235       Pointer = &Table[Index3 >> JuBits];
 236       Index   = (UINT16) (Len - TableBits);
 237
 238       while (Index != 0) {
 239         if (*Pointer == 0) {
 240           Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;
 241           *Pointer = Avail++;
 242         }
 243
 244         if (Index3 & Mask) {
 245           Pointer = &Sd->mRight[*Pointer];
 246         } else {
 247           Pointer = &Sd->mLeft[*Pointer];
 248         }
 249
 250         Index3 <<= 1;
 251         Index--;
 252       }
 253
 254       *Pointer = Char;
 255
 256     }
 257
 258     Start[Len] = NextCode;
 259   }
 260   //
 261   // Succeeds
 262   //
 263   return 0;
 264 }
 265
 266 /**
 267   Decodes a position value.
 268
 269   @param  Sd the global scratch data
 270
 271   @return The position value decoded.
 272
 273 **/
 274 UINT32
 275 DecodeP (
 276   IN  SCRATCH_DATA  *Sd
 277   )
 278 {
 279   UINT16  Val;
 280   UINT32  Mask;
 281   UINT32  Pos;
 282
 283   Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
 284
 285   if (Val >= MAXNP) {
 286     Mask = 1U << (BITBUFSIZ - 1 - 8);
 287
 288     do {
 289
 290       if (Sd->mBitBuf & Mask) {
 291         Val = Sd->mRight[Val];
 292       } else {
 293         Val = Sd->mLeft[Val];
 294       }
 295
 296       Mask >>= 1;
 297     } while (Val >= MAXNP);
 298   }
 299   //
 300   // Advance what we have read
 301   //
 302   FillBuf (Sd, Sd->mPTLen[Val]);
 303
 304   Pos = Val;
 305   if (Val > 1) {
 306     Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
 307   }
 308
 309   return Pos;
 310 }
 311
 312 /**
 313   Reads code lengths for the Extra Set or the Position Set.
 314
 315   @param  Sd The global scratch data.
 316   @param  nn Number of symbols.
 317   @param  nbit Number of bits needed to represent nn.
 318   @param  Special The special symbol that needs to be taken care of.
 319
 320   @retval  0 OK.
 321   @retval  BAD_TABLE Table is corrupted.
 322
 323 **/
 324 UINT16
 325 ReadPTLen (
 326   IN  SCRATCH_DATA  *Sd,
 327   IN  UINT16        nn,
 328   IN  UINT16        nbit,
 329   IN  UINT16        Special
 330   )
 331 {
 332   UINT16  Number;
 333   UINT16  CharC;
 334   volatile UINT16  Index;
 335   UINT32  Mask;
 336
 337   Number = (UINT16) GetBits (Sd, nbit);
 338
 339   if (Number == 0) {
 340     CharC = (UINT16) GetBits (Sd, nbit);
 341
 342     for (Index = 0; Index < 256; Index++) {
 343       Sd->mPTTable[Index] = CharC;
 344     }
 345
 346     for (Index = 0; Index < nn; Index++) {
 347       Sd->mPTLen[Index] = 0;
 348     }
 349
 350     return 0;
 351   }
 352
 353   Index = 0;
 354
 355   while (Index < Number) {
 356
 357     CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
 358
 359     if (CharC == 7) {
 360       Mask = 1U << (BITBUFSIZ - 1 - 3);
 361       while (Mask & Sd->mBitBuf) {
 362         Mask >>= 1;
 363         CharC += 1;
 364       }
 365     }
 366
 367     FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
 368
 369     Sd->mPTLen[Index++] = (UINT8) CharC;
 370
 371     if (Index == Special) {
 372       CharC = (UINT16) GetBits (Sd, 2);
 373       while ((INT16) (--CharC) >= 0) {
 374         Sd->mPTLen[Index++] = 0;
 375       }
 376     }
 377   }
 378
 379   while (Index < nn) {
 380     Sd->mPTLen[Index++] = 0;
 381   }
 382
 383   return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
 384 }
 385
 386 /**
 387   Reads code lengths for Char&Len Set.
 388
 389   @param  Sd the global scratch data
 390
 391 **/
 392 VOID
 393 ReadCLen (
 394   SCRATCH_DATA  *Sd
 395   )
 396 {
 397   UINT16  Number;
 398   UINT16  CharC;
 399   volatile UINT16  Index;
 400   UINT32  Mask;
 401
 402   Number = (UINT16) GetBits (Sd, CBIT);
 403
 404   if (Number == 0) {
 405     CharC = (UINT16) GetBits (Sd, CBIT);
 406
 407     for (Index = 0; Index < NC; Index++) {
 408       Sd->mCLen[Index] = 0;
 409     }
 410
 411     for (Index = 0; Index < 4096; Index++) {
 412       Sd->mCTable[Index] = CharC;
 413     }
 414
 415     return ;
 416   }
 417
 418   Index = 0;
 419   while (Index < Number) {
 420
 421     CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
 422     if (CharC >= NT) {
 423       Mask = 1U << (BITBUFSIZ - 1 - 8);
 424
 425       do {
 426
 427         if (Mask & Sd->mBitBuf) {
 428           CharC = Sd->mRight[CharC];
 429         } else {
 430           CharC = Sd->mLeft[CharC];
 431         }
 432
 433         Mask >>= 1;
 434
 435       } while (CharC >= NT);
 436     }
 437     //
 438     // Advance what we have read
 439     //
 440     FillBuf (Sd, Sd->mPTLen[CharC]);
 441
 442     if (CharC <= 2) {
 443
 444       if (CharC == 0) {
 445         CharC = 1;
 446       } else if (CharC == 1) {
 447         CharC = (UINT16) (GetBits (Sd, 4) + 3);
 448       } else if (CharC == 2) {
 449         CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
 450       }
 451
 452       while ((INT16) (--CharC) >= 0) {
 453         Sd->mCLen[Index++] = 0;
 454       }
 455
 456     } else {
 457
 458       Sd->mCLen[Index++] = (UINT8) (CharC - 2);
 459
 460     }
 461   }
 462
 463   while (Index < NC) {
 464     Sd->mCLen[Index++] = 0;
 465   }
 466
 467   MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
 468
 469   return ;
 470 }
 471
 472 /**
 473   Decode a character/length value.
 474
 475   @param  Sd The global scratch data.
 476
 477   @return The value decoded.
 478
 479 **/
 480 UINT16
 481 DecodeC (
 482   SCRATCH_DATA  *Sd
 483   )
 484 {
 485   UINT16  Index2;
 486   UINT32  Mask;
 487
 488   if (Sd->mBlockSize == 0) {
 489     //
 490     // Starting a new block
 491     //
 492     Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);
 493     Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
 494     if (Sd->mBadTableFlag != 0) {
 495       return 0;
 496     }
 497
 498     ReadCLen (Sd);
 499
 500     Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
 501     if (Sd->mBadTableFlag != 0) {
 502       return 0;
 503     }
 504   }
 505
 506   Sd->mBlockSize--;
 507   Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
 508
 509   if (Index2 >= NC) {
 510     Mask = 1U << (BITBUFSIZ - 1 - 12);
 511
 512     do {
 513       if (Sd->mBitBuf & Mask) {
 514         Index2 = Sd->mRight[Index2];
 515       } else {
 516         Index2 = Sd->mLeft[Index2];
 517       }
 518
 519       Mask >>= 1;
 520     } while (Index2 >= NC);
 521   }
 522   //
 523   // Advance what we have read
 524   //
 525   FillBuf (Sd, Sd->mCLen[Index2]);
 526
 527   return Index2;
 528 }
 529
 530 /**
 531   Decode the source data and put the resulting data into the destination buffer.
 532
 533   @param  Sd The global scratch data
 534
 535 **/
 536 VOID
 537 Decode (
 538   SCRATCH_DATA  *Sd
 539   )
 540 {
 541   UINT16  BytesRemain;
 542   UINT32  DataIdx;
 543   UINT16  CharC;
 544
 545   BytesRemain = (UINT16) (-1);
 546
 547   DataIdx     = 0;
 548
 549   for (;;) {
 550     CharC = DecodeC (Sd);
 551     if (Sd->mBadTableFlag != 0) {
 552       return ;
 553     }
 554
 555     if (CharC < 256) {
 556       //
 557       // Process an Original character
 558       //
 559       if (Sd->mOutBuf >= Sd->mOrigSize) {
 560         return ;
 561       } else {
 562         Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
 563       }
 564
 565     } else {
 566       //
 567       // Process a Pointer
 568       //
 569       CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
 570
 571       BytesRemain = CharC;
 572
 573       DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;
 574
 575       BytesRemain--;
 576       while ((INT16) (BytesRemain) >= 0) {
 577         Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
 578         if (Sd->mOutBuf >= Sd->mOrigSize) {
 579           return ;
 580         }
 581
 582         BytesRemain--;
 583       }
 584     }
 585   }
 586
 587   return ;
 588 }
 589
 590 /**
 591   The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
 592
 593   @param  Source The source buffer containing the compressed data.
 594   @param  SourceSize The size of source buffer
 595   @param  DestinationSize The size of destination buffer.
 596   @param  ScratchSize The size of scratch buffer.
 597
 598   @retval  RETURN_SUCCESS The size of destination buffer and the size of scratch buffer are successull retrieved.
 599   @retval  RETURN_INVALID_PARAMETER The source data is corrupted
 600
 601 **/
 602 RETURN_STATUS
 603 EFIAPI
 604 UefiDecompressGetInfo (
 605   IN  CONST VOID  *Source,
 606   IN  UINT32      SourceSize,
 607   OUT UINT32      *DestinationSize,
 608   OUT UINT32      *ScratchSize
 609   )
 610 {
 611   UINT32  CompressedSize;
 612
 613   ASSERT (Source != NULL);
 614   ASSERT (DestinationSize != NULL);
 615   ASSERT (ScratchSize != NULL);
 616
 617   *ScratchSize  = sizeof (SCRATCH_DATA);
 618
 619   if (SourceSize < 8) {
 620     return RETURN_INVALID_PARAMETER;
 621   }
 622
 623   CopyMem (&CompressedSize, Source, sizeof (UINT32));
 624   CopyMem (DestinationSize, (VOID *)((UINT8 *)Source + 4), sizeof (UINT32));
 625
 626   if (SourceSize < (CompressedSize + 8)) {
 627     return RETURN_INVALID_PARAMETER;
 628   }
 629
 630   return RETURN_SUCCESS;
 631 }
 632
 633 /**
 634   The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
 635
 636   @param  Source The source buffer containing the compressed data.
 637   @param  Destination The destination buffer to store the decompressed data
 638   @param  Scratch The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.
 639
 640   @retval  RETURN_SUCCESS Decompression is successfull
 641   @retval  RETURN_INVALID_PARAMETER The source data is corrupted
 642
 643 **/
 644 RETURN_STATUS
 645 EFIAPI
 646 UefiDecompress (
 647   IN CONST VOID  *Source,
 648   IN OUT VOID    *Destination,
 649   IN OUT VOID    *Scratch
 650   )
 651 {
 652   volatile UINT32  Index;
 653   UINT32           CompSize;
 654   UINT32           OrigSize;
 655   SCRATCH_DATA     *Sd;
 656   CONST UINT8      *Src;
 657   UINT8            *Dst;
 658
 659   ASSERT (Source != NULL);
 660   ASSERT (Destination != NULL);
 661   ASSERT (Scratch != NULL);
 662
 663   Src     = Source;
 664   Dst     = Destination;
 665
 666   Sd = (SCRATCH_DATA *) Scratch;
 667
 668   CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
 669   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
 670
 671   //
 672   // If compressed file size is 0, return
 673   //
 674   if (OrigSize == 0) {
 675     return RETURN_SUCCESS;
 676   }
 677
 678   Src = Src + 8;
 679
 680   for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
 681     ((UINT8 *) Sd)[Index] = 0;
 682   }
 683   //
 684   // The length of the field 'Position Set Code Length Array Size' in Block Header.
 685   // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
 686   // For Tiano de/compression algorithm(Version 2), mPBit = 5
 687   //
 688   Sd->mPBit     = 4;
 689   Sd->mSrcBase  = (UINT8 *)Src;
 690   Sd->mDstBase  = Dst;
 691   Sd->mCompSize = CompSize;
 692   Sd->mOrigSize = OrigSize;
 693
 694   //
 695   // Fill the first BITBUFSIZ bits
 696   //
 697   FillBuf (Sd, BITBUFSIZ);
 698
 699   //
 700   // Decompress it
 701   //
 702   Decode (Sd);
 703
 704   if (Sd->mBadTableFlag != 0) {
 705     //
 706     // Something wrong with the source
 707     //
 708     return RETURN_INVALID_PARAMETER;
 709   }
 710
 711   return RETURN_SUCCESS;
 712 }