3 Copyright (c) 2007 - 2008, Intel Corporation
4 All rights reserved. This program and the accompanying materials
5 are licensed and made available under the terms and conditions of the BSD License
6 which accompanies this distribution. The full text of the license may be found at
7 http://opensource.org/licenses/bsd-license.php
9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 Compression routine. The compression algorithm is a mixture of
19 LZ77 and Huffman coding. LZ77 transforms the source data into a
20 sequence of Original Characters and Pointers to repeated strings.
21 This sequence is further divided into Blocks and Huffman codings
22 are applied to each Block.
27 #include "TianoCompress.h"
28 #include "EfiUtilityMsgs.h"
36 static BOOLEAN VerboseMode
= FALSE
;
37 static BOOLEAN QuietMode
= FALSE
;
39 #define UINT8_MAX 0xff
44 #define WNDSIZ (1U << WNDBIT)
46 #define BLKSIZ (1U << 14) // 16 * 1024U
47 #define PERC_FLAG 0x80000000U
50 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
51 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
52 #define CRCPOLY 0xA001
53 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
56 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
58 //#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
60 #define NP (WNDBIT + 1)
62 //#define NT (CODE_BIT + 3)
73 STATIC BOOLEAN ENCODE
= FALSE
;
74 STATIC BOOLEAN DECODE
= FALSE
;
75 STATIC UINT8
*mSrc
, *mDst
, *mSrcUpperLimit
, *mDstUpperLimit
;
76 STATIC UINT8
*mLevel
, *mText
, *mChildCount
, *mBuf
, mCLen
[NC
], mPTLen
[NPT
], *mLen
;
77 STATIC INT16 mHeap
[NC
+ 1];
78 STATIC INT32 mRemainder
, mMatchLen
, mBitCount
, mHeapSize
, mN
;
79 STATIC UINT32 mBufSiz
= 0, mOutputPos
, mOutputMask
, mSubBitBuf
, mCrc
;
80 STATIC UINT32 mCompSize
, mOrigSize
;
82 STATIC UINT16
*mFreq
, *mSortPtr
, mLenCnt
[17], mLeft
[2 * NC
- 1], mRight
[2 * NC
- 1], mCrcTable
[UINT8_MAX
+ 1],
83 mCFreq
[2 * NC
- 1], mCCode
[NC
], mPFreq
[2 * NP
- 1], mPTCode
[NPT
], mTFreq
[2 * NT
- 1];
85 STATIC NODE mPos
, mMatchPos
, mAvail
, *mPosition
, *mParent
, *mPrev
, *mNext
= NULL
;
87 static UINTN DebugLevel
;
88 static BOOLEAN DebugMode
;
97 IN OUT UINT32
*DstSize
103 The internal implementation of [Efi/Tiano]Compress().
107 SrcBuffer - The buffer storing the source data
108 SrcSize - The size of source data
109 DstBuffer - The buffer to store the compressed data
111 Version - The version of de/compression algorithm.
112 Version 1 for EFI 1.1 de/compression algorithm.
113 Version 2 for Tiano de/compression algorithm.
117 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
118 DstSize contains the size needed.
119 EFI_SUCCESS - Compression is successful.
120 EFI_OUT_OF_RESOURCES - No resource to complete function.
121 EFI_INVALID_PARAMETER - Parameter supplied is wrong.
142 mSrcUpperLimit
= mSrc
+ SrcSize
;
144 mDstUpperLimit
= mDst
+*DstSize
;
151 mOrigSize
= mCompSize
= 0;
158 if (EFI_ERROR (Status
)) {
159 return EFI_OUT_OF_RESOURCES
;
163 // Null terminate the compressed data
166 if (mDst
< mDstUpperLimit
) {
171 // Fill in compressed size and original size
175 PutDword (mCompSize
+ 1);
176 PutDword (mOrigSize
);
181 if (mCompSize
+ 1 + 8 > *DstSize
) {
182 *DstSize
= mCompSize
+ 1 + 8;
183 return EFI_BUFFER_TOO_SMALL
;
185 *DstSize
= mCompSize
+ 1 + 8;
200 Put a dword to output stream
204 Data - the dword to put
210 if (mDst
< mDstUpperLimit
) {
211 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
214 if (mDst
< mDstUpperLimit
) {
215 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
218 if (mDst
< mDstUpperLimit
) {
219 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
222 if (mDst
< mDstUpperLimit
) {
223 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
236 Allocate memory spaces for data structures used in compression process
243 EFI_SUCCESS - Memory is allocated successfully
244 EFI_OUT_OF_RESOURCES - Allocation fails
250 mText
= malloc (WNDSIZ
* 2 + MAXMATCH
);
251 for (Index
= 0; Index
< WNDSIZ
* 2 + MAXMATCH
; Index
++) {
255 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
256 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
257 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
258 mParent
= malloc (WNDSIZ
* 2 * sizeof (*mParent
));
259 mPrev
= malloc (WNDSIZ
* 2 * sizeof (*mPrev
));
260 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
263 mBuf
= malloc (mBufSiz
);
264 while (mBuf
== NULL
) {
265 mBufSiz
= (mBufSiz
/ 10U) * 9U;
266 if (mBufSiz
< 4 * 1024U) {
267 return EFI_OUT_OF_RESOURCES
;
270 mBuf
= malloc (mBufSiz
);
286 Called when compression is completed to free memory previously allocated.
298 if (mLevel
!= NULL
) {
302 if (mChildCount
!= NULL
) {
306 if (mPosition
!= NULL
) {
310 if (mParent
!= NULL
) {
338 Initialize String Info Log data structures
348 for (Index
= WNDSIZ
; Index
<= WNDSIZ
+ UINT8_MAX
; Index
++) {
350 mPosition
[Index
] = NIL
; // sentinel
353 for (Index
= WNDSIZ
; Index
< WNDSIZ
* 2; Index
++) {
354 mParent
[Index
] = NIL
;
358 for (Index
= 1; Index
< WNDSIZ
- 1; Index
++) {
359 mNext
[Index
] = (NODE
) (Index
+ 1);
362 mNext
[WNDSIZ
- 1] = NIL
;
363 for (Index
= WNDSIZ
* 2; Index
<= MAX_HASH_VAL
; Index
++) {
378 Find child node given the parent node and the edge character
382 NodeQ - the parent node
383 CharC - the edge character
387 The child node (NIL if not found)
393 NodeR
= mNext
[HASH (NodeQ
, CharC
)];
397 mParent
[NIL
] = NodeQ
;
398 while (mParent
[NodeR
] != NodeQ
) {
399 NodeR
= mNext
[NodeR
];
416 Create a new child for a given parent node.
420 Parent - the parent node
421 CharC - the edge character
422 Child - the child node
431 Node1
= (NODE
) HASH (Parent
, CharC
);
432 Node2
= mNext
[Node1
];
433 mNext
[Node1
] = Child
;
434 mNext
[Child
] = Node2
;
435 mPrev
[Node2
] = Child
;
436 mPrev
[Child
] = Node1
;
437 mParent
[Child
] = Parent
;
438 mChildCount
[Parent
]++;
454 Old - the node to split
465 mChildCount
[New
] = 0;
466 TempNode
= mPrev
[Old
];
467 mPrev
[New
] = TempNode
;
468 mNext
[TempNode
] = New
;
469 TempNode
= mNext
[Old
];
470 mNext
[New
] = TempNode
;
471 mPrev
[TempNode
] = New
;
472 mParent
[New
] = mParent
[Old
];
473 mLevel
[New
] = (UINT8
) mMatchLen
;
474 mPosition
[New
] = mPos
;
475 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
476 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
488 Insert string info for current position into the String Info Log
504 if (mMatchLen
>= 4) {
506 // We have just got a long match, the target tree
507 // can be located by MatchPos + 1. Travese the tree
508 // from bottom up to get to a proper starting point.
509 // The usage of PERC_FLAG ensures proper node deletion
510 // in DeleteNode() later.
513 NodeR
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
514 NodeQ
= mParent
[NodeR
];
515 while (NodeQ
== NIL
) {
516 NodeR
= mNext
[NodeR
];
517 NodeQ
= mParent
[NodeR
];
520 while (mLevel
[NodeQ
] >= mMatchLen
) {
522 NodeQ
= mParent
[NodeQ
];
526 while (mPosition
[NodeT
] < 0) {
527 mPosition
[NodeT
] = mPos
;
528 NodeT
= mParent
[NodeT
];
531 if (NodeT
< WNDSIZ
) {
532 mPosition
[NodeT
] = (NODE
) (mPos
| (UINT32
) PERC_FLAG
);
536 // Locate the target tree
538 NodeQ
= (NODE
) (mText
[mPos
] + WNDSIZ
);
539 CharC
= mText
[mPos
+ 1];
540 NodeR
= Child (NodeQ
, CharC
);
542 MakeChild (NodeQ
, CharC
, mPos
);
550 // Traverse down the tree to find a match.
551 // Update Position value along the route.
552 // Node split or creation is involved.
555 if (NodeR
>= WNDSIZ
) {
559 Index2
= mLevel
[NodeR
];
560 mMatchPos
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
563 if (mMatchPos
>= mPos
) {
567 t1
= &mText
[mPos
+ mMatchLen
];
568 t2
= &mText
[mMatchPos
+ mMatchLen
];
569 while (mMatchLen
< Index2
) {
580 if (mMatchLen
>= MAXMATCH
) {
584 mPosition
[NodeR
] = mPos
;
586 NodeR
= Child (NodeQ
, *t1
);
588 MakeChild (NodeQ
, *t1
, mPos
);
595 NodeT
= mPrev
[NodeR
];
598 NodeT
= mNext
[NodeR
];
601 mParent
[mPos
] = NodeQ
;
602 mParent
[NodeR
] = NIL
;
605 // Special usage of 'next'
620 Delete outdated string info. (The Usage of PERC_FLAG
621 ensures a clean deletion)
635 if (mParent
[mPos
] == NIL
) {
641 mNext
[NodeR
] = NodeS
;
642 mPrev
[NodeS
] = NodeR
;
643 NodeR
= mParent
[mPos
];
645 if (NodeR
>= WNDSIZ
) {
649 mChildCount
[NodeR
]--;
650 if (mChildCount
[NodeR
] > 1) {
654 NodeT
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
660 NodeQ
= mParent
[NodeR
];
661 NodeU
= mPosition
[NodeQ
];
662 while (NodeU
& (UINT32
) PERC_FLAG
) {
663 NodeU
&= (UINT32
)~PERC_FLAG
;
672 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
);
673 NodeQ
= mParent
[NodeQ
];
674 NodeU
= mPosition
[NodeQ
];
677 if (NodeQ
< WNDSIZ
) {
686 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
| (UINT32
) PERC_FLAG
);
689 NodeS
= Child (NodeR
, mText
[NodeT
+ mLevel
[NodeR
]]);
690 NodeT
= mPrev
[NodeS
];
691 NodeU
= mNext
[NodeS
];
692 mNext
[NodeT
] = NodeU
;
693 mPrev
[NodeU
] = NodeT
;
694 NodeT
= mPrev
[NodeR
];
695 mNext
[NodeT
] = NodeS
;
696 mPrev
[NodeS
] = NodeT
;
697 NodeT
= mNext
[NodeR
];
698 mPrev
[NodeT
] = NodeS
;
699 mNext
[NodeS
] = NodeT
;
700 mParent
[NodeS
] = mParent
[NodeR
];
701 mParent
[NodeR
] = NIL
;
702 mNext
[NodeR
] = mAvail
;
715 Advance the current position (read in new data if needed).
716 Delete outdated string info. Find a match string for current position.
728 if (mPos
== WNDSIZ
* 2) {
729 memmove (&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
730 Number
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
731 mRemainder
+= Number
;
748 The main controlling routine for compression process.
754 EFI_SUCCESS - The compression is successful
755 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
763 Status
= AllocateMemory ();
764 if (EFI_ERROR (Status
)) {
773 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
778 if (mMatchLen
> mRemainder
) {
779 mMatchLen
= mRemainder
;
782 while (mRemainder
> 0) {
783 LastMatchLen
= mMatchLen
;
784 LastMatchPos
= mMatchPos
;
786 if (mMatchLen
> mRemainder
) {
787 mMatchLen
= mRemainder
;
790 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
792 // Not enough benefits are gained by outputting a pointer,
793 // so just output the original character
795 Output (mText
[mPos
- 1], 0);
799 if (LastMatchLen
== THRESHOLD
) {
800 if (((mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)) > (1U << 11)) {
801 Output (mText
[mPos
- 1], 0);
806 // Outputting a pointer is beneficial enough, do it.
809 LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
810 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)
813 while (LastMatchLen
> 0) {
818 if (mMatchLen
> mRemainder
) {
819 mMatchLen
= mRemainder
;
838 Count the frequencies for the Extra Set
851 for (Index
= 0; Index
< NT
; Index
++) {
856 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
861 while (Index
< Number
) {
862 Index3
= mCLen
[Index
++];
865 while (Index
< Number
&& mCLen
[Index
] == 0) {
871 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
872 } else if (Count
<= 18) {
874 } else if (Count
== 19) {
881 mTFreq
[Index3
+ 2]++;
897 Outputs the code length array for the Extra Set or the Position Set.
901 Number - the number of symbols
902 nbit - the number of bits needed to represent 'n'
903 Special - the special symbol that needs to be take care of
912 while (Number
> 0 && mPTLen
[Number
- 1] == 0) {
916 PutBits (nbit
, Number
);
918 while (Index
< Number
) {
919 Index3
= mPTLen
[Index
++];
923 PutBits (Index3
- 3, (1U << (Index3
- 3)) - 2);
926 if (Index
== Special
) {
927 while (Index
< 6 && mPTLen
[Index
] == 0) {
931 PutBits (2, (Index
- 3) & 3);
945 Outputs the code length array for Char&Length Set
959 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
963 PutBits (CBIT
, Number
);
965 while (Index
< Number
) {
966 Index3
= mCLen
[Index
++];
969 while (Index
< Number
&& mCLen
[Index
] == 0) {
975 for (Index3
= 0; Index3
< Count
; Index3
++) {
976 PutBits (mPTLen
[0], mPTCode
[0]);
978 } else if (Count
<= 18) {
979 PutBits (mPTLen
[1], mPTCode
[1]);
980 PutBits (4, Count
- 3);
981 } else if (Count
== 19) {
982 PutBits (mPTLen
[0], mPTCode
[0]);
983 PutBits (mPTLen
[1], mPTCode
[1]);
986 PutBits (mPTLen
[2], mPTCode
[2]);
987 PutBits (CBIT
, Count
- 20);
990 PutBits (mPTLen
[Index3
+ 2], mPTCode
[Index3
+ 2]);
1001 PutBits (mCLen
[Value
], mCCode
[Value
]);
1020 PutBits (mPTLen
[Index
], mPTCode
[Index
]);
1022 PutBits (Index
- 1, Value
& (0xFFFFFFFFU
>> (32 - Index
+ 1)));
1033 Routine Description:
1035 Huffman code the block and output it.
1054 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1055 Size
= mCFreq
[Root
];
1060 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1062 WritePTLen (NT
, TBIT
, 3);
1065 PutBits (TBIT
, Root
);
1073 PutBits (CBIT
, Root
);
1076 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1078 WritePTLen (NP
, PBIT
, -1);
1081 PutBits (PBIT
, Root
);
1085 for (Index
= 0; Index
< Size
; Index
++) {
1086 if (Index
% UINT8_BIT
== 0) {
1087 Flags
= mBuf
[Pos
++];
1092 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1093 EncodeC (mBuf
[Pos
++] + (1U << UINT8_BIT
));
1094 Index3
= mBuf
[Pos
++];
1095 for (Index2
= 0; Index2
< 3; Index2
++) {
1096 Index3
<<= UINT8_BIT
;
1097 Index3
+= mBuf
[Pos
++];
1102 EncodeC (mBuf
[Pos
++]);
1106 for (Index
= 0; Index
< NC
; Index
++) {
1110 for (Index
= 0; Index
< NP
; Index
++) {
1123 Routine Description:
1125 Outputs an Original Character or a Pointer
1129 CharC - The original character or the 'String Length' element of a Pointer
1130 Pos - The 'Position' field of a Pointer
1138 if ((mOutputMask
>>= 1) == 0) {
1139 mOutputMask
= 1U << (UINT8_BIT
- 1);
1141 // Check the buffer overflow per outputing UINT8_BIT symbols
1142 // which is an Original Character or a Pointer. The biggest
1143 // symbol is a Pointer which occupies 5 bytes.
1145 if (mOutputPos
>= mBufSiz
- 5 * UINT8_BIT
) {
1150 CPos
= mOutputPos
++;
1154 mBuf
[mOutputPos
++] = (UINT8
) CharC
;
1156 if (CharC
>= (1U << UINT8_BIT
)) {
1157 mBuf
[CPos
] |= mOutputMask
;
1158 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 24);
1159 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 16);
1160 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> (UINT8_BIT
));
1161 mBuf
[mOutputPos
++] = (UINT8
) Pos
;
1180 for (Index
= 0; Index
< NC
; Index
++) {
1184 for (Index
= 0; Index
< NP
; Index
++) {
1188 mOutputPos
= mOutputMask
= 0;
1202 // Flush remaining bits
1204 PutBits (UINT8_BIT
- 1, 0);
1219 for (Index
= 0; Index
<= UINT8_MAX
; Index
++) {
1221 for (Index2
= 0; Index2
< UINT8_BIT
; Index2
++) {
1223 Temp
= (Temp
>> 1) ^ CRCPOLY
;
1229 mCrcTable
[Index
] = (UINT16
) Temp
;
1241 Routine Description:
1243 Outputs rightmost n bits of x
1247 Number - the rightmost n bits of the data is used
1256 while (Number
>= mBitCount
) {
1258 // Number -= mBitCount should never equal to 32
1260 Temp
= (UINT8
) (mSubBitBuf
| (Value
>> (Number
-= mBitCount
)));
1262 if (mDst
< mDstUpperLimit
) {
1268 mBitCount
= UINT8_BIT
;
1271 mSubBitBuf
|= Value
<< (mBitCount
-= Number
);
1282 Routine Description:
1288 Pointer - the buffer to hold the data
1289 Number - number of bytes to read
1293 number of bytes actually read
1299 for (Index
= 0; mSrc
< mSrcUpperLimit
&& Index
< Number
; Index
++) {
1300 *Pointer
++ = *mSrc
++;
1306 mOrigSize
+= Number
;
1309 while (Index
>= 0) {
1310 UPDATE_CRC (*Pointer
++);
1323 mBitCount
= UINT8_BIT
;
1334 Routine Description:
1336 Count the number of each code length for a Huffman tree.
1340 Index - the top node
1346 STATIC INT32 Depth
= 0;
1349 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1352 CountLen (mLeft
[Index
]);
1353 CountLen (mRight
[Index
]);
1365 Routine Description:
1367 Create code length array for a Huffman tree
1371 Root - the root of the tree
1383 for (Index
= 0; Index
<= 16; Index
++) {
1390 // Adjust the length count array so that
1391 // no code will be generated longer than its designated length
1394 for (Index
= 16; Index
> 0; Index
--) {
1395 Cum
+= mLenCnt
[Index
] << (16 - Index
);
1398 while (Cum
!= (1U << 16)) {
1400 for (Index
= 15; Index
> 0; Index
--) {
1401 if (mLenCnt
[Index
] != 0) {
1403 mLenCnt
[Index
+ 1] += 2;
1411 for (Index
= 16; Index
> 0; Index
--) {
1412 Index3
= mLenCnt
[Index
];
1414 while (Index3
>= 0) {
1415 mLen
[*mSortPtr
++] = (UINT8
) Index
;
1431 // priority queue: send Index-th entry down heap
1433 Index3
= mHeap
[Index
];
1435 while (Index2
<= mHeapSize
) {
1436 if (Index2
< mHeapSize
&& mFreq
[mHeap
[Index2
]] > mFreq
[mHeap
[Index2
+ 1]]) {
1440 if (mFreq
[Index3
] <= mFreq
[mHeap
[Index2
]]) {
1444 mHeap
[Index
] = mHeap
[Index2
];
1449 mHeap
[Index
] = (INT16
) Index3
;
1461 Routine Description:
1463 Assign code to each symbol based on the code length array
1467 Number - number of symbols
1468 Len - the code length array
1469 Code - stores codes for each symbol
1479 for (Index
= 1; Index
<= 16; Index
++) {
1480 Start
[Index
+ 1] = (UINT16
) ((Start
[Index
] + mLenCnt
[Index
]) << 1);
1483 for (Index
= 0; Index
< Number
; Index
++) {
1484 Code
[Index
] = Start
[Len
[Index
]]++;
1492 IN UINT16 FreqParm
[],
1493 OUT UINT8 LenParm
[ ],
1494 OUT UINT16 CodeParm
[]
1498 Routine Description:
1500 Generates Huffman codes given a frequency distribution of symbols
1504 NParm - number of symbols
1505 FreqParm - frequency of each symbol
1506 LenParm - code length for each symbol
1507 CodeParm - code for each symbol
1511 Root of the Huffman tree.
1521 // make tree, calculate len[], return root
1529 for (Index
= 0; Index
< mN
; Index
++) {
1533 mHeap
[mHeapSize
] = (INT16
) Index
;
1537 if (mHeapSize
< 2) {
1538 CodeParm
[mHeap
[1]] = 0;
1542 for (Index
= mHeapSize
/ 2; Index
>= 1; Index
--) {
1544 // make priority queue
1549 mSortPtr
= CodeParm
;
1553 *mSortPtr
++ = (UINT16
) Index
;
1556 mHeap
[1] = mHeap
[mHeapSize
--];
1560 *mSortPtr
++ = (UINT16
) Index2
;
1564 mFreq
[Index3
] = (UINT16
) (mFreq
[Index
] + mFreq
[Index2
]);
1565 mHeap
[1] = (INT16
) Index3
;
1567 mLeft
[Index3
] = (UINT16
) Index
;
1568 mRight
[Index3
] = (UINT16
) Index2
;
1569 } while (mHeapSize
> 1);
1571 mSortPtr
= CodeParm
;
1573 MakeCode (NParm
, LenParm
, CodeParm
);
1583 IN
char *InputFileName
,
1584 OUT UINT8
*FileBuffer
,
1585 OUT UINT32
*BufferLength
1589 Routine Description:
1591 Get the contents of file specified in InputFileName
1596 InputFileName - Name of the input file.
1598 FileBuffer - Output buffer to contain data
1600 BufferLength - Actual length of the data
1604 EFI_SUCCESS on successful return
1605 EFI_ABORTED if unable to open input file.
1615 // Copy the file contents to the output buffer.
1617 InputFile
= fopen (InputFileName
, "rb");
1618 if (InputFile
== NULL
) {
1619 Error (NULL
, 0, 0001, "Error opening file: %s", InputFileName
);
1623 fseek (InputFile
, 0, SEEK_END
);
1624 FileSize
= ftell (InputFile
);
1625 fseek (InputFile
, 0, SEEK_SET
);
1627 // Now read the contents of the file into the buffer
1629 if (FileSize
> 0 && FileBuffer
!= NULL
) {
1630 if (fread (FileBuffer
, FileSize
, 1, InputFile
) != 1) {
1631 Error (NULL
, 0, 0004, "Error reading contents of input file: %s", InputFileName
);
1638 Size
+= (UINTN
) FileSize
;
1639 *BufferLength
= Size
;
1641 if (FileBuffer
!= NULL
) {
1644 return EFI_BUFFER_TOO_SMALL
;
1654 Routine Description:
1656 Displays the standard utility information to SDTOUT
1668 fprintf (stdout
, "%s Version %d.%d\n", UTILITY_NAME
, UTILITY_MAJOR_VERSION
, UTILITY_MINOR_VERSION
);
1677 Routine Description:
1679 Displays the utility usage syntax to STDOUT
1694 fprintf (stdout
, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME
);
1697 // Copyright declaration
1699 fprintf (stdout
, "Copyright (c) 2007, Intel Corporation. All rights reserved.\n\n");
1704 fprintf (stdout
, "Options:\n");
1705 fprintf (stdout
, " -o FileName, --output FileName\n\
1706 File will be created to store the ouput content.\n");
1707 fprintf (stdout
, " -v, --verbose\n\
1708 Turn on verbose output with informational messages.\n");
1709 fprintf (stdout
, " -q, --quiet\n\
1710 Disable all messages except key message and fatal error\n");
1711 fprintf (stdout
, " --debug [0-9]\n\
1712 Enable debug messages, at input debug level.\n");
1713 fprintf (stdout
, " --version\n\
1714 Show program's version number and exit.\n");
1715 fprintf (stdout
, " -h, --help\n\
1716 Show this help message and exit.\n");
1727 Routine Description:
1733 command line parameters
1737 EFI_SUCCESS Section header successfully generated and section concatenated.
1738 EFI_ABORTED Could not generate the section
1739 EFI_OUT_OF_RESOURCES No resource to complete the operation.
1744 char *OutputFileName
;
1745 char *InputFileName
;
1752 SCRATCH_DATA
*Scratch
;
1756 SetUtilityName(UTILITY_NAME
);
1764 InputFileName
= NULL
;
1765 OutputFileName
= NULL
;
1771 // Verify the correct number of arguments
1774 Error (NULL
, 0, 1001, "Missing options", "No input options specified.");
1779 if ((strcmp(argv
[1], "-h") == 0) || (strcmp(argv
[1], "--help") == 0)) {
1784 if ((strcmp(argv
[1], "--version") == 0)) {
1791 if (strcmp(argv
[0],"-e") == 0) {
1793 // encode the input file
1798 } else if (strcmp(argv
[0], "-d") == 0) {
1800 // decode the input file
1807 // Error command line
1809 Error (NULL
, 0, 1003, "Invalid option value", "the options specified are not recognized.");
1815 if ((strcmp(argv
[0], "-v") == 0) || (stricmp(argv
[0], "--verbose") == 0)) {
1822 if (stricmp (argv
[0], "--debug") == 0) {
1825 Status
= AsciiStringToUint64(argv
[0], FALSE
, &DebugLevel
);
1826 if (DebugLevel
> 9) {
1827 Error (NULL
, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv
[0]);
1830 if (DebugLevel
>=5 && DebugLevel
<=9){
1839 if ((strcmp(argv
[0], "-q") == 0) || (stricmp (argv
[0], "--quiet") == 0)) {
1846 if ((strcmp(argv
[0], "-o") == 0) || (stricmp (argv
[0], "--output") == 0)) {
1847 if (argv
[1] == NULL
|| argv
[1][0] == '-') {
1848 Error (NULL
, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
1851 OutputFileName
= argv
[1];
1857 if (argv
[0][0]!='-') {
1858 InputFileName
= argv
[0];
1864 Error (NULL
, 0, 1000, "Unknown option", argv
[0]);
1868 if (InputFileName
== NULL
) {
1869 Error (NULL
, 0, 1001, "Missing options", "No input files specified.");
1874 // All Parameters has been parsed, now set the message print level
1878 } else if (VerboseMode
) {
1880 } else if (DebugMode
) {
1881 SetPrintLevel(DebugLevel
);
1885 VerboseMsg("%s tool start.\n", UTILITY_NAME
);
1887 Scratch
= (SCRATCH_DATA
*)malloc(sizeof(SCRATCH_DATA
));
1888 if (Scratch
== NULL
) {
1889 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1893 InputFile
= fopen (InputFileName
, "rb");
1894 if (InputFile
== NULL
) {
1895 Error (NULL
, 0, 0001, "Error opening input file", InputFileName
);
1899 Status
= GetFileContents(
1904 if (Status
== EFI_BUFFER_TOO_SMALL
) {
1905 FileBuffer
= (UINT8
*) malloc (InputLength
);
1906 if (FileBuffer
== NULL
) {
1907 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1911 Status
= GetFileContents (
1918 if (EFI_ERROR(Status
)) {
1923 if (OutputFileName
!= NULL
) {
1924 OutputFile
= fopen (OutputFileName
, "wb");
1925 if (OutputFile
== NULL
) {
1926 Error (NULL
, 0, 0001, "Error opening output file for writing", OutputFileName
);
1927 if (InputFile
!= NULL
) {
1933 OutputFileName
= DEFAULT_OUTPUT_FILE
;
1934 OutputFile
= fopen (OutputFileName
, "wb");
1939 // First call TianoCompress to get DstSize
1942 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding", NULL
);
1944 Status
= TianoCompress ((UINT8
*)FileBuffer
, InputLength
, OutBuffer
, &DstSize
);
1946 if (Status
== EFI_BUFFER_TOO_SMALL
) {
1947 OutBuffer
= (UINT8
*) malloc (DstSize
);
1948 if (OutBuffer
== NULL
) {
1949 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 fwrite(OutBuffer
,(size_t)DstSize
, 1, OutputFile
);
1965 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding Successful!\n", NULL
);
1968 VerboseMsg("Encoding successful\n");
1974 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Decoding\n", NULL
);
1977 // Get Compressed file original size
1979 Src
= (UINT8
*)FileBuffer
;
1980 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
1983 // Allocate OutputBuffer
1985 OutBuffer
= (UINT8
*)malloc(OrigSize
);
1986 if (OutBuffer
== NULL
) {
1987 Error (NULL
, 0, 4001, "Resource:", "Memory cannot be allocated!");
1991 Status
= Decompress((VOID
*)FileBuffer
, (VOID
*)OutBuffer
, (VOID
*)Scratch
, 2);
1992 if (Status
!= EFI_SUCCESS
) {
1996 fwrite(OutBuffer
, (size_t)(Scratch
->mOrigSize
), 1, OutputFile
);
2002 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding successful!\n", NULL
);
2006 VerboseMsg("Decoding successful\n");
2014 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Encoding Error\n", NULL
);
2015 } else if (DECODE
) {
2016 DebugMsg(UTILITY_NAME
, 0, DebugLevel
, "Decoding Error\n", NULL
);
2019 if (Scratch
!= NULL
) {
2022 if (FileBuffer
!= NULL
) {
2025 if (OutBuffer
!= NULL
) {
2030 VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME
, GetUtilityStatus ());
2032 return GetUtilityStatus ();
2037 IN SCRATCH_DATA
*Sd
,
2042 Routine Description:
2044 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
2048 Sd - The global scratch data
2049 NumOfBits - The number of bits to shift and read.
2055 Sd
->mBitBuf
= (UINT32
) (Sd
->mBitBuf
<< NumOfBits
);
2057 while (NumOfBits
> Sd
->mBitCount
) {
2059 Sd
->mBitBuf
|= (UINT32
) (Sd
->mSubBitBuf
<< (NumOfBits
= (UINT16
) (NumOfBits
- Sd
->mBitCount
)));
2061 if (Sd
->mCompSize
> 0) {
2063 // Get 1 byte into SubBitBuf
2067 Sd
->mSubBitBuf
= Sd
->mSrcBase
[Sd
->mInBuf
++];
2072 // No more bits from the source, just pad zero bit.
2080 Sd
->mBitCount
= (UINT16
) (Sd
->mBitCount
- NumOfBits
);
2081 Sd
->mBitBuf
|= Sd
->mSubBitBuf
>> Sd
->mBitCount
;
2086 IN SCRATCH_DATA
*Sd
,
2091 Routine Description:
2093 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
2094 NumOfBits of bits from source. Returns NumOfBits of bits that are
2099 Sd - The global scratch data.
2100 NumOfBits - The number of bits to pop and read.
2104 The bits that are popped out.
2110 OutBits
= (UINT32
) (Sd
->mBitBuf
>> (BITBUFSIZ
- NumOfBits
));
2112 FillBuf (Sd
, NumOfBits
);
2119 IN SCRATCH_DATA
*Sd
,
2120 IN UINT16 NumOfChar
,
2122 IN UINT16 TableBits
,
2127 Routine Description:
2129 Creates Huffman Code mapping table according to code length array.
2133 Sd - The global scratch data
2134 NumOfChar - Number of symbols in the symbol set
2135 BitLen - Code length array
2136 TableBits - The width of the mapping table
2142 BAD_TABLE - The table is corrupted.
2151 volatile UINT16 Index
;
2161 for (Index
= 1; Index
<= 16; Index
++) {
2165 for (Index
= 0; Index
< NumOfChar
; Index
++) {
2166 Count
[BitLen
[Index
]]++;
2171 for (Index
= 1; Index
<= 16; Index
++) {
2172 WordOfStart
= Start
[Index
];
2173 WordOfCount
= Count
[Index
];
2174 Start
[Index
+ 1] = (UINT16
) (WordOfStart
+ (WordOfCount
<< (16 - Index
)));
2177 if (Start
[17] != 0) {
2181 return (UINT16
) BAD_TABLE
;
2184 JuBits
= (UINT16
) (16 - TableBits
);
2186 for (Index
= 1; Index
<= TableBits
; Index
++) {
2187 Start
[Index
] >>= JuBits
;
2188 Weight
[Index
] = (UINT16
) (1U << (TableBits
- Index
));
2191 while (Index
<= 16) {
2192 Weight
[Index
] = (UINT16
) (1U << (16 - Index
));
2196 Index
= (UINT16
) (Start
[TableBits
+ 1] >> JuBits
);
2199 Index3
= (UINT16
) (1U << TableBits
);
2200 while (Index
!= Index3
) {
2206 Mask
= (UINT16
) (1U << (15 - TableBits
));
2208 for (Char
= 0; Char
< NumOfChar
; Char
++) {
2215 NextCode
= (UINT16
) (Start
[Len
] + Weight
[Len
]);
2217 if (Len
<= TableBits
) {
2219 for (Index
= Start
[Len
]; Index
< NextCode
; Index
++) {
2220 Table
[Index
] = Char
;
2225 Index3
= Start
[Len
];
2226 Pointer
= &Table
[Index3
>> JuBits
];
2227 Index
= (UINT16
) (Len
- TableBits
);
2229 while (Index
!= 0) {
2230 if (*Pointer
== 0) {
2231 Sd
->mRight
[Avail
] = Sd
->mLeft
[Avail
] = 0;
2235 if (Index3
& Mask
) {
2236 Pointer
= &Sd
->mRight
[*Pointer
];
2238 Pointer
= &Sd
->mLeft
[*Pointer
];
2249 Start
[Len
] = NextCode
;
2263 Routine Description:
2265 Decodes a position value.
2269 Sd - the global scratch data
2273 The position value decoded.
2281 Val
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2284 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2288 if (Sd
->mBitBuf
& Mask
) {
2289 Val
= Sd
->mRight
[Val
];
2291 Val
= Sd
->mLeft
[Val
];
2295 } while (Val
>= MAXNP
);
2298 // Advance what we have read
2300 FillBuf (Sd
, Sd
->mPTLen
[Val
]);
2304 Pos
= (UINT32
) ((1U << (Val
- 1)) + GetBits (Sd
, (UINT16
) (Val
- 1)));
2312 IN SCRATCH_DATA
*Sd
,
2319 Routine Description:
2321 Reads code lengths for the Extra Set or the Position Set
2325 Sd - The global scratch data
2326 nn - Number of symbols
2327 nbit - Number of bits needed to represent nn
2328 Special - The special symbol that needs to be taken care of
2333 BAD_TABLE - Table is corrupted.
2339 volatile UINT16 Index
;
2342 Number
= (UINT16
) GetBits (Sd
, nbit
);
2345 CharC
= (UINT16
) GetBits (Sd
, nbit
);
2347 for (Index
= 0; Index
< 256; Index
++) {
2348 Sd
->mPTTable
[Index
] = CharC
;
2351 for (Index
= 0; Index
< nn
; Index
++) {
2352 Sd
->mPTLen
[Index
] = 0;
2360 while (Index
< Number
) {
2362 CharC
= (UINT16
) (Sd
->mBitBuf
>> (BITBUFSIZ
- 3));
2365 Mask
= 1U << (BITBUFSIZ
- 1 - 3);
2366 while (Mask
& Sd
->mBitBuf
) {
2372 FillBuf (Sd
, (UINT16
) ((CharC
< 7) ? 3 : CharC
- 3));
2374 Sd
->mPTLen
[Index
++] = (UINT8
) CharC
;
2376 if (Index
== Special
) {
2377 CharC
= (UINT16
) GetBits (Sd
, 2);
2378 while ((INT16
) (--CharC
) >= 0) {
2379 Sd
->mPTLen
[Index
++] = 0;
2384 while (Index
< nn
) {
2385 Sd
->mPTLen
[Index
++] = 0;
2388 return MakeTable (Sd
, nn
, Sd
->mPTLen
, 8, Sd
->mPTTable
);
2397 Routine Description:
2399 Reads code lengths for Char&Len Set.
2403 Sd - the global scratch data
2411 volatile UINT16 Index
;
2414 Number
= (UINT16
) GetBits (Sd
, CBIT
);
2417 CharC
= (UINT16
) GetBits (Sd
, CBIT
);
2419 for (Index
= 0; Index
< NC
; Index
++) {
2420 Sd
->mCLen
[Index
] = 0;
2423 for (Index
= 0; Index
< 4096; Index
++) {
2424 Sd
->mCTable
[Index
] = CharC
;
2431 while (Index
< Number
) {
2433 CharC
= Sd
->mPTTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 8)];
2435 Mask
= 1U << (BITBUFSIZ
- 1 - 8);
2439 if (Mask
& Sd
->mBitBuf
) {
2440 CharC
= Sd
->mRight
[CharC
];
2442 CharC
= Sd
->mLeft
[CharC
];
2447 } while (CharC
>= NT
);
2450 // Advance what we have read
2452 FillBuf (Sd
, Sd
->mPTLen
[CharC
]);
2458 } else if (CharC
== 1) {
2459 CharC
= (UINT16
) (GetBits (Sd
, 4) + 3);
2460 } else if (CharC
== 2) {
2461 CharC
= (UINT16
) (GetBits (Sd
, CBIT
) + 20);
2464 while ((INT16
) (--CharC
) >= 0) {
2465 Sd
->mCLen
[Index
++] = 0;
2470 Sd
->mCLen
[Index
++] = (UINT8
) (CharC
- 2);
2475 while (Index
< NC
) {
2476 Sd
->mCLen
[Index
++] = 0;
2479 MakeTable (Sd
, NC
, Sd
->mCLen
, 12, Sd
->mCTable
);
2490 Routine Description:
2492 Decode a character/length value.
2496 Sd - The global scratch data.
2507 if (Sd
->mBlockSize
== 0) {
2509 // Starting a new block
2511 Sd
->mBlockSize
= (UINT16
) GetBits (Sd
, 16);
2512 Sd
->mBadTableFlag
= ReadPTLen (Sd
, NT
, TBIT
, 3);
2513 if (Sd
->mBadTableFlag
!= 0) {
2519 Sd
->mBadTableFlag
= ReadPTLen (Sd
, MAXNP
, Sd
->mPBit
, (UINT16
) (-1));
2520 if (Sd
->mBadTableFlag
!= 0) {
2526 Index2
= Sd
->mCTable
[Sd
->mBitBuf
>> (BITBUFSIZ
- 12)];
2529 Mask
= 1U << (BITBUFSIZ
- 1 - 12);
2532 if (Sd
->mBitBuf
& Mask
) {
2533 Index2
= Sd
->mRight
[Index2
];
2535 Index2
= Sd
->mLeft
[Index2
];
2539 } while (Index2
>= NC
);
2542 // Advance what we have read
2544 FillBuf (Sd
, Sd
->mCLen
[Index2
]);
2555 Routine Description:
2557 Decode the source data and put the resulting data into the destination buffer.
2561 Sd - The global scratch data
2571 BytesRemain
= (UINT16
) (-1);
2576 CharC
= DecodeC (Sd
);
2577 if (Sd
->mBadTableFlag
!= 0) {
2583 // Process an Original character
2585 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2588 Sd
->mDstBase
[Sd
->mOutBuf
++] = (UINT8
) CharC
;
2593 // Process a Pointer
2595 CharC
= (UINT16
) (CharC
- (UINT8_MAX
+ 1 - THRESHOLD
));
2597 BytesRemain
= CharC
;
2599 DataIdx
= Sd
->mOutBuf
- DecodeP (Sd
) - 1;
2602 while ((INT16
) (BytesRemain
) >= 0) {
2603 Sd
->mDstBase
[Sd
->mOutBuf
++] = Sd
->mDstBase
[DataIdx
++];
2604 if (Sd
->mOutBuf
>= Sd
->mOrigSize
) {
2621 IN OUT VOID
*Destination
,
2622 IN OUT VOID
*Scratch
,
2627 Routine Description:
2629 The internal implementation of Decompress().
2633 Source - The source buffer containing the compressed data.
2634 Destination - The destination buffer to store the decompressed data
2635 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
2636 Version - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2640 RETURN_SUCCESS - Decompression is successfull
2641 RETURN_INVALID_PARAMETER - The source data is corrupted
2645 volatile UINT32 Index
;
2653 // Verify input is not NULL
2656 // assert(Destination);
2659 Src
= (UINT8
*)Source
;
2660 Dst
= (UINT8
*)Destination
;
2662 Sd
= (SCRATCH_DATA
*) Scratch
;
2663 CompSize
= Src
[0] + (Src
[1] << 8) + (Src
[2] << 16) + (Src
[3] << 24);
2664 OrigSize
= Src
[4] + (Src
[5] << 8) + (Src
[6] << 16) + (Src
[7] << 24);
2667 // If compressed file size is 0, return
2669 if (OrigSize
== 0) {
2670 return RETURN_SUCCESS
;
2675 for (Index
= 0; Index
< sizeof (SCRATCH_DATA
); Index
++) {
2676 ((UINT8
*) Sd
)[Index
] = 0;
2679 // The length of the field 'Position Set Code Length Array Size' in Block Header.
2680 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2681 // For Tiano de/compression algorithm(Version 2), mPBit = 5
2693 Sd
->mSrcBase
= (UINT8
*)Src
;
2695 Sd
->mCompSize
= CompSize
;
2696 Sd
->mOrigSize
= OrigSize
;
2699 // Fill the first BITBUFSIZ bits
2701 FillBuf (Sd
, BITBUFSIZ
);
2709 if (Sd
->mBadTableFlag
!= 0) {
2711 // Something wrong with the source
2713 return RETURN_INVALID_PARAMETER
;
2716 return RETURN_SUCCESS
;