Tools/CodeTools/Source/Common/EfiDecompress.c

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