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