]>
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
86 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
90 Sd - The global scratch data
91 NumOfBits - The number of bits to shift and read.
97 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
99 while (NumOfBits
> Sd
->mBitCount
) {
101 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
103 if (Sd
->mCompSize
> 0) {
105 // Get 1 byte into SubBitBuf
109 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
114 // No more bits from the source, just pad zero bit.
122 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
123 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
135 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
136 NumOfBits of bits from source. Returns NumOfBits of bits that are
141 Sd - The global scratch data.
142 NumOfBits - The number of bits to pop and read.
146 The bits that are popped out.
152 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
154 FillBuf (Sd
, NumOfBits
);
171 Creates Huffman Code mapping table according to code length array.
175 Sd - The global scratch data
176 NumOfChar - Number of symbols in the symbol set
177 BitLen - Code length array
178 TableBits - The width of the mapping table
184 BAD_TABLE - The table is corrupted.
201 SetMem (&Count
[1], sizeof(UINT16
) * 16, 0);
203 for (Index
= 0; Index
< NumOfChar
; Index
++) {
204 Count
[BitLen
[Index
]]++;
209 for (Index
= 1; Index
<= 16; Index
++) {
210 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
213 if (Start
[17] != 0) {
215 return (UINT16
) BAD_TABLE
;
218 JuBits
= (UINT16
) (16 - TableBits
);
220 for (Index
= 1; Index
<= TableBits
; Index
++) {
221 Start
[Index
] >>= JuBits
;
222 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
225 while (Index
<= 16) {
226 Weight
[Index
++] = (UINT16
) (1U << (16 - Index
));
229 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
232 Index3
= (UINT16
) (1U << TableBits
);
233 SetMem(&Table
[Index
], sizeof(UINT16
) * (Index3
- Index
+ 1), 0);
237 Mask
= (UINT16
) (1U << (15 - TableBits
));
239 for (Char
= 0; Char
< NumOfChar
; Char
++) {
246 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
248 if (Len
<= TableBits
) {
250 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
257 Pointer
= &Table
[Index3
>> JuBits
];
258 Index
= (UINT16
) (Len
- TableBits
);
262 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
267 Pointer
= &Sd
->mRight
[*Pointer
];
269 Pointer
= &Sd
->mLeft
[*Pointer
];
280 Start
[Len
] = NextCode
;
296 Decodes a position value.
300 Sd - the global scratch data
304 The position value decoded.
312 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
315 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
319 if (Sd
->mBitBuf
& Mask
) {
320 Val
= Sd
->mRight
[Val
];
322 Val
= Sd
->mLeft
[Val
];
326 } while (Val
>= MAXNP
);
329 // Advance what we have read
331 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
335 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
352 Reads code lengths for the Extra Set or the Position Set
356 Sd - The global scratch data
357 nn - Number of symbols
358 nbit - Number of bits needed to represent nn
359 Special - The special symbol that needs to be taken care of
364 BAD_TABLE - Table is corrupted.
373 Number
= (UINT16
) GetBits (Sd
, nbit
);
376 CharC
= (UINT16
) GetBits (Sd
, nbit
);
378 for (Index
= 0; Index
< 256; Index
++) {
379 Sd
->mPTTable
[Index
] = CharC
;
382 SetMem ((VOID
*) &Sd
->mPTLen
, nn
* sizeof(UINT8
), 0);
389 while (Index
< Number
) {
391 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
394 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
395 while (Mask
& Sd
->mBitBuf
) {
401 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
403 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
405 if (Index
== Special
) {
406 CharC
= (UINT16
) GetBits (Sd
, 2);
407 while ((INT16
) (--CharC
) >= 0) {
408 Sd
->mPTLen
[Index
++] = 0;
413 SetMem ((VOID
*) &Sd
->mPTLen
[Index
], (nn
- Index
) * sizeof(UINT8
), 0);
414 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
425 Reads code lengths for Char&Len Set.
429 Sd - the global scratch data
440 Number
= (UINT16
) GetBits (Sd
, CBIT
);
443 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
445 SetMem ((VOID
*)&Sd
->mCLen
, sizeof(UINT8
) * NC
, 0);
447 for (Index
= 0; Index
< 4096; Index
++) {
448 Sd
->mCTable
[Index
] = CharC
;
455 while (Index
< Number
) {
457 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
459 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
463 if (Mask
& Sd
->mBitBuf
) {
464 CharC
= Sd
->mRight
[CharC
];
466 CharC
= Sd
->mLeft
[CharC
];
471 } while (CharC
>= NT
);
474 // Advance what we have read
476 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
482 } else if (CharC
== 1) {
483 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
484 } else if (CharC
== 2) {
485 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
488 while ((INT16
) (--CharC
) >= 0) {
489 Sd
->mCLen
[Index
++] = 0;
494 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
499 SetMem ((VOID
*) &Sd
->mCLen
[Index
], sizeof(UINT8
) * (NC
- Index
), 0);
501 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
514 Decode a character/length value.
518 Sd - The global scratch data.
529 if (Sd
->mBlockSize
== 0) {
531 // Starting a new block
533 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
534 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
535 if (Sd
->mBadTableFlag
!= 0) {
541 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
542 if (Sd
->mBadTableFlag
!= 0) {
548 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
551 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
554 if (Sd
->mBitBuf
& Mask
) {
555 Index2
= Sd
->mRight
[Index2
];
557 Index2
= Sd
->mLeft
[Index2
];
561 } while (Index2
>= NC
);
564 // Advance what we have read
566 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
579 Decode the source data and put the resulting data into the destination buffer.
583 Sd - The global scratch data
593 BytesRemain
= (UINT16
) (-1);
598 CharC
= DecodeC (Sd
);
599 if (Sd
->mBadTableFlag
!= 0) {
605 // Process an Original character
607 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
610 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
617 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
621 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
624 while ((INT16
) (BytesRemain
) >= 0) {
625 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
626 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
642 OUT UINT32
*ScratchSize
648 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
652 Source - The source buffer containing the compressed data.
653 SrcSize - The size of source buffer
654 DstSize - The size of destination buffer.
655 ScratchSize - The size of scratch buffer.
659 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
660 EFI_INVALID_PARAMETER - The source data is corrupted
666 *ScratchSize
= sizeof (SCRATCH_DATA
);
670 return EFI_INVALID_PARAMETER
;
673 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
681 IN OUT VOID
*Destination
,
683 IN OUT VOID
*Scratch
,
684 IN UINT32 ScratchSize
,
691 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
695 Source - The source buffer containing the compressed data.
696 SrcSize - The size of source buffer
697 Destination - The destination buffer to store the decompressed data
698 DstSize - The size of destination buffer.
699 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
700 ScratchSize - The size of scratch buffer.
701 Version - The version of de/compression algorithm.
702 Version 1 for EFI 1.1 de/compression algorithm.
703 Version 2 for Tiano de/compression algorithm.
707 EFI_SUCCESS - Decompression is successfull
708 EFI_INVALID_PARAMETER - The source data is corrupted
719 Status
= EFI_SUCCESS
;
723 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
724 return EFI_INVALID_PARAMETER
;
727 Sd
= (SCRATCH_DATA
*) Scratch
;
730 return EFI_INVALID_PARAMETER
;
733 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
734 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
737 // If compressed file size is 0, return
743 if (SrcSize
< CompSize
+ 8) {
744 return EFI_INVALID_PARAMETER
;
747 if (DstSize
!= OrigSize
) {
748 return EFI_INVALID_PARAMETER
;
753 SetMem ((VOID
*) Sd
, sizeof(SCRATCH_DATA
), 0);
756 // The length of the field 'Position Set Code Length Array Size' in Block Header.
757 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
758 // For Tiano de/compression algorithm(Version 2), mPBit = 5
771 // Currently, only have 2 versions
773 return EFI_INVALID_PARAMETER
;
778 Sd
->mCompSize
= CompSize
;
779 Sd
->mOrigSize
= OrigSize
;
782 // Fill the first BITBUFSIZ bits
784 FillBuf (Sd
, BITBUFSIZ
);
791 if (Sd
->mBadTableFlag
!= 0) {
793 // Something wrong with the source
795 Status
= EFI_INVALID_PARAMETER
;
807 OUT UINT32
*ScratchSize
813 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.GetInfo().
817 This - The protocol instance pointer
818 Source - The source buffer containing the compressed data.
819 SrcSize - The size of source buffer
820 DstSize - The size of destination buffer.
821 ScratchSize - The size of scratch buffer.
825 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
826 EFI_INVALID_PARAMETER - The source data is corrupted
843 IN OUT VOID
*Destination
,
845 IN OUT VOID
*Scratch
,
846 IN UINT32 ScratchSize
852 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.Decompress().
856 This - The protocol instance pointer
857 Source - The source buffer containing the compressed data.
858 SrcSize - The size of source buffer
859 Destination - The destination buffer to store the decompressed data
860 DstSize - The size of destination buffer.
861 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
862 ScratchSize - The size of scratch buffer.
866 EFI_SUCCESS - Decompression is successfull
867 EFI_INVALID_PARAMETER - The source data is corrupted
872 // For EFI 1.1 de/compression algorithm, the version is 1.
891 OUT UINT32
*ScratchSize
897 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
901 This - The protocol instance pointer
902 Source - The source buffer containing the compressed data.
903 SrcSize - The size of source buffer
904 DstSize - The size of destination buffer.
905 ScratchSize - The size of scratch buffer.
909 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
910 EFI_INVALID_PARAMETER - The source data is corrupted
927 IN OUT VOID
*Destination
,
929 IN OUT VOID
*Scratch
,
930 IN UINT32 ScratchSize
936 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
940 This - The protocol instance pointer
941 Source - The source buffer containing the compressed data.
942 SrcSize - The size of source buffer
943 Destination - The destination buffer to store the decompressed data
944 DstSize - The size of destination buffer.
945 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
946 ScratchSize - The size of scratch buffer.
950 EFI_SUCCESS - Decompression is successfull
951 EFI_INVALID_PARAMETER - The source data is corrupted
956 // For Tiano de/compression algorithm, the version is 2.