]>
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<BR>
5 Portions copyright (c) 2008-2009 Apple Inc. All rights reserved.<BR>
6 All rights reserved. This program and the accompanying materials
7 are licensed and made available under the terms and conditions of the BSD License
8 which accompanies this distribution. The full text of the license may be found at
9 http://opensource.org/licenses/bsd-license.php
11 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
12 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 #include <Library/BaseLib.h>
19 #include <Library/DebugLib.h>
20 #include <Library/BaseMemoryLib.h>
21 #include <Library/UefiDecompressLib.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.
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 if (Index
< Index3
) {
196 SetMem16 (Table
+ Index
, (Index3
- Index
) * sizeof (*Table
), 0);
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
);
225 if (*Pointer
== 0 && Avail
< (2 * NC
- 1)) {
226 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
230 if (*Pointer
< (2 * NC
- 1)) {
231 if ((Index3
& Mask
) != 0) {
232 Pointer
= &Sd
->mRight
[*Pointer
];
234 Pointer
= &Sd
->mLeft
[*Pointer
];
246 Start
[Len
] = NextCode
;
255 Decodes a position value.
257 Get a position value according to Position Huffman Table.
259 @param Sd the global scratch data
261 @return The position value decoded.
273 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
276 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
280 if ((Sd
->mBitBuf
& Mask
) != 0) {
281 Val
= Sd
->mRight
[Val
];
283 Val
= Sd
->mLeft
[Val
];
287 } while (Val
>= MAXNP
);
290 // Advance what we have read
292 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
296 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
303 Reads code lengths for the Extra Set or the Position Set.
305 Read in the Extra Set or Pointion Set Length Arrary, then
306 generate the Huffman code mapping for them.
308 @param Sd The global scratch data.
309 @param nn Number of symbols.
310 @param nbit Number of bits needed to represent nn.
311 @param Special The special symbol that needs to be taken care of.
314 @retval BAD_TABLE Table is corrupted.
331 // Read Extra Set Code Length Array size
333 Number
= (UINT16
) GetBits (Sd
, nbit
);
337 // This represents only Huffman code used
339 CharC
= (UINT16
) GetBits (Sd
, nbit
);
341 SetMem16 (&Sd
->mPTTable
[0] , sizeof (Sd
->mPTTable
), CharC
);
343 SetMem (Sd
->mPTLen
, nn
, 0);
350 while (Index
< Number
&& Index
< NPT
) {
352 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
355 // If a code length is less than 7, then it is encoded as a 3-bit
356 // value. Or it is encoded as a series of "1"s followed by a
357 // terminating "0". The number of "1"s = Code length - 4.
360 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
361 while (Mask
& Sd
->mBitBuf
) {
367 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
369 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
373 // After the third length of the code length concatenation,
374 // a 2-bit value is used to indicated the number of consecutive
375 // zero lengths after the third length.
377 if (Index
== Special
) {
378 CharC
= (UINT16
) GetBits (Sd
, 2);
379 while ((INT16
) (--CharC
) >= 0 && Index
< NPT
) {
380 Sd
->mPTLen
[Index
++] = 0;
385 while (Index
< nn
&& Index
< NPT
) {
386 Sd
->mPTLen
[Index
++] = 0;
389 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
393 Reads code lengths for Char&Len Set.
395 Read in and decode the Char&Len Set Code Length Array, then
396 generate the Huffman Code mapping table for the Char&Len Set.
398 @param Sd the global scratch data
411 Number
= (UINT16
) GetBits (Sd
, CBIT
);
415 // This represents only Huffman code used
417 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
419 SetMem (Sd
->mCLen
, NC
, 0);
420 SetMem16 (&Sd
->mCTable
[0], sizeof (Sd
->mCTable
), CharC
);
426 while (Index
< Number
&& Index
< NC
) {
427 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
429 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
433 if (Mask
& Sd
->mBitBuf
) {
434 CharC
= Sd
->mRight
[CharC
];
436 CharC
= Sd
->mLeft
[CharC
];
441 } while (CharC
>= NT
);
444 // Advance what we have read
446 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
452 } else if (CharC
== 1) {
453 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
454 } else if (CharC
== 2) {
455 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
458 while ((INT16
) (--CharC
) >= 0 && Index
< NC
) {
459 Sd
->mCLen
[Index
++] = 0;
464 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
469 SetMem (Sd
->mCLen
+ Index
, NC
- Index
, 0);
471 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
477 Decode a character/length value.
479 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
480 Huffman code mapping table for Extra Set, Code&Len Set and
483 @param Sd The global scratch data.
485 @return The value decoded.
496 if (Sd
->mBlockSize
== 0) {
498 // Starting a new block
499 // Read BlockSize from block header
501 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
504 // Read in the Extra Set Code Length Arrary,
505 // Generate the Huffman code mapping table for Extra Set.
507 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
508 if (Sd
->mBadTableFlag
!= 0) {
513 // Read in and decode the Char&Len Set Code Length Arrary,
514 // Generate the Huffman code mapping table for Char&Len Set.
519 // Read in the Position Set Code Length Arrary,
520 // Generate the Huffman code mapping table for the Position Set.
522 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
523 if (Sd
->mBadTableFlag
!= 0) {
529 // Get one code according to Code&Set Huffman Table
532 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
535 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
538 if ((Sd
->mBitBuf
& Mask
) != 0) {
539 Index2
= Sd
->mRight
[Index2
];
541 Index2
= Sd
->mLeft
[Index2
];
545 } while (Index2
>= NC
);
548 // Advance what we have read
550 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
556 Decode the source data and put the resulting data into the destination buffer.
558 @param Sd The global scratch data
570 BytesRemain
= (UINT16
) (-1);
576 // Get one code from mBitBuf
578 CharC
= DecodeC (Sd
);
579 if (Sd
->mBadTableFlag
!= 0) {
585 // Process an Original character
587 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
591 // Write orignal character into mDstBase
593 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
600 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
608 // Locate string position
610 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
613 // Write BytesRemain of bytes into mDstBase
616 while ((INT16
) (BytesRemain
) >= 0) {
617 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
618 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
632 Given a compressed source buffer, this function retrieves the size of
633 the uncompressed buffer and the size of the scratch buffer required
634 to decompress the compressed source buffer.
636 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
637 required to decompress the buffer specified by Source and SourceSize.
638 If the size of the uncompressed buffer or the size of the scratch buffer cannot
639 be determined from the compressed data specified by Source and SourceData,
640 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
641 buffer is returned in DestinationSize, the size of the scratch buffer is returned
642 in ScratchSize, and RETURN_SUCCESS is returned.
643 This function does not have scratch buffer available to perform a thorough
644 checking of the validity of the source data. It just retrieves the "Original Size"
645 field from the beginning bytes of the source data and output it as DestinationSize.
646 And ScratchSize is specific to the decompression implementation.
648 If Source is NULL, then ASSERT().
649 If DestinationSize is NULL, then ASSERT().
650 If ScratchSize is NULL, then ASSERT().
652 @param Source The source buffer containing the compressed data.
653 @param SourceSize The size, in bytes, of the source buffer.
654 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
655 that will be generated when the compressed buffer specified
656 by Source and SourceSize is decompressed..
657 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
658 is required to decompress the compressed buffer specified
659 by Source and SourceSize.
661 @retval RETURN_SUCCESS The size of the uncompressed data was returned
662 in DestinationSize and the size of the scratch
663 buffer was returned in ScratchSize.
664 @retval RETURN_INVALID_PARAMETER
665 The size of the uncompressed data or the size of
666 the scratch buffer cannot be determined from
667 the compressed data specified by Source
672 UefiDecompressGetInfo (
673 IN CONST VOID
*Source
,
674 IN UINT32 SourceSize
,
675 OUT UINT32
*DestinationSize
,
676 OUT UINT32
*ScratchSize
679 UINT32 CompressedSize
;
681 ASSERT (Source
!= NULL
);
682 ASSERT (DestinationSize
!= NULL
);
683 ASSERT (ScratchSize
!= NULL
);
685 if (SourceSize
< 8) {
686 return RETURN_INVALID_PARAMETER
;
689 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
690 if (SourceSize
< (CompressedSize
+ 8)) {
691 return RETURN_INVALID_PARAMETER
;
694 *ScratchSize
= sizeof (SCRATCH_DATA
);
695 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
697 return RETURN_SUCCESS
;
701 Decompresses a compressed source buffer.
703 Extracts decompressed data to its original form.
704 This function is designed so that the decompression algorithm can be implemented
705 without using any memory services. As a result, this function is not allowed to
706 call any memory allocation services in its implementation. It is the caller's
707 responsibility to allocate and free the Destination and Scratch buffers.
708 If the compressed source data specified by Source is successfully decompressed
709 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
710 specified by Source is not in a valid compressed data format,
711 then RETURN_INVALID_PARAMETER is returned.
713 If Source is NULL, then ASSERT().
714 If Destination is NULL, then ASSERT().
715 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
717 @param Source The source buffer containing the compressed data.
718 @param Destination The destination buffer to store the decompressed data
719 @param Scratch A temporary scratch buffer that is used to perform the decompression.
720 This is an optional parameter that may be NULL if the
721 required scratch buffer size is 0.
723 @retval RETURN_SUCCESS Decompression completed successfully, and
724 the uncompressed buffer is returned in Destination.
725 @retval RETURN_INVALID_PARAMETER
726 The source buffer specified by Source is corrupted
727 (not in a valid compressed format).
732 IN CONST VOID
*Source
,
733 IN OUT VOID
*Destination
,
734 IN OUT VOID
*Scratch OPTIONAL
743 ASSERT (Source
!= NULL
);
744 ASSERT (Destination
!= NULL
);
745 ASSERT (Scratch
!= NULL
);
750 Sd
= (SCRATCH_DATA
*) Scratch
;
752 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
753 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
756 // If compressed file size is 0, return
759 return RETURN_SUCCESS
;
763 SetMem (Sd
, sizeof (SCRATCH_DATA
), 0);
766 // The length of the field 'Position Set Code Length Array Size' in Block Header.
767 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
770 Sd
->mSrcBase
= (UINT8
*)Src
;
773 // CompSize and OrigSize are caculated in bytes
775 Sd
->mCompSize
= CompSize
;
776 Sd
->mOrigSize
= OrigSize
;
779 // Fill the first BITBUFSIZ bits
781 FillBuf (Sd
, BITBUFSIZ
);
788 if (Sd
->mBadTableFlag
!= 0) {
790 // Something wrong with the source
792 return RETURN_INVALID_PARAMETER
;
795 return RETURN_SUCCESS
;