1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief Collects and verifies integrity of Stream size information
6 // Copyright (C) 2007 Lasse Collin
8 // This library is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Lesser General Public
10 // License as published by the Free Software Foundation; either
11 // version 2.1 of the License, or (at your option) any later version.
13 // This library 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 GNU
16 // Lesser General Public License for more details.
18 ///////////////////////////////////////////////////////////////////////////////
25 /// Known Size of Header Metadata Block; here's some
27 /// - LZMA_VLI_VALUE_UNKNOWN indicates that we don't know
28 /// if Header Metadata Block is present.
29 /// - 0 indicates that Header Metadata Block is not present.
30 lzma_vli header_metadata_size;
32 /// Known Total Size of the Data Blocks in the Stream
35 /// Known Uncompressed Size of the Data Blocks in the Stream
36 lzma_vli uncompressed_size;
38 /// Known Size of Footer Metadata Block
39 lzma_vli footer_metadata_size;
43 /// Sum of Total Size fields stored to the Index so far
46 /// Sum of Uncompressed Size fields stored to the Index so far
47 lzma_vli uncompressed_size;
49 /// First Index Record in the list, or NULL if Index is empty.
52 /// Number of Index Records
55 /// Number of Index Records
56 size_t incomplete_count;
58 /// True when we know that no more Records will get added
63 /// Start offset of the Stream. This is needed to calculate
64 /// lzma_info_iter.stream_offset.
65 lzma_vli stream_start_offset;
67 /// True if Index is present in Header Metadata Block
68 bool has_index_in_header_metadata;
72 //////////////////////
73 // Create/Reset/End //
74 //////////////////////
77 index_init(lzma_info *info)
79 info->index.total_size = 0;
80 info->index.uncompressed_size = 0;
81 info->index.head = NULL;
82 info->index.record_count = 0;
83 info->index.incomplete_count = 0;
84 info->index.is_final = false;
90 info_init(lzma_info *info)
92 info->known.header_metadata_size = LZMA_VLI_VALUE_UNKNOWN;
93 info->known.total_size = LZMA_VLI_VALUE_UNKNOWN;
94 info->known.uncompressed_size = LZMA_VLI_VALUE_UNKNOWN;
95 info->known.footer_metadata_size = LZMA_VLI_VALUE_UNKNOWN;
96 info->stream_start_offset = 0;
97 info->has_index_in_header_metadata = false;
105 extern LZMA_API lzma_info *
106 lzma_info_init(lzma_info *info, lzma_allocator *allocator)
109 info = lzma_alloc(sizeof(lzma_info), allocator);
111 lzma_index_free(info->index.head, allocator);
121 lzma_info_free(lzma_info *info, lzma_allocator *allocator)
123 lzma_index_free(info->index.head, allocator);
124 lzma_free(info, allocator);
134 set_size(lzma_vli new_size, lzma_vli *known_size, lzma_vli index_size,
137 assert(new_size <= LZMA_VLI_VALUE_MAX);
139 lzma_ret ret = LZMA_OK;
141 if (forbid_zero && new_size == 0)
142 ret = LZMA_PROG_ERROR;
143 else if (index_size > new_size)
144 ret = LZMA_DATA_ERROR;
145 else if (*known_size == LZMA_VLI_VALUE_UNKNOWN)
146 *known_size = new_size;
147 else if (*known_size != new_size)
148 ret = LZMA_DATA_ERROR;
154 extern LZMA_API lzma_ret
155 lzma_info_size_set(lzma_info *info, lzma_info_size type, lzma_vli size)
157 if (size > LZMA_VLI_VALUE_MAX)
158 return LZMA_PROG_ERROR;
161 case LZMA_INFO_STREAM_START:
162 info->stream_start_offset = size;
165 case LZMA_INFO_HEADER_METADATA:
166 return set_size(size, &info->known.header_metadata_size,
169 case LZMA_INFO_TOTAL:
170 return set_size(size, &info->known.total_size,
171 info->index.total_size, true);
173 case LZMA_INFO_UNCOMPRESSED:
174 return set_size(size, &info->known.uncompressed_size,
175 info->index.uncompressed_size, false);
177 case LZMA_INFO_FOOTER_METADATA:
178 return set_size(size, &info->known.footer_metadata_size,
182 return LZMA_PROG_ERROR;
186 extern LZMA_API lzma_ret
187 lzma_info_index_set(lzma_info *info, lzma_allocator *allocator,
188 lzma_index *i_new, lzma_bool eat_index)
191 return LZMA_PROG_ERROR;
193 lzma_index *i_old = info->index.head;
197 // If the new Index has fewer Records than the old one,
198 // the new Index cannot be valid.
200 return LZMA_DATA_ERROR;
202 // The new Index must be complete i.e. no unknown
204 if (i_new->total_size > LZMA_VLI_VALUE_MAX
205 || i_new->uncompressed_size
206 > LZMA_VLI_VALUE_MAX) {
208 lzma_index_free(i_new, allocator);
210 return LZMA_PROG_ERROR;
213 // Compare the values from the new Index with the old
214 // Index. The old Index may be incomplete; in that
216 // - use the value from the new Index as is;
217 // - update the appropriate info->index.foo_size; and
218 // - decrease the count of incomplete Index Records.
219 bool was_incomplete = false;
221 if (i_old->total_size == LZMA_VLI_VALUE_UNKNOWN) {
222 assert(!info->index.is_final);
223 was_incomplete = true;
225 i_old->total_size = i_new->total_size;
227 if (lzma_vli_add(info->index.total_size,
228 i_new->total_size)) {
230 lzma_index_free(i_new,
233 return LZMA_PROG_ERROR;
235 } else if (i_old->total_size != i_new->total_size) {
237 lzma_index_free(i_new, allocator);
239 return LZMA_DATA_ERROR;
242 if (i_old->uncompressed_size
243 == LZMA_VLI_VALUE_UNKNOWN) {
244 assert(!info->index.is_final);
245 was_incomplete = true;
247 i_old->uncompressed_size
248 = i_new->uncompressed_size;
250 if (lzma_vli_add(info->index.uncompressed_size,
251 i_new->uncompressed_size)) {
253 lzma_index_free(i_new,
256 return LZMA_PROG_ERROR;
258 } else if (i_old->uncompressed_size
259 != i_new->uncompressed_size) {
261 lzma_index_free(i_new, allocator);
263 return LZMA_DATA_ERROR;
266 if (was_incomplete) {
267 assert(!info->index.is_final);
268 assert(info->index.incomplete_count > 0);
269 --info->index.incomplete_count;
272 // Get rid of *i_new. It's now identical with *i_old.
273 lzma_index *tmp = i_new->next;
275 lzma_free(i_new, allocator);
279 // We want to leave i_old pointing to the last
280 // Index Record in the old Index. This way we can
281 // concatenate the possible new Records from i_new.
282 if (i_old->next == NULL)
289 assert(info->index.incomplete_count == 0);
291 // If Index was already known to be final, i_new must be NULL now.
292 // The new Index cannot contain more Records that we already have.
293 if (info->index.is_final) {
294 assert(info->index.head != NULL);
298 lzma_index_free(i_new, allocator);
300 return LZMA_DATA_ERROR;
306 // The rest of the new Index is merged to the old Index. Keep the
307 // current i_new pointer in available. We need it when merging the
308 // new Index with the old one, and if an error occurs so we can
309 // get rid of the broken part of the new Index.
310 lzma_index *i_start = i_new;
311 while (i_new != NULL) {
312 // The new Index must be complete i.e. no unknown values.
313 if (i_new->total_size > LZMA_VLI_VALUE_MAX
314 || i_new->uncompressed_size
315 > LZMA_VLI_VALUE_MAX) {
317 lzma_index_free(i_start, allocator);
319 return LZMA_PROG_ERROR;
322 // Update info->index.foo_sizes.
323 if (lzma_vli_add(info->index.total_size, i_new->total_size)
324 || lzma_vli_add(info->index.uncompressed_size,
325 i_new->uncompressed_size)) {
327 lzma_index_free(i_start, allocator);
329 return LZMA_PROG_ERROR;
332 ++info->index.record_count;
336 // All the Records in the new Index are good, and info->index.foo_sizes
337 // were successfully updated.
338 if (lzma_info_index_finish(info) != LZMA_OK) {
340 lzma_index_free(i_start, allocator);
342 return LZMA_DATA_ERROR;
345 // The Index is ready to be merged. If we aren't supposed to eat
346 // the Index, make a copy of it first.
347 if (!eat_index && i_start != NULL) {
348 i_start = lzma_index_dup(i_start, allocator);
350 return LZMA_MEM_ERROR;
353 // Concatenate the new Index with the old one. Note that it is
354 // possible that we don't have any old Index.
355 if (info->index.head == NULL)
356 info->index.head = i_start;
358 i_old->next = i_start;
364 extern LZMA_API lzma_ret
365 lzma_info_metadata_set(lzma_info *info, lzma_allocator *allocator,
366 lzma_metadata *metadata, lzma_bool is_header_metadata,
369 // Validate *metadata.
370 if (metadata->header_metadata_size > LZMA_VLI_VALUE_MAX
371 || !lzma_vli_is_valid(metadata->total_size)
372 || !lzma_vli_is_valid(metadata->uncompressed_size)) {
374 lzma_index_free(metadata->index, allocator);
375 metadata->index = NULL;
378 return LZMA_PROG_ERROR;
382 if (metadata->index != NULL) {
383 if (is_header_metadata)
384 info->has_index_in_header_metadata = true;
386 const lzma_ret ret = lzma_info_index_set(
387 info, allocator, metadata->index, eat_index);
390 metadata->index = NULL;
395 } else if (!is_header_metadata
396 && (metadata->total_size == LZMA_VLI_VALUE_UNKNOWN
397 || !info->has_index_in_header_metadata)) {
398 // Either Total Size or Index must be present in Footer
399 // Metadata Block. If Index is not present, it must have
400 // already been in the Header Metadata Block. Since we
401 // got here, these conditions weren't met.
402 return LZMA_DATA_ERROR;
405 // Size of Header Metadata
406 if (!is_header_metadata)
407 return_if_error(lzma_info_size_set(
408 info, LZMA_INFO_HEADER_METADATA,
409 metadata->header_metadata_size));
412 if (metadata->total_size != LZMA_VLI_VALUE_UNKNOWN)
413 return_if_error(lzma_info_size_set(info,
414 LZMA_INFO_TOTAL, metadata->total_size));
417 if (metadata->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN)
418 return_if_error(lzma_info_size_set(info,
419 LZMA_INFO_UNCOMPRESSED,
420 metadata->uncompressed_size));
430 extern LZMA_API lzma_vli
431 lzma_info_size_get(const lzma_info *info, lzma_info_size type)
434 case LZMA_INFO_STREAM_START:
435 return info->stream_start_offset;
437 case LZMA_INFO_HEADER_METADATA:
438 return info->known.header_metadata_size;
440 case LZMA_INFO_TOTAL:
441 return info->known.total_size;
443 case LZMA_INFO_UNCOMPRESSED:
444 return info->known.uncompressed_size;
446 case LZMA_INFO_FOOTER_METADATA:
447 return info->known.footer_metadata_size;
450 return LZMA_VLI_VALUE_UNKNOWN;
454 extern LZMA_API lzma_index *
455 lzma_info_index_get(lzma_info *info, lzma_bool detach)
457 lzma_index *i = info->index.head;
466 extern LZMA_API size_t
467 lzma_info_index_count_get(const lzma_info *info)
469 return info->index.record_count;
485 #define iter_info ((lzma_info *)(iter->internal[ITER_INFO]))
487 #define iter_index ((lzma_index *)(iter->internal[ITER_INDEX]))
491 lzma_info_iter_begin(lzma_info *info, lzma_info_iter *iter)
493 *iter = (lzma_info_iter){
494 .total_size = LZMA_VLI_VALUE_UNKNOWN,
495 .uncompressed_size = LZMA_VLI_VALUE_UNKNOWN,
496 .stream_offset = LZMA_VLI_VALUE_UNKNOWN,
497 .uncompressed_offset = LZMA_VLI_VALUE_UNKNOWN,
498 .internal = { info, NULL, NULL, NULL },
505 extern LZMA_API lzma_ret
506 lzma_info_iter_next(lzma_info_iter *iter, lzma_allocator *allocator)
508 // FIXME debug remove
509 lzma_info *info = iter_info;
512 if (iter_index == NULL) {
513 // The first call after lzma_info_iter_begin().
514 if (iter_info->known.header_metadata_size
515 == LZMA_VLI_VALUE_UNKNOWN)
516 iter->stream_offset = LZMA_VLI_VALUE_UNKNOWN;
517 else if (lzma_vli_sum3(iter->stream_offset,
518 iter_info->stream_start_offset,
519 LZMA_STREAM_HEADER_SIZE,
520 iter_info->known.header_metadata_size))
521 return LZMA_PROG_ERROR;
523 iter->uncompressed_offset = 0;
525 if (iter_info->index.head != NULL) {
526 // The first Index Record has already been allocated.
527 iter->internal[ITER_INDEX] = iter_info->index.head;
528 iter->total_size = iter_index->total_size;
529 iter->uncompressed_size
530 = iter_index->uncompressed_size;
534 // Update iter->*_offsets.
535 if (iter->stream_offset != LZMA_VLI_VALUE_UNKNOWN) {
536 if (iter_index->total_size == LZMA_VLI_VALUE_UNKNOWN)
537 iter->stream_offset = LZMA_VLI_VALUE_UNKNOWN;
538 else if (lzma_vli_add(iter->stream_offset,
539 iter_index->total_size))
540 return LZMA_DATA_ERROR;
543 if (iter->uncompressed_offset != LZMA_VLI_VALUE_UNKNOWN) {
544 if (iter_index->uncompressed_size
545 == LZMA_VLI_VALUE_UNKNOWN)
546 iter->uncompressed_offset
547 = LZMA_VLI_VALUE_UNKNOWN;
548 else if (lzma_vli_add(iter->uncompressed_offset,
549 iter_index->uncompressed_size))
550 return LZMA_DATA_ERROR;
553 if (iter_index->next != NULL) {
554 // The next Record has already been allocated.
555 iter->internal[ITER_INDEX] = iter_index->next;
556 iter->total_size = iter_index->total_size;
557 iter->uncompressed_size
558 = iter_index->uncompressed_size;
563 // Don't add new Records to a final Index.
564 if (iter_info->index.is_final)
565 return LZMA_DATA_ERROR;
567 // Allocate and initialize a new Index Record.
568 lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);
570 return LZMA_MEM_ERROR;
572 i->total_size = LZMA_VLI_VALUE_UNKNOWN;
573 i->uncompressed_size = LZMA_VLI_VALUE_UNKNOWN;
576 iter->total_size = LZMA_VLI_VALUE_UNKNOWN;
577 iter->uncompressed_size = LZMA_VLI_VALUE_UNKNOWN;
579 // Decide where to put the new Index Record.
580 if (iter_info->index.head == NULL)
581 iter_info->index.head = i;
583 if (iter_index != NULL)
584 iter_index->next = i;
586 iter->internal[ITER_INDEX] = i;
588 ++iter_info->index.record_count;
589 ++iter_info->index.incomplete_count;
595 extern LZMA_API lzma_ret
596 lzma_info_iter_set(lzma_info_iter *iter,
597 lzma_vli total_size, lzma_vli uncompressed_size)
599 // FIXME debug remove
600 lzma_info *info = iter_info;
603 if (iter_index == NULL || !lzma_vli_is_valid(total_size)
604 || !lzma_vli_is_valid(uncompressed_size))
605 return LZMA_PROG_ERROR;
607 const bool was_incomplete = iter_index->total_size
608 == LZMA_VLI_VALUE_UNKNOWN
609 || iter_index->uncompressed_size
610 == LZMA_VLI_VALUE_UNKNOWN;
612 if (total_size != LZMA_VLI_VALUE_UNKNOWN) {
613 if (iter_index->total_size == LZMA_VLI_VALUE_UNKNOWN) {
614 iter_index->total_size = total_size;
616 if (lzma_vli_add(iter_info->index.total_size,
618 || iter_info->index.total_size
619 > iter_info->known.total_size)
620 return LZMA_DATA_ERROR;
622 } else if (iter_index->total_size != total_size) {
623 return LZMA_DATA_ERROR;
627 if (uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
628 if (iter_index->uncompressed_size == LZMA_VLI_VALUE_UNKNOWN) {
629 iter_index->uncompressed_size = uncompressed_size;
631 if (lzma_vli_add(iter_info->index.uncompressed_size,
633 || iter_info->index.uncompressed_size
634 > iter_info->known.uncompressed_size)
635 return LZMA_DATA_ERROR;
637 } else if (iter_index->uncompressed_size
638 != uncompressed_size) {
639 return LZMA_DATA_ERROR;
643 // Check if the new information we got managed to finish this
644 // Index Record. If so, update the count of incomplete Index Records.
645 if (was_incomplete && iter_index->total_size
646 != LZMA_VLI_VALUE_UNKNOWN
647 && iter_index->uncompressed_size
648 != LZMA_VLI_VALUE_UNKNOWN) {
649 assert(iter_info->index.incomplete_count > 0);
650 --iter_info->index.incomplete_count;
653 // Make sure that the known sizes are now available in *iter.
654 iter->total_size = iter_index->total_size;
655 iter->uncompressed_size = iter_index->uncompressed_size;
661 extern LZMA_API lzma_ret
662 lzma_info_index_finish(lzma_info *info)
664 if (info->index.record_count == 0 || info->index.incomplete_count > 0
665 || lzma_info_size_set(info, LZMA_INFO_TOTAL,
666 info->index.total_size)
667 || lzma_info_size_set(info, LZMA_INFO_UNCOMPRESSED,
668 info->index.uncompressed_size))
669 return LZMA_DATA_ERROR;
671 info->index.is_final = true;
681 extern LZMA_API lzma_vli
682 lzma_info_metadata_locate(const lzma_info *info, lzma_bool is_header_metadata)
687 if (info->known.header_metadata_size == LZMA_VLI_VALUE_UNKNOWN) {
688 // We don't know if Header Metadata Block is present, thus
689 // we cannot locate it either.
691 // Well, you could say that just assume that it is present.
692 // I'm not sure if this is useful. But it can be useful to
693 // be able to use this function and get LZMA_VLI_VALUE_UNKNOWN
694 // to detect that Header Metadata Block wasn't present.
696 } else if (is_header_metadata) {
697 error = lzma_vli_sum(size, info->stream_start_offset,
698 LZMA_STREAM_HEADER_SIZE);
699 } else if (!info->index.is_final) {
700 // Since we don't know if we have all the Index Records yet,
701 // we cannot know where the Footer Metadata Block is.
704 error = lzma_vli_sum4(size, info->stream_start_offset,
705 LZMA_STREAM_HEADER_SIZE,
706 info->known.header_metadata_size,
707 info->known.total_size);
710 return error ? LZMA_VLI_VALUE_UNKNOWN : size;
714 extern LZMA_API uint32_t
715 lzma_info_metadata_alignment_get(
716 const lzma_info *info, lzma_bool is_header_metadata)
720 if (is_header_metadata) {
721 alignment = info->stream_start_offset
722 + LZMA_STREAM_HEADER_SIZE;
724 alignment = info->stream_start_offset + LZMA_STREAM_HEADER_SIZE
725 + info->known.header_metadata_size
726 + info->known.total_size;
733 extern LZMA_API lzma_ret
734 lzma_info_iter_locate(lzma_info_iter *iter, lzma_allocator *allocator,
735 lzma_vli uncompressed_offset, lzma_bool allow_alloc)
737 if (iter == NULL || uncompressed_offset > LZMA_VLI_VALUE_MAX)
738 return LZMA_PROG_ERROR;
740 // Quick check in case Index is final.
741 if (iter_info->index.is_final) {
742 assert(iter_info->known.uncompressed_size
743 == iter_info->index.uncompressed_size);
744 if (uncompressed_offset >= iter_info->index.uncompressed_size)
745 return LZMA_DATA_ERROR;
748 // TODO: Optimize so that it uses existing info from *iter when
752 if (iter_info->known.header_metadata_size != LZMA_VLI_VALUE_UNKNOWN) {
753 if (lzma_vli_sum3(iter->stream_offset,
754 iter_info->stream_start_offset,
755 LZMA_STREAM_HEADER_SIZE,
756 iter_info->known.header_metadata_size))
757 return LZMA_PROG_ERROR;
759 // We don't know the Size of Header Metadata Block, thus
760 // we cannot calculate the Stream offset either.
761 iter->stream_offset = LZMA_VLI_VALUE_UNKNOWN;
764 iter->uncompressed_offset = 0;
766 // If we have no Index Records, it's obvious that we need to
768 if (iter_info->index.head == NULL) {
769 assert(!iter_info->index.is_final);
771 return LZMA_DATA_ERROR;
773 return lzma_info_iter_next(iter, allocator);
776 // Locate an appropriate Index Record.
777 lzma_index *i = iter_info->index.head;
779 // - If Uncompressed Size in the Record is unknown,
780 // we have no chance to search further.
781 // - If the next Record would go past the requested offset,
782 // we have found our target Data Block.
783 if (i->uncompressed_size == LZMA_VLI_VALUE_UNKNOWN
784 || iter->uncompressed_offset
785 + i->uncompressed_size > uncompressed_offset) {
786 iter->total_size = i->total_size;
787 iter->uncompressed_size = i->uncompressed_size;
788 iter->internal[ITER_INDEX] = i;
792 // Update the stream offset. It may be unknown if we didn't
793 // know the size of Header Metadata Block.
794 if (iter->stream_offset != LZMA_VLI_VALUE_UNKNOWN)
795 if (lzma_vli_add(iter->stream_offset, i->total_size))
796 return LZMA_PROG_ERROR;
798 // Update the uncompressed offset. This cannot overflow since
799 // the Index is known to be valid.
800 iter->uncompressed_offset += i->uncompressed_size;
802 // Move to the next Block.
803 if (i->next == NULL) {
804 assert(!iter_info->index.is_final);
806 return LZMA_DATA_ERROR;
808 iter->internal[ITER_INDEX] = i;
809 return lzma_info_iter_next(iter, allocator);