]>
git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
2 UEFI Decompress Library implementation refer to UEFI specification.
4 Copyright (c) 2006 - 2018, 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
12 #include <Library/BaseLib.h>
13 #include <Library/DebugLib.h>
14 #include <Library/BaseMemoryLib.h>
15 #include <Library/UefiDecompressLib.h>
17 #include "BaseUefiDecompressLibInternals.h"
20 Read NumOfBit of bits from source into mBitBuf.
22 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
24 @param Sd The global scratch data.
25 @param NumOfBits The number of bits to shift and read.
35 // Left shift NumOfBits of bits in advance
37 Sd
->mBitBuf
= (UINT32
) LShiftU64 (((UINT64
)Sd
->mBitBuf
), NumOfBits
);
40 // Copy data needed in bytes into mSbuBitBuf
42 while (NumOfBits
> Sd
->mBitCount
) {
43 NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
);
44 Sd
->mBitBuf
|= (UINT32
) LShiftU64 (((UINT64
)Sd
->mSubBitBuf
), NumOfBits
);
46 if (Sd
->mCompSize
> 0) {
48 // Get 1 byte into SubBitBuf
51 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
56 // No more bits from the source, just pad zero bit.
65 // Calculate additional bit count read to update mBitCount
67 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
70 // Copy NumOfBits of bits from mSubBitBuf into mBitBuf
72 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
76 Get NumOfBits of bits out from mBitBuf.
78 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
79 NumOfBits of bits from source. Returns NumOfBits of bits that are
82 @param Sd The global scratch data.
83 @param NumOfBits The number of bits to pop and read.
85 @return The bits that are popped out.
97 // Pop NumOfBits of Bits from Left
99 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
102 // Fill up mBitBuf from source
104 FillBuf (Sd
, NumOfBits
);
110 Creates Huffman Code mapping table according to code length array.
112 Creates Huffman Code mapping table for Extra Set, Char&Len Set
113 and Position Set according to code length array.
114 If TableBits > 16, then ASSERT ().
116 @param Sd The global scratch data.
117 @param NumOfChar The number of symbols in the symbol set.
118 @param BitLen Code length array.
119 @param TableBits The width of the mapping table.
120 @param Table The table to be created.
123 @retval BAD_TABLE The table is corrupted.
149 UINT16 MaxTableLength
;
152 // The maximum mapping table width supported by this internal
153 // working function is 16.
155 ASSERT (TableBits
<= 16);
157 for (Index
= 0; Index
<= 16; Index
++) {
161 for (Index
= 0; Index
< NumOfChar
; Index
++) {
162 if (BitLen
[Index
] > 16) {
163 return (UINT16
) BAD_TABLE
;
165 Count
[BitLen
[Index
]]++;
171 for (Index
= 1; Index
<= 16; Index
++) {
172 WordOfStart
= Start
[Index
];
173 WordOfCount
= Count
[Index
];
174 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
177 if (Start
[17] != 0) {
179 return (UINT16
) BAD_TABLE
;
182 JuBits
= (UINT16
) (16 - TableBits
);
185 for (Index
= 1; Index
<= TableBits
; Index
++) {
186 Start
[Index
] >>= JuBits
;
187 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
190 while (Index
<= 16) {
191 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
195 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
198 Index3
= (UINT16
) (1U << TableBits
);
199 if (Index
< Index3
) {
200 SetMem16 (Table
+ Index
, (Index3
- Index
) * sizeof (*Table
), 0);
205 Mask
= (UINT16
) (1U << (15 - TableBits
));
206 MaxTableLength
= (UINT16
) (1U << TableBits
);
208 for (Char
= 0; Char
< NumOfChar
; Char
++) {
211 if (Len
== 0 || Len
>= 17) {
215 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
217 if (Len
<= TableBits
) {
219 if (Start
[Len
] >= NextCode
|| NextCode
> MaxTableLength
){
220 return (UINT16
) BAD_TABLE
;
223 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
230 Pointer
= &Table
[Index3
>> JuBits
];
231 Index
= (UINT16
) (Len
- TableBits
);
234 if (*Pointer
== 0 && Avail
< (2 * NC
- 1)) {
235 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
239 if (*Pointer
< (2 * NC
- 1)) {
240 if ((Index3
& Mask
) != 0) {
241 Pointer
= &Sd
->mRight
[*Pointer
];
243 Pointer
= &Sd
->mLeft
[*Pointer
];
255 Start
[Len
] = NextCode
;
264 Decodes a position value.
266 Get a position value according to Position Huffman Table.
268 @param Sd The global scratch data.
270 @return The position value decoded.
282 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
285 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
289 if ((Sd
->mBitBuf
& Mask
) != 0) {
290 Val
= Sd
->mRight
[Val
];
292 Val
= Sd
->mLeft
[Val
];
296 } while (Val
>= MAXNP
);
299 // Advance what we have read
301 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
305 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
312 Reads code lengths for the Extra Set or the Position Set.
314 Read in the Extra Set or Position Set Length Array, then
315 generate the Huffman code mapping for them.
317 @param Sd The global scratch data.
318 @param nn The number of symbols.
319 @param nbit The number of bits needed to represent nn.
320 @param Special The special symbol that needs to be taken care of.
323 @retval BAD_TABLE Table is corrupted.
341 // Read Extra Set Code Length Array size
343 Number
= (UINT16
) GetBits (Sd
, nbit
);
347 // This represents only Huffman code used
349 CharC
= (UINT16
) GetBits (Sd
, nbit
);
351 SetMem16 (&Sd
->mPTTable
[0] , sizeof (Sd
->mPTTable
), CharC
);
353 SetMem (Sd
->mPTLen
, nn
, 0);
360 while (Index
< Number
&& Index
< NPT
) {
362 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
365 // If a code length is less than 7, then it is encoded as a 3-bit
366 // value. Or it is encoded as a series of "1"s followed by a
367 // terminating "0". The number of "1"s = Code length - 4.
370 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
371 while (Mask
& Sd
->mBitBuf
) {
377 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
379 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
383 // After the third length of the code length concatenation,
384 // a 2-bit value is used to indicated the number of consecutive
385 // zero lengths after the third length.
387 if (Index
== Special
) {
388 CharC
= (UINT16
) GetBits (Sd
, 2);
389 while ((INT16
) (--CharC
) >= 0 && Index
< NPT
) {
390 Sd
->mPTLen
[Index
++] = 0;
395 while (Index
< nn
&& Index
< NPT
) {
396 Sd
->mPTLen
[Index
++] = 0;
399 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
403 Reads code lengths for Char&Len Set.
405 Read in and decode the Char&Len Set Code Length Array, then
406 generate the Huffman Code mapping table for the Char&Len Set.
408 @param Sd The global scratch data.
421 Number
= (UINT16
) GetBits (Sd
, CBIT
);
425 // This represents only Huffman code used
427 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
429 SetMem (Sd
->mCLen
, NC
, 0);
430 SetMem16 (&Sd
->mCTable
[0], sizeof (Sd
->mCTable
), CharC
);
436 while (Index
< Number
&& Index
< NC
) {
437 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
439 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
443 if (Mask
& Sd
->mBitBuf
) {
444 CharC
= Sd
->mRight
[CharC
];
446 CharC
= Sd
->mLeft
[CharC
];
451 } while (CharC
>= NT
);
454 // Advance what we have read
456 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
462 } else if (CharC
== 1) {
463 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
464 } else if (CharC
== 2) {
465 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
468 while ((INT16
) (--CharC
) >= 0 && Index
< NC
) {
469 Sd
->mCLen
[Index
++] = 0;
474 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
479 SetMem (Sd
->mCLen
+ Index
, NC
- Index
, 0);
481 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
487 Decode a character/length value.
489 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
490 Huffman code mapping table for Extra Set, Code&Len Set and
493 @param Sd The global scratch data.
495 @return The value decoded.
506 if (Sd
->mBlockSize
== 0) {
508 // Starting a new block
509 // Read BlockSize from block header
511 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
514 // Read in the Extra Set Code Length Array,
515 // Generate the Huffman code mapping table for Extra Set.
517 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
518 if (Sd
->mBadTableFlag
!= 0) {
523 // Read in and decode the Char&Len Set Code Length Array,
524 // Generate the Huffman code mapping table for Char&Len Set.
529 // Read in the Position Set Code Length Array,
530 // Generate the Huffman code mapping table for the Position Set.
532 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
533 if (Sd
->mBadTableFlag
!= 0) {
539 // Get one code according to Code&Set Huffman Table
542 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
545 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
548 if ((Sd
->mBitBuf
& Mask
) != 0) {
549 Index2
= Sd
->mRight
[Index2
];
551 Index2
= Sd
->mLeft
[Index2
];
555 } while (Index2
>= NC
);
558 // Advance what we have read
560 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
566 Decode the source data and put the resulting data into the destination buffer.
568 @param Sd The global scratch data.
580 BytesRemain
= (UINT16
) (-1);
586 // Get one code from mBitBuf
588 CharC
= DecodeC (Sd
);
589 if (Sd
->mBadTableFlag
!= 0) {
595 // Process an Original character
597 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
601 // Write orignal character into mDstBase
603 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
610 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
618 // Locate string position
620 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
623 // Write BytesRemain of bytes into mDstBase
627 while ((INT16
) (BytesRemain
) >= 0) {
628 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
631 if (DataIdx
>= Sd
->mOrigSize
) {
632 Sd
->mBadTableFlag
= (UINT16
) BAD_TABLE
;
635 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
640 // Once mOutBuf is fully filled, directly return
642 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
653 Given a compressed source buffer, this function retrieves the size of
654 the uncompressed buffer and the size of the scratch buffer required
655 to decompress the compressed source buffer.
657 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
658 required to decompress the buffer specified by Source and SourceSize.
659 If the size of the uncompressed buffer or the size of the scratch buffer cannot
660 be determined from the compressed data specified by Source and SourceData,
661 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
662 buffer is returned in DestinationSize, the size of the scratch buffer is returned
663 in ScratchSize, and RETURN_SUCCESS is returned.
664 This function does not have scratch buffer available to perform a thorough
665 checking of the validity of the source data. It just retrieves the "Original Size"
666 field from the beginning bytes of the source data and output it as DestinationSize.
667 And ScratchSize is specific to the decompression implementation.
669 If Source is NULL, then ASSERT().
670 If DestinationSize is NULL, then ASSERT().
671 If ScratchSize is NULL, then ASSERT().
673 @param Source The source buffer containing the compressed data.
674 @param SourceSize The size, in bytes, of the source buffer.
675 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
676 that will be generated when the compressed buffer specified
677 by Source and SourceSize is decompressed.
678 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
679 is required to decompress the compressed buffer specified
680 by Source and SourceSize.
682 @retval RETURN_SUCCESS The size of the uncompressed data was returned
683 in DestinationSize, and the size of the scratch
684 buffer was returned in ScratchSize.
685 @retval RETURN_INVALID_PARAMETER
686 The size of the uncompressed data or the size of
687 the scratch buffer cannot be determined from
688 the compressed data specified by Source
693 UefiDecompressGetInfo (
694 IN CONST VOID
*Source
,
695 IN UINT32 SourceSize
,
696 OUT UINT32
*DestinationSize
,
697 OUT UINT32
*ScratchSize
700 UINT32 CompressedSize
;
702 ASSERT (Source
!= NULL
);
703 ASSERT (DestinationSize
!= NULL
);
704 ASSERT (ScratchSize
!= NULL
);
706 if (SourceSize
< 8) {
707 return RETURN_INVALID_PARAMETER
;
710 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
711 if (SourceSize
< (CompressedSize
+ 8) || (CompressedSize
+ 8) < 8) {
712 return RETURN_INVALID_PARAMETER
;
715 *ScratchSize
= sizeof (SCRATCH_DATA
);
716 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
718 return RETURN_SUCCESS
;
722 Decompresses a compressed source buffer.
724 Extracts decompressed data to its original form.
725 This function is designed so that the decompression algorithm can be implemented
726 without using any memory services. As a result, this function is not allowed to
727 call any memory allocation services in its implementation. It is the caller's
728 responsibility to allocate and free the Destination and Scratch buffers.
729 If the compressed source data specified by Source is successfully decompressed
730 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
731 specified by Source is not in a valid compressed data format,
732 then RETURN_INVALID_PARAMETER is returned.
734 If Source is NULL, then ASSERT().
735 If Destination is NULL, then ASSERT().
736 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
738 @param Source The source buffer containing the compressed data.
739 @param Destination The destination buffer to store the decompressed data.
740 @param Scratch A temporary scratch buffer that is used to perform the decompression.
741 This is an optional parameter that may be NULL if the
742 required scratch buffer size is 0.
744 @retval RETURN_SUCCESS Decompression completed successfully, and
745 the uncompressed buffer is returned in Destination.
746 @retval RETURN_INVALID_PARAMETER
747 The source buffer specified by Source is corrupted
748 (not in a valid compressed format).
753 IN CONST VOID
*Source
,
754 IN OUT VOID
*Destination
,
755 IN OUT VOID
*Scratch OPTIONAL
764 ASSERT (Source
!= NULL
);
765 ASSERT (Destination
!= NULL
);
766 ASSERT (Scratch
!= NULL
);
771 Sd
= (SCRATCH_DATA
*) Scratch
;
773 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
774 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
777 // If compressed file size is 0, return
780 return RETURN_SUCCESS
;
784 SetMem (Sd
, sizeof (SCRATCH_DATA
), 0);
787 // The length of the field 'Position Set Code Length Array Size' in Block Header.
788 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
791 Sd
->mSrcBase
= (UINT8
*)Src
;
794 // CompSize and OrigSize are calculated in bytes
796 Sd
->mCompSize
= CompSize
;
797 Sd
->mOrigSize
= OrigSize
;
800 // Fill the first BITBUFSIZ bits
802 FillBuf (Sd
, BITBUFSIZ
);
809 if (Sd
->mBadTableFlag
!= 0) {
811 // Something wrong with the source
813 return RETURN_INVALID_PARAMETER
;
816 return RETURN_SUCCESS
;