]>
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 - 2014, 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
);
411 for (i
= 0 ; i
< WNDSIZ
* 2 + MAXMATCH
; i
++) {
415 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof(*mLevel
));
416 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof(*mChildCount
));
417 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof(*mPosition
));
418 mParent
= malloc (WNDSIZ
* 2 * sizeof(*mParent
));
419 mPrev
= malloc (WNDSIZ
* 2 * sizeof(*mPrev
));
420 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof(*mNext
));
422 mBufSiz
= 16 * 1024U;
423 while ((mBuf
= malloc(mBufSiz
)) == NULL
) {
424 mBufSiz
= (mBufSiz
/ 10U) * 9U;
425 if (mBufSiz
< 4 * 1024U) {
426 return EFI_OUT_OF_RESOURCES
;
440 Called when compression is completed to free memory previously allocated.
491 Initialize String Info Log data structures
501 for (i
= WNDSIZ
; i
<= WNDSIZ
+ UINT8_MAX
; i
++) {
503 mPosition
[i
] = NIL
; /* sentinel */
505 for (i
= WNDSIZ
; i
< WNDSIZ
* 2; i
++) {
509 for (i
= 1; i
< WNDSIZ
- 1; i
++) {
510 mNext
[i
] = (NODE
)(i
+ 1);
513 mNext
[WNDSIZ
- 1] = NIL
;
514 for (i
= WNDSIZ
* 2; i
<= MAX_HASH_VAL
; i
++) {
530 Find child node given the parent node and the edge character
535 c - the edge character
539 The child node (NIL if not found)
545 r
= mNext
[HASH(q
, c
)];
546 mParent
[NIL
] = q
; /* sentinel */
547 while (mParent
[r
] != q
) {
565 Create a new child for a given parent node.
570 c - the edge character
579 h
= (NODE
)HASH(q
, c
);
602 Old - the node to split
612 mChildCount
[New
] = 0;
619 mParent
[New
] = mParent
[Old
];
620 mLevel
[New
] = (UINT8
)mMatchLen
;
621 mPosition
[New
] = mPos
;
622 MakeChild(New
, mText
[mMatchPos
+ mMatchLen
], Old
);
623 MakeChild(New
, mText
[mPos
+ mMatchLen
], mPos
);
633 Insert string info for current position into the String Info Log
644 if (mMatchLen
>= 4) {
647 // We have just got a long match, the target tree
648 // can be located by MatchPos + 1. Travese the tree
649 // from bottom up to get to a proper starting point.
650 // The usage of PERC_FLAG ensures proper node deletion
651 // in DeleteNode() later.
655 r
= (INT16
)((mMatchPos
+ 1) | WNDSIZ
);
656 while ((q
= mParent
[r
]) == NIL
) {
659 while (mLevel
[q
] >= mMatchLen
) {
660 r
= q
; q
= mParent
[q
];
663 while (mPosition
[t
] < 0) {
668 mPosition
[t
] = (NODE
)(mPos
| PERC_FLAG
);
673 // Locate the target tree
676 q
= (INT16
)(mText
[mPos
] + WNDSIZ
);
678 if ((r
= Child(q
, c
)) == NIL
) {
679 MakeChild(q
, c
, mPos
);
687 // Traverse down the tree to find a match.
688 // Update Position value along the route.
689 // Node split or creation is involved.
698 mMatchPos
= (NODE
)(mPosition
[r
] & ~PERC_FLAG
);
700 if (mMatchPos
>= mPos
) {
703 t1
= &mText
[mPos
+ mMatchLen
];
704 t2
= &mText
[mMatchPos
+ mMatchLen
];
705 while (mMatchLen
< j
) {
714 if (mMatchLen
>= MAXMATCH
) {
719 if ((r
= Child(q
, *t1
)) == NIL
) {
720 MakeChild(q
, *t1
, mPos
);
735 // Special usage of 'next'
748 Delete outdated string info. (The Usage of PERC_FLAG
749 ensures a clean deletion)
759 if (mParent
[mPos
] == NIL
) {
769 if (r
>= WNDSIZ
|| --mChildCount
[r
] > 1) {
772 t
= (NODE
)(mPosition
[r
] & ~PERC_FLAG
);
778 while ((u
= mPosition
[q
]) & PERC_FLAG
) {
786 mPosition
[q
] = (INT16
)(s
| WNDSIZ
);
796 mPosition
[q
] = (INT16
)(s
| WNDSIZ
| PERC_FLAG
);
798 s
= Child(r
, mText
[t
+ mLevel
[r
]]);
809 mParent
[s
] = mParent
[r
];
822 Advance the current position (read in new data if needed).
823 Delete outdated string info. Find a match string for current position.
834 if (++mPos
== WNDSIZ
* 2) {
835 memmove(&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
836 n
= FreadCrc(&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
851 The main controlling routine for compression process.
857 EFI_SUCCESS - The compression is successful
858 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
866 Status
= AllocateMemory();
867 if (EFI_ERROR(Status
)) {
876 mRemainder
= FreadCrc(&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
881 if (mMatchLen
> mRemainder
) {
882 mMatchLen
= mRemainder
;
884 while (mRemainder
> 0) {
885 LastMatchLen
= mMatchLen
;
886 LastMatchPos
= mMatchPos
;
888 if (mMatchLen
> mRemainder
) {
889 mMatchLen
= mRemainder
;
892 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
895 // Not enough benefits are gained by outputting a pointer,
896 // so just output the original character
899 Output(mText
[mPos
- 1], 0);
903 // Outputting a pointer is beneficial enough, do it.
906 Output(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
907 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
908 while (--LastMatchLen
> 0) {
911 if (mMatchLen
> mRemainder
) {
912 mMatchLen
= mRemainder
;
929 Count the frequencies for the Extra Set
937 INT32 i
, k
, n
, Count
;
939 for (i
= 0; i
< NT
; i
++) {
943 while (n
> 0 && mCLen
[n
- 1] == 0) {
951 while (i
< n
&& mCLen
[i
] == 0) {
956 mTFreq
[0] = (UINT16
)(mTFreq
[0] + Count
);
957 } else if (Count
<= 18) {
959 } else if (Count
== 19) {
982 Outputs the code length array for the Extra Set or the Position Set.
986 n - the number of symbols
987 nbit - the number of bits needed to represent 'n'
988 Special - the special symbol that needs to be take care of
996 while (n
> 0 && mPTLen
[n
- 1] == 0) {
1006 PutBits(k
- 3, (1U << (k
- 3)) - 2);
1009 while (i
< 6 && mPTLen
[i
] == 0) {
1012 PutBits(2, (i
- 3) & 3);
1022 Routine Description:
1024 Outputs the code length array for Char&Length Set
1032 INT32 i
, k
, n
, Count
;
1035 while (n
> 0 && mCLen
[n
- 1] == 0) {
1044 while (i
< n
&& mCLen
[i
] == 0) {
1049 for (k
= 0; k
< Count
; k
++) {
1050 PutBits(mPTLen
[0], mPTCode
[0]);
1052 } else if (Count
<= 18) {
1053 PutBits(mPTLen
[1], mPTCode
[1]);
1054 PutBits(4, Count
- 3);
1055 } else if (Count
== 19) {
1056 PutBits(mPTLen
[0], mPTCode
[0]);
1057 PutBits(mPTLen
[1], mPTCode
[1]);
1060 PutBits(mPTLen
[2], mPTCode
[2]);
1061 PutBits(CBIT
, Count
- 20);
1064 PutBits(mPTLen
[k
+ 2], mPTCode
[k
+ 2]);
1075 PutBits(mCLen
[c
], mCCode
[c
]);
1092 PutBits(mPTLen
[c
], mPTCode
[c
]);
1094 PutBits(c
- 1, p
& (0xFFFFU
>> (17 - c
)));
1103 Routine Description:
1105 Huffman code the block and output it.
1113 UINT32 i
, k
, Flags
, Root
, Pos
, Size
;
1116 Root
= MakeTree(NC
, mCFreq
, mCLen
, mCCode
);
1117 Size
= mCFreq
[Root
];
1121 Root
= MakeTree(NT
, mTFreq
, mPTLen
, mPTCode
);
1123 WritePTLen(NT
, TBIT
, 3);
1126 PutBits(TBIT
, Root
);
1133 PutBits(CBIT
, Root
);
1135 Root
= MakeTree(NP
, mPFreq
, mPTLen
, mPTCode
);
1137 WritePTLen(NP
, PBIT
, -1);
1140 PutBits(PBIT
, Root
);
1143 for (i
= 0; i
< Size
; i
++) {
1144 if (i
% UINT8_BIT
== 0) {
1145 Flags
= mBuf
[Pos
++];
1149 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1150 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1151 k
= mBuf
[Pos
++] << UINT8_BIT
;
1155 EncodeC(mBuf
[Pos
++]);
1158 for (i
= 0; i
< NC
; i
++) {
1161 for (i
= 0; i
< NP
; i
++) {
1175 Routine Description:
1177 Outputs an Original Character or a Pointer
1181 c - The original character or the 'String Length' element of a Pointer
1182 p - The 'Position' field of a Pointer
1190 if ((mOutputMask
>>= 1) == 0) {
1191 mOutputMask
= 1U << (UINT8_BIT
- 1);
1192 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1196 CPos
= mOutputPos
++;
1199 mBuf
[mOutputPos
++] = (UINT8
) c
;
1201 if (c
>= (1U << UINT8_BIT
)) {
1202 mBuf
[CPos
] |= mOutputMask
;
1203 mBuf
[mOutputPos
++] = (UINT8
)(p
>> UINT8_BIT
);
1204 mBuf
[mOutputPos
++] = (UINT8
) p
;
1220 for (i
= 0; i
< NC
; i
++) {
1223 for (i
= 0; i
< NP
; i
++) {
1226 mOutputPos
= mOutputMask
= 0;
1238 // Flush remaining bits
1240 PutBits(UINT8_BIT
- 1, 0);
1252 for (i
= 0; i
<= UINT8_MAX
; i
++) {
1254 for (j
= 0; j
< UINT8_BIT
; j
++) {
1256 r
= (r
>> 1) ^ CRCPOLY
;
1261 mCrcTable
[i
] = (UINT16
)r
;
1273 Routine Description:
1275 Outputs rightmost n bits of x
1279 n - the rightmost n bits of the data is used
1288 if (n
< mBitCount
) {
1289 mSubBitBuf
|= x
<< (mBitCount
-= n
);
1292 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (n
-= mBitCount
)));
1293 if (mDst
< mDstUpperLimit
) {
1298 if (n
< UINT8_BIT
) {
1299 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- n
);
1302 Temp
= (UINT8
)(x
>> (n
- UINT8_BIT
));
1303 if (mDst
< mDstUpperLimit
) {
1308 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- n
);
1321 Routine Description:
1327 p - the buffer to hold the data
1328 n - number of bytes to read
1332 number of bytes actually read
1338 for (i
= 0; mSrc
< mSrcUpperLimit
&& i
< n
; i
++) {
1356 mBitCount
= UINT8_BIT
;
1367 Routine Description:
1369 Count the number of each code length for a Huffman tree.
1379 STATIC INT32 Depth
= 0;
1382 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1385 CountLen(mLeft
[i
]);
1386 CountLen(mRight
[i
]);
1398 Routine Description:
1400 Create code length array for a Huffman tree
1404 Root - the root of the tree
1411 for (i
= 0; i
<= 16; i
++) {
1417 // Adjust the length count array so that
1418 // no code will be generated longer than its designated length
1422 for (i
= 16; i
> 0; i
--) {
1423 Cum
+= mLenCnt
[i
] << (16 - i
);
1425 while (Cum
!= (1U << 16)) {
1427 for (i
= 15; i
> 0; i
--) {
1428 if (mLenCnt
[i
] != 0) {
1436 for (i
= 16; i
> 0; i
--) {
1439 mLen
[*mSortPtr
++] = (UINT8
)i
;
1453 // priority queue: send i-th entry down heap
1457 while ((j
= 2 * i
) <= mHeapSize
) {
1458 if (j
< mHeapSize
&& mFreq
[mHeap
[j
]] > mFreq
[mHeap
[j
+ 1]]) {
1461 if (mFreq
[k
] <= mFreq
[mHeap
[j
]]) {
1464 mHeap
[i
] = mHeap
[j
];
1467 mHeap
[i
] = (INT16
)k
;
1479 Routine Description:
1481 Assign code to each symbol based on the code length array
1485 n - number of symbols
1486 Len - the code length array
1487 Code - stores codes for each symbol
1497 for (i
= 1; i
<= 16; i
++) {
1498 Start
[i
+ 1] = (UINT16
)((Start
[i
] + mLenCnt
[i
]) << 1);
1500 for (i
= 0; i
< n
; i
++) {
1501 Code
[i
] = Start
[Len
[i
]]++;
1509 IN UINT16 FreqParm
[],
1510 OUT UINT8 LenParm
[],
1511 OUT UINT16 CodeParm
[]
1515 Routine Description:
1517 Generates Huffman codes given a frequency distribution of symbols
1521 NParm - number of symbols
1522 FreqParm - frequency of each symbol
1523 LenParm - code length for each symbol
1524 CodeParm - code for each symbol
1528 Root of the Huffman tree.
1532 INT32 i
, j
, k
, Avail
;
1535 // make tree, calculate len[], return root
1544 for (i
= 0; i
< mN
; i
++) {
1547 mHeap
[++mHeapSize
] = (INT16
)i
;
1550 if (mHeapSize
< 2) {
1551 CodeParm
[mHeap
[1]] = 0;
1554 for (i
= mHeapSize
/ 2; i
>= 1; i
--) {
1557 // make priority queue
1561 mSortPtr
= CodeParm
;
1565 *mSortPtr
++ = (UINT16
)i
;
1567 mHeap
[1] = mHeap
[mHeapSize
--];
1571 *mSortPtr
++ = (UINT16
)j
;
1574 mFreq
[k
] = (UINT16
)(mFreq
[i
] + mFreq
[j
]);
1575 mHeap
[1] = (INT16
)k
;
1577 mLeft
[k
] = (UINT16
)i
;
1578 mRight
[k
] = (UINT16
)j
;
1579 } while (mHeapSize
> 1);
1581 mSortPtr
= CodeParm
;
1583 MakeCode(NParm
, LenParm
, CodeParm
);