]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/CCode/Source/Common/Decompress.c
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)
19 for Efi and Tiano compress algorithm.
23 #include "Decompress.h"
26 // Decompression algorithm begins here
35 // C: Char&Len Set; P: Position Set; T: exTra Set
37 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
42 #define MAXNP ((1U << MAXPBIT) - 1)
43 #define NT (CODE_BIT + 3)
51 UINT8
*mSrcBase
; // Starting address of compressed data
52 UINT8
*mDstBase
; // Starting address of decompressed data
65 UINT16 mLeft
[2 * NC
- 1];
66 UINT16 mRight
[2 * NC
- 1];
73 STATIC UINT16 mPbit
= EFIPBIT
;
85 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
89 Sd - The global scratch data
90 NumOfBit - The number of bits to shift and read.
96 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
98 while (NumOfBits
> Sd
->mBitCount
) {
100 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
102 if (Sd
->mCompSize
> 0) {
104 // Get 1 byte into SubBitBuf
108 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
113 // No more bits from the source, just pad zero bit.
121 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
122 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
);
172 Creates Huffman Code mapping table according to code length array.
176 Sd - The global scratch data
177 NumOfChar - Number of symbols in the symbol set
178 BitLen - Code length array
179 TableBits - The width of the mapping table
185 BAD_TABLE - The table is corrupted.
202 for (Index
= 1; Index
<= 16; Index
++) {
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 while (Index
!= Index3
) {
242 Mask
= (UINT16
) (1U << (15 - TableBits
));
244 for (Char
= 0; Char
< NumOfChar
; Char
++) {
251 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
253 if (Len
<= TableBits
) {
255 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
262 Pointer
= &Table
[Index3
>> JuBits
];
263 Index
= (UINT16
) (Len
- TableBits
);
267 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
272 Pointer
= &Sd
->mRight
[*Pointer
];
274 Pointer
= &Sd
->mLeft
[*Pointer
];
285 Start
[Len
] = NextCode
;
302 Decodes a position value.
306 Sd - the global scratch data
310 The position value decoded.
318 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
321 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
325 if (Sd
->mBitBuf
& Mask
) {
326 Val
= Sd
->mRight
[Val
];
328 Val
= Sd
->mLeft
[Val
];
332 } while (Val
>= MAXNP
);
335 // Advance what we have read
337 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
341 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
359 Reads code lengths for the Extra Set or the Position Set
363 Sd - The global scratch data
364 nn - Number of symbols
365 nbit - Number of bits needed to represent nn
366 Special - The special symbol that needs to be taken care of
371 BAD_TABLE - Table is corrupted.
380 Number
= (UINT16
) GetBits (Sd
, nbit
);
383 CharC
= (UINT16
) GetBits (Sd
, nbit
);
385 for (Index
= 0; Index
< 256; Index
++) {
386 Sd
->mPTTable
[Index
] = CharC
;
389 for (Index
= 0; Index
< nn
; Index
++) {
390 Sd
->mPTLen
[Index
] = 0;
398 while (Index
< Number
) {
400 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
403 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
404 while (Mask
& Sd
->mBitBuf
) {
410 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
412 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
414 if (Index
== Special
) {
415 CharC
= (UINT16
) GetBits (Sd
, 2);
417 while ((INT16
) (CharC
) >= 0) {
418 Sd
->mPTLen
[Index
++] = 0;
425 Sd
->mPTLen
[Index
++] = 0;
428 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
440 Reads code lengths for Char&Len Set.
444 Sd - the global scratch data
455 Number
= (UINT16
) GetBits (Sd
, CBIT
);
458 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
460 for (Index
= 0; Index
< NC
; Index
++) {
461 Sd
->mCLen
[Index
] = 0;
464 for (Index
= 0; Index
< 4096; Index
++) {
465 Sd
->mCTable
[Index
] = CharC
;
472 while (Index
< Number
) {
474 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
476 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
480 if (Mask
& Sd
->mBitBuf
) {
481 CharC
= Sd
->mRight
[CharC
];
483 CharC
= Sd
->mLeft
[CharC
];
488 } while (CharC
>= NT
);
491 // Advance what we have read
493 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
499 } else if (CharC
== 1) {
500 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
501 } else if (CharC
== 2) {
502 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
506 while ((INT16
) (CharC
) >= 0) {
507 Sd
->mCLen
[Index
++] = 0;
513 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
519 Sd
->mCLen
[Index
++] = 0;
522 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
536 Decode a character/length value.
540 Sd - The global scratch data.
551 if (Sd
->mBlockSize
== 0) {
553 // Starting a new block
555 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
556 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
557 if (Sd
->mBadTableFlag
!= 0) {
563 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, mPbit
, (UINT16
) (-1));
564 if (Sd
->mBadTableFlag
!= 0) {
570 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
573 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
576 if (Sd
->mBitBuf
& Mask
) {
577 Index2
= Sd
->mRight
[Index2
];
579 Index2
= Sd
->mLeft
[Index2
];
583 } while (Index2
>= NC
);
586 // Advance what we have read
588 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
602 Decode the source data and put the resulting data into the destination buffer.
606 Sd - The global scratch data
616 BytesRemain
= (UINT16
) (-1);
621 CharC
= DecodeC (Sd
);
622 if (Sd
->mBadTableFlag
!= 0) {
628 // Process an Original character
630 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
631 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
639 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
643 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
646 while ((INT16
) (BytesRemain
) >= 0) {
647 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
648 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
665 OUT UINT32
*ScratchSize
671 The implementation of EFI_DECOMPRESS_PROTOCOL.GetInfo().
675 Source - The source buffer containing the compressed data.
676 SrcSize - The size of source buffer
677 DstSize - The size of destination buffer.
678 ScratchSize - The size of scratch buffer.
682 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
683 EFI_INVALID_PARAMETER - The source data is corrupted
689 *ScratchSize
= sizeof (SCRATCH_DATA
);
693 return EFI_INVALID_PARAMETER
;
696 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
704 IN OUT VOID
*Destination
,
706 IN OUT VOID
*Scratch
,
707 IN UINT32 ScratchSize
713 The implementation Efi and Tiano Decompress().
717 Source - The source buffer containing the compressed data.
718 SrcSize - The size of source buffer
719 Destination - The destination buffer to store the decompressed data
720 DstSize - The size of destination buffer.
721 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
722 ScratchSize - The size of scratch buffer.
726 EFI_SUCCESS - Decompression is successfull
727 EFI_INVALID_PARAMETER - The source data is corrupted
739 Status
= EFI_SUCCESS
;
743 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
744 return EFI_INVALID_PARAMETER
;
747 Sd
= (SCRATCH_DATA
*) Scratch
;
750 return EFI_INVALID_PARAMETER
;
753 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
754 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
756 if (SrcSize
< CompSize
+ 8) {
757 return EFI_INVALID_PARAMETER
;
760 if (DstSize
!= OrigSize
) {
761 return EFI_INVALID_PARAMETER
;
766 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
767 ((UINT8
*) Sd
)[Index
] = 0;
772 Sd
->mCompSize
= CompSize
;
773 Sd
->mOrigSize
= OrigSize
;
776 // Fill the first BITBUFSIZ bits
778 FillBuf (Sd
, BITBUFSIZ
);
785 if (Sd
->mBadTableFlag
!= 0) {
787 // Something wrong with the source
789 Status
= EFI_INVALID_PARAMETER
;
800 OUT UINT32
*ScratchSize
806 The implementation Efi Decompress GetInfo().
810 Source - The source buffer containing the compressed data.
811 SrcSize - The size of source buffer
812 DstSize - The size of destination buffer.
813 ScratchSize - The size of scratch buffer.
817 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
818 EFI_INVALID_PARAMETER - The source data is corrupted
822 return GetInfo (Source
, SrcSize
, DstSize
, ScratchSize
);
830 OUT UINT32
*ScratchSize
836 The implementation Tiano Decompress GetInfo().
840 Source - The source buffer containing the compressed data.
841 SrcSize - The size of source buffer
842 DstSize - The size of destination buffer.
843 ScratchSize - The size of scratch buffer.
847 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
848 EFI_INVALID_PARAMETER - The source data is corrupted
852 return GetInfo (Source
, SrcSize
, DstSize
, ScratchSize
);
859 IN OUT VOID
*Destination
,
861 IN OUT VOID
*Scratch
,
862 IN UINT32 ScratchSize
868 The implementation of Efi Decompress().
872 Source - The source buffer containing the compressed data.
873 SrcSize - The size of source buffer
874 Destination - The destination buffer to store the decompressed data
875 DstSize - The size of destination buffer.
876 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
877 ScratchSize - The size of scratch buffer.
881 EFI_SUCCESS - Decompression is successfull
882 EFI_INVALID_PARAMETER - The source data is corrupted
887 return Decompress (Source
, SrcSize
, Destination
, DstSize
, Scratch
, ScratchSize
);
894 IN OUT VOID
*Destination
,
896 IN OUT VOID
*Scratch
,
897 IN UINT32 ScratchSize
903 The implementation of Tiano Decompress().
907 Source - The source buffer containing the compressed data.
908 SrcSize - The size of source buffer
909 Destination - The destination buffer to store the decompressed data
910 DstSize - The size of destination buffer.
911 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
912 ScratchSize - The size of scratch buffer.
916 EFI_SUCCESS - Decompression is successfull
917 EFI_INVALID_PARAMETER - The source data is corrupted
922 return Decompress (Source
, SrcSize
, Destination
, DstSize
, Scratch
, ScratchSize
);