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