]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/TianoCompress/TianoCompress.c
93cb6c3ac31427f1de6e6f4c4c3c32618f708f76
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.
2166 for (Index
= 0; Index
<= 16; Index
++) {
2170 for (Index
= 0; Index
< NumOfChar
; Index
++) {
2171 Count
[BitLen
[Index
]]++;
2177 for (Index
= 1; Index
<= 16; Index
++) {
2178 WordOfStart
= Start
[Index
];
2179 WordOfCount
= Count
[Index
];
2180 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
2183 if (Start
[17] != 0) {
2187 return (UINT16
) BAD_TABLE
;
2190 JuBits
= (UINT16
) (16 - TableBits
);
2193 for (Index
= 1; Index
<= TableBits
; Index
++) {
2194 Start
[Index
] >>= JuBits
;
2195 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
2198 while (Index
<= 16) {
2199 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
2203 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
2206 Index3
= (UINT16
) (1U << TableBits
);
2207 while (Index
!= Index3
) {
2213 Mask
= (UINT16
) (1U << (15 - TableBits
));
2215 for (Char
= 0; Char
< NumOfChar
; Char
++) {
2218 if (Len
== 0 || Len
>= 17) {
2222 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
2224 if (Len
<= TableBits
) {
2226 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
2227 Table
[Index
] = Char
;
2232 Index3
= Start
[Len
];
2233 Pointer
= &Table
[Index3
>> JuBits
];
2234 Index
= (UINT16
) (Len
- TableBits
);
2236 while (Index
!= 0) {
2237 if (*Pointer
== 0) {
2238 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
2242 if (Index3
& Mask
) {
2243 Pointer
= &Sd
->mRight
[*Pointer
];
2245 Pointer
= &Sd
->mLeft
[*Pointer
];
2256 Start
[Len
] = NextCode
;
2270 Routine Description:
2272 Decodes a position value.
2276 Sd - the global scratch data
2280 The position value decoded.
2288 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2291 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2295 if (Sd
->mBitBuf
& Mask
) {
2296 Val
= Sd
->mRight
[Val
];
2298 Val
= Sd
->mLeft
[Val
];
2302 } while (Val
>= MAXNP
);
2305 // Advance what we have read
2307 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
2311 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
2319 IN SCRATCH_DATA
*Sd
,
2326 Routine Description:
2328 Reads code lengths for the Extra Set or the Position Set
2332 Sd - The global scratch data
2333 nn - Number of symbols
2334 nbit - Number of bits needed to represent nn
2335 Special - The special symbol that needs to be taken care of
2340 BAD_TABLE - Table is corrupted.
2346 volatile UINT16 Index
;
2351 Number
= (UINT16
) GetBits (Sd
, nbit
);
2354 CharC
= (UINT16
) GetBits (Sd
, nbit
);
2356 for (Index
= 0; Index
< 256; Index
++) {
2357 Sd
->mPTTable
[Index
] = CharC
;
2360 for (Index
= 0; Index
< nn
; Index
++) {
2361 Sd
->mPTLen
[Index
] = 0;
2369 while (Index
< Number
) {
2371 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
2374 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
2375 while (Mask
& Sd
->mBitBuf
) {
2381 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
2383 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
2385 if (Index
== Special
) {
2386 CharC
= (UINT16
) GetBits (Sd
, 2);
2387 while ((INT16
) (--CharC
) >= 0) {
2388 Sd
->mPTLen
[Index
++] = 0;
2393 while (Index
< nn
) {
2394 Sd
->mPTLen
[Index
++] = 0;
2397 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
2406 Routine Description:
2408 Reads code lengths for Char&Len Set.
2412 Sd - the global scratch data
2420 volatile UINT16 Index
;
2423 Number
= (UINT16
) GetBits (Sd
, CBIT
);
2426 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
2428 for (Index
= 0; Index
< NC
; Index
++) {
2429 Sd
->mCLen
[Index
] = 0;
2432 for (Index
= 0; Index
< 4096; Index
++) {
2433 Sd
->mCTable
[Index
] = CharC
;
2440 while (Index
< Number
) {
2442 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2444 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2448 if (Mask
& Sd
->mBitBuf
) {
2449 CharC
= Sd
->mRight
[CharC
];
2451 CharC
= Sd
->mLeft
[CharC
];
2456 } while (CharC
>= NT
);
2459 // Advance what we have read
2461 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
2467 } else if (CharC
== 1) {
2468 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
2469 } else if (CharC
== 2) {
2470 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
2473 while ((INT16
) (--CharC
) >= 0) {
2474 Sd
->mCLen
[Index
++] = 0;
2479 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
2484 while (Index
< NC
) {
2485 Sd
->mCLen
[Index
++] = 0;
2488 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
2499 Routine Description:
2501 Decode a character/length value.
2505 Sd - The global scratch data.
2516 if (Sd
->mBlockSize
== 0) {
2518 // Starting a new block
2520 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
2521 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
2522 if (Sd
->mBadTableFlag
!= 0) {
2528 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
2529 if (Sd
->mBadTableFlag
!= 0) {
2535 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
2538 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
2541 if (Sd
->mBitBuf
& Mask
) {
2542 Index2
= Sd
->mRight
[Index2
];
2544 Index2
= Sd
->mLeft
[Index2
];
2548 } while (Index2
>= NC
);
2551 // Advance what we have read
2553 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
2564 Routine Description:
2566 Decode the source data and put the resulting data into the destination buffer.
2570 Sd - The global scratch data
2580 BytesRemain
= (UINT16
) (-1);
2585 CharC
= DecodeC (Sd
);
2586 if (Sd
->mBadTableFlag
!= 0) {
2592 // Process an Original character
2594 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2597 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
2602 // Process a Pointer
2604 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
2606 BytesRemain
= CharC
;
2608 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
2611 while ((INT16
) (BytesRemain
) >= 0) {
2612 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
2613 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2630 IN OUT VOID
*Destination
,
2631 IN OUT VOID
*Scratch
,
2636 Routine Description:
2638 The internal implementation of Decompress().
2642 Source - The source buffer containing the compressed data.
2643 Destination - The destination buffer to store the decompressed data
2644 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
2645 Version - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2649 RETURN_SUCCESS - Decompression is successfull
2650 RETURN_INVALID_PARAMETER - The source data is corrupted
2654 volatile UINT32 Index
;
2662 // Verify input is not NULL
2665 // assert(Destination);
2668 Src
= (UINT8
*)Source
;
2669 Dst
= (UINT8
*)Destination
;
2671 Sd
= (SCRATCH_DATA
*) Scratch
;
2672 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
2673 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
2676 // If compressed file size is 0, return
2678 if (OrigSize
== 0) {
2679 return RETURN_SUCCESS
;
2684 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
2685 ((UINT8
*) Sd
)[Index
] = 0;
2688 // The length of the field 'Position Set Code Length Array Size' in Block Header.
2689 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2690 // For Tiano de/compression algorithm(Version 2), mPBit = 5
2702 Sd
->mSrcBase
= (UINT8
*)Src
;
2704 Sd
->mCompSize
= CompSize
;
2705 Sd
->mOrigSize
= OrigSize
;
2708 // Fill the first BITBUFSIZ bits
2710 FillBuf (Sd
, BITBUFSIZ
);
2718 if (Sd
->mBadTableFlag
!= 0) {
2720 // Something wrong with the source
2722 return RETURN_INVALID_PARAMETER
;
2725 return RETURN_SUCCESS
;