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