]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/TianoCompress/TianoCompress.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.
5 This sequence is further divided into Blocks and Huffman codings are applied to
8 Copyright (c) 2007 - 2016, Intel Corporation. All rights reserved.<BR>
9 This program and the accompanying materials
10 are licensed and made available under the terms and conditions of the BSD License
11 which accompanies this distribution. The full text of the license may be found at
12 http://opensource.org/licenses/bsd-license.php
14 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
15 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
20 #include "TianoCompress.h"
21 #include "EfiUtilityMsgs.h"
29 static BOOLEAN VerboseMode
= FALSE
;
30 static BOOLEAN QuietMode
= FALSE
;
32 #define UINT8_MAX 0xff
37 #define WNDSIZ (1U << WNDBIT)
39 #define BLKSIZ (1U << 14) // 16 * 1024U
40 #define PERC_FLAG 0x80000000U
43 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
44 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
45 #define CRCPOLY 0xA001
46 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
49 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
51 //#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
53 #define NP (WNDBIT + 1)
55 //#define NT (CODE_BIT + 3)
66 STATIC BOOLEAN ENCODE
= FALSE
;
67 STATIC BOOLEAN DECODE
= FALSE
;
68 STATIC UINT8
*mSrc
, *mDst
, *mSrcUpperLimit
, *mDstUpperLimit
;
69 STATIC UINT8
*mLevel
, *mText
, *mChildCount
, *mBuf
, mCLen
[NC
], mPTLen
[NPT
], *mLen
;
70 STATIC INT16 mHeap
[NC
+ 1];
71 STATIC INT32 mRemainder
, mMatchLen
, mBitCount
, mHeapSize
, mN
;
72 STATIC UINT32 mBufSiz
= 0, mOutputPos
, mOutputMask
, mSubBitBuf
, mCrc
;
73 STATIC UINT32 mCompSize
, mOrigSize
;
75 STATIC UINT16
*mFreq
, *mSortPtr
, mLenCnt
[17], mLeft
[2 * NC
- 1], mRight
[2 * NC
- 1], mCrcTable
[UINT8_MAX
+ 1],
76 mCFreq
[2 * NC
- 1], mCCode
[NC
], mPFreq
[2 * NP
- 1], mPTCode
[NPT
], mTFreq
[2 * NT
- 1];
78 STATIC NODE mPos
, mMatchPos
, mAvail
, *mPosition
, *mParent
, *mPrev
, *mNext
= NULL
;
80 static UINT64 DebugLevel
;
81 static BOOLEAN DebugMode
;
90 IN OUT UINT32
*DstSize
96 The internal implementation of [Efi/Tiano]Compress().
100 SrcBuffer - The buffer storing the source data
101 SrcSize - The size of source data
102 DstBuffer - The buffer to store the compressed data
104 Version - The version of de/compression algorithm.
105 Version 1 for EFI 1.1 de/compression algorithm.
106 Version 2 for Tiano de/compression algorithm.
110 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
111 DstSize contains the size needed.
112 EFI_SUCCESS - Compression is successful.
113 EFI_OUT_OF_RESOURCES - No resource to complete function.
114 EFI_INVALID_PARAMETER - Parameter supplied is wrong.
135 mSrcUpperLimit
= mSrc
+ SrcSize
;
137 mDstUpperLimit
= mDst
+*DstSize
;
144 mOrigSize
= mCompSize
= 0;
151 if (EFI_ERROR (Status
)) {
152 return EFI_OUT_OF_RESOURCES
;
156 // Null terminate the compressed data
159 if (mDst
< mDstUpperLimit
) {
164 // Fill in compressed size and original size
168 PutDword (mCompSize
+ 1);
169 PutDword (mOrigSize
);
174 if (mCompSize
+ 1 + 8 > *DstSize
) {
175 *DstSize
= mCompSize
+ 1 + 8;
176 return EFI_BUFFER_TOO_SMALL
;
178 *DstSize
= mCompSize
+ 1 + 8;
192 Put a dword to output stream
196 Data - the dword to put
202 if (mDst
< mDstUpperLimit
) {
203 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
206 if (mDst
< mDstUpperLimit
) {
207 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
210 if (mDst
< mDstUpperLimit
) {
211 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
214 if (mDst
< mDstUpperLimit
) {
215 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
228 Allocate memory spaces for data structures used in compression process
235 EFI_SUCCESS - Memory is allocated successfully
236 EFI_OUT_OF_RESOURCES - Allocation fails
242 mText
= malloc (WNDSIZ
* 2 + MAXMATCH
);
244 Error (NULL
, 0, 4001, "Resource", "memory cannot be allocated!");
245 return EFI_OUT_OF_RESOURCES
;
247 for (Index
= 0; Index
< WNDSIZ
* 2 + MAXMATCH
; Index
++) {
251 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
252 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
253 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
254 mParent
= malloc (WNDSIZ
* 2 * sizeof (*mParent
));
255 mPrev
= malloc (WNDSIZ
* 2 * sizeof (*mPrev
));
256 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
257 if (mLevel
== NULL
|| mChildCount
== NULL
|| mPosition
== NULL
||
258 mParent
== NULL
|| mPrev
== NULL
|| mNext
== NULL
) {
259 Error (NULL
, 0, 4001, "Resource", "memory cannot be allocated!");
260 return EFI_OUT_OF_RESOURCES
;
264 mBuf
= malloc (mBufSiz
);
265 while (mBuf
== NULL
) {
266 mBufSiz
= (mBufSiz
/ 10U) * 9U;
267 if (mBufSiz
< 4 * 1024U) {
268 return EFI_OUT_OF_RESOURCES
;
271 mBuf
= malloc (mBufSiz
);
287 Called when compression is completed to free memory previously allocated.
299 if (mLevel
!= NULL
) {
303 if (mChildCount
!= NULL
) {
307 if (mPosition
!= NULL
) {
311 if (mParent
!= NULL
) {
339 Initialize String Info Log data structures
349 for (Index
= WNDSIZ
; Index
<= WNDSIZ
+ UINT8_MAX
; Index
++) {
351 mPosition
[Index
] = NIL
; // sentinel
354 for (Index
= WNDSIZ
; Index
< WNDSIZ
* 2; Index
++) {
355 mParent
[Index
] = NIL
;
359 for (Index
= 1; Index
< WNDSIZ
- 1; Index
++) {
360 mNext
[Index
] = (NODE
) (Index
+ 1);
363 mNext
[WNDSIZ
- 1] = NIL
;
364 for (Index
= WNDSIZ
* 2; Index
<= MAX_HASH_VAL
; Index
++) {
379 Find child node given the parent node and the edge character
383 NodeQ - the parent node
384 CharC - the edge character
388 The child node (NIL if not found)
394 NodeR
= mNext
[HASH (NodeQ
, CharC
)];
398 mParent
[NIL
] = NodeQ
;
399 while (mParent
[NodeR
] != NodeQ
) {
400 NodeR
= mNext
[NodeR
];
417 Create a new child for a given parent node.
421 Parent - the parent node
422 CharC - the edge character
423 Child - the child node
432 Node1
= (NODE
) HASH (Parent
, CharC
);
433 Node2
= mNext
[Node1
];
434 mNext
[Node1
] = Child
;
435 mNext
[Child
] = Node2
;
436 mPrev
[Node2
] = Child
;
437 mPrev
[Child
] = Node1
;
438 mParent
[Child
] = Parent
;
439 mChildCount
[Parent
]++;
455 Old - the node to split
466 mChildCount
[New
] = 0;
467 TempNode
= mPrev
[Old
];
468 mPrev
[New
] = TempNode
;
469 mNext
[TempNode
] = New
;
470 TempNode
= mNext
[Old
];
471 mNext
[New
] = TempNode
;
472 mPrev
[TempNode
] = New
;
473 mParent
[New
] = mParent
[Old
];
474 mLevel
[New
] = (UINT8
) mMatchLen
;
475 mPosition
[New
] = mPos
;
476 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
477 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
489 Insert string info for current position into the String Info Log
505 if (mMatchLen
>= 4) {
507 // We have just got a long match, the target tree
508 // can be located by MatchPos + 1. Travese the tree
509 // from bottom up to get to a proper starting point.
510 // The usage of PERC_FLAG ensures proper node deletion
511 // in DeleteNode() later.
514 NodeR
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
515 NodeQ
= mParent
[NodeR
];
516 while (NodeQ
== NIL
) {
517 NodeR
= mNext
[NodeR
];
518 NodeQ
= mParent
[NodeR
];
521 while (mLevel
[NodeQ
] >= mMatchLen
) {
523 NodeQ
= mParent
[NodeQ
];
527 while (mPosition
[NodeT
] < 0) {
528 mPosition
[NodeT
] = mPos
;
529 NodeT
= mParent
[NodeT
];
532 if (NodeT
< WNDSIZ
) {
533 mPosition
[NodeT
] = (NODE
) (mPos
| (UINT32
) PERC_FLAG
);
537 // Locate the target tree
539 NodeQ
= (NODE
) (mText
[mPos
] + WNDSIZ
);
540 CharC
= mText
[mPos
+ 1];
541 NodeR
= Child (NodeQ
, CharC
);
543 MakeChild (NodeQ
, CharC
, mPos
);
551 // Traverse down the tree to find a match.
552 // Update Position value along the route.
553 // Node split or creation is involved.
556 if (NodeR
>= WNDSIZ
) {
560 Index2
= mLevel
[NodeR
];
561 mMatchPos
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
564 if (mMatchPos
>= mPos
) {
568 t1
= &mText
[mPos
+ mMatchLen
];
569 t2
= &mText
[mMatchPos
+ mMatchLen
];
570 while (mMatchLen
< Index2
) {
581 if (mMatchLen
>= MAXMATCH
) {
585 mPosition
[NodeR
] = mPos
;
587 NodeR
= Child (NodeQ
, *t1
);
589 MakeChild (NodeQ
, *t1
, mPos
);
596 NodeT
= mPrev
[NodeR
];
599 NodeT
= mNext
[NodeR
];
602 mParent
[mPos
] = NodeQ
;
603 mParent
[NodeR
] = NIL
;
606 // Special usage of 'next'
621 Delete outdated string info. (The Usage of PERC_FLAG
622 ensures a clean deletion)
636 if (mParent
[mPos
] == NIL
) {
642 mNext
[NodeR
] = NodeS
;
643 mPrev
[NodeS
] = NodeR
;
644 NodeR
= mParent
[mPos
];
646 if (NodeR
>= WNDSIZ
) {
650 mChildCount
[NodeR
]--;
651 if (mChildCount
[NodeR
] > 1) {
655 NodeT
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
661 NodeQ
= mParent
[NodeR
];
662 NodeU
= mPosition
[NodeQ
];
663 while (NodeU
& (UINT32
) PERC_FLAG
) {
664 NodeU
&= (UINT32
)~PERC_FLAG
;
673 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
);
674 NodeQ
= mParent
[NodeQ
];
675 NodeU
= mPosition
[NodeQ
];
678 if (NodeQ
< WNDSIZ
) {
687 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
| (UINT32
) PERC_FLAG
);
690 NodeS
= Child (NodeR
, mText
[NodeT
+ mLevel
[NodeR
]]);
691 NodeT
= mPrev
[NodeS
];
692 NodeU
= mNext
[NodeS
];
693 mNext
[NodeT
] = NodeU
;
694 mPrev
[NodeU
] = NodeT
;
695 NodeT
= mPrev
[NodeR
];
696 mNext
[NodeT
] = NodeS
;
697 mPrev
[NodeS
] = NodeT
;
698 NodeT
= mNext
[NodeR
];
699 mPrev
[NodeT
] = NodeS
;
700 mNext
[NodeS
] = NodeT
;
701 mParent
[NodeS
] = mParent
[NodeR
];
702 mParent
[NodeR
] = NIL
;
703 mNext
[NodeR
] = mAvail
;
716 Advance the current position (read in new data if needed).
717 Delete outdated string info. Find a match string for current position.
729 if (mPos
== WNDSIZ
* 2) {
730 memmove (&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
731 Number
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
732 mRemainder
+= Number
;
749 The main controlling routine for compression process.
755 EFI_SUCCESS - The compression is successful
756 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
764 Status
= AllocateMemory ();
765 if (EFI_ERROR (Status
)) {
774 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
779 if (mMatchLen
> mRemainder
) {
780 mMatchLen
= mRemainder
;
783 while (mRemainder
> 0) {
784 LastMatchLen
= mMatchLen
;
785 LastMatchPos
= mMatchPos
;
787 if (mMatchLen
> mRemainder
) {
788 mMatchLen
= mRemainder
;
791 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
793 // Not enough benefits are gained by outputting a pointer,
794 // so just output the original character
796 Output (mText
[mPos
- 1], 0);
800 if (LastMatchLen
== THRESHOLD
) {
801 if (((mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)) > (1U << 11)) {
802 Output (mText
[mPos
- 1], 0);
807 // Outputting a pointer is beneficial enough, do it.
810 LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
811 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)
814 while (LastMatchLen
> 0) {
819 if (mMatchLen
> mRemainder
) {
820 mMatchLen
= mRemainder
;
839 Count the frequencies for the Extra Set
852 for (Index
= 0; Index
< NT
; Index
++) {
857 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
862 while (Index
< Number
) {
863 Index3
= mCLen
[Index
++];
866 while (Index
< Number
&& mCLen
[Index
] == 0) {
872 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
873 } else if (Count
<= 18) {
875 } else if (Count
== 19) {
882 mTFreq
[Index3
+ 2]++;
898 Outputs the code length array for the Extra Set or the Position Set.
902 Number - the number of symbols
903 nbit - the number of bits needed to represent 'n'
904 Special - the special symbol that needs to be take care of
913 while (Number
> 0 && mPTLen
[Number
- 1] == 0) {
917 PutBits (nbit
, Number
);
919 while (Index
< Number
) {
920 Index3
= mPTLen
[Index
++];
924 PutBits (Index3
- 3, (1U << (Index3
- 3)) - 2);
927 if (Index
== Special
) {
928 while (Index
< 6 && mPTLen
[Index
] == 0) {
932 PutBits (2, (Index
- 3) & 3);
946 Outputs the code length array for Char&Length Set
960 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
964 PutBits (CBIT
, Number
);
966 while (Index
< Number
) {
967 Index3
= mCLen
[Index
++];
970 while (Index
< Number
&& mCLen
[Index
] == 0) {
976 for (Index3
= 0; Index3
< Count
; Index3
++) {
977 PutBits (mPTLen
[0], mPTCode
[0]);
979 } else if (Count
<= 18) {
980 PutBits (mPTLen
[1], mPTCode
[1]);
981 PutBits (4, Count
- 3);
982 } else if (Count
== 19) {
983 PutBits (mPTLen
[0], mPTCode
[0]);
984 PutBits (mPTLen
[1], mPTCode
[1]);
987 PutBits (mPTLen
[2], mPTCode
[2]);
988 PutBits (CBIT
, Count
- 20);
991 PutBits (mPTLen
[Index3
+ 2], mPTCode
[Index3
+ 2]);
1002 PutBits (mCLen
[Value
], mCCode
[Value
]);
1021 PutBits (mPTLen
[Index
], mPTCode
[Index
]);
1023 PutBits (Index
- 1, Value
& (0xFFFFFFFFU
>> (32 - Index
+ 1)));
1034 Routine Description:
1036 Huffman code the block and output it.
1055 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1056 Size
= mCFreq
[Root
];
1061 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1063 WritePTLen (NT
, TBIT
, 3);
1066 PutBits (TBIT
, Root
);
1074 PutBits (CBIT
, Root
);
1077 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1079 WritePTLen (NP
, PBIT
, -1);
1082 PutBits (PBIT
, Root
);
1086 for (Index
= 0; Index
< Size
; Index
++) {
1087 if (Index
% UINT8_BIT
== 0) {
1088 Flags
= mBuf
[Pos
++];
1093 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1094 EncodeC (mBuf
[Pos
++] + (1U << UINT8_BIT
));
1095 Index3
= mBuf
[Pos
++];
1096 for (Index2
= 0; Index2
< 3; Index2
++) {
1097 Index3
<<= UINT8_BIT
;
1098 Index3
+= mBuf
[Pos
++];
1103 EncodeC (mBuf
[Pos
++]);
1107 for (Index
= 0; Index
< NC
; Index
++) {
1111 for (Index
= 0; Index
< NP
; Index
++) {
1124 Routine Description:
1126 Outputs an Original Character or a Pointer
1130 CharC - The original character or the 'String Length' element of a Pointer
1131 Pos - The 'Position' field of a Pointer
1139 if ((mOutputMask
>>= 1) == 0) {
1140 mOutputMask
= 1U << (UINT8_BIT
- 1);
1142 // Check the buffer overflow per outputing UINT8_BIT symbols
1143 // which is an Original Character or a Pointer. The biggest
1144 // symbol is a Pointer which occupies 5 bytes.
1146 if (mOutputPos
>= mBufSiz
- 5 * UINT8_BIT
) {
1151 CPos
= mOutputPos
++;
1155 mBuf
[mOutputPos
++] = (UINT8
) CharC
;
1157 if (CharC
>= (1U << UINT8_BIT
)) {
1158 mBuf
[CPos
] |= mOutputMask
;
1159 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 24);
1160 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 16);
1161 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> (UINT8_BIT
));
1162 mBuf
[mOutputPos
++] = (UINT8
) Pos
;
1181 for (Index
= 0; Index
< NC
; Index
++) {
1185 for (Index
= 0; Index
< NP
; Index
++) {
1189 mOutputPos
= mOutputMask
= 0;
1203 // Flush remaining bits
1205 PutBits (UINT8_BIT
- 1, 0);
1220 for (Index
= 0; Index
<= UINT8_MAX
; Index
++) {
1222 for (Index2
= 0; Index2
< UINT8_BIT
; Index2
++) {
1224 Temp
= (Temp
>> 1) ^ CRCPOLY
;
1230 mCrcTable
[Index
] = (UINT16
) Temp
;
1242 Routine Description:
1244 Outputs rightmost n bits of x
1248 Number - the rightmost n bits of the data is used
1257 while (Number
>= mBitCount
) {
1259 // Number -= mBitCount should never equal to 32
1261 Temp
= (UINT8
) (mSubBitBuf
| (Value
>> (Number
-= mBitCount
)));
1263 if (mDst
< mDstUpperLimit
) {
1269 mBitCount
= UINT8_BIT
;
1272 mSubBitBuf
|= Value
<< (mBitCount
-= Number
);
1283 Routine Description:
1289 Pointer - the buffer to hold the data
1290 Number - number of bytes to read
1294 number of bytes actually read
1300 for (Index
= 0; mSrc
< mSrcUpperLimit
&& Index
< Number
; Index
++) {
1301 *Pointer
++ = *mSrc
++;
1307 mOrigSize
+= Number
;
1310 while (Index
>= 0) {
1311 UPDATE_CRC (*Pointer
++);
1324 mBitCount
= UINT8_BIT
;
1335 Routine Description:
1337 Count the number of each code length for a Huffman tree.
1341 Index - the top node
1347 STATIC INT32 Depth
= 0;
1350 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1353 CountLen (mLeft
[Index
]);
1354 CountLen (mRight
[Index
]);
1366 Routine Description:
1368 Create code length array for a Huffman tree
1372 Root - the root of the tree
1384 for (Index
= 0; Index
<= 16; Index
++) {
1391 // Adjust the length count array so that
1392 // no code will be generated longer than its designated length
1395 for (Index
= 16; Index
> 0; Index
--) {
1396 Cum
+= mLenCnt
[Index
] << (16 - Index
);
1399 while (Cum
!= (1U << 16)) {
1401 for (Index
= 15; Index
> 0; Index
--) {
1402 if (mLenCnt
[Index
] != 0) {
1404 mLenCnt
[Index
+ 1] += 2;
1412 for (Index
= 16; Index
> 0; Index
--) {
1413 Index3
= mLenCnt
[Index
];
1415 while (Index3
>= 0) {
1416 mLen
[*mSortPtr
++] = (UINT8
) Index
;
1432 // priority queue: send Index-th entry down heap
1434 Index3
= mHeap
[Index
];
1436 while (Index2
<= mHeapSize
) {
1437 if (Index2
< mHeapSize
&& mFreq
[mHeap
[Index2
]] > mFreq
[mHeap
[Index2
+ 1]]) {
1441 if (mFreq
[Index3
] <= mFreq
[mHeap
[Index2
]]) {
1445 mHeap
[Index
] = mHeap
[Index2
];
1450 mHeap
[Index
] = (INT16
) Index3
;
1462 Routine Description:
1464 Assign code to each symbol based on the code length array
1468 Number - number of symbols
1469 Len - the code length array
1470 Code - stores codes for each symbol
1480 for (Index
= 1; Index
<= 16; Index
++) {
1481 Start
[Index
+ 1] = (UINT16
) ((Start
[Index
] + mLenCnt
[Index
]) << 1);
1484 for (Index
= 0; Index
< Number
; Index
++) {
1485 Code
[Index
] = Start
[Len
[Index
]]++;
1493 IN UINT16 FreqParm
[],
1494 OUT UINT8 LenParm
[ ],
1495 OUT UINT16 CodeParm
[]
1499 Routine Description:
1501 Generates Huffman codes given a frequency distribution of symbols
1505 NParm - number of symbols
1506 FreqParm - frequency of each symbol
1507 LenParm - code length for each symbol
1508 CodeParm - code for each symbol
1512 Root of the Huffman tree.
1522 // make tree, calculate len[], return root
1530 for (Index
= 0; Index
< mN
; Index
++) {
1534 mHeap
[mHeapSize
] = (INT16
) Index
;
1538 if (mHeapSize
< 2) {
1539 CodeParm
[mHeap
[1]] = 0;
1543 for (Index
= mHeapSize
/ 2; Index
>= 1; Index
--) {
1545 // make priority queue
1550 mSortPtr
= CodeParm
;
1554 *mSortPtr
++ = (UINT16
) Index
;
1557 mHeap
[1] = mHeap
[mHeapSize
--];
1561 *mSortPtr
++ = (UINT16
) Index2
;
1565 mFreq
[Index3
] = (UINT16
) (mFreq
[Index
] + mFreq
[Index2
]);
1566 mHeap
[1] = (INT16
) Index3
;
1568 mLeft
[Index3
] = (UINT16
) Index
;
1569 mRight
[Index3
] = (UINT16
) Index2
;
1570 } while (mHeapSize
> 1);
1572 mSortPtr
= CodeParm
;
1574 MakeCode (NParm
, LenParm
, CodeParm
);
1584 IN
char *InputFileName
,
1585 OUT UINT8
*FileBuffer
,
1586 OUT UINT32
*BufferLength
1590 Routine Description:
1592 Get the contents of file specified in InputFileName
1597 InputFileName - Name of the input file.
1599 FileBuffer - Output buffer to contain data
1601 BufferLength - Actual length of the data
1605 EFI_SUCCESS on successful return
1606 EFI_ABORTED if unable to open input file.
1616 // Copy the file contents to the output buffer.
1618 InputFile
= fopen (LongFilePath (InputFileName
), "rb");
1619 if (InputFile
== NULL
) {
1620 Error (NULL
, 0, 0001, "Error opening file: %s", InputFileName
);
1624 fseek (InputFile
, 0, SEEK_END
);
1625 FileSize
= ftell (InputFile
);
1626 fseek (InputFile
, 0, SEEK_SET
);
1628 // Now read the contents of the file into the buffer
1630 if (FileSize
> 0 && FileBuffer
!= NULL
) {
1631 if (fread (FileBuffer
, FileSize
, 1, InputFile
) != 1) {
1632 Error (NULL
, 0, 0004, "Error reading contents of input file: %s", InputFileName
);
1639 Size
+= (UINTN
) FileSize
;
1640 *BufferLength
= Size
;
1642 if (FileBuffer
!= NULL
) {
1645 return EFI_BUFFER_TOO_SMALL
;
1655 Routine Description:
1657 Displays the standard utility information to SDTOUT
1669 fprintf (stdout
, "%s Version %d.%d %s \n", UTILITY_NAME
, UTILITY_MAJOR_VERSION
, UTILITY_MINOR_VERSION
, __BUILD_VERSION
);
1678 Routine Description:
1680 Displays the utility usage syntax to STDOUT
1695 fprintf (stdout
, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME
);
1698 // Copyright declaration
1700 fprintf (stdout
, "Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.\n\n");
1705 fprintf (stdout
, "Options:\n");
1706 fprintf (stdout
, " -o FileName, --output FileName\n\
1707 File will be created to store the ouput content.\n");
1708 fprintf (stdout
, " -v, --verbose\n\
1709 Turn on verbose output with informational messages.\n");
1710 fprintf (stdout
, " -q, --quiet\n\
1711 Disable all messages except key message and fatal error\n");
1712 fprintf (stdout
, " --debug [0-9]\n\
1713 Enable debug messages, at input debug level.\n");
1714 fprintf (stdout
, " --version\n\
1715 Show program's version number and exit.\n");
1716 fprintf (stdout
, " -h, --help\n\
1717 Show this help message and exit.\n");
1728 Routine Description:
1734 command line parameters
1738 EFI_SUCCESS Section header successfully generated and section concatenated.
1739 EFI_ABORTED Could not generate the section
1740 EFI_OUT_OF_RESOURCES No resource to complete the operation.
1745 char *OutputFileName
;
1746 char *InputFileName
;
1753 SCRATCH_DATA
*Scratch
;
1757 SetUtilityName(UTILITY_NAME
);
1765 InputFileName
= NULL
;
1766 OutputFileName
= NULL
;
1772 // Verify the correct number of arguments
1775 Error (NULL
, 0, 1001, "Missing options", "No input options specified.");
1780 if ((strcmp(argv
[1], "-h") == 0) || (strcmp(argv
[1], "--help") == 0)) {
1785 if ((strcmp(argv
[1], "--version") == 0)) {
1792 if (strcmp(argv
[0],"-e") == 0) {
1794 // encode the input file
1799 } else if (strcmp(argv
[0], "-d") == 0) {
1801 // decode the input file
1808 // Error command line
1810 Error (NULL
, 0, 1003, "Invalid option value", "the options specified are not recognized.");
1816 if ((strcmp(argv
[0], "-v") == 0) || (stricmp(argv
[0], "--verbose") == 0)) {
1823 if (stricmp (argv
[0], "--debug") == 0) {
1826 Status
= AsciiStringToUint64(argv
[0], FALSE
, &DebugLevel
);
1827 if (DebugLevel
> 9) {
1828 Error (NULL
, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv
[0]);
1831 if (DebugLevel
>=5 && DebugLevel
<=9){
1840 if ((strcmp(argv
[0], "-q") == 0) || (stricmp (argv
[0], "--quiet") == 0)) {
1847 if ((strcmp(argv
[0], "-o") == 0) || (stricmp (argv
[0], "--output") == 0)) {
1848 if (argv
[1] == NULL
|| argv
[1][0] == '-') {
1849 Error (NULL
, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
1852 OutputFileName
= argv
[1];
1858 if (argv
[0][0]!='-') {
1859 InputFileName
= argv
[0];
1865 Error (NULL
, 0, 1000, "Unknown option", argv
[0]);
1869 if (InputFileName
== NULL
) {
1870 Error (NULL
, 0, 1001, "Missing options", "No input files specified.");
1875 // All Parameters has been parsed, now set the message print level
1879 } else if (VerboseMode
) {
1881 } else if (DebugMode
) {
1882 SetPrintLevel(DebugLevel
);
1886 VerboseMsg("%s tool start.\n", UTILITY_NAME
);
1888 Scratch
= (SCRATCH_DATA
*)malloc(sizeof(SCRATCH_DATA
));
1889 if (Scratch
== NULL
) {
1890 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1894 InputFile
= fopen (LongFilePath (InputFileName
), "rb");
1895 if (InputFile
== NULL
) {
1896 Error (NULL
, 0, 0001, "Error opening input file", InputFileName
);
1900 Status
= GetFileContents(
1905 if (Status
== EFI_BUFFER_TOO_SMALL
) {
1906 FileBuffer
= (UINT8
*) malloc (InputLength
);
1907 if (FileBuffer
== NULL
) {
1908 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1912 Status
= GetFileContents (
1919 if (EFI_ERROR(Status
)) {
1924 if (OutputFileName
== NULL
) {
1925 OutputFileName
= DEFAULT_OUTPUT_FILE
;
1927 OutputFile
= fopen (LongFilePath (OutputFileName
), "wb");
1928 if (OutputFile
== NULL
) {
1929 Error (NULL
, 0, 0001, "Error opening output file for writing", OutputFileName
);
1930 if (InputFile
!= NULL
) {
1938 // First call TianoCompress to get DstSize
1941 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding", NULL
);
1943 Status
= TianoCompress ((UINT8
*)FileBuffer
, InputLength
, OutBuffer
, &DstSize
);
1945 if (Status
== EFI_BUFFER_TOO_SMALL
) {
1946 OutBuffer
= (UINT8
*) malloc (DstSize
);
1947 if (OutBuffer
== NULL
) {
1948 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1953 Status
= TianoCompress ((UINT8
*)FileBuffer
, InputLength
, OutBuffer
, &DstSize
);
1954 if (Status
!= EFI_SUCCESS
) {
1955 Error (NULL
, 0, 0007, "Error compressing file", NULL
);
1959 if (OutBuffer
== NULL
) {
1960 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1964 fwrite(OutBuffer
,(size_t)DstSize
, 1, OutputFile
);
1970 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding Successful!\n", NULL
);
1973 VerboseMsg("Encoding successful\n");
1979 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Decoding\n", NULL
);
1982 // Get Compressed file original size
1984 Src
= (UINT8
*)FileBuffer
;
1985 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
1988 // Allocate OutputBuffer
1990 OutBuffer
= (UINT8
*)malloc(OrigSize
);
1991 if (OutBuffer
== NULL
) {
1992 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1996 Status
= Decompress((VOID
*)FileBuffer
, (VOID
*)OutBuffer
, (VOID
*)Scratch
, 2);
1997 if (Status
!= EFI_SUCCESS
) {
2001 fwrite(OutBuffer
, (size_t)(Scratch
->mOrigSize
), 1, OutputFile
);
2007 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding successful!\n", NULL
);
2011 VerboseMsg("Decoding successful\n");
2019 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding Error\n", NULL
);
2020 } else if (DECODE
) {
2021 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Decoding Error\n", NULL
);
2024 if (Scratch
!= NULL
) {
2027 if (FileBuffer
!= NULL
) {
2030 if (OutBuffer
!= NULL
) {
2035 VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME
, GetUtilityStatus ());
2037 return GetUtilityStatus ();
2042 IN SCRATCH_DATA
*Sd
,
2047 Routine Description:
2049 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
2053 Sd - The global scratch data
2054 NumOfBits - The number of bits to shift and read.
2060 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
2062 while (NumOfBits
> Sd
->mBitCount
) {
2064 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
2066 if (Sd
->mCompSize
> 0) {
2068 // Get 1 byte into SubBitBuf
2072 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
2077 // No more bits from the source, just pad zero bit.
2085 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
2086 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
2091 IN SCRATCH_DATA
*Sd
,
2096 Routine Description:
2098 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
2099 NumOfBits of bits from source. Returns NumOfBits of bits that are
2104 Sd - The global scratch data.
2105 NumOfBits - The number of bits to pop and read.
2109 The bits that are popped out.
2115 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
2117 FillBuf (Sd
, NumOfBits
);
2124 IN SCRATCH_DATA
*Sd
,
2125 IN UINT16 NumOfChar
,
2127 IN UINT16 TableBits
,
2132 Routine Description:
2134 Creates Huffman Code mapping table according to code length array.
2138 Sd - The global scratch data
2139 NumOfChar - Number of symbols in the symbol set
2140 BitLen - Code length array
2141 TableBits - The width of the mapping table
2147 BAD_TABLE - The table is corrupted.
2156 volatile UINT16 Index
;
2166 for (Index
= 1; Index
<= 16; Index
++) {
2170 for (Index
= 0; Index
< NumOfChar
; Index
++) {
2171 Count
[BitLen
[Index
]]++;
2176 for (Index
= 1; Index
<= 16; Index
++) {
2177 WordOfStart
= Start
[Index
];
2178 WordOfCount
= Count
[Index
];
2179 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
2182 if (Start
[17] != 0) {
2186 return (UINT16
) BAD_TABLE
;
2189 JuBits
= (UINT16
) (16 - TableBits
);
2191 for (Index
= 1; Index
<= TableBits
; Index
++) {
2192 Start
[Index
] >>= JuBits
;
2193 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
2196 while (Index
<= 16) {
2197 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
2201 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
2204 Index3
= (UINT16
) (1U << TableBits
);
2205 while (Index
!= Index3
) {
2211 Mask
= (UINT16
) (1U << (15 - TableBits
));
2213 for (Char
= 0; Char
< NumOfChar
; Char
++) {
2220 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
2222 if (Len
<= TableBits
) {
2224 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
2225 Table
[Index
] = Char
;
2230 Index3
= Start
[Len
];
2231 Pointer
= &Table
[Index3
>> JuBits
];
2232 Index
= (UINT16
) (Len
- TableBits
);
2234 while (Index
!= 0) {
2235 if (*Pointer
== 0) {
2236 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
2240 if (Index3
& Mask
) {
2241 Pointer
= &Sd
->mRight
[*Pointer
];
2243 Pointer
= &Sd
->mLeft
[*Pointer
];
2254 Start
[Len
] = NextCode
;
2268 Routine Description:
2270 Decodes a position value.
2274 Sd - the global scratch data
2278 The position value decoded.
2286 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2289 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2293 if (Sd
->mBitBuf
& Mask
) {
2294 Val
= Sd
->mRight
[Val
];
2296 Val
= Sd
->mLeft
[Val
];
2300 } while (Val
>= MAXNP
);
2303 // Advance what we have read
2305 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
2309 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
2317 IN SCRATCH_DATA
*Sd
,
2324 Routine Description:
2326 Reads code lengths for the Extra Set or the Position Set
2330 Sd - The global scratch data
2331 nn - Number of symbols
2332 nbit - Number of bits needed to represent nn
2333 Special - The special symbol that needs to be taken care of
2338 BAD_TABLE - Table is corrupted.
2344 volatile UINT16 Index
;
2347 Number
= (UINT16
) GetBits (Sd
, nbit
);
2350 CharC
= (UINT16
) GetBits (Sd
, nbit
);
2352 for (Index
= 0; Index
< 256; Index
++) {
2353 Sd
->mPTTable
[Index
] = CharC
;
2356 for (Index
= 0; Index
< nn
; Index
++) {
2357 Sd
->mPTLen
[Index
] = 0;
2365 while (Index
< Number
) {
2367 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
2370 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
2371 while (Mask
& Sd
->mBitBuf
) {
2377 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
2379 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
2381 if (Index
== Special
) {
2382 CharC
= (UINT16
) GetBits (Sd
, 2);
2383 while ((INT16
) (--CharC
) >= 0) {
2384 Sd
->mPTLen
[Index
++] = 0;
2389 while (Index
< nn
) {
2390 Sd
->mPTLen
[Index
++] = 0;
2393 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
2402 Routine Description:
2404 Reads code lengths for Char&Len Set.
2408 Sd - the global scratch data
2416 volatile UINT16 Index
;
2419 Number
= (UINT16
) GetBits (Sd
, CBIT
);
2422 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
2424 for (Index
= 0; Index
< NC
; Index
++) {
2425 Sd
->mCLen
[Index
] = 0;
2428 for (Index
= 0; Index
< 4096; Index
++) {
2429 Sd
->mCTable
[Index
] = CharC
;
2436 while (Index
< Number
) {
2438 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2440 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2444 if (Mask
& Sd
->mBitBuf
) {
2445 CharC
= Sd
->mRight
[CharC
];
2447 CharC
= Sd
->mLeft
[CharC
];
2452 } while (CharC
>= NT
);
2455 // Advance what we have read
2457 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
2463 } else if (CharC
== 1) {
2464 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
2465 } else if (CharC
== 2) {
2466 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
2469 while ((INT16
) (--CharC
) >= 0) {
2470 Sd
->mCLen
[Index
++] = 0;
2475 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
2480 while (Index
< NC
) {
2481 Sd
->mCLen
[Index
++] = 0;
2484 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
2495 Routine Description:
2497 Decode a character/length value.
2501 Sd - The global scratch data.
2512 if (Sd
->mBlockSize
== 0) {
2514 // Starting a new block
2516 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
2517 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
2518 if (Sd
->mBadTableFlag
!= 0) {
2524 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
2525 if (Sd
->mBadTableFlag
!= 0) {
2531 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
2534 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
2537 if (Sd
->mBitBuf
& Mask
) {
2538 Index2
= Sd
->mRight
[Index2
];
2540 Index2
= Sd
->mLeft
[Index2
];
2544 } while (Index2
>= NC
);
2547 // Advance what we have read
2549 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
2560 Routine Description:
2562 Decode the source data and put the resulting data into the destination buffer.
2566 Sd - The global scratch data
2576 BytesRemain
= (UINT16
) (-1);
2581 CharC
= DecodeC (Sd
);
2582 if (Sd
->mBadTableFlag
!= 0) {
2588 // Process an Original character
2590 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2593 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
2598 // Process a Pointer
2600 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
2602 BytesRemain
= CharC
;
2604 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
2607 while ((INT16
) (BytesRemain
) >= 0) {
2608 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
2609 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2626 IN OUT VOID
*Destination
,
2627 IN OUT VOID
*Scratch
,
2632 Routine Description:
2634 The internal implementation of Decompress().
2638 Source - The source buffer containing the compressed data.
2639 Destination - The destination buffer to store the decompressed data
2640 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
2641 Version - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2645 RETURN_SUCCESS - Decompression is successfull
2646 RETURN_INVALID_PARAMETER - The source data is corrupted
2650 volatile UINT32 Index
;
2658 // Verify input is not NULL
2661 // assert(Destination);
2664 Src
= (UINT8
*)Source
;
2665 Dst
= (UINT8
*)Destination
;
2667 Sd
= (SCRATCH_DATA
*) Scratch
;
2668 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
2669 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
2672 // If compressed file size is 0, return
2674 if (OrigSize
== 0) {
2675 return RETURN_SUCCESS
;
2680 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
2681 ((UINT8
*) Sd
)[Index
] = 0;
2684 // The length of the field 'Position Set Code Length Array Size' in Block Header.
2685 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2686 // For Tiano de/compression algorithm(Version 2), mPBit = 5
2698 Sd
->mSrcBase
= (UINT8
*)Src
;
2700 Sd
->mCompSize
= CompSize
;
2701 Sd
->mOrigSize
= OrigSize
;
2704 // Fill the first BITBUFSIZ bits
2706 FillBuf (Sd
, BITBUFSIZ
);
2714 if (Sd
->mBadTableFlag
!= 0) {
2716 // Something wrong with the source
2718 return RETURN_INVALID_PARAMETER
;
2721 return RETURN_SUCCESS
;