]>
git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
9fc637e0582e163eef0c87137a19676cf7915183
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 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.
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.
18 #include <Library/BaseLib.h>
19 #include <Library/DebugLib.h>
20 #include <Library/BaseMemoryLib.h>
21 #include <Library/UefiDecompressLib.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
) LShiftU64 (((UINT64
)Sd
->mBitBuf
), NumOfBits
);
46 // Copy data needed in bytes into mSbuBitBuf
48 while (NumOfBits
> Sd
->mBitCount
) {
49 NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
);
50 Sd
->mBitBuf
|= (UINT32
) LShiftU64 (((UINT64
)Sd
->mSubBitBuf
), NumOfBits
);
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 // Calculate 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.
120 If TableBits > 16, then ASSERT ().
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.
129 @retval BAD_TABLE The table is corrupted.
155 UINT16 MaxTableLength
;
158 // The maximum mapping table width supported by this internal
159 // working function is 16.
161 ASSERT (TableBits
<= 16);
163 for (Index
= 0; Index
<= 16; Index
++) {
167 for (Index
= 0; Index
< NumOfChar
; Index
++) {
168 if (BitLen
[Index
] > 16) {
169 return (UINT16
) BAD_TABLE
;
171 Count
[BitLen
[Index
]]++;
177 for (Index
= 1; Index
<= 16; Index
++) {
178 WordOfStart
= Start
[Index
];
179 WordOfCount
= Count
[Index
];
180 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
183 if (Start
[17] != 0) {
185 return (UINT16
) BAD_TABLE
;
188 JuBits
= (UINT16
) (16 - TableBits
);
191 for (Index
= 1; Index
<= TableBits
; Index
++) {
192 Start
[Index
] >>= JuBits
;
193 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
196 while (Index
<= 16) {
197 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
201 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
204 Index3
= (UINT16
) (1U << TableBits
);
205 if (Index
< Index3
) {
206 SetMem16 (Table
+ Index
, (Index3
- Index
) * sizeof (*Table
), 0);
211 Mask
= (UINT16
) (1U << (15 - TableBits
));
212 MaxTableLength
= (UINT16
) (1U << TableBits
);
214 for (Char
= 0; Char
< NumOfChar
; Char
++) {
217 if (Len
== 0 || Len
>= 17) {
221 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
223 if (Len
<= TableBits
) {
225 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
226 if (Index
>= MaxTableLength
) {
227 return (UINT16
) BAD_TABLE
;
235 Pointer
= &Table
[Index3
>> JuBits
];
236 Index
= (UINT16
) (Len
- TableBits
);
239 if (*Pointer
== 0 && Avail
< (2 * NC
- 1)) {
240 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
244 if (*Pointer
< (2 * NC
- 1)) {
245 if ((Index3
& Mask
) != 0) {
246 Pointer
= &Sd
->mRight
[*Pointer
];
248 Pointer
= &Sd
->mLeft
[*Pointer
];
260 Start
[Len
] = NextCode
;
269 Decodes a position value.
271 Get a position value according to Position Huffman Table.
273 @param Sd The global scratch data.
275 @return The position value decoded.
287 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
290 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
294 if ((Sd
->mBitBuf
& Mask
) != 0) {
295 Val
= Sd
->mRight
[Val
];
297 Val
= Sd
->mLeft
[Val
];
301 } while (Val
>= MAXNP
);
304 // Advance what we have read
306 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
310 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
317 Reads code lengths for the Extra Set or the Position Set.
319 Read in the Extra Set or Position Set Length Array, then
320 generate the Huffman code mapping for them.
322 @param Sd The global scratch data.
323 @param nn The number of symbols.
324 @param nbit The number of bits needed to represent nn.
325 @param Special The special symbol that needs to be taken care of.
328 @retval BAD_TABLE Table is corrupted.
346 // Read Extra Set Code Length Array size
348 Number
= (UINT16
) GetBits (Sd
, nbit
);
352 // This represents only Huffman code used
354 CharC
= (UINT16
) GetBits (Sd
, nbit
);
356 SetMem16 (&Sd
->mPTTable
[0] , sizeof (Sd
->mPTTable
), CharC
);
358 SetMem (Sd
->mPTLen
, nn
, 0);
365 while (Index
< Number
&& Index
< NPT
) {
367 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
370 // If a code length is less than 7, then it is encoded as a 3-bit
371 // value. Or it is encoded as a series of "1"s followed by a
372 // terminating "0". The number of "1"s = Code length - 4.
375 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
376 while (Mask
& Sd
->mBitBuf
) {
382 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
384 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
388 // After the third length of the code length concatenation,
389 // a 2-bit value is used to indicated the number of consecutive
390 // zero lengths after the third length.
392 if (Index
== Special
) {
393 CharC
= (UINT16
) GetBits (Sd
, 2);
394 while ((INT16
) (--CharC
) >= 0 && Index
< NPT
) {
395 Sd
->mPTLen
[Index
++] = 0;
400 while (Index
< nn
&& Index
< NPT
) {
401 Sd
->mPTLen
[Index
++] = 0;
404 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
408 Reads code lengths for Char&Len Set.
410 Read in and decode the Char&Len Set Code Length Array, then
411 generate the Huffman Code mapping table for the Char&Len Set.
413 @param Sd The global scratch data.
426 Number
= (UINT16
) GetBits (Sd
, CBIT
);
430 // This represents only Huffman code used
432 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
434 SetMem (Sd
->mCLen
, NC
, 0);
435 SetMem16 (&Sd
->mCTable
[0], sizeof (Sd
->mCTable
), CharC
);
441 while (Index
< Number
&& Index
< NC
) {
442 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
444 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
448 if (Mask
& Sd
->mBitBuf
) {
449 CharC
= Sd
->mRight
[CharC
];
451 CharC
= Sd
->mLeft
[CharC
];
456 } while (CharC
>= NT
);
459 // Advance what we have read
461 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
467 } else if (CharC
== 1) {
468 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
469 } else if (CharC
== 2) {
470 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
473 while ((INT16
) (--CharC
) >= 0 && Index
< NC
) {
474 Sd
->mCLen
[Index
++] = 0;
479 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
484 SetMem (Sd
->mCLen
+ Index
, NC
- Index
, 0);
486 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
492 Decode a character/length value.
494 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
495 Huffman code mapping table for Extra Set, Code&Len Set and
498 @param Sd The global scratch data.
500 @return The value decoded.
511 if (Sd
->mBlockSize
== 0) {
513 // Starting a new block
514 // Read BlockSize from block header
516 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
519 // Read in the Extra Set Code Length Array,
520 // Generate the Huffman code mapping table for Extra Set.
522 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
523 if (Sd
->mBadTableFlag
!= 0) {
528 // Read in and decode the Char&Len Set Code Length Array,
529 // Generate the Huffman code mapping table for Char&Len Set.
534 // Read in the Position Set Code Length Array,
535 // Generate the Huffman code mapping table for the Position Set.
537 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
538 if (Sd
->mBadTableFlag
!= 0) {
544 // Get one code according to Code&Set Huffman Table
547 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
550 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
553 if ((Sd
->mBitBuf
& Mask
) != 0) {
554 Index2
= Sd
->mRight
[Index2
];
556 Index2
= Sd
->mLeft
[Index2
];
560 } while (Index2
>= NC
);
563 // Advance what we have read
565 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
571 Decode the source data and put the resulting data into the destination buffer.
573 @param Sd The global scratch data.
585 BytesRemain
= (UINT16
) (-1);
591 // Get one code from mBitBuf
593 CharC
= DecodeC (Sd
);
594 if (Sd
->mBadTableFlag
!= 0) {
600 // Process an Original character
602 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
606 // Write orignal character into mDstBase
608 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
615 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
623 // Locate string position
625 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
628 // Write BytesRemain of bytes into mDstBase
632 while ((INT16
) (BytesRemain
) >= 0) {
633 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
636 if (DataIdx
>= Sd
->mOrigSize
) {
637 Sd
->mBadTableFlag
= (UINT16
) BAD_TABLE
;
640 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
652 Given a compressed source buffer, this function retrieves the size of
653 the uncompressed buffer and the size of the scratch buffer required
654 to decompress the compressed source buffer.
656 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
657 required to decompress the buffer specified by Source and SourceSize.
658 If the size of the uncompressed buffer or the size of the scratch buffer cannot
659 be determined from the compressed data specified by Source and SourceData,
660 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
661 buffer is returned in DestinationSize, the size of the scratch buffer is returned
662 in ScratchSize, and RETURN_SUCCESS is returned.
663 This function does not have scratch buffer available to perform a thorough
664 checking of the validity of the source data. It just retrieves the "Original Size"
665 field from the beginning bytes of the source data and output it as DestinationSize.
666 And ScratchSize is specific to the decompression implementation.
668 If Source is NULL, then ASSERT().
669 If DestinationSize is NULL, then ASSERT().
670 If ScratchSize is NULL, then ASSERT().
672 @param Source The source buffer containing the compressed data.
673 @param SourceSize The size, in bytes, of the source buffer.
674 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
675 that will be generated when the compressed buffer specified
676 by Source and SourceSize is decompressed.
677 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
678 is required to decompress the compressed buffer specified
679 by Source and SourceSize.
681 @retval RETURN_SUCCESS The size of the uncompressed data was returned
682 in DestinationSize, and the size of the scratch
683 buffer was returned in ScratchSize.
684 @retval RETURN_INVALID_PARAMETER
685 The size of the uncompressed data or the size of
686 the scratch buffer cannot be determined from
687 the compressed data specified by Source
692 UefiDecompressGetInfo (
693 IN CONST VOID
*Source
,
694 IN UINT32 SourceSize
,
695 OUT UINT32
*DestinationSize
,
696 OUT UINT32
*ScratchSize
699 UINT32 CompressedSize
;
701 ASSERT (Source
!= NULL
);
702 ASSERT (DestinationSize
!= NULL
);
703 ASSERT (ScratchSize
!= NULL
);
705 if (SourceSize
< 8) {
706 return RETURN_INVALID_PARAMETER
;
709 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
710 if (SourceSize
< (CompressedSize
+ 8) || (CompressedSize
+ 8) < 8) {
711 return RETURN_INVALID_PARAMETER
;
714 *ScratchSize
= sizeof (SCRATCH_DATA
);
715 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
717 return RETURN_SUCCESS
;
721 Decompresses a compressed source buffer.
723 Extracts decompressed data to its original form.
724 This function is designed so that the decompression algorithm can be implemented
725 without using any memory services. As a result, this function is not allowed to
726 call any memory allocation services in its implementation. It is the caller's
727 responsibility to allocate and free the Destination and Scratch buffers.
728 If the compressed source data specified by Source is successfully decompressed
729 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
730 specified by Source is not in a valid compressed data format,
731 then RETURN_INVALID_PARAMETER is returned.
733 If Source is NULL, then ASSERT().
734 If Destination is NULL, then ASSERT().
735 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
737 @param Source The source buffer containing the compressed data.
738 @param Destination The destination buffer to store the decompressed data.
739 @param Scratch A temporary scratch buffer that is used to perform the decompression.
740 This is an optional parameter that may be NULL if the
741 required scratch buffer size is 0.
743 @retval RETURN_SUCCESS Decompression completed successfully, and
744 the uncompressed buffer is returned in Destination.
745 @retval RETURN_INVALID_PARAMETER
746 The source buffer specified by Source is corrupted
747 (not in a valid compressed format).
752 IN CONST VOID
*Source
,
753 IN OUT VOID
*Destination
,
754 IN OUT VOID
*Scratch OPTIONAL
763 ASSERT (Source
!= NULL
);
764 ASSERT (Destination
!= NULL
);
765 ASSERT (Scratch
!= NULL
);
770 Sd
= (SCRATCH_DATA
*) Scratch
;
772 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
773 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
776 // If compressed file size is 0, return
779 return RETURN_SUCCESS
;
783 SetMem (Sd
, sizeof (SCRATCH_DATA
), 0);
786 // The length of the field 'Position Set Code Length Array Size' in Block Header.
787 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
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
;