]> 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
Add check when use Index as Array [Index] to avoid out of Array bound.
[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
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 volatile 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 while (Index != Index3) {
196 Table[Index++] = 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) {
226 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
227 *Pointer = Avail++;
228 }
229
230 if ((Index3 & Mask) != 0) {
231 Pointer = &Sd->mRight[*Pointer];
232 } else {
233 Pointer = &Sd->mLeft[*Pointer];
234 }
235
236 Index3 <<= 1;
237 Index--;
238 }
239
240 *Pointer = Char;
241
242 }
243
244 Start[Len] = NextCode;
245 }
246 //
247 // Succeeds
248 //
249 return 0;
250 }
251
252 /**
253 Decodes a position value.
254
255 Get a position value according to Position Huffman Table.
256
257 @param Sd the global scratch data
258
259 @return The position value decoded.
260
261 **/
262 UINT32
263 DecodeP (
264 IN SCRATCH_DATA *Sd
265 )
266 {
267 UINT16 Val;
268 UINT32 Mask;
269 UINT32 Pos;
270
271 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
272
273 if (Val >= MAXNP) {
274 Mask = 1U << (BITBUFSIZ - 1 - 8);
275
276 do {
277
278 if ((Sd->mBitBuf & Mask) != 0) {
279 Val = Sd->mRight[Val];
280 } else {
281 Val = Sd->mLeft[Val];
282 }
283
284 Mask >>= 1;
285 } while (Val >= MAXNP);
286 }
287 //
288 // Advance what we have read
289 //
290 FillBuf (Sd, Sd->mPTLen[Val]);
291
292 Pos = Val;
293 if (Val > 1) {
294 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
295 }
296
297 return Pos;
298 }
299
300 /**
301 Reads code lengths for the Extra Set or the Position Set.
302
303 Read in the Extra Set or Pointion Set Length Arrary, then
304 generate the Huffman code mapping for them.
305
306 @param Sd The global scratch data.
307 @param nn Number of symbols.
308 @param nbit Number of bits needed to represent nn.
309 @param Special The special symbol that needs to be taken care of.
310
311 @retval 0 OK.
312 @retval BAD_TABLE Table is corrupted.
313
314 **/
315 UINT16
316 ReadPTLen (
317 IN SCRATCH_DATA *Sd,
318 IN UINT16 nn,
319 IN UINT16 nbit,
320 IN UINT16 Special
321 )
322 {
323 UINT16 Number;
324 UINT16 CharC;
325 volatile UINT16 Index;
326 UINT32 Mask;
327
328 //
329 // Read Extra Set Code Length Array size
330 //
331 Number = (UINT16) GetBits (Sd, nbit);
332
333 if (Number == 0) {
334 //
335 // This represents only Huffman code used
336 //
337 CharC = (UINT16) GetBits (Sd, nbit);
338
339 for (Index = 0; Index < 256; Index++) {
340 Sd->mPTTable[Index] = CharC;
341 }
342
343 for (Index = 0; Index < nn; Index++) {
344 Sd->mPTLen[Index] = 0;
345 }
346
347 return 0;
348 }
349
350 Index = 0;
351
352 while (Index < Number && Index < NPT) {
353
354 CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
355
356 //
357 // If a code length is less than 7, then it is encoded as a 3-bit
358 // value. Or it is encoded as a series of "1"s followed by a
359 // terminating "0". The number of "1"s = Code length - 4.
360 //
361 if (CharC == 7) {
362 Mask = 1U << (BITBUFSIZ - 1 - 3);
363 while (Mask & Sd->mBitBuf) {
364 Mask >>= 1;
365 CharC += 1;
366 }
367 }
368
369 FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
370
371 Sd->mPTLen[Index++] = (UINT8) CharC;
372
373 //
374 // For Code&Len Set,
375 // After the third length of the code length concatenation,
376 // a 2-bit value is used to indicated the number of consecutive
377 // zero lengths after the third length.
378 //
379 if (Index == Special) {
380 CharC = (UINT16) GetBits (Sd, 2);
381 while ((INT16) (--CharC) >= 0) {
382 Sd->mPTLen[Index++] = 0;
383 }
384 }
385 }
386
387 while (Index < nn && Index < NPT) {
388 Sd->mPTLen[Index++] = 0;
389 }
390
391 return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
392 }
393
394 /**
395 Reads code lengths for Char&Len Set.
396
397 Read in and decode the Char&Len Set Code Length Array, then
398 generate the Huffman Code mapping table for the Char&Len Set.
399
400 @param Sd the global scratch data
401
402 **/
403 VOID
404 ReadCLen (
405 SCRATCH_DATA *Sd
406 )
407 {
408 UINT16 Number;
409 UINT16 CharC;
410 volatile UINT16 Index;
411 UINT32 Mask;
412
413 Number = (UINT16) GetBits (Sd, CBIT);
414
415 if (Number == 0) {
416 //
417 // This represents only Huffman code used
418 //
419 CharC = (UINT16) GetBits (Sd, CBIT);
420
421 for (Index = 0; Index < NC; Index++) {
422 Sd->mCLen[Index] = 0;
423 }
424
425 for (Index = 0; Index < 4096; Index++) {
426 Sd->mCTable[Index] = CharC;
427 }
428
429 return ;
430 }
431
432 Index = 0;
433 while (Index < Number && Index < NC) {
434 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
435 if (CharC >= NT) {
436 Mask = 1U << (BITBUFSIZ - 1 - 8);
437
438 do {
439
440 if (Mask & Sd->mBitBuf) {
441 CharC = Sd->mRight[CharC];
442 } else {
443 CharC = Sd->mLeft[CharC];
444 }
445
446 Mask >>= 1;
447
448 } while (CharC >= NT);
449 }
450 //
451 // Advance what we have read
452 //
453 FillBuf (Sd, Sd->mPTLen[CharC]);
454
455 if (CharC <= 2) {
456
457 if (CharC == 0) {
458 CharC = 1;
459 } else if (CharC == 1) {
460 CharC = (UINT16) (GetBits (Sd, 4) + 3);
461 } else if (CharC == 2) {
462 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
463 }
464
465 while ((INT16) (--CharC) >= 0) {
466 Sd->mCLen[Index++] = 0;
467 }
468
469 } else {
470
471 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
472
473 }
474 }
475
476 while (Index < NC) {
477 Sd->mCLen[Index++] = 0;
478 }
479
480 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
481
482 return ;
483 }
484
485 /**
486 Decode a character/length value.
487
488 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
489 Huffman code mapping table for Extra Set, Code&Len Set and
490 Position Set.
491
492 @param Sd The global scratch data.
493
494 @return The value decoded.
495
496 **/
497 UINT16
498 DecodeC (
499 SCRATCH_DATA *Sd
500 )
501 {
502 UINT16 Index2;
503 UINT32 Mask;
504
505 if (Sd->mBlockSize == 0) {
506 //
507 // Starting a new block
508 // Read BlockSize from block header
509 //
510 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
511
512 //
513 // Read in the Extra Set Code Length Arrary,
514 // Generate the Huffman code mapping table for Extra Set.
515 //
516 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
517 if (Sd->mBadTableFlag != 0) {
518 return 0;
519 }
520
521 //
522 // Read in and decode the Char&Len Set Code Length Arrary,
523 // Generate the Huffman code mapping table for Char&Len Set.
524 //
525 ReadCLen (Sd);
526
527 //
528 // Read in the Position Set Code Length Arrary,
529 // Generate the Huffman code mapping table for the Position Set.
530 //
531 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
532 if (Sd->mBadTableFlag != 0) {
533 return 0;
534 }
535 }
536
537 //
538 // Get one code according to Code&Set Huffman Table
539 //
540 Sd->mBlockSize--;
541 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
542
543 if (Index2 >= NC) {
544 Mask = 1U << (BITBUFSIZ - 1 - 12);
545
546 do {
547 if ((Sd->mBitBuf & Mask) != 0) {
548 Index2 = Sd->mRight[Index2];
549 } else {
550 Index2 = Sd->mLeft[Index2];
551 }
552
553 Mask >>= 1;
554 } while (Index2 >= NC);
555 }
556 //
557 // Advance what we have read
558 //
559 FillBuf (Sd, Sd->mCLen[Index2]);
560
561 return Index2;
562 }
563
564 /**
565 Decode the source data and put the resulting data into the destination buffer.
566
567 @param Sd The global scratch data
568
569 **/
570 VOID
571 Decode (
572 SCRATCH_DATA *Sd
573 )
574 {
575 UINT16 BytesRemain;
576 UINT32 DataIdx;
577 UINT16 CharC;
578
579 BytesRemain = (UINT16) (-1);
580
581 DataIdx = 0;
582
583 for (;;) {
584 //
585 // Get one code from mBitBuf
586 //
587 CharC = DecodeC (Sd);
588 if (Sd->mBadTableFlag != 0) {
589 goto Done;
590 }
591
592 if (CharC < 256) {
593 //
594 // Process an Original character
595 //
596 if (Sd->mOutBuf >= Sd->mOrigSize) {
597 goto Done;
598 } else {
599 //
600 // Write orignal character into mDstBase
601 //
602 Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
603 }
604
605 } else {
606 //
607 // Process a Pointer
608 //
609 CharC = (UINT16) (CharC - (BIT8 - THRESHOLD));
610
611 //
612 // Get string length
613 //
614 BytesRemain = CharC;
615
616 //
617 // Locate string position
618 //
619 DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
620
621 //
622 // Write BytesRemain of bytes into mDstBase
623 //
624 BytesRemain--;
625 while ((INT16) (BytesRemain) >= 0) {
626 Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
627 if (Sd->mOutBuf >= Sd->mOrigSize) {
628 goto Done;
629 }
630
631 BytesRemain--;
632 }
633 }
634 }
635
636 Done:
637 return ;
638 }
639
640 /**
641 Given a compressed source buffer, this function retrieves the size of
642 the uncompressed buffer and the size of the scratch buffer required
643 to decompress the compressed source buffer.
644
645 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
646 required to decompress the buffer specified by Source and SourceSize.
647 If the size of the uncompressed buffer or the size of the scratch buffer cannot
648 be determined from the compressed data specified by Source and SourceData,
649 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
650 buffer is returned in DestinationSize, the size of the scratch buffer is returned
651 in ScratchSize, and RETURN_SUCCESS is returned.
652 This function does not have scratch buffer available to perform a thorough
653 checking of the validity of the source data. It just retrieves the "Original Size"
654 field from the beginning bytes of the source data and output it as DestinationSize.
655 And ScratchSize is specific to the decompression implementation.
656
657 If Source is NULL, then ASSERT().
658 If DestinationSize is NULL, then ASSERT().
659 If ScratchSize is NULL, then ASSERT().
660
661 @param Source The source buffer containing the compressed data.
662 @param SourceSize The size, in bytes, of the source buffer.
663 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
664 that will be generated when the compressed buffer specified
665 by Source and SourceSize is decompressed..
666 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
667 is required to decompress the compressed buffer specified
668 by Source and SourceSize.
669
670 @retval RETURN_SUCCESS The size of the uncompressed data was returned
671 in DestinationSize and the size of the scratch
672 buffer was returned in ScratchSize.
673 @retval RETURN_INVALID_PARAMETER
674 The size of the uncompressed data or the size of
675 the scratch buffer cannot be determined from
676 the compressed data specified by Source
677 and SourceSize.
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 if (SourceSize < 8) {
695 return RETURN_INVALID_PARAMETER;
696 }
697
698 CompressedSize = ReadUnaligned32 ((UINT32 *)Source);
699 if (SourceSize < (CompressedSize + 8)) {
700 return RETURN_INVALID_PARAMETER;
701 }
702
703 *ScratchSize = sizeof (SCRATCH_DATA);
704 *DestinationSize = ReadUnaligned32 ((UINT32 *)Source + 1);
705
706 return RETURN_SUCCESS;
707 }
708
709 /**
710 Decompresses a compressed source buffer.
711
712 Extracts decompressed data to its original form.
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 completed successfully, and
733 the uncompressed buffer is returned in Destination.
734 @retval RETURN_INVALID_PARAMETER
735 The source buffer specified by Source is corrupted
736 (not in a valid compressed format).
737 **/
738 RETURN_STATUS
739 EFIAPI
740 UefiDecompress (
741 IN CONST VOID *Source,
742 IN OUT VOID *Destination,
743 IN OUT VOID *Scratch OPTIONAL
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 UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
780 //
781 Sd->mPBit = 4;
782 Sd->mSrcBase = (UINT8 *)Src;
783 Sd->mDstBase = Dst;
784 //
785 // CompSize and OrigSize are caculated in bytes
786 //
787 Sd->mCompSize = CompSize;
788 Sd->mOrigSize = OrigSize;
789
790 //
791 // Fill the first BITBUFSIZ bits
792 //
793 FillBuf (Sd, BITBUFSIZ);
794
795 //
796 // Decompress it
797 //
798 Decode (Sd);
799
800 if (Sd->mBadTableFlag != 0) {
801 //
802 // Something wrong with the source
803 //
804 return RETURN_INVALID_PARAMETER;
805 }
806
807 return RETURN_SUCCESS;
808 }
EFI Development Kit II mirror for PVE