]>
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 - 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.
17 #include <Library/BaseLib.h>
18 #include <Library/DebugLib.h>
19 #include <Library/BaseMemoryLib.h>
20 #include <Library/UefiDecompressLib.h>
22 #include "BaseUefiDecompressLibInternals.h"
25 Read NumOfBit of bits from source into mBitBuf.
27 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
29 @param Sd The global scratch data
30 @param NumOfBits The number of bits to shift and read.
40 // Left shift NumOfBits of bits in advance
42 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
45 // Copy data needed in bytes into mSbuBitBuf
47 while (NumOfBits
> Sd
->mBitCount
) {
49 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
51 if (Sd
->mCompSize
> 0) {
53 // Get 1 byte into SubBitBuf
56 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
61 // No more bits from the source, just pad zero bit.
70 // Caculate additional bit count read to update mBitCount
72 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
75 // Copy NumOfBits of bits from mSubBitBuf into mBitBuf
77 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
81 Get NumOfBits of bits out from mBitBuf.
83 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
84 NumOfBits of bits from source. Returns NumOfBits of bits that are
87 @param Sd The global scratch data.
88 @param NumOfBits The number of bits to pop and read.
90 @return The bits that are popped out.
102 // Pop NumOfBits of Bits from Left
104 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
107 // Fill up mBitBuf from source
109 FillBuf (Sd
, NumOfBits
);
115 Creates Huffman Code mapping table according to code length array.
117 Creates Huffman Code mapping table for Extra Set, Char&Len Set
118 and Position Set according to code length array.
120 @param Sd The global scratch data
121 @param NumOfChar Number of symbols in the symbol set
122 @param BitLen Code length array
123 @param TableBits The width of the mapping table
124 @param Table The table to be created.
127 @retval BAD_TABLE The table is corrupted.
155 for (Index
= 0; Index
<= 16; Index
++) {
159 for (Index
= 0; Index
< NumOfChar
; Index
++) {
160 Count
[BitLen
[Index
]]++;
166 for (Index
= 1; Index
<= 16; Index
++) {
167 WordOfStart
= Start
[Index
];
168 WordOfCount
= Count
[Index
];
169 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
172 if (Start
[17] != 0) {
174 return (UINT16
) BAD_TABLE
;
177 JuBits
= (UINT16
) (16 - TableBits
);
180 for (Index
= 1; Index
<= TableBits
; Index
++) {
181 Start
[Index
] >>= JuBits
;
182 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
185 while (Index
<= 16) {
186 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
190 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
193 Index3
= (UINT16
) (1U << TableBits
);
194 if (Index
< Index3
) {
195 SetMem16 (Table
+ Index
, (Index3
- Index
) * sizeof (*Table
), 0);
200 Mask
= (UINT16
) (1U << (15 - TableBits
));
202 for (Char
= 0; Char
< NumOfChar
; Char
++) {
205 if (Len
== 0 || Len
>= 17) {
209 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
211 if (Len
<= TableBits
) {
213 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
220 Pointer
= &Table
[Index3
>> JuBits
];
221 Index
= (UINT16
) (Len
- TableBits
);
224 if (*Pointer
== 0 && Avail
< (2 * NC
- 1)) {
225 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
229 if (*Pointer
< (2 * NC
- 1)) {
230 if ((Index3
& Mask
) != 0) {
231 Pointer
= &Sd
->mRight
[*Pointer
];
233 Pointer
= &Sd
->mLeft
[*Pointer
];
245 Start
[Len
] = NextCode
;
254 Decodes a position value.
256 Get a position value according to Position Huffman Table.
258 @param Sd the global scratch data
260 @return The position value decoded.
272 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
275 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
279 if ((Sd
->mBitBuf
& Mask
) != 0) {
280 Val
= Sd
->mRight
[Val
];
282 Val
= Sd
->mLeft
[Val
];
286 } while (Val
>= MAXNP
);
289 // Advance what we have read
291 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
295 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
302 Reads code lengths for the Extra Set or the Position Set.
304 Read in the Extra Set or Pointion Set Length Arrary, then
305 generate the Huffman code mapping for them.
307 @param Sd The global scratch data.
308 @param nn Number of symbols.
309 @param nbit Number of bits needed to represent nn.
310 @param Special The special symbol that needs to be taken care of.
313 @retval BAD_TABLE Table is corrupted.
330 // Read Extra Set Code Length Array size
332 Number
= (UINT16
) GetBits (Sd
, nbit
);
336 // This represents only Huffman code used
338 CharC
= (UINT16
) GetBits (Sd
, nbit
);
340 for (Index
= 0; Index
< 256; Index
++) {
341 Sd
->mPTTable
[Index
] = CharC
;
344 SetMem (Sd
->mPTLen
, nn
, 0);
351 while (Index
< Number
&& Index
< NPT
) {
353 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
356 // If a code length is less than 7, then it is encoded as a 3-bit
357 // value. Or it is encoded as a series of "1"s followed by a
358 // terminating "0". The number of "1"s = Code length - 4.
361 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
362 while (Mask
& Sd
->mBitBuf
) {
368 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
370 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
374 // After the third length of the code length concatenation,
375 // a 2-bit value is used to indicated the number of consecutive
376 // zero lengths after the third length.
378 if (Index
== Special
) {
379 CharC
= (UINT16
) GetBits (Sd
, 2);
380 while ((INT16
) (--CharC
) >= 0 && Index
< NPT
) {
381 Sd
->mPTLen
[Index
++] = 0;
386 while (Index
< nn
&& Index
< NPT
) {
387 Sd
->mPTLen
[Index
++] = 0;
390 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
394 Reads code lengths for Char&Len Set.
396 Read in and decode the Char&Len Set Code Length Array, then
397 generate the Huffman Code mapping table for the Char&Len Set.
399 @param Sd the global scratch data
412 Number
= (UINT16
) GetBits (Sd
, CBIT
);
416 // This represents only Huffman code used
418 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
420 SetMem (Sd
->mCLen
, NC
, 0);
422 for (Index
= 0; Index
< 4096; Index
++) {
423 Sd
->mCTable
[Index
] = CharC
;
430 while (Index
< Number
&& Index
< NC
) {
431 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
433 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
437 if (Mask
& Sd
->mBitBuf
) {
438 CharC
= Sd
->mRight
[CharC
];
440 CharC
= Sd
->mLeft
[CharC
];
445 } while (CharC
>= NT
);
448 // Advance what we have read
450 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
456 } else if (CharC
== 1) {
457 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
458 } else if (CharC
== 2) {
459 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
462 while ((INT16
) (--CharC
) >= 0 && Index
< NC
) {
463 Sd
->mCLen
[Index
++] = 0;
468 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
473 SetMem (Sd
->mCLen
+ Index
, NC
- Index
, 0);
475 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
481 Decode a character/length value.
483 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
484 Huffman code mapping table for Extra Set, Code&Len Set and
487 @param Sd The global scratch data.
489 @return The value decoded.
500 if (Sd
->mBlockSize
== 0) {
502 // Starting a new block
503 // Read BlockSize from block header
505 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
508 // Read in the Extra Set Code Length Arrary,
509 // Generate the Huffman code mapping table for Extra Set.
511 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
512 if (Sd
->mBadTableFlag
!= 0) {
517 // Read in and decode the Char&Len Set Code Length Arrary,
518 // Generate the Huffman code mapping table for Char&Len Set.
523 // Read in the Position Set Code Length Arrary,
524 // Generate the Huffman code mapping table for the Position Set.
526 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
527 if (Sd
->mBadTableFlag
!= 0) {
533 // Get one code according to Code&Set Huffman Table
536 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
539 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
542 if ((Sd
->mBitBuf
& Mask
) != 0) {
543 Index2
= Sd
->mRight
[Index2
];
545 Index2
= Sd
->mLeft
[Index2
];
549 } while (Index2
>= NC
);
552 // Advance what we have read
554 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
560 Decode the source data and put the resulting data into the destination buffer.
562 @param Sd The global scratch data
574 BytesRemain
= (UINT16
) (-1);
580 // Get one code from mBitBuf
582 CharC
= DecodeC (Sd
);
583 if (Sd
->mBadTableFlag
!= 0) {
589 // Process an Original character
591 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
595 // Write orignal character into mDstBase
597 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
604 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
612 // Locate string position
614 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
617 // Write BytesRemain of bytes into mDstBase
620 while ((INT16
) (BytesRemain
) >= 0) {
621 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
622 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
636 Given a compressed source buffer, this function retrieves the size of
637 the uncompressed buffer and the size of the scratch buffer required
638 to decompress the compressed source buffer.
640 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
641 required to decompress the buffer specified by Source and SourceSize.
642 If the size of the uncompressed buffer or the size of the scratch buffer cannot
643 be determined from the compressed data specified by Source and SourceData,
644 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
645 buffer is returned in DestinationSize, the size of the scratch buffer is returned
646 in ScratchSize, and RETURN_SUCCESS is returned.
647 This function does not have scratch buffer available to perform a thorough
648 checking of the validity of the source data. It just retrieves the "Original Size"
649 field from the beginning bytes of the source data and output it as DestinationSize.
650 And ScratchSize is specific to the decompression implementation.
652 If Source is NULL, then ASSERT().
653 If DestinationSize is NULL, then ASSERT().
654 If ScratchSize is NULL, then ASSERT().
656 @param Source The source buffer containing the compressed data.
657 @param SourceSize The size, in bytes, of the source buffer.
658 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
659 that will be generated when the compressed buffer specified
660 by Source and SourceSize is decompressed..
661 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
662 is required to decompress the compressed buffer specified
663 by Source and SourceSize.
665 @retval RETURN_SUCCESS The size of the uncompressed data was returned
666 in DestinationSize and the size of the scratch
667 buffer was returned in ScratchSize.
668 @retval RETURN_INVALID_PARAMETER
669 The size of the uncompressed data or the size of
670 the scratch buffer cannot be determined from
671 the compressed data specified by Source
676 UefiDecompressGetInfo (
677 IN CONST VOID
*Source
,
678 IN UINT32 SourceSize
,
679 OUT UINT32
*DestinationSize
,
680 OUT UINT32
*ScratchSize
683 UINT32 CompressedSize
;
685 ASSERT (Source
!= NULL
);
686 ASSERT (DestinationSize
!= NULL
);
687 ASSERT (ScratchSize
!= NULL
);
689 if (SourceSize
< 8) {
690 return RETURN_INVALID_PARAMETER
;
693 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
694 if (SourceSize
< (CompressedSize
+ 8)) {
695 return RETURN_INVALID_PARAMETER
;
698 *ScratchSize
= sizeof (SCRATCH_DATA
);
699 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
701 return RETURN_SUCCESS
;
705 Decompresses a compressed source buffer.
707 Extracts decompressed data to its original form.
708 This function is designed so that the decompression algorithm can be implemented
709 without using any memory services. As a result, this function is not allowed to
710 call any memory allocation services in its implementation. It is the caller's r
711 esponsibility to allocate and free the Destination and Scratch buffers.
712 If the compressed source data specified by Source is sucessfully decompressed
713 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
714 specified by Source is not in a valid compressed data format,
715 then RETURN_INVALID_PARAMETER is returned.
717 If Source is NULL, then ASSERT().
718 If Destination is NULL, then ASSERT().
719 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
721 @param Source The source buffer containing the compressed data.
722 @param Destination The destination buffer to store the decompressed data
723 @param Scratch A temporary scratch buffer that is used to perform the decompression.
724 This is an optional parameter that may be NULL if the
725 required scratch buffer size is 0.
727 @retval RETURN_SUCCESS Decompression completed successfully, and
728 the uncompressed buffer is returned in Destination.
729 @retval RETURN_INVALID_PARAMETER
730 The source buffer specified by Source is corrupted
731 (not in a valid compressed format).
736 IN CONST VOID
*Source
,
737 IN OUT VOID
*Destination
,
738 IN OUT VOID
*Scratch OPTIONAL
747 ASSERT (Source
!= NULL
);
748 ASSERT (Destination
!= NULL
);
749 ASSERT (Scratch
!= NULL
);
754 Sd
= (SCRATCH_DATA
*) Scratch
;
756 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
757 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
760 // If compressed file size is 0, return
763 return RETURN_SUCCESS
;
767 SetMem (Sd
, sizeof (SCRATCH_DATA
), 0);
770 // The length of the field 'Position Set Code Length Array Size' in Block Header.
771 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
774 Sd
->mSrcBase
= (UINT8
*)Src
;
777 // CompSize and OrigSize are caculated in bytes
779 Sd
->mCompSize
= CompSize
;
780 Sd
->mOrigSize
= OrigSize
;
783 // Fill the first BITBUFSIZ bits
785 FillBuf (Sd
, BITBUFSIZ
);
792 if (Sd
->mBadTableFlag
!= 0) {
794 // Something wrong with the source
796 return RETURN_INVALID_PARAMETER
;
799 return RETURN_SUCCESS
;