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