]>
git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
21d35e29da3e71cea487e937f991f6af27297036
2 UEFI Decompress Library implementation refer to UEFI specification.
4 Copyright (c) 2006 - 2008, 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
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.
19 #include <Library/BaseLib.h>
20 #include <Library/UefiDecompressLib.h>
21 #include <Library/DebugLib.h>
23 #include "BaseUefiDecompressLibInternals.h"
26 Read NumOfBit of bits from source into mBitBuf.
28 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
30 @param Sd The global scratch data
31 @param NumOfBits The number of bits to shift and read.
41 // Left shift NumOfBits of bits in advance
43 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
46 // Copy data needed in bytes into mSbuBitBuf
48 while (NumOfBits
> Sd
->mBitCount
) {
50 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
52 if (Sd
->mCompSize
> 0) {
54 // Get 1 byte into SubBitBuf
57 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
62 // No more bits from the source, just pad zero bit.
71 // Caculate additional bit count read to update mBitCount
73 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
76 // Copy NumOfBits of bits from mSubBitBuf into mBitBuf
78 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
82 Get NumOfBits of bits out from mBitBuf.
84 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
85 NumOfBits of bits from source. Returns NumOfBits of bits that are
88 @param Sd The global scratch data.
89 @param NumOfBits The number of bits to pop and read.
91 @return The bits that are popped out.
103 // Pop NumOfBits of Bits from Left
105 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
108 // Fill up mBitBuf from source
110 FillBuf (Sd
, NumOfBits
);
116 Creates Huffman Code mapping table according to code length array.
118 Creates Huffman Code mapping table for Extra Set, Char&Len Set
119 and Position Set according to code length array.
121 @param Sd The global scratch data
122 @param NumOfChar Number of symbols in the symbol set
123 @param BitLen Code length array
124 @param TableBits The width of the mapping table
125 @param Table The table to be created
128 @retval BAD_TABLE The table is corrupted.
145 volatile UINT16 Index
;
156 for (Index
= 1; Index
<= 16; Index
++) {
160 for (Index
= 0; Index
< NumOfChar
; Index
++) {
161 Count
[BitLen
[Index
]]++;
166 for (Index
= 1; Index
<= 16; Index
++) {
167 WordOfStart
= Start
[Index
];
168 WordOfCount
= Count
[Index
];
169 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
172 if (Start
[17] != 0) {
174 return (UINT16
) BAD_TABLE
;
177 JuBits
= (UINT16
) (16 - TableBits
);
179 for (Index
= 1; Index
<= TableBits
; Index
++) {
180 Start
[Index
] >>= JuBits
;
181 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
184 while (Index
<= 16) {
185 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
189 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
192 Index3
= (UINT16
) (1U << TableBits
);
193 while (Index
!= Index3
) {
199 Mask
= (UINT16
) (1U << (15 - TableBits
));
201 for (Char
= 0; Char
< NumOfChar
; Char
++) {
208 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
210 if (Len
<= TableBits
) {
212 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
219 Pointer
= &Table
[Index3
>> JuBits
];
220 Index
= (UINT16
) (Len
- TableBits
);
224 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
228 if ((Index3
& Mask
) != 0) {
229 Pointer
= &Sd
->mRight
[*Pointer
];
231 Pointer
= &Sd
->mLeft
[*Pointer
];
242 Start
[Len
] = NextCode
;
251 Decodes a position value.
253 Get a position value according to Position Huffman Table.
255 @param Sd the global scratch data
257 @return The position value decoded.
269 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
272 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
276 if ((Sd
->mBitBuf
& Mask
) != 0) {
277 Val
= Sd
->mRight
[Val
];
279 Val
= Sd
->mLeft
[Val
];
283 } while (Val
>= MAXNP
);
286 // Advance what we have read
288 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
292 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
299 Reads code lengths for the Extra Set or the Position Set.
301 Read in the Extra Set or Pointion Set Length Arrary, then
302 generate the Huffman code mapping for them.
304 @param Sd The global scratch data.
305 @param nn Number of symbols.
306 @param nbit Number of bits needed to represent nn.
307 @param Special The special symbol that needs to be taken care of.
310 @retval BAD_TABLE Table is corrupted.
323 volatile UINT16 Index
;
327 // Read Extra Set Code Length Array size
329 Number
= (UINT16
) GetBits (Sd
, nbit
);
333 // This represents only Huffman code used
335 CharC
= (UINT16
) GetBits (Sd
, nbit
);
337 for (Index
= 0; Index
< 256; Index
++) {
338 Sd
->mPTTable
[Index
] = CharC
;
341 for (Index
= 0; Index
< nn
; Index
++) {
342 Sd
->mPTLen
[Index
] = 0;
350 while (Index
< Number
) {
352 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
355 // If a code length is less than 7, then it is encoded as a 3-bit
356 // value. Or it is encoded as a series of "1"s followed by a
357 // terminating "0". The number of "1"s = Code length - 4.
360 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
361 while (Mask
& Sd
->mBitBuf
) {
367 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
369 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
373 // After the third length of the code length concatenation,
374 // a 2-bit value is used to indicated the number of consecutive
375 // zero lengths after the third length.
377 if (Index
== Special
) {
378 CharC
= (UINT16
) GetBits (Sd
, 2);
379 while ((INT16
) (--CharC
) >= 0) {
380 Sd
->mPTLen
[Index
++] = 0;
386 Sd
->mPTLen
[Index
++] = 0;
389 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
393 Reads code lengths for Char&Len Set.
395 Read in and decode the Char&Len Set Code Length Array, then
396 generate the Huffman Code mapping table for the Char&Len Set.
398 @param Sd the global scratch data
408 volatile UINT16 Index
;
411 Number
= (UINT16
) GetBits (Sd
, CBIT
);
415 // This represents only Huffman code used
417 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
419 for (Index
= 0; Index
< NC
; Index
++) {
420 Sd
->mCLen
[Index
] = 0;
423 for (Index
= 0; Index
< 4096; Index
++) {
424 Sd
->mCTable
[Index
] = CharC
;
431 while (Index
< Number
) {
432 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
434 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
438 if (Mask
& Sd
->mBitBuf
) {
439 CharC
= Sd
->mRight
[CharC
];
441 CharC
= Sd
->mLeft
[CharC
];
446 } while (CharC
>= NT
);
449 // Advance what we have read
451 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
457 } else if (CharC
== 1) {
458 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
459 } else if (CharC
== 2) {
460 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
463 while ((INT16
) (--CharC
) >= 0) {
464 Sd
->mCLen
[Index
++] = 0;
469 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
475 Sd
->mCLen
[Index
++] = 0;
478 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
484 Decode a character/length value.
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
490 @param Sd The global scratch data.
492 @return The value decoded.
503 if (Sd
->mBlockSize
== 0) {
505 // Starting a new block
506 // Read BlockSize from block header
508 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
511 // Read in the Extra Set Code Length Arrary,
512 // Generate the Huffman code mapping table for Extra Set.
514 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
515 if (Sd
->mBadTableFlag
!= 0) {
520 // Read in and decode the Char&Len Set Code Length Arrary,
521 // Generate the Huffman code mapping table for Char&Len Set.
526 // Read in the Position Set Code Length Arrary,
527 // Generate the Huffman code mapping table for the Position Set.
529 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
530 if (Sd
->mBadTableFlag
!= 0) {
536 // Get one code according to Code&Set Huffman Table
539 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
542 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
545 if ((Sd
->mBitBuf
& Mask
) != 0) {
546 Index2
= Sd
->mRight
[Index2
];
548 Index2
= Sd
->mLeft
[Index2
];
552 } while (Index2
>= NC
);
555 // Advance what we have read
557 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
563 Decode the source data and put the resulting data into the destination buffer.
565 @param Sd The global scratch data
577 BytesRemain
= (UINT16
) (-1);
583 // Get one code from mBitBuf
585 CharC
= DecodeC (Sd
);
586 if (Sd
->mBadTableFlag
!= 0) {
592 // Process an Original character
594 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
598 // Write orignal character into mDstBase
600 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
607 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
615 // Locate string position
617 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
620 // Write BytesRemain of bytes into mDstBase
623 while ((INT16
) (BytesRemain
) >= 0) {
624 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
625 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
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.
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.
655 If Source is NULL, then ASSERT().
656 If DestinationSize is NULL, then ASSERT().
657 If ScratchSize is NULL, then ASSERT().
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.
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
679 UefiDecompressGetInfo (
680 IN CONST VOID
*Source
,
681 IN UINT32 SourceSize
,
682 OUT UINT32
*DestinationSize
,
683 OUT UINT32
*ScratchSize
686 UINT32 CompressedSize
;
688 ASSERT (Source
!= NULL
);
689 ASSERT (DestinationSize
!= NULL
);
690 ASSERT (ScratchSize
!= NULL
);
692 if (SourceSize
< 8) {
693 return RETURN_INVALID_PARAMETER
;
696 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
697 if (SourceSize
< (CompressedSize
+ 8)) {
698 return RETURN_INVALID_PARAMETER
;
701 *ScratchSize
= sizeof (SCRATCH_DATA
);
702 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
704 return RETURN_SUCCESS
;
708 Decompresses a compressed source buffer.
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 r
714 esponsibility to allocate and free the Destination and Scratch buffers.
715 If the compressed source data specified by Source is sucessfully 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.
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().
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.
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).
739 IN CONST VOID
*Source
,
740 IN OUT VOID
*Destination
,
741 IN OUT VOID
*Scratch OPTIONAL
744 volatile UINT32 Index
;
751 ASSERT (Source
!= NULL
);
752 ASSERT (Destination
!= NULL
);
753 ASSERT (Scratch
!= NULL
);
758 Sd
= (SCRATCH_DATA
*) Scratch
;
760 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
761 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
764 // If compressed file size is 0, return
767 return RETURN_SUCCESS
;
772 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
773 ((UINT8
*) Sd
)[Index
] = 0;
776 // The length of the field 'Position Set Code Length Array Size' in Block Header.
777 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
780 Sd
->mSrcBase
= (UINT8
*)Src
;
783 // CompSize and OrigSize are caculated in bytes
785 Sd
->mCompSize
= CompSize
;
786 Sd
->mOrigSize
= OrigSize
;
789 // Fill the first BITBUFSIZ bits
791 FillBuf (Sd
, BITBUFSIZ
);
798 if (Sd
->mBadTableFlag
!= 0) {
800 // Something wrong with the source
802 return RETURN_INVALID_PARAMETER
;
805 return RETURN_SUCCESS
;