]>
git.proxmox.com Git - mirror_edk2.git/blob - OldMdePkg/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
17 #include "BaseUefiDecompressLibInternals.h"
20 Read NumOfBit of bits from source into mBitBuf
22 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
24 @param Sd The global scratch data
25 @param NumOfBits The number of bits to shift and read.
35 // Left shift NumOfBits of bits in advance
37 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
40 // Copy data needed in bytes into mSbuBitBuf
42 while (NumOfBits
> Sd
->mBitCount
) {
44 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
46 if (Sd
->mCompSize
> 0) {
48 // Get 1 byte into SubBitBuf
51 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
56 // No more bits from the source, just pad zero bit.
65 // Caculate additional bit count read to update mBitCount
67 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
70 // Copy NumOfBits of bits from mSubBitBuf into mBitBuf
72 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
76 Get NumOfBits of bits out from mBitBuf
78 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
79 NumOfBits of bits from source. Returns NumOfBits of bits that are
82 @param Sd The global scratch data.
83 @param NumOfBits The number of bits to pop and read.
85 @return The bits that are popped out.
97 // Pop NumOfBits of Bits from Left
99 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
102 // Fill up mBitBuf from source
104 FillBuf (Sd
, NumOfBits
);
110 Creates Huffman Code mapping table according to code length array.
112 Creates Huffman Code mapping table for Extra Set, Char&Len Set
113 and Position Set according to code length array.
115 @param Sd The global scratch data
116 @param NumOfChar Number of symbols in the symbol set
117 @param BitLen Code length array
118 @param TableBits The width of the mapping table
119 @param Table The table
122 @retval BAD_TABLE The table is corrupted.
139 volatile UINT16 Index
;
150 for (Index
= 1; Index
<= 16; Index
++) {
154 for (Index
= 0; Index
< NumOfChar
; Index
++) {
155 Count
[BitLen
[Index
]]++;
160 for (Index
= 1; Index
<= 16; Index
++) {
161 WordOfStart
= Start
[Index
];
162 WordOfCount
= Count
[Index
];
163 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
166 if (Start
[17] != 0) {
168 return (UINT16
) BAD_TABLE
;
171 JuBits
= (UINT16
) (16 - TableBits
);
173 for (Index
= 1; Index
<= TableBits
; Index
++) {
174 Start
[Index
] >>= JuBits
;
175 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
178 while (Index
<= 16) {
179 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
183 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
186 Index3
= (UINT16
) (1U << TableBits
);
187 while (Index
!= Index3
) {
193 Mask
= (UINT16
) (1U << (15 - TableBits
));
195 for (Char
= 0; Char
< NumOfChar
; Char
++) {
202 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
204 if (Len
<= TableBits
) {
206 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
213 Pointer
= &Table
[Index3
>> JuBits
];
214 Index
= (UINT16
) (Len
- TableBits
);
218 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
223 Pointer
= &Sd
->mRight
[*Pointer
];
225 Pointer
= &Sd
->mLeft
[*Pointer
];
236 Start
[Len
] = NextCode
;
245 Decodes a position value.
247 Get a position value according to Position Huffman Table.
249 @param Sd the global scratch data
251 @return The position value decoded.
263 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
266 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
270 if (Sd
->mBitBuf
& Mask
) {
271 Val
= Sd
->mRight
[Val
];
273 Val
= Sd
->mLeft
[Val
];
277 } while (Val
>= MAXNP
);
280 // Advance what we have read
282 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
286 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
293 Reads code lengths for the Extra Set or the Position Set.
295 Read in the Extra Set or Pointion Set Length Arrary, then
296 generate the Huffman code mapping for them.
298 @param Sd The global scratch data.
299 @param nn Number of symbols.
300 @param nbit Number of bits needed to represent nn.
301 @param Special The special symbol that needs to be taken care of.
304 @retval BAD_TABLE Table is corrupted.
317 volatile UINT16 Index
;
321 // Read Extra Set Code Length Array size
323 Number
= (UINT16
) GetBits (Sd
, nbit
);
327 // This represents only Huffman code used
329 CharC
= (UINT16
) GetBits (Sd
, nbit
);
331 for (Index
= 0; Index
< 256; Index
++) {
332 Sd
->mPTTable
[Index
] = CharC
;
335 for (Index
= 0; Index
< nn
; Index
++) {
336 Sd
->mPTLen
[Index
] = 0;
344 while (Index
< Number
) {
346 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
349 // If a code length is less than 7, then it is encoded as a 3-bit
350 // value. Or it is encoded as a series of "1"s followed by a
351 // terminating "0". The number of "1"s = Code length - 4.
354 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
355 while (Mask
& Sd
->mBitBuf
) {
361 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
363 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
367 // After the third length of the code length concatenation,
368 // a 2-bit value is used to indicated the number of consecutive
369 // zero lengths after the third length.
371 if (Index
== Special
) {
372 CharC
= (UINT16
) GetBits (Sd
, 2);
373 while ((INT16
) (--CharC
) >= 0) {
374 Sd
->mPTLen
[Index
++] = 0;
380 Sd
->mPTLen
[Index
++] = 0;
383 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
387 Reads code lengths for Char&Len Set.
389 Read in and decode the Char&Len Set Code Length Array, then
390 generate the Huffman Code mapping table for the Char&Len Set.
392 @param Sd the global scratch data
402 volatile UINT16 Index
;
405 Number
= (UINT16
) GetBits (Sd
, CBIT
);
409 // This represents only Huffman code used
411 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
413 for (Index
= 0; Index
< NC
; Index
++) {
414 Sd
->mCLen
[Index
] = 0;
417 for (Index
= 0; Index
< 4096; Index
++) {
418 Sd
->mCTable
[Index
] = CharC
;
425 while (Index
< Number
) {
426 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
428 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
432 if (Mask
& Sd
->mBitBuf
) {
433 CharC
= Sd
->mRight
[CharC
];
435 CharC
= Sd
->mLeft
[CharC
];
440 } while (CharC
>= NT
);
443 // Advance what we have read
445 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
451 } else if (CharC
== 1) {
452 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
453 } else if (CharC
== 2) {
454 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
457 while ((INT16
) (--CharC
) >= 0) {
458 Sd
->mCLen
[Index
++] = 0;
463 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
469 Sd
->mCLen
[Index
++] = 0;
472 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
478 Decode a character/length value.
480 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
481 Huffman code mapping table for Extra Set, Code&Len Set and
484 @param Sd The global scratch data.
486 @return The value decoded.
497 if (Sd
->mBlockSize
== 0) {
499 // Starting a new block
500 // Read BlockSize from block header
502 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
505 // Read in the Extra Set Code Length Arrary,
506 // Generate the Huffman code mapping table for Extra Set.
508 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
509 if (Sd
->mBadTableFlag
!= 0) {
514 // Read in and decode the Char&Len Set Code Length Arrary,
515 // Generate the Huffman code mapping table for Char&Len Set.
520 // Read in the Position Set Code Length Arrary,
521 // Generate the Huffman code mapping table for the Position Set.
523 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
524 if (Sd
->mBadTableFlag
!= 0) {
530 // Get one code according to Code&Set Huffman Table
533 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
536 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
539 if (Sd
->mBitBuf
& Mask
) {
540 Index2
= Sd
->mRight
[Index2
];
542 Index2
= Sd
->mLeft
[Index2
];
546 } while (Index2
>= NC
);
549 // Advance what we have read
551 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
557 Decode the source data and put the resulting data into the destination buffer.
559 Decode the source data and put the resulting data into the destination buffer.
561 @param Sd The global scratch data
573 BytesRemain
= (UINT16
) (-1);
579 // Get one code from mBitBuf
581 CharC
= DecodeC (Sd
);
582 if (Sd
->mBadTableFlag
!= 0) {
588 // Process an Original character
590 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
594 // Write orignal character into mDstBase
596 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
603 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
611 // Locate string position
613 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
616 // Write BytesRemain of bytes into mDstBase
619 while ((INT16
) (BytesRemain
) >= 0) {
620 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
621 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
635 Retrieves the size of the uncompressed buffer and the size of the scratch buffer.
637 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
638 required to decompress the buffer specified by Source and SourceSize.
639 If the size of the uncompressed buffer or the size of the scratch buffer cannot
640 be determined from the compressed data specified by Source and SourceData,
641 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
642 buffer is returned in DestinationSize, the size of the scratch buffer is returned
643 in ScratchSize, and RETURN_SUCCESS is returned.
644 This function does not have scratch buffer available to perform a thorough
645 checking of the validity of the source data. It just retrieves the "Original Size"
646 field from the beginning bytes of the source data and output it as DestinationSize.
647 And ScratchSize is specific to the decompression implementation.
649 If Source is NULL, then ASSERT().
650 If DestinationSize is NULL, then ASSERT().
651 If ScratchSize is NULL, then ASSERT().
653 @param Source The source buffer containing the compressed data.
654 @param SourceSize The size, in bytes, of the source buffer.
655 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
656 that will be generated when the compressed buffer specified
657 by Source and SourceSize is decompressed..
658 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
659 is required to decompress the compressed buffer specified
660 by Source and SourceSize.
662 @retval RETURN_SUCCESS The size of destination buffer and the size of scratch
663 buffer are successull retrieved.
664 @retval RETURN_INVALID_PARAMETER The source data is corrupted
669 UefiDecompressGetInfo (
670 IN CONST VOID
*Source
,
671 IN UINT32 SourceSize
,
672 OUT UINT32
*DestinationSize
,
673 OUT UINT32
*ScratchSize
676 UINT32 CompressedSize
;
678 ASSERT (Source
!= NULL
);
679 ASSERT (DestinationSize
!= NULL
);
680 ASSERT (ScratchSize
!= NULL
);
682 *ScratchSize
= sizeof (SCRATCH_DATA
);
684 if (SourceSize
< 8) {
685 return RETURN_INVALID_PARAMETER
;
688 CopyMem (&CompressedSize
, Source
, sizeof (UINT32
));
689 CopyMem (DestinationSize
, (VOID
*)((UINT8
*)Source
+ 4), sizeof (UINT32
));
691 if (SourceSize
< (CompressedSize
+ 8)) {
692 return RETURN_INVALID_PARAMETER
;
695 return RETURN_SUCCESS
;
699 Decompresses a compressed source buffer.
701 This function is designed so that the decompression algorithm can be implemented
702 without using any memory services. As a result, this function is not allowed to
703 call any memory allocation services in its implementation. It is the caller's r
704 esponsibility to allocate and free the Destination and Scratch buffers.
705 If the compressed source data specified by Source is sucessfully decompressed
706 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
707 specified by Source is not in a valid compressed data format,
708 then RETURN_INVALID_PARAMETER is returned.
710 If Source is NULL, then ASSERT().
711 If Destination is NULL, then ASSERT().
712 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
714 @param Source The source buffer containing the compressed data.
715 @param Destination The destination buffer to store the decompressed data
716 @param Scratch A temporary scratch buffer that is used to perform the decompression.
717 This is an optional parameter that may be NULL if the
718 required scratch buffer size is 0.
720 @retval RETURN_SUCCESS Decompression is successfull
721 @retval RETURN_INVALID_PARAMETER The source data is corrupted
727 IN CONST VOID
*Source
,
728 IN OUT VOID
*Destination
,
732 volatile UINT32 Index
;
739 ASSERT (Source
!= NULL
);
740 ASSERT (Destination
!= NULL
);
741 ASSERT (Scratch
!= NULL
);
746 Sd
= (SCRATCH_DATA
*) Scratch
;
748 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
749 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
752 // If compressed file size is 0, return
755 return RETURN_SUCCESS
;
760 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
761 ((UINT8
*) Sd
)[Index
] = 0;
764 // The length of the field 'Position Set Code Length Array Size' in Block Header.
765 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
766 // For Tiano de/compression algorithm(Version 2), mPBit = 5
769 Sd
->mSrcBase
= (UINT8
*)Src
;
772 // CompSize and OrigSize are caculated in bytes
774 Sd
->mCompSize
= CompSize
;
775 Sd
->mOrigSize
= OrigSize
;
778 // Fill the first BITBUFSIZ bits
780 FillBuf (Sd
, BITBUFSIZ
);
787 if (Sd
->mBadTableFlag
!= 0) {
789 // Something wrong with the source
791 return RETURN_INVALID_PARAMETER
;
794 return RETURN_SUCCESS
;