]> git.proxmox.com Git - mirror_edk2.git/blob - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
projects / mirror_edk2.git / blob
? search:


15917a1c12b767805e6d21fad185fd50a9a233ef
[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 Module Name: UefiDecompressLib.c
14
15 **/
16
17 //
18 // Include common header file for this module.
19 //
20 #include "CommonHeader.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
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 volatile 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 = 1; Index <= 16; Index++) {
156 Count[Index] = 0;
157 }
158
159 for (Index = 0; Index < NumOfChar; Index++) {
160 Count[BitLen[Index]]++;
161 }
162
163 Start[1] = 0;
164
165 for (Index = 1; Index <= 16; Index++) {
166 WordOfStart = Start[Index];
167 WordOfCount = Count[Index];
168 Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
169 }
170
171 if (Start[17] != 0) {
172 /*(1U << 16)*/
173 return (UINT16) BAD_TABLE;
174 }
175
176 JuBits = (UINT16) (16 - TableBits);
177
178 for (Index = 1; Index <= TableBits; Index++) {
179 Start[Index] >>= JuBits;
180 Weight[Index] = (UINT16) (1U << (TableBits - Index));
181 }
182
183 while (Index <= 16) {
184 Weight[Index] = (UINT16) (1U << (16 - Index));
185 Index++;
186 }
187
188 Index = (UINT16) (Start[TableBits + 1] >> JuBits);
189
190 if (Index != 0) {
191 Index3 = (UINT16) (1U << TableBits);
192 while (Index != Index3) {
193 Table[Index++] = 0;
194 }
195 }
196
197 Avail = NumOfChar;
198 Mask = (UINT16) (1U << (15 - TableBits));
199
200 for (Char = 0; Char < NumOfChar; Char++) {
201
202 Len = BitLen[Char];
203 if (Len == 0) {
204 continue;
205 }
206
207 NextCode = (UINT16) (Start[Len] + Weight[Len]);
208
209 if (Len <= TableBits) {
210
211 for (Index = Start[Len]; Index < NextCode; Index++) {
212 Table[Index] = Char;
213 }
214
215 } else {
216
217 Index3 = Start[Len];
218 Pointer = &Table[Index3 >> JuBits];
219 Index = (UINT16) (Len - TableBits);
220
221 while (Index != 0) {
222 if (*Pointer == 0) {
223 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
224 *Pointer = Avail++;
225 }
226
227 if (Index3 & Mask) {
228 Pointer = &Sd->mRight[*Pointer];
229 } else {
230 Pointer = &Sd->mLeft[*Pointer];
231 }
232
233 Index3 <<= 1;
234 Index--;
235 }
236
237 *Pointer = Char;
238
239 }
240
241 Start[Len] = NextCode;
242 }
243 //
244 // Succeeds
245 //
246 return 0;
247 }
248
249 /**
250 Decodes a position value.
251
252 Get a position value according to Position Huffman Table.
253
254 @param Sd the global scratch data
255
256 @return The position value decoded.
257
258 **/
259 UINT32
260 DecodeP (
261 IN SCRATCH_DATA *Sd
262 )
263 {
264 UINT16 Val;
265 UINT32 Mask;
266 UINT32 Pos;
267
268 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
269
270 if (Val >= MAXNP) {
271 Mask = 1U << (BITBUFSIZ - 1 - 8);
272
273 do {
274
275 if (Sd->mBitBuf & Mask) {
276 Val = Sd->mRight[Val];
277 } else {
278 Val = Sd->mLeft[Val];
279 }
280
281 Mask >>= 1;
282 } while (Val >= MAXNP);
283 }
284 //
285 // Advance what we have read
286 //
287 FillBuf (Sd, Sd->mPTLen[Val]);
288
289 Pos = Val;
290 if (Val > 1) {
291 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
292 }
293
294 return Pos;
295 }
296
297 /**
298 Reads code lengths for the Extra Set or the Position Set.
299
300 Read in the Extra Set or Pointion Set Length Arrary, then
301 generate the Huffman code mapping for them.
302
303 @param Sd The global scratch data.
304 @param nn Number of symbols.
305 @param nbit Number of bits needed to represent nn.
306 @param Special The special symbol that needs to be taken care of.
307
308 @retval 0 OK.
309 @retval BAD_TABLE Table is corrupted.
310
311 **/
312 UINT16
313 ReadPTLen (
314 IN SCRATCH_DATA *Sd,
315 IN UINT16 nn,
316 IN UINT16 nbit,
317 IN UINT16 Special
318 )
319 {
320 UINT16 Number;
321 UINT16 CharC;
322 volatile UINT16 Index;
323 UINT32 Mask;
324
325 //
326 // Read Extra Set Code Length Array size
327 //
328 Number = (UINT16) GetBits (Sd, nbit);
329
330 if (Number == 0) {
331 //
332 // This represents only Huffman code used
333 //
334 CharC = (UINT16) GetBits (Sd, nbit);
335
336 for (Index = 0; Index < 256; Index++) {
337 Sd->mPTTable[Index] = CharC;
338 }
339
340 for (Index = 0; Index < nn; Index++) {
341 Sd->mPTLen[Index] = 0;
342 }
343
344 return 0;
345 }
346
347 Index = 0;
348
349 while (Index < Number) {
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) {
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 volatile 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 for (Index = 0; Index < NC; Index++) {
419 Sd->mCLen[Index] = 0;
420 }
421
422 for (Index = 0; Index < 4096; Index++) {
423 Sd->mCTable[Index] = CharC;
424 }
425
426 return ;
427 }
428
429 Index = 0;
430 while (Index < Number) {
431 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
432 if (CharC >= NT) {
433 Mask = 1U << (BITBUFSIZ - 1 - 8);
434
435 do {
436
437 if (Mask & Sd->mBitBuf) {
438 CharC = Sd->mRight[CharC];
439 } else {
440 CharC = Sd->mLeft[CharC];
441 }
442
443 Mask >>= 1;
444
445 } while (CharC >= NT);
446 }
447 //
448 // Advance what we have read
449 //
450 FillBuf (Sd, Sd->mPTLen[CharC]);
451
452 if (CharC <= 2) {
453
454 if (CharC == 0) {
455 CharC = 1;
456 } else if (CharC == 1) {
457 CharC = (UINT16) (GetBits (Sd, 4) + 3);
458 } else if (CharC == 2) {
459 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
460 }
461
462 while ((INT16) (--CharC) >= 0) {
463 Sd->mCLen[Index++] = 0;
464 }
465
466 } else {
467
468 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
469
470 }
471 }
472
473 while (Index < NC) {
474 Sd->mCLen[Index++] = 0;
475 }
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) {
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 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 Retrieves the size of the uncompressed buffer and the size of the scratch 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 destination buffer and the size of scratch
668 buffer are successull retrieved.
669 @retval RETURN_INVALID_PARAMETER The source data is corrupted
670
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 *ScratchSize = sizeof (SCRATCH_DATA);
688
689 if (SourceSize < 8) {
690 return RETURN_INVALID_PARAMETER;
691 }
692
693 CopyMem (&CompressedSize, Source, sizeof (UINT32));
694 CopyMem (DestinationSize, (VOID *)((UINT8 *)Source + 4), sizeof (UINT32));
695
696 if (SourceSize < (CompressedSize + 8)) {
697 return RETURN_INVALID_PARAMETER;
698 }
699
700 return RETURN_SUCCESS;
701 }
702
703 /**
704 Decompresses a compressed source buffer.
705
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 is successfull
726 @retval RETURN_INVALID_PARAMETER The source data is corrupted
727
728 **/
729 RETURN_STATUS
730 EFIAPI
731 UefiDecompress (
732 IN CONST VOID *Source,
733 IN OUT VOID *Destination,
734 IN OUT VOID *Scratch
735 )
736 {
737 volatile UINT32 Index;
738 UINT32 CompSize;
739 UINT32 OrigSize;
740 SCRATCH_DATA *Sd;
741 CONST UINT8 *Src;
742 UINT8 *Dst;
743
744 ASSERT (Source != NULL);
745 ASSERT (Destination != NULL);
746 ASSERT (Scratch != NULL);
747
748 Src = Source;
749 Dst = Destination;
750
751 Sd = (SCRATCH_DATA *) Scratch;
752
753 CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
754 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
755
756 //
757 // If compressed file size is 0, return
758 //
759 if (OrigSize == 0) {
760 return RETURN_SUCCESS;
761 }
762
763 Src = Src + 8;
764
765 for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
766 ((UINT8 *) Sd)[Index] = 0;
767 }
768 //
769 // The length of the field 'Position Set Code Length Array Size' in Block Header.
770 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
771 // For Tiano de/compression algorithm(Version 2), mPBit = 5
772 //
773 Sd->mPBit = 4;
774 Sd->mSrcBase = (UINT8 *)Src;
775 Sd->mDstBase = Dst;
776 //
777 // CompSize and OrigSize are caculated in bytes
778 //
779 Sd->mCompSize = CompSize;
780 Sd->mOrigSize = OrigSize;
781
782 //
783 // Fill the first BITBUFSIZ bits
784 //
785 FillBuf (Sd, BITBUFSIZ);
786
787 //
788 // Decompress it
789 //
790 Decode (Sd);
791
792 if (Sd->mBadTableFlag != 0) {
793 //
794 // Something wrong with the source
795 //
796 return RETURN_INVALID_PARAMETER;
797 }
798
799 return RETURN_SUCCESS;
800 }
EFI Development Kit II mirror for PVE