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


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