]>
git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
2f0a0c8c4507ecc96ccc1c3ca18e9cdd1c79d0c8
2 UEFI Decompress Library implementation refer to UEFI specification.
4 Copyright (c) 2006 - 2019, Intel Corporation. All rights reserved.<BR>
5 Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
6 SPDX-License-Identifier: BSD-2-Clause-Patent
10 #include "BaseUefiDecompressLibInternals.h"
13 Read NumOfBit of bits from source into mBitBuf.
15 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
17 @param Sd The global scratch data.
18 @param NumOfBits The number of bits to shift and read.
28 // Left shift NumOfBits of bits in advance
30 Sd
->mBitBuf
= (UINT32
)LShiftU64 (((UINT64
)Sd
->mBitBuf
), NumOfBits
);
33 // Copy data needed in bytes into mSbuBitBuf
35 while (NumOfBits
> Sd
->mBitCount
) {
36 NumOfBits
= (UINT16
)(NumOfBits
- Sd
->mBitCount
);
37 Sd
->mBitBuf
|= (UINT32
)LShiftU64 (((UINT64
)Sd
->mSubBitBuf
), NumOfBits
);
39 if (Sd
->mCompSize
> 0) {
41 // Get 1 byte into SubBitBuf
44 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
48 // No more bits from the source, just pad zero bit.
56 // Calculate additional bit count read to update mBitCount
58 Sd
->mBitCount
= (UINT16
)(Sd
->mBitCount
- NumOfBits
);
61 // Copy NumOfBits of bits from mSubBitBuf into mBitBuf
63 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
67 Get NumOfBits of bits out from mBitBuf.
69 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
70 NumOfBits of bits from source. Returns NumOfBits of bits that are
73 @param Sd The global scratch data.
74 @param NumOfBits The number of bits to pop and read.
76 @return The bits that are popped out.
88 // Pop NumOfBits of Bits from Left
90 OutBits
= (UINT32
)(Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
93 // Fill up mBitBuf from source
95 FillBuf (Sd
, NumOfBits
);
101 Creates Huffman Code mapping table according to code length array.
103 Creates Huffman Code mapping table for Extra Set, Char&Len Set
104 and Position Set according to code length array.
105 If TableBits > 16, then ASSERT ().
107 @param Sd The global scratch data.
108 @param NumOfChar The number of symbols in the symbol set.
109 @param BitLen Code length array.
110 @param TableBits The width of the mapping table.
111 @param Table The table to be created.
114 @retval BAD_TABLE The table is corrupted.
140 UINT16 MaxTableLength
;
143 // The maximum mapping table width supported by this internal
144 // working function is 16.
146 ASSERT (TableBits
<= 16);
148 for (Index
= 0; Index
<= 16; Index
++) {
152 for (Index
= 0; Index
< NumOfChar
; Index
++) {
153 if (BitLen
[Index
] > 16) {
154 return (UINT16
)BAD_TABLE
;
157 Count
[BitLen
[Index
]]++;
163 for (Index
= 1; Index
<= 16; Index
++) {
164 WordOfStart
= Start
[Index
];
165 WordOfCount
= Count
[Index
];
166 Start
[Index
+ 1] = (UINT16
)(WordOfStart
+ (WordOfCount
<< (16 - Index
)));
169 if (Start
[17] != 0) {
171 return (UINT16
)BAD_TABLE
;
174 JuBits
= (UINT16
)(16 - TableBits
);
177 for (Index
= 1; Index
<= TableBits
; Index
++) {
178 Start
[Index
] >>= JuBits
;
179 Weight
[Index
] = (UINT16
)(1U << (TableBits
- Index
));
182 while (Index
<= 16) {
183 Weight
[Index
] = (UINT16
)(1U << (16 - Index
));
187 Index
= (UINT16
)(Start
[TableBits
+ 1] >> JuBits
);
190 Index3
= (UINT16
)(1U << TableBits
);
191 if (Index
< Index3
) {
192 SetMem16 (Table
+ Index
, (Index3
- Index
) * sizeof (*Table
), 0);
197 Mask
= (UINT16
)(1U << (15 - TableBits
));
198 MaxTableLength
= (UINT16
)(1U << TableBits
);
200 for (Char
= 0; Char
< NumOfChar
; Char
++) {
202 if ((Len
== 0) || (Len
>= 17)) {
206 NextCode
= (UINT16
)(Start
[Len
] + Weight
[Len
]);
208 if (Len
<= TableBits
) {
209 if ((Start
[Len
] >= NextCode
) || (NextCode
> MaxTableLength
)) {
210 return (UINT16
)BAD_TABLE
;
213 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
218 Pointer
= &Table
[Index3
>> JuBits
];
219 Index
= (UINT16
)(Len
- TableBits
);
222 if ((*Pointer
== 0) && (Avail
< (2 * NC
- 1))) {
223 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
227 if (*Pointer
< (2 * NC
- 1)) {
228 if ((Index3
& Mask
) != 0) {
229 Pointer
= &Sd
->mRight
[*Pointer
];
231 Pointer
= &Sd
->mLeft
[*Pointer
];
242 Start
[Len
] = NextCode
;
252 Decodes a position value.
254 Get a position value according to Position Huffman Table.
256 @param Sd The global scratch data.
258 @return The position value decoded.
270 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
273 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
);
287 // Advance what we have read
289 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
293 Pos
= (UINT32
)((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
)(Val
- 1)));
300 Reads code lengths for the Extra Set or the Position Set.
302 Read in the Extra Set or Position Set Length Array, then
303 generate the Huffman code mapping for them.
305 @param Sd The global scratch data.
306 @param nn The number of symbols.
307 @param nbit The number of bits needed to represent nn.
308 @param Special The special symbol that needs to be taken care of.
311 @retval BAD_TABLE Table is corrupted.
329 // Read Extra Set Code Length Array size
331 Number
= (UINT16
)GetBits (Sd
, nbit
);
335 // This represents only Huffman code used
337 CharC
= (UINT16
)GetBits (Sd
, nbit
);
339 SetMem16 (&Sd
->mPTTable
[0], sizeof (Sd
->mPTTable
), CharC
);
341 SetMem (Sd
->mPTLen
, nn
, 0);
348 while (Index
< Number
&& Index
< NPT
) {
349 CharC
= (UINT16
)(Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
352 // If a code length is less than 7, then it is encoded as a 3-bit
353 // value. Or it is encoded as a series of "1"s followed by a
354 // terminating "0". The number of "1"s = Code length - 4.
357 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
358 while (Mask
& Sd
->mBitBuf
) {
364 FillBuf (Sd
, (UINT16
)((CharC
< 7) ? 3 : CharC
- 3));
366 Sd
->mPTLen
[Index
++] = (UINT8
)CharC
;
370 // After the third length of the code length concatenation,
371 // a 2-bit value is used to indicated the number of consecutive
372 // zero lengths after the third length.
374 if (Index
== Special
) {
375 CharC
= (UINT16
)GetBits (Sd
, 2);
376 while ((INT16
)(--CharC
) >= 0 && Index
< NPT
) {
377 Sd
->mPTLen
[Index
++] = 0;
382 while (Index
< nn
&& Index
< NPT
) {
383 Sd
->mPTLen
[Index
++] = 0;
386 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
390 Reads code lengths for Char&Len Set.
392 Read in and decode the Char&Len Set Code Length Array, then
393 generate the Huffman Code mapping table for the Char&Len Set.
395 @param Sd The global scratch data.
408 Number
= (UINT16
)GetBits (Sd
, CBIT
);
412 // This represents only Huffman code used
414 CharC
= (UINT16
)GetBits (Sd
, CBIT
);
416 SetMem (Sd
->mCLen
, NC
, 0);
417 SetMem16 (&Sd
->mCTable
[0], sizeof (Sd
->mCTable
), CharC
);
423 while (Index
< Number
&& Index
< NC
) {
424 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
426 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
429 if (Mask
& Sd
->mBitBuf
) {
430 CharC
= Sd
->mRight
[CharC
];
432 CharC
= Sd
->mLeft
[CharC
];
436 } while (CharC
>= NT
);
440 // Advance what we have read
442 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
447 } else if (CharC
== 1) {
448 CharC
= (UINT16
)(GetBits (Sd
, 4) + 3);
449 } else if (CharC
== 2) {
450 CharC
= (UINT16
)(GetBits (Sd
, CBIT
) + 20);
453 while ((INT16
)(--CharC
) >= 0 && Index
< NC
) {
454 Sd
->mCLen
[Index
++] = 0;
457 Sd
->mCLen
[Index
++] = (UINT8
)(CharC
- 2);
461 SetMem (Sd
->mCLen
+ Index
, NC
- Index
, 0);
463 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
469 Decode a character/length value.
471 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
472 Huffman code mapping table for Extra Set, Code&Len Set and
475 @param Sd The global scratch data.
477 @return The value decoded.
488 if (Sd
->mBlockSize
== 0) {
490 // Starting a new block
491 // Read BlockSize from block header
493 Sd
->mBlockSize
= (UINT16
)GetBits (Sd
, 16);
496 // Read in the Extra Set Code Length Array,
497 // Generate the Huffman code mapping table for Extra Set.
499 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
500 if (Sd
->mBadTableFlag
!= 0) {
505 // Read in and decode the Char&Len Set Code Length Array,
506 // Generate the Huffman code mapping table for Char&Len Set.
511 // Read in the Position Set Code Length Array,
512 // Generate the Huffman code mapping table for the Position Set.
514 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
)(-1));
515 if (Sd
->mBadTableFlag
!= 0) {
521 // Get one code according to Code&Set Huffman Table
524 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
527 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
530 if ((Sd
->mBitBuf
& Mask
) != 0) {
531 Index2
= Sd
->mRight
[Index2
];
533 Index2
= Sd
->mLeft
[Index2
];
537 } while (Index2
>= NC
);
541 // Advance what we have read
543 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
549 Decode the source data and put the resulting data into the destination buffer.
551 @param Sd The global scratch data.
563 BytesRemain
= (UINT16
)(-1);
569 // Get one code from mBitBuf
571 CharC
= DecodeC (Sd
);
572 if (Sd
->mBadTableFlag
!= 0) {
578 // Process an Original character
580 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
584 // Write orignal character into mDstBase
586 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
)CharC
;
592 CharC
= (UINT16
)(CharC
- (BIT8
- THRESHOLD
));
600 // Locate string position
602 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
605 // Write BytesRemain of bytes into mDstBase
609 while ((INT16
)(BytesRemain
) >= 0) {
610 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
614 if (DataIdx
>= Sd
->mOrigSize
) {
615 Sd
->mBadTableFlag
= (UINT16
)BAD_TABLE
;
619 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
625 // Once mOutBuf is fully filled, directly return
627 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
638 Given a compressed source buffer, this function retrieves the size of
639 the uncompressed buffer and the size of the scratch buffer required
640 to decompress the compressed source buffer.
642 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
643 required to decompress the buffer specified by Source and SourceSize.
644 If the size of the uncompressed buffer or the size of the scratch buffer cannot
645 be determined from the compressed data specified by Source and SourceData,
646 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
647 buffer is returned in DestinationSize, the size of the scratch buffer is returned
648 in ScratchSize, and RETURN_SUCCESS is returned.
649 This function does not have scratch buffer available to perform a thorough
650 checking of the validity of the source data. It just retrieves the "Original Size"
651 field from the beginning bytes of the source data and output it as DestinationSize.
652 And ScratchSize is specific to the decompression implementation.
654 If Source is NULL, then ASSERT().
655 If DestinationSize is NULL, then ASSERT().
656 If ScratchSize is NULL, then ASSERT().
658 @param Source The source buffer containing the compressed data.
659 @param SourceSize The size, in bytes, of the source buffer.
660 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
661 that will be generated when the compressed buffer specified
662 by Source and SourceSize is decompressed.
663 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
664 is required to decompress the compressed buffer specified
665 by Source and SourceSize.
667 @retval RETURN_SUCCESS The size of the uncompressed data was returned
668 in DestinationSize, and the size of the scratch
669 buffer was returned in ScratchSize.
670 @retval RETURN_INVALID_PARAMETER
671 The size of the uncompressed data or the size of
672 the scratch buffer cannot be determined from
673 the compressed data specified by Source
678 UefiDecompressGetInfo (
679 IN CONST VOID
*Source
,
680 IN UINT32 SourceSize
,
681 OUT UINT32
*DestinationSize
,
682 OUT UINT32
*ScratchSize
685 UINT32 CompressedSize
;
687 ASSERT (Source
!= NULL
);
688 ASSERT (DestinationSize
!= NULL
);
689 ASSERT (ScratchSize
!= NULL
);
691 if (SourceSize
< 8) {
692 return RETURN_INVALID_PARAMETER
;
695 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
696 if ((SourceSize
< (CompressedSize
+ 8)) || ((CompressedSize
+ 8) < 8)) {
697 return RETURN_INVALID_PARAMETER
;
700 *ScratchSize
= sizeof (SCRATCH_DATA
);
701 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
703 return RETURN_SUCCESS
;
707 Decompresses a compressed source buffer.
709 Extracts decompressed data to its original form.
710 This function is designed so that the decompression algorithm can be implemented
711 without using any memory services. As a result, this function is not allowed to
712 call any memory allocation services in its implementation. It is the caller's
713 responsibility to allocate and free the Destination and Scratch buffers.
714 If the compressed source data specified by Source is successfully decompressed
715 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
716 specified by Source is not in a valid compressed data format,
717 then RETURN_INVALID_PARAMETER is returned.
719 If Source is NULL, then ASSERT().
720 If Destination is NULL, then ASSERT().
721 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
722 If the Version is not 1 or 2, 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.
729 @param Version 1 for UEFI Decompress algoruthm, 2 for Tiano Decompess algorithm.
731 @retval RETURN_SUCCESS Decompression completed successfully, and
732 the uncompressed buffer is returned in Destination.
733 @retval RETURN_INVALID_PARAMETER
734 The source buffer specified by Source is corrupted
735 (not in a valid compressed format).
738 UefiTianoDecompress (
739 IN CONST VOID
*Source
,
740 IN OUT VOID
*Destination
,
741 IN OUT VOID
*Scratch
,
751 ASSERT (Source
!= NULL
);
752 ASSERT (Destination
!= NULL
);
753 ASSERT (Scratch
!= NULL
);
754 ASSERT (Version
== 1 || Version
== 2);
759 Sd
= (SCRATCH_DATA
*)Scratch
;
761 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
762 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
765 // If compressed file size is 0, return
768 return RETURN_SUCCESS
;
772 SetMem (Sd
, sizeof (SCRATCH_DATA
), 0);
775 // The length of the field 'Position Set Code Length Array Size' in Block Header.
776 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
777 // For Tiano de/compression algorithm(Version 2), mPBit = 5
790 Sd
->mSrcBase
= (UINT8
*)Src
;
793 // CompSize and OrigSize are calculated in bytes
795 Sd
->mCompSize
= CompSize
;
796 Sd
->mOrigSize
= OrigSize
;
799 // Fill the first BITBUFSIZ bits
801 FillBuf (Sd
, BITBUFSIZ
);
808 if (Sd
->mBadTableFlag
!= 0) {
810 // Something wrong with the source
812 return RETURN_INVALID_PARAMETER
;
815 return RETURN_SUCCESS
;
819 Decompresses a UEFI compressed source buffer.
821 Extracts decompressed data to its original form.
822 This function is designed so that the decompression algorithm can be implemented
823 without using any memory services. As a result, this function is not allowed to
824 call any memory allocation services in its implementation. It is the caller's
825 responsibility to allocate and free the Destination and Scratch buffers.
826 If the compressed source data specified by Source is successfully decompressed
827 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
828 specified by Source is not in a valid compressed data format,
829 then RETURN_INVALID_PARAMETER is returned.
831 If Source is NULL, then ASSERT().
832 If Destination is NULL, then ASSERT().
833 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
835 @param Source The source buffer containing the compressed data.
836 @param Destination The destination buffer to store the decompressed data
837 @param Scratch A temporary scratch buffer that is used to perform the decompression.
838 This is an optional parameter that may be NULL if the
839 required scratch buffer size is 0.
841 @retval RETURN_SUCCESS Decompression completed successfully, and
842 the uncompressed buffer is returned in Destination.
843 @retval RETURN_INVALID_PARAMETER
844 The source buffer specified by Source is corrupted
845 (not in a valid compressed format).
850 IN CONST VOID
*Source
,
851 IN OUT VOID
*Destination
,
852 IN OUT VOID
*Scratch OPTIONAL
855 return UefiTianoDecompress (Source
, Destination
, Scratch
, 1);