]>
git.proxmox.com Git - mirror_edk2.git/blob - ShellPkg/Library/UefiShellDebug1CommandsLib/Compress.c
2 Main file for compression routine.
4 Compression routine. The compression algorithm is a mixture of
5 LZ77 and Huffman coding. LZ77 transforms the source data into a
6 sequence of Original Characters and Pointers to repeated strings.
7 This sequence is further divided into Blocks and Huffman codings
8 are applied to each Block.
10 Copyright (c) 2007 - 2010, Intel Corporation. All rights reserved.<BR>
11 This program and the accompanying materials
12 are licensed and made available under the terms and conditions of the BSD License
13 which accompanies this distribution. The full text of the license may be found at
14 http://opensource.org/licenses/bsd-license.php
16 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
17 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
21 #include <Library/MemoryAllocationLib.h>
22 #include <Library/BaseMemoryLib.h>
23 #include <Library/DebugLib.h>
24 #include <ShellBase.h>
30 #define UINT8_MAX 0xff
35 #define WNDSIZ (1U << WNDBIT)
37 #define BLKSIZ (1U << 14) // 16 * 1024U
38 #define PERC_FLAG 0x8000U
41 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
42 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
43 #define CRCPOLY 0xA001
44 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
47 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
49 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
51 #define NP (WNDBIT + 1)
53 #define NT (CODE_BIT + 3)
61 // Function Prototypes
65 Put a dword to output stream
67 @param[in] Data The dword to put.
251 IN UINT16 FreqParm
[ ],
252 OUT UINT8 LenParm
[ ],
253 OUT UINT16 CodeParm
[ ]
259 STATIC UINT8
*mSrc
, *mDst
, *mSrcUpperLimit
, *mDstUpperLimit
;
261 STATIC UINT8
*mLevel
, *mText
, *mChildCount
, *mBuf
, mCLen
[NC
], mPTLen
[NPT
], *mLen
;
262 STATIC INT16 mHeap
[NC
+ 1];
263 STATIC INT32 mRemainder
, mMatchLen
, mBitCount
, mHeapSize
, mN
;
264 STATIC UINT32 mBufSiz
= 0, mOutputPos
, mOutputMask
, mSubBitBuf
, mCrc
;
265 STATIC UINT32 mCompSize
, mOrigSize
;
267 STATIC UINT16
*mFreq
, *mSortPtr
, mLenCnt
[17], mLeft
[2 * NC
- 1], mRight
[2 * NC
- 1],
268 mCrcTable
[UINT8_MAX
+ 1], mCFreq
[2 * NC
- 1], mCTable
[4096], mCCode
[NC
],
269 mPFreq
[2 * NP
- 1], mPTCode
[NPT
], mTFreq
[2 * NT
- 1];
271 STATIC NODE mPos
, mMatchPos
, mAvail
, *mPosition
, *mParent
, *mPrev
, *mNext
= NULL
;
277 The compression routine.
279 @param[in] SrcBuffer The buffer containing the source data.
280 @param[in] SrcSizae Number of bytes in SrcBuffer.
281 @param[in] DstBuffer The buffer to put the compressed image in.
282 @param[in,out] DstSize On input the size (in bytes) of DstBuffer, on
283 return the number of bytes placed in DstBuffer.
285 @retval EFI_SUCCESS The compression was sucessful.
286 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
294 IN OUT UINT64
*DstSize
313 mSrcUpperLimit
= mSrc
+ SrcSize
;
315 mDstUpperLimit
= mDst
+*DstSize
;
322 mOrigSize
= mCompSize
= 0;
329 if (EFI_ERROR (Status
)) {
330 return EFI_OUT_OF_RESOURCES
;
333 // Null terminate the compressed data
335 if (mDst
< mDstUpperLimit
) {
339 // Fill in compressed size and original size
342 PutDword (mCompSize
+ 1);
343 PutDword (mOrigSize
);
348 if (mCompSize
+ 1 + 8 > *DstSize
) {
349 *DstSize
= mCompSize
+ 1 + 8;
350 return EFI_BUFFER_TOO_SMALL
;
352 *DstSize
= mCompSize
+ 1 + 8;
359 Put a dword to output stream
361 @param[in] Data The dword to put.
369 if (mDst
< mDstUpperLimit
) {
370 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
373 if (mDst
< mDstUpperLimit
) {
374 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
377 if (mDst
< mDstUpperLimit
) {
378 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
381 if (mDst
< mDstUpperLimit
) {
382 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
395 Allocate memory spaces for data structures used in compression process
403 EFI_SUCCESS - Memory is allocated successfully
404 EFI_OUT_OF_RESOURCES - Allocation fails
408 mText
= AllocateZeroPool (WNDSIZ
* 2 + MAXMATCH
);
409 mLevel
= AllocatePool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
410 mChildCount
= AllocatePool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
411 mPosition
= AllocatePool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
412 mParent
= AllocatePool (WNDSIZ
* 2 * sizeof (*mParent
));
413 mPrev
= AllocatePool (WNDSIZ
* 2 * sizeof (*mPrev
));
414 mNext
= AllocatePool ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
417 mBuf
= AllocatePool (mBufSiz
);
418 while (mBuf
== NULL
) {
419 mBufSiz
= (mBufSiz
/ 10U) * 9U;
420 if (mBufSiz
< 4 * 1024U) {
421 return EFI_OUT_OF_RESOURCES
;
424 mBuf
= AllocatePool (mBufSiz
);
441 Called when compression is completed to free memory previously allocated.
449 SHELL_FREE_NON_NULL (mText
);
450 SHELL_FREE_NON_NULL (mLevel
);
451 SHELL_FREE_NON_NULL (mChildCount
);
452 SHELL_FREE_NON_NULL (mPosition
);
453 SHELL_FREE_NON_NULL (mParent
);
454 SHELL_FREE_NON_NULL (mPrev
);
455 SHELL_FREE_NON_NULL (mNext
);
456 SHELL_FREE_NON_NULL (mBuf
);
468 Initialize String Info Log data structures
478 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
479 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
481 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
484 for (i
= 1; i
< WNDSIZ
- 1; i
++) {
485 mNext
[i
] = (NODE
) (i
+ 1);
488 mNext
[WNDSIZ
- 1] = NIL
;
489 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
502 Find child node given the parent node and the edge character
507 c - the edge character
511 The child node (NIL if not found)
517 r
= mNext
[HASH (q
, c
)];
518 mParent
[NIL
] = q
; /* sentinel */
519 while (mParent
[r
] != q
) {
537 Create a new child for a given parent node.
542 c - the edge character
553 h
= (NODE
) HASH (q
, c
);
576 Old - the node to split
588 mChildCount
[New
] = 0;
595 mParent
[New
] = mParent
[Old
];
596 mLevel
[New
] = (UINT8
) mMatchLen
;
597 mPosition
[New
] = mPos
;
598 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
599 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
611 Insert string info for current position into the String Info Log
630 if (mMatchLen
>= 4) {
632 // We have just got a long match, the target tree
633 // can be located by MatchPos + 1. Travese the tree
634 // from bottom up to get to a proper starting point.
635 // The usage of PERC_FLAG ensures proper node deletion
636 // in DeleteNode() later.
639 r
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
646 while (mLevel
[q
] >= mMatchLen
) {
652 while (mPosition
[t
] < 0) {
658 mPosition
[t
] = (NODE
) (mPos
| PERC_FLAG
);
662 // Locate the target tree
664 q
= (NODE
) (mText
[mPos
] + WNDSIZ
);
668 MakeChild (q
, c
, mPos
);
676 // Traverse down the tree to find a match.
677 // Update Position value along the route.
678 // Node split or creation is involved.
686 mMatchPos
= (NODE
) (mPosition
[r
] & ~PERC_FLAG
);
689 if (mMatchPos
>= mPos
) {
693 t1
= &mText
[mPos
+ mMatchLen
];
694 t2
= &mText
[mMatchPos
+ mMatchLen
];
695 while (mMatchLen
< j
) {
706 if (mMatchLen
>= MAXMATCH
) {
714 MakeChild (q
, *t1
, mPos
);
731 // Special usage of 'next'
746 Delete outdated string info. (The Usage of PERC_FLAG
747 ensures a clean deletion)
765 if (mParent
[mPos
] == NIL
) {
780 if (mChildCount
[r
] > 1) {
784 t
= (NODE
) (mPosition
[r
] & ~PERC_FLAG
);
792 while ((u
& PERC_FLAG
) != 0){
802 mPosition
[q
] = (NODE
) (s
| WNDSIZ
);
816 mPosition
[q
] = (NODE
) (s
| WNDSIZ
| PERC_FLAG
);
819 s
= Child (r
, mText
[t
+ mLevel
[r
]]);
830 mParent
[s
] = mParent
[r
];
845 Advance the current position (read in new data if needed).
846 Delete outdated string info. Find a match string for current position.
859 if (mPos
== WNDSIZ
* 2) {
860 Temp
= AllocatePool (WNDSIZ
+ MAXMATCH
);
861 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
862 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
864 n
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
882 The main controlling routine for compression process.
888 EFI_SUCCESS - The compression is successful
889 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
897 Status
= AllocateMemory ();
898 if (EFI_ERROR (Status
)) {
907 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
912 if (mMatchLen
> mRemainder
) {
913 mMatchLen
= mRemainder
;
916 while (mRemainder
> 0) {
917 LastMatchLen
= mMatchLen
;
918 LastMatchPos
= mMatchPos
;
920 if (mMatchLen
> mRemainder
) {
921 mMatchLen
= mRemainder
;
924 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
926 // Not enough benefits are gained by outputting a pointer,
927 // so just output the original character
929 CompressOutput(mText
[mPos
- 1], 0);
932 // Outputting a pointer is beneficial enough, do it.
935 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
936 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
938 while (LastMatchLen
> 0) {
943 if (mMatchLen
> mRemainder
) {
944 mMatchLen
= mRemainder
;
963 Count the frequencies for the Extra Set
979 for (i
= 0; i
< NT
; i
++) {
984 while (n
> 0 && mCLen
[n
- 1] == 0) {
993 while (i
< n
&& mCLen
[i
] == 0) {
999 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
1000 } else if (Count
<= 18) {
1002 } else if (Count
== 19) {
1009 ASSERT((k
+2)<(2 * NT
- 1));
1024 Routine Description:
1026 Outputs the code length array for the Extra Set or the Position Set.
1030 n - the number of symbols
1031 nbit - the number of bits needed to represent 'n'
1032 Special - the special symbol that needs to be take care of
1042 while (n
> 0 && mPTLen
[n
- 1] == 0) {
1053 PutBits (k
- 3, (1U << (k
- 3)) - 2);
1057 while (i
< 6 && mPTLen
[i
] == 0) {
1061 PutBits (2, (i
- 3) & 3);
1073 Routine Description:
1075 Outputs the code length array for Char&Length Set
1092 while (n
> 0 && mCLen
[n
- 1] == 0) {
1102 while (i
< n
&& mCLen
[i
] == 0) {
1108 for (k
= 0; k
< Count
; k
++) {
1109 PutBits (mPTLen
[0], mPTCode
[0]);
1111 } else if (Count
<= 18) {
1112 PutBits (mPTLen
[1], mPTCode
[1]);
1113 PutBits (4, Count
- 3);
1114 } else if (Count
== 19) {
1115 PutBits (mPTLen
[0], mPTCode
[0]);
1116 PutBits (mPTLen
[1], mPTCode
[1]);
1119 PutBits (mPTLen
[2], mPTCode
[2]);
1120 PutBits (CBIT
, Count
- 20);
1124 PutBits (mPTLen
[k
+ 2], mPTCode
[k
+ 2]);
1135 PutBits (mCLen
[c
], mCCode
[c
]);
1155 PutBits (mPTLen
[c
], mPTCode
[c
]);
1157 PutBits(c
- 1, p
& (0xFFFFU
>> (17 - c
)));
1168 Routine Description:
1170 Huffman code the block and output it.
1195 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1196 Size
= mCFreq
[Root
];
1200 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1202 WritePTLen (NT
, TBIT
, 3);
1205 PutBits (TBIT
, Root
);
1213 PutBits (CBIT
, Root
);
1216 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1218 WritePTLen (NP
, PBIT
, -1);
1221 PutBits (PBIT
, Root
);
1225 for (i
= 0; i
< Size
; i
++) {
1226 if (i
% UINT8_BIT
== 0) {
1227 Flags
= mBuf
[Pos
++];
1231 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1232 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1233 k
= mBuf
[Pos
++] << UINT8_BIT
;
1238 EncodeC (mBuf
[Pos
++]);
1242 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1243 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1254 Routine Description:
1256 Outputs an Original Character or a Pointer
1260 c - The original character or the 'String Length' element of a Pointer
1261 p - The 'Position' field of a Pointer
1269 if ((mOutputMask
>>= 1) == 0) {
1270 mOutputMask
= 1U << (UINT8_BIT
- 1);
1271 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1276 CPos
= mOutputPos
++;
1279 mBuf
[mOutputPos
++] = (UINT8
) c
;
1281 if (c
>= (1U << UINT8_BIT
)) {
1282 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1283 mBuf
[mOutputPos
++] = (UINT8
)(p
>> UINT8_BIT
);
1284 mBuf
[mOutputPos
++] = (UINT8
) p
;
1300 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1301 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1303 mOutputPos
= mOutputMask
= 0;
1317 // Flush remaining bits
1319 PutBits (UINT8_BIT
- 1, 0);
1336 for (i
= 0; i
<= UINT8_MAX
; i
++) {
1338 for (j
= 0; j
< UINT8_BIT
; j
++) {
1340 r
= (r
>> 1) ^ CRCPOLY
;
1346 mCrcTable
[i
] = (UINT16
) r
;
1358 Routine Description:
1360 Outputs rightmost n bits of x
1364 n - the rightmost n bits of the data is used
1375 if (n
< mBitCount
) {
1376 mSubBitBuf
|= x
<< (mBitCount
-= n
);
1379 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (n
-= mBitCount
)));
1380 if (mDst
< mDstUpperLimit
) {
1385 if (n
< UINT8_BIT
) {
1386 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- n
);
1389 Temp
= (UINT8
)(x
>> (n
- UINT8_BIT
));
1390 if (mDst
< mDstUpperLimit
) {
1395 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- n
);
1408 Routine Description:
1414 p - the buffer to hold the data
1415 n - number of bytes to read
1419 number of bytes actually read
1425 for (i
= 0; mSrc
< mSrcUpperLimit
&& i
< n
; i
++) {
1448 mBitCount
= UINT8_BIT
;
1459 Routine Description:
1461 Count the number of each code length for a Huffman tree.
1471 STATIC INT32 Depth
= 0;
1474 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1477 CountLen (mLeft
[i
]);
1478 CountLen (mRight
[i
]);
1490 Routine Description:
1492 Create code length array for a Huffman tree
1496 Root - the root of the tree
1509 for (i
= 0; i
<= 16; i
++) {
1516 // Adjust the length count array so that
1517 // no code will be generated longer than its designated length
1520 for (i
= 16; i
> 0; i
--) {
1521 Cum
+= mLenCnt
[i
] << (16 - i
);
1524 while (Cum
!= (1U << 16)) {
1526 for (i
= 15; i
> 0; i
--) {
1527 if (mLenCnt
[i
] != 0) {
1529 mLenCnt
[i
+ 1] += 2;
1537 for (i
= 16; i
> 0; i
--) {
1541 mLen
[*mSortPtr
++] = (UINT8
) i
;
1558 // priority queue: send i-th entry down heap
1562 while (j
<= mHeapSize
) {
1563 if (j
< mHeapSize
&& mFreq
[mHeap
[j
]] > mFreq
[mHeap
[j
+ 1]]) {
1567 if (mFreq
[k
] <= mFreq
[mHeap
[j
]]) {
1571 mHeap
[i
] = mHeap
[j
];
1576 mHeap
[i
] = (INT16
) k
;
1588 Routine Description:
1590 Assign code to each symbol based on the code length array
1594 n - number of symbols
1595 Len - the code length array
1596 Code - stores codes for each symbol
1608 for (i
= 1; i
<= 16; i
++) {
1609 Start
[i
+ 1] = (UINT16
) ((Start
[i
] + mLenCnt
[i
]) << 1);
1612 for (i
= 0; i
< n
; i
++) {
1613 Code
[i
] = Start
[Len
[i
]]++;
1621 IN UINT16 FreqParm
[ ],
1622 OUT UINT8 LenParm
[ ],
1623 OUT UINT16 CodeParm
[ ]
1627 Routine Description:
1629 Generates Huffman codes given a frequency distribution of symbols
1633 NParm - number of symbols
1634 FreqParm - frequency of each symbol
1635 LenParm - code length for each symbol
1636 CodeParm - code for each symbol
1640 Root of the Huffman tree.
1653 // make tree, calculate len[], return root
1661 for (i
= 0; i
< mN
; i
++) {
1663 if ((mFreq
[i
]) != 0) {
1665 mHeap
[mHeapSize
] = (INT16
) i
;
1669 if (mHeapSize
< 2) {
1670 CodeParm
[mHeap
[1]] = 0;
1674 for (i
= mHeapSize
/ 2; i
>= 1; i
--) {
1676 // make priority queue
1681 mSortPtr
= CodeParm
;
1685 *mSortPtr
++ = (UINT16
) i
;
1688 mHeap
[1] = mHeap
[mHeapSize
--];
1692 *mSortPtr
++ = (UINT16
) j
;
1696 mFreq
[k
] = (UINT16
) (mFreq
[i
] + mFreq
[j
]);
1697 mHeap
[1] = (INT16
) k
;
1699 mLeft
[k
] = (UINT16
) i
;
1700 mRight
[k
] = (UINT16
) j
;
1701 } while (mHeapSize
> 1);
1703 mSortPtr
= CodeParm
;
1705 MakeCode (NParm
, LenParm
, CodeParm
);