]>
git.proxmox.com Git - mirror_edk2.git/blob - EdkCompatibilityPkg/Sample/Tools/Source/Common/Decompress.c
3 Copyright (c) 2004 - 2006, Intel Corporation. All rights reserved.<BR>
4 This program and the accompanying materials
5 are licensed and made available under the terms and conditions of the BSD License
6 which accompanies this distribution. The full text of the license may be found at
7 http://opensource.org/licenses/bsd-license.php
9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 Decompressor. Algorithm Ported from OPSD code (Decomp.asm)
22 #include "TianoCommon.h"
26 // Decompression algorithm begins here
32 #define UINT8_MAX 0xff
36 // C: Char&Len Set; P: Position Set; T: exTra Set
38 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
42 #define MAXNP ((1U << MAXPBIT) - 1)
43 #define NT (CODE_BIT + 3)
51 UINT8
*mSrcBase
; // Starting address of compressed data
52 UINT8
*mDstBase
; // Starting address of decompressed data
65 UINT16 mLeft
[2 * NC
- 1];
66 UINT16 mRight
[2 * NC
- 1];
73 // The length of the field 'Position Set Code Length Array Size' in Block Header.
74 // For EFI 1.1 de/compression algorithm, mPBit = 4
75 // For Tiano de/compression algorithm, mPBit = 5
90 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
94 Sd - The global scratch data
95 NumOfBits - The number of bits to shift and read.
101 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
103 while (NumOfBits
> Sd
->mBitCount
) {
105 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
107 if (Sd
->mCompSize
> 0) {
109 // Get 1 byte into SubBitBuf
113 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
118 // No more bits from the source, just pad zero bit.
126 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
127 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
140 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
141 NumOfBits of bits from source. Returns NumOfBits of bits that are
146 Sd - The global scratch data.
147 NumOfBits - The number of bits to pop and read.
151 The bits that are popped out.
157 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
159 FillBuf (Sd
, NumOfBits
);
177 Creates Huffman Code mapping table according to code length array.
181 Sd - The global scratch data
182 NumOfChar - Number of symbols in the symbol set
183 BitLen - Code length array
184 TableBits - The width of the mapping table
190 BAD_TABLE - The table is corrupted.
207 for (Index
= 1; Index
<= 16; Index
++) {
211 for (Index
= 0; Index
< NumOfChar
; Index
++) {
212 Count
[BitLen
[Index
]]++;
217 for (Index
= 1; Index
<= 16; Index
++) {
218 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
221 if (Start
[17] != 0) {
223 return (UINT16
) BAD_TABLE
;
226 JuBits
= (UINT16
) (16 - TableBits
);
228 for (Index
= 1; Index
<= TableBits
; Index
++) {
229 Start
[Index
] >>= JuBits
;
230 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
233 while (Index
<= 16) {
234 Weight
[Index
++] = (UINT16
) (1U << (16 - Index
));
237 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
240 Index3
= (UINT16
) (1U << TableBits
);
241 while (Index
!= Index3
) {
247 Mask
= (UINT16
) (1U << (15 - TableBits
));
249 for (Char
= 0; Char
< NumOfChar
; Char
++) {
256 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
258 if (Len
<= TableBits
) {
260 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
267 Pointer
= &Table
[Index3
>> JuBits
];
268 Index
= (UINT16
) (Len
- TableBits
);
272 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
277 Pointer
= &Sd
->mRight
[*Pointer
];
279 Pointer
= &Sd
->mLeft
[*Pointer
];
290 Start
[Len
] = NextCode
;
307 Decodes a position value.
311 Sd - the global scratch data
315 The position value decoded.
323 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
326 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
330 if (Sd
->mBitBuf
& Mask
) {
331 Val
= Sd
->mRight
[Val
];
333 Val
= Sd
->mLeft
[Val
];
337 } while (Val
>= MAXNP
);
340 // Advance what we have read
342 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
346 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
364 Reads code lengths for the Extra Set or the Position Set
368 Sd - The global scratch data
369 nn - Number of symbols
370 nbit - Number of bits needed to represent nn
371 Special - The special symbol that needs to be taken care of
376 BAD_TABLE - Table is corrupted.
385 Number
= (UINT16
) GetBits (Sd
, nbit
);
388 CharC
= (UINT16
) GetBits (Sd
, nbit
);
390 for (Index
= 0; Index
< 256; Index
++) {
391 Sd
->mPTTable
[Index
] = CharC
;
394 for (Index
= 0; Index
< nn
; Index
++) {
395 Sd
->mPTLen
[Index
] = 0;
403 while (Index
< Number
) {
405 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
408 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
409 while (Mask
& Sd
->mBitBuf
) {
415 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
417 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
419 if (Index
== Special
) {
420 CharC
= (UINT16
) GetBits (Sd
, 2);
421 while ((INT16
) (--CharC
) >= 0) {
422 Sd
->mPTLen
[Index
++] = 0;
428 Sd
->mPTLen
[Index
++] = 0;
431 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
443 Reads code lengths for Char&Len Set.
447 Sd - the global scratch data
458 Number
= (UINT16
) GetBits (Sd
, CBIT
);
461 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
463 for (Index
= 0; Index
< NC
; Index
++) {
464 Sd
->mCLen
[Index
] = 0;
467 for (Index
= 0; Index
< 4096; Index
++) {
468 Sd
->mCTable
[Index
] = CharC
;
475 while (Index
< Number
) {
477 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
479 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
483 if (Mask
& Sd
->mBitBuf
) {
484 CharC
= Sd
->mRight
[CharC
];
486 CharC
= Sd
->mLeft
[CharC
];
491 } while (CharC
>= NT
);
494 // Advance what we have read
496 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
502 } else if (CharC
== 1) {
503 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
504 } else if (CharC
== 2) {
505 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
508 while ((INT16
) (--CharC
) >= 0) {
509 Sd
->mCLen
[Index
++] = 0;
514 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
520 Sd
->mCLen
[Index
++] = 0;
523 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
537 Decode a character/length value.
541 Sd - The global scratch data.
552 if (Sd
->mBlockSize
== 0) {
554 // Starting a new block
556 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
557 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
558 if (Sd
->mBadTableFlag
!= 0) {
564 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
565 if (Sd
->mBadTableFlag
!= 0) {
571 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
574 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
577 if (Sd
->mBitBuf
& Mask
) {
578 Index2
= Sd
->mRight
[Index2
];
580 Index2
= Sd
->mLeft
[Index2
];
584 } while (Index2
>= NC
);
587 // Advance what we have read
589 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
603 Decode the source data and put the resulting data into the destination buffer.
607 Sd - The global scratch data
617 BytesRemain
= (UINT16
) (-1);
622 CharC
= DecodeC (Sd
);
623 if (Sd
->mBadTableFlag
!= 0) {
629 // Process an Original character
631 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
634 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
641 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
645 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
648 while ((INT16
) (BytesRemain
) >= 0) {
649 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
650 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
667 OUT UINT32
*ScratchSize
673 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
677 Source - The source buffer containing the compressed data.
678 SrcSize - The size of source buffer
679 DstSize - The size of destination buffer.
680 ScratchSize - The size of scratch buffer.
684 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successfully retrieved.
685 EFI_INVALID_PARAMETER - The source data is corrupted
691 *ScratchSize
= sizeof (SCRATCH_DATA
);
695 return EFI_INVALID_PARAMETER
;
698 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
706 IN OUT VOID
*Destination
,
708 IN OUT VOID
*Scratch
,
709 IN UINT32 ScratchSize
,
716 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
720 Source - The source buffer containing the compressed data.
721 SrcSize - The size of source buffer
722 Destination - The destination buffer to store the decompressed data
723 DstSize - The size of destination buffer.
724 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
725 ScratchSize - The size of scratch buffer.
726 Version - The version of de/compression algorithm.
727 Version 1 for EFI 1.1 de/compression algorithm.
728 Version 2 for Tiano de/compression algorithm.
732 EFI_SUCCESS - Decompression is successfull
733 EFI_INVALID_PARAMETER - The source data is corrupted
745 Status
= EFI_SUCCESS
;
749 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
750 return EFI_INVALID_PARAMETER
;
753 Sd
= (SCRATCH_DATA
*) Scratch
;
756 return EFI_INVALID_PARAMETER
;
759 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
760 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
763 // If compressed file size is 0, return
769 if (SrcSize
< CompSize
+ 8) {
770 return EFI_INVALID_PARAMETER
;
773 if (DstSize
!= OrigSize
) {
774 return EFI_INVALID_PARAMETER
;
779 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
780 ((UINT8
*) Sd
)[Index
] = 0;
783 // The length of the field 'Position Set Code Length Array Size' in Block Header.
784 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
785 // For Tiano de/compression algorithm(Version 2), mPBit = 5
798 // Currently, only have 2 versions
800 return EFI_INVALID_PARAMETER
;
805 Sd
->mCompSize
= CompSize
;
806 Sd
->mOrigSize
= OrigSize
;
809 // Fill the first BITBUFSIZ bits
811 FillBuf (Sd
, BITBUFSIZ
);
818 if (Sd
->mBadTableFlag
!= 0) {
820 // Something wrong with the source
822 Status
= EFI_INVALID_PARAMETER
;
834 OUT UINT32
*ScratchSize
840 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.GetInfo().
844 This - The protocol instance pointer
845 Source - The source buffer containing the compressed data.
846 SrcSize - The size of source buffer
847 DstSize - The size of destination buffer.
848 ScratchSize - The size of scratch buffer.
852 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successfully retrieved.
853 EFI_INVALID_PARAMETER - The source data is corrupted
870 IN OUT VOID
*Destination
,
872 IN OUT VOID
*Scratch
,
873 IN UINT32 ScratchSize
879 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.Decompress().
883 This - The protocol instance pointer
884 Source - The source buffer containing the compressed data.
885 SrcSize - The size of source buffer
886 Destination - The destination buffer to store the decompressed data
887 DstSize - The size of destination buffer.
888 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
889 ScratchSize - The size of scratch buffer.
893 EFI_SUCCESS - Decompression is successfull
894 EFI_INVALID_PARAMETER - The source data is corrupted
899 // For EFI 1.1 de/compression algorithm, the version is 1.
918 OUT UINT32
*ScratchSize
924 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
928 This - The protocol instance pointer
929 Source - The source buffer containing the compressed data.
930 SrcSize - The size of source buffer
931 DstSize - The size of destination buffer.
932 ScratchSize - The size of scratch buffer.
936 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successfully retrieved.
937 EFI_INVALID_PARAMETER - The source data is corrupted
954 IN OUT VOID
*Destination
,
956 IN OUT VOID
*Scratch
,
957 IN UINT32 ScratchSize
963 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
967 This - The protocol instance pointer
968 Source - The source buffer containing the compressed data.
969 SrcSize - The size of source buffer
970 Destination - The destination buffer to store the decompressed data
971 DstSize - The size of destination buffer.
972 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
973 ScratchSize - The size of scratch buffer.
977 EFI_SUCCESS - Decompression is successfull
978 EFI_INVALID_PARAMETER - The source data is corrupted
983 // For Tiano de/compression algorithm, the version is 2.