]> 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
Minor grammatical work--mostly adding periods. Items with ONLY period added did...
[mirror_edk2.git] / MdePkg / Library / BaseUefiDecompressLib / BaseUefiDecompressLib.c
1 /** @file
2 UEFI Decompress Library implementation refer to UEFI specification.
3
4 Copyright (c) 2006 - 2010, Intel Corporation. All rights reserved.<BR>
5 Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
6 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 If TableBits > 16, then ASSERT ().
121
122 @param Sd The global scratch data
123 @param NumOfChar The number of symbols in the symbol set
124 @param BitLen Code length array
125 @param TableBits The width of the mapping table
126 @param Table The table to be created.
127
128 @retval 0 OK.
129 @retval BAD_TABLE The table is corrupted.
130
131 **/
132 UINT16
133 MakeTable (
134 IN SCRATCH_DATA *Sd,
135 IN UINT16 NumOfChar,
136 IN UINT8 *BitLen,
137 IN UINT16 TableBits,
138 OUT UINT16 *Table
139 )
140 {
141 UINT16 Count[17];
142 UINT16 Weight[17];
143 UINT16 Start[18];
144 UINT16 *Pointer;
145 UINT16 Index3;
146 UINT16 Index;
147 UINT16 Len;
148 UINT16 Char;
149 UINT16 JuBits;
150 UINT16 Avail;
151 UINT16 NextCode;
152 UINT16 Mask;
153 UINT16 WordOfStart;
154 UINT16 WordOfCount;
155
156 //
157 // The maximum mapping table width supported by this internal
158 // working function is 16.
159 //
160 ASSERT (TableBits <= 16);
161
162 for (Index = 0; Index <= 16; Index++) {
163 Count[Index] = 0;
164 }
165
166 for (Index = 0; Index < NumOfChar; Index++) {
167 Count[BitLen[Index]]++;
168 }
169
170 Start[0] = 0;
171 Start[1] = 0;
172
173 for (Index = 1; Index <= 16; Index++) {
174 WordOfStart = Start[Index];
175 WordOfCount = Count[Index];
176 Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
177 }
178
179 if (Start[17] != 0) {
180 /*(1U << 16)*/
181 return (UINT16) BAD_TABLE;
182 }
183
184 JuBits = (UINT16) (16 - TableBits);
185
186 Weight[0] = 0;
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 if (Index < Index3) {
202 SetMem16 (Table + Index, (Index3 - Index) * sizeof (*Table), 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 || Len >= 17) {
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 && Avail < (2 * NC - 1)) {
232 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
233 *Pointer = Avail++;
234 }
235
236 if (*Pointer < (2 * NC - 1)) {
237 if ((Index3 & Mask) != 0) {
238 Pointer = &Sd->mRight[*Pointer];
239 } else {
240 Pointer = &Sd->mLeft[*Pointer];
241 }
242 }
243
244 Index3 <<= 1;
245 Index--;
246 }
247
248 *Pointer = Char;
249
250 }
251
252 Start[Len] = NextCode;
253 }
254 //
255 // Succeeds
256 //
257 return 0;
258 }
259
260 /**
261 Decodes a position value.
262
263 Get a position value according to Position Huffman Table.
264
265 @param Sd the global scratch data
266
267 @return The position value decoded.
268
269 **/
270 UINT32
271 DecodeP (
272 IN SCRATCH_DATA *Sd
273 )
274 {
275 UINT16 Val;
276 UINT32 Mask;
277 UINT32 Pos;
278
279 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
280
281 if (Val >= MAXNP) {
282 Mask = 1U << (BITBUFSIZ - 1 - 8);
283
284 do {
285
286 if ((Sd->mBitBuf & Mask) != 0) {
287 Val = Sd->mRight[Val];
288 } else {
289 Val = Sd->mLeft[Val];
290 }
291
292 Mask >>= 1;
293 } while (Val >= MAXNP);
294 }
295 //
296 // Advance what we have read
297 //
298 FillBuf (Sd, Sd->mPTLen[Val]);
299
300 Pos = Val;
301 if (Val > 1) {
302 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
303 }
304
305 return Pos;
306 }
307
308 /**
309 Reads code lengths for the Extra Set or the Position Set.
310
311 Read in the Extra Set or Pointion Set Length Arrary, then
312 generate the Huffman code mapping for them.
313
314 @param Sd The global scratch data.
315 @param nn The number of symbols.
316 @param nbit The number of bits needed to represent nn.
317 @param Special The special symbol that needs to be taken care of.
318
319 @retval 0 OK.
320 @retval BAD_TABLE Table is corrupted.
321
322 **/
323 UINT16
324 ReadPTLen (
325 IN SCRATCH_DATA *Sd,
326 IN UINT16 nn,
327 IN UINT16 nbit,
328 IN UINT16 Special
329 )
330 {
331 UINT16 Number;
332 UINT16 CharC;
333 UINT16 Index;
334 UINT32 Mask;
335
336 //
337 // Read Extra Set Code Length Array size
338 //
339 Number = (UINT16) GetBits (Sd, nbit);
340
341 if (Number == 0) {
342 //
343 // This represents only Huffman code used
344 //
345 CharC = (UINT16) GetBits (Sd, nbit);
346
347 SetMem16 (&Sd->mPTTable[0] , sizeof (Sd->mPTTable), CharC);
348
349 SetMem (Sd->mPTLen, nn, 0);
350
351 return 0;
352 }
353
354 Index = 0;
355
356 while (Index < Number && Index < NPT) {
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 && Index < NPT) {
386 Sd->mPTLen[Index++] = 0;
387 }
388 }
389 }
390
391 while (Index < nn && Index < NPT) {
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 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 SetMem (Sd->mCLen, NC, 0);
426 SetMem16 (&Sd->mCTable[0], sizeof (Sd->mCTable), CharC);
427
428 return ;
429 }
430
431 Index = 0;
432 while (Index < Number && Index < NC) {
433 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
434 if (CharC >= NT) {
435 Mask = 1U << (BITBUFSIZ - 1 - 8);
436
437 do {
438
439 if (Mask & Sd->mBitBuf) {
440 CharC = Sd->mRight[CharC];
441 } else {
442 CharC = Sd->mLeft[CharC];
443 }
444
445 Mask >>= 1;
446
447 } while (CharC >= NT);
448 }
449 //
450 // Advance what we have read
451 //
452 FillBuf (Sd, Sd->mPTLen[CharC]);
453
454 if (CharC <= 2) {
455
456 if (CharC == 0) {
457 CharC = 1;
458 } else if (CharC == 1) {
459 CharC = (UINT16) (GetBits (Sd, 4) + 3);
460 } else if (CharC == 2) {
461 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
462 }
463
464 while ((INT16) (--CharC) >= 0 && Index < NC) {
465 Sd->mCLen[Index++] = 0;
466 }
467
468 } else {
469
470 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
471
472 }
473 }
474
475 SetMem (Sd->mCLen + Index, NC - Index, 0);
476
477 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
478
479 return ;
480 }
481
482 /**
483 Decode a character/length value.
484
485 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
486 Huffman code mapping table for Extra Set, Code&Len Set and
487 Position Set.
488
489 @param Sd The global scratch data.
490
491 @return The value decoded.
492
493 **/
494 UINT16
495 DecodeC (
496 SCRATCH_DATA *Sd
497 )
498 {
499 UINT16 Index2;
500 UINT32 Mask;
501
502 if (Sd->mBlockSize == 0) {
503 //
504 // Starting a new block
505 // Read BlockSize from block header
506 //
507 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
508
509 //
510 // Read in the Extra Set Code Length Arrary,
511 // Generate the Huffman code mapping table for Extra Set.
512 //
513 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
514 if (Sd->mBadTableFlag != 0) {
515 return 0;
516 }
517
518 //
519 // Read in and decode the Char&Len Set Code Length Arrary,
520 // Generate the Huffman code mapping table for Char&Len Set.
521 //
522 ReadCLen (Sd);
523
524 //
525 // Read in the Position Set Code Length Arrary,
526 // Generate the Huffman code mapping table for the Position Set.
527 //
528 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
529 if (Sd->mBadTableFlag != 0) {
530 return 0;
531 }
532 }
533
534 //
535 // Get one code according to Code&Set Huffman Table
536 //
537 Sd->mBlockSize--;
538 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
539
540 if (Index2 >= NC) {
541 Mask = 1U << (BITBUFSIZ - 1 - 12);
542
543 do {
544 if ((Sd->mBitBuf & Mask) != 0) {
545 Index2 = Sd->mRight[Index2];
546 } else {
547 Index2 = Sd->mLeft[Index2];
548 }
549
550 Mask >>= 1;
551 } while (Index2 >= NC);
552 }
553 //
554 // Advance what we have read
555 //
556 FillBuf (Sd, Sd->mCLen[Index2]);
557
558 return Index2;
559 }
560
561 /**
562 Decode the source data and put the resulting data into the destination buffer.
563
564 @param Sd The global scratch data
565
566 **/
567 VOID
568 Decode (
569 SCRATCH_DATA *Sd
570 )
571 {
572 UINT16 BytesRemain;
573 UINT32 DataIdx;
574 UINT16 CharC;
575
576 BytesRemain = (UINT16) (-1);
577
578 DataIdx = 0;
579
580 for (;;) {
581 //
582 // Get one code from mBitBuf
583 //
584 CharC = DecodeC (Sd);
585 if (Sd->mBadTableFlag != 0) {
586 goto Done;
587 }
588
589 if (CharC < 256) {
590 //
591 // Process an Original character
592 //
593 if (Sd->mOutBuf >= Sd->mOrigSize) {
594 goto Done;
595 } else {
596 //
597 // Write orignal character into mDstBase
598 //
599 Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
600 }
601
602 } else {
603 //
604 // Process a Pointer
605 //
606 CharC = (UINT16) (CharC - (BIT8 - THRESHOLD));
607
608 //
609 // Get string length
610 //
611 BytesRemain = CharC;
612
613 //
614 // Locate string position
615 //
616 DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
617
618 //
619 // Write BytesRemain of bytes into mDstBase
620 //
621 BytesRemain--;
622 while ((INT16) (BytesRemain) >= 0) {
623 Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
624 if (Sd->mOutBuf >= Sd->mOrigSize) {
625 goto Done;
626 }
627
628 BytesRemain--;
629 }
630 }
631 }
632
633 Done:
634 return ;
635 }
636
637 /**
638 Given a compressed source buffer, this function retrieves the size of
639 the uncompressed buffer and the size of the scratch buffer required
640 to decompress the compressed source buffer.
641
642 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
643 required to decompress the buffer specified by Source and SourceSize.
644 If the size of the uncompressed buffer or the size of the scratch buffer cannot
645 be determined from the compressed data specified by Source and SourceData,
646 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
647 buffer is returned in DestinationSize, the size of the scratch buffer is returned
648 in ScratchSize, and RETURN_SUCCESS is returned.
649 This function does not have scratch buffer available to perform a thorough
650 checking of the validity of the source data. It just retrieves the "Original Size"
651 field from the beginning bytes of the source data and output it as DestinationSize.
652 And ScratchSize is specific to the decompression implementation.
653
654 If Source is NULL, then ASSERT().
655 If DestinationSize is NULL, then ASSERT().
656 If ScratchSize is NULL, then ASSERT().
657
658 @param Source The source buffer containing the compressed data.
659 @param SourceSize The size, in bytes, of the source buffer.
660 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
661 that will be generated when the compressed buffer specified
662 by Source and SourceSize is decompressed..
663 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
664 is required to decompress the compressed buffer specified
665 by Source and SourceSize.
666
667 @retval RETURN_SUCCESS The size of the uncompressed data was returned
668 in DestinationSize and the size of the scratch
669 buffer was returned in ScratchSize.
670 @retval RETURN_INVALID_PARAMETER
671 The size of the uncompressed data or the size of
672 the scratch buffer cannot be determined from
673 the compressed data specified by Source
674 and SourceSize.
675 **/
676 RETURN_STATUS
677 EFIAPI
678 UefiDecompressGetInfo (
679 IN CONST VOID *Source,
680 IN UINT32 SourceSize,
681 OUT UINT32 *DestinationSize,
682 OUT UINT32 *ScratchSize
683 )
684 {
685 UINT32 CompressedSize;
686
687 ASSERT (Source != NULL);
688 ASSERT (DestinationSize != NULL);
689 ASSERT (ScratchSize != NULL);
690
691 if (SourceSize < 8) {
692 return RETURN_INVALID_PARAMETER;
693 }
694
695 CompressedSize = ReadUnaligned32 ((UINT32 *)Source);
696 if (SourceSize < (CompressedSize + 8)) {
697 return RETURN_INVALID_PARAMETER;
698 }
699
700 *ScratchSize = sizeof (SCRATCH_DATA);
701 *DestinationSize = ReadUnaligned32 ((UINT32 *)Source + 1);
702
703 return RETURN_SUCCESS;
704 }
705
706 /**
707 Decompresses a compressed source buffer.
708
709 Extracts decompressed data to its original form.
710 This function is designed so that the decompression algorithm can be implemented
711 without using any memory services. As a result, this function is not allowed to
712 call any memory allocation services in its implementation. It is the caller's
713 responsibility to allocate and free the Destination and Scratch buffers.
714 If the compressed source data specified by Source is successfully decompressed
715 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
716 specified by Source is not in a valid compressed data format,
717 then RETURN_INVALID_PARAMETER is returned.
718
719 If Source is NULL, then ASSERT().
720 If Destination is NULL, then ASSERT().
721 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
722
723 @param Source The source buffer containing the compressed data.
724 @param Destination The destination buffer to store the decompressed data
725 @param Scratch A temporary scratch buffer that is used to perform the decompression.
726 This is an optional parameter that may be NULL if the
727 required scratch buffer size is 0.
728
729 @retval RETURN_SUCCESS Decompression completed successfully, and
730 the uncompressed buffer is returned in Destination.
731 @retval RETURN_INVALID_PARAMETER
732 The source buffer specified by Source is corrupted
733 (not in a valid compressed format).
734 **/
735 RETURN_STATUS
736 EFIAPI
737 UefiDecompress (
738 IN CONST VOID *Source,
739 IN OUT VOID *Destination,
740 IN OUT VOID *Scratch OPTIONAL
741 )
742 {
743 UINT32 CompSize;
744 UINT32 OrigSize;
745 SCRATCH_DATA *Sd;
746 CONST UINT8 *Src;
747 UINT8 *Dst;
748
749 ASSERT (Source != NULL);
750 ASSERT (Destination != NULL);
751 ASSERT (Scratch != NULL);
752
753 Src = Source;
754 Dst = Destination;
755
756 Sd = (SCRATCH_DATA *) Scratch;
757
758 CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
759 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
760
761 //
762 // If compressed file size is 0, return
763 //
764 if (OrigSize == 0) {
765 return RETURN_SUCCESS;
766 }
767
768 Src = Src + 8;
769 SetMem (Sd, sizeof (SCRATCH_DATA), 0);
770
771 //
772 // The length of the field 'Position Set Code Length Array Size' in Block Header.
773 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
774 //
775 Sd->mPBit = 4;
776 Sd->mSrcBase = (UINT8 *)Src;
777 Sd->mDstBase = Dst;
778 //
779 // CompSize and OrigSize are caculated in bytes
780 //
781 Sd->mCompSize = CompSize;
782 Sd->mOrigSize = OrigSize;
783
784 //
785 // Fill the first BITBUFSIZ bits
786 //
787 FillBuf (Sd, BITBUFSIZ);
788
789 //
790 // Decompress it
791 //
792 Decode (Sd);
793
794 if (Sd->mBadTableFlag != 0) {
795 //
796 // Something wrong with the source
797 //
798 return RETURN_INVALID_PARAMETER;
799 }
800
801 return RETURN_SUCCESS;
802 }
EFI Development Kit II mirror for PVE