]>
git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
2 UEFI Decompress Library.
4 Copyright (c) 2006, 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.
13 Module Name: UefiDecompressLib.c
18 // Decompression algorithm begins here
27 // C: Char&Len Set; P: Position Set; T: exTra Set
29 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
33 #define MAXNP ((1U << MAXPBIT) - 1)
34 #define NT (CODE_BIT + 3)
42 UINT8
*mSrcBase
; ///< Starting address of compressed data
43 UINT8
*mDstBase
; ///< Starting address of decompressed data
56 UINT16 mLeft
[2 * NC
- 1];
57 UINT16 mRight
[2 * NC
- 1];
64 /// The length of the field 'Position Set Code Length Array Size' in Block Header.
65 /// For EFI 1.1 de/compression algorithm, mPBit = 4
66 /// For Tiano de/compression algorithm, mPBit = 5
72 Read NumOfBit of bits from source into mBitBuf
74 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
76 @param Sd The global scratch data
77 @param NumOfBits The number of bits to shift and read.
87 // Left shift NumOfBits of bits in advance
89 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
92 // Copy data needed in bytes into mSbuBitBuf
94 while (NumOfBits
> Sd
->mBitCount
) {
96 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
98 if (Sd
->mCompSize
> 0) {
100 // Get 1 byte into SubBitBuf
103 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
108 // No more bits from the source, just pad zero bit.
117 // Caculate additional bit count read to update mBitCount
119 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
122 // Copy NumOfBits of bits from mSubBitBuf into mBitBuf
124 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
128 Get NumOfBits of bits out from mBitBuf
130 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
131 NumOfBits of bits from source. Returns NumOfBits of bits that are
134 @param Sd The global scratch data.
135 @param NumOfBits The number of bits to pop and read.
137 @return The bits that are popped out.
149 // Pop NumOfBits of Bits from Left
151 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
154 // Fill up mBitBuf from source
156 FillBuf (Sd
, NumOfBits
);
162 Creates Huffman Code mapping table according to code length array.
164 Creates Huffman Code mapping table for Extra Set, Char&Len Set
165 and Position Set according to code length array.
167 @param Sd The global scratch data
168 @param NumOfChar Number of symbols in the symbol set
169 @param BitLen Code length array
170 @param TableBits The width of the mapping table
171 @param Table The table
174 @retval BAD_TABLE The table is corrupted.
191 volatile UINT16 Index
;
199 for (Index
= 1; Index
<= 16; Index
++) {
203 for (Index
= 0; Index
< NumOfChar
; Index
++) {
204 Count
[BitLen
[Index
]]++;
209 for (Index
= 1; Index
<= 16; Index
++) {
210 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
213 if (Start
[17] != 0) {
215 return (UINT16
) BAD_TABLE
;
218 JuBits
= (UINT16
) (16 - TableBits
);
220 for (Index
= 1; Index
<= TableBits
; Index
++) {
221 Start
[Index
] >>= JuBits
;
222 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
225 while (Index
<= 16) {
226 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
230 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
233 Index3
= (UINT16
) (1U << TableBits
);
234 while (Index
!= Index3
) {
240 Mask
= (UINT16
) (1U << (15 - TableBits
));
242 for (Char
= 0; Char
< NumOfChar
; Char
++) {
249 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
251 if (Len
<= TableBits
) {
253 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
260 Pointer
= &Table
[Index3
>> JuBits
];
261 Index
= (UINT16
) (Len
- TableBits
);
265 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
270 Pointer
= &Sd
->mRight
[*Pointer
];
272 Pointer
= &Sd
->mLeft
[*Pointer
];
283 Start
[Len
] = NextCode
;
292 Decodes a position value.
294 Get a position value according to Position Huffman Table.
296 @param Sd the global scratch data
298 @return The position value decoded.
310 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
313 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
317 if (Sd
->mBitBuf
& Mask
) {
318 Val
= Sd
->mRight
[Val
];
320 Val
= Sd
->mLeft
[Val
];
324 } while (Val
>= MAXNP
);
327 // Advance what we have read
329 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
333 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
340 Reads code lengths for the Extra Set or the Position Set.
342 Read in the Extra Set or Pointion Set Length Arrary, then
343 generate the Huffman code mapping for them.
345 @param Sd The global scratch data.
346 @param nn Number of symbols.
347 @param nbit Number of bits needed to represent nn.
348 @param Special The special symbol that needs to be taken care of.
351 @retval BAD_TABLE Table is corrupted.
364 volatile UINT16 Index
;
368 // Read Extra Set Code Length Array size
370 Number
= (UINT16
) GetBits (Sd
, nbit
);
374 // This represents only Huffman code used
376 CharC
= (UINT16
) GetBits (Sd
, nbit
);
378 for (Index
= 0; Index
< 256; Index
++) {
379 Sd
->mPTTable
[Index
] = CharC
;
382 for (Index
= 0; Index
< nn
; Index
++) {
383 Sd
->mPTLen
[Index
] = 0;
391 while (Index
< Number
) {
393 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
396 // If a code length is less than 7, then it is encoded as a 3-bit
397 // value. Or it is encoded as a series of "1"s followed by a
398 // terminating "0". The number of "1"s = Code length - 4.
401 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
402 while (Mask
& Sd
->mBitBuf
) {
408 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
410 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
414 // After the third length of the code length concatenation,
415 // a 2-bit value is used to indicated the number of consecutive
416 // zero lengths after the third length.
418 if (Index
== Special
) {
419 CharC
= (UINT16
) GetBits (Sd
, 2);
420 while ((INT16
) (--CharC
) >= 0) {
421 Sd
->mPTLen
[Index
++] = 0;
427 Sd
->mPTLen
[Index
++] = 0;
430 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
434 Reads code lengths for Char&Len Set.
436 Read in and decode the Char&Len Set Code Length Array, then
437 generate the Huffman Code mapping table for the Char&Len Set.
439 @param Sd the global scratch data
449 volatile UINT16 Index
;
452 Number
= (UINT16
) GetBits (Sd
, CBIT
);
456 // This represents only Huffman code used
458 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
460 for (Index
= 0; Index
< NC
; Index
++) {
461 Sd
->mCLen
[Index
] = 0;
464 for (Index
= 0; Index
< 4096; Index
++) {
465 Sd
->mCTable
[Index
] = CharC
;
472 while (Index
< Number
) {
473 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
475 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
479 if (Mask
& Sd
->mBitBuf
) {
480 CharC
= Sd
->mRight
[CharC
];
482 CharC
= Sd
->mLeft
[CharC
];
487 } while (CharC
>= NT
);
490 // Advance what we have read
492 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
498 } else if (CharC
== 1) {
499 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
500 } else if (CharC
== 2) {
501 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
504 while ((INT16
) (--CharC
) >= 0) {
505 Sd
->mCLen
[Index
++] = 0;
510 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
516 Sd
->mCLen
[Index
++] = 0;
519 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
525 Decode a character/length value.
527 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
528 Huffman code mapping table for Extra Set, Code&Len Set and
531 @param Sd The global scratch data.
533 @return The value decoded.
544 if (Sd
->mBlockSize
== 0) {
546 // Starting a new block
547 // Read BlockSize from block header
549 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
552 // Read in the Extra Set Code Length Arrary,
553 // Generate the Huffman code mapping table for Extra Set.
555 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
556 if (Sd
->mBadTableFlag
!= 0) {
561 // Read in and decode the Char&Len Set Code Length Arrary,
562 // Generate the Huffman code mapping table for Char&Len Set.
567 // Read in the Position Set Code Length Arrary,
568 // Generate the Huffman code mapping table for the Position Set.
570 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
571 if (Sd
->mBadTableFlag
!= 0) {
577 // Get one code according to Code&Set Huffman Table
580 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
583 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
586 if (Sd
->mBitBuf
& Mask
) {
587 Index2
= Sd
->mRight
[Index2
];
589 Index2
= Sd
->mLeft
[Index2
];
593 } while (Index2
>= NC
);
596 // Advance what we have read
598 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
604 Decode the source data and put the resulting data into the destination buffer.
606 Decode the source data and put the resulting data into the destination buffer.
608 @param Sd The global scratch data
620 BytesRemain
= (UINT16
) (-1);
626 // Get one code from mBitBuf
628 CharC
= DecodeC (Sd
);
629 if (Sd
->mBadTableFlag
!= 0) {
635 // Process an Original character
637 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
641 // Write orignal character into mDstBase
643 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
650 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
658 // Locate string position
660 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
663 // Write BytesRemain of bytes into mDstBase
666 while ((INT16
) (BytesRemain
) >= 0) {
667 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
668 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
681 Retrieves the size of the uncompressed buffer and the size of the scratch buffer.
683 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
684 required to decompress the buffer specified by Source and SourceSize.
685 If the size of the uncompressed buffer or the size of the scratch buffer cannot
686 be determined from the compressed data specified by Source and SourceData,
687 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
688 buffer is returned in DestinationSize, the size of the scratch buffer is returned
689 in ScratchSize, and RETURN_SUCCESS is returned.
690 This function does not have scratch buffer available to perform a thorough
691 checking of the validity of the source data. It just retrieves the "Original Size"
692 field from the beginning bytes of the source data and output it as DestinationSize.
693 And ScratchSize is specific to the decompression implementation.
695 If Source is NULL, then ASSERT().
696 If DestinationSize is NULL, then ASSERT().
697 If ScratchSize is NULL, then ASSERT().
699 @param Source The source buffer containing the compressed data.
700 @param SourceSize The size, in bytes, of the source buffer.
701 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
702 that will be generated when the compressed buffer specified
703 by Source and SourceSize is decompressed..
704 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
705 is required to decompress the compressed buffer specified
706 by Source and SourceSize.
708 @retval RETURN_SUCCESS The size of destination buffer and the size of scratch
709 buffer are successull retrieved.
710 @retval RETURN_INVALID_PARAMETER The source data is corrupted
715 UefiDecompressGetInfo (
716 IN CONST VOID
*Source
,
717 IN UINT32 SourceSize
,
718 OUT UINT32
*DestinationSize
,
719 OUT UINT32
*ScratchSize
722 UINT32 CompressedSize
;
724 ASSERT (Source
!= NULL
);
725 ASSERT (DestinationSize
!= NULL
);
726 ASSERT (ScratchSize
!= NULL
);
728 *ScratchSize
= sizeof (SCRATCH_DATA
);
730 if (SourceSize
< 8) {
731 return RETURN_INVALID_PARAMETER
;
734 CopyMem (&CompressedSize
, Source
, sizeof (UINT32
));
735 CopyMem (DestinationSize
, (VOID
*)((UINT8
*)Source
+ 4), sizeof (UINT32
));
737 if (SourceSize
< (CompressedSize
+ 8)) {
738 return RETURN_INVALID_PARAMETER
;
741 return RETURN_SUCCESS
;
745 Decompresses a compressed source buffer.
747 This function is designed so that the decompression algorithm can be implemented
748 without using any memory services. As a result, this function is not allowed to
749 call any memory allocation services in its implementation. It is the caller's r
750 esponsibility to allocate and free the Destination and Scratch buffers.
751 If the compressed source data specified by Source is sucessfully decompressed
752 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
753 specified by Source is not in a valid compressed data format,
754 then RETURN_INVALID_PARAMETER is returned.
756 If Source is NULL, then ASSERT().
757 If Destination is NULL, then ASSERT().
758 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
760 @param Source The source buffer containing the compressed data.
761 @param Destination The destination buffer to store the decompressed data
762 @param Scratch A temporary scratch buffer that is used to perform the decompression.
763 This is an optional parameter that may be NULL if the
764 required scratch buffer size is 0.
766 @retval RETURN_SUCCESS Decompression is successfull
767 @retval RETURN_INVALID_PARAMETER The source data is corrupted
773 IN CONST VOID
*Source
,
774 IN OUT VOID
*Destination
,
778 volatile UINT32 Index
;
785 ASSERT (Source
!= NULL
);
786 ASSERT (Destination
!= NULL
);
787 ASSERT (Scratch
!= NULL
);
792 Sd
= (SCRATCH_DATA
*) Scratch
;
794 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
795 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
798 // If compressed file size is 0, return
801 return RETURN_SUCCESS
;
806 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
807 ((UINT8
*) Sd
)[Index
] = 0;
810 // The length of the field 'Position Set Code Length Array Size' in Block Header.
811 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
812 // For Tiano de/compression algorithm(Version 2), mPBit = 5
815 Sd
->mSrcBase
= (UINT8
*)Src
;
818 // CompSize and OrigSize are caculated in bytes
820 Sd
->mCompSize
= CompSize
;
821 Sd
->mOrigSize
= OrigSize
;
824 // Fill the first BITBUFSIZ bits
826 FillBuf (Sd
, BITBUFSIZ
);
833 if (Sd
->mBadTableFlag
!= 0) {
835 // Something wrong with the source
837 return RETURN_INVALID_PARAMETER
;
840 return RETURN_SUCCESS
;