]> 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
Fix the bug that SetMem.S of BaseMemoryLibOptDxe is incorrect.
[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 && Avail < (2 * NC - 1)) {
225 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
226 *Pointer = Avail++;
227 }
228
229 if (*Pointer < (2 * NC - 1)) {
230 if ((Index3 & Mask) != 0) {
231 Pointer = &Sd->mRight[*Pointer];
232 } else {
233 Pointer = &Sd->mLeft[*Pointer];
234 }
235 }
236
237 Index3 <<= 1;
238 Index--;
239 }
240
241 *Pointer = Char;
242
243 }
244
245 Start[Len] = NextCode;
246 }
247 //
248 // Succeeds
249 //
250 return 0;
251 }
252
253 /**
254 Decodes a position value.
255
256 Get a position value according to Position Huffman Table.
257
258 @param Sd the global scratch data
259
260 @return The position value decoded.
261
262 **/
263 UINT32
264 DecodeP (
265 IN SCRATCH_DATA *Sd
266 )
267 {
268 UINT16 Val;
269 UINT32 Mask;
270 UINT32 Pos;
271
272 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
273
274 if (Val >= MAXNP) {
275 Mask = 1U << (BITBUFSIZ - 1 - 8);
276
277 do {
278
279 if ((Sd->mBitBuf & Mask) != 0) {
280 Val = Sd->mRight[Val];
281 } else {
282 Val = Sd->mLeft[Val];
283 }
284
285 Mask >>= 1;
286 } while (Val >= MAXNP);
287 }
288 //
289 // Advance what we have read
290 //
291 FillBuf (Sd, Sd->mPTLen[Val]);
292
293 Pos = Val;
294 if (Val > 1) {
295 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
296 }
297
298 return Pos;
299 }
300
301 /**
302 Reads code lengths for the Extra Set or the Position Set.
303
304 Read in the Extra Set or Pointion Set Length Arrary, then
305 generate the Huffman code mapping for them.
306
307 @param Sd The global scratch data.
308 @param nn Number of symbols.
309 @param nbit Number of bits needed to represent nn.
310 @param Special The special symbol that needs to be taken care of.
311
312 @retval 0 OK.
313 @retval BAD_TABLE Table is corrupted.
314
315 **/
316 UINT16
317 ReadPTLen (
318 IN SCRATCH_DATA *Sd,
319 IN UINT16 nn,
320 IN UINT16 nbit,
321 IN UINT16 Special
322 )
323 {
324 UINT16 Number;
325 UINT16 CharC;
326 UINT16 Index;
327 UINT32 Mask;
328
329 //
330 // Read Extra Set Code Length Array size
331 //
332 Number = (UINT16) GetBits (Sd, nbit);
333
334 if (Number == 0) {
335 //
336 // This represents only Huffman code used
337 //
338 CharC = (UINT16) GetBits (Sd, nbit);
339
340 for (Index = 0; Index < 256; Index++) {
341 Sd->mPTTable[Index] = CharC;
342 }
343
344 SetMem (Sd->mPTLen, nn, 0);
345
346 return 0;
347 }
348
349 Index = 0;
350
351 while (Index < Number && Index < NPT) {
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 && Index < NPT) {
381 Sd->mPTLen[Index++] = 0;
382 }
383 }
384 }
385
386 while (Index < nn && Index < NPT) {
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 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 SetMem (Sd->mCLen, NC, 0);
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 && Index < NC) {
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 && Index < NC) {
463 Sd->mCLen[Index++] = 0;
464 }
465
466 } else {
467
468 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
469
470 }
471 }
472
473 SetMem (Sd->mCLen + Index, NC - Index, 0);
474
475 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
476
477 return ;
478 }
479
480 /**
481 Decode a character/length value.
482
483 Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates
484 Huffman code mapping table for Extra Set, Code&Len Set and
485 Position Set.
486
487 @param Sd The global scratch data.
488
489 @return The value decoded.
490
491 **/
492 UINT16
493 DecodeC (
494 SCRATCH_DATA *Sd
495 )
496 {
497 UINT16 Index2;
498 UINT32 Mask;
499
500 if (Sd->mBlockSize == 0) {
501 //
502 // Starting a new block
503 // Read BlockSize from block header
504 //
505 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
506
507 //
508 // Read in the Extra Set Code Length Arrary,
509 // Generate the Huffman code mapping table for Extra Set.
510 //
511 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
512 if (Sd->mBadTableFlag != 0) {
513 return 0;
514 }
515
516 //
517 // Read in and decode the Char&Len Set Code Length Arrary,
518 // Generate the Huffman code mapping table for Char&Len Set.
519 //
520 ReadCLen (Sd);
521
522 //
523 // Read in the Position Set Code Length Arrary,
524 // Generate the Huffman code mapping table for the Position Set.
525 //
526 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
527 if (Sd->mBadTableFlag != 0) {
528 return 0;
529 }
530 }
531
532 //
533 // Get one code according to Code&Set Huffman Table
534 //
535 Sd->mBlockSize--;
536 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
537
538 if (Index2 >= NC) {
539 Mask = 1U << (BITBUFSIZ - 1 - 12);
540
541 do {
542 if ((Sd->mBitBuf & Mask) != 0) {
543 Index2 = Sd->mRight[Index2];
544 } else {
545 Index2 = Sd->mLeft[Index2];
546 }
547
548 Mask >>= 1;
549 } while (Index2 >= NC);
550 }
551 //
552 // Advance what we have read
553 //
554 FillBuf (Sd, Sd->mCLen[Index2]);
555
556 return Index2;
557 }
558
559 /**
560 Decode the source data and put the resulting data into the destination buffer.
561
562 @param Sd The global scratch data
563
564 **/
565 VOID
566 Decode (
567 SCRATCH_DATA *Sd
568 )
569 {
570 UINT16 BytesRemain;
571 UINT32 DataIdx;
572 UINT16 CharC;
573
574 BytesRemain = (UINT16) (-1);
575
576 DataIdx = 0;
577
578 for (;;) {
579 //
580 // Get one code from mBitBuf
581 //
582 CharC = DecodeC (Sd);
583 if (Sd->mBadTableFlag != 0) {
584 goto Done;
585 }
586
587 if (CharC < 256) {
588 //
589 // Process an Original character
590 //
591 if (Sd->mOutBuf >= Sd->mOrigSize) {
592 goto Done;
593 } else {
594 //
595 // Write orignal character into mDstBase
596 //
597 Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
598 }
599
600 } else {
601 //
602 // Process a Pointer
603 //
604 CharC = (UINT16) (CharC - (BIT8 - THRESHOLD));
605
606 //
607 // Get string length
608 //
609 BytesRemain = CharC;
610
611 //
612 // Locate string position
613 //
614 DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
615
616 //
617 // Write BytesRemain of bytes into mDstBase
618 //
619 BytesRemain--;
620 while ((INT16) (BytesRemain) >= 0) {
621 Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
622 if (Sd->mOutBuf >= Sd->mOrigSize) {
623 goto Done;
624 }
625
626 BytesRemain--;
627 }
628 }
629 }
630
631 Done:
632 return ;
633 }
634
635 /**
636 Given a compressed source buffer, this function retrieves the size of
637 the uncompressed buffer and the size of the scratch buffer required
638 to decompress the compressed source buffer.
639
640 Retrieves the size of the uncompressed buffer and the temporary scratch buffer
641 required to decompress the buffer specified by Source and SourceSize.
642 If the size of the uncompressed buffer or the size of the scratch buffer cannot
643 be determined from the compressed data specified by Source and SourceData,
644 then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed
645 buffer is returned in DestinationSize, the size of the scratch buffer is returned
646 in ScratchSize, and RETURN_SUCCESS is returned.
647 This function does not have scratch buffer available to perform a thorough
648 checking of the validity of the source data. It just retrieves the "Original Size"
649 field from the beginning bytes of the source data and output it as DestinationSize.
650 And ScratchSize is specific to the decompression implementation.
651
652 If Source is NULL, then ASSERT().
653 If DestinationSize is NULL, then ASSERT().
654 If ScratchSize is NULL, then ASSERT().
655
656 @param Source The source buffer containing the compressed data.
657 @param SourceSize The size, in bytes, of the source buffer.
658 @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer
659 that will be generated when the compressed buffer specified
660 by Source and SourceSize is decompressed..
661 @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that
662 is required to decompress the compressed buffer specified
663 by Source and SourceSize.
664
665 @retval RETURN_SUCCESS The size of the uncompressed data was returned
666 in DestinationSize and the size of the scratch
667 buffer was returned in ScratchSize.
668 @retval RETURN_INVALID_PARAMETER
669 The size of the uncompressed data or the size of
670 the scratch buffer cannot be determined from
671 the compressed data specified by Source
672 and SourceSize.
673 **/
674 RETURN_STATUS
675 EFIAPI
676 UefiDecompressGetInfo (
677 IN CONST VOID *Source,
678 IN UINT32 SourceSize,
679 OUT UINT32 *DestinationSize,
680 OUT UINT32 *ScratchSize
681 )
682 {
683 UINT32 CompressedSize;
684
685 ASSERT (Source != NULL);
686 ASSERT (DestinationSize != NULL);
687 ASSERT (ScratchSize != NULL);
688
689 if (SourceSize < 8) {
690 return RETURN_INVALID_PARAMETER;
691 }
692
693 CompressedSize = ReadUnaligned32 ((UINT32 *)Source);
694 if (SourceSize < (CompressedSize + 8)) {
695 return RETURN_INVALID_PARAMETER;
696 }
697
698 *ScratchSize = sizeof (SCRATCH_DATA);
699 *DestinationSize = ReadUnaligned32 ((UINT32 *)Source + 1);
700
701 return RETURN_SUCCESS;
702 }
703
704 /**
705 Decompresses a compressed source buffer.
706
707 Extracts decompressed data to its original form.
708 This function is designed so that the decompression algorithm can be implemented
709 without using any memory services. As a result, this function is not allowed to
710 call any memory allocation services in its implementation. It is the caller's
711 responsibility to allocate and free the Destination and Scratch buffers.
712 If the compressed source data specified by Source is successfully decompressed
713 into Destination, then RETURN_SUCCESS is returned. If the compressed source data
714 specified by Source is not in a valid compressed data format,
715 then RETURN_INVALID_PARAMETER is returned.
716
717 If Source is NULL, then ASSERT().
718 If Destination is NULL, then ASSERT().
719 If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().
720
721 @param Source The source buffer containing the compressed data.
722 @param Destination The destination buffer to store the decompressed data
723 @param Scratch A temporary scratch buffer that is used to perform the decompression.
724 This is an optional parameter that may be NULL if the
725 required scratch buffer size is 0.
726
727 @retval RETURN_SUCCESS Decompression completed successfully, and
728 the uncompressed buffer is returned in Destination.
729 @retval RETURN_INVALID_PARAMETER
730 The source buffer specified by Source is corrupted
731 (not in a valid compressed format).
732 **/
733 RETURN_STATUS
734 EFIAPI
735 UefiDecompress (
736 IN CONST VOID *Source,
737 IN OUT VOID *Destination,
738 IN OUT VOID *Scratch OPTIONAL
739 )
740 {
741 UINT32 CompSize;
742 UINT32 OrigSize;
743 SCRATCH_DATA *Sd;
744 CONST UINT8 *Src;
745 UINT8 *Dst;
746
747 ASSERT (Source != NULL);
748 ASSERT (Destination != NULL);
749 ASSERT (Scratch != NULL);
750
751 Src = Source;
752 Dst = Destination;
753
754 Sd = (SCRATCH_DATA *) Scratch;
755
756 CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
757 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
758
759 //
760 // If compressed file size is 0, return
761 //
762 if (OrigSize == 0) {
763 return RETURN_SUCCESS;
764 }
765
766 Src = Src + 8;
767 SetMem (Sd, sizeof (SCRATCH_DATA), 0);
768
769 //
770 // The length of the field 'Position Set Code Length Array Size' in Block Header.
771 // For UEFI 2.0 de/compression algorithm(Version 1), mPBit = 4
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