]>
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 SetMem (&Count
[1], sizeof(UINT16
) * 16, 0);
206 for (Index
= 0; Index
< NumOfChar
; Index
++) {
207 Count
[BitLen
[Index
]]++;
212 for (Index
= 1; Index
<= 16; Index
++) {
213 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
216 if (Start
[17] != 0) {
218 return (UINT16
) BAD_TABLE
;
221 JuBits
= (UINT16
) (16 - TableBits
);
223 for (Index
= 1; Index
<= TableBits
; Index
++) {
224 Start
[Index
] >>= JuBits
;
225 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
228 while (Index
<= 16) {
229 Weight
[Index
++] = (UINT16
) (1U << (16 - Index
));
232 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
235 Index3
= (UINT16
) (1U << TableBits
);
236 SetMem(&Table
[Index
], sizeof(UINT16
) * (Index3
- Index
+ 1), 0);
240 Mask
= (UINT16
) (1U << (15 - TableBits
));
242 for (Char
= 0; Char
< NumOfChar
; Char
++) {
249 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
251 if (Len
<= TableBits
) {
253 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
260 Pointer
= &Table
[Index3
>> JuBits
];
261 Index
= (UINT16
) (Len
- TableBits
);
265 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
270 Pointer
= &Sd
->mRight
[*Pointer
];
272 Pointer
= &Sd
->mLeft
[*Pointer
];
283 Start
[Len
] = NextCode
;
300 Decodes a position value.
304 Sd - the global scratch data
308 The position value decoded.
316 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
319 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
323 if (Sd
->mBitBuf
& Mask
) {
324 Val
= Sd
->mRight
[Val
];
326 Val
= Sd
->mLeft
[Val
];
330 } while (Val
>= MAXNP
);
333 // Advance what we have read
335 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
339 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
357 Reads code lengths for the Extra Set or the Position Set
361 Sd - The global scratch data
362 nn - Number of symbols
363 nbit - Number of bits needed to represent nn
364 Special - The special symbol that needs to be taken care of
369 BAD_TABLE - Table is corrupted.
378 Number
= (UINT16
) GetBits (Sd
, nbit
);
381 CharC
= (UINT16
) GetBits (Sd
, nbit
);
383 for (Index
= 0; Index
< 256; Index
++) {
384 Sd
->mPTTable
[Index
] = CharC
;
387 SetMem ((VOID
*) &Sd
->mPTLen
, nn
* sizeof(UINT8
), 0);
394 while (Index
< Number
) {
396 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
399 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
400 while (Mask
& Sd
->mBitBuf
) {
406 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
408 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
410 if (Index
== Special
) {
411 CharC
= (UINT16
) GetBits (Sd
, 2);
412 while ((INT16
) (--CharC
) >= 0) {
413 Sd
->mPTLen
[Index
++] = 0;
418 SetMem ((VOID
*) &Sd
->mPTLen
[Index
], (nn
- Index
) * sizeof(UINT8
), 0);
419 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
431 Reads code lengths for Char&Len Set.
435 Sd - the global scratch data
446 Number
= (UINT16
) GetBits (Sd
, CBIT
);
449 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
451 SetMem ((VOID
*)&Sd
->mCLen
, sizeof(UINT8
) * NC
, 0);
453 for (Index
= 0; Index
< 4096; Index
++) {
454 Sd
->mCTable
[Index
] = CharC
;
461 while (Index
< Number
) {
463 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
465 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
469 if (Mask
& Sd
->mBitBuf
) {
470 CharC
= Sd
->mRight
[CharC
];
472 CharC
= Sd
->mLeft
[CharC
];
477 } while (CharC
>= NT
);
480 // Advance what we have read
482 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
488 } else if (CharC
== 1) {
489 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
490 } else if (CharC
== 2) {
491 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
494 while ((INT16
) (--CharC
) >= 0) {
495 Sd
->mCLen
[Index
++] = 0;
500 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
505 SetMem ((VOID
*) &Sd
->mCLen
[Index
], sizeof(UINT8
) * (NC
- Index
), 0);
507 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
521 Decode a character/length value.
525 Sd - The global scratch data.
536 if (Sd
->mBlockSize
== 0) {
538 // Starting a new block
540 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
541 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
542 if (Sd
->mBadTableFlag
!= 0) {
548 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
549 if (Sd
->mBadTableFlag
!= 0) {
555 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
558 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
561 if (Sd
->mBitBuf
& Mask
) {
562 Index2
= Sd
->mRight
[Index2
];
564 Index2
= Sd
->mLeft
[Index2
];
568 } while (Index2
>= NC
);
571 // Advance what we have read
573 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
587 Decode the source data and put the resulting data into the destination buffer.
591 Sd - The global scratch data
601 BytesRemain
= (UINT16
) (-1);
606 CharC
= DecodeC (Sd
);
607 if (Sd
->mBadTableFlag
!= 0) {
613 // Process an Original character
615 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
618 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
625 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
629 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
632 while ((INT16
) (BytesRemain
) >= 0) {
633 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
634 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
651 OUT UINT32
*ScratchSize
657 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
661 Source - The source buffer containing the compressed data.
662 SrcSize - The size of source buffer
663 DstSize - The size of destination buffer.
664 ScratchSize - The size of scratch buffer.
668 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
669 EFI_INVALID_PARAMETER - The source data is corrupted
675 *ScratchSize
= sizeof (SCRATCH_DATA
);
679 return EFI_INVALID_PARAMETER
;
682 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
690 IN OUT VOID
*Destination
,
692 IN OUT VOID
*Scratch
,
693 IN UINT32 ScratchSize
,
700 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
704 Source - The source buffer containing the compressed data.
705 SrcSize - The size of source buffer
706 Destination - The destination buffer to store the decompressed data
707 DstSize - The size of destination buffer.
708 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
709 ScratchSize - The size of scratch buffer.
710 Version - The version of de/compression algorithm.
711 Version 1 for EFI 1.1 de/compression algorithm.
712 Version 2 for Tiano de/compression algorithm.
716 EFI_SUCCESS - Decompression is successfull
717 EFI_INVALID_PARAMETER - The source data is corrupted
728 Status
= EFI_SUCCESS
;
732 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
733 return EFI_INVALID_PARAMETER
;
736 Sd
= (SCRATCH_DATA
*) Scratch
;
739 return EFI_INVALID_PARAMETER
;
742 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
743 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
746 // If compressed file size is 0, return
752 if (SrcSize
< CompSize
+ 8) {
753 return EFI_INVALID_PARAMETER
;
756 if (DstSize
!= OrigSize
) {
757 return EFI_INVALID_PARAMETER
;
762 SetMem ((VOID
*) Sd
, sizeof(SCRATCH_DATA
), 0);
765 // The length of the field 'Position Set Code Length Array Size' in Block Header.
766 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
767 // For Tiano de/compression algorithm(Version 2), mPBit = 5
780 // Currently, only have 2 versions
782 return EFI_INVALID_PARAMETER
;
787 Sd
->mCompSize
= CompSize
;
788 Sd
->mOrigSize
= OrigSize
;
791 // Fill the first BITBUFSIZ bits
793 FillBuf (Sd
, BITBUFSIZ
);
800 if (Sd
->mBadTableFlag
!= 0) {
802 // Something wrong with the source
804 Status
= EFI_INVALID_PARAMETER
;
816 OUT UINT32
*ScratchSize
822 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.GetInfo().
826 This - The protocol instance pointer
827 Source - The source buffer containing the compressed data.
828 SrcSize - The size of source buffer
829 DstSize - The size of destination buffer.
830 ScratchSize - The size of scratch buffer.
834 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
835 EFI_INVALID_PARAMETER - The source data is corrupted
852 IN OUT VOID
*Destination
,
854 IN OUT VOID
*Scratch
,
855 IN UINT32 ScratchSize
861 The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.Decompress().
865 This - The protocol instance pointer
866 Source - The source buffer containing the compressed data.
867 SrcSize - The size of source buffer
868 Destination - The destination buffer to store the decompressed data
869 DstSize - The size of destination buffer.
870 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
871 ScratchSize - The size of scratch buffer.
875 EFI_SUCCESS - Decompression is successfull
876 EFI_INVALID_PARAMETER - The source data is corrupted
881 // For EFI 1.1 de/compression algorithm, the version is 1.
900 OUT UINT32
*ScratchSize
906 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
910 This - The protocol instance pointer
911 Source - The source buffer containing the compressed data.
912 SrcSize - The size of source buffer
913 DstSize - The size of destination buffer.
914 ScratchSize - The size of scratch buffer.
918 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
919 EFI_INVALID_PARAMETER - The source data is corrupted
936 IN OUT VOID
*Destination
,
938 IN OUT VOID
*Scratch
,
939 IN UINT32 ScratchSize
945 The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
949 This - The protocol instance pointer
950 Source - The source buffer containing the compressed data.
951 SrcSize - The size of source buffer
952 Destination - The destination buffer to store the decompressed data
953 DstSize - The size of destination buffer.
954 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
955 ScratchSize - The size of scratch buffer.
959 EFI_SUCCESS - Decompression is successfull
960 EFI_INVALID_PARAMETER - The source data is corrupted
965 // For Tiano de/compression algorithm, the version is 2.