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
));
344 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
347 Index3
= (UINT16
) (1U << TableBits
);
348 while (Index
!= Index3
) {
354 Mask
= (UINT16
) (1U << (15 - TableBits
));
356 for (Char
= 0; Char
< NumOfChar
; Char
++) {
363 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
365 if (Len
<= TableBits
) {
367 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
374 Pointer
= &Table
[Index3
>> JuBits
];
375 Index
= (UINT16
) (Len
- TableBits
);
379 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
384 Pointer
= &Sd
->mRight
[*Pointer
];
386 Pointer
= &Sd
->mLeft
[*Pointer
];
397 Start
[Len
] = NextCode
;
414 Decodes a position value.
418 Sd - the global scratch data
422 The position value decoded.
430 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
433 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
437 if (Sd
->mBitBuf
& Mask
) {
438 Val
= Sd
->mRight
[Val
];
440 Val
= Sd
->mLeft
[Val
];
444 } while (Val
>= MAXNP
);
447 // Advance what we have read
449 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
453 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
471 Reads code lengths for the Extra Set or the Position Set
475 Sd - The global scratch data
476 nn - Number of symbols
477 nbit - Number of bits needed to represent nn
478 Special - The special symbol that needs to be taken care of
483 BAD_TABLE - Table is corrupted.
492 Number
= (UINT16
) GetBits (Sd
, nbit
);
495 CharC
= (UINT16
) GetBits (Sd
, nbit
);
497 for (Index
= 0; Index
< 256; Index
++) {
498 Sd
->mPTTable
[Index
] = CharC
;
501 for (Index
= 0; Index
< nn
; Index
++) {
502 Sd
->mPTLen
[Index
] = 0;
510 while (Index
< Number
) {
512 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
515 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
516 while (Mask
& Sd
->mBitBuf
) {
522 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
524 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
526 if (Index
== Special
) {
527 CharC
= (UINT16
) GetBits (Sd
, 2);
528 while ((INT16
) (--CharC
) >= 0) {
529 Sd
->mPTLen
[Index
++] = 0;
535 Sd
->mPTLen
[Index
++] = 0;
538 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
550 Reads code lengths for Char&Len Set.
554 Sd - the global scratch data
565 Number
= (UINT16
) GetBits (Sd
, CBIT
);
568 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
570 for (Index
= 0; Index
< NC
; Index
++) {
571 Sd
->mCLen
[Index
] = 0;
574 for (Index
= 0; Index
< 4096; Index
++) {
575 Sd
->mCTable
[Index
] = CharC
;
582 while (Index
< Number
) {
584 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
586 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
590 if (Mask
& Sd
->mBitBuf
) {
591 CharC
= Sd
->mRight
[CharC
];
593 CharC
= Sd
->mLeft
[CharC
];
598 } while (CharC
>= NT
);
601 // Advance what we have read
603 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
609 } else if (CharC
== 1) {
610 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
611 } else if (CharC
== 2) {
612 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
615 while ((INT16
) (--CharC
) >= 0) {
616 Sd
->mCLen
[Index
++] = 0;
621 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
627 Sd
->mCLen
[Index
++] = 0;
630 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
644 Decode a character/length value.
648 Sd - The global scratch data.
659 if (Sd
->mBlockSize
== 0) {
661 // Starting a new block
663 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
664 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
665 if (Sd
->mBadTableFlag
!= 0) {
671 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
672 if (Sd
->mBadTableFlag
!= 0) {
678 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
681 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
684 if (Sd
->mBitBuf
& Mask
) {
685 Index2
= Sd
->mRight
[Index2
];
687 Index2
= Sd
->mLeft
[Index2
];
691 } while (Index2
>= NC
);
694 // Advance what we have read
696 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
710 Decode the source data and put the resulting data into the destination buffer.
714 Sd - The global scratch data
724 BytesRemain
= (UINT16
) (-1);
729 CharC
= DecodeC (Sd
);
730 if (Sd
->mBadTableFlag
!= 0) {
736 // Process an Original character
738 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
741 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
748 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
752 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
755 while ((INT16
) (BytesRemain
) >= 0) {
756 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
757 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.