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