]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/TianoCompress/TianoCompress.c
f810511f5f2f9a57c57bec78b4e9c63a06f9ac50
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
;
1774 // Verify the correct number of arguments
1777 Error (NULL
, 0, 1001, "Missing options", "No input options specified.");
1782 if ((strcmp(argv
[1], "-h") == 0) || (strcmp(argv
[1], "--help") == 0)) {
1787 if ((strcmp(argv
[1], "--version") == 0)) {
1794 if (strcmp(argv
[0],"-e") == 0) {
1796 // encode the input file
1801 } else if (strcmp(argv
[0], "-d") == 0) {
1803 // decode the input file
1810 // Error command line
1812 Error (NULL
, 0, 1003, "Invalid option value", "the options specified are not recognized.");
1818 if ((strcmp(argv
[0], "-v") == 0) || (stricmp(argv
[0], "--verbose") == 0)) {
1825 if (stricmp (argv
[0], "--debug") == 0) {
1828 Status
= AsciiStringToUint64(argv
[0], FALSE
, &DebugLevel
);
1829 if (DebugLevel
> 9) {
1830 Error (NULL
, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv
[0]);
1833 if (DebugLevel
>=5 && DebugLevel
<=9){
1842 if ((strcmp(argv
[0], "-q") == 0) || (stricmp (argv
[0], "--quiet") == 0)) {
1849 if ((strcmp(argv
[0], "-o") == 0) || (stricmp (argv
[0], "--output") == 0)) {
1850 if (argv
[1] == NULL
|| argv
[1][0] == '-') {
1851 Error (NULL
, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
1854 OutputFileName
= argv
[1];
1860 if (argv
[0][0]!='-') {
1861 InputFileName
= argv
[0];
1867 Error (NULL
, 0, 1000, "Unknown option", argv
[0]);
1871 if (InputFileName
== NULL
) {
1872 Error (NULL
, 0, 1001, "Missing options", "No input files specified.");
1877 // All Parameters has been parsed, now set the message print level
1881 } else if (VerboseMode
) {
1883 } else if (DebugMode
) {
1884 SetPrintLevel(DebugLevel
);
1888 VerboseMsg("%s tool start.\n", UTILITY_NAME
);
1890 Scratch
= (SCRATCH_DATA
*)malloc(sizeof(SCRATCH_DATA
));
1891 if (Scratch
== NULL
) {
1892 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1896 InputFile
= fopen (LongFilePath (InputFileName
), "rb");
1897 if (InputFile
== NULL
) {
1898 Error (NULL
, 0, 0001, "Error opening input file", InputFileName
);
1902 Status
= GetFileContents(
1907 if (Status
== EFI_BUFFER_TOO_SMALL
) {
1908 FileBuffer
= (UINT8
*) malloc (InputLength
);
1909 if (FileBuffer
== NULL
) {
1910 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1914 Status
= GetFileContents (
1921 if (EFI_ERROR(Status
)) {
1922 Error (NULL
, 0, 0004, "Error getting contents of file: %s", InputFileName
);
1926 if (OutputFileName
== NULL
) {
1927 OutputFileName
= DEFAULT_OUTPUT_FILE
;
1929 OutputFile
= fopen (LongFilePath (OutputFileName
), "wb");
1930 if (OutputFile
== NULL
) {
1931 Error (NULL
, 0, 0001, "Error opening output file for writing", OutputFileName
);
1937 // First call TianoCompress to get DstSize
1940 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding", NULL
);
1942 Status
= TianoCompress ((UINT8
*)FileBuffer
, InputLength
, OutBuffer
, &DstSize
);
1944 if (Status
== EFI_BUFFER_TOO_SMALL
) {
1945 OutBuffer
= (UINT8
*) malloc (DstSize
);
1946 if (OutBuffer
== NULL
) {
1947 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1952 Status
= TianoCompress ((UINT8
*)FileBuffer
, InputLength
, OutBuffer
, &DstSize
);
1953 if (Status
!= EFI_SUCCESS
) {
1954 Error (NULL
, 0, 0007, "Error compressing file", NULL
);
1958 if (OutBuffer
== NULL
) {
1959 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1963 fwrite(OutBuffer
,(size_t)DstSize
, 1, OutputFile
);
1971 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding Successful!\n", NULL
);
1974 VerboseMsg("Encoding successful\n");
1980 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Decoding\n", NULL
);
1983 // Get Compressed file original size
1985 Src
= (UINT8
*)FileBuffer
;
1986 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
1989 // Allocate OutputBuffer
1991 OutBuffer
= (UINT8
*)malloc(OrigSize
);
1992 if (OutBuffer
== NULL
) {
1993 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1997 Status
= Decompress((VOID
*)FileBuffer
, (VOID
*)OutBuffer
, (VOID
*)Scratch
, 2);
1998 if (Status
!= EFI_SUCCESS
) {
2002 fwrite(OutBuffer
, (size_t)(Scratch
->mOrigSize
), 1, OutputFile
);
2010 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding successful!\n", NULL
);
2014 VerboseMsg("Decoding successful\n");
2022 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding Error\n", NULL
);
2023 } else if (DECODE
) {
2024 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Decoding Error\n", NULL
);
2027 if (OutputFile
!= NULL
) {
2030 if (InputFile
!= NULL
) {
2033 if (Scratch
!= NULL
) {
2036 if (FileBuffer
!= NULL
) {
2039 if (OutBuffer
!= NULL
) {
2044 VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME
, GetUtilityStatus ());
2046 return GetUtilityStatus ();
2051 IN SCRATCH_DATA
*Sd
,
2056 Routine Description:
2058 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
2062 Sd - The global scratch data
2063 NumOfBits - The number of bits to shift and read.
2069 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
2071 while (NumOfBits
> Sd
->mBitCount
) {
2073 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
2075 if (Sd
->mCompSize
> 0) {
2077 // Get 1 byte into SubBitBuf
2081 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
2086 // No more bits from the source, just pad zero bit.
2094 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
2095 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
2100 IN SCRATCH_DATA
*Sd
,
2105 Routine Description:
2107 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
2108 NumOfBits of bits from source. Returns NumOfBits of bits that are
2113 Sd - The global scratch data.
2114 NumOfBits - The number of bits to pop and read.
2118 The bits that are popped out.
2124 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
2126 FillBuf (Sd
, NumOfBits
);
2133 IN SCRATCH_DATA
*Sd
,
2134 IN UINT16 NumOfChar
,
2136 IN UINT16 TableBits
,
2141 Routine Description:
2143 Creates Huffman Code mapping table according to code length array.
2147 Sd - The global scratch data
2148 NumOfChar - Number of symbols in the symbol set
2149 BitLen - Code length array
2150 TableBits - The width of the mapping table
2156 BAD_TABLE - The table is corrupted.
2175 for (Index
= 0; Index
<= 16; Index
++) {
2179 for (Index
= 0; Index
< NumOfChar
; Index
++) {
2180 Count
[BitLen
[Index
]]++;
2186 for (Index
= 1; Index
<= 16; Index
++) {
2187 WordOfStart
= Start
[Index
];
2188 WordOfCount
= Count
[Index
];
2189 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
2192 if (Start
[17] != 0) {
2196 return (UINT16
) BAD_TABLE
;
2199 JuBits
= (UINT16
) (16 - TableBits
);
2202 for (Index
= 1; Index
<= TableBits
; Index
++) {
2203 Start
[Index
] >>= JuBits
;
2204 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
2207 while (Index
<= 16) {
2208 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
2212 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
2215 Index3
= (UINT16
) (1U << TableBits
);
2216 while (Index
!= Index3
) {
2222 Mask
= (UINT16
) (1U << (15 - TableBits
));
2224 for (Char
= 0; Char
< NumOfChar
; Char
++) {
2227 if (Len
== 0 || Len
>= 17) {
2231 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
2233 if (Len
<= TableBits
) {
2235 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
2236 Table
[Index
] = Char
;
2241 Index3
= Start
[Len
];
2242 Pointer
= &Table
[Index3
>> JuBits
];
2243 Index
= (UINT16
) (Len
- TableBits
);
2245 while (Index
!= 0) {
2246 if (*Pointer
== 0) {
2247 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
2251 if (Index3
& Mask
) {
2252 Pointer
= &Sd
->mRight
[*Pointer
];
2254 Pointer
= &Sd
->mLeft
[*Pointer
];
2265 Start
[Len
] = NextCode
;
2279 Routine Description:
2281 Decodes a position value.
2285 Sd - the global scratch data
2289 The position value decoded.
2297 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2300 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2304 if (Sd
->mBitBuf
& Mask
) {
2305 Val
= Sd
->mRight
[Val
];
2307 Val
= Sd
->mLeft
[Val
];
2311 } while (Val
>= MAXNP
);
2314 // Advance what we have read
2316 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
2320 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
2328 IN SCRATCH_DATA
*Sd
,
2335 Routine Description:
2337 Reads code lengths for the Extra Set or the Position Set
2341 Sd - The global scratch data
2342 nn - Number of symbols
2343 nbit - Number of bits needed to represent nn
2344 Special - The special symbol that needs to be taken care of
2349 BAD_TABLE - Table is corrupted.
2355 volatile UINT16 Index
;
2360 Number
= (UINT16
) GetBits (Sd
, nbit
);
2363 CharC
= (UINT16
) GetBits (Sd
, nbit
);
2365 for (Index
= 0; Index
< 256; Index
++) {
2366 Sd
->mPTTable
[Index
] = CharC
;
2369 for (Index
= 0; Index
< nn
; Index
++) {
2370 Sd
->mPTLen
[Index
] = 0;
2378 while (Index
< Number
) {
2380 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
2383 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
2384 while (Mask
& Sd
->mBitBuf
) {
2390 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
2392 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
2394 if (Index
== Special
) {
2395 CharC
= (UINT16
) GetBits (Sd
, 2);
2396 while ((INT16
) (--CharC
) >= 0) {
2397 Sd
->mPTLen
[Index
++] = 0;
2402 while (Index
< nn
) {
2403 Sd
->mPTLen
[Index
++] = 0;
2406 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
2415 Routine Description:
2417 Reads code lengths for Char&Len Set.
2421 Sd - the global scratch data
2429 volatile UINT16 Index
;
2432 Number
= (UINT16
) GetBits (Sd
, CBIT
);
2435 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
2437 for (Index
= 0; Index
< NC
; Index
++) {
2438 Sd
->mCLen
[Index
] = 0;
2441 for (Index
= 0; Index
< 4096; Index
++) {
2442 Sd
->mCTable
[Index
] = CharC
;
2449 while (Index
< Number
) {
2451 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2453 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2457 if (Mask
& Sd
->mBitBuf
) {
2458 CharC
= Sd
->mRight
[CharC
];
2460 CharC
= Sd
->mLeft
[CharC
];
2465 } while (CharC
>= NT
);
2468 // Advance what we have read
2470 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
2476 } else if (CharC
== 1) {
2477 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
2478 } else if (CharC
== 2) {
2479 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
2482 while ((INT16
) (--CharC
) >= 0) {
2483 Sd
->mCLen
[Index
++] = 0;
2488 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
2493 while (Index
< NC
) {
2494 Sd
->mCLen
[Index
++] = 0;
2497 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
2508 Routine Description:
2510 Decode a character/length value.
2514 Sd - The global scratch data.
2525 if (Sd
->mBlockSize
== 0) {
2527 // Starting a new block
2529 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
2530 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
2531 if (Sd
->mBadTableFlag
!= 0) {
2537 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
2538 if (Sd
->mBadTableFlag
!= 0) {
2544 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
2547 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
2550 if (Sd
->mBitBuf
& Mask
) {
2551 Index2
= Sd
->mRight
[Index2
];
2553 Index2
= Sd
->mLeft
[Index2
];
2557 } while (Index2
>= NC
);
2560 // Advance what we have read
2562 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
2573 Routine Description:
2575 Decode the source data and put the resulting data into the destination buffer.
2579 Sd - The global scratch data
2589 BytesRemain
= (UINT16
) (-1);
2594 CharC
= DecodeC (Sd
);
2595 if (Sd
->mBadTableFlag
!= 0) {
2601 // Process an Original character
2603 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2606 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
2611 // Process a Pointer
2613 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
2615 BytesRemain
= CharC
;
2617 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
2620 while ((INT16
) (BytesRemain
) >= 0) {
2621 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
2622 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2639 IN OUT VOID
*Destination
,
2640 IN OUT VOID
*Scratch
,
2645 Routine Description:
2647 The internal implementation of Decompress().
2651 Source - The source buffer containing the compressed data.
2652 Destination - The destination buffer to store the decompressed data
2653 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
2654 Version - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2658 RETURN_SUCCESS - Decompression is successfull
2659 RETURN_INVALID_PARAMETER - The source data is corrupted
2663 volatile UINT32 Index
;
2671 // Verify input is not NULL
2674 // assert(Destination);
2677 Src
= (UINT8
*)Source
;
2678 Dst
= (UINT8
*)Destination
;
2680 Sd
= (SCRATCH_DATA
*) Scratch
;
2681 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
2682 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
2685 // If compressed file size is 0, return
2687 if (OrigSize
== 0) {
2688 return RETURN_SUCCESS
;
2693 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
2694 ((UINT8
*) Sd
)[Index
] = 0;
2697 // The length of the field 'Position Set Code Length Array Size' in Block Header.
2698 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2699 // For Tiano de/compression algorithm(Version 2), mPBit = 5
2711 Sd
->mSrcBase
= (UINT8
*)Src
;
2713 Sd
->mCompSize
= CompSize
;
2714 Sd
->mOrigSize
= OrigSize
;
2717 // Fill the first BITBUFSIZ bits
2719 FillBuf (Sd
, BITBUFSIZ
);
2727 if (Sd
->mBadTableFlag
!= 0) {
2729 // Something wrong with the source
2731 return RETURN_INVALID_PARAMETER
;
2734 return RETURN_SUCCESS
;