]> git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
projects / mirror_edk2.git / blob
? search:


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