]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/Common/Decompress.c
3 Copyright (c) 2004 - 2008, 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.
25 #include "Decompress.h"
28 // Decompression algorithm begins here
37 // C: Char&Len Set; P: Position Set; T: exTra Set
39 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
44 #define MAXNP ((1U << MAXPBIT) - 1)
45 #define NT (CODE_BIT + 3)
53 UINT8
*mSrcBase
; // Starting address of compressed data
54 UINT8
*mDstBase
; // Starting address of decompressed data
67 UINT16 mLeft
[2 * NC
- 1];
68 UINT16 mRight
[2 * NC
- 1];
75 STATIC UINT16 mPbit
= EFIPBIT
;
87 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
91 Sd - The global scratch data
92 NumOfBit - 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 for (Index
= 1; Index
<= 16; Index
++) {
208 for (Index
= 0; Index
< NumOfChar
; Index
++) {
209 Count
[BitLen
[Index
]]++;
214 for (Index
= 1; Index
<= 16; Index
++) {
215 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
218 if (Start
[17] != 0) {
220 return (UINT16
) BAD_TABLE
;
223 JuBits
= (UINT16
) (16 - TableBits
);
225 for (Index
= 1; Index
<= TableBits
; Index
++) {
226 Start
[Index
] >>= JuBits
;
227 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
230 while (Index
<= 16) {
231 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
235 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
238 Index3
= (UINT16
) (1U << TableBits
);
239 while (Index
!= Index3
) {
245 Mask
= (UINT16
) (1U << (15 - TableBits
));
247 for (Char
= 0; Char
< NumOfChar
; Char
++) {
254 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
256 if (Len
<= TableBits
) {
258 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
265 Pointer
= &Table
[Index3
>> JuBits
];
266 Index
= (UINT16
) (Len
- TableBits
);
270 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
275 Pointer
= &Sd
->mRight
[*Pointer
];
277 Pointer
= &Sd
->mLeft
[*Pointer
];
288 Start
[Len
] = NextCode
;
305 Decodes a position value.
309 Sd - the global scratch data
313 The position value decoded.
321 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
324 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
328 if (Sd
->mBitBuf
& Mask
) {
329 Val
= Sd
->mRight
[Val
];
331 Val
= Sd
->mLeft
[Val
];
335 } while (Val
>= MAXNP
);
338 // Advance what we have read
340 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
344 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
362 Reads code lengths for the Extra Set or the Position Set
366 Sd - The global scratch data
367 nn - Number of symbols
368 nbit - Number of bits needed to represent nn
369 Special - The special symbol that needs to be taken care of
374 BAD_TABLE - Table is corrupted.
383 Number
= (UINT16
) GetBits (Sd
, nbit
);
386 CharC
= (UINT16
) GetBits (Sd
, nbit
);
388 for (Index
= 0; Index
< 256; Index
++) {
389 Sd
->mPTTable
[Index
] = CharC
;
392 for (Index
= 0; Index
< nn
; Index
++) {
393 Sd
->mPTLen
[Index
] = 0;
401 while (Index
< Number
) {
403 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
406 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
407 while (Mask
& Sd
->mBitBuf
) {
413 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
415 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
417 if (Index
== Special
) {
418 CharC
= (UINT16
) GetBits (Sd
, 2);
420 while ((INT16
) (CharC
) >= 0) {
421 Sd
->mPTLen
[Index
++] = 0;
428 Sd
->mPTLen
[Index
++] = 0;
431 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
443 Reads code lengths for Char&Len Set.
447 Sd - the global scratch data
458 Number
= (UINT16
) GetBits (Sd
, CBIT
);
461 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
463 for (Index
= 0; Index
< NC
; Index
++) {
464 Sd
->mCLen
[Index
] = 0;
467 for (Index
= 0; Index
< 4096; Index
++) {
468 Sd
->mCTable
[Index
] = CharC
;
475 while (Index
< Number
) {
477 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
479 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
483 if (Mask
& Sd
->mBitBuf
) {
484 CharC
= Sd
->mRight
[CharC
];
486 CharC
= Sd
->mLeft
[CharC
];
491 } while (CharC
>= NT
);
494 // Advance what we have read
496 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
502 } else if (CharC
== 1) {
503 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
504 } else if (CharC
== 2) {
505 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
509 while ((INT16
) (CharC
) >= 0) {
510 Sd
->mCLen
[Index
++] = 0;
516 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
522 Sd
->mCLen
[Index
++] = 0;
525 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
539 Decode a character/length value.
543 Sd - The global scratch data.
554 if (Sd
->mBlockSize
== 0) {
556 // Starting a new block
558 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
559 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
560 if (Sd
->mBadTableFlag
!= 0) {
566 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, mPbit
, (UINT16
) (-1));
567 if (Sd
->mBadTableFlag
!= 0) {
573 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
576 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
579 if (Sd
->mBitBuf
& Mask
) {
580 Index2
= Sd
->mRight
[Index2
];
582 Index2
= Sd
->mLeft
[Index2
];
586 } while (Index2
>= NC
);
589 // Advance what we have read
591 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
605 Decode the source data and put the resulting data into the destination buffer.
609 Sd - The global scratch data
619 BytesRemain
= (UINT16
) (-1);
624 CharC
= DecodeC (Sd
);
625 if (Sd
->mBadTableFlag
!= 0) {
631 // Process an Original character
633 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
634 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
642 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
646 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
649 while ((INT16
) (BytesRemain
) >= 0) {
650 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
651 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
668 OUT UINT32
*ScratchSize
674 The implementation of EFI_DECOMPRESS_PROTOCOL.GetInfo().
678 Source - The source buffer containing the compressed data.
679 SrcSize - The size of source buffer
680 DstSize - The size of destination buffer.
681 ScratchSize - The size of scratch buffer.
685 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
686 EFI_INVALID_PARAMETER - The source data is corrupted
692 *ScratchSize
= sizeof (SCRATCH_DATA
);
696 return EFI_INVALID_PARAMETER
;
699 *DstSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
707 IN OUT VOID
*Destination
,
709 IN OUT VOID
*Scratch
,
710 IN UINT32 ScratchSize
716 The implementation Efi and Tiano Decompress().
720 Source - The source buffer containing the compressed data.
721 SrcSize - The size of source buffer
722 Destination - The destination buffer to store the decompressed data
723 DstSize - The size of destination buffer.
724 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
725 ScratchSize - The size of scratch buffer.
729 EFI_SUCCESS - Decompression is successfull
730 EFI_INVALID_PARAMETER - The source data is corrupted
742 Status
= EFI_SUCCESS
;
746 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
747 return EFI_INVALID_PARAMETER
;
750 Sd
= (SCRATCH_DATA
*) Scratch
;
753 return EFI_INVALID_PARAMETER
;
756 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
757 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
759 if (SrcSize
< CompSize
+ 8) {
760 return EFI_INVALID_PARAMETER
;
763 if (DstSize
!= OrigSize
) {
764 return EFI_INVALID_PARAMETER
;
769 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
770 ((UINT8
*) Sd
)[Index
] = 0;
775 Sd
->mCompSize
= CompSize
;
776 Sd
->mOrigSize
= OrigSize
;
779 // Fill the first BITBUFSIZ bits
781 FillBuf (Sd
, BITBUFSIZ
);
788 if (Sd
->mBadTableFlag
!= 0) {
790 // Something wrong with the source
792 Status
= EFI_INVALID_PARAMETER
;
803 OUT UINT32
*ScratchSize
809 The implementation Efi Decompress GetInfo().
813 Source - The source buffer containing the compressed data.
814 SrcSize - The size of source buffer
815 DstSize - The size of destination buffer.
816 ScratchSize - The size of scratch buffer.
820 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
821 EFI_INVALID_PARAMETER - The source data is corrupted
825 return GetInfo (Source
, SrcSize
, DstSize
, ScratchSize
);
833 OUT UINT32
*ScratchSize
839 The implementation Tiano Decompress GetInfo().
843 Source - The source buffer containing the compressed data.
844 SrcSize - The size of source buffer
845 DstSize - The size of destination buffer.
846 ScratchSize - The size of scratch buffer.
850 EFI_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
851 EFI_INVALID_PARAMETER - The source data is corrupted
855 return GetInfo (Source
, SrcSize
, DstSize
, ScratchSize
);
862 IN OUT VOID
*Destination
,
864 IN OUT VOID
*Scratch
,
865 IN UINT32 ScratchSize
871 The implementation of Efi Decompress().
875 Source - The source buffer containing the compressed data.
876 SrcSize - The size of source buffer
877 Destination - The destination buffer to store the decompressed data
878 DstSize - The size of destination buffer.
879 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
880 ScratchSize - The size of scratch buffer.
884 EFI_SUCCESS - Decompression is successfull
885 EFI_INVALID_PARAMETER - The source data is corrupted
890 return Decompress (Source
, SrcSize
, Destination
, DstSize
, Scratch
, ScratchSize
);
897 IN OUT VOID
*Destination
,
899 IN OUT VOID
*Scratch
,
900 IN UINT32 ScratchSize
906 The implementation of Tiano Decompress().
910 Source - The source buffer containing the compressed data.
911 SrcSize - The size of source buffer
912 Destination - The destination buffer to store the decompressed data
913 DstSize - The size of destination buffer.
914 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
915 ScratchSize - The size of scratch buffer.
919 EFI_SUCCESS - Decompression is successfull
920 EFI_INVALID_PARAMETER - The source data is corrupted
925 return Decompress (Source
, SrcSize
, Destination
, DstSize
, Scratch
, ScratchSize
);
932 OUT VOID
**Destination
,
941 Status
= EFI_SUCCESS
;
944 *Destination
= (VOID
*)malloc(SrcSize
);
945 if (*Destination
!= NULL
) {
946 memcpy(*Destination
, Source
, SrcSize
);
948 Status
= EFI_OUT_OF_RESOURCES
;
952 Status
= EfiGetInfo(Source
, SrcSize
, DstSize
, &ScratchSize
);
953 if (Status
== EFI_SUCCESS
) {
954 Scratch
= (VOID
*)malloc(ScratchSize
);
955 *Destination
= (VOID
*)malloc(*DstSize
);
956 if (Scratch
!= NULL
&& *Destination
!= NULL
) {
957 Status
= EfiDecompress(Source
, SrcSize
, *Destination
, *DstSize
, Scratch
, ScratchSize
);
959 Status
= EFI_OUT_OF_RESOURCES
;
964 Status
= TianoGetInfo(Source
, SrcSize
, DstSize
, &ScratchSize
);
965 if (Status
== EFI_SUCCESS
) {
966 Scratch
= (VOID
*)malloc(ScratchSize
);
967 *Destination
= (VOID
*)malloc(*DstSize
);
968 if (Scratch
!= NULL
&& *Destination
!= NULL
) {
969 Status
= TianoDecompress(Source
, SrcSize
, *Destination
, *DstSize
, Scratch
, ScratchSize
);
971 Status
= EFI_OUT_OF_RESOURCES
;
976 Status
= EFI_INVALID_PARAMETER
;