]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/CodeTools/Source/Common/EfiDecompress.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)
22 #include "EfiDecompress.h"
25 // Decompression algorithm begins here
34 // C: Char&Len Set; P: Position Set; T: exTra Set
36 #define NC (0xff + MAXMATCH + 2 - THRESHOLD)
40 #define MAXNP ((1U << PBIT) - 1)
41 #define NT (CODE_BIT + 3)
49 UINT8
*mSrcBase
; // Starting address of compressed data
50 UINT8
*mDstBase
; // Starting address of decompressed data
63 UINT16 mLeft
[2 * NC
- 1];
64 UINT16 mRight
[2 * NC
- 1];
81 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
85 Sd - The global scratch data
86 NumOfBit - The number of bits to shift and read.
92 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
94 while (NumOfBits
> Sd
->mBitCount
) {
96 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
98 if (Sd
->mCompSize
> 0) {
100 // Get 1 byte into SubBitBuf
104 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
109 // No more bits from the source, just pad zero bit.
117 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
118 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
131 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
132 NumOfBits of bits from source. Returns NumOfBits of bits that are
137 Sd - The global scratch data.
138 NumOfBits - The number of bits to pop and read.
142 The bits that are popped out.
148 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
150 FillBuf (Sd
, NumOfBits
);
168 Creates Huffman Code mapping table according to code length array.
172 Sd - The global scratch data
173 NumOfChar - Number of symbols in the symbol set
174 BitLen - Code length array
175 TableBits - The width of the mapping table
181 BAD_TABLE - The table is corrupted.
198 for (Index
= 1; Index
<= 16; Index
++) {
202 for (Index
= 0; Index
< NumOfChar
; Index
++) {
203 Count
[BitLen
[Index
]]++;
208 for (Index
= 1; Index
<= 16; Index
++) {
209 Start
[Index
+ 1] = (UINT16
) (Start
[Index
] + (Count
[Index
] << (16 - Index
)));
212 if (Start
[17] != 0) {
214 return (UINT16
) BAD_TABLE
;
217 JuBits
= (UINT16
) (16 - TableBits
);
219 for (Index
= 1; Index
<= TableBits
; Index
++) {
220 Start
[Index
] >>= JuBits
;
221 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
224 while (Index
<= 16) {
225 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
, PBIT
, (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 of EFI_DECOMPRESS_PROTOCOL.Decompress().
713 This - The protocol instance pointer
714 Source - The source buffer containing the compressed data.
715 SrcSize - The size of source buffer
716 Destination - The destination buffer to store the decompressed data
717 DstSize - The size of destination buffer.
718 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
719 ScratchSize - The size of scratch buffer.
723 EFI_SUCCESS - Decompression is successfull
724 EFI_INVALID_PARAMETER - The source data is corrupted
736 Status
= EFI_SUCCESS
;
740 if (ScratchSize
< sizeof (SCRATCH_DATA
)) {
741 return EFI_INVALID_PARAMETER
;
744 Sd
= (SCRATCH_DATA
*) Scratch
;
747 return EFI_INVALID_PARAMETER
;
750 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
751 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
753 if (SrcSize
< CompSize
+ 8) {
754 return EFI_INVALID_PARAMETER
;
757 if (DstSize
!= OrigSize
) {
758 return EFI_INVALID_PARAMETER
;
763 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
764 ((UINT8
*) Sd
)[Index
] = 0;
769 Sd
->mCompSize
= CompSize
;
770 Sd
->mOrigSize
= OrigSize
;
773 // Fill the first BITBUFSIZ bits
775 FillBuf (Sd
, BITBUFSIZ
);
782 if (Sd
->mBadTableFlag
!= 0) {
784 // Something wrong with the source
786 Status
= EFI_INVALID_PARAMETER
;