1 /*
2 * Deflate (zlib) (un)compression functions
3 *
4 * Copyright (C) 2010-2021, Joachim Metz <joachim.metz@gmail.com>
5 *
6 * Refer to AUTHORS for acknowledgements.
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22 #include <common.h>
23 #include <byte_stream.h>
24 #include <memory.h>
25 #include <types.h>
26
27 #include "libqcow_deflate.h"
28 #include "libqcow_libcerror.h"
29
30 libqcow_deflate_huffman_table_t libqcow_deflate_fixed_huffman_distances_table;
31 libqcow_deflate_huffman_table_t libqcow_deflate_fixed_huffman_literals_table;
32
33 int libqcow_deflate_fixed_huffman_tables_initialized = 0;
34
35 /* Retrieves a value from the bit stream
36 * Returns 1 on success or -1 on error
37 */
libqcow_deflate_bit_stream_get_value(libqcow_deflate_bit_stream_t * bit_stream,uint8_t number_of_bits,uint32_t * value_32bit,libcerror_error_t ** error)38 int libqcow_deflate_bit_stream_get_value(
39 libqcow_deflate_bit_stream_t *bit_stream,
40 uint8_t number_of_bits,
41 uint32_t *value_32bit,
42 libcerror_error_t **error )
43 {
44 static char *function = "libqcow_deflate_bit_stream_get_value";
45 uint32_t safe_value_32bit = 0;
46
47 if( bit_stream == NULL )
48 {
49 libcerror_error_set(
50 error,
51 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
52 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
53 "%s: invalid bit stream.",
54 function );
55
56 return( -1 );
57 }
58 if( number_of_bits > (uint8_t) 32 )
59 {
60 libcerror_error_set(
61 error,
62 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
63 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
64 "%s: invalid number of bits value exceeds maximum.",
65 function );
66
67 return( -1 );
68 }
69 if( value_32bit == NULL )
70 {
71 libcerror_error_set(
72 error,
73 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
74 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
75 "%s: invalid 32-bit value.",
76 function );
77
78 return( -1 );
79 }
80 if( number_of_bits == 0 )
81 {
82 *value_32bit = 0;
83
84 return( 1 );
85 }
86 while( bit_stream->bit_buffer_size < number_of_bits )
87 {
88 if( bit_stream->byte_stream_offset >= bit_stream->byte_stream_size )
89 {
90 libcerror_error_set(
91 error,
92 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
93 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
94 "%s: invalid byte stream value to small.",
95 function );
96
97 return( -1 );
98 }
99 safe_value_32bit = bit_stream->byte_stream[ bit_stream->byte_stream_offset++ ];
100 safe_value_32bit <<= bit_stream->bit_buffer_size;
101
102 bit_stream->bit_buffer |= safe_value_32bit;
103 bit_stream->bit_buffer_size += 8;
104 }
105 safe_value_32bit = bit_stream->bit_buffer;
106
107 if( number_of_bits < 32 )
108 {
109 /* On VS 2008 32-bit "~( 0xfffffffUL << 32 )" does not behave as expected
110 */
111 safe_value_32bit &= ~( 0xffffffffUL << number_of_bits );
112
113 bit_stream->bit_buffer >>= number_of_bits;
114 bit_stream->bit_buffer_size -= number_of_bits;
115 }
116 else
117 {
118 bit_stream->bit_buffer = 0;
119 bit_stream->bit_buffer_size = 0;
120 }
121 *value_32bit = safe_value_32bit;
122
123 return( 1 );
124 }
125
126 /* Constructs the Huffman table
127 * Returns 1 on success, 0 if the table is empty or -1 on error
128 */
libqcow_deflate_huffman_table_construct(libqcow_deflate_huffman_table_t * table,const uint16_t * code_sizes_array,int number_of_code_sizes,libcerror_error_t ** error)129 int libqcow_deflate_huffman_table_construct(
130 libqcow_deflate_huffman_table_t *table,
131 const uint16_t *code_sizes_array,
132 int number_of_code_sizes,
133 libcerror_error_t **error )
134 {
135 int code_offsets_array[ 16 ];
136
137 static char *function = "libqcow_deflate_huffman_table_construct";
138 uint16_t code_size = 0;
139 uint8_t bit_index = 0;
140 int code_offset = 0;
141 int left_value = 0;
142 int symbol = 0;
143
144 if( table == NULL )
145 {
146 libcerror_error_set(
147 error,
148 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
149 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
150 "%s: invalid table.",
151 function );
152
153 return( -1 );
154 }
155 if( code_sizes_array == NULL )
156 {
157 libcerror_error_set(
158 error,
159 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
160 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
161 "%s: invalid code sizes array.",
162 function );
163
164 return( -1 );
165 }
166 if( number_of_code_sizes < 0 )
167 {
168 libcerror_error_set(
169 error,
170 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
171 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
172 "%s: invalid number of code sizes value out of bounds.",
173 function );
174
175 return( -1 );
176 }
177 /* TODO hardcoded for now */
178 table->maximum_number_of_bits = 15;
179
180 if( table->maximum_number_of_bits > 15 )
181 {
182 libcerror_error_set(
183 error,
184 LIBCERROR_ERROR_DOMAIN_RUNTIME,
185 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
186 "%s: invalid table - number of bits values out of bounds.",
187 function );
188
189 return( -1 );
190 }
191 table->number_of_codes = (int) table->maximum_number_of_bits + 1;
192
193 if( memory_set(
194 &( table->codes_array ),
195 0,
196 288 * sizeof( int ) ) == NULL )
197 {
198 libcerror_error_set(
199 error,
200 LIBCERROR_ERROR_DOMAIN_MEMORY,
201 LIBCERROR_MEMORY_ERROR_SET_FAILED,
202 "%s: unable to clear code counts array.",
203 function );
204
205 return( -1 );
206 }
207 if( memory_set(
208 &( table->code_counts_array ),
209 0,
210 16 * sizeof( int ) ) == NULL )
211 {
212 libcerror_error_set(
213 error,
214 LIBCERROR_ERROR_DOMAIN_MEMORY,
215 LIBCERROR_MEMORY_ERROR_SET_FAILED,
216 "%s: unable to clear code counts array.",
217 function );
218
219 return( -1 );
220 }
221 for( symbol = 0;
222 symbol < number_of_code_sizes;
223 symbol++ )
224 {
225 code_size = code_sizes_array[ symbol ];
226
227 if( code_size > table->number_of_codes )
228 {
229 libcerror_error_set(
230 error,
231 LIBCERROR_ERROR_DOMAIN_RUNTIME,
232 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
233 "%s: invalid symbol: %d code size: %" PRIu16 " value out of bounds.",
234 function,
235 symbol,
236 code_size );
237
238 return( -1 );
239 }
240 table->code_counts_array[ code_size ] += 1;
241 }
242 /* The table has no codes
243 */
244 if( table->code_counts_array[ 0 ] == number_of_code_sizes )
245 {
246 return( 0 );
247 }
248 /* Check if the set of code sizes is incomplete or over-subscribed
249 */
250 left_value = 1;
251
252 for( bit_index = 1;
253 bit_index <= table->maximum_number_of_bits;
254 bit_index++ )
255 {
256 left_value <<= 1;
257 left_value -= table->code_counts_array[ bit_index ];
258
259 if( left_value < 0 )
260 {
261 libcerror_error_set(
262 error,
263 LIBCERROR_ERROR_DOMAIN_RUNTIME,
264 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
265 "%s: code sizes are over-subscribed.",
266 function );
267
268 return( -1 );
269 }
270 }
271 /* Calculate the offsets for sorting the symbol table
272 */
273 code_offsets_array[ 0 ] = 0;
274 code_offsets_array[ 1 ] = 0;
275
276 for( bit_index = 1;
277 bit_index < table->maximum_number_of_bits;
278 bit_index++ )
279 {
280 code_offsets_array[ bit_index + 1 ] = code_offsets_array[ bit_index ]
281 + table->code_counts_array[ bit_index ];
282 }
283 for( symbol = 0;
284 symbol < number_of_code_sizes;
285 symbol++ )
286 {
287 code_size = code_sizes_array[ symbol ];
288
289 if( code_size == 0 )
290 {
291 continue;
292 }
293 code_offset = code_offsets_array[ code_size ];
294
295 if( ( code_offset < 0 )
296 || ( code_offset > number_of_code_sizes ) )
297 {
298 libcerror_error_set(
299 error,
300 LIBCERROR_ERROR_DOMAIN_RUNTIME,
301 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
302 "%s: invalid symbol: %d code offset: %d value out of bounds.",
303 function,
304 symbol,
305 code_offset );
306
307 return( -1 );
308 }
309 code_offsets_array[ code_size ] += 1;
310 table->codes_array[ code_offset ] = symbol;
311 }
312 /* TODO only used by dynamic Huffman
313 if( left_value > 0 )
314 {
315 libcerror_error_set(
316 error,
317 LIBCERROR_ERROR_DOMAIN_RUNTIME,
318 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
319 "%s: code sizes are incomplete.",
320 function );
321
322 return( -1 );
323 }
324 */
325 return( 1 );
326 }
327
328 /* Retrieves a Huffman encoded value from the bit stream
329 * Returns 1 on success or -1 on error
330 */
libqcow_deflate_bit_stream_get_huffman_encoded_value(libqcow_deflate_bit_stream_t * bit_stream,libqcow_deflate_huffman_table_t * table,uint32_t * value_32bit,libcerror_error_t ** error)331 int libqcow_deflate_bit_stream_get_huffman_encoded_value(
332 libqcow_deflate_bit_stream_t *bit_stream,
333 libqcow_deflate_huffman_table_t *table,
334 uint32_t *value_32bit,
335 libcerror_error_t **error )
336 {
337 static char *function = "libqcow_deflate_bit_stream_get_huffman_encoded_value";
338 uint32_t bit_buffer = 0;
339 uint32_t safe_value_32bit = 0;
340 uint8_t bit_index = 0;
341 uint8_t number_of_bits = 0;
342 int code_size_count = 0;
343 int first_huffman_code = 0;
344 int first_index = 0;
345 int huffman_code = 0;
346 int result = 0;
347
348 if( bit_stream == NULL )
349 {
350 libcerror_error_set(
351 error,
352 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
353 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
354 "%s: invalid bit stream.",
355 function );
356
357 return( -1 );
358 }
359 if( table == NULL )
360 {
361 libcerror_error_set(
362 error,
363 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
364 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
365 "%s: invalid table.",
366 function );
367
368 return( -1 );
369 }
370 if( value_32bit == NULL )
371 {
372 libcerror_error_set(
373 error,
374 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
375 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
376 "%s: invalid 32-bit value.",
377 function );
378
379 return( -1 );
380 }
381 /* Try to fill the bit buffer with the maximum number of bits
382 */
383 while( bit_stream->bit_buffer_size < table->maximum_number_of_bits )
384 {
385 if( bit_stream->byte_stream_offset >= bit_stream->byte_stream_size )
386 {
387 break;
388 }
389 safe_value_32bit = bit_stream->byte_stream[ bit_stream->byte_stream_offset++ ];
390 safe_value_32bit <<= bit_stream->bit_buffer_size;
391
392 bit_stream->bit_buffer |= safe_value_32bit;
393 bit_stream->bit_buffer_size += 8;
394 }
395 if( table->maximum_number_of_bits < bit_stream->bit_buffer_size )
396 {
397 number_of_bits = table->maximum_number_of_bits;
398 }
399 else
400 {
401 number_of_bits = bit_stream->bit_buffer_size;
402 }
403 bit_buffer = bit_stream->bit_buffer;
404
405 for( bit_index = 1;
406 bit_index <= number_of_bits;
407 bit_index++ )
408 {
409 huffman_code <<= 1;
410 huffman_code |= (int) bit_buffer & 0x00000001UL;
411 bit_buffer >>= 1;
412
413 code_size_count = table->code_counts_array[ bit_index ];
414
415 if( ( huffman_code - code_size_count ) < first_huffman_code )
416 {
417 safe_value_32bit = table->codes_array[ first_index + ( huffman_code - first_huffman_code ) ];
418
419 result = 1;
420
421 break;
422 }
423 first_huffman_code += code_size_count;
424 first_huffman_code <<= 1;
425 first_index += code_size_count;
426 }
427 if( result != 0 )
428 {
429 bit_stream->bit_buffer >>= bit_index;
430 bit_stream->bit_buffer_size -= bit_index;
431 }
432 if( result != 1 )
433 {
434 libcerror_error_set(
435 error,
436 LIBCERROR_ERROR_DOMAIN_RUNTIME,
437 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
438 "%s: invalid huffman encoded value.",
439 function );
440
441 return( -1 );
442 }
443 *value_32bit = safe_value_32bit;
444
445 return( 1 );
446 }
447
448 /* Initializes the dynamic Huffman tables
449 * Returns 1 on success or -1 on error
450 */
libqcow_deflate_initialize_dynamic_huffman_tables(libqcow_deflate_bit_stream_t * bit_stream,libqcow_deflate_huffman_table_t * literals_table,libqcow_deflate_huffman_table_t * distances_table,libcerror_error_t ** error)451 int libqcow_deflate_initialize_dynamic_huffman_tables(
452 libqcow_deflate_bit_stream_t *bit_stream,
453 libqcow_deflate_huffman_table_t *literals_table,
454 libqcow_deflate_huffman_table_t *distances_table,
455 libcerror_error_t **error )
456 {
457 uint16_t code_size_array[ 316 ];
458
459 uint8_t code_sizes_sequence[ 19 ] = {
460 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2,
461 14, 1, 15 };
462
463 libqcow_deflate_huffman_table_t codes_table;
464
465 static char *function = "libqcow_deflate_initialize_dynamic_huffman_tables";
466 uint32_t code_size = 0;
467 uint32_t code_size_index = 0;
468 uint32_t code_size_sequence = 0;
469 uint32_t number_of_code_sizes = 0;
470 uint32_t number_of_distance_codes = 0;
471 uint32_t number_of_literal_codes = 0;
472 uint32_t symbol = 0;
473 uint32_t times_to_repeat = 0;
474
475 if( libqcow_deflate_bit_stream_get_value(
476 bit_stream,
477 14,
478 &number_of_code_sizes,
479 error ) != 1 )
480 {
481 libcerror_error_set(
482 error,
483 LIBCERROR_ERROR_DOMAIN_RUNTIME,
484 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
485 "%s: unable to retrieve value from bit stream.",
486 function );
487
488 return( -1 );
489 }
490 number_of_literal_codes = number_of_code_sizes & 0x0000001fUL;
491 number_of_code_sizes >>= 5;
492 number_of_distance_codes = number_of_code_sizes & 0x0000001fUL;
493 number_of_code_sizes >>= 5;
494
495 number_of_literal_codes += 257;
496
497 if( number_of_literal_codes > 286 )
498 {
499 libcerror_error_set(
500 error,
501 LIBCERROR_ERROR_DOMAIN_RUNTIME,
502 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
503 "%s: invalid number of literal codes value out of bounds.",
504 function );
505
506 return( -1 );
507 }
508 number_of_distance_codes += 1;
509
510 if( number_of_distance_codes > 30 )
511 {
512 libcerror_error_set(
513 error,
514 LIBCERROR_ERROR_DOMAIN_RUNTIME,
515 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
516 "%s: invalid number of distance codes value out of bounds.",
517 function );
518
519 return( -1 );
520 }
521 number_of_code_sizes += 4;
522
523 for( code_size_index = 0;
524 code_size_index < number_of_code_sizes;
525 code_size_index++ )
526 {
527 if( libqcow_deflate_bit_stream_get_value(
528 bit_stream,
529 3,
530 &code_size,
531 error ) != 1 )
532 {
533 libcerror_error_set(
534 error,
535 LIBCERROR_ERROR_DOMAIN_RUNTIME,
536 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
537 "%s: unable to retrieve value from bit stream.",
538 function );
539
540 return( -1 );
541 }
542 code_size_sequence = code_sizes_sequence[ code_size_index ];
543
544 code_size_array[ code_size_sequence ] = (uint16_t) code_size;
545 }
546 while( code_size_index < 19 )
547 {
548 code_size_sequence = code_sizes_sequence[ code_size_index++ ];
549
550 code_size_array[ code_size_sequence ] = 0;
551 }
552 if( libqcow_deflate_huffman_table_construct(
553 &codes_table,
554 code_size_array,
555 19,
556 error ) != 1 )
557 {
558 libcerror_error_set(
559 error,
560 LIBCERROR_ERROR_DOMAIN_RUNTIME,
561 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
562 "%s: unable to construct codes table.",
563 function );
564
565 return( -1 );
566 }
567 number_of_code_sizes = number_of_literal_codes + number_of_distance_codes;
568
569 code_size_index = 0;
570
571 while( code_size_index < number_of_code_sizes )
572 {
573 if( libqcow_deflate_bit_stream_get_huffman_encoded_value(
574 bit_stream,
575 &codes_table,
576 &symbol,
577 error ) != 1 )
578 {
579 libcerror_error_set(
580 error,
581 LIBCERROR_ERROR_DOMAIN_RUNTIME,
582 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
583 "%s: unable to retrieve literal value from bit stream.",
584 function );
585
586 return( -1 );
587 }
588 if( symbol < 16 )
589 {
590 code_size_array[ code_size_index++ ] = (uint16_t) symbol;
591
592 continue;
593 }
594 code_size = 0;
595
596 if( symbol == 16 )
597 {
598 if( code_size_index == 0 )
599 {
600 libcerror_error_set(
601 error,
602 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
603 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
604 "%s: invalid code size index value out of bounds.",
605 function );
606
607 return( -1 );
608 }
609 code_size = (uint32_t) code_size_array[ code_size_index - 1 ];
610
611 if( libqcow_deflate_bit_stream_get_value(
612 bit_stream,
613 2,
614 ×_to_repeat,
615 error ) != 1 )
616 {
617 libcerror_error_set(
618 error,
619 LIBCERROR_ERROR_DOMAIN_RUNTIME,
620 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
621 "%s: unable to retrieve value from bit stream.",
622 function );
623
624 return( -1 );
625 }
626 times_to_repeat += 3;
627 }
628 else if( symbol == 17 )
629 {
630 if( libqcow_deflate_bit_stream_get_value(
631 bit_stream,
632 3,
633 ×_to_repeat,
634 error ) != 1 )
635 {
636 libcerror_error_set(
637 error,
638 LIBCERROR_ERROR_DOMAIN_RUNTIME,
639 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
640 "%s: unable to retrieve value from bit stream.",
641 function );
642
643 return( -1 );
644 }
645 times_to_repeat += 3;
646 }
647 else if( symbol == 18 )
648 {
649 if( libqcow_deflate_bit_stream_get_value(
650 bit_stream,
651 7,
652 ×_to_repeat,
653 error ) != 1 )
654 {
655 libcerror_error_set(
656 error,
657 LIBCERROR_ERROR_DOMAIN_RUNTIME,
658 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
659 "%s: unable to retrieve value from bit stream.",
660 function );
661
662 return( -1 );
663 }
664 times_to_repeat += 11;
665 }
666 else
667 {
668 libcerror_error_set(
669 error,
670 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
671 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
672 "%s: invalid code value value out of bounds.",
673 function );
674
675 return( -1 );
676 }
677 if( ( code_size_index + times_to_repeat ) > number_of_code_sizes )
678 {
679 libcerror_error_set(
680 error,
681 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
682 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
683 "%s: invalid times to repeat value out of bounds.",
684 function );
685
686 return( -1 );
687 }
688 while( times_to_repeat > 0 )
689 {
690 code_size_array[ code_size_index++ ] = (uint16_t) code_size;
691
692 times_to_repeat--;
693 }
694 }
695 if( code_size_array[ 256 ] == 0 )
696 {
697 libcerror_error_set(
698 error,
699 LIBCERROR_ERROR_DOMAIN_RUNTIME,
700 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
701 "%s: end-of-block code value missing in literal codes array.",
702 function );
703
704 return( -1 );
705 }
706 if( libqcow_deflate_huffman_table_construct(
707 literals_table,
708 code_size_array,
709 number_of_literal_codes,
710 error ) != 1 )
711 {
712 libcerror_error_set(
713 error,
714 LIBCERROR_ERROR_DOMAIN_RUNTIME,
715 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
716 "%s: unable to construct literals table.",
717 function );
718
719 return( -1 );
720 }
721 if( libqcow_deflate_huffman_table_construct(
722 distances_table,
723 &( code_size_array[ number_of_literal_codes ] ),
724 number_of_distance_codes,
725 error ) != 1 )
726 {
727 libcerror_error_set(
728 error,
729 LIBCERROR_ERROR_DOMAIN_RUNTIME,
730 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
731 "%s: unable to construct distances table.",
732 function );
733
734 return( -1 );
735 }
736 return( 1 );
737 }
738
739 /* Initializes the fixed Huffman tables
740 * Returns 1 on success or -1 on error
741 */
libqcow_deflate_initialize_fixed_huffman_tables(libqcow_deflate_huffman_table_t * literals_table,libqcow_deflate_huffman_table_t * distances_table,libcerror_error_t ** error)742 int libqcow_deflate_initialize_fixed_huffman_tables(
743 libqcow_deflate_huffman_table_t *literals_table,
744 libqcow_deflate_huffman_table_t *distances_table,
745 libcerror_error_t **error )
746 {
747 uint16_t code_size_array[ 318 ];
748
749 static char *function = "libqcow_deflate_initialize_fixed_huffman_tables";
750 uint16_t symbol = 0;
751
752 for( symbol = 0;
753 symbol < 318;
754 symbol++ )
755 {
756 if( symbol < 144 )
757 {
758 code_size_array[ symbol ] = 8;
759 }
760 else if( symbol < 256 )
761 {
762 code_size_array[ symbol ] = 9;
763 }
764 else if( symbol < 280 )
765 {
766 code_size_array[ symbol ] = 7;
767 }
768 else if( symbol < 288 )
769 {
770 code_size_array[ symbol ] = 8;
771 }
772 else
773 {
774 code_size_array[ symbol ] = 5;
775 }
776 }
777 if( libqcow_deflate_huffman_table_construct(
778 literals_table,
779 code_size_array,
780 288,
781 error ) != 1 )
782 {
783 libcerror_error_set(
784 error,
785 LIBCERROR_ERROR_DOMAIN_RUNTIME,
786 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
787 "%s: unable to construct literals table.",
788 function );
789
790 return( -1 );
791 }
792 if( libqcow_deflate_huffman_table_construct(
793 distances_table,
794 &( code_size_array[ 288 ] ),
795 30,
796 error ) != 1 )
797 {
798 libcerror_error_set(
799 error,
800 LIBCERROR_ERROR_DOMAIN_RUNTIME,
801 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
802 "%s: unable to construct distances table.",
803 function );
804
805 return( -1 );
806 }
807 return( 1 );
808 }
809
810 /* Decodes a Huffman compressed block
811 * Returns 1 on success or -1 on error
812 */
libqcow_deflate_decode_huffman(libqcow_deflate_bit_stream_t * bit_stream,libqcow_deflate_huffman_table_t * literals_table,libqcow_deflate_huffman_table_t * distances_table,uint8_t * uncompressed_data,size_t uncompressed_data_size,size_t * uncompressed_data_offset,libcerror_error_t ** error)813 int libqcow_deflate_decode_huffman(
814 libqcow_deflate_bit_stream_t *bit_stream,
815 libqcow_deflate_huffman_table_t *literals_table,
816 libqcow_deflate_huffman_table_t *distances_table,
817 uint8_t *uncompressed_data,
818 size_t uncompressed_data_size,
819 size_t *uncompressed_data_offset,
820 libcerror_error_t **error )
821 {
822 uint16_t literal_codes_base[ 29 ] = {
823 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
824 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 };
825
826 uint16_t literal_codes_number_of_extra_bits[ 29 ] = {
827 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
828 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 };
829
830 uint16_t distance_codes_base[ 30 ] = {
831 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
832 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193,
833 12289, 16385, 24577 };
834
835 uint16_t distance_codes_number_of_extra_bits[ 30 ] = {
836 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
837 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 };
838
839 static char *function = "libqcow_deflate_decode_huffman";
840 size_t data_offset = 0;
841 uint32_t code_value = 0;
842 uint32_t extra_bits = 0;
843 uint16_t compression_offset = 0;
844 uint16_t compression_size = 0;
845 uint16_t number_of_extra_bits = 0;
846
847 if( uncompressed_data == NULL )
848 {
849 libcerror_error_set(
850 error,
851 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
852 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
853 "%s: invalid uncompressed data.",
854 function );
855
856 return( -1 );
857 }
858 if( uncompressed_data_size > (size_t) SSIZE_MAX )
859 {
860 libcerror_error_set(
861 error,
862 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
863 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
864 "%s: invalid uncompressed data size value exceeds maximum.",
865 function );
866
867 return( -1 );
868 }
869 if( uncompressed_data_offset == NULL )
870 {
871 libcerror_error_set(
872 error,
873 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
874 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
875 "%s: invalid uncompressed data offset.",
876 function );
877
878 return( -1 );
879 }
880 data_offset = *uncompressed_data_offset;
881
882 do
883 {
884 if( libqcow_deflate_bit_stream_get_huffman_encoded_value(
885 bit_stream,
886 literals_table,
887 &code_value,
888 error ) != 1 )
889 {
890 libcerror_error_set(
891 error,
892 LIBCERROR_ERROR_DOMAIN_RUNTIME,
893 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
894 "%s: unable to retrieve literal value from bit stream.",
895 function );
896
897 return( -1 );
898 }
899 if( code_value < 256 )
900 {
901 if( data_offset >= uncompressed_data_size )
902 {
903 libcerror_error_set(
904 error,
905 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
906 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
907 "%s: invalid uncompressed data value too small.",
908 function );
909
910 return( -1 );
911 }
912 uncompressed_data[ data_offset++ ] = (uint8_t) code_value;
913 }
914 else if( ( code_value > 256 )
915 && ( code_value < 286 ) )
916 {
917 code_value -= 257;
918
919 number_of_extra_bits = literal_codes_number_of_extra_bits[ code_value ];
920
921 if( libqcow_deflate_bit_stream_get_value(
922 bit_stream,
923 (uint8_t) number_of_extra_bits,
924 &extra_bits,
925 error ) != 1 )
926 {
927 libcerror_error_set(
928 error,
929 LIBCERROR_ERROR_DOMAIN_RUNTIME,
930 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
931 "%s: unable to retrieve literal extra value from bit stream.",
932 function );
933
934 return( -1 );
935 }
936 compression_size = literal_codes_base[ code_value ] + (uint16_t) extra_bits;
937
938 if( libqcow_deflate_bit_stream_get_huffman_encoded_value(
939 bit_stream,
940 distances_table,
941 &code_value,
942 error ) != 1 )
943 {
944 libcerror_error_set(
945 error,
946 LIBCERROR_ERROR_DOMAIN_RUNTIME,
947 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
948 "%s: unable to retrieve distance value from bit stream.",
949 function );
950
951 return( -1 );
952 }
953 number_of_extra_bits = distance_codes_number_of_extra_bits[ code_value ];
954
955 if( libqcow_deflate_bit_stream_get_value(
956 bit_stream,
957 (uint8_t) number_of_extra_bits,
958 &extra_bits,
959 error ) != 1 )
960 {
961 libcerror_error_set(
962 error,
963 LIBCERROR_ERROR_DOMAIN_RUNTIME,
964 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
965 "%s: unable to retrieve distance extra value from bit stream.",
966 function );
967
968 return( -1 );
969 }
970 compression_offset = distance_codes_base[ code_value ] + (uint16_t) extra_bits;
971
972 if( compression_offset > data_offset )
973 {
974 libcerror_error_set(
975 error,
976 LIBCERROR_ERROR_DOMAIN_RUNTIME,
977 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
978 "%s: invalid compression offset value out of bounds.",
979 function );
980
981 return( -1 );
982 }
983 if( ( data_offset + compression_size ) > uncompressed_data_size )
984 {
985 libcerror_error_set(
986 error,
987 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
988 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
989 "%s: invalid uncompressed data value too small.",
990 function );
991
992 return( -1 );
993 }
994 while( compression_size > 0 )
995 {
996 uncompressed_data[ data_offset ] = uncompressed_data[ data_offset - compression_offset ];
997
998 data_offset++;
999 compression_size--;
1000 }
1001 }
1002 else if( code_value != 256 )
1003 {
1004 libcerror_error_set(
1005 error,
1006 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1007 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1008 "%s: invalid code value: %" PRIu16 ".",
1009 function,
1010 code_value );
1011
1012 return( -1 );
1013 }
1014 }
1015 while( code_value != 256 );
1016
1017 *uncompressed_data_offset = data_offset;
1018
1019 return( 1 );
1020 }
1021
1022 /* Calculates the little-endian Adler-32 of a buffer
1023 * It uses the initial value to calculate a new Adler-32
1024 * Returns 1 if successful or -1 on error
1025 */
libqcow_deflate_calculate_adler32(uint32_t * checksum_value,const uint8_t * buffer,size_t size,uint32_t initial_value,libcerror_error_t ** error)1026 int libqcow_deflate_calculate_adler32(
1027 uint32_t *checksum_value,
1028 const uint8_t *buffer,
1029 size_t size,
1030 uint32_t initial_value,
1031 libcerror_error_t **error )
1032 {
1033 static char *function = "libqcow_deflate_calculate_adler32";
1034 size_t buffer_offset = 0;
1035 uint32_t lower_word = 0;
1036 uint32_t upper_word = 0;
1037 uint32_t value_32bit = 0;
1038 int block_index = 0;
1039
1040 if( checksum_value == NULL )
1041 {
1042 libcerror_error_set(
1043 error,
1044 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1045 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1046 "%s: invalid checksum value.",
1047 function );
1048
1049 return( -1 );
1050 }
1051 if( buffer == NULL )
1052 {
1053 libcerror_error_set(
1054 error,
1055 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1056 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1057 "%s: invalid buffer.",
1058 function );
1059
1060 return( -1 );
1061 }
1062 if( size > (size_t) SSIZE_MAX )
1063 {
1064 libcerror_error_set(
1065 error,
1066 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1067 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1068 "%s: invalid size value exceeds maximum.",
1069 function );
1070
1071 return( -1 );
1072 }
1073 lower_word = initial_value & 0xffff;
1074 upper_word = ( initial_value >> 16 ) & 0xffff;
1075
1076 while( size >= 0x15b0 )
1077 {
1078 /* The modulo calculation is needed per 5552 (0x15b0) bytes
1079 * 5552 / 16 = 347
1080 */
1081 for( block_index = 0;
1082 block_index < 347;
1083 block_index++ )
1084 {
1085 lower_word += buffer[ buffer_offset++ ];
1086 upper_word += lower_word;
1087
1088 lower_word += buffer[ buffer_offset++ ];
1089 upper_word += lower_word;
1090
1091 lower_word += buffer[ buffer_offset++ ];
1092 upper_word += lower_word;
1093
1094 lower_word += buffer[ buffer_offset++ ];
1095 upper_word += lower_word;
1096
1097 lower_word += buffer[ buffer_offset++ ];
1098 upper_word += lower_word;
1099
1100 lower_word += buffer[ buffer_offset++ ];
1101 upper_word += lower_word;
1102
1103 lower_word += buffer[ buffer_offset++ ];
1104 upper_word += lower_word;
1105
1106 lower_word += buffer[ buffer_offset++ ];
1107 upper_word += lower_word;
1108
1109 lower_word += buffer[ buffer_offset++ ];
1110 upper_word += lower_word;
1111
1112 lower_word += buffer[ buffer_offset++ ];
1113 upper_word += lower_word;
1114
1115 lower_word += buffer[ buffer_offset++ ];
1116 upper_word += lower_word;
1117
1118 lower_word += buffer[ buffer_offset++ ];
1119 upper_word += lower_word;
1120
1121 lower_word += buffer[ buffer_offset++ ];
1122 upper_word += lower_word;
1123
1124 lower_word += buffer[ buffer_offset++ ];
1125 upper_word += lower_word;
1126
1127 lower_word += buffer[ buffer_offset++ ];
1128 upper_word += lower_word;
1129
1130 lower_word += buffer[ buffer_offset++ ];
1131 upper_word += lower_word;
1132 }
1133 /* Optimized equivalent of:
1134 * lower_word %= 0xfff1
1135 */
1136 value_32bit = lower_word >> 16;
1137 lower_word &= 0x0000ffffUL;
1138 lower_word += ( value_32bit << 4 ) - value_32bit;
1139
1140 if( lower_word > 65521 )
1141 {
1142 value_32bit = lower_word >> 16;
1143 lower_word &= 0x0000ffffUL;
1144 lower_word += ( value_32bit << 4 ) - value_32bit;
1145 }
1146 if( lower_word >= 65521 )
1147 {
1148 lower_word -= 65521;
1149 }
1150 /* Optimized equivalent of:
1151 * upper_word %= 0xfff1
1152 */
1153 value_32bit = upper_word >> 16;
1154 upper_word &= 0x0000ffffUL;
1155 upper_word += ( value_32bit << 4 ) - value_32bit;
1156
1157 if( upper_word > 65521 )
1158 {
1159 value_32bit = upper_word >> 16;
1160 upper_word &= 0x0000ffffUL;
1161 upper_word += ( value_32bit << 4 ) - value_32bit;
1162 }
1163 if( upper_word >= 65521 )
1164 {
1165 upper_word -= 65521;
1166 }
1167 size -= 0x15b0;
1168 }
1169 if( size > 0 )
1170 {
1171 while( size > 16 )
1172 {
1173 lower_word += buffer[ buffer_offset++ ];
1174 upper_word += lower_word;
1175
1176 lower_word += buffer[ buffer_offset++ ];
1177 upper_word += lower_word;
1178
1179 lower_word += buffer[ buffer_offset++ ];
1180 upper_word += lower_word;
1181
1182 lower_word += buffer[ buffer_offset++ ];
1183 upper_word += lower_word;
1184
1185 lower_word += buffer[ buffer_offset++ ];
1186 upper_word += lower_word;
1187
1188 lower_word += buffer[ buffer_offset++ ];
1189 upper_word += lower_word;
1190
1191 lower_word += buffer[ buffer_offset++ ];
1192 upper_word += lower_word;
1193
1194 lower_word += buffer[ buffer_offset++ ];
1195 upper_word += lower_word;
1196
1197 lower_word += buffer[ buffer_offset++ ];
1198 upper_word += lower_word;
1199
1200 lower_word += buffer[ buffer_offset++ ];
1201 upper_word += lower_word;
1202
1203 lower_word += buffer[ buffer_offset++ ];
1204 upper_word += lower_word;
1205
1206 lower_word += buffer[ buffer_offset++ ];
1207 upper_word += lower_word;
1208
1209 lower_word += buffer[ buffer_offset++ ];
1210 upper_word += lower_word;
1211
1212 lower_word += buffer[ buffer_offset++ ];
1213 upper_word += lower_word;
1214
1215 lower_word += buffer[ buffer_offset++ ];
1216 upper_word += lower_word;
1217
1218 lower_word += buffer[ buffer_offset++ ];
1219 upper_word += lower_word;
1220
1221 size -= 16;
1222 }
1223 while( size > 0 )
1224 {
1225 lower_word += buffer[ buffer_offset++ ];
1226 upper_word += lower_word;
1227
1228 size--;
1229 }
1230 /* Optimized equivalent of:
1231 * lower_word %= 0xfff1
1232 */
1233 value_32bit = lower_word >> 16;
1234 lower_word &= 0x0000ffffUL;
1235 lower_word += ( value_32bit << 4 ) - value_32bit;
1236
1237 if( lower_word > 65521 )
1238 {
1239 value_32bit = lower_word >> 16;
1240 lower_word &= 0x0000ffffUL;
1241 lower_word += ( value_32bit << 4 ) - value_32bit;
1242 }
1243 if( lower_word >= 65521 )
1244 {
1245 lower_word -= 65521;
1246 }
1247 /* Optimized equivalent of:
1248 * upper_word %= 0xfff1
1249 */
1250 value_32bit = upper_word >> 16;
1251 upper_word &= 0x0000ffffUL;
1252 upper_word += ( value_32bit << 4 ) - value_32bit;
1253
1254 if( upper_word > 65521 )
1255 {
1256 value_32bit = upper_word >> 16;
1257 upper_word &= 0x0000ffffUL;
1258 upper_word += ( value_32bit << 4 ) - value_32bit;
1259 }
1260 if( upper_word >= 65521 )
1261 {
1262 upper_word -= 65521;
1263 }
1264 }
1265 *checksum_value = ( upper_word << 16 ) | lower_word;
1266
1267 return( 1 );
1268 }
1269
1270 /* Reads the compressed data header
1271 * Returns 1 on success or -1 on error
1272 */
libqcow_deflate_read_data_header(const uint8_t * compressed_data,size_t compressed_data_size,size_t * compressed_data_offset,libcerror_error_t ** error)1273 int libqcow_deflate_read_data_header(
1274 const uint8_t *compressed_data,
1275 size_t compressed_data_size,
1276 size_t *compressed_data_offset,
1277 libcerror_error_t **error )
1278 {
1279 static char *function = "libqcow_deflate_read_data_header";
1280 size_t safe_offset = 0;
1281 uint32_t compression_window_size = 0;
1282 uint32_t preset_dictionary_identifier = 0;
1283 uint8_t flags = 0;
1284 uint8_t compression_data = 0;
1285 uint8_t compression_information = 0;
1286 uint8_t compression_method = 0;
1287 uint8_t compression_window_bits = 0;
1288
1289 if( compressed_data == NULL )
1290 {
1291 libcerror_error_set(
1292 error,
1293 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1294 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1295 "%s: invalid compressed data.",
1296 function );
1297
1298 return( -1 );
1299 }
1300 if( compressed_data_size > (size_t) SSIZE_MAX )
1301 {
1302 libcerror_error_set(
1303 error,
1304 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1305 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1306 "%s: invalid compressed data size value exceeds maximum.",
1307 function );
1308
1309 return( -1 );
1310 }
1311 if( compressed_data_offset == NULL )
1312 {
1313 libcerror_error_set(
1314 error,
1315 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1316 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1317 "%s: invalid compressed data offset.",
1318 function );
1319
1320 return( -1 );
1321 }
1322 safe_offset = *compressed_data_offset;
1323
1324 if( ( compressed_data_size < 2 )
1325 || ( safe_offset > ( compressed_data_size - 2 ) ) )
1326 {
1327 libcerror_error_set(
1328 error,
1329 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1330 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
1331 "%s: invalid compressed data value too small.",
1332 function );
1333
1334 return( -1 );
1335 }
1336 compression_data = compressed_data[ safe_offset++ ];
1337 flags = compressed_data[ safe_offset++ ];
1338
1339 compression_method = compression_data & 0x0f;
1340 compression_information = compression_data >> 4;
1341
1342 /* TODO validate check bits */
1343 if( ( flags & 0x20 ) != 0 )
1344 {
1345 if( ( compressed_data_size < 6 )
1346 || ( safe_offset > ( compressed_data_size - 6 ) ) )
1347 {
1348 libcerror_error_set(
1349 error,
1350 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1351 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
1352 "%s: invalid compressed data value too small.",
1353 function );
1354
1355 return( -1 );
1356 }
1357 byte_stream_copy_to_uint32_big_endian(
1358 &( compressed_data[ 2 ] ),
1359 preset_dictionary_identifier );
1360
1361 safe_offset += 4;
1362 }
1363 if( compression_method != 8 )
1364 {
1365 libcerror_error_set(
1366 error,
1367 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1368 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
1369 "%s: unsupported compression method: %" PRIu8 ".",
1370 function,
1371 compression_method );
1372
1373 return( -1 );
1374 }
1375 compression_window_bits = (uint8_t) compression_information + 8;
1376 compression_window_size = (uint32_t) 1UL << compression_window_bits;
1377
1378 if( compression_window_size > 32768 )
1379 {
1380 libcerror_error_set(
1381 error,
1382 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1383 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
1384 "%s: unsupported compression window size: %" PRIu32 ".",
1385 function,
1386 compression_window_size );
1387
1388 return( -1 );
1389 }
1390 *compressed_data_offset += safe_offset;
1391
1392 return( 1 );
1393 }
1394
1395 /* Reads a block of compressed data
1396 * Returns 1 on success or -1 on error
1397 */
libqcow_deflate_read_block(libqcow_deflate_bit_stream_t * bit_stream,uint8_t * uncompressed_data,size_t uncompressed_data_size,size_t * uncompressed_data_offset,uint8_t * last_block_flag,libcerror_error_t ** error)1398 int libqcow_deflate_read_block(
1399 libqcow_deflate_bit_stream_t *bit_stream,
1400 uint8_t *uncompressed_data,
1401 size_t uncompressed_data_size,
1402 size_t *uncompressed_data_offset,
1403 uint8_t *last_block_flag,
1404 libcerror_error_t **error )
1405 {
1406 libqcow_deflate_huffman_table_t dynamic_huffman_distances_table;
1407 libqcow_deflate_huffman_table_t dynamic_huffman_literals_table;
1408
1409 static char *function = "libqcow_deflate_read_block";
1410 size_t safe_uncompressed_data_offset = 0;
1411 uint32_t block_size = 0;
1412 uint32_t block_size_copy = 0;
1413 uint32_t value_32bit = 0;
1414 uint8_t block_type = 0;
1415 uint8_t skip_bits = 0;
1416
1417 if( bit_stream == NULL )
1418 {
1419 libcerror_error_set(
1420 error,
1421 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1422 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1423 "%s: invalid bit stream.",
1424 function );
1425
1426 return( -1 );
1427 }
1428 if( uncompressed_data == NULL )
1429 {
1430 libcerror_error_set(
1431 error,
1432 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1433 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1434 "%s: invalid uncompressed data.",
1435 function );
1436
1437 return( -1 );
1438 }
1439 if( uncompressed_data_size > (size_t) SSIZE_MAX )
1440 {
1441 libcerror_error_set(
1442 error,
1443 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1444 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1445 "%s: invalid uncompressed data size value exceeds maximum.",
1446 function );
1447
1448 return( -1 );
1449 }
1450 if( uncompressed_data_offset == NULL )
1451 {
1452 libcerror_error_set(
1453 error,
1454 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1455 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1456 "%s: invalid uncompressed data.",
1457 function );
1458
1459 return( -1 );
1460 }
1461 if( last_block_flag == NULL )
1462 {
1463 libcerror_error_set(
1464 error,
1465 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1466 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1467 "%s: invalid last block flag.",
1468 function );
1469
1470 return( -1 );
1471 }
1472 safe_uncompressed_data_offset = *uncompressed_data_offset;
1473
1474 if( libqcow_deflate_fixed_huffman_tables_initialized == 0 )
1475 {
1476 if( libqcow_deflate_initialize_fixed_huffman_tables(
1477 &libqcow_deflate_fixed_huffman_literals_table,
1478 &libqcow_deflate_fixed_huffman_distances_table,
1479 error ) != 1 )
1480 {
1481 libcerror_error_set(
1482 error,
1483 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1484 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
1485 "%s: unable to construct fixed Huffman tables.",
1486 function );
1487
1488 return( -1 );
1489 }
1490 libqcow_deflate_fixed_huffman_tables_initialized = 1;
1491 }
1492 /* TODO find optimized solution to read bit stream from bytes */
1493
1494 if( libqcow_deflate_bit_stream_get_value(
1495 bit_stream,
1496 3,
1497 &value_32bit,
1498 error ) != 1 )
1499 {
1500 libcerror_error_set(
1501 error,
1502 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1503 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1504 "%s: unable to retrieve value from bit stream.",
1505 function );
1506
1507 return( -1 );
1508 }
1509 *last_block_flag = (uint8_t) ( value_32bit & 0x00000001UL );
1510 value_32bit >>= 1;
1511 block_type = (uint8_t) value_32bit;
1512
1513 switch( block_type )
1514 {
1515 case LIBQCOW_DEFLATE_BLOCK_TYPE_UNCOMPRESSED:
1516 /* Ignore the bits in the buffer upto the next byte
1517 */
1518 skip_bits = bit_stream->bit_buffer_size & 0x07;
1519
1520 if( skip_bits > 0 )
1521 {
1522 if( libqcow_deflate_bit_stream_get_value(
1523 bit_stream,
1524 skip_bits,
1525 &value_32bit,
1526 error ) != 1 )
1527 {
1528 libcerror_error_set(
1529 error,
1530 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1531 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1532 "%s: unable to retrieve value from bit stream.",
1533 function );
1534
1535 return( -1 );
1536 }
1537 }
1538 if( libqcow_deflate_bit_stream_get_value(
1539 bit_stream,
1540 32,
1541 &block_size,
1542 error ) != 1 )
1543 {
1544 libcerror_error_set(
1545 error,
1546 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1547 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1548 "%s: unable to retrieve value from bit stream.",
1549 function );
1550
1551 return( -1 );
1552 }
1553 block_size_copy = ( block_size >> 16 ) ^ 0x0000ffffUL;
1554 block_size &= 0x0000ffffUL;
1555
1556 if( block_size != block_size_copy )
1557 {
1558 libcerror_error_set(
1559 error,
1560 LIBCERROR_ERROR_DOMAIN_INPUT,
1561 LIBCERROR_INPUT_ERROR_VALUE_MISMATCH,
1562 "%s: mismatch in block size ( %" PRIu32 " != %" PRIu32 " ).",
1563 function,
1564 block_size,
1565 block_size_copy );
1566
1567 return( -1 );
1568 }
1569 if( block_size == 0 )
1570 {
1571 break;
1572 }
1573 if( (size_t) block_size > ( bit_stream->byte_stream_size - bit_stream->byte_stream_offset ) )
1574 {
1575 libcerror_error_set(
1576 error,
1577 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1578 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
1579 "%s: invalid compressed data value too small.",
1580 function );
1581
1582 return( -1 );
1583 }
1584 if( (size_t) block_size > ( uncompressed_data_size - safe_uncompressed_data_offset ) )
1585 {
1586 libcerror_error_set(
1587 error,
1588 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1589 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
1590 "%s: invalid uncompressed data value too small.",
1591 function );
1592
1593 return( -1 );
1594 }
1595 if( memory_copy(
1596 &( uncompressed_data[ safe_uncompressed_data_offset ] ),
1597 &( bit_stream->byte_stream[ bit_stream->byte_stream_offset ] ),
1598 (size_t) block_size ) == NULL )
1599 {
1600 libcerror_error_set(
1601 error,
1602 LIBCERROR_ERROR_DOMAIN_MEMORY,
1603 LIBCERROR_MEMORY_ERROR_COPY_FAILED,
1604 "%s: unable to initialize lz buffer.",
1605 function );
1606
1607 return( -1 );
1608 }
1609 bit_stream->byte_stream_offset += block_size;
1610 safe_uncompressed_data_offset += block_size;
1611
1612 /* Flush the bit-stream buffer
1613 */
1614 bit_stream->bit_buffer = 0;
1615 bit_stream->bit_buffer_size = 0;
1616
1617 break;
1618
1619 case LIBQCOW_DEFLATE_BLOCK_TYPE_HUFFMAN_FIXED:
1620 if( libqcow_deflate_decode_huffman(
1621 bit_stream,
1622 &libqcow_deflate_fixed_huffman_literals_table,
1623 &libqcow_deflate_fixed_huffman_distances_table,
1624 uncompressed_data,
1625 uncompressed_data_size,
1626 &safe_uncompressed_data_offset,
1627 error ) != 1 )
1628 {
1629 libcerror_error_set(
1630 error,
1631 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1632 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1633 "%s: unable to decode fixed Huffman encoded bit stream.",
1634 function );
1635
1636 return( -1 );
1637 }
1638 break;
1639
1640 case LIBQCOW_DEFLATE_BLOCK_TYPE_HUFFMAN_DYNAMIC:
1641 if( libqcow_deflate_initialize_dynamic_huffman_tables(
1642 bit_stream,
1643 &dynamic_huffman_literals_table,
1644 &dynamic_huffman_distances_table,
1645 error ) != 1 )
1646 {
1647 libcerror_error_set(
1648 error,
1649 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1650 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
1651 "%s: unable to construct dynamic Huffman tables.",
1652 function );
1653
1654 return( -1 );
1655 }
1656 if( libqcow_deflate_decode_huffman(
1657 bit_stream,
1658 &dynamic_huffman_literals_table,
1659 &dynamic_huffman_distances_table,
1660 uncompressed_data,
1661 uncompressed_data_size,
1662 &safe_uncompressed_data_offset,
1663 error ) != 1 )
1664 {
1665 libcerror_error_set(
1666 error,
1667 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1668 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1669 "%s: unable to decode dynamic Huffman encoded bit stream.",
1670 function );
1671
1672 return( -1 );
1673 }
1674 break;
1675
1676 case LIBQCOW_DEFLATE_BLOCK_TYPE_RESERVED:
1677 default:
1678 libcerror_error_set(
1679 error,
1680 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1681 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
1682 "%s: unsupported block type.",
1683 function );
1684
1685 return( -1 );
1686 }
1687 *uncompressed_data_offset = safe_uncompressed_data_offset;
1688
1689 return( 1 );
1690 }
1691
1692 /* Decompresses data using deflate compression
1693 * Returns 1 on success or -1 on error
1694 */
libqcow_deflate_decompress(const uint8_t * compressed_data,size_t compressed_data_size,uint8_t * uncompressed_data,size_t * uncompressed_data_size,libcerror_error_t ** error)1695 int libqcow_deflate_decompress(
1696 const uint8_t *compressed_data,
1697 size_t compressed_data_size,
1698 uint8_t *uncompressed_data,
1699 size_t *uncompressed_data_size,
1700 libcerror_error_t **error )
1701 {
1702 libqcow_deflate_bit_stream_t bit_stream;
1703
1704 static char *function = "libqcow_deflate_decompress";
1705 size_t compressed_data_offset = 0;
1706 size_t uncompressed_data_offset = 0;
1707 uint8_t last_block_flag = 0;
1708
1709 if( compressed_data == NULL )
1710 {
1711 libcerror_error_set(
1712 error,
1713 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1714 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1715 "%s: invalid compressed data.",
1716 function );
1717
1718 return( -1 );
1719 }
1720 if( compressed_data_size > (size_t) SSIZE_MAX )
1721 {
1722 libcerror_error_set(
1723 error,
1724 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1725 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1726 "%s: invalid compressed data size value exceeds maximum.",
1727 function );
1728
1729 return( -1 );
1730 }
1731 if( uncompressed_data == NULL )
1732 {
1733 libcerror_error_set(
1734 error,
1735 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1736 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1737 "%s: invalid uncompressed data.",
1738 function );
1739
1740 return( -1 );
1741 }
1742 if( uncompressed_data_size == NULL )
1743 {
1744 libcerror_error_set(
1745 error,
1746 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1747 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1748 "%s: invalid uncompressed data size.",
1749 function );
1750
1751 return( -1 );
1752 }
1753 if( *uncompressed_data_size > (size_t) SSIZE_MAX )
1754 {
1755 libcerror_error_set(
1756 error,
1757 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1758 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1759 "%s: invalid uncompressed data size value exceeds maximum.",
1760 function );
1761
1762 return( -1 );
1763 }
1764 if( compressed_data_offset >= compressed_data_size )
1765 {
1766 libcerror_error_set(
1767 error,
1768 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1769 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
1770 "%s: invalid compressed data value too small.",
1771 function );
1772
1773 return( -1 );
1774 }
1775 bit_stream.byte_stream = compressed_data;
1776 bit_stream.byte_stream_size = compressed_data_size;
1777 bit_stream.byte_stream_offset = compressed_data_offset;
1778 bit_stream.bit_buffer = 0;
1779 bit_stream.bit_buffer_size = 0;
1780
1781 while( bit_stream.byte_stream_offset < bit_stream.byte_stream_size )
1782 {
1783 if( libqcow_deflate_read_block(
1784 &bit_stream,
1785 uncompressed_data,
1786 *uncompressed_data_size,
1787 &uncompressed_data_offset,
1788 &last_block_flag,
1789 error ) != 1 )
1790 {
1791 libcerror_error_set(
1792 error,
1793 LIBCERROR_ERROR_DOMAIN_IO,
1794 LIBCERROR_IO_ERROR_READ_FAILED,
1795 "%s: unable to read block of compressed data.",
1796 function );
1797
1798 return( -1 );
1799 }
1800 if( last_block_flag != 0 )
1801 {
1802 break;
1803 }
1804 }
1805 *uncompressed_data_size = uncompressed_data_offset;
1806
1807 return( 1 );
1808 }
1809
1810 /* Decompresses data using zlib compression
1811 * Returns 1 on success or -1 on error
1812 */
libqcow_deflate_decompress_zlib(const uint8_t * compressed_data,size_t compressed_data_size,uint8_t * uncompressed_data,size_t * uncompressed_data_size,libcerror_error_t ** error)1813 int libqcow_deflate_decompress_zlib(
1814 const uint8_t *compressed_data,
1815 size_t compressed_data_size,
1816 uint8_t *uncompressed_data,
1817 size_t *uncompressed_data_size,
1818 libcerror_error_t **error )
1819 {
1820 libqcow_deflate_bit_stream_t bit_stream;
1821
1822 static char *function = "libqcow_deflate_decompress_zlib";
1823 size_t compressed_data_offset = 0;
1824 size_t uncompressed_data_offset = 0;
1825 uint32_t calculated_checksum = 0;
1826 uint32_t stored_checksum = 0;
1827 uint8_t last_block_flag = 0;
1828
1829 if( compressed_data == NULL )
1830 {
1831 libcerror_error_set(
1832 error,
1833 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1834 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1835 "%s: invalid compressed data.",
1836 function );
1837
1838 return( -1 );
1839 }
1840 if( compressed_data_size > (size_t) SSIZE_MAX )
1841 {
1842 libcerror_error_set(
1843 error,
1844 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1845 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1846 "%s: invalid compressed data size value exceeds maximum.",
1847 function );
1848
1849 return( -1 );
1850 }
1851 if( uncompressed_data == NULL )
1852 {
1853 libcerror_error_set(
1854 error,
1855 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1856 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1857 "%s: invalid uncompressed data.",
1858 function );
1859
1860 return( -1 );
1861 }
1862 if( uncompressed_data_size == NULL )
1863 {
1864 libcerror_error_set(
1865 error,
1866 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1867 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1868 "%s: invalid uncompressed data size.",
1869 function );
1870
1871 return( -1 );
1872 }
1873 if( *uncompressed_data_size > (size_t) SSIZE_MAX )
1874 {
1875 libcerror_error_set(
1876 error,
1877 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1878 LIBCERROR_ARGUMENT_ERROR_VALUE_EXCEEDS_MAXIMUM,
1879 "%s: invalid uncompressed data size value exceeds maximum.",
1880 function );
1881
1882 return( -1 );
1883 }
1884 if( libqcow_deflate_read_data_header(
1885 compressed_data,
1886 compressed_data_size,
1887 &compressed_data_offset,
1888 error ) != 1 )
1889 {
1890 libcerror_error_set(
1891 error,
1892 LIBCERROR_ERROR_DOMAIN_IO,
1893 LIBCERROR_IO_ERROR_READ_FAILED,
1894 "%s: unable to read data header.",
1895 function );
1896
1897 return( -1 );
1898 }
1899 if( compressed_data_offset >= compressed_data_size )
1900 {
1901 libcerror_error_set(
1902 error,
1903 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1904 LIBCERROR_ARGUMENT_ERROR_VALUE_TOO_SMALL,
1905 "%s: invalid compressed data value too small.",
1906 function );
1907
1908 return( -1 );
1909 }
1910 bit_stream.byte_stream = compressed_data;
1911 bit_stream.byte_stream_size = compressed_data_size;
1912 bit_stream.byte_stream_offset = compressed_data_offset;
1913 bit_stream.bit_buffer = 0;
1914 bit_stream.bit_buffer_size = 0;
1915
1916 while( bit_stream.byte_stream_offset < bit_stream.byte_stream_size )
1917 {
1918 if( libqcow_deflate_read_block(
1919 &bit_stream,
1920 uncompressed_data,
1921 *uncompressed_data_size,
1922 &uncompressed_data_offset,
1923 &last_block_flag,
1924 error ) != 1 )
1925 {
1926 libcerror_error_set(
1927 error,
1928 LIBCERROR_ERROR_DOMAIN_IO,
1929 LIBCERROR_IO_ERROR_READ_FAILED,
1930 "%s: unable to read block of compressed data.",
1931 function );
1932
1933 return( -1 );
1934 }
1935 if( last_block_flag != 0 )
1936 {
1937 break;
1938 }
1939 }
1940 if( ( bit_stream.byte_stream_size - bit_stream.byte_stream_offset ) >= 4 )
1941 {
1942 while( bit_stream.bit_buffer_size >= 8 )
1943 {
1944 bit_stream.byte_stream_offset -= 1;
1945 bit_stream.bit_buffer_size -= 8;
1946 }
1947 byte_stream_copy_to_uint32_big_endian(
1948 &( bit_stream.byte_stream[ bit_stream.byte_stream_offset ] ),
1949 stored_checksum );
1950
1951 if( libqcow_deflate_calculate_adler32(
1952 &calculated_checksum,
1953 uncompressed_data,
1954 uncompressed_data_offset,
1955 1,
1956 error ) != 1 )
1957 {
1958 libcerror_error_set(
1959 error,
1960 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1961 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
1962 "%s: unable to calculate checksum.",
1963 function );
1964
1965 return( -1 );
1966 }
1967 if( stored_checksum != calculated_checksum )
1968 {
1969 libcerror_error_set(
1970 error,
1971 LIBCERROR_ERROR_DOMAIN_INPUT,
1972 LIBCERROR_INPUT_ERROR_CHECKSUM_MISMATCH,
1973 "%s: checksum does not match (stored: 0x%08" PRIx32 ", calculated: 0x%08" PRIx32 ").",
1974 function,
1975 stored_checksum,
1976 calculated_checksum );
1977
1978 return( -1 );
1979 }
1980 }
1981 *uncompressed_data_size = uncompressed_data_offset;
1982
1983 return( 1 );
1984 }
1985
1986