]> 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 some comments introduced by tools.
[mirror_edk2.git] / MdePkg / Library / BaseUefiDecompressLib / BaseUefiDecompressLib.c
1 /** @file
2 UEFI Decompress Library.
3
4 Copyright (c) 2006, 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/UefiDecompressLib.h>
20 #include <Library/DebugLib.h>
21 #include <Library/BaseMemoryLib.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
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 = 1; Index <= 16; Index++) {
157 Count[Index] = 0;
158 }
159
160 for (Index = 0; Index < NumOfChar; Index++) {
161 Count[BitLen[Index]]++;
162 }
163
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 for (Index = 1; Index <= TableBits; Index++) {
180 Start[Index] >>= JuBits;
181 Weight[Index] = (UINT16) (1U << (TableBits - Index));
182 }
183
184 while (Index <= 16) {
185 Weight[Index] = (UINT16) (1U << (16 - Index));
186 Index++;
187 }
188
189 Index = (UINT16) (Start[TableBits + 1] >> JuBits);
190
191 if (Index != 0) {
192 Index3 = (UINT16) (1U << TableBits);
193 while (Index != Index3) {
194 Table[Index++] = 0;
195 }
196 }
197
198 Avail = NumOfChar;
199 Mask = (UINT16) (1U << (15 - TableBits));
200
201 for (Char = 0; Char < NumOfChar; Char++) {
202
203 Len = BitLen[Char];
204 if (Len == 0) {
205 continue;
206 }
207
208 NextCode = (UINT16) (Start[Len] + Weight[Len]);
209
210 if (Len <= TableBits) {
211
212 for (Index = Start[Len]; Index < NextCode; Index++) {
213 Table[Index] = Char;
214 }
215
216 } else {
217
218 Index3 = Start[Len];
219 Pointer = &Table[Index3 >> JuBits];
220 Index = (UINT16) (Len - TableBits);
221
222 while (Index != 0) {
223 if (*Pointer == 0) {
224 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
225 *Pointer = Avail++;
226 }
227
228 if (Index3 & Mask) {
229 Pointer = &Sd->mRight[*Pointer];
230 } else {
231 Pointer = &Sd->mLeft[*Pointer];
232 }
233
234 Index3 <<= 1;
235 Index--;
236 }
237
238 *Pointer = Char;
239
240 }
241
242 Start[Len] = NextCode;
243 }
244 //
245 // Succeeds
246 //
247 return 0;
248 }
249
250 /**
251 Decodes a position value.
252
253 Get a position value according to Position Huffman Table.
254
255 @param Sd the global scratch data
256
257 @return The position value decoded.
258
259 **/
260 UINT32
261 DecodeP (
262 IN SCRATCH_DATA *Sd
263 )
264 {
265 UINT16 Val;
266 UINT32 Mask;
267 UINT32 Pos;
268
269 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
270
271 if (Val >= MAXNP) {
272 Mask = 1U << (BITBUFSIZ - 1 - 8);
273
274 do {
275
276 if (Sd->mBitBuf & Mask) {
277 Val = Sd->mRight[Val];
278 } else {
279 Val = Sd->mLeft[Val];
280 }
281
282 Mask >>= 1;
283 } while (Val >= MAXNP);
284 }
285 //
286 // Advance what we have read
287 //
288 FillBuf (Sd, Sd->mPTLen[Val]);
289
290 Pos = Val;
291 if (Val > 1) {
292 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
293 }
294
295 return Pos;
296 }
297
298 /**
299 Reads code lengths for the Extra Set or the Position Set.
300
301 Read in the Extra Set or Pointion Set Length Arrary, then
302 generate the Huffman code mapping for them.
303
304 @param Sd The global scratch data.
305 @param nn Number of symbols.
306 @param nbit Number of bits needed to represent nn.
307 @param Special The special symbol that needs to be taken care of.
308
309 @retval 0 OK.
310 @retval BAD_TABLE Table is corrupted.
311
312 **/
313 UINT16
314 ReadPTLen (
315 IN SCRATCH_DATA *Sd,
316 IN UINT16 nn,
317 IN UINT16 nbit,
318 IN UINT16 Special
319 )
320 {
321 UINT16 Number;
322 UINT16 CharC;
323 volatile UINT16 Index;
324 UINT32 Mask;
325
326 //
327 // Read Extra Set Code Length Array size
328 //
329 Number = (UINT16) GetBits (Sd, nbit);
330
331 if (Number == 0) {
332 //
333 // This represents only Huffman code used
334 //
335 CharC = (UINT16) GetBits (Sd, nbit);
336
337 for (Index = 0; Index < 256; Index++) {
338 Sd->mPTTable[Index] = CharC;
339 }
340
341 for (Index = 0; Index < nn; Index++) {
342 Sd->mPTLen[Index] = 0;
343 }
344
345 return 0;
346 }
347
348 Index = 0;
349
350 while (Index < Number) {
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) {
380 Sd->mPTLen[Index++] = 0;
381 }
382 }
383 }
384
385 while (Index < nn) {
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 volatile 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 for (Index = 0; Index < NC; Index++) {
420 Sd->mCLen[Index] = 0;
421 }
422
423 for (Index = 0; Index < 4096; Index++) {
424 Sd->mCTable[Index] = CharC;
425 }
426
427 return ;
428 }
429
430 Index = 0;
431 while (Index < Number) {
432 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
433 if (CharC >= NT) {
434 Mask = 1U << (BITBUFSIZ - 1 - 8);
435
436 do {
437
438 if (Mask & Sd->mBitBuf) {
439 CharC = Sd->mRight[CharC];
440 } else {
441 CharC = Sd->mLeft[CharC];
442 }
443
444 Mask >>= 1;
445
446 } while (CharC >= NT);
447 }
448 //
449 // Advance what we have read
450 //
451 FillBuf (Sd, Sd->mPTLen[CharC]);
452
453 if (CharC <= 2) {
454
455 if (CharC == 0) {
456 CharC = 1;
457 } else if (CharC == 1) {
458 CharC = (UINT16) (GetBits (Sd, 4) + 3);
459 } else if (CharC == 2) {
460 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
461 }
462
463 while ((INT16) (--CharC) >= 0) {
464 Sd->mCLen[Index++] = 0;
465 }
466
467 } else {
468
469 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
470
471 }
472 }
473
474 while (Index < NC) {
475 Sd->mCLen[Index++] = 0;
476 }
477
478 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
479
480 return ;
481 }
482
483 /**
484 Decode a character/length value.
485
486 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
487 Huffman code mapping table for Extra Set, Code&Len Set and
488 Position Set.
489
490 @param Sd The global scratch data.
491
492 @return The value decoded.
493
494 **/
495 UINT16
496 DecodeC (
497 SCRATCH_DATA *Sd
498 )
499 {
500 UINT16 Index2;
501 UINT32 Mask;
502
503 if (Sd->mBlockSize == 0) {
504 //
505 // Starting a new block
506 // Read BlockSize from block header
507 //
508 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
509
510 //
511 // Read in the Extra Set Code Length Arrary,
512 // Generate the Huffman code mapping table for Extra Set.
513 //
514 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
515 if (Sd->mBadTableFlag != 0) {
516 return 0;
517 }
518
519 //
520 // Read in and decode the Char&Len Set Code Length Arrary,
521 // Generate the Huffman code mapping table for Char&Len Set.
522 //
523 ReadCLen (Sd);
524
525 //
526 // Read in the Position Set Code Length Arrary,
527 // Generate the Huffman code mapping table for the Position Set.
528 //
529 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
530 if (Sd->mBadTableFlag != 0) {
531 return 0;
532 }
533 }
534
535 //
536 // Get one code according to Code&Set Huffman Table
537 //
538 Sd->mBlockSize--;
539 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
540
541 if (Index2 >= NC) {
542 Mask = 1U << (BITBUFSIZ - 1 - 12);
543
544 do {
545 if (Sd->mBitBuf & Mask) {
546 Index2 = Sd->mRight[Index2];
547 } else {
548 Index2 = Sd->mLeft[Index2];
549 }
550
551 Mask >>= 1;
552 } while (Index2 >= NC);
553 }
554 //
555 // Advance what we have read
556 //
557 FillBuf (Sd, Sd->mCLen[Index2]);
558
559 return Index2;
560 }
561
562 /**
563 Decode the source data and put the resulting data into the destination buffer.
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 - (UINT8_MAX + 1 - 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 Retrieves the size of the uncompressed buffer and the size of the scratch buffer.
642
643 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
644 required to decompress the buffer specified by Source and SourceSize.
645 If the size of the uncompressed buffer or the size of the scratch buffer cannot
646 be determined from the compressed data specified by Source and SourceData,
647 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
648 buffer is returned in DestinationSize, the size of the scratch buffer is returned
649 in ScratchSize, and RETURN_SUCCESS is returned.
650 This function does not have scratch buffer available to perform a thorough
651 checking of the validity of the source data. It just retrieves the "Original Size"
652 field from the beginning bytes of the source data and output it as DestinationSize.
653 And ScratchSize is specific to the decompression implementation.
654
655 If Source is NULL, then ASSERT().
656 If DestinationSize is NULL, then ASSERT().
657 If ScratchSize is NULL, then ASSERT().
658
659 @param Source The source buffer containing the compressed data.
660 @param SourceSize The size, in bytes, of the source buffer.
661 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
662 that will be generated when the compressed buffer specified
663 by Source and SourceSize is decompressed..
664 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
665 is required to decompress the compressed buffer specified
666 by Source and SourceSize.
667
668 @retval RETURN_SUCCESS The size of destination buffer and the size of scratch
669 buffer are successull retrieved.
670 @retval RETURN_INVALID_PARAMETER The source data is corrupted
671
672 **/
673 RETURN_STATUS
674 EFIAPI
675 UefiDecompressGetInfo (
676 IN CONST VOID *Source,
677 IN UINT32 SourceSize,
678 OUT UINT32 *DestinationSize,
679 OUT UINT32 *ScratchSize
680 )
681 {
682 UINT32 CompressedSize;
683
684 ASSERT (Source != NULL);
685 ASSERT (DestinationSize != NULL);
686 ASSERT (ScratchSize != NULL);
687
688 *ScratchSize = sizeof (SCRATCH_DATA);
689
690 if (SourceSize < 8) {
691 return RETURN_INVALID_PARAMETER;
692 }
693
694 CopyMem (&CompressedSize, Source, sizeof (UINT32));
695 CopyMem (DestinationSize, (VOID *)((UINT8 *)Source + 4), sizeof (UINT32));
696
697 if (SourceSize < (CompressedSize + 8)) {
698 return RETURN_INVALID_PARAMETER;
699 }
700
701 return RETURN_SUCCESS;
702 }
703
704 /**
705 Decompresses a compressed source buffer.
706
707 This function is designed so that the decompression algorithm can be implemented
708 without using any memory services. As a result, this function is not allowed to
709 call any memory allocation services in its implementation. It is the caller's r
710 esponsibility to allocate and free the Destination and Scratch buffers.
711 If the compressed source data specified by Source is sucessfully decompressed
712 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
713 specified by Source is not in a valid compressed data format,
714 then RETURN_INVALID_PARAMETER is returned.
715
716 If Source is NULL, then ASSERT().
717 If Destination is NULL, then ASSERT().
718 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
719
720 @param Source The source buffer containing the compressed data.
721 @param Destination The destination buffer to store the decompressed data
722 @param Scratch A temporary scratch buffer that is used to perform the decompression.
723 This is an optional parameter that may be NULL if the
724 required scratch buffer size is 0.
725
726 @retval RETURN_SUCCESS Decompression is successfull
727 @retval RETURN_INVALID_PARAMETER The source data is corrupted
728
729 **/
730 RETURN_STATUS
731 EFIAPI
732 UefiDecompress (
733 IN CONST VOID *Source,
734 IN OUT VOID *Destination,
735 IN OUT VOID *Scratch
736 )
737 {
738 volatile UINT32 Index;
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
766 for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
767 ((UINT8 *) Sd)[Index] = 0;
768 }
769 //
770 // The length of the field 'Position Set Code Length Array Size' in Block Header.
771 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
772 // For Tiano de/compression algorithm(Version 2), mPBit = 5
773 //
774 Sd->mPBit = 4;
775 Sd->mSrcBase = (UINT8 *)Src;
776 Sd->mDstBase = Dst;
777 //
778 // CompSize and OrigSize are caculated in bytes
779 //
780 Sd->mCompSize = CompSize;
781 Sd->mOrigSize = OrigSize;
782
783 //
784 // Fill the first BITBUFSIZ bits
785 //
786 FillBuf (Sd, BITBUFSIZ);
787
788 //
789 // Decompress it
790 //
791 Decode (Sd);
792
793 if (Sd->mBadTableFlag != 0) {
794 //
795 // Something wrong with the source
796 //
797 return RETURN_INVALID_PARAMETER;
798 }
799
800 return RETURN_SUCCESS;
801 }
EFI Development Kit II mirror for PVE