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
138 #define UINT8_MAX 0xff
139 #define BAD_TABLE - 1
142 // C: Char&Len Set; P: Position Set; T: exTra Set
144 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
148 #define MAXNP ((1U << MAXPBIT) - 1)
149 #define NT (CODE_BIT + 3)
157 UINT8
*mSrcBase
; // Starting address of compressed data
158 UINT8
*mDstBase
; // Starting address of decompressed data
169 UINT16 mBadTableFlag
;
171 UINT16 mLeft
[2 * NC
- 1];
172 UINT16 mRight
[2 * NC
- 1];
175 UINT16 mCTable
[4096];
176 UINT16 mPTTable
[256];
179 // The length of the field 'Position Set Code Length Array Size' in Block Header.
180 // For EFI 1.1 de/compression algorithm, mPBit = 4
181 // For Tiano de/compression algorithm, mPBit = 5
196 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
200 Sd - The global scratch data
201 NumOfBits - The number of bits to shift and read.
207 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
209 while (NumOfBits
> Sd
->mBitCount
) {
211 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
213 if (Sd
->mCompSize
> 0) {
215 // Get 1 byte into SubBitBuf
219 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
224 // No more bits from the source, just pad zero bit.
232 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
233 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
246 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
247 NumOfBits of bits from source. Returns NumOfBits of bits that are
252 Sd - The global scratch data.
253 NumOfBits - The number of bits to pop and read.
257 The bits that are popped out.
263 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
265 FillBuf (Sd
, NumOfBits
);
283 Creates Huffman Code mapping table according to code length array.
287 Sd - The global scratch data
288 NumOfChar - Number of symbols in the symbol set
289 BitLen - Code length array
290 TableBits - The width of the mapping table
296 BAD_TABLE - The table is corrupted.
313 for (Index
= 1; Index
<= 16; Index
++) {
317 for (Index
= 0; Index
< NumOfChar
; Index
++) {
318 Count
[BitLen
[Index
]]++;
323 for (Index
= 1; Index
<= 16; Index
++) {
324 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
327 if (Start
[17] != 0) {
329 return (UINT16
) BAD_TABLE
;
332 JuBits
= (UINT16
) (16 - TableBits
);
334 for (Index
= 1; Index
<= TableBits
; Index
++) {
335 Start
[Index
] >>= JuBits
;
336 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
339 while (Index
<= 16) {
340 Weight
[Index
++] = (UINT16
) (1U << (16 - Index
));
343 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
346 Index3
= (UINT16
) (1U << TableBits
);
347 while (Index
!= Index3
) {
353 Mask
= (UINT16
) (1U << (15 - TableBits
));
355 for (Char
= 0; Char
< NumOfChar
; Char
++) {
362 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
364 if (Len
<= TableBits
) {
366 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
373 Pointer
= &Table
[Index3
>> JuBits
];
374 Index
= (UINT16
) (Len
- TableBits
);
378 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
383 Pointer
= &Sd
->mRight
[*Pointer
];
385 Pointer
= &Sd
->mLeft
[*Pointer
];
396 Start
[Len
] = NextCode
;
413 Decodes a position value.
417 Sd - the global scratch data
421 The position value decoded.
429 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
432 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
436 if (Sd
->mBitBuf
& Mask
) {
437 Val
= Sd
->mRight
[Val
];
439 Val
= Sd
->mLeft
[Val
];
443 } while (Val
>= MAXNP
);
446 // Advance what we have read
448 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
452 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
470 Reads code lengths for the Extra Set or the Position Set
474 Sd - The global scratch data
475 nn - Number of symbols
476 nbit - Number of bits needed to represent nn
477 Special - The special symbol that needs to be taken care of
482 BAD_TABLE - Table is corrupted.
491 Number
= (UINT16
) GetBits (Sd
, nbit
);
494 CharC
= (UINT16
) GetBits (Sd
, nbit
);
496 for (Index
= 0; Index
< 256; Index
++) {
497 Sd
->mPTTable
[Index
] = CharC
;
500 for (Index
= 0; Index
< nn
; Index
++) {
501 Sd
->mPTLen
[Index
] = 0;
509 while (Index
< Number
) {
511 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
514 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
515 while (Mask
& Sd
->mBitBuf
) {
521 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
523 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
525 if (Index
== Special
) {
526 CharC
= (UINT16
) GetBits (Sd
, 2);
527 while ((INT16
) (--CharC
) >= 0) {
528 Sd
->mPTLen
[Index
++] = 0;
534 Sd
->mPTLen
[Index
++] = 0;
537 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
549 Reads code lengths for Char&Len Set.
553 Sd - the global scratch data
564 Number
= (UINT16
) GetBits (Sd
, CBIT
);
567 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
569 for (Index
= 0; Index
< NC
; Index
++) {
570 Sd
->mCLen
[Index
] = 0;
573 for (Index
= 0; Index
< 4096; Index
++) {
574 Sd
->mCTable
[Index
] = CharC
;
581 while (Index
< Number
) {
583 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
585 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
589 if (Mask
& Sd
->mBitBuf
) {
590 CharC
= Sd
->mRight
[CharC
];
592 CharC
= Sd
->mLeft
[CharC
];
597 } while (CharC
>= NT
);
600 // Advance what we have read
602 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
608 } else if (CharC
== 1) {
609 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
610 } else if (CharC
== 2) {
611 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
614 while ((INT16
) (--CharC
) >= 0) {
615 Sd
->mCLen
[Index
++] = 0;
620 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
626 Sd
->mCLen
[Index
++] = 0;
629 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
643 Decode a character/length value.
647 Sd - The global scratch data.
658 if (Sd
->mBlockSize
== 0) {
660 // Starting a new block
662 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
663 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
664 if (Sd
->mBadTableFlag
!= 0) {
670 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
671 if (Sd
->mBadTableFlag
!= 0) {
677 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
680 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
683 if (Sd
->mBitBuf
& Mask
) {
684 Index2
= Sd
->mRight
[Index2
];
686 Index2
= Sd
->mLeft
[Index2
];
690 } while (Index2
>= NC
);
693 // Advance what we have read
695 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
709 Decode the source data and put the resulting data into the destination buffer.
713 Sd - The global scratch data
723 BytesRemain
= (UINT16
) (-1);
728 CharC
= DecodeC (Sd
);
729 if (Sd
->mBadTableFlag
!= 0) {
735 // Process an Original character
737 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
740 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
747 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
751 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
754 while ((INT16
) (BytesRemain
) >= 0) {
755 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
756 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
773 OUT UINT32
*ScratchSize
779 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
783 Source - The source buffer containing the compressed data.
784 SrcSize - The size of source buffer
785 DstSize - The size of destination buffer.
786 ScratchSize - The size of scratch buffer.
790 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
791 EFI_INVALID_PARAMETER - The source data is corrupted
797 *ScratchSize
= sizeof (SCRATCH_DATA
);
801 return EFI_INVALID_PARAMETER
;
804 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
812 IN OUT VOID
*Destination
,
814 IN OUT VOID
*Scratch
,
815 IN UINT32 ScratchSize
,
822 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
826 Source - The source buffer containing the compressed data.
827 SrcSize - The size of source buffer
828 Destination - The destination buffer to store the decompressed data
829 DstSize - The size of destination buffer.
830 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
831 ScratchSize - The size of scratch buffer.
832 Version - The version of de/compression algorithm.
833 Version 1 for EFI 1.1 de/compression algorithm.
834 Version 2 for Tiano de/compression algorithm.
838 EFI_SUCCESS - Decompression is successfull
839 EFI_INVALID_PARAMETER - The source data is corrupted
851 Status
= EFI_SUCCESS
;
855 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
856 return EFI_INVALID_PARAMETER
;
859 Sd
= (SCRATCH_DATA
*) Scratch
;
862 return EFI_INVALID_PARAMETER
;
865 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
866 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
869 // If compressed file size is 0, return
875 if (SrcSize
< CompSize
+ 8) {
876 return EFI_INVALID_PARAMETER
;
879 if (DstSize
!= OrigSize
) {
880 return EFI_INVALID_PARAMETER
;
885 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
886 ((UINT8
*) Sd
)[Index
] = 0;
889 // The length of the field 'Position Set Code Length Array Size' in Block Header.
890 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
891 // For Tiano de/compression algorithm(Version 2), mPBit = 5
904 // Currently, only have 2 versions
906 return EFI_INVALID_PARAMETER
;
911 Sd
->mCompSize
= CompSize
;
912 Sd
->mOrigSize
= OrigSize
;
915 // Fill the first BITBUFSIZ bits
917 FillBuf (Sd
, BITBUFSIZ
);
924 if (Sd
->mBadTableFlag
!= 0) {
926 // Something wrong with the source
928 Status
= EFI_INVALID_PARAMETER
;
937 IN EFI_DECOMPRESS_PROTOCOL
*This
,
941 OUT UINT32
*ScratchSize
947 The implementation of EFI_DECOMPRESS_PROTOCOL.GetInfo().
951 This - The protocol instance pointer
952 Source - The source buffer containing the compressed data.
953 SrcSize - The size of source buffer
954 DstSize - The size of destination buffer.
955 ScratchSize - The size of scratch buffer.
959 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
960 EFI_INVALID_PARAMETER - The source data is corrupted
975 IN EFI_DECOMPRESS_PROTOCOL
*This
,
978 IN OUT VOID
*Destination
,
980 IN OUT VOID
*Scratch
,
981 IN UINT32 ScratchSize
987 The implementation of EFI_DECOMPRESS_PROTOCOL.Decompress().
991 This - The protocol instance pointer
992 Source - The source buffer containing the compressed data.
993 SrcSize - The size of source buffer
994 Destination - The destination buffer to store the decompressed data
995 DstSize - The size of destination buffer.
996 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
997 ScratchSize - The size of scratch buffer.
1001 EFI_SUCCESS - Decompression is successfull
1002 EFI_INVALID_PARAMETER - The source data is corrupted
1007 // For EFI 1.1 de/compression algorithm, the version is 1.
1023 IN EFI_TIANO_DECOMPRESS_PROTOCOL
*This
,
1026 OUT UINT32
*DstSize
,
1027 OUT UINT32
*ScratchSize
1031 Routine Description:
1033 The implementation of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
1037 This - The protocol instance pointer
1038 Source - The source buffer containing the compressed data.
1039 SrcSize - The size of source buffer
1040 DstSize - The size of destination buffer.
1041 ScratchSize - The size of scratch buffer.
1045 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
1046 EFI_INVALID_PARAMETER - The source data is corrupted
1061 IN EFI_TIANO_DECOMPRESS_PROTOCOL
*This
,
1064 IN OUT VOID
*Destination
,
1066 IN OUT VOID
*Scratch
,
1067 IN UINT32 ScratchSize
1071 Routine Description:
1073 The implementation of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
1077 This - The protocol instance pointer
1078 Source - The source buffer containing the compressed data.
1079 SrcSize - The size of source buffer
1080 Destination - The destination buffer to store the decompressed data
1081 DstSize - The size of destination buffer.
1082 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
1083 ScratchSize - The size of scratch buffer.
1087 EFI_SUCCESS - Decompression is successfull
1088 EFI_INVALID_PARAMETER - The source data is corrupted
1093 // For Tiano de/compression algorithm, the version is 2.