3 Copyright (c) 2004, 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)
22 #include "TianoCommon.h"
23 #include EFI_PROTOCOL_DEFINITION (Decompress)
24 #include EFI_PROTOCOL_DEFINITION (TianoDecompress)
29 IN EFI_DECOMPRESS_PROTOCOL
*This
,
33 OUT UINT32
*ScratchSize
39 IN EFI_DECOMPRESS_PROTOCOL
*This
,
42 IN OUT VOID
*Destination
,
51 IN EFI_TIANO_DECOMPRESS_PROTOCOL
*This
,
55 OUT UINT32
*ScratchSize
61 IN EFI_TIANO_DECOMPRESS_PROTOCOL
*This
,
64 IN OUT VOID
*Destination
,
71 // The protocol instance
74 EFI_DECOMPRESS_PROTOCOL mEfiDecompress
= {
79 EFI_TIANO_DECOMPRESS_PROTOCOL mTianoDecompress
= {
85 InstallEfiDecompress (
86 IN OUT EFI_DECOMPRESS_PROTOCOL
**This
92 Install EFI decompress protocol.
96 This - Pointer to get decompress protocol as output
100 EFI_SUCCESS - EFI decompress protocol successfully installed.
104 *This
= &mEfiDecompress
;
109 InstallTianoDecompress (
110 EFI_TIANO_DECOMPRESS_PROTOCOL
**This
116 Install Tiano decompress protocol.
120 This - Pointer to get decompress protocol as output
124 EFI_SUCCESS - Tiano decompress protocol successfully installed.
128 *This
= &mTianoDecompress
;
132 // Decompression algorithm begins here
139 #define UINT8_MAX 0xff
141 #define BAD_TABLE - 1
144 // C: Char&Len Set; P: Position Set; T: exTra Set
146 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
150 #define MAXNP ((1U << MAXPBIT) - 1)
151 #define NT (CODE_BIT + 3)
159 UINT8
*mSrcBase
; // Starting address of compressed data
160 UINT8
*mDstBase
; // Starting address of decompressed data
171 UINT16 mBadTableFlag
;
173 UINT16 mLeft
[2 * NC
- 1];
174 UINT16 mRight
[2 * NC
- 1];
177 UINT16 mCTable
[4096];
178 UINT16 mPTTable
[256];
181 // The length of the field 'Position Set Code Length Array Size' in Block Header.
182 // For EFI 1.1 de/compression algorithm, mPBit = 4
183 // For Tiano de/compression algorithm, mPBit = 5
198 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
202 Sd - The global scratch data
203 NumOfBits - The number of bits to shift and read.
209 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
211 while (NumOfBits
> Sd
->mBitCount
) {
213 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
215 if (Sd
->mCompSize
> 0) {
217 // Get 1 byte into SubBitBuf
221 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
226 // No more bits from the source, just pad zero bit.
234 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
235 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
248 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
249 NumOfBits of bits from source. Returns NumOfBits of bits that are
254 Sd - The global scratch data.
255 NumOfBits - The number of bits to pop and read.
259 The bits that are popped out.
265 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
267 FillBuf (Sd
, NumOfBits
);
285 Creates Huffman Code mapping table according to code length array.
289 Sd - The global scratch data
290 NumOfChar - Number of symbols in the symbol set
291 BitLen - Code length array
292 TableBits - The width of the mapping table
298 BAD_TABLE - The table is corrupted.
315 for (Index
= 1; Index
<= 16; Index
++) {
319 for (Index
= 0; Index
< NumOfChar
; Index
++) {
320 Count
[BitLen
[Index
]]++;
325 for (Index
= 1; Index
<= 16; Index
++) {
326 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
329 if (Start
[17] != 0) {
331 return (UINT16
) BAD_TABLE
;
334 JuBits
= (UINT16
) (16 - TableBits
);
336 for (Index
= 1; Index
<= TableBits
; Index
++) {
337 Start
[Index
] >>= JuBits
;
338 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
341 while (Index
<= 16) {
342 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
346 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
349 Index3
= (UINT16
) (1U << TableBits
);
350 while (Index
!= Index3
) {
356 Mask
= (UINT16
) (1U << (15 - TableBits
));
358 for (Char
= 0; Char
< NumOfChar
; Char
++) {
365 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
367 if (Len
<= TableBits
) {
369 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
376 Pointer
= &Table
[Index3
>> JuBits
];
377 Index
= (UINT16
) (Len
- TableBits
);
381 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
386 Pointer
= &Sd
->mRight
[*Pointer
];
388 Pointer
= &Sd
->mLeft
[*Pointer
];
399 Start
[Len
] = NextCode
;
416 Decodes a position value.
420 Sd - the global scratch data
424 The position value decoded.
432 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
435 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
439 if (Sd
->mBitBuf
& Mask
) {
440 Val
= Sd
->mRight
[Val
];
442 Val
= Sd
->mLeft
[Val
];
446 } while (Val
>= MAXNP
);
449 // Advance what we have read
451 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
455 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
473 Reads code lengths for the Extra Set or the Position Set
477 Sd - The global scratch data
478 nn - Number of symbols
479 nbit - Number of bits needed to represent nn
480 Special - The special symbol that needs to be taken care of
485 BAD_TABLE - Table is corrupted.
494 Number
= (UINT16
) GetBits (Sd
, nbit
);
497 CharC
= (UINT16
) GetBits (Sd
, nbit
);
499 for (Index
= 0; Index
< 256; Index
++) {
500 Sd
->mPTTable
[Index
] = CharC
;
503 for (Index
= 0; Index
< nn
; Index
++) {
504 Sd
->mPTLen
[Index
] = 0;
512 while (Index
< Number
) {
514 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
517 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
518 while (Mask
& Sd
->mBitBuf
) {
524 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
526 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
528 if (Index
== Special
) {
529 CharC
= (UINT16
) GetBits (Sd
, 2);
530 while ((INT16
) (--CharC
) >= 0) {
531 Sd
->mPTLen
[Index
++] = 0;
537 Sd
->mPTLen
[Index
++] = 0;
540 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
552 Reads code lengths for Char&Len Set.
556 Sd - the global scratch data
567 Number
= (UINT16
) GetBits (Sd
, CBIT
);
570 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
572 for (Index
= 0; Index
< NC
; Index
++) {
573 Sd
->mCLen
[Index
] = 0;
576 for (Index
= 0; Index
< 4096; Index
++) {
577 Sd
->mCTable
[Index
] = CharC
;
584 while (Index
< Number
) {
586 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
588 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
592 if (Mask
& Sd
->mBitBuf
) {
593 CharC
= Sd
->mRight
[CharC
];
595 CharC
= Sd
->mLeft
[CharC
];
600 } while (CharC
>= NT
);
603 // Advance what we have read
605 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
611 } else if (CharC
== 1) {
612 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
613 } else if (CharC
== 2) {
614 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
617 while ((INT16
) (--CharC
) >= 0) {
618 Sd
->mCLen
[Index
++] = 0;
623 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
629 Sd
->mCLen
[Index
++] = 0;
632 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
646 Decode a character/length value.
650 Sd - The global scratch data.
661 if (Sd
->mBlockSize
== 0) {
663 // Starting a new block
665 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
666 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
667 if (Sd
->mBadTableFlag
!= 0) {
673 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
674 if (Sd
->mBadTableFlag
!= 0) {
680 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
683 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
686 if (Sd
->mBitBuf
& Mask
) {
687 Index2
= Sd
->mRight
[Index2
];
689 Index2
= Sd
->mLeft
[Index2
];
693 } while (Index2
>= NC
);
696 // Advance what we have read
698 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
712 Decode the source data and put the resulting data into the destination buffer.
716 Sd - The global scratch data
726 BytesRemain
= (UINT16
) (-1);
731 CharC
= DecodeC (Sd
);
732 if (Sd
->mBadTableFlag
!= 0) {
738 // Process an Original character
740 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
743 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
750 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
754 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
757 while ((INT16
) (BytesRemain
) >= 0) {
758 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
759 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
774 OUT UINT32
*ScratchSize
780 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
784 Source - The source buffer containing the compressed data.
785 SrcSize - The size of source buffer
786 DstSize - The size of destination buffer.
787 ScratchSize - The size of scratch buffer.
791 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
792 EFI_INVALID_PARAMETER - The source data is corrupted
798 *ScratchSize
= sizeof (SCRATCH_DATA
);
802 return EFI_INVALID_PARAMETER
;
805 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
813 IN OUT VOID
*Destination
,
815 IN OUT VOID
*Scratch
,
816 IN UINT32 ScratchSize
,
823 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
827 Source - The source buffer containing the compressed data.
828 SrcSize - The size of source buffer
829 Destination - The destination buffer to store the decompressed data
830 DstSize - The size of destination buffer.
831 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
832 ScratchSize - The size of scratch buffer.
833 Version - The version of de/compression algorithm.
834 Version 1 for EFI 1.1 de/compression algorithm.
835 Version 2 for Tiano de/compression algorithm.
839 EFI_SUCCESS - Decompression is successfull
840 EFI_INVALID_PARAMETER - The source data is corrupted
852 Status
= EFI_SUCCESS
;
856 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
857 return EFI_INVALID_PARAMETER
;
860 Sd
= (SCRATCH_DATA
*) Scratch
;
863 return EFI_INVALID_PARAMETER
;
866 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
867 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
870 // If compressed file size is 0, return
876 if (SrcSize
< CompSize
+ 8) {
877 return EFI_INVALID_PARAMETER
;
880 if (DstSize
!= OrigSize
) {
881 return EFI_INVALID_PARAMETER
;
886 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
887 ((UINT8
*) Sd
)[Index
] = 0;
890 // The length of the field 'Position Set Code Length Array Size' in Block Header.
891 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
892 // For Tiano de/compression algorithm(Version 2), mPBit = 5
905 // Currently, only have 2 versions
907 return EFI_INVALID_PARAMETER
;
912 Sd
->mCompSize
= CompSize
;
913 Sd
->mOrigSize
= OrigSize
;
916 // Fill the first BITBUFSIZ bits
918 FillBuf (Sd
, BITBUFSIZ
);
925 if (Sd
->mBadTableFlag
!= 0) {
927 // Something wrong with the source
929 Status
= EFI_INVALID_PARAMETER
;
938 IN EFI_DECOMPRESS_PROTOCOL
*This
,
942 OUT UINT32
*ScratchSize
948 The implementation of EFI_DECOMPRESS_PROTOCOL.GetInfo().
952 This - The protocol instance pointer
953 Source - The source buffer containing the compressed data.
954 SrcSize - The size of source buffer
955 DstSize - The size of destination buffer.
956 ScratchSize - The size of scratch buffer.
960 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
961 EFI_INVALID_PARAMETER - The source data is corrupted
976 IN EFI_DECOMPRESS_PROTOCOL
*This
,
979 IN OUT VOID
*Destination
,
981 IN OUT VOID
*Scratch
,
982 IN UINT32 ScratchSize
988 The implementation of EFI_DECOMPRESS_PROTOCOL.Decompress().
992 This - The protocol instance pointer
993 Source - The source buffer containing the compressed data.
994 SrcSize - The size of source buffer
995 Destination - The destination buffer to store the decompressed data
996 DstSize - The size of destination buffer.
997 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
998 ScratchSize - The size of scratch buffer.
1002 EFI_SUCCESS - Decompression is successfull
1003 EFI_INVALID_PARAMETER - The source data is corrupted
1008 // For EFI 1.1 de/compression algorithm, the version is 1.
1024 IN EFI_TIANO_DECOMPRESS_PROTOCOL
*This
,
1027 OUT UINT32
*DstSize
,
1028 OUT UINT32
*ScratchSize
1032 Routine Description:
1034 The implementation of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
1038 This - The protocol instance pointer
1039 Source - The source buffer containing the compressed data.
1040 SrcSize - The size of source buffer
1041 DstSize - The size of destination buffer.
1042 ScratchSize - The size of scratch buffer.
1046 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
1047 EFI_INVALID_PARAMETER - The source data is corrupted
1062 IN EFI_TIANO_DECOMPRESS_PROTOCOL
*This
,
1065 IN OUT VOID
*Destination
,
1067 IN OUT VOID
*Scratch
,
1068 IN UINT32 ScratchSize
1072 Routine Description:
1074 The implementation of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
1078 This - The protocol instance pointer
1079 Source - The source buffer containing the compressed data.
1080 SrcSize - The size of source buffer
1081 Destination - The destination buffer to store the decompressed data
1082 DstSize - The size of destination buffer.
1083 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
1084 ScratchSize - The size of scratch buffer.
1088 EFI_SUCCESS - Decompression is successfull
1089 EFI_INVALID_PARAMETER - The source data is corrupted
1094 // For Tiano de/compression algorithm, the version is 2.