]>
git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
58f7791fe7c9504854e6cfaf31c657038dd37108
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
= 0; Index
<= 16; Index
++) {
160 for (Index
= 0; Index
< NumOfChar
; Index
++) {
161 Count
[BitLen
[Index
]]++;
167 for (Index
= 1; Index
<= 16; Index
++) {
168 WordOfStart
= Start
[Index
];
169 WordOfCount
= Count
[Index
];
170 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
173 if (Start
[17] != 0) {
175 return (UINT16
) BAD_TABLE
;
178 JuBits
= (UINT16
) (16 - TableBits
);
181 for (Index
= 1; Index
<= TableBits
; Index
++) {
182 Start
[Index
] >>= JuBits
;
183 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
186 while (Index
<= 16) {
187 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
191 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
194 Index3
= (UINT16
) (1U << TableBits
);
195 while (Index
!= Index3
) {
201 Mask
= (UINT16
) (1U << (15 - TableBits
));
203 for (Char
= 0; Char
< NumOfChar
; Char
++) {
206 if (Len
== 0 || Len
>= 17) {
210 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
212 if (Len
<= TableBits
) {
214 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
221 Pointer
= &Table
[Index3
>> JuBits
];
222 Index
= (UINT16
) (Len
- TableBits
);
226 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
230 if ((Index3
& Mask
) != 0) {
231 Pointer
= &Sd
->mRight
[*Pointer
];
233 Pointer
= &Sd
->mLeft
[*Pointer
];
244 Start
[Len
] = NextCode
;
253 Decodes a position value.
255 Get a position value according to Position Huffman Table.
257 @param Sd the global scratch data
259 @return The position value decoded.
271 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
274 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
278 if ((Sd
->mBitBuf
& Mask
) != 0) {
279 Val
= Sd
->mRight
[Val
];
281 Val
= Sd
->mLeft
[Val
];
285 } while (Val
>= MAXNP
);
288 // Advance what we have read
290 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
294 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
301 Reads code lengths for the Extra Set or the Position Set.
303 Read in the Extra Set or Pointion Set Length Arrary, then
304 generate the Huffman code mapping for them.
306 @param Sd The global scratch data.
307 @param nn Number of symbols.
308 @param nbit Number of bits needed to represent nn.
309 @param Special The special symbol that needs to be taken care of.
312 @retval BAD_TABLE Table is corrupted.
325 volatile UINT16 Index
;
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 for (Index
= 0; Index
< 256; Index
++) {
340 Sd
->mPTTable
[Index
] = CharC
;
343 for (Index
= 0; Index
< nn
; Index
++) {
344 Sd
->mPTLen
[Index
] = 0;
352 while (Index
< Number
&& Index
< NPT
) {
354 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
357 // If a code length is less than 7, then it is encoded as a 3-bit
358 // value. Or it is encoded as a series of "1"s followed by a
359 // terminating "0". The number of "1"s = Code length - 4.
362 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
363 while (Mask
& Sd
->mBitBuf
) {
369 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
371 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
375 // After the third length of the code length concatenation,
376 // a 2-bit value is used to indicated the number of consecutive
377 // zero lengths after the third length.
379 if (Index
== Special
) {
380 CharC
= (UINT16
) GetBits (Sd
, 2);
381 while ((INT16
) (--CharC
) >= 0) {
382 Sd
->mPTLen
[Index
++] = 0;
387 while (Index
< nn
&& Index
< NPT
) {
388 Sd
->mPTLen
[Index
++] = 0;
391 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
395 Reads code lengths for Char&Len Set.
397 Read in and decode the Char&Len Set Code Length Array, then
398 generate the Huffman Code mapping table for the Char&Len Set.
400 @param Sd the global scratch data
410 volatile UINT16 Index
;
413 Number
= (UINT16
) GetBits (Sd
, CBIT
);
417 // This represents only Huffman code used
419 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
421 for (Index
= 0; Index
< NC
; Index
++) {
422 Sd
->mCLen
[Index
] = 0;
425 for (Index
= 0; Index
< 4096; Index
++) {
426 Sd
->mCTable
[Index
] = CharC
;
433 while (Index
< Number
&& Index
< NC
) {
434 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
436 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
440 if (Mask
& Sd
->mBitBuf
) {
441 CharC
= Sd
->mRight
[CharC
];
443 CharC
= Sd
->mLeft
[CharC
];
448 } while (CharC
>= NT
);
451 // Advance what we have read
453 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
459 } else if (CharC
== 1) {
460 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
461 } else if (CharC
== 2) {
462 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
465 while ((INT16
) (--CharC
) >= 0) {
466 Sd
->mCLen
[Index
++] = 0;
471 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
477 Sd
->mCLen
[Index
++] = 0;
480 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
486 Decode a character/length value.
488 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
489 Huffman code mapping table for Extra Set, Code&Len Set and
492 @param Sd The global scratch data.
494 @return The value decoded.
505 if (Sd
->mBlockSize
== 0) {
507 // Starting a new block
508 // Read BlockSize from block header
510 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
513 // Read in the Extra Set Code Length Arrary,
514 // Generate the Huffman code mapping table for Extra Set.
516 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
517 if (Sd
->mBadTableFlag
!= 0) {
522 // Read in and decode the Char&Len Set Code Length Arrary,
523 // Generate the Huffman code mapping table for Char&Len Set.
528 // Read in the Position Set Code Length Arrary,
529 // Generate the Huffman code mapping table for the Position Set.
531 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
532 if (Sd
->mBadTableFlag
!= 0) {
538 // Get one code according to Code&Set Huffman Table
541 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
544 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
547 if ((Sd
->mBitBuf
& Mask
) != 0) {
548 Index2
= Sd
->mRight
[Index2
];
550 Index2
= Sd
->mLeft
[Index2
];
554 } while (Index2
>= NC
);
557 // Advance what we have read
559 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
565 Decode the source data and put the resulting data into the destination buffer.
567 @param Sd The global scratch data
579 BytesRemain
= (UINT16
) (-1);
585 // Get one code from mBitBuf
587 CharC
= DecodeC (Sd
);
588 if (Sd
->mBadTableFlag
!= 0) {
594 // Process an Original character
596 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
600 // Write orignal character into mDstBase
602 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
609 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
617 // Locate string position
619 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
622 // Write BytesRemain of bytes into mDstBase
625 while ((INT16
) (BytesRemain
) >= 0) {
626 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
627 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
641 Given a compressed source buffer, this function retrieves the size of
642 the uncompressed buffer and the size of the scratch buffer required
643 to decompress the compressed source buffer.
645 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
646 required to decompress the buffer specified by Source and SourceSize.
647 If the size of the uncompressed buffer or the size of the scratch buffer cannot
648 be determined from the compressed data specified by Source and SourceData,
649 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
650 buffer is returned in DestinationSize, the size of the scratch buffer is returned
651 in ScratchSize, and RETURN_SUCCESS is returned.
652 This function does not have scratch buffer available to perform a thorough
653 checking of the validity of the source data. It just retrieves the "Original Size"
654 field from the beginning bytes of the source data and output it as DestinationSize.
655 And ScratchSize is specific to the decompression implementation.
657 If Source is NULL, then ASSERT().
658 If DestinationSize is NULL, then ASSERT().
659 If ScratchSize is NULL, then ASSERT().
661 @param Source The source buffer containing the compressed data.
662 @param SourceSize The size, in bytes, of the source buffer.
663 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
664 that will be generated when the compressed buffer specified
665 by Source and SourceSize is decompressed..
666 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
667 is required to decompress the compressed buffer specified
668 by Source and SourceSize.
670 @retval RETURN_SUCCESS The size of the uncompressed data was returned
671 in DestinationSize and the size of the scratch
672 buffer was returned in ScratchSize.
673 @retval RETURN_INVALID_PARAMETER
674 The size of the uncompressed data or the size of
675 the scratch buffer cannot be determined from
676 the compressed data specified by Source
681 UefiDecompressGetInfo (
682 IN CONST VOID
*Source
,
683 IN UINT32 SourceSize
,
684 OUT UINT32
*DestinationSize
,
685 OUT UINT32
*ScratchSize
688 UINT32 CompressedSize
;
690 ASSERT (Source
!= NULL
);
691 ASSERT (DestinationSize
!= NULL
);
692 ASSERT (ScratchSize
!= NULL
);
694 if (SourceSize
< 8) {
695 return RETURN_INVALID_PARAMETER
;
698 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
699 if (SourceSize
< (CompressedSize
+ 8)) {
700 return RETURN_INVALID_PARAMETER
;
703 *ScratchSize
= sizeof (SCRATCH_DATA
);
704 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
706 return RETURN_SUCCESS
;
710 Decompresses a compressed source buffer.
712 Extracts decompressed data to its original form.
713 This function is designed so that the decompression algorithm can be implemented
714 without using any memory services. As a result, this function is not allowed to
715 call any memory allocation services in its implementation. It is the caller's r
716 esponsibility to allocate and free the Destination and Scratch buffers.
717 If the compressed source data specified by Source is sucessfully decompressed
718 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
719 specified by Source is not in a valid compressed data format,
720 then RETURN_INVALID_PARAMETER is returned.
722 If Source is NULL, then ASSERT().
723 If Destination is NULL, then ASSERT().
724 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
726 @param Source The source buffer containing the compressed data.
727 @param Destination The destination buffer to store the decompressed data
728 @param Scratch A temporary scratch buffer that is used to perform the decompression.
729 This is an optional parameter that may be NULL if the
730 required scratch buffer size is 0.
732 @retval RETURN_SUCCESS Decompression completed successfully, and
733 the uncompressed buffer is returned in Destination.
734 @retval RETURN_INVALID_PARAMETER
735 The source buffer specified by Source is corrupted
736 (not in a valid compressed format).
741 IN CONST VOID
*Source
,
742 IN OUT VOID
*Destination
,
743 IN OUT VOID
*Scratch OPTIONAL
746 volatile UINT32 Index
;
753 ASSERT (Source
!= NULL
);
754 ASSERT (Destination
!= NULL
);
755 ASSERT (Scratch
!= NULL
);
760 Sd
= (SCRATCH_DATA
*) Scratch
;
762 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
763 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
766 // If compressed file size is 0, return
769 return RETURN_SUCCESS
;
774 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
775 ((UINT8
*) Sd
)[Index
] = 0;
778 // The length of the field 'Position Set Code Length Array Size' in Block Header.
779 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
782 Sd
->mSrcBase
= (UINT8
*)Src
;
785 // CompSize and OrigSize are caculated in bytes
787 Sd
->mCompSize
= CompSize
;
788 Sd
->mOrigSize
= OrigSize
;
791 // Fill the first BITBUFSIZ bits
793 FillBuf (Sd
, BITBUFSIZ
);
800 if (Sd
->mBadTableFlag
!= 0) {
802 // Something wrong with the source
804 return RETURN_INVALID_PARAMETER
;
807 return RETURN_SUCCESS
;