]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/Common/EfiCompress.c
2 Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
3 coding. LZ77 transforms the source data into a sequence of Original Characters
4 and Pointers to repeated strings. This sequence is further divided into Blocks
5 and Huffman codings are applied to each Block.
7 Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
8 This program and the accompanying materials
9 are licensed and made available under the terms and conditions of the BSD License
10 which accompanies this distribution. The full text of the license may be found at
11 http://opensource.org/licenses/bsd-license.php
13 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
14 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
27 #define UINT8_MAX 0xff
32 #define WNDSIZ (1U << WNDBIT)
34 #define PERC_FLAG 0x8000U
37 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
38 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
39 #define CRCPOLY 0xA001
40 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
43 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
46 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
48 #define NP (WNDBIT + 1)
50 #define NT (CODE_BIT + 3)
59 // Function Prototypes
230 IN UINT16 FreqParm
[],
232 OUT UINT16 CodeParm
[]
240 STATIC UINT8
*mSrc
, *mDst
, *mSrcUpperLimit
, *mDstUpperLimit
;
242 STATIC UINT8
*mLevel
, *mText
, *mChildCount
, *mBuf
, mCLen
[NC
], mPTLen
[NPT
], *mLen
;
243 STATIC INT16 mHeap
[NC
+ 1];
244 STATIC INT32 mRemainder
, mMatchLen
, mBitCount
, mHeapSize
, mN
;
245 STATIC UINT32 mBufSiz
= 0, mOutputPos
, mOutputMask
, mSubBitBuf
, mCrc
;
246 STATIC UINT32 mCompSize
, mOrigSize
;
248 STATIC UINT16
*mFreq
, *mSortPtr
, mLenCnt
[17], mLeft
[2 * NC
- 1], mRight
[2 * NC
- 1],
249 mCrcTable
[UINT8_MAX
+ 1], mCFreq
[2 * NC
- 1],mCCode
[NC
],
250 mPFreq
[2 * NP
- 1], mPTCode
[NPT
], mTFreq
[2 * NT
- 1];
252 STATIC NODE mPos
, mMatchPos
, mAvail
, *mPosition
, *mParent
, *mPrev
, *mNext
= NULL
;
264 IN OUT UINT32
*DstSize
270 The main compression routine.
274 SrcBuffer - The buffer storing the source data
275 SrcSize - The size of source data
276 DstBuffer - The buffer to store the compressed data
277 DstSize - On input, the size of DstBuffer; On output,
278 the size of the actual compressed data.
282 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
283 DstSize contains the size needed.
284 EFI_SUCCESS - Compression is successful.
288 EFI_STATUS Status
= EFI_SUCCESS
;
305 mSrcUpperLimit
= mSrc
+ SrcSize
;
307 mDstUpperLimit
= mDst
+ *DstSize
;
314 mOrigSize
= mCompSize
= 0;
322 if (EFI_ERROR (Status
)) {
323 return EFI_OUT_OF_RESOURCES
;
327 // Null terminate the compressed data
329 if (mDst
< mDstUpperLimit
) {
334 // Fill in compressed size and original size
337 PutDword(mCompSize
+1);
344 if (mCompSize
+ 1 + 8 > *DstSize
) {
345 *DstSize
= mCompSize
+ 1 + 8;
346 return EFI_BUFFER_TOO_SMALL
;
348 *DstSize
= mCompSize
+ 1 + 8;
363 Put a dword to output stream
367 Data - the dword to put
373 if (mDst
< mDstUpperLimit
) {
374 *mDst
++ = (UINT8
)(((UINT8
)(Data
)) & 0xff);
377 if (mDst
< mDstUpperLimit
) {
378 *mDst
++ = (UINT8
)(((UINT8
)(Data
>> 0x08)) & 0xff);
381 if (mDst
< mDstUpperLimit
) {
382 *mDst
++ = (UINT8
)(((UINT8
)(Data
>> 0x10)) & 0xff);
385 if (mDst
< mDstUpperLimit
) {
386 *mDst
++ = (UINT8
)(((UINT8
)(Data
>> 0x18)) & 0xff);
397 Allocate memory spaces for data structures used in compression process
403 EFI_SUCCESS - Memory is allocated successfully
404 EFI_OUT_OF_RESOURCES - Allocation fails
410 mText
= malloc (WNDSIZ
* 2 + MAXMATCH
);
412 return EFI_OUT_OF_RESOURCES
;
414 for (i
= 0 ; i
< WNDSIZ
* 2 + MAXMATCH
; i
++) {
418 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof(*mLevel
));
419 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof(*mChildCount
));
420 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof(*mPosition
));
421 mParent
= malloc (WNDSIZ
* 2 * sizeof(*mParent
));
422 mPrev
= malloc (WNDSIZ
* 2 * sizeof(*mPrev
));
423 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof(*mNext
));
424 if (mLevel
== NULL
|| mChildCount
== NULL
|| mPosition
== NULL
||
425 mParent
== NULL
|| mPrev
== NULL
|| mNext
== NULL
) {
426 return EFI_OUT_OF_RESOURCES
;
429 mBufSiz
= 16 * 1024U;
430 while ((mBuf
= malloc(mBufSiz
)) == NULL
) {
431 mBufSiz
= (mBufSiz
/ 10U) * 9U;
432 if (mBufSiz
< 4 * 1024U) {
433 return EFI_OUT_OF_RESOURCES
;
447 Called when compression is completed to free memory previously allocated.
498 Initialize String Info Log data structures
508 for (i
= WNDSIZ
; i
<= WNDSIZ
+ UINT8_MAX
; i
++) {
510 mPosition
[i
] = NIL
; /* sentinel */
512 for (i
= WNDSIZ
; i
< WNDSIZ
* 2; i
++) {
516 for (i
= 1; i
< WNDSIZ
- 1; i
++) {
517 mNext
[i
] = (NODE
)(i
+ 1);
520 mNext
[WNDSIZ
- 1] = NIL
;
521 for (i
= WNDSIZ
* 2; i
<= MAX_HASH_VAL
; i
++) {
537 Find child node given the parent node and the edge character
542 c - the edge character
546 The child node (NIL if not found)
552 r
= mNext
[HASH(q
, c
)];
553 mParent
[NIL
] = q
; /* sentinel */
554 while (mParent
[r
] != q
) {
572 Create a new child for a given parent node.
577 c - the edge character
586 h
= (NODE
)HASH(q
, c
);
609 Old - the node to split
619 mChildCount
[New
] = 0;
626 mParent
[New
] = mParent
[Old
];
627 mLevel
[New
] = (UINT8
)mMatchLen
;
628 mPosition
[New
] = mPos
;
629 MakeChild(New
, mText
[mMatchPos
+ mMatchLen
], Old
);
630 MakeChild(New
, mText
[mPos
+ mMatchLen
], mPos
);
640 Insert string info for current position into the String Info Log
651 if (mMatchLen
>= 4) {
654 // We have just got a long match, the target tree
655 // can be located by MatchPos + 1. Travese the tree
656 // from bottom up to get to a proper starting point.
657 // The usage of PERC_FLAG ensures proper node deletion
658 // in DeleteNode() later.
662 r
= (INT16
)((mMatchPos
+ 1) | WNDSIZ
);
663 while ((q
= mParent
[r
]) == NIL
) {
666 while (mLevel
[q
] >= mMatchLen
) {
667 r
= q
; q
= mParent
[q
];
670 while (mPosition
[t
] < 0) {
675 mPosition
[t
] = (NODE
)(mPos
| PERC_FLAG
);
680 // Locate the target tree
683 q
= (INT16
)(mText
[mPos
] + WNDSIZ
);
685 if ((r
= Child(q
, c
)) == NIL
) {
686 MakeChild(q
, c
, mPos
);
694 // Traverse down the tree to find a match.
695 // Update Position value along the route.
696 // Node split or creation is involved.
705 mMatchPos
= (NODE
)(mPosition
[r
] & ~PERC_FLAG
);
707 if (mMatchPos
>= mPos
) {
710 t1
= &mText
[mPos
+ mMatchLen
];
711 t2
= &mText
[mMatchPos
+ mMatchLen
];
712 while (mMatchLen
< j
) {
721 if (mMatchLen
>= MAXMATCH
) {
726 if ((r
= Child(q
, *t1
)) == NIL
) {
727 MakeChild(q
, *t1
, mPos
);
742 // Special usage of 'next'
755 Delete outdated string info. (The Usage of PERC_FLAG
756 ensures a clean deletion)
766 if (mParent
[mPos
] == NIL
) {
776 if (r
>= WNDSIZ
|| --mChildCount
[r
] > 1) {
779 t
= (NODE
)(mPosition
[r
] & ~PERC_FLAG
);
785 while ((u
= mPosition
[q
]) & PERC_FLAG
) {
793 mPosition
[q
] = (INT16
)(s
| WNDSIZ
);
803 mPosition
[q
] = (INT16
)(s
| WNDSIZ
| PERC_FLAG
);
805 s
= Child(r
, mText
[t
+ mLevel
[r
]]);
816 mParent
[s
] = mParent
[r
];
829 Advance the current position (read in new data if needed).
830 Delete outdated string info. Find a match string for current position.
841 if (++mPos
== WNDSIZ
* 2) {
842 memmove(&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
843 n
= FreadCrc(&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
858 The main controlling routine for compression process.
864 EFI_SUCCESS - The compression is successful
865 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
873 Status
= AllocateMemory();
874 if (EFI_ERROR(Status
)) {
883 mRemainder
= FreadCrc(&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
888 if (mMatchLen
> mRemainder
) {
889 mMatchLen
= mRemainder
;
891 while (mRemainder
> 0) {
892 LastMatchLen
= mMatchLen
;
893 LastMatchPos
= mMatchPos
;
895 if (mMatchLen
> mRemainder
) {
896 mMatchLen
= mRemainder
;
899 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
902 // Not enough benefits are gained by outputting a pointer,
903 // so just output the original character
906 Output(mText
[mPos
- 1], 0);
910 // Outputting a pointer is beneficial enough, do it.
913 Output(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
914 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
915 while (--LastMatchLen
> 0) {
918 if (mMatchLen
> mRemainder
) {
919 mMatchLen
= mRemainder
;
936 Count the frequencies for the Extra Set
944 INT32 i
, k
, n
, Count
;
946 for (i
= 0; i
< NT
; i
++) {
950 while (n
> 0 && mCLen
[n
- 1] == 0) {
958 while (i
< n
&& mCLen
[i
] == 0) {
963 mTFreq
[0] = (UINT16
)(mTFreq
[0] + Count
);
964 } else if (Count
<= 18) {
966 } else if (Count
== 19) {
989 Outputs the code length array for the Extra Set or the Position Set.
993 n - the number of symbols
994 nbit - the number of bits needed to represent 'n'
995 Special - the special symbol that needs to be take care of
1003 while (n
> 0 && mPTLen
[n
- 1] == 0) {
1013 PutBits(k
- 3, (1U << (k
- 3)) - 2);
1016 while (i
< 6 && mPTLen
[i
] == 0) {
1019 PutBits(2, (i
- 3) & 3);
1029 Routine Description:
1031 Outputs the code length array for Char&Length Set
1039 INT32 i
, k
, n
, Count
;
1042 while (n
> 0 && mCLen
[n
- 1] == 0) {
1051 while (i
< n
&& mCLen
[i
] == 0) {
1056 for (k
= 0; k
< Count
; k
++) {
1057 PutBits(mPTLen
[0], mPTCode
[0]);
1059 } else if (Count
<= 18) {
1060 PutBits(mPTLen
[1], mPTCode
[1]);
1061 PutBits(4, Count
- 3);
1062 } else if (Count
== 19) {
1063 PutBits(mPTLen
[0], mPTCode
[0]);
1064 PutBits(mPTLen
[1], mPTCode
[1]);
1067 PutBits(mPTLen
[2], mPTCode
[2]);
1068 PutBits(CBIT
, Count
- 20);
1071 PutBits(mPTLen
[k
+ 2], mPTCode
[k
+ 2]);
1082 PutBits(mCLen
[c
], mCCode
[c
]);
1099 PutBits(mPTLen
[c
], mPTCode
[c
]);
1101 PutBits(c
- 1, p
& (0xFFFFU
>> (17 - c
)));
1110 Routine Description:
1112 Huffman code the block and output it.
1120 UINT32 i
, k
, Flags
, Root
, Pos
, Size
;
1123 Root
= MakeTree(NC
, mCFreq
, mCLen
, mCCode
);
1124 Size
= mCFreq
[Root
];
1128 Root
= MakeTree(NT
, mTFreq
, mPTLen
, mPTCode
);
1130 WritePTLen(NT
, TBIT
, 3);
1133 PutBits(TBIT
, Root
);
1140 PutBits(CBIT
, Root
);
1142 Root
= MakeTree(NP
, mPFreq
, mPTLen
, mPTCode
);
1144 WritePTLen(NP
, PBIT
, -1);
1147 PutBits(PBIT
, Root
);
1150 for (i
= 0; i
< Size
; i
++) {
1151 if (i
% UINT8_BIT
== 0) {
1152 Flags
= mBuf
[Pos
++];
1156 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1157 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1158 k
= mBuf
[Pos
++] << UINT8_BIT
;
1162 EncodeC(mBuf
[Pos
++]);
1165 for (i
= 0; i
< NC
; i
++) {
1168 for (i
= 0; i
< NP
; i
++) {
1182 Routine Description:
1184 Outputs an Original Character or a Pointer
1188 c - The original character or the 'String Length' element of a Pointer
1189 p - The 'Position' field of a Pointer
1197 if ((mOutputMask
>>= 1) == 0) {
1198 mOutputMask
= 1U << (UINT8_BIT
- 1);
1199 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1203 CPos
= mOutputPos
++;
1206 mBuf
[mOutputPos
++] = (UINT8
) c
;
1208 if (c
>= (1U << UINT8_BIT
)) {
1209 mBuf
[CPos
] |= mOutputMask
;
1210 mBuf
[mOutputPos
++] = (UINT8
)(p
>> UINT8_BIT
);
1211 mBuf
[mOutputPos
++] = (UINT8
) p
;
1227 for (i
= 0; i
< NC
; i
++) {
1230 for (i
= 0; i
< NP
; i
++) {
1233 mOutputPos
= mOutputMask
= 0;
1245 // Flush remaining bits
1247 PutBits(UINT8_BIT
- 1, 0);
1259 for (i
= 0; i
<= UINT8_MAX
; i
++) {
1261 for (j
= 0; j
< UINT8_BIT
; j
++) {
1263 r
= (r
>> 1) ^ CRCPOLY
;
1268 mCrcTable
[i
] = (UINT16
)r
;
1280 Routine Description:
1282 Outputs rightmost n bits of x
1286 n - the rightmost n bits of the data is used
1295 if (n
< mBitCount
) {
1296 mSubBitBuf
|= x
<< (mBitCount
-= n
);
1299 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (n
-= mBitCount
)));
1300 if (mDst
< mDstUpperLimit
) {
1305 if (n
< UINT8_BIT
) {
1306 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- n
);
1309 Temp
= (UINT8
)(x
>> (n
- UINT8_BIT
));
1310 if (mDst
< mDstUpperLimit
) {
1315 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- n
);
1328 Routine Description:
1334 p - the buffer to hold the data
1335 n - number of bytes to read
1339 number of bytes actually read
1345 for (i
= 0; mSrc
< mSrcUpperLimit
&& i
< n
; i
++) {
1363 mBitCount
= UINT8_BIT
;
1374 Routine Description:
1376 Count the number of each code length for a Huffman tree.
1386 STATIC INT32 Depth
= 0;
1389 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1392 CountLen(mLeft
[i
]);
1393 CountLen(mRight
[i
]);
1405 Routine Description:
1407 Create code length array for a Huffman tree
1411 Root - the root of the tree
1418 for (i
= 0; i
<= 16; i
++) {
1424 // Adjust the length count array so that
1425 // no code will be generated longer than its designated length
1429 for (i
= 16; i
> 0; i
--) {
1430 Cum
+= mLenCnt
[i
] << (16 - i
);
1432 while (Cum
!= (1U << 16)) {
1434 for (i
= 15; i
> 0; i
--) {
1435 if (mLenCnt
[i
] != 0) {
1443 for (i
= 16; i
> 0; i
--) {
1446 mLen
[*mSortPtr
++] = (UINT8
)i
;
1460 // priority queue: send i-th entry down heap
1464 while ((j
= 2 * i
) <= mHeapSize
) {
1465 if (j
< mHeapSize
&& mFreq
[mHeap
[j
]] > mFreq
[mHeap
[j
+ 1]]) {
1468 if (mFreq
[k
] <= mFreq
[mHeap
[j
]]) {
1471 mHeap
[i
] = mHeap
[j
];
1474 mHeap
[i
] = (INT16
)k
;
1486 Routine Description:
1488 Assign code to each symbol based on the code length array
1492 n - number of symbols
1493 Len - the code length array
1494 Code - stores codes for each symbol
1504 for (i
= 1; i
<= 16; i
++) {
1505 Start
[i
+ 1] = (UINT16
)((Start
[i
] + mLenCnt
[i
]) << 1);
1507 for (i
= 0; i
< n
; i
++) {
1508 Code
[i
] = Start
[Len
[i
]]++;
1516 IN UINT16 FreqParm
[],
1517 OUT UINT8 LenParm
[],
1518 OUT UINT16 CodeParm
[]
1522 Routine Description:
1524 Generates Huffman codes given a frequency distribution of symbols
1528 NParm - number of symbols
1529 FreqParm - frequency of each symbol
1530 LenParm - code length for each symbol
1531 CodeParm - code for each symbol
1535 Root of the Huffman tree.
1539 INT32 i
, j
, k
, Avail
;
1542 // make tree, calculate len[], return root
1551 for (i
= 0; i
< mN
; i
++) {
1554 mHeap
[++mHeapSize
] = (INT16
)i
;
1557 if (mHeapSize
< 2) {
1558 CodeParm
[mHeap
[1]] = 0;
1561 for (i
= mHeapSize
/ 2; i
>= 1; i
--) {
1564 // make priority queue
1568 mSortPtr
= CodeParm
;
1572 *mSortPtr
++ = (UINT16
)i
;
1574 mHeap
[1] = mHeap
[mHeapSize
--];
1578 *mSortPtr
++ = (UINT16
)j
;
1581 mFreq
[k
] = (UINT16
)(mFreq
[i
] + mFreq
[j
]);
1582 mHeap
[1] = (INT16
)k
;
1584 mLeft
[k
] = (UINT16
)i
;
1585 mRight
[k
] = (UINT16
)j
;
1586 } while (mHeapSize
> 1);
1588 mSortPtr
= CodeParm
;
1590 MakeCode(NParm
, LenParm
, CodeParm
);