]>
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 - 2010, Intel Corporation. All rights reserved.<BR>
5 Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
6 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.
120 If TableBits > 16, then ASSERT ().
122 @param Sd The global scratch data.
123 @param NumOfChar The number of symbols in the symbol set.
124 @param BitLen Code length array.
125 @param TableBits The width of the mapping table.
126 @param Table The table to be created.
129 @retval BAD_TABLE The table is corrupted.
157 // The maximum mapping table width supported by this internal
158 // working function is 16.
160 ASSERT (TableBits
<= 16);
162 for (Index
= 0; Index
<= 16; Index
++) {
166 for (Index
= 0; Index
< NumOfChar
; Index
++) {
167 Count
[BitLen
[Index
]]++;
173 for (Index
= 1; Index
<= 16; Index
++) {
174 WordOfStart
= Start
[Index
];
175 WordOfCount
= Count
[Index
];
176 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
179 if (Start
[17] != 0) {
181 return (UINT16
) BAD_TABLE
;
184 JuBits
= (UINT16
) (16 - TableBits
);
187 for (Index
= 1; Index
<= TableBits
; Index
++) {
188 Start
[Index
] >>= JuBits
;
189 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
192 while (Index
<= 16) {
193 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
197 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
200 Index3
= (UINT16
) (1U << TableBits
);
201 if (Index
< Index3
) {
202 SetMem16 (Table
+ Index
, (Index3
- Index
) * sizeof (*Table
), 0);
207 Mask
= (UINT16
) (1U << (15 - TableBits
));
209 for (Char
= 0; Char
< NumOfChar
; Char
++) {
212 if (Len
== 0 || Len
>= 17) {
216 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
218 if (Len
<= TableBits
) {
220 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
227 Pointer
= &Table
[Index3
>> JuBits
];
228 Index
= (UINT16
) (Len
- TableBits
);
231 if (*Pointer
== 0 && Avail
< (2 * NC
- 1)) {
232 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
236 if (*Pointer
< (2 * NC
- 1)) {
237 if ((Index3
& Mask
) != 0) {
238 Pointer
= &Sd
->mRight
[*Pointer
];
240 Pointer
= &Sd
->mLeft
[*Pointer
];
252 Start
[Len
] = NextCode
;
261 Decodes a position value.
263 Get a position value according to Position Huffman Table.
265 @param Sd The global scratch data.
267 @return The position value decoded.
279 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
282 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
286 if ((Sd
->mBitBuf
& Mask
) != 0) {
287 Val
= Sd
->mRight
[Val
];
289 Val
= Sd
->mLeft
[Val
];
293 } while (Val
>= MAXNP
);
296 // Advance what we have read
298 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
302 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
309 Reads code lengths for the Extra Set or the Position Set.
311 Read in the Extra Set or Pointion Set Length Arrary, then
312 generate the Huffman code mapping for them.
314 @param Sd The global scratch data.
315 @param nn The number of symbols.
316 @param nbit The number of bits needed to represent nn.
317 @param Special The special symbol that needs to be taken care of.
320 @retval BAD_TABLE Table is corrupted.
337 // Read Extra Set Code Length Array size
339 Number
= (UINT16
) GetBits (Sd
, nbit
);
343 // This represents only Huffman code used
345 CharC
= (UINT16
) GetBits (Sd
, nbit
);
347 SetMem16 (&Sd
->mPTTable
[0] , sizeof (Sd
->mPTTable
), CharC
);
349 SetMem (Sd
->mPTLen
, nn
, 0);
356 while (Index
< Number
&& Index
< NPT
) {
358 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
361 // If a code length is less than 7, then it is encoded as a 3-bit
362 // value. Or it is encoded as a series of "1"s followed by a
363 // terminating "0". The number of "1"s = Code length - 4.
366 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
367 while (Mask
& Sd
->mBitBuf
) {
373 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
375 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
379 // After the third length of the code length concatenation,
380 // a 2-bit value is used to indicated the number of consecutive
381 // zero lengths after the third length.
383 if (Index
== Special
) {
384 CharC
= (UINT16
) GetBits (Sd
, 2);
385 while ((INT16
) (--CharC
) >= 0 && Index
< NPT
) {
386 Sd
->mPTLen
[Index
++] = 0;
391 while (Index
< nn
&& Index
< NPT
) {
392 Sd
->mPTLen
[Index
++] = 0;
395 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
399 Reads code lengths for Char&Len Set.
401 Read in and decode the Char&Len Set Code Length Array, then
402 generate the Huffman Code mapping table for the Char&Len Set.
404 @param Sd The global scratch data.
417 Number
= (UINT16
) GetBits (Sd
, CBIT
);
421 // This represents only Huffman code used
423 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
425 SetMem (Sd
->mCLen
, NC
, 0);
426 SetMem16 (&Sd
->mCTable
[0], sizeof (Sd
->mCTable
), CharC
);
432 while (Index
< Number
&& Index
< NC
) {
433 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
435 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
439 if (Mask
& Sd
->mBitBuf
) {
440 CharC
= Sd
->mRight
[CharC
];
442 CharC
= Sd
->mLeft
[CharC
];
447 } while (CharC
>= NT
);
450 // Advance what we have read
452 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
458 } else if (CharC
== 1) {
459 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
460 } else if (CharC
== 2) {
461 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
464 while ((INT16
) (--CharC
) >= 0 && Index
< NC
) {
465 Sd
->mCLen
[Index
++] = 0;
470 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
475 SetMem (Sd
->mCLen
+ Index
, NC
- Index
, 0);
477 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
483 Decode a character/length value.
485 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
486 Huffman code mapping table for Extra Set, Code&Len Set and
489 @param Sd The global scratch data.
491 @return The value decoded.
502 if (Sd
->mBlockSize
== 0) {
504 // Starting a new block
505 // Read BlockSize from block header
507 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
510 // Read in the Extra Set Code Length Arrary,
511 // Generate the Huffman code mapping table for Extra Set.
513 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
514 if (Sd
->mBadTableFlag
!= 0) {
519 // Read in and decode the Char&Len Set Code Length Arrary,
520 // Generate the Huffman code mapping table for Char&Len Set.
525 // Read in the Position Set Code Length Arrary,
526 // Generate the Huffman code mapping table for the Position Set.
528 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
529 if (Sd
->mBadTableFlag
!= 0) {
535 // Get one code according to Code&Set Huffman Table
538 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
541 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
544 if ((Sd
->mBitBuf
& Mask
) != 0) {
545 Index2
= Sd
->mRight
[Index2
];
547 Index2
= Sd
->mLeft
[Index2
];
551 } while (Index2
>= NC
);
554 // Advance what we have read
556 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
562 Decode the source data and put the resulting data into the destination buffer.
564 @param Sd The global scratch data.
576 BytesRemain
= (UINT16
) (-1);
582 // Get one code from mBitBuf
584 CharC
= DecodeC (Sd
);
585 if (Sd
->mBadTableFlag
!= 0) {
591 // Process an Original character
593 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
597 // Write orignal character into mDstBase
599 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
606 CharC
= (UINT16
) (CharC
- (BIT8
- THRESHOLD
));
614 // Locate string position
616 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
619 // Write BytesRemain of bytes into mDstBase
622 while ((INT16
) (BytesRemain
) >= 0) {
623 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
624 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
638 Given a compressed source buffer, this function retrieves the size of
639 the uncompressed buffer and the size of the scratch buffer required
640 to decompress the compressed source buffer.
642 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
643 required to decompress the buffer specified by Source and SourceSize.
644 If the size of the uncompressed buffer or the size of the scratch buffer cannot
645 be determined from the compressed data specified by Source and SourceData,
646 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
647 buffer is returned in DestinationSize, the size of the scratch buffer is returned
648 in ScratchSize, and RETURN_SUCCESS is returned.
649 This function does not have scratch buffer available to perform a thorough
650 checking of the validity of the source data. It just retrieves the "Original Size"
651 field from the beginning bytes of the source data and output it as DestinationSize.
652 And ScratchSize is specific to the decompression implementation.
654 If Source is NULL, then ASSERT().
655 If DestinationSize is NULL, then ASSERT().
656 If ScratchSize is NULL, then ASSERT().
658 @param Source The source buffer containing the compressed data.
659 @param SourceSize The size, in bytes, of the source buffer.
660 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
661 that will be generated when the compressed buffer specified
662 by Source and SourceSize is decompressed.
663 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
664 is required to decompress the compressed buffer specified
665 by Source and SourceSize.
667 @retval RETURN_SUCCESS The size of the uncompressed data was returned
668 in DestinationSize, and the size of the scratch
669 buffer was returned in ScratchSize.
670 @retval RETURN_INVALID_PARAMETER
671 The size of the uncompressed data or the size of
672 the scratch buffer cannot be determined from
673 the compressed data specified by Source
678 UefiDecompressGetInfo (
679 IN CONST VOID
*Source
,
680 IN UINT32 SourceSize
,
681 OUT UINT32
*DestinationSize
,
682 OUT UINT32
*ScratchSize
685 UINT32 CompressedSize
;
687 ASSERT (Source
!= NULL
);
688 ASSERT (DestinationSize
!= NULL
);
689 ASSERT (ScratchSize
!= NULL
);
691 if (SourceSize
< 8) {
692 return RETURN_INVALID_PARAMETER
;
695 CompressedSize
= ReadUnaligned32 ((UINT32
*)Source
);
696 if (SourceSize
< (CompressedSize
+ 8)) {
697 return RETURN_INVALID_PARAMETER
;
700 *ScratchSize
= sizeof (SCRATCH_DATA
);
701 *DestinationSize
= ReadUnaligned32 ((UINT32
*)Source
+ 1);
703 return RETURN_SUCCESS
;
707 Decompresses a compressed source buffer.
709 Extracts decompressed data to its original form.
710 This function is designed so that the decompression algorithm can be implemented
711 without using any memory services. As a result, this function is not allowed to
712 call any memory allocation services in its implementation. It is the caller's
713 responsibility to allocate and free the Destination and Scratch buffers.
714 If the compressed source data specified by Source is successfully decompressed
715 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
716 specified by Source is not in a valid compressed data format,
717 then RETURN_INVALID_PARAMETER is returned.
719 If Source is NULL, then ASSERT().
720 If Destination is NULL, then ASSERT().
721 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
723 @param Source The source buffer containing the compressed data.
724 @param Destination The destination buffer to store the decompressed data.
725 @param Scratch A temporary scratch buffer that is used to perform the decompression.
726 This is an optional parameter that may be NULL if the
727 required scratch buffer size is 0.
729 @retval RETURN_SUCCESS Decompression completed successfully, and
730 the uncompressed buffer is returned in Destination.
731 @retval RETURN_INVALID_PARAMETER
732 The source buffer specified by Source is corrupted
733 (not in a valid compressed format).
738 IN CONST VOID
*Source
,
739 IN OUT VOID
*Destination
,
740 IN OUT VOID
*Scratch OPTIONAL
749 ASSERT (Source
!= NULL
);
750 ASSERT (Destination
!= NULL
);
751 ASSERT (Scratch
!= NULL
);
756 Sd
= (SCRATCH_DATA
*) Scratch
;
758 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
759 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
762 // If compressed file size is 0, return
765 return RETURN_SUCCESS
;
769 SetMem (Sd
, sizeof (SCRATCH_DATA
), 0);
772 // The length of the field 'Position Set Code Length Array Size' in Block Header.
773 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
776 Sd
->mSrcBase
= (UINT8
*)Src
;
779 // CompSize and OrigSize are caculated in bytes
781 Sd
->mCompSize
= CompSize
;
782 Sd
->mOrigSize
= OrigSize
;
785 // Fill the first BITBUFSIZ bits
787 FillBuf (Sd
, BITBUFSIZ
);
794 if (Sd
->mBadTableFlag
!= 0) {
796 // Something wrong with the source
798 return RETURN_INVALID_PARAMETER
;
801 return RETURN_SUCCESS
;