1 /* Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
2 * Use of this source code is governed by a BSD-style license that can be
3 * found in the LICENSE file.
4 */
5
6 /*++
7
8 Copyright (c) 2006, Intel Corporation
9 All rights reserved. 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
13
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.
16
17 Module Name:
18
19 EfiCompress.c
20
21 Abstract:
22
23 Compression routine. The compression algorithm is a mixture of
24 LZ77 and Huffman coding. LZ77 transforms the source data into a
25 sequence of Original Characters and Pointers to repeated strings.
26 This sequence is further divided into Blocks and Huffman codings
27 are applied to each Block.
28
29 --*/
30
31 #include <errno.h>
32 #include <stdint.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <sys/types.h>
37 #include <sys/stat.h>
38 #include <unistd.h>
39
40 #include "eficompress.h"
41
42
43 //
44 // Macro Definitions
45 //
46
47 typedef INT16 NODE;
48 #define UINT8_BIT 8
49 #define THRESHOLD 3
50 #define INIT_CRC 0
51 #define WNDBIT 13
52 #define WNDSIZ (1U << WNDBIT)
53 #define MAXMATCH 256
54 #define PERC_FLAG 0x8000U
55 #define CODE_BIT 16
56 #define NIL 0
57 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
58 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
59 #define CRCPOLY 0xA001
60 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
61
62 //
63 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
64 //
65
66 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
67 #define CBIT 9
68 #define NP (WNDBIT + 1)
69 #define PBIT 4
70 #define NT (CODE_BIT + 3)
71 #define TBIT 5
72 #if NT > NP
73 #define NPT NT
74 #else
75 #define NPT NP
76 #endif
77
78 //
79 // Function Prototypes
80 //
81
82 STATIC
83 VOID
84 PutDword(
85 IN UINT32 Data
86 );
87
88 STATIC
89 EFI_STATUS
90 AllocateMemory (
91 );
92
93 STATIC
94 VOID
95 FreeMemory (
96 );
97
98 STATIC
99 VOID
100 InitSlide (
101 );
102
103 STATIC
104 NODE
105 Child (
106 IN NODE q,
107 IN UINT8 c
108 );
109
110 STATIC
111 VOID
112 MakeChild (
113 IN NODE q,
114 IN UINT8 c,
115 IN NODE r
116 );
117
118 STATIC
119 VOID
120 Split (
121 IN NODE Old
122 );
123
124 STATIC
125 VOID
126 InsertNode (
127 );
128
129 STATIC
130 VOID
131 DeleteNode (
132 );
133
134 STATIC
135 VOID
136 GetNextMatch (
137 );
138
139 STATIC
140 EFI_STATUS
141 Encode (
142 );
143
144 STATIC
145 VOID
146 CountTFreq (
147 );
148
149 STATIC
150 VOID
151 WritePTLen (
152 IN INT32 n,
153 IN INT32 nbit,
154 IN INT32 Special
155 );
156
157 STATIC
158 VOID
159 WriteCLen (
160 );
161
162 STATIC
163 VOID
164 EncodeC (
165 IN INT32 c
166 );
167
168 STATIC
169 VOID
170 EncodeP (
171 IN UINT32 p
172 );
173
174 STATIC
175 VOID
176 SendBlock (
177 );
178
179 STATIC
180 VOID
181 Output (
182 IN UINT32 c,
183 IN UINT32 p
184 );
185
186 STATIC
187 VOID
188 HufEncodeStart (
189 );
190
191 STATIC
192 VOID
193 HufEncodeEnd (
194 );
195
196 STATIC
197 VOID
198 MakeCrcTable (
199 );
200
201 STATIC
202 VOID
203 PutBits (
204 IN INT32 n,
205 IN UINT32 x
206 );
207
208 STATIC
209 INT32
210 FreadCrc (
211 OUT UINT8 *p,
212 IN INT32 n
213 );
214
215 STATIC
216 VOID
217 InitPutBits (
218 );
219
220 STATIC
221 VOID
222 CountLen (
223 IN INT32 i
224 );
225
226 STATIC
227 VOID
228 MakeLen (
229 IN INT32 Root
230 );
231
232 STATIC
233 VOID
234 DownHeap (
235 IN INT32 i
236 );
237
238 STATIC
239 VOID
240 MakeCode (
241 IN INT32 n,
242 IN UINT8 Len[],
243 OUT UINT16 Code[]
244 );
245
246 STATIC
247 INT32
248 MakeTree (
249 IN INT32 NParm,
250 IN UINT16 FreqParm[],
251 OUT UINT8 LenParm[],
252 OUT UINT16 CodeParm[]
253 );
254
255
256 //
257 // Global Variables
258 //
259
260 STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
261
262 STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
263 STATIC INT16 mHeap[NC + 1];
264 STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
265 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
266 STATIC UINT32 mCompSize, mOrigSize;
267
268 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1],
269 mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1], mCCode[NC],
270 mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
271
272 STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
273
274
275 //
276 // functions
277 //
278
279 EFI_STATUS
EfiCompress(IN UINT8 * SrcBuffer,IN UINT32 SrcSize,IN UINT8 * DstBuffer,IN OUT UINT32 * DstSize)280 EfiCompress (
281 IN UINT8 *SrcBuffer,
282 IN UINT32 SrcSize,
283 IN UINT8 *DstBuffer,
284 IN OUT UINT32 *DstSize
285 )
286 /*++
287
288 Routine Description:
289
290 The main compression routine.
291
292 Arguments:
293
294 SrcBuffer - The buffer storing the source data
295 SrcSize - The size of source data
296 DstBuffer - The buffer to store the compressed data
297 DstSize - On input, the size of DstBuffer; On output,
298 the size of the actual compressed data.
299
300 Returns:
301
302 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
303 DstSize contains the size needed.
304 EFI_SUCCESS - Compression is successful.
305
306 --*/
307 {
308 EFI_STATUS Status = EFI_SUCCESS;
309
310 //
311 // Initializations
312 //
313 mBufSiz = 0;
314 mBuf = NULL;
315 mText = NULL;
316 mLevel = NULL;
317 mChildCount = NULL;
318 mPosition = NULL;
319 mParent = NULL;
320 mPrev = NULL;
321 mNext = NULL;
322
323
324 mSrc = SrcBuffer;
325 mSrcUpperLimit = mSrc + SrcSize;
326 mDst = DstBuffer;
327 mDstUpperLimit = mDst + *DstSize;
328
329 PutDword(0L);
330 PutDword(0L);
331
332 MakeCrcTable ();
333
334 mOrigSize = mCompSize = 0;
335 mCrc = INIT_CRC;
336
337 //
338 // Compress it
339 //
340
341 Status = Encode();
342 if (EFI_ERROR (Status)) {
343 return EFI_OUT_OF_RESOURCES;
344 }
345
346 //
347 // Null terminate the compressed data
348 //
349 if (mDst < mDstUpperLimit) {
350 *mDst++ = 0;
351 }
352
353 //
354 // Fill in compressed size and original size
355 //
356 mDst = DstBuffer;
357 PutDword(mCompSize+1);
358 PutDword(mOrigSize);
359
360 //
361 // Return
362 //
363
364 if (mCompSize + 1 + 8 > *DstSize) {
365 *DstSize = mCompSize + 1 + 8;
366 return EFI_BUFFER_TOO_SMALL;
367 } else {
368 *DstSize = mCompSize + 1 + 8;
369 return EFI_SUCCESS;
370 }
371
372 }
373
374 STATIC
375 VOID
PutDword(IN UINT32 Data)376 PutDword(
377 IN UINT32 Data
378 )
379 /*++
380
381 Routine Description:
382
383 Put a dword to output stream
384
385 Arguments:
386
387 Data - the dword to put
388
389 Returns: (VOID)
390
391 --*/
392 {
393 if (mDst < mDstUpperLimit) {
394 *mDst++ = (UINT8)(((UINT8)(Data )) & 0xff);
395 }
396
397 if (mDst < mDstUpperLimit) {
398 *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);
399 }
400
401 if (mDst < mDstUpperLimit) {
402 *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);
403 }
404
405 if (mDst < mDstUpperLimit) {
406 *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);
407 }
408 }
409
410 STATIC
411 EFI_STATUS
AllocateMemory()412 AllocateMemory ()
413 /*++
414
415 Routine Description:
416
417 Allocate memory spaces for data structures used in compression process
418
419 Argements: (VOID)
420
421 Returns:
422
423 EFI_SUCCESS - Memory is allocated successfully
424 EFI_OUT_OF_RESOURCES - Allocation fails
425
426 --*/
427 {
428 UINT32 i;
429
430 mText = malloc (WNDSIZ * 2 + MAXMATCH);
431 for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
432 mText[i] = 0;
433 }
434
435 mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
436 mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
437 mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
438 mParent = malloc (WNDSIZ * 2 * sizeof(*mParent));
439 mPrev = malloc (WNDSIZ * 2 * sizeof(*mPrev));
440 mNext = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
441
442 mBufSiz = 16 * 1024U;
443 while ((mBuf = malloc(mBufSiz)) == NULL) {
444 mBufSiz = (mBufSiz / 10U) * 9U;
445 if (mBufSiz < 4 * 1024U) {
446 return EFI_OUT_OF_RESOURCES;
447 }
448 }
449 mBuf[0] = 0;
450
451 return EFI_SUCCESS;
452 }
453
454 VOID
FreeMemory()455 FreeMemory ()
456 /*++
457
458 Routine Description:
459
460 Called when compression is completed to free memory previously allocated.
461
462 Arguments: (VOID)
463
464 Returns: (VOID)
465
466 --*/
467 {
468 if (mText) {
469 free (mText);
470 }
471
472 if (mLevel) {
473 free (mLevel);
474 }
475
476 if (mChildCount) {
477 free (mChildCount);
478 }
479
480 if (mPosition) {
481 free (mPosition);
482 }
483
484 if (mParent) {
485 free (mParent);
486 }
487
488 if (mPrev) {
489 free (mPrev);
490 }
491
492 if (mNext) {
493 free (mNext);
494 }
495
496 if (mBuf) {
497 free (mBuf);
498 }
499
500 return;
501 }
502
503
504 STATIC
505 VOID
InitSlide()506 InitSlide ()
507 /*++
508
509 Routine Description:
510
511 Initialize String Info Log data structures
512
513 Arguments: (VOID)
514
515 Returns: (VOID)
516
517 --*/
518 {
519 NODE i;
520
521 for (i = WNDSIZ; i <= WNDSIZ + UINT8_MAX; i++) {
522 mLevel[i] = 1;
523 mPosition[i] = NIL; /* sentinel */
524 }
525 for (i = WNDSIZ; i < WNDSIZ * 2; i++) {
526 mParent[i] = NIL;
527 }
528 mAvail = 1;
529 for (i = 1; i < WNDSIZ - 1; i++) {
530 mNext[i] = (NODE)(i + 1);
531 }
532
533 mNext[WNDSIZ - 1] = NIL;
534 for (i = WNDSIZ * 2; i <= MAX_HASH_VAL; i++) {
535 mNext[i] = NIL;
536 }
537 }
538
539
540 STATIC
541 NODE
Child(IN NODE q,IN UINT8 c)542 Child (
543 IN NODE q,
544 IN UINT8 c
545 )
546 /*++
547
548 Routine Description:
549
550 Find child node given the parent node and the edge character
551
552 Arguments:
553
554 q - the parent node
555 c - the edge character
556
557 Returns:
558
559 The child node (NIL if not found)
560
561 --*/
562 {
563 NODE r;
564
565 r = mNext[HASH(q, c)];
566 mParent[NIL] = q; /* sentinel */
567 while (mParent[r] != q) {
568 r = mNext[r];
569 }
570
571 return r;
572 }
573
574 STATIC
575 VOID
MakeChild(IN NODE q,IN UINT8 c,IN NODE r)576 MakeChild (
577 IN NODE q,
578 IN UINT8 c,
579 IN NODE r
580 )
581 /*++
582
583 Routine Description:
584
585 Create a new child for a given parent node.
586
587 Arguments:
588
589 q - the parent node
590 c - the edge character
591 r - the child node
592
593 Returns: (VOID)
594
595 --*/
596 {
597 NODE h, t;
598
599 h = (NODE)HASH(q, c);
600 t = mNext[h];
601 mNext[h] = r;
602 mNext[r] = t;
603 mPrev[t] = r;
604 mPrev[r] = h;
605 mParent[r] = q;
606 mChildCount[q]++;
607 }
608
609 STATIC
610 VOID
Split(NODE Old)611 Split (
612 NODE Old
613 )
614 /*++
615
616 Routine Description:
617
618 Split a node.
619
620 Arguments:
621
622 Old - the node to split
623
624 Returns: (VOID)
625
626 --*/
627 {
628 NODE New, t;
629
630 New = mAvail;
631 mAvail = mNext[New];
632 mChildCount[New] = 0;
633 t = mPrev[Old];
634 mPrev[New] = t;
635 mNext[t] = New;
636 t = mNext[Old];
637 mNext[New] = t;
638 mPrev[t] = New;
639 mParent[New] = mParent[Old];
640 mLevel[New] = (UINT8)mMatchLen;
641 mPosition[New] = mPos;
642 MakeChild(New, mText[mMatchPos + mMatchLen], Old);
643 MakeChild(New, mText[mPos + mMatchLen], mPos);
644 }
645
646 STATIC
647 VOID
InsertNode()648 InsertNode ()
649 /*++
650
651 Routine Description:
652
653 Insert string info for current position into the String Info Log
654
655 Arguments: (VOID)
656
657 Returns: (VOID)
658
659 --*/
660 {
661 NODE q, r, j, t;
662 UINT8 c, *t1, *t2;
663
664 if (mMatchLen >= 4) {
665
666 //
667 // We have just got a long match, the target tree
668 // can be located by MatchPos + 1. Travese the tree
669 // from bottom up to get to a proper starting point.
670 // The usage of PERC_FLAG ensures proper node deletion
671 // in DeleteNode() later.
672 //
673
674 mMatchLen--;
675 r = (INT16)((mMatchPos + 1) | WNDSIZ);
676 while ((q = mParent[r]) == NIL) {
677 r = mNext[r];
678 }
679 while (mLevel[q] >= mMatchLen) {
680 r = q; q = mParent[q];
681 }
682 t = q;
683 while (mPosition[t] < 0) {
684 mPosition[t] = mPos;
685 t = mParent[t];
686 }
687 if (t < WNDSIZ) {
688 mPosition[t] = (NODE)(mPos | PERC_FLAG);
689 }
690 } else {
691
692 //
693 // Locate the target tree
694 //
695
696 q = (INT16)(mText[mPos] + WNDSIZ);
697 c = mText[mPos + 1];
698 if ((r = Child(q, c)) == NIL) {
699 MakeChild(q, c, mPos);
700 mMatchLen = 1;
701 return;
702 }
703 mMatchLen = 2;
704 }
705
706 //
707 // Traverse down the tree to find a match.
708 // Update Position value along the route.
709 // Node split or creation is involved.
710 //
711
712 for ( ; ; ) {
713 if (r >= WNDSIZ) {
714 j = MAXMATCH;
715 mMatchPos = r;
716 } else {
717 j = mLevel[r];
718 mMatchPos = (NODE)(mPosition[r] & ~PERC_FLAG);
719 }
720 if (mMatchPos >= mPos) {
721 mMatchPos -= WNDSIZ;
722 }
723 t1 = &mText[mPos + mMatchLen];
724 t2 = &mText[mMatchPos + mMatchLen];
725 while (mMatchLen < j) {
726 if (*t1 != *t2) {
727 Split(r);
728 return;
729 }
730 mMatchLen++;
731 t1++;
732 t2++;
733 }
734 if (mMatchLen >= MAXMATCH) {
735 break;
736 }
737 mPosition[r] = mPos;
738 q = r;
739 if ((r = Child(q, *t1)) == NIL) {
740 MakeChild(q, *t1, mPos);
741 return;
742 }
743 mMatchLen++;
744 }
745 t = mPrev[r];
746 mPrev[mPos] = t;
747 mNext[t] = mPos;
748 t = mNext[r];
749 mNext[mPos] = t;
750 mPrev[t] = mPos;
751 mParent[mPos] = q;
752 mParent[r] = NIL;
753
754 //
755 // Special usage of 'next'
756 //
757 mNext[r] = mPos;
758
759 }
760
761 STATIC
762 VOID
DeleteNode()763 DeleteNode ()
764 /*++
765
766 Routine Description:
767
768 Delete outdated string info. (The Usage of PERC_FLAG
769 ensures a clean deletion)
770
771 Arguments: (VOID)
772
773 Returns: (VOID)
774
775 --*/
776 {
777 NODE q, r, s, t, u;
778
779 if (mParent[mPos] == NIL) {
780 return;
781 }
782
783 r = mPrev[mPos];
784 s = mNext[mPos];
785 mNext[r] = s;
786 mPrev[s] = r;
787 r = mParent[mPos];
788 mParent[mPos] = NIL;
789 if (r >= WNDSIZ || --mChildCount[r] > 1) {
790 return;
791 }
792 t = (NODE)(mPosition[r] & ~PERC_FLAG);
793 if (t >= mPos) {
794 t -= WNDSIZ;
795 }
796 s = t;
797 q = mParent[r];
798 while ((u = mPosition[q]) & PERC_FLAG) {
799 u &= ~PERC_FLAG;
800 if (u >= mPos) {
801 u -= WNDSIZ;
802 }
803 if (u > s) {
804 s = u;
805 }
806 mPosition[q] = (INT16)(s | WNDSIZ);
807 q = mParent[q];
808 }
809 if (q < WNDSIZ) {
810 if (u >= mPos) {
811 u -= WNDSIZ;
812 }
813 if (u > s) {
814 s = u;
815 }
816 mPosition[q] = (INT16)(s | WNDSIZ | PERC_FLAG);
817 }
818 s = Child(r, mText[t + mLevel[r]]);
819 t = mPrev[s];
820 u = mNext[s];
821 mNext[t] = u;
822 mPrev[u] = t;
823 t = mPrev[r];
824 mNext[t] = s;
825 mPrev[s] = t;
826 t = mNext[r];
827 mPrev[t] = s;
828 mNext[s] = t;
829 mParent[s] = mParent[r];
830 mParent[r] = NIL;
831 mNext[r] = mAvail;
832 mAvail = r;
833 }
834
835 STATIC
836 VOID
GetNextMatch()837 GetNextMatch ()
838 /*++
839
840 Routine Description:
841
842 Advance the current position (read in new data if needed).
843 Delete outdated string info. Find a match string for current position.
844
845 Arguments: (VOID)
846
847 Returns: (VOID)
848
849 --*/
850 {
851 INT32 n;
852
853 mRemainder--;
854 if (++mPos == WNDSIZ * 2) {
855 memmove(&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
856 n = FreadCrc(&mText[WNDSIZ + MAXMATCH], WNDSIZ);
857 mRemainder += n;
858 mPos = WNDSIZ;
859 }
860 DeleteNode();
861 InsertNode();
862 }
863
864 STATIC
865 EFI_STATUS
Encode()866 Encode ()
867 /*++
868
869 Routine Description:
870
871 The main controlling routine for compression process.
872
873 Arguments: (VOID)
874
875 Returns:
876
877 EFI_SUCCESS - The compression is successful
878 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
879
880 --*/
881 {
882 EFI_STATUS Status;
883 INT32 LastMatchLen;
884 NODE LastMatchPos;
885
886 Status = AllocateMemory();
887 if (EFI_ERROR(Status)) {
888 FreeMemory();
889 return Status;
890 }
891
892 InitSlide();
893
894 HufEncodeStart();
895
896 mRemainder = FreadCrc(&mText[WNDSIZ], WNDSIZ + MAXMATCH);
897
898 mMatchLen = 0;
899 mPos = WNDSIZ;
900 InsertNode();
901 if (mMatchLen > mRemainder) {
902 mMatchLen = mRemainder;
903 }
904 while (mRemainder > 0) {
905 LastMatchLen = mMatchLen;
906 LastMatchPos = mMatchPos;
907 GetNextMatch();
908 if (mMatchLen > mRemainder) {
909 mMatchLen = mRemainder;
910 }
911
912 if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
913
914 //
915 // Not enough benefits are gained by outputting a pointer,
916 // so just output the original character
917 //
918
919 Output(mText[mPos - 1], 0);
920 } else {
921
922 //
923 // Outputting a pointer is beneficial enough, do it.
924 //
925
926 Output(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
927 (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
928 while (--LastMatchLen > 0) {
929 GetNextMatch();
930 }
931 if (mMatchLen > mRemainder) {
932 mMatchLen = mRemainder;
933 }
934 }
935 }
936
937 HufEncodeEnd();
938 FreeMemory();
939 return EFI_SUCCESS;
940 }
941
942 STATIC
943 VOID
CountTFreq()944 CountTFreq ()
945 /*++
946
947 Routine Description:
948
949 Count the frequencies for the Extra Set
950
951 Arguments: (VOID)
952
953 Returns: (VOID)
954
955 --*/
956 {
957 INT32 i, k, n, Count;
958
959 for (i = 0; i < NT; i++) {
960 mTFreq[i] = 0;
961 }
962 n = NC;
963 while (n > 0 && mCLen[n - 1] == 0) {
964 n--;
965 }
966 i = 0;
967 while (i < n) {
968 k = mCLen[i++];
969 if (k == 0) {
970 Count = 1;
971 while (i < n && mCLen[i] == 0) {
972 i++;
973 Count++;
974 }
975 if (Count <= 2) {
976 mTFreq[0] = (UINT16)(mTFreq[0] + Count);
977 } else if (Count <= 18) {
978 mTFreq[1]++;
979 } else if (Count == 19) {
980 mTFreq[0]++;
981 mTFreq[1]++;
982 } else {
983 mTFreq[2]++;
984 }
985 } else {
986 mTFreq[k + 2]++;
987 }
988 }
989 }
990
991 STATIC
992 VOID
WritePTLen(IN INT32 n,IN INT32 nbit,IN INT32 Special)993 WritePTLen (
994 IN INT32 n,
995 IN INT32 nbit,
996 IN INT32 Special
997 )
998 /*++
999
1000 Routine Description:
1001
1002 Outputs the code length array for the Extra Set or the Position Set.
1003
1004 Arguments:
1005
1006 n - the number of symbols
1007 nbit - the number of bits needed to represent 'n'
1008 Special - the special symbol that needs to be take care of
1009
1010 Returns: (VOID)
1011
1012 --*/
1013 {
1014 INT32 i, k;
1015
1016 while (n > 0 && mPTLen[n - 1] == 0) {
1017 n--;
1018 }
1019 PutBits(nbit, n);
1020 i = 0;
1021 while (i < n) {
1022 k = mPTLen[i++];
1023 if (k <= 6) {
1024 PutBits(3, k);
1025 } else {
1026 PutBits(k - 3, (1U << (k - 3)) - 2);
1027 }
1028 if (i == Special) {
1029 while (i < 6 && mPTLen[i] == 0) {
1030 i++;
1031 }
1032 PutBits(2, (i - 3) & 3);
1033 }
1034 }
1035 }
1036
1037 STATIC
1038 VOID
WriteCLen()1039 WriteCLen ()
1040 /*++
1041
1042 Routine Description:
1043
1044 Outputs the code length array for Char&Length Set
1045
1046 Arguments: (VOID)
1047
1048 Returns: (VOID)
1049
1050 --*/
1051 {
1052 INT32 i, k, n, Count;
1053
1054 n = NC;
1055 while (n > 0 && mCLen[n - 1] == 0) {
1056 n--;
1057 }
1058 PutBits(CBIT, n);
1059 i = 0;
1060 while (i < n) {
1061 k = mCLen[i++];
1062 if (k == 0) {
1063 Count = 1;
1064 while (i < n && mCLen[i] == 0) {
1065 i++;
1066 Count++;
1067 }
1068 if (Count <= 2) {
1069 for (k = 0; k < Count; k++) {
1070 PutBits(mPTLen[0], mPTCode[0]);
1071 }
1072 } else if (Count <= 18) {
1073 PutBits(mPTLen[1], mPTCode[1]);
1074 PutBits(4, Count - 3);
1075 } else if (Count == 19) {
1076 PutBits(mPTLen[0], mPTCode[0]);
1077 PutBits(mPTLen[1], mPTCode[1]);
1078 PutBits(4, 15);
1079 } else {
1080 PutBits(mPTLen[2], mPTCode[2]);
1081 PutBits(CBIT, Count - 20);
1082 }
1083 } else {
1084 PutBits(mPTLen[k + 2], mPTCode[k + 2]);
1085 }
1086 }
1087 }
1088
1089 STATIC
1090 VOID
EncodeC(IN INT32 c)1091 EncodeC (
1092 IN INT32 c
1093 )
1094 {
1095 PutBits(mCLen[c], mCCode[c]);
1096 }
1097
1098 STATIC
1099 VOID
EncodeP(IN UINT32 p)1100 EncodeP (
1101 IN UINT32 p
1102 )
1103 {
1104 UINT32 c, q;
1105
1106 c = 0;
1107 q = p;
1108 while (q) {
1109 q >>= 1;
1110 c++;
1111 }
1112 PutBits(mPTLen[c], mPTCode[c]);
1113 if (c > 1) {
1114 PutBits(c - 1, p & (0xFFFFU >> (17 - c)));
1115 }
1116 }
1117
1118 STATIC
1119 VOID
SendBlock()1120 SendBlock ()
1121 /*++
1122
1123 Routine Description:
1124
1125 Huffman code the block and output it.
1126
1127 Argument: (VOID)
1128
1129 Returns: (VOID)
1130
1131 --*/
1132 {
1133 UINT32 i, k, Flags, Root, Pos, Size;
1134 Flags = 0;
1135
1136 Root = MakeTree(NC, mCFreq, mCLen, mCCode);
1137 Size = mCFreq[Root];
1138 PutBits(16, Size);
1139 if (Root >= NC) {
1140 CountTFreq();
1141 Root = MakeTree(NT, mTFreq, mPTLen, mPTCode);
1142 if (Root >= NT) {
1143 WritePTLen(NT, TBIT, 3);
1144 } else {
1145 PutBits(TBIT, 0);
1146 PutBits(TBIT, Root);
1147 }
1148 WriteCLen();
1149 } else {
1150 PutBits(TBIT, 0);
1151 PutBits(TBIT, 0);
1152 PutBits(CBIT, 0);
1153 PutBits(CBIT, Root);
1154 }
1155 Root = MakeTree(NP, mPFreq, mPTLen, mPTCode);
1156 if (Root >= NP) {
1157 WritePTLen(NP, PBIT, -1);
1158 } else {
1159 PutBits(PBIT, 0);
1160 PutBits(PBIT, Root);
1161 }
1162 Pos = 0;
1163 for (i = 0; i < Size; i++) {
1164 if (i % UINT8_BIT == 0) {
1165 Flags = mBuf[Pos++];
1166 } else {
1167 Flags <<= 1;
1168 }
1169 if (Flags & (1U << (UINT8_BIT - 1))) {
1170 EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
1171 k = mBuf[Pos++] << UINT8_BIT;
1172 k += mBuf[Pos++];
1173 EncodeP(k);
1174 } else {
1175 EncodeC(mBuf[Pos++]);
1176 }
1177 }
1178 for (i = 0; i < NC; i++) {
1179 mCFreq[i] = 0;
1180 }
1181 for (i = 0; i < NP; i++) {
1182 mPFreq[i] = 0;
1183 }
1184 }
1185
1186
1187 STATIC
1188 VOID
Output(IN UINT32 c,IN UINT32 p)1189 Output (
1190 IN UINT32 c,
1191 IN UINT32 p
1192 )
1193 /*++
1194
1195 Routine Description:
1196
1197 Outputs an Original Character or a Pointer
1198
1199 Arguments:
1200
1201 c - The original character or the 'String Length' element of a Pointer
1202 p - The 'Position' field of a Pointer
1203
1204 Returns: (VOID)
1205
1206 --*/
1207 {
1208 STATIC UINT32 CPos;
1209
1210 if ((mOutputMask >>= 1) == 0) {
1211 mOutputMask = 1U << (UINT8_BIT - 1);
1212 if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
1213 SendBlock();
1214 mOutputPos = 0;
1215 }
1216 CPos = mOutputPos++;
1217 mBuf[CPos] = 0;
1218 }
1219 mBuf[mOutputPos++] = (UINT8) c;
1220 mCFreq[c]++;
1221 if (c >= (1U << UINT8_BIT)) {
1222 mBuf[CPos] |= mOutputMask;
1223 mBuf[mOutputPos++] = (UINT8)(p >> UINT8_BIT);
1224 mBuf[mOutputPos++] = (UINT8) p;
1225 c = 0;
1226 while (p) {
1227 p >>= 1;
1228 c++;
1229 }
1230 mPFreq[c]++;
1231 }
1232 }
1233
1234 STATIC
1235 VOID
HufEncodeStart()1236 HufEncodeStart ()
1237 {
1238 INT32 i;
1239
1240 for (i = 0; i < NC; i++) {
1241 mCFreq[i] = 0;
1242 }
1243 for (i = 0; i < NP; i++) {
1244 mPFreq[i] = 0;
1245 }
1246 mOutputPos = mOutputMask = 0;
1247 InitPutBits();
1248 return;
1249 }
1250
1251 STATIC
1252 VOID
HufEncodeEnd()1253 HufEncodeEnd ()
1254 {
1255 SendBlock();
1256
1257 //
1258 // Flush remaining bits
1259 //
1260 PutBits(UINT8_BIT - 1, 0);
1261
1262 return;
1263 }
1264
1265
1266 STATIC
1267 VOID
MakeCrcTable()1268 MakeCrcTable ()
1269 {
1270 UINT32 i, j, r;
1271
1272 for (i = 0; i <= UINT8_MAX; i++) {
1273 r = i;
1274 for (j = 0; j < UINT8_BIT; j++) {
1275 if (r & 1) {
1276 r = (r >> 1) ^ CRCPOLY;
1277 } else {
1278 r >>= 1;
1279 }
1280 }
1281 mCrcTable[i] = (UINT16)r;
1282 }
1283 }
1284
1285 STATIC
1286 VOID
PutBits(IN INT32 n,IN UINT32 x)1287 PutBits (
1288 IN INT32 n,
1289 IN UINT32 x
1290 )
1291 /*++
1292
1293 Routine Description:
1294
1295 Outputs rightmost n bits of x
1296
1297 Argments:
1298
1299 n - the rightmost n bits of the data is used
1300 x - the data
1301
1302 Returns: (VOID)
1303
1304 --*/
1305 {
1306 UINT8 Temp;
1307
1308 if (n < mBitCount) {
1309 mSubBitBuf |= x << (mBitCount -= n);
1310 } else {
1311
1312 Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));
1313 if (mDst < mDstUpperLimit) {
1314 *mDst++ = Temp;
1315 }
1316 mCompSize++;
1317
1318 if (n < UINT8_BIT) {
1319 mSubBitBuf = x << (mBitCount = UINT8_BIT - n);
1320 } else {
1321
1322 Temp = (UINT8)(x >> (n - UINT8_BIT));
1323 if (mDst < mDstUpperLimit) {
1324 *mDst++ = Temp;
1325 }
1326 mCompSize++;
1327
1328 mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - n);
1329 }
1330 }
1331 }
1332
1333 STATIC
1334 INT32
FreadCrc(OUT UINT8 * p,IN INT32 n)1335 FreadCrc (
1336 OUT UINT8 *p,
1337 IN INT32 n
1338 )
1339 /*++
1340
1341 Routine Description:
1342
1343 Read in source data
1344
1345 Arguments:
1346
1347 p - the buffer to hold the data
1348 n - number of bytes to read
1349
1350 Returns:
1351
1352 number of bytes actually read
1353
1354 --*/
1355 {
1356 INT32 i;
1357
1358 for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {
1359 *p++ = *mSrc++;
1360 }
1361 n = i;
1362
1363 p -= n;
1364 mOrigSize += n;
1365 while (--i >= 0) {
1366 UPDATE_CRC(*p++);
1367 }
1368 return n;
1369 }
1370
1371
1372 STATIC
1373 VOID
InitPutBits()1374 InitPutBits ()
1375 {
1376 mBitCount = UINT8_BIT;
1377 mSubBitBuf = 0;
1378 }
1379
1380 STATIC
1381 VOID
CountLen(IN INT32 i)1382 CountLen (
1383 IN INT32 i
1384 )
1385 /*++
1386
1387 Routine Description:
1388
1389 Count the number of each code length for a Huffman tree.
1390
1391 Arguments:
1392
1393 i - the top node
1394
1395 Returns: (VOID)
1396
1397 --*/
1398 {
1399 STATIC INT32 Depth = 0;
1400
1401 if (i < mN) {
1402 mLenCnt[(Depth < 16) ? Depth : 16]++;
1403 } else {
1404 Depth++;
1405 CountLen(mLeft [i]);
1406 CountLen(mRight[i]);
1407 Depth--;
1408 }
1409 }
1410
1411 STATIC
1412 VOID
MakeLen(IN INT32 Root)1413 MakeLen (
1414 IN INT32 Root
1415 )
1416 /*++
1417
1418 Routine Description:
1419
1420 Create code length array for a Huffman tree
1421
1422 Arguments:
1423
1424 Root - the root of the tree
1425
1426 --*/
1427 {
1428 INT32 i, k;
1429 UINT32 Cum;
1430
1431 for (i = 0; i <= 16; i++) {
1432 mLenCnt[i] = 0;
1433 }
1434 CountLen(Root);
1435
1436 //
1437 // Adjust the length count array so that
1438 // no code will be generated longer than its designated length
1439 //
1440
1441 Cum = 0;
1442 for (i = 16; i > 0; i--) {
1443 Cum += mLenCnt[i] << (16 - i);
1444 }
1445 while (Cum != (1U << 16)) {
1446 mLenCnt[16]--;
1447 for (i = 15; i > 0; i--) {
1448 if (mLenCnt[i] != 0) {
1449 mLenCnt[i]--;
1450 mLenCnt[i+1] += 2;
1451 break;
1452 }
1453 }
1454 Cum--;
1455 }
1456 for (i = 16; i > 0; i--) {
1457 k = mLenCnt[i];
1458 while (--k >= 0) {
1459 mLen[*mSortPtr++] = (UINT8)i;
1460 }
1461 }
1462 }
1463
1464 STATIC
1465 VOID
DownHeap(IN INT32 i)1466 DownHeap (
1467 IN INT32 i
1468 )
1469 {
1470 INT32 j, k;
1471
1472 //
1473 // priority queue: send i-th entry down heap
1474 //
1475
1476 k = mHeap[i];
1477 while ((j = 2 * i) <= mHeapSize) {
1478 if (j < mHeapSize && mFreq[mHeap[j]] > mFreq[mHeap[j + 1]]) {
1479 j++;
1480 }
1481 if (mFreq[k] <= mFreq[mHeap[j]]) {
1482 break;
1483 }
1484 mHeap[i] = mHeap[j];
1485 i = j;
1486 }
1487 mHeap[i] = (INT16)k;
1488 }
1489
1490 STATIC
1491 VOID
MakeCode(IN INT32 n,IN UINT8 Len[],OUT UINT16 Code[])1492 MakeCode (
1493 IN INT32 n,
1494 IN UINT8 Len[],
1495 OUT UINT16 Code[]
1496 )
1497 /*++
1498
1499 Routine Description:
1500
1501 Assign code to each symbol based on the code length array
1502
1503 Arguments:
1504
1505 n - number of symbols
1506 Len - the code length array
1507 Code - stores codes for each symbol
1508
1509 Returns: (VOID)
1510
1511 --*/
1512 {
1513 INT32 i;
1514 UINT16 Start[18];
1515
1516 Start[1] = 0;
1517 for (i = 1; i <= 16; i++) {
1518 Start[i + 1] = (UINT16)((Start[i] + mLenCnt[i]) << 1);
1519 }
1520 for (i = 0; i < n; i++) {
1521 Code[i] = Start[Len[i]]++;
1522 }
1523 }
1524
1525 STATIC
1526 INT32
MakeTree(IN INT32 NParm,IN UINT16 FreqParm[],OUT UINT8 LenParm[],OUT UINT16 CodeParm[])1527 MakeTree (
1528 IN INT32 NParm,
1529 IN UINT16 FreqParm[],
1530 OUT UINT8 LenParm[],
1531 OUT UINT16 CodeParm[]
1532 )
1533 /*++
1534
1535 Routine Description:
1536
1537 Generates Huffman codes given a frequency distribution of symbols
1538
1539 Arguments:
1540
1541 NParm - number of symbols
1542 FreqParm - frequency of each symbol
1543 LenParm - code length for each symbol
1544 CodeParm - code for each symbol
1545
1546 Returns:
1547
1548 Root of the Huffman tree.
1549
1550 --*/
1551 {
1552 INT32 i, j, k, Avail;
1553
1554 //
1555 // make tree, calculate len[], return root
1556 //
1557
1558 mN = NParm;
1559 mFreq = FreqParm;
1560 mLen = LenParm;
1561 Avail = mN;
1562 mHeapSize = 0;
1563 mHeap[1] = 0;
1564 for (i = 0; i < mN; i++) {
1565 mLen[i] = 0;
1566 if (mFreq[i]) {
1567 mHeap[++mHeapSize] = (INT16)i;
1568 }
1569 }
1570 if (mHeapSize < 2) {
1571 CodeParm[mHeap[1]] = 0;
1572 return mHeap[1];
1573 }
1574 for (i = mHeapSize / 2; i >= 1; i--) {
1575
1576 //
1577 // make priority queue
1578 //
1579 DownHeap(i);
1580 }
1581 mSortPtr = CodeParm;
1582 do {
1583 i = mHeap[1];
1584 if (i < mN) {
1585 *mSortPtr++ = (UINT16)i;
1586 }
1587 mHeap[1] = mHeap[mHeapSize--];
1588 DownHeap(1);
1589 j = mHeap[1];
1590 if (j < mN) {
1591 *mSortPtr++ = (UINT16)j;
1592 }
1593 k = Avail++;
1594 mFreq[k] = (UINT16)(mFreq[i] + mFreq[j]);
1595 mHeap[1] = (INT16)k;
1596 DownHeap(1);
1597 mLeft[k] = (UINT16)i;
1598 mRight[k] = (UINT16)j;
1599 } while (mHeapSize > 1);
1600
1601 mSortPtr = CodeParm;
1602 MakeLen(k);
1603 MakeCode(NParm, LenParm, CodeParm);
1604
1605 //
1606 // return root
1607 //
1608 return k;
1609 }
1610
1611
1612 #ifndef FOR_LIBRARY
main(int argc,char * argv[])1613 int main(int argc, char *argv[])
1614 {
1615 char *progname;
1616 int retval = 1;
1617
1618 progname = strrchr(argv[0], '/');
1619 if (progname)
1620 progname++;
1621 else
1622 progname = argv[0];
1623
1624 if (argc != 3)
1625 {
1626 fprintf(stderr, "\nUsage: %s INFILE OUTFILE\n\n", progname);
1627 exit(1);
1628 }
1629
1630 char *infile = argv[1];
1631 char *outfile = argv[2];
1632
1633 struct stat istat;
1634 if (0 != stat(infile, &istat)) {
1635 fprintf(stderr, "%s: can't stat %s: %s\n",
1636 progname,
1637 infile,
1638 strerror(errno));
1639 exit(1);
1640 }
1641 uint32_t isize = (uint32_t)istat.st_size;
1642
1643 printf("%s is %d bytes\n", infile, isize);
1644
1645 FILE *ifp = fopen(infile, "rb");
1646 if (!ifp)
1647 {
1648 fprintf(stderr, "%s: can't read %s: %s\n",
1649 progname,
1650 infile,
1651 strerror(errno));
1652 exit(1);
1653 }
1654
1655 // read input file into buffer
1656 uint8_t *ibuf = malloc(isize);
1657 if (!ibuf) {
1658 fprintf(stderr, "%s: can't malloc %d bytes: %s\n",
1659 progname,
1660 isize,
1661 strerror(errno));
1662 goto done1;
1663 }
1664 if (1 != fread(ibuf, isize, 1, ifp)) {
1665 fprintf(stderr, "%s: can't read %d bytes: %s\n",
1666 progname,
1667 isize,
1668 strerror(errno));
1669 goto done2;
1670 }
1671
1672 // assume compression will actually work
1673 uint32_t osize = isize;
1674 uint8_t *obuf = malloc(osize);
1675 if (!obuf) {
1676 fprintf(stderr, "%s: can't allocate %d bytes: %s\n",
1677 progname,
1678 osize,
1679 strerror(errno));
1680 goto done2;
1681 }
1682
1683 // try it and see
1684 EFI_STATUS r = EfiCompress(ibuf, isize, obuf, &osize);
1685 if (r != EFI_SUCCESS) {
1686 fprintf(stderr, "%s: compression failed with code %d\n",
1687 progname,
1688 r);
1689 goto done3;
1690 }
1691
1692 printf("Compressed %d bytes to %d bytes\n", isize, osize);
1693
1694 // Write it out
1695 FILE *ofp = fopen(outfile, "wb");
1696 if (!ofp)
1697 {
1698 fprintf(stderr, "%s: can't open %s for writing: %s\n",
1699 progname,
1700 outfile,
1701 strerror(errno));
1702 goto done3;
1703 }
1704
1705 if (1 != fwrite(obuf, osize, 1, ofp)) {
1706 fprintf(stderr, "%s: can't write %d bytes: %s\n",
1707 progname,
1708 osize,
1709 strerror(errno));
1710 goto done4;
1711 }
1712
1713 printf("wrote %d bytes to %s\n", osize, outfile);
1714 retval = 0;
1715
1716 done4:
1717 fclose(ofp);
1718
1719 done3:
1720 free(obuf);
1721
1722 done2:
1723 free(ibuf);
1724
1725 done1:
1726 fclose(ifp);
1727
1728 return retval;
1729 }
1730 #endif // FOR_LIBRARY
1731