]>
git.proxmox.com Git - mirror_edk2.git/blob - DuetPkg/EfiLdr/TianoDecompress.c
3 Copyright (c) 2004 - 2006, Intel Corporation
4 All rights reserved. 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)
21 #include <TianoDecompress.h>
23 // Decompression algorithm begins here
29 #define UINT8_MAX 0xff
33 // C: Char&Len Set; P: Position Set; T: exTra Set
35 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
39 #define MAXNP ((1U << MAXPBIT) - 1)
40 #define NT (CODE_BIT + 3)
48 UINT8
*mSrcBase
; // Starting address of compressed data
49 UINT8
*mDstBase
; // Starting address of decompressed data
62 UINT16 mLeft
[2 * NC
- 1];
63 UINT16 mRight
[2 * NC
- 1];
70 // The length of the field 'Position Set Code Length Array Size' in Block Header.
71 // For EFI 1.1 de/compression algorithm, mPBit = 4
72 // For Tiano de/compression algorithm, mPBit = 5
87 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
91 Sd - The global scratch data
92 NumOfBits - The number of bits to shift and read.
98 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
100 while (NumOfBits
> Sd
->mBitCount
) {
102 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
104 if (Sd
->mCompSize
> 0) {
106 // Get 1 byte into SubBitBuf
110 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
115 // No more bits from the source, just pad zero bit.
123 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
124 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
137 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
138 NumOfBits of bits from source. Returns NumOfBits of bits that are
143 Sd - The global scratch data.
144 NumOfBits - The number of bits to pop and read.
148 The bits that are popped out.
154 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
156 FillBuf (Sd
, NumOfBits
);
174 Creates Huffman Code mapping table according to code length array.
178 Sd - The global scratch data
179 NumOfChar - Number of symbols in the symbol set
180 BitLen - Code length array
181 TableBits - The width of the mapping table
187 BAD_TABLE - The table is corrupted.
204 for (Index
= 1; Index
<= 16; Index
++) {
208 for (Index
= 0; Index
< NumOfChar
; Index
++) {
209 Count
[BitLen
[Index
]]++;
214 for (Index
= 1; Index
<= 16; Index
++) {
215 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
218 if (Start
[17] != 0) {
220 return (UINT16
) BAD_TABLE
;
223 JuBits
= (UINT16
) (16 - TableBits
);
225 for (Index
= 1; Index
<= TableBits
; Index
++) {
226 Start
[Index
] >>= JuBits
;
227 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
230 while (Index
<= 16) {
231 Weight
[Index
++] = (UINT16
) (1U << (16 - Index
));
234 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
237 Index3
= (UINT16
) (1U << TableBits
);
238 while (Index
!= Index3
) {
244 Mask
= (UINT16
) (1U << (15 - TableBits
));
246 for (Char
= 0; Char
< NumOfChar
; Char
++) {
253 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
255 if (Len
<= TableBits
) {
257 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
264 Pointer
= &Table
[Index3
>> JuBits
];
265 Index
= (UINT16
) (Len
- TableBits
);
269 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
274 Pointer
= &Sd
->mRight
[*Pointer
];
276 Pointer
= &Sd
->mLeft
[*Pointer
];
287 Start
[Len
] = NextCode
;
304 Decodes a position value.
308 Sd - the global scratch data
312 The position value decoded.
320 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
323 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
327 if (Sd
->mBitBuf
& Mask
) {
328 Val
= Sd
->mRight
[Val
];
330 Val
= Sd
->mLeft
[Val
];
334 } while (Val
>= MAXNP
);
337 // Advance what we have read
339 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
343 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
361 Reads code lengths for the Extra Set or the Position Set
365 Sd - The global scratch data
366 nn - Number of symbols
367 nbit - Number of bits needed to represent nn
368 Special - The special symbol that needs to be taken care of
373 BAD_TABLE - Table is corrupted.
382 Number
= (UINT16
) GetBits (Sd
, nbit
);
385 CharC
= (UINT16
) GetBits (Sd
, nbit
);
387 for (Index
= 0; Index
< 256; Index
++) {
388 Sd
->mPTTable
[Index
] = CharC
;
391 for (Index
= 0; Index
< nn
; Index
++) {
392 Sd
->mPTLen
[Index
] = 0;
400 while (Index
< Number
) {
402 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
405 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
406 while (Mask
& Sd
->mBitBuf
) {
412 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
414 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
416 if (Index
== Special
) {
417 CharC
= (UINT16
) GetBits (Sd
, 2);
418 while ((INT16
) (--CharC
) >= 0) {
419 Sd
->mPTLen
[Index
++] = 0;
425 Sd
->mPTLen
[Index
++] = 0;
428 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
440 Reads code lengths for Char&Len Set.
444 Sd - the global scratch data
455 Number
= (UINT16
) GetBits (Sd
, CBIT
);
458 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
460 for (Index
= 0; Index
< NC
; Index
++) {
461 Sd
->mCLen
[Index
] = 0;
464 for (Index
= 0; Index
< 4096; Index
++) {
465 Sd
->mCTable
[Index
] = CharC
;
472 while (Index
< Number
) {
474 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
476 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
480 if (Mask
& Sd
->mBitBuf
) {
481 CharC
= Sd
->mRight
[CharC
];
483 CharC
= Sd
->mLeft
[CharC
];
488 } while (CharC
>= NT
);
491 // Advance what we have read
493 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
499 } else if (CharC
== 1) {
500 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
501 } else if (CharC
== 2) {
502 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
505 while ((INT16
) (--CharC
) >= 0) {
506 Sd
->mCLen
[Index
++] = 0;
511 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
517 Sd
->mCLen
[Index
++] = 0;
520 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
534 Decode a character/length value.
538 Sd - The global scratch data.
549 if (Sd
->mBlockSize
== 0) {
551 // Starting a new block
553 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
554 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
555 if (Sd
->mBadTableFlag
!= 0) {
561 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
562 if (Sd
->mBadTableFlag
!= 0) {
568 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
571 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
574 if (Sd
->mBitBuf
& Mask
) {
575 Index2
= Sd
->mRight
[Index2
];
577 Index2
= Sd
->mLeft
[Index2
];
581 } while (Index2
>= NC
);
584 // Advance what we have read
586 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
600 Decode the source data and put the resulting data into the destination buffer.
604 Sd - The global scratch data
614 BytesRemain
= (UINT16
) (-1);
619 CharC
= DecodeC (Sd
);
620 if (Sd
->mBadTableFlag
!= 0) {
626 // Process an Original character
628 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
631 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
638 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
642 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
645 while ((INT16
) (BytesRemain
) >= 0) {
646 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
647 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
664 OUT UINT32
*ScratchSize
670 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
674 Source - The source buffer containing the compressed data.
675 SrcSize - The size of source buffer
676 DstSize - The size of destination buffer.
677 ScratchSize - The size of scratch buffer.
681 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
682 EFI_INVALID_PARAMETER - The source data is corrupted
688 *ScratchSize
= sizeof (SCRATCH_DATA
);
692 return EFI_INVALID_PARAMETER
;
695 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
703 IN OUT VOID
*Destination
,
705 IN OUT VOID
*Scratch
,
706 IN UINT32 ScratchSize
,
713 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
717 Source - The source buffer containing the compressed data.
718 SrcSize - The size of source buffer
719 Destination - The destination buffer to store the decompressed data
720 DstSize - The size of destination buffer.
721 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
722 ScratchSize - The size of scratch buffer.
723 Version - The version of de/compression algorithm.
724 Version 1 for EFI 1.1 de/compression algorithm.
725 Version 2 for Tiano de/compression algorithm.
729 EFI_SUCCESS - Decompression is successfull
730 EFI_INVALID_PARAMETER - The source data is corrupted
742 Status
= EFI_SUCCESS
;
746 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
747 return EFI_INVALID_PARAMETER
;
750 Sd
= (SCRATCH_DATA
*) Scratch
;
753 return EFI_INVALID_PARAMETER
;
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
766 if (SrcSize
< CompSize
+ 8) {
767 return EFI_INVALID_PARAMETER
;
770 if (DstSize
!= OrigSize
) {
771 return EFI_INVALID_PARAMETER
;
776 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
777 ((UINT8
*) Sd
)[Index
] = 0;
780 // The length of the field 'Position Set Code Length Array Size' in Block Header.
781 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
782 // For Tiano de/compression algorithm(Version 2), mPBit = 5
795 // Currently, only have 2 versions
797 return EFI_INVALID_PARAMETER
;
802 Sd
->mCompSize
= CompSize
;
803 Sd
->mOrigSize
= OrigSize
;
806 // Fill the first BITBUFSIZ bits
808 FillBuf (Sd
, BITBUFSIZ
);
815 if (Sd
->mBadTableFlag
!= 0) {
817 // Something wrong with the source
819 Status
= EFI_INVALID_PARAMETER
;
831 OUT UINT32
*ScratchSize
837 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.GetInfo().
841 This - The protocol instance pointer
842 Source - The source buffer containing the compressed data.
843 SrcSize - The size of source buffer
844 DstSize - The size of destination buffer.
845 ScratchSize - The size of scratch buffer.
849 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
850 EFI_INVALID_PARAMETER - The source data is corrupted
867 IN OUT VOID
*Destination
,
869 IN OUT VOID
*Scratch
,
870 IN UINT32 ScratchSize
876 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.Decompress().
880 This - The protocol instance pointer
881 Source - The source buffer containing the compressed data.
882 SrcSize - The size of source buffer
883 Destination - The destination buffer to store the decompressed data
884 DstSize - The size of destination buffer.
885 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
886 ScratchSize - The size of scratch buffer.
890 EFI_SUCCESS - Decompression is successfull
891 EFI_INVALID_PARAMETER - The source data is corrupted
896 // For EFI 1.1 de/compression algorithm, the version is 1.
915 OUT UINT32
*ScratchSize
921 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
925 This - The protocol instance pointer
926 Source - The source buffer containing the compressed data.
927 SrcSize - The size of source buffer
928 DstSize - The size of destination buffer.
929 ScratchSize - The size of scratch buffer.
933 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
934 EFI_INVALID_PARAMETER - The source data is corrupted
951 IN OUT VOID
*Destination
,
953 IN OUT VOID
*Scratch
,
954 IN UINT32 ScratchSize
960 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
964 This - The protocol instance pointer
965 Source - The source buffer containing the compressed data.
966 SrcSize - The size of source buffer
967 Destination - The destination buffer to store the decompressed data
968 DstSize - The size of destination buffer.
969 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
970 ScratchSize - The size of scratch buffer.
974 EFI_SUCCESS - Decompression is successfull
975 EFI_INVALID_PARAMETER - The source data is corrupted
980 // For Tiano de/compression algorithm, the version is 2.