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