]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/Common/Decompress.c
2 Decompressor. Algorithm Ported from OPSD code (Decomp.asm) for Efi and Tiano
5 Copyright (c) 2004 - 2014, Intel Corporation. All rights reserved.<BR>
6 This program and the accompanying materials
7 are licensed and made available under the terms and conditions of the BSD License
8 which accompanies this distribution. The full text of the license may be found at
9 http://opensource.org/licenses/bsd-license.php
11 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
12 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 #include "Decompress.h"
21 // Decompression algorithm begins here
30 // C: Char&Len Set; P: Position Set; T: exTra Set
32 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
37 #define MAXNP ((1U << MAXPBIT) - 1)
38 #define NT (CODE_BIT + 3)
46 UINT8
*mSrcBase
; // Starting address of compressed data
47 UINT8
*mDstBase
; // Starting address of decompressed data
60 UINT16 mLeft
[2 * NC
- 1];
61 UINT16 mRight
[2 * NC
- 1];
68 STATIC UINT16 mPbit
= EFIPBIT
;
80 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
84 Sd - The global scratch data
85 NumOfBit - The number of bits to shift and read.
91 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
93 while (NumOfBits
> Sd
->mBitCount
) {
95 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
97 if (Sd
->mCompSize
> 0) {
99 // Get 1 byte into SubBitBuf
103 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
108 // No more bits from the source, just pad zero bit.
116 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
117 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
130 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
131 NumOfBits of bits from source. Returns NumOfBits of bits that are
136 Sd - The global scratch data.
137 NumOfBits - The number of bits to pop and read.
141 The bits that are popped out.
147 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
149 FillBuf (Sd
, NumOfBits
);
167 Creates Huffman Code mapping table according to code length array.
171 Sd - The global scratch data
172 NumOfChar - Number of symbols in the symbol set
173 BitLen - Code length array
174 TableBits - The width of the mapping table
180 BAD_TABLE - The table is corrupted.
197 for (Index
= 1; Index
<= 16; Index
++) {
201 for (Index
= 0; Index
< NumOfChar
; Index
++) {
202 Count
[BitLen
[Index
]]++;
207 for (Index
= 1; Index
<= 16; Index
++) {
208 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
211 if (Start
[17] != 0) {
213 return (UINT16
) BAD_TABLE
;
216 JuBits
= (UINT16
) (16 - TableBits
);
218 for (Index
= 1; Index
<= TableBits
; Index
++) {
219 Start
[Index
] >>= JuBits
;
220 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
223 while (Index
<= 16) {
224 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
228 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
231 Index3
= (UINT16
) (1U << TableBits
);
232 while (Index
!= Index3
) {
238 Mask
= (UINT16
) (1U << (15 - TableBits
));
240 for (Char
= 0; Char
< NumOfChar
; Char
++) {
247 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
249 if (Len
<= TableBits
) {
251 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
258 Pointer
= &Table
[Index3
>> JuBits
];
259 Index
= (UINT16
) (Len
- TableBits
);
263 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
268 Pointer
= &Sd
->mRight
[*Pointer
];
270 Pointer
= &Sd
->mLeft
[*Pointer
];
281 Start
[Len
] = NextCode
;
298 Decodes a position value.
302 Sd - the global scratch data
306 The position value decoded.
314 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
317 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
321 if (Sd
->mBitBuf
& Mask
) {
322 Val
= Sd
->mRight
[Val
];
324 Val
= Sd
->mLeft
[Val
];
328 } while (Val
>= MAXNP
);
331 // Advance what we have read
333 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
337 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
355 Reads code lengths for the Extra Set or the Position Set
359 Sd - The global scratch data
360 nn - Number of symbols
361 nbit - Number of bits needed to represent nn
362 Special - The special symbol that needs to be taken care of
367 BAD_TABLE - Table is corrupted.
376 Number
= (UINT16
) GetBits (Sd
, nbit
);
379 CharC
= (UINT16
) GetBits (Sd
, nbit
);
381 for (Index
= 0; Index
< 256; Index
++) {
382 Sd
->mPTTable
[Index
] = CharC
;
385 for (Index
= 0; Index
< nn
; Index
++) {
386 Sd
->mPTLen
[Index
] = 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);
413 while ((INT16
) (CharC
) >= 0) {
414 Sd
->mPTLen
[Index
++] = 0;
421 Sd
->mPTLen
[Index
++] = 0;
424 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
436 Reads code lengths for Char&Len Set.
440 Sd - the global scratch data
451 Number
= (UINT16
) GetBits (Sd
, CBIT
);
454 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
456 for (Index
= 0; Index
< NC
; Index
++) {
457 Sd
->mCLen
[Index
] = 0;
460 for (Index
= 0; Index
< 4096; Index
++) {
461 Sd
->mCTable
[Index
] = CharC
;
468 while (Index
< Number
) {
470 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
472 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
476 if (Mask
& Sd
->mBitBuf
) {
477 CharC
= Sd
->mRight
[CharC
];
479 CharC
= Sd
->mLeft
[CharC
];
484 } while (CharC
>= NT
);
487 // Advance what we have read
489 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
495 } else if (CharC
== 1) {
496 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
497 } else if (CharC
== 2) {
498 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
502 while ((INT16
) (CharC
) >= 0) {
503 Sd
->mCLen
[Index
++] = 0;
509 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
515 Sd
->mCLen
[Index
++] = 0;
518 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
532 Decode a character/length value.
536 Sd - The global scratch data.
547 if (Sd
->mBlockSize
== 0) {
549 // Starting a new block
551 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
552 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
553 if (Sd
->mBadTableFlag
!= 0) {
559 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, mPbit
, (UINT16
) (-1));
560 if (Sd
->mBadTableFlag
!= 0) {
566 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
569 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
572 if (Sd
->mBitBuf
& Mask
) {
573 Index2
= Sd
->mRight
[Index2
];
575 Index2
= Sd
->mLeft
[Index2
];
579 } while (Index2
>= NC
);
582 // Advance what we have read
584 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
598 Decode the source data and put the resulting data into the destination buffer.
602 Sd - The global scratch data
612 BytesRemain
= (UINT16
) (-1);
617 CharC
= DecodeC (Sd
);
618 if (Sd
->mBadTableFlag
!= 0) {
624 // Process an Original character
626 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
627 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
635 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
639 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
642 while ((INT16
) (BytesRemain
) >= 0) {
643 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
644 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
661 OUT UINT32
*ScratchSize
667 The implementation of EFI_DECOMPRESS_PROTOCOL.GetInfo().
671 Source - The source buffer containing the compressed data.
672 SrcSize - The size of source buffer
673 DstSize - The size of destination buffer.
674 ScratchSize - The size of scratch buffer.
678 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
679 EFI_INVALID_PARAMETER - The source data is corrupted
685 *ScratchSize
= sizeof (SCRATCH_DATA
);
689 return EFI_INVALID_PARAMETER
;
692 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
700 IN OUT VOID
*Destination
,
702 IN OUT VOID
*Scratch
,
703 IN UINT32 ScratchSize
709 The implementation Efi and Tiano Decompress().
713 Source - The source buffer containing the compressed data.
714 SrcSize - The size of source buffer
715 Destination - The destination buffer to store the decompressed data
716 DstSize - The size of destination buffer.
717 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
718 ScratchSize - The size of scratch buffer.
722 EFI_SUCCESS - Decompression is successfull
723 EFI_INVALID_PARAMETER - The source data is corrupted
735 Status
= EFI_SUCCESS
;
739 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
740 return EFI_INVALID_PARAMETER
;
743 Sd
= (SCRATCH_DATA
*) Scratch
;
746 return EFI_INVALID_PARAMETER
;
749 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
750 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
752 if (SrcSize
< CompSize
+ 8) {
753 return EFI_INVALID_PARAMETER
;
756 if (DstSize
!= OrigSize
) {
757 return EFI_INVALID_PARAMETER
;
762 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
763 ((UINT8
*) Sd
)[Index
] = 0;
768 Sd
->mCompSize
= CompSize
;
769 Sd
->mOrigSize
= OrigSize
;
772 // Fill the first BITBUFSIZ bits
774 FillBuf (Sd
, BITBUFSIZ
);
781 if (Sd
->mBadTableFlag
!= 0) {
783 // Something wrong with the source
785 Status
= EFI_INVALID_PARAMETER
;
796 OUT UINT32
*ScratchSize
802 The implementation Efi Decompress GetInfo().
806 Source - The source buffer containing the compressed data.
807 SrcSize - The size of source buffer
808 DstSize - The size of destination buffer.
809 ScratchSize - The size of scratch buffer.
813 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
814 EFI_INVALID_PARAMETER - The source data is corrupted
818 return GetInfo (Source
, SrcSize
, DstSize
, ScratchSize
);
826 OUT UINT32
*ScratchSize
832 The implementation Tiano Decompress GetInfo().
836 Source - The source buffer containing the compressed data.
837 SrcSize - The size of source buffer
838 DstSize - The size of destination buffer.
839 ScratchSize - The size of scratch buffer.
843 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
844 EFI_INVALID_PARAMETER - The source data is corrupted
848 return GetInfo (Source
, SrcSize
, DstSize
, ScratchSize
);
855 IN OUT VOID
*Destination
,
857 IN OUT VOID
*Scratch
,
858 IN UINT32 ScratchSize
864 The implementation of Efi Decompress().
868 Source - The source buffer containing the compressed data.
869 SrcSize - The size of source buffer
870 Destination - The destination buffer to store the decompressed data
871 DstSize - The size of destination buffer.
872 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
873 ScratchSize - The size of scratch buffer.
877 EFI_SUCCESS - Decompression is successfull
878 EFI_INVALID_PARAMETER - The source data is corrupted
883 return Decompress (Source
, SrcSize
, Destination
, DstSize
, Scratch
, ScratchSize
);
890 IN OUT VOID
*Destination
,
892 IN OUT VOID
*Scratch
,
893 IN UINT32 ScratchSize
899 The implementation of Tiano Decompress().
903 Source - The source buffer containing the compressed data.
904 SrcSize - The size of source buffer
905 Destination - The destination buffer to store the decompressed data
906 DstSize - The size of destination buffer.
907 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
908 ScratchSize - The size of scratch buffer.
912 EFI_SUCCESS - Decompression is successfull
913 EFI_INVALID_PARAMETER - The source data is corrupted
918 return Decompress (Source
, SrcSize
, Destination
, DstSize
, Scratch
, ScratchSize
);
925 OUT VOID
**Destination
,
934 Status
= EFI_SUCCESS
;
937 *Destination
= (VOID
*)malloc(SrcSize
);
938 if (*Destination
!= NULL
) {
939 memcpy(*Destination
, Source
, SrcSize
);
941 Status
= EFI_OUT_OF_RESOURCES
;
945 Status
= EfiGetInfo(Source
, SrcSize
, DstSize
, &ScratchSize
);
946 if (Status
== EFI_SUCCESS
) {
947 Scratch
= (VOID
*)malloc(ScratchSize
);
948 *Destination
= (VOID
*)malloc(*DstSize
);
949 if (Scratch
!= NULL
&& *Destination
!= NULL
) {
950 Status
= EfiDecompress(Source
, SrcSize
, *Destination
, *DstSize
, Scratch
, ScratchSize
);
952 Status
= EFI_OUT_OF_RESOURCES
;
957 Status
= TianoGetInfo(Source
, SrcSize
, DstSize
, &ScratchSize
);
958 if (Status
== EFI_SUCCESS
) {
959 Scratch
= (VOID
*)malloc(ScratchSize
);
960 *Destination
= (VOID
*)malloc(*DstSize
);
961 if (Scratch
!= NULL
&& *Destination
!= NULL
) {
962 Status
= TianoDecompress(Source
, SrcSize
, *Destination
, *DstSize
, Scratch
, ScratchSize
);
964 Status
= EFI_OUT_OF_RESOURCES
;
969 Status
= EFI_INVALID_PARAMETER
;