]>
git.proxmox.com Git - mirror_edk2.git/blob - EdkCompatibilityPkg/Foundation/Library/EdkIIGlueLib/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
3 Copyright (c) 2004 - 2010, Intel Corporation. All rights reserved.<BR>
4 This program and the accompanying materials
5 are licensed and made available under the terms and conditions of the BSD License
6 which accompanies this distribution. The full text of the license may be found at
7 http://opensource.org/licenses/bsd-license.php
9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
15 BaseUefiDecompressLib.c
19 UEFI Decompress Library.
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
128 @retval BAD_TABLE The table is corrupted.
156 // TableBits should not be greater than 16.
158 if (TableBits
>= (sizeof (Count
)/sizeof (UINT16
))) {
159 return (UINT16
) BAD_TABLE
;
163 // Initialize Count array starting from Index 0, as there is a possibility of Count array being uninitialized.
165 for (Index
= 0; Index
<= 16; Index
++) {
169 for (Index
= 0; Index
< NumOfChar
; Index
++) {
171 // Count array index should not be greater than or equal to its size.
173 if (BitLen
[Index
] < (sizeof (Count
)/sizeof (UINT16
))) {
174 Count
[BitLen
[Index
]]++;
176 return (UINT16
) BAD_TABLE
;
183 for (Index
= 1; Index
<= 16; Index
++) {
184 WordOfStart
= Start
[Index
];
185 WordOfCount
= Count
[Index
];
186 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
189 if (Start
[17] != 0) {
191 return (UINT16
) BAD_TABLE
;
194 JuBits
= (UINT16
) (16 - TableBits
);
196 for (Index
= 1; Index
<= TableBits
; Index
++) {
197 Start
[Index
] >>= JuBits
;
198 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
201 while (Index
<= 16) {
202 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
206 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
209 Index3
= (UINT16
) (1U << TableBits
);
210 while (Index
!= Index3
) {
216 Mask
= (UINT16
) (1U << (15 - TableBits
));
218 for (Char
= 0; Char
< NumOfChar
; Char
++) {
221 if (Len
== 0 || Len
>= 17) {
225 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
227 if (Len
<= TableBits
) {
229 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
236 Pointer
= &Table
[Index3
>> JuBits
];
237 Index
= (UINT16
) (Len
- TableBits
);
241 // Avail should be lesser than size of mRight and mLeft to prevent buffer overflow.
243 if ((*Pointer
== 0) && (Avail
< sizeof (Sd
->mRight
)/sizeof (UINT16
)) && (Avail
< sizeof (Sd
->mLeft
)/sizeof (UINT16
))) {
244 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
249 // *Pointer should be lesser than size of mRight and mLeft to prevent buffer overflow.
251 if ((Index3
& Mask
) && (*Pointer
< (sizeof (Sd
->mRight
)/sizeof (UINT16
)))) {
252 Pointer
= &Sd
->mRight
[*Pointer
];
253 } else if (*Pointer
< (sizeof (Sd
->mLeft
)/sizeof (UINT16
))) {
254 Pointer
= &Sd
->mLeft
[*Pointer
];
265 Start
[Len
] = NextCode
;
274 Decodes a position value.
276 Get a position value according to Position Huffman Table.
278 @param Sd the global scratch data
280 @return The position value decoded.
292 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
295 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
299 if (Sd
->mBitBuf
& Mask
) {
300 Val
= Sd
->mRight
[Val
];
302 Val
= Sd
->mLeft
[Val
];
306 } while (Val
>= MAXNP
);
309 // Advance what we have read
311 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
315 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
322 Reads code lengths for the Extra Set or the Position Set.
324 Read in the Extra Set or Position Set Length Array, then
325 generate the Huffman code mapping for them.
327 @param Sd The global scratch data.
328 @param nn Number of symbols.
329 @param nbit Number of bits needed to represent nn.
330 @param Special The special symbol that needs to be taken care of.
333 @retval BAD_TABLE Table is corrupted.
346 volatile UINT16 Index
;
350 // Read Extra Set Code Length Array size
352 Number
= (UINT16
) GetBits (Sd
, nbit
);
354 if ((Number
> sizeof (Sd
->mPTLen
)) || (nn
> sizeof (Sd
->mPTLen
))) {
356 // Fail if Number or nn is greater than size of mPTLen
358 return (UINT16
) BAD_TABLE
;
363 // This represents only Huffman code used
365 CharC
= (UINT16
) GetBits (Sd
, nbit
);
367 for (Index
= 0; Index
< 256; Index
++) {
368 Sd
->mPTTable
[Index
] = CharC
;
371 for (Index
= 0; Index
< nn
; Index
++) {
372 Sd
->mPTLen
[Index
] = 0;
380 while (Index
< Number
) {
382 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
385 // If a code length is less than 7, then it is encoded as a 3-bit
386 // value. Or it is encoded as a series of "1"s followed by a
387 // terminating "0". The number of "1"s = Code length - 4.
390 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
391 while (Mask
& Sd
->mBitBuf
) {
397 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
399 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
403 // After the third length of the code length concatenation,
404 // a 2-bit value is used to indicated the number of consecutive
405 // zero lengths after the third length.
407 if (Index
== Special
) {
408 CharC
= (UINT16
) GetBits (Sd
, 2);
409 while ((INT16
) (--CharC
) >= 0) {
410 if (Index
>= sizeof (Sd
->mPTLen
)) {
412 // Fail if Index is greater than or equal to mPTLen
414 return (UINT16
) BAD_TABLE
;
416 Sd
->mPTLen
[Index
++] = 0;
422 Sd
->mPTLen
[Index
++] = 0;
425 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
429 Reads code lengths for Char&Len Set.
431 Read in and decode the Char&Len Set Code Length Array, then
432 generate the Huffman Code mapping table for the Char&Len Set.
434 @param Sd the global scratch data
444 volatile UINT16 Index
;
447 Number
= (UINT16
) GetBits (Sd
, CBIT
);
451 // This represents only Huffman code used
453 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
455 for (Index
= 0; Index
< NC
; Index
++) {
456 Sd
->mCLen
[Index
] = 0;
459 for (Index
= 0; Index
< 4096; Index
++) {
460 Sd
->mCTable
[Index
] = CharC
;
467 while (Index
< Number
) {
468 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
470 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
474 if (Mask
& Sd
->mBitBuf
) {
475 CharC
= Sd
->mRight
[CharC
];
477 CharC
= Sd
->mLeft
[CharC
];
482 } while (CharC
>= NT
);
485 // Advance what we have read
487 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
493 } else if (CharC
== 1) {
494 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
495 } else if (CharC
== 2) {
496 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
499 while ((INT16
) (--CharC
) >= 0) {
500 Sd
->mCLen
[Index
++] = 0;
505 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
511 Sd
->mCLen
[Index
++] = 0;
514 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
520 Decode a character/length value.
522 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
523 Huffman code mapping table for Extra Set, Code&Len Set and
526 @param Sd The global scratch data.
528 @return The value decoded.
539 if (Sd
->mBlockSize
== 0) {
541 // Starting a new block
542 // Read BlockSize from block header
544 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
547 // Read in the Extra Set Code Length Array,
548 // Generate the Huffman code mapping table for Extra Set.
550 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
551 if (Sd
->mBadTableFlag
!= 0) {
556 // Read in and decode the Char&Len Set Code Length Array,
557 // Generate the Huffman code mapping table for Char&Len Set.
562 // Read in the Position Set Code Length Array,
563 // Generate the Huffman code mapping table for the Position Set.
565 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
566 if (Sd
->mBadTableFlag
!= 0) {
572 // Get one code according to Code&Set Huffman Table
575 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
578 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
581 if (Sd
->mBitBuf
& Mask
) {
582 Index2
= Sd
->mRight
[Index2
];
584 Index2
= Sd
->mLeft
[Index2
];
588 } while (Index2
>= NC
);
591 // Advance what we have read
593 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
599 Decode the source data and put the resulting data into the destination buffer.
601 Decode the source data and put the resulting data into the destination buffer.
603 @param Sd The global scratch data
615 BytesRemain
= (UINT16
) (-1);
621 // Get one code from mBitBuf
623 CharC
= DecodeC (Sd
);
624 if (Sd
->mBadTableFlag
!= 0) {
630 // Process an Original character
632 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
636 // Write orignal character into mDstBase
638 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
645 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
653 // Locate string position
655 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
658 // Write BytesRemain of bytes into mDstBase
661 while ((INT16
) (BytesRemain
) >= 0) {
662 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
663 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
677 Retrieves the size of the uncompressed buffer and the size of the scratch buffer.
679 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
680 required to decompress the buffer specified by Source and SourceSize.
681 If the size of the uncompressed buffer or the size of the scratch buffer cannot
682 be determined from the compressed data specified by Source and SourceData,
683 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
684 buffer is returned in DestinationSize, the size of the scratch buffer is returned
685 in ScratchSize, and RETURN_SUCCESS is returned.
686 This function does not have scratch buffer available to perform a thorough
687 checking of the validity of the source data. It just retrieves the "Original Size"
688 field from the beginning bytes of the source data and output it as DestinationSize.
689 And ScratchSize is specific to the decompression implementation.
691 If Source is NULL, then ASSERT().
692 If DestinationSize is NULL, then ASSERT().
693 If ScratchSize is NULL, then ASSERT().
695 @param Source The source buffer containing the compressed data.
696 @param SourceSize The size, in bytes, of the source buffer.
697 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
698 that will be generated when the compressed buffer specified
699 by Source and SourceSize is decompressed..
700 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
701 is required to decompress the compressed buffer specified
702 by Source and SourceSize.
704 @retval RETURN_SUCCESS The size of destination buffer and the size of scratch
705 buffer are successfully retrieved.
706 @retval RETURN_INVALID_PARAMETER The source data is corrupted
711 UefiDecompressGetInfo (
712 IN CONST VOID
*Source
,
713 IN UINT32 SourceSize
,
714 OUT UINT32
*DestinationSize
,
715 OUT UINT32
*ScratchSize
718 UINT32 CompressedSize
;
720 ASSERT (Source
!= NULL
);
721 ASSERT (DestinationSize
!= NULL
);
722 ASSERT (ScratchSize
!= NULL
);
724 *ScratchSize
= sizeof (SCRATCH_DATA
);
726 if (SourceSize
< 8) {
727 return RETURN_INVALID_PARAMETER
;
730 CopyMem (&CompressedSize
, Source
, sizeof (UINT32
));
731 CopyMem (DestinationSize
, (VOID
*)((UINT8
*)Source
+ 4), sizeof (UINT32
));
733 if (SourceSize
< (CompressedSize
+ 8)) {
734 return RETURN_INVALID_PARAMETER
;
737 return RETURN_SUCCESS
;
741 Decompresses a compressed source buffer.
743 This function is designed so that the decompression algorithm can be implemented
744 without using any memory services. As a result, this function is not allowed to
745 call any memory allocation services in its implementation. It is the caller's r
746 esponsibility to allocate and free the Destination and Scratch buffers.
747 If the compressed source data specified by Source is sucessfully decompressed
748 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
749 specified by Source is not in a valid compressed data format,
750 then RETURN_INVALID_PARAMETER is returned.
752 If Source is NULL, then ASSERT().
753 If Destination is NULL, then ASSERT().
754 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
756 @param Source The source buffer containing the compressed data.
757 @param Destination The destination buffer to store the decompressed data
758 @param Scratch A temporary scratch buffer that is used to perform the decompression.
759 This is an optional parameter that may be NULL if the
760 required scratch buffer size is 0.
762 @retval RETURN_SUCCESS Decompression is successfull
763 @retval RETURN_INVALID_PARAMETER The source data is corrupted
769 IN CONST VOID
*Source
,
770 IN OUT VOID
*Destination
,
774 volatile UINT32 Index
;
781 ASSERT (Source
!= NULL
);
782 ASSERT (Destination
!= NULL
);
783 ASSERT (Scratch
!= NULL
);
788 Sd
= (SCRATCH_DATA
*) Scratch
;
790 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
791 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
794 // If compressed file size is 0, return
797 return RETURN_SUCCESS
;
802 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
803 ((UINT8
*) Sd
)[Index
] = 0;
806 // The length of the field 'Position Set Code Length Array Size' in Block Header.
807 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
808 // For Tiano de/compression algorithm(Version 2), mPBit = 5
811 Sd
->mSrcBase
= (UINT8
*)Src
;
814 // CompSize and OrigSize are caculated in bytes
816 Sd
->mCompSize
= CompSize
;
817 Sd
->mOrigSize
= OrigSize
;
820 // Fill the first BITBUFSIZ bits
822 FillBuf (Sd
, BITBUFSIZ
);
829 if (Sd
->mBadTableFlag
!= 0) {
831 // Something wrong with the source
833 return RETURN_INVALID_PARAMETER
;
836 return RETURN_SUCCESS
;