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