]> git.proxmox.com Git - mirror_edk2.git/blame - MdePkg/Library/BaseUefiDecompressLib/BaseUefiDecompressLib.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Initial import.
[mirror_edk2.git] / MdePkg / Library / BaseUefiDecompressLib / BaseUefiDecompressLib.c
CommitLineData
878ddf1f 1/** @file\r
2 UEFI Decompress Library.\r
3\r
4 Copyright (c) 2006, Intel Corporation\r
5 All rights reserved. This program and the accompanying materials\r
6 are licensed and made available under the terms and conditions of the BSD License\r
7 which accompanies this distribution. The full text of the license may be found at\r
8 http://opensource.org/licenses/bsd-license.php\r
9\r
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
12\r
13 Module Name: UefiDecompressLib.c\r
14\r
15**/\r
16\r
17//\r
18// Decompression algorithm begins here\r
19//\r
20#define BITBUFSIZ 32\r
21#define MAXMATCH 256\r
22#define THRESHOLD 3\r
23#define CODE_BIT 16\r
24#define BAD_TABLE - 1\r
25\r
26//\r
27// C: Char&Len Set; P: Position Set; T: exTra Set\r
28//\r
29#define NC (0xff + MAXMATCH + 2 - THRESHOLD)\r
30#define CBIT 9\r
31#define MAXPBIT 5\r
32#define TBIT 5\r
33#define MAXNP ((1U << MAXPBIT) - 1)\r
34#define NT (CODE_BIT + 3)\r
35#if NT > MAXNP\r
36#define NPT NT\r
37#else\r
38#define NPT MAXNP\r
39#endif\r
40\r
41typedef struct {\r
42 UINT8 *mSrcBase; ///< Starting address of compressed data\r
43 UINT8 *mDstBase; ///< Starting address of decompressed data\r
44 UINT32 mOutBuf;\r
45 UINT32 mInBuf;\r
46\r
47 UINT16 mBitCount;\r
48 UINT32 mBitBuf;\r
49 UINT32 mSubBitBuf;\r
50 UINT16 mBlockSize;\r
51 UINT32 mCompSize;\r
52 UINT32 mOrigSize;\r
53\r
54 UINT16 mBadTableFlag;\r
55\r
56 UINT16 mLeft[2 * NC - 1];\r
57 UINT16 mRight[2 * NC - 1];\r
58 UINT8 mCLen[NC];\r
59 UINT8 mPTLen[NPT];\r
60 UINT16 mCTable[4096];\r
61 UINT16 mPTTable[256];\r
62\r
63 ///\r
64 /// The length of the field 'Position Set Code Length Array Size' in Block Header.\r
65 /// For EFI 1.1 de/compression algorithm, mPBit = 4\r
66 /// For Tiano de/compression algorithm, mPBit = 5\r
67 ///\r
68 UINT8 mPBit;\r
69} SCRATCH_DATA;\r
70\r
71/**\r
72 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.\r
73\r
74 @param Sd The global scratch data\r
75 @param NumOfBits The number of bits to shift and read.\r
76\r
77**/\r
78VOID\r
79FillBuf (\r
80 IN SCRATCH_DATA *Sd,\r
81 IN UINT16 NumOfBits\r
82 )\r
83{\r
84 Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);\r
85\r
86 while (NumOfBits > Sd->mBitCount) {\r
87\r
88 Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));\r
89\r
90 if (Sd->mCompSize > 0) {\r
91 //\r
92 // Get 1 byte into SubBitBuf\r
93 //\r
94 Sd->mCompSize--;\r
95 Sd->mSubBitBuf = 0;\r
96 Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++];\r
97 Sd->mBitCount = 8;\r
98\r
99 } else {\r
100 //\r
101 // No more bits from the source, just pad zero bit.\r
102 //\r
103 Sd->mSubBitBuf = 0;\r
104 Sd->mBitCount = 8;\r
105\r
106 }\r
107 }\r
108\r
109 Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);\r
110 Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;\r
111}\r
112\r
113/**\r
114 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent \r
115 NumOfBits of bits from source. Returns NumOfBits of bits that are \r
116 popped out.\r
117\r
118 @param Sd The global scratch data.\r
119 @param NumOfBits The number of bits to pop and read.\r
120\r
121 @return The bits that are popped out.\r
122\r
123**/\r
124UINT32\r
125GetBits (\r
126 IN SCRATCH_DATA *Sd,\r
127 IN UINT16 NumOfBits\r
128 )\r
129{\r
130 UINT32 OutBits;\r
131\r
132 OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));\r
133\r
134 FillBuf (Sd, NumOfBits);\r
135\r
136 return OutBits;\r
137}\r
138\r
139/**\r
140 Creates Huffman Code mapping table according to code length array.\r
141\r
142 @param Sd The global scratch data\r
143 @param NumOfChar Number of symbols in the symbol set\r
144 @param BitLen Code length array\r
145 @param TableBits The width of the mapping table\r
146 @param Table The table\r
147\r
148 @retval 0 OK.\r
149 @retval BAD_TABLE The table is corrupted.\r
150\r
151**/\r
152UINT16\r
153MakeTable (\r
154 IN SCRATCH_DATA *Sd,\r
155 IN UINT16 NumOfChar,\r
156 IN UINT8 *BitLen,\r
157 IN UINT16 TableBits,\r
158 OUT UINT16 *Table\r
159 )\r
160{\r
161 UINT16 Count[17];\r
162 UINT16 Weight[17];\r
163 UINT16 Start[18];\r
164 UINT16 *Pointer;\r
165 UINT16 Index3;\r
166 volatile UINT16 Index;\r
167 UINT16 Len;\r
168 UINT16 Char;\r
169 UINT16 JuBits;\r
170 UINT16 Avail;\r
171 UINT16 NextCode;\r
172 UINT16 Mask;\r
173\r
174 for (Index = 1; Index <= 16; Index++) {\r
175 Count[Index] = 0;\r
176 }\r
177\r
178 for (Index = 0; Index < NumOfChar; Index++) {\r
179 Count[BitLen[Index]]++;\r
180 }\r
181\r
182 Start[1] = 0;\r
183\r
184 for (Index = 1; Index <= 16; Index++) {\r
185 Start[Index + 1] = (UINT16) (Start[Index] + (Count[Index] << (16 - Index)));\r
186 }\r
187\r
188 if (Start[17] != 0) {\r
189 /*(1U << 16)*/\r
190 return (UINT16) BAD_TABLE;\r
191 }\r
192\r
193 JuBits = (UINT16) (16 - TableBits);\r
194\r
195 for (Index = 1; Index <= TableBits; Index++) {\r
196 Start[Index] >>= JuBits;\r
197 Weight[Index] = (UINT16) (1U << (TableBits - Index));\r
198 }\r
199\r
200 while (Index <= 16) {\r
201 Weight[Index] = (UINT16) (1U << (16 - Index));\r
202 Index++; \r
203 }\r
204\r
205 Index = (UINT16) (Start[TableBits + 1] >> JuBits);\r
206\r
207 if (Index != 0) {\r
208 Index3 = (UINT16) (1U << TableBits);\r
209 while (Index != Index3) {\r
210 Table[Index++] = 0;\r
211 }\r
212 }\r
213\r
214 Avail = NumOfChar;\r
215 Mask = (UINT16) (1U << (15 - TableBits));\r
216\r
217 for (Char = 0; Char < NumOfChar; Char++) {\r
218\r
219 Len = BitLen[Char];\r
220 if (Len == 0) {\r
221 continue;\r
222 }\r
223\r
224 NextCode = (UINT16) (Start[Len] + Weight[Len]);\r
225\r
226 if (Len <= TableBits) {\r
227\r
228 for (Index = Start[Len]; Index < NextCode; Index++) {\r
229 Table[Index] = Char;\r
230 }\r
231\r
232 } else {\r
233\r
234 Index3 = Start[Len];\r
235 Pointer = &Table[Index3 >> JuBits];\r
236 Index = (UINT16) (Len - TableBits);\r
237\r
238 while (Index != 0) {\r
239 if (*Pointer == 0) {\r
240 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;\r
241 *Pointer = Avail++;\r
242 }\r
243\r
244 if (Index3 & Mask) {\r
245 Pointer = &Sd->mRight[*Pointer];\r
246 } else {\r
247 Pointer = &Sd->mLeft[*Pointer];\r
248 }\r
249\r
250 Index3 <<= 1;\r
251 Index--;\r
252 }\r
253\r
254 *Pointer = Char;\r
255\r
256 }\r
257\r
258 Start[Len] = NextCode;\r
259 }\r
260 //\r
261 // Succeeds\r
262 //\r
263 return 0;\r
264}\r
265\r
266/**\r
267 Decodes a position value.\r
268\r
269 @param Sd the global scratch data\r
270\r
271 @return The position value decoded.\r
272\r
273**/\r
274UINT32\r
275DecodeP (\r
276 IN SCRATCH_DATA *Sd\r
277 )\r
278{\r
279 UINT16 Val;\r
280 UINT32 Mask;\r
281 UINT32 Pos;\r
282\r
283 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
284\r
285 if (Val >= MAXNP) {\r
286 Mask = 1U << (BITBUFSIZ - 1 - 8);\r
287\r
288 do {\r
289\r
290 if (Sd->mBitBuf & Mask) {\r
291 Val = Sd->mRight[Val];\r
292 } else {\r
293 Val = Sd->mLeft[Val];\r
294 }\r
295\r
296 Mask >>= 1;\r
297 } while (Val >= MAXNP);\r
298 }\r
299 //\r
300 // Advance what we have read\r
301 //\r
302 FillBuf (Sd, Sd->mPTLen[Val]);\r
303\r
304 Pos = Val;\r
305 if (Val > 1) {\r
306 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));\r
307 }\r
308\r
309 return Pos;\r
310}\r
311\r
312/**\r
313 Reads code lengths for the Extra Set or the Position Set.\r
314\r
315 @param Sd The global scratch data.\r
316 @param nn Number of symbols.\r
317 @param nbit Number of bits needed to represent nn.\r
318 @param Special The special symbol that needs to be taken care of.\r
319\r
320 @retval 0 OK.\r
321 @retval BAD_TABLE Table is corrupted.\r
322\r
323**/\r
324UINT16\r
325ReadPTLen (\r
326 IN SCRATCH_DATA *Sd,\r
327 IN UINT16 nn,\r
328 IN UINT16 nbit,\r
329 IN UINT16 Special\r
330 )\r
331{\r
332 UINT16 Number;\r
333 UINT16 CharC;\r
334 volatile UINT16 Index;\r
335 UINT32 Mask;\r
336\r
337 Number = (UINT16) GetBits (Sd, nbit);\r
338\r
339 if (Number == 0) {\r
340 CharC = (UINT16) GetBits (Sd, nbit);\r
341\r
342 for (Index = 0; Index < 256; Index++) {\r
343 Sd->mPTTable[Index] = CharC;\r
344 }\r
345\r
346 for (Index = 0; Index < nn; Index++) {\r
347 Sd->mPTLen[Index] = 0;\r
348 }\r
349\r
350 return 0;\r
351 }\r
352\r
353 Index = 0;\r
354\r
355 while (Index < Number) {\r
356\r
357 CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));\r
358\r
359 if (CharC == 7) {\r
360 Mask = 1U << (BITBUFSIZ - 1 - 3);\r
361 while (Mask & Sd->mBitBuf) {\r
362 Mask >>= 1;\r
363 CharC += 1;\r
364 }\r
365 }\r
366\r
367 FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));\r
368\r
369 Sd->mPTLen[Index++] = (UINT8) CharC;\r
370\r
371 if (Index == Special) {\r
372 CharC = (UINT16) GetBits (Sd, 2);\r
373 while ((INT16) (--CharC) >= 0) {\r
374 Sd->mPTLen[Index++] = 0;\r
375 }\r
376 }\r
377 }\r
378\r
379 while (Index < nn) {\r
380 Sd->mPTLen[Index++] = 0;\r
381 }\r
382\r
383 return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);\r
384}\r
385\r
386/**\r
387 Reads code lengths for Char&Len Set.\r
388\r
389 @param Sd the global scratch data\r
390\r
391**/\r
392VOID\r
393ReadCLen (\r
394 SCRATCH_DATA *Sd\r
395 )\r
396{\r
397 UINT16 Number;\r
398 UINT16 CharC;\r
399 volatile UINT16 Index;\r
400 UINT32 Mask;\r
401\r
402 Number = (UINT16) GetBits (Sd, CBIT);\r
403\r
404 if (Number == 0) {\r
405 CharC = (UINT16) GetBits (Sd, CBIT);\r
406\r
407 for (Index = 0; Index < NC; Index++) {\r
408 Sd->mCLen[Index] = 0;\r
409 }\r
410\r
411 for (Index = 0; Index < 4096; Index++) {\r
412 Sd->mCTable[Index] = CharC;\r
413 }\r
414\r
415 return ;\r
416 }\r
417\r
418 Index = 0;\r
419 while (Index < Number) {\r
420\r
421 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
422 if (CharC >= NT) {\r
423 Mask = 1U << (BITBUFSIZ - 1 - 8);\r
424\r
425 do {\r
426\r
427 if (Mask & Sd->mBitBuf) {\r
428 CharC = Sd->mRight[CharC];\r
429 } else {\r
430 CharC = Sd->mLeft[CharC];\r
431 }\r
432\r
433 Mask >>= 1;\r
434\r
435 } while (CharC >= NT);\r
436 }\r
437 //\r
438 // Advance what we have read\r
439 //\r
440 FillBuf (Sd, Sd->mPTLen[CharC]);\r
441\r
442 if (CharC <= 2) {\r
443\r
444 if (CharC == 0) {\r
445 CharC = 1;\r
446 } else if (CharC == 1) {\r
447 CharC = (UINT16) (GetBits (Sd, 4) + 3);\r
448 } else if (CharC == 2) {\r
449 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);\r
450 }\r
451\r
452 while ((INT16) (--CharC) >= 0) {\r
453 Sd->mCLen[Index++] = 0;\r
454 }\r
455\r
456 } else {\r
457\r
458 Sd->mCLen[Index++] = (UINT8) (CharC - 2);\r
459\r
460 }\r
461 }\r
462\r
463 while (Index < NC) {\r
464 Sd->mCLen[Index++] = 0;\r
465 }\r
466\r
467 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);\r
468\r
469 return ;\r
470}\r
471\r
472/**\r
473 Decode a character/length value.\r
474\r
475 @param Sd The global scratch data.\r
476\r
477 @return The value decoded.\r
478\r
479**/\r
480UINT16\r
481DecodeC (\r
482 SCRATCH_DATA *Sd\r
483 )\r
484{\r
485 UINT16 Index2;\r
486 UINT32 Mask;\r
487\r
488 if (Sd->mBlockSize == 0) {\r
489 //\r
490 // Starting a new block\r
491 //\r
492 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);\r
493 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);\r
494 if (Sd->mBadTableFlag != 0) {\r
495 return 0;\r
496 }\r
497\r
498 ReadCLen (Sd);\r
499\r
500 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));\r
501 if (Sd->mBadTableFlag != 0) {\r
502 return 0;\r
503 }\r
504 }\r
505\r
506 Sd->mBlockSize--;\r
507 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];\r
508\r
509 if (Index2 >= NC) {\r
510 Mask = 1U << (BITBUFSIZ - 1 - 12);\r
511\r
512 do {\r
513 if (Sd->mBitBuf & Mask) {\r
514 Index2 = Sd->mRight[Index2];\r
515 } else {\r
516 Index2 = Sd->mLeft[Index2];\r
517 }\r
518\r
519 Mask >>= 1;\r
520 } while (Index2 >= NC);\r
521 }\r
522 //\r
523 // Advance what we have read\r
524 //\r
525 FillBuf (Sd, Sd->mCLen[Index2]);\r
526\r
527 return Index2;\r
528}\r
529\r
530/**\r
531 Decode the source data and put the resulting data into the destination buffer.\r
532\r
533 @param Sd The global scratch data\r
534\r
535**/\r
536VOID\r
537Decode (\r
538 SCRATCH_DATA *Sd\r
539 )\r
540{\r
541 UINT16 BytesRemain;\r
542 UINT32 DataIdx;\r
543 UINT16 CharC;\r
544\r
545 BytesRemain = (UINT16) (-1);\r
546\r
547 DataIdx = 0;\r
548\r
549 for (;;) {\r
550 CharC = DecodeC (Sd);\r
551 if (Sd->mBadTableFlag != 0) {\r
552 return ;\r
553 }\r
554\r
555 if (CharC < 256) {\r
556 //\r
557 // Process an Original character\r
558 //\r
559 if (Sd->mOutBuf >= Sd->mOrigSize) {\r
560 return ;\r
561 } else {\r
562 Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;\r
563 }\r
564\r
565 } else {\r
566 //\r
567 // Process a Pointer\r
568 //\r
569 CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));\r
570\r
571 BytesRemain = CharC;\r
572\r
573 DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;\r
574\r
575 BytesRemain--;\r
576 while ((INT16) (BytesRemain) >= 0) {\r
577 Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];\r
578 if (Sd->mOutBuf >= Sd->mOrigSize) {\r
579 return ;\r
580 }\r
581\r
582 BytesRemain--;\r
583 }\r
584 }\r
585 }\r
586\r
587 return ;\r
588}\r
589\r
590/**\r
591 The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().\r
592\r
593 @param Source The source buffer containing the compressed data.\r
594 @param SourceSize The size of source buffer\r
595 @param DestinationSize The size of destination buffer.\r
596 @param ScratchSize The size of scratch buffer.\r
597\r
598 @retval RETURN_SUCCESS The size of destination buffer and the size of scratch buffer are successull retrieved.\r
599 @retval RETURN_INVALID_PARAMETER The source data is corrupted\r
600\r
601**/\r
602RETURN_STATUS\r
603EFIAPI\r
604UefiDecompressGetInfo (\r
605 IN CONST VOID *Source,\r
606 IN UINT32 SourceSize,\r
607 OUT UINT32 *DestinationSize,\r
608 OUT UINT32 *ScratchSize\r
609 )\r
610{\r
611 UINT32 CompressedSize;\r
612\r
613 ASSERT (Source != NULL);\r
614 ASSERT (DestinationSize != NULL);\r
615 ASSERT (ScratchSize != NULL);\r
616\r
617 *ScratchSize = sizeof (SCRATCH_DATA);\r
618\r
619 if (SourceSize < 8) {\r
620 return RETURN_INVALID_PARAMETER;\r
621 }\r
622\r
623 CopyMem (&CompressedSize, Source, sizeof (UINT32));\r
624 CopyMem (DestinationSize, (VOID *)((UINT8 *)Source + 4), sizeof (UINT32));\r
625\r
626 if (SourceSize < (CompressedSize + 8)) {\r
627 return RETURN_INVALID_PARAMETER;\r
628 }\r
629\r
630 return RETURN_SUCCESS;\r
631}\r
632\r
633/**\r
634 The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().\r
635\r
636 @param Source The source buffer containing the compressed data.\r
637 @param Destination The destination buffer to store the decompressed data\r
638 @param Scratch The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.\r
639\r
640 @retval RETURN_SUCCESS Decompression is successfull\r
641 @retval RETURN_INVALID_PARAMETER The source data is corrupted\r
642\r
643**/\r
644RETURN_STATUS\r
645EFIAPI\r
646UefiDecompress (\r
647 IN CONST VOID *Source,\r
648 IN OUT VOID *Destination,\r
649 IN OUT VOID *Scratch\r
650 )\r
651{\r
652 volatile UINT32 Index;\r
653 UINT32 CompSize;\r
654 UINT32 OrigSize;\r
655 SCRATCH_DATA *Sd;\r
656 CONST UINT8 *Src;\r
657 UINT8 *Dst;\r
658\r
659 ASSERT (Source != NULL);\r
660 ASSERT (Destination != NULL);\r
661 ASSERT (Scratch != NULL);\r
662\r
663 Src = Source;\r
664 Dst = Destination;\r
665\r
666 Sd = (SCRATCH_DATA *) Scratch;\r
667\r
668 CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);\r
669 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);\r
670\r
671 //\r
672 // If compressed file size is 0, return\r
673 //\r
674 if (OrigSize == 0) {\r
675 return RETURN_SUCCESS;\r
676 }\r
677\r
678 Src = Src + 8;\r
679\r
680 for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {\r
681 ((UINT8 *) Sd)[Index] = 0;\r
682 }\r
683 //\r
684 // The length of the field 'Position Set Code Length Array Size' in Block Header.\r
685 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4\r
686 // For Tiano de/compression algorithm(Version 2), mPBit = 5\r
687 //\r
688 Sd->mPBit = 4;\r
689 Sd->mSrcBase = (UINT8 *)Src;\r
690 Sd->mDstBase = Dst;\r
691 Sd->mCompSize = CompSize;\r
692 Sd->mOrigSize = OrigSize;\r
693\r
694 //\r
695 // Fill the first BITBUFSIZ bits\r
696 //\r
697 FillBuf (Sd, BITBUFSIZ);\r
698\r
699 //\r
700 // Decompress it\r
701 //\r
702 Decode (Sd);\r
703\r
704 if (Sd->mBadTableFlag != 0) {\r
705 //\r
706 // Something wrong with the source\r
707 //\r
708 return RETURN_INVALID_PARAMETER;\r
709 }\r
710\r
711 return RETURN_SUCCESS;\r
712}\r
EFI Development Kit II mirror for PVE