acde4d503e3eb8f4619975bfcda72364643374cc
[mirror_edk2.git] / IntelFrameworkModulePkg / Library / BaseUefiTianoCustomDecompressLib / BaseUefiTianoCustomDecompressLib.c
1 /**@file
2 UEFI and Custom Decompress Library
3
4 Copyright (c) 2006, Intel Corporation
5 All rights reserved. This program and the accompanying materials
6 are licensed and made available under the terms and conditions of the BSD License
7 which accompanies this distribution. The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php
9
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
12
13 **/
14
15 #include "BaseUefiTianoCustomDecompressLibInternals.h"
16
17 VOID
18 FillBuf (
19 IN SCRATCH_DATA *Sd,
20 IN UINT16 NumOfBits
21 )
22 /*++
23
24 Routine Description:
25
26 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
27
28 Arguments:
29
30 Sd - The global scratch data
31 NumOfBits - The number of bits to shift and read.
32
33 Returns: (VOID)
34
35 --*/
36 {
37 Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
38
39 while (NumOfBits > Sd->mBitCount) {
40
41 Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
42
43 if (Sd->mCompSize > 0) {
44 //
45 // Get 1 byte into SubBitBuf
46 //
47 Sd->mCompSize--;
48 Sd->mSubBitBuf = 0;
49 Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++];
50 Sd->mBitCount = 8;
51
52 } else {
53 //
54 // No more bits from the source, just pad zero bit.
55 //
56 Sd->mSubBitBuf = 0;
57 Sd->mBitCount = 8;
58
59 }
60 }
61
62 Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
63 Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
64 }
65
66 UINT32
67 GetBits (
68 IN SCRATCH_DATA *Sd,
69 IN UINT16 NumOfBits
70 )
71 /*++
72
73 Routine Description:
74
75 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
76 NumOfBits of bits from source. Returns NumOfBits of bits that are
77 popped out.
78
79 Arguments:
80
81 Sd - The global scratch data.
82 NumOfBits - The number of bits to pop and read.
83
84 Returns:
85
86 The bits that are popped out.
87
88 --*/
89 {
90 UINT32 OutBits;
91
92 OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
93
94 FillBuf (Sd, NumOfBits);
95
96 return OutBits;
97 }
98
99 UINT16
100 MakeTable (
101 IN SCRATCH_DATA *Sd,
102 IN UINT16 NumOfChar,
103 IN UINT8 *BitLen,
104 IN UINT16 TableBits,
105 OUT UINT16 *Table
106 )
107 /*++
108
109 Routine Description:
110
111 Creates Huffman Code mapping table according to code length array.
112
113 Arguments:
114
115 Sd - The global scratch data
116 NumOfChar - Number of symbols in the symbol set
117 BitLen - Code length array
118 TableBits - The width of the mapping table
119 Table - The table
120
121 Returns:
122
123 0 - OK.
124 BAD_TABLE - The table is corrupted.
125
126 --*/
127 {
128 UINT16 Count[17];
129 UINT16 Weight[17];
130 UINT16 Start[18];
131 UINT16 *Pointer;
132 UINT16 Index3;
133 volatile UINT16 Index;
134 UINT16 Len;
135 UINT16 Char;
136 UINT16 JuBits;
137 UINT16 Avail;
138 UINT16 NextCode;
139 UINT16 Mask;
140 UINT16 WordOfStart;
141 UINT16 WordOfCount;
142
143 for (Index = 1; Index <= 16; Index++) {
144 Count[Index] = 0;
145 }
146
147 for (Index = 0; Index < NumOfChar; Index++) {
148 Count[BitLen[Index]]++;
149 }
150
151 Start[1] = 0;
152
153 for (Index = 1; Index <= 16; Index++) {
154 WordOfStart = Start[Index];
155 WordOfCount = Count[Index];
156 Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
157 }
158
159 if (Start[17] != 0) {
160 /*(1U << 16)*/
161 return (UINT16) BAD_TABLE;
162 }
163
164 JuBits = (UINT16) (16 - TableBits);
165
166 for (Index = 1; Index <= TableBits; Index++) {
167 Start[Index] >>= JuBits;
168 Weight[Index] = (UINT16) (1U << (TableBits - Index));
169 }
170
171 while (Index <= 16) {
172 Weight[Index] = (UINT16) (1U << (16 - Index));
173 Index++;
174 }
175
176 Index = (UINT16) (Start[TableBits + 1] >> JuBits);
177
178 if (Index != 0) {
179 Index3 = (UINT16) (1U << TableBits);
180 while (Index != Index3) {
181 Table[Index++] = 0;
182 }
183 }
184
185 Avail = NumOfChar;
186 Mask = (UINT16) (1U << (15 - TableBits));
187
188 for (Char = 0; Char < NumOfChar; Char++) {
189
190 Len = BitLen[Char];
191 if (Len == 0) {
192 continue;
193 }
194
195 NextCode = (UINT16) (Start[Len] + Weight[Len]);
196
197 if (Len <= TableBits) {
198
199 for (Index = Start[Len]; Index < NextCode; Index++) {
200 Table[Index] = Char;
201 }
202
203 } else {
204
205 Index3 = Start[Len];
206 Pointer = &Table[Index3 >> JuBits];
207 Index = (UINT16) (Len - TableBits);
208
209 while (Index != 0) {
210 if (*Pointer == 0) {
211 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
212 *Pointer = Avail++;
213 }
214
215 if (Index3 & Mask) {
216 Pointer = &Sd->mRight[*Pointer];
217 } else {
218 Pointer = &Sd->mLeft[*Pointer];
219 }
220
221 Index3 <<= 1;
222 Index--;
223 }
224
225 *Pointer = Char;
226
227 }
228
229 Start[Len] = NextCode;
230 }
231 //
232 // Succeeds
233 //
234 return 0;
235 }
236
237 UINT32
238 DecodeP (
239 IN SCRATCH_DATA *Sd
240 )
241 /*++
242
243 Routine Description:
244
245 Decodes a position value.
246
247 Arguments:
248
249 Sd - the global scratch data
250
251 Returns:
252
253 The position value decoded.
254
255 --*/
256 {
257 UINT16 Val;
258 UINT32 Mask;
259 UINT32 Pos;
260
261 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
262
263 if (Val >= MAXNP) {
264 Mask = 1U << (BITBUFSIZ - 1 - 8);
265
266 do {
267
268 if (Sd->mBitBuf & Mask) {
269 Val = Sd->mRight[Val];
270 } else {
271 Val = Sd->mLeft[Val];
272 }
273
274 Mask >>= 1;
275 } while (Val >= MAXNP);
276 }
277 //
278 // Advance what we have read
279 //
280 FillBuf (Sd, Sd->mPTLen[Val]);
281
282 Pos = Val;
283 if (Val > 1) {
284 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
285 }
286
287 return Pos;
288 }
289
290 UINT16
291 ReadPTLen (
292 IN SCRATCH_DATA *Sd,
293 IN UINT16 nn,
294 IN UINT16 nbit,
295 IN UINT16 Special
296 )
297 /*++
298
299 Routine Description:
300
301 Reads code lengths for the Extra Set or the Position Set
302
303 Arguments:
304
305 Sd - The global scratch data
306 nn - Number of symbols
307 nbit - Number of bits needed to represent nn
308 Special - The special symbol that needs to be taken care of
309
310 Returns:
311
312 0 - OK.
313 BAD_TABLE - Table is corrupted.
314
315 --*/
316 {
317 UINT16 Number;
318 UINT16 CharC;
319 volatile UINT16 Index;
320 UINT32 Mask;
321
322 Number = (UINT16) GetBits (Sd, nbit);
323
324 if (Number == 0) {
325 CharC = (UINT16) GetBits (Sd, nbit);
326
327 for (Index = 0; Index < 256; Index++) {
328 Sd->mPTTable[Index] = CharC;
329 }
330
331 for (Index = 0; Index < nn; Index++) {
332 Sd->mPTLen[Index] = 0;
333 }
334
335 return 0;
336 }
337
338 Index = 0;
339
340 while (Index < Number) {
341
342 CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
343
344 if (CharC == 7) {
345 Mask = 1U << (BITBUFSIZ - 1 - 3);
346 while (Mask & Sd->mBitBuf) {
347 Mask >>= 1;
348 CharC += 1;
349 }
350 }
351
352 FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
353
354 Sd->mPTLen[Index++] = (UINT8) CharC;
355
356 if (Index == Special) {
357 CharC = (UINT16) GetBits (Sd, 2);
358 while ((INT16) (--CharC) >= 0) {
359 Sd->mPTLen[Index++] = 0;
360 }
361 }
362 }
363
364 while (Index < nn) {
365 Sd->mPTLen[Index++] = 0;
366 }
367
368 return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
369 }
370
371 VOID
372 ReadCLen (
373 SCRATCH_DATA *Sd
374 )
375 /*++
376
377 Routine Description:
378
379 Reads code lengths for Char&Len Set.
380
381 Arguments:
382
383 Sd - the global scratch data
384
385 Returns: (VOID)
386
387 --*/
388 {
389 UINT16 Number;
390 UINT16 CharC;
391 volatile UINT16 Index;
392 UINT32 Mask;
393
394 Number = (UINT16) GetBits (Sd, CBIT);
395
396 if (Number == 0) {
397 CharC = (UINT16) GetBits (Sd, CBIT);
398
399 for (Index = 0; Index < NC; Index++) {
400 Sd->mCLen[Index] = 0;
401 }
402
403 for (Index = 0; Index < 4096; Index++) {
404 Sd->mCTable[Index] = CharC;
405 }
406
407 return ;
408 }
409
410 Index = 0;
411 while (Index < Number) {
412
413 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
414 if (CharC >= NT) {
415 Mask = 1U << (BITBUFSIZ - 1 - 8);
416
417 do {
418
419 if (Mask & Sd->mBitBuf) {
420 CharC = Sd->mRight[CharC];
421 } else {
422 CharC = Sd->mLeft[CharC];
423 }
424
425 Mask >>= 1;
426
427 } while (CharC >= NT);
428 }
429 //
430 // Advance what we have read
431 //
432 FillBuf (Sd, Sd->mPTLen[CharC]);
433
434 if (CharC <= 2) {
435
436 if (CharC == 0) {
437 CharC = 1;
438 } else if (CharC == 1) {
439 CharC = (UINT16) (GetBits (Sd, 4) + 3);
440 } else if (CharC == 2) {
441 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
442 }
443
444 while ((INT16) (--CharC) >= 0) {
445 Sd->mCLen[Index++] = 0;
446 }
447
448 } else {
449
450 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
451
452 }
453 }
454
455 while (Index < NC) {
456 Sd->mCLen[Index++] = 0;
457 }
458
459 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
460
461 return ;
462 }
463
464 UINT16
465 DecodeC (
466 SCRATCH_DATA *Sd
467 )
468 /*++
469
470 Routine Description:
471
472 Decode a character/length value.
473
474 Arguments:
475
476 Sd - The global scratch data.
477
478 Returns:
479
480 The value decoded.
481
482 --*/
483 {
484 UINT16 Index2;
485 UINT32 Mask;
486
487 if (Sd->mBlockSize == 0) {
488 //
489 // Starting a new block
490 //
491 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
492 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
493 if (Sd->mBadTableFlag != 0) {
494 return 0;
495 }
496
497 ReadCLen (Sd);
498
499 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
500 if (Sd->mBadTableFlag != 0) {
501 return 0;
502 }
503 }
504
505 Sd->mBlockSize--;
506 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
507
508 if (Index2 >= NC) {
509 Mask = 1U << (BITBUFSIZ - 1 - 12);
510
511 do {
512 if (Sd->mBitBuf & Mask) {
513 Index2 = Sd->mRight[Index2];
514 } else {
515 Index2 = Sd->mLeft[Index2];
516 }
517
518 Mask >>= 1;
519 } while (Index2 >= NC);
520 }
521 //
522 // Advance what we have read
523 //
524 FillBuf (Sd, Sd->mCLen[Index2]);
525
526 return Index2;
527 }
528
529 VOID
530 Decode (
531 SCRATCH_DATA *Sd
532 )
533 /*++
534
535 Routine Description:
536
537 Decode the source data and put the resulting data into the destination buffer.
538
539 Arguments:
540
541 Sd - The global scratch data
542
543 Returns: (VOID)
544
545 --*/
546 {
547 UINT16 BytesRemain;
548 UINT32 DataIdx;
549 UINT16 CharC;
550
551 BytesRemain = (UINT16) (-1);
552
553 DataIdx = 0;
554
555 for (;;) {
556 CharC = DecodeC (Sd);
557 if (Sd->mBadTableFlag != 0) {
558 goto Done ;
559 }
560
561 if (CharC < 256) {
562 //
563 // Process an Original character
564 //
565 if (Sd->mOutBuf >= Sd->mOrigSize) {
566 goto Done ;
567 } else {
568 Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
569 }
570
571 } else {
572 //
573 // Process a Pointer
574 //
575 CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
576
577 BytesRemain = CharC;
578
579 DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
580
581 BytesRemain--;
582 while ((INT16) (BytesRemain) >= 0) {
583 Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
584 if (Sd->mOutBuf >= Sd->mOrigSize) {
585 goto Done ;
586 }
587
588 BytesRemain--;
589 }
590 }
591 }
592
593 Done:
594 return ;
595 }
596
597 RETURN_STATUS
598 EFIAPI
599 UefiDecompressGetInfo (
600 IN CONST VOID *Source,
601 IN UINT32 SourceSize,
602 OUT UINT32 *DestinationSize,
603 OUT UINT32 *ScratchSize
604 )
605 /*++
606
607 Routine Description:
608
609 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
610
611 Arguments:
612
613 Source - The source buffer containing the compressed data.
614 SourceSize - The size of source buffer
615 DestinationSize - The size of destination buffer.
616 ScratchSize - The size of scratch buffer.
617
618 Returns:
619
620 RETURN_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
621 RETURN_INVALID_PARAMETER - The source data is corrupted
622
623 --*/
624 {
625 UINT32 CompressedSize;
626
627 ASSERT (Source != NULL);
628 ASSERT (DestinationSize != NULL);
629 ASSERT (ScratchSize != NULL);
630
631 *ScratchSize = sizeof (SCRATCH_DATA);
632
633 if (SourceSize < 8) {
634 return RETURN_INVALID_PARAMETER;
635 }
636
637 CopyMem (&CompressedSize, Source, sizeof (UINT32));
638 CopyMem (DestinationSize, (VOID *)((UINT8 *)Source + 4), sizeof (UINT32));
639
640 if (SourceSize < (CompressedSize + 8)) {
641 return RETURN_INVALID_PARAMETER;
642 }
643
644 return RETURN_SUCCESS;
645 }
646
647 RETURN_STATUS
648 EFIAPI
649 UefiTianoDecompress (
650 IN CONST VOID *Source,
651 IN OUT VOID *Destination,
652 IN OUT VOID *Scratch,
653 IN UINT32 Version
654 )
655 /*++
656
657 Routine Description:
658
659 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
660
661 Arguments:
662
663 Source - The source buffer containing the compressed data.
664 Destination - The destination buffer to store the decompressed data
665 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
666 Version - 1 for UEFI Decompress algoruthm, 2 for Tiano Decompess algorithm
667
668 Returns:
669
670 RETURN_SUCCESS - Decompression is successfull
671 RETURN_INVALID_PARAMETER - The source data is corrupted
672
673 --*/
674 {
675 volatile UINT32 Index;
676 UINT32 CompSize;
677 UINT32 OrigSize;
678 SCRATCH_DATA *Sd;
679 CONST UINT8 *Src;
680 UINT8 *Dst;
681
682 ASSERT (Source != NULL);
683 ASSERT (Destination != NULL);
684 ASSERT (Scratch != NULL);
685
686 Src = Source;
687 Dst = Destination;
688
689 Sd = (SCRATCH_DATA *) Scratch;
690
691 CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
692 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
693
694 //
695 // If compressed file size is 0, return
696 //
697 if (OrigSize == 0) {
698 return RETURN_SUCCESS;
699 }
700
701 Src = Src + 8;
702
703 for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
704 ((UINT8 *) Sd)[Index] = 0;
705 }
706 //
707 // The length of the field 'Position Set Code Length Array Size' in Block Header.
708 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
709 // For Tiano de/compression algorithm(Version 2), mPBit = 5
710 //
711 switch (Version) {
712 case 1 :
713 Sd->mPBit = 4;
714 break;
715 case 2 :
716 Sd->mPBit = 5;
717 break;
718 default:
719 ASSERT (FALSE);
720 }
721 Sd->mSrcBase = (UINT8 *)Src;
722 Sd->mDstBase = Dst;
723 Sd->mCompSize = CompSize;
724 Sd->mOrigSize = OrigSize;
725
726 //
727 // Fill the first BITBUFSIZ bits
728 //
729 FillBuf (Sd, BITBUFSIZ);
730
731 //
732 // Decompress it
733 //
734 Decode (Sd);
735
736 if (Sd->mBadTableFlag != 0) {
737 //
738 // Something wrong with the source
739 //
740 return RETURN_INVALID_PARAMETER;
741 }
742
743 return RETURN_SUCCESS;
744 }
745
746 RETURN_STATUS
747 EFIAPI
748 UefiDecompress (
749 IN CONST VOID *Source,
750 IN OUT VOID *Destination,
751 IN OUT VOID *Scratch
752 )
753 /*++
754
755 Routine Description:
756
757 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
758
759 Arguments:
760
761 Source - The source buffer containing the compressed data.
762 Destination - The destination buffer to store the decompressed data
763 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
764
765 Returns:
766
767 RETURN_SUCCESS - Decompression is successfull
768 RETURN_INVALID_PARAMETER - The source data is corrupted
769
770 --*/
771 {
772 return UefiTianoDecompress (Source, Destination, Scratch, 1);
773 }
774
775 RETURN_STATUS
776 EFIAPI
777 CustomDecompressGetInfo (
778 IN CONST VOID *Source,
779 IN UINT32 SourceSize,
780 OUT UINT32 *DestinationSize,
781 OUT UINT32 *ScratchSize
782 )
783 /*++
784
785 Routine Description:
786
787 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
788
789 Arguments:
790
791 Source - The source buffer containing the compressed data.
792 SourceSize - The size of source buffer
793 DestinationSize - The size of destination buffer.
794 ScratchSize - The size of scratch buffer.
795
796 Returns:
797
798 RETURN_SUCCESS - The size of destination buffer and the size of scratch buffer are successull retrieved.
799 RETURN_INVALID_PARAMETER - The source data is corrupted
800
801 --*/
802 {
803 return UefiDecompressGetInfo (Source, SourceSize, DestinationSize, ScratchSize);
804 }
805
806 RETURN_STATUS
807 EFIAPI
808 CustomDecompress (
809 IN CONST VOID *Source,
810 IN OUT VOID *Destination,
811 IN OUT VOID *Scratch
812 )
813 /*++
814
815 Routine Description:
816
817 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
818
819 Arguments:
820
821 Source - The source buffer containing the compressed data.
822 Destination - The destination buffer to store the decompressed data
823 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
824
825 Returns:
826
827 RETURN_SUCCESS - Decompression is successfull
828 RETURN_INVALID_PARAMETER - The source data is corrupted
829
830 --*/
831 {
832 return UefiTianoDecompress (Source, Destination, Scratch, 2);
833 }