diff options
Diffstat (limited to 'src/liblzma/common/info.c')
| -rw-r--r-- | src/liblzma/common/info.c | 823 |
1 files changed, 823 insertions, 0 deletions
diff --git a/src/liblzma/common/info.c b/src/liblzma/common/info.c new file mode 100644 index 00000000..2a59a029 --- /dev/null +++ b/src/liblzma/common/info.c @@ -0,0 +1,823 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file info.c +/// \brief Collects and verifies integrity of Stream size information +// +// Copyright (C) 2007 Lasse Collin +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// Lesser General Public License for more details. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "common.h" + + +struct lzma_info_s { + struct { + /// Known Size of Header Metadata Block; here's some + /// special things: + /// - LZMA_VLI_VALUE_UNKNOWN indicates that we don't know + /// if Header Metadata Block is present. + /// - 0 indicates that Header Metadata Block is not present. + lzma_vli header_metadata_size; + + /// Known Total Size of the Data Blocks in the Stream + lzma_vli total_size; + + /// Known Uncompressed Size of the Data Blocks in the Stream + lzma_vli uncompressed_size; + + /// Known Size of Footer Metadata Block + lzma_vli footer_metadata_size; + } known; + + struct { + /// Sum of Total Size fields stored to the Index so far + lzma_vli total_size; + + /// Sum of Uncompressed Size fields stored to the Index so far + lzma_vli uncompressed_size; + + /// First Index Record in the list, or NULL if Index is empty. + lzma_index *head; + + /// Number of Index Records + size_t record_count; + + /// Number of Index Records + size_t incomplete_count; + + /// True when we know that no more Records will get added + /// to the Index. + bool is_final; + } index; + + /// Start offset of the Stream. This is needed to calculate + /// lzma_info_iter.stream_offset. + lzma_vli stream_start_offset; + + /// True if Index is present in Header Metadata Block + bool has_index_in_header_metadata; +}; + + +////////////////////// +// Create/Reset/End // +////////////////////// + +static void +index_init(lzma_info *info) +{ + info->index.total_size = 0; + info->index.uncompressed_size = 0; + info->index.head = NULL; + info->index.record_count = 0; + info->index.incomplete_count = 0; + info->index.is_final = false; + return; +} + + +static void +info_init(lzma_info *info) +{ + info->known.header_metadata_size = LZMA_VLI_VALUE_UNKNOWN; + info->known.total_size = LZMA_VLI_VALUE_UNKNOWN; + info->known.uncompressed_size = LZMA_VLI_VALUE_UNKNOWN; + info->known.footer_metadata_size = LZMA_VLI_VALUE_UNKNOWN; + info->stream_start_offset = 0; + info->has_index_in_header_metadata = false; + + index_init(info); + + return; +} + + +extern LZMA_API lzma_info * +lzma_info_init(lzma_info *info, lzma_allocator *allocator) +{ + if (info == NULL) + info = lzma_alloc(sizeof(lzma_info), allocator); + else + lzma_index_free(info->index.head, allocator); + + if (info != NULL) + info_init(info); + + return info; +} + + +extern LZMA_API void +lzma_info_free(lzma_info *info, lzma_allocator *allocator) +{ + lzma_index_free(info->index.head, allocator); + lzma_free(info, allocator); + return; +} + + +///////// +// Set // +///////// + +static lzma_ret +set_size(lzma_vli new_size, lzma_vli *known_size, lzma_vli index_size, + bool forbid_zero) +{ + assert(new_size <= LZMA_VLI_VALUE_MAX); + + lzma_ret ret = LZMA_OK; + + if (forbid_zero && new_size == 0) + ret = LZMA_PROG_ERROR; + else if (index_size > new_size) + ret = LZMA_DATA_ERROR; + else if (*known_size == LZMA_VLI_VALUE_UNKNOWN) + *known_size = new_size; + else if (*known_size != new_size) + ret = LZMA_DATA_ERROR; + + return ret; +} + + +extern LZMA_API lzma_ret +lzma_info_size_set(lzma_info *info, lzma_info_size type, lzma_vli size) +{ + if (size > LZMA_VLI_VALUE_MAX) + return LZMA_PROG_ERROR; + + switch (type) { + case LZMA_INFO_STREAM_START: + info->stream_start_offset = size; + return LZMA_OK; + + case LZMA_INFO_HEADER_METADATA: + return set_size(size, &info->known.header_metadata_size, + 0, false); + + case LZMA_INFO_TOTAL: + return set_size(size, &info->known.total_size, + info->index.total_size, true); + + case LZMA_INFO_UNCOMPRESSED: + return set_size(size, &info->known.uncompressed_size, + info->index.uncompressed_size, false); + + case LZMA_INFO_FOOTER_METADATA: + return set_size(size, &info->known.footer_metadata_size, + 0, true); + } + + return LZMA_PROG_ERROR; +} + + +extern LZMA_API lzma_ret +lzma_info_index_set(lzma_info *info, lzma_allocator *allocator, + lzma_index *i_new, lzma_bool eat_index) +{ + if (i_new == NULL) + return LZMA_PROG_ERROR; + + lzma_index *i_old = info->index.head; + + if (i_old != NULL) { + while (true) { + // If the new Index has fewer Records than the old one, + // the new Index cannot be valid. + if (i_new == NULL) + return LZMA_DATA_ERROR; + + // The new Index must be complete i.e. no unknown + // values. + if (i_new->total_size > LZMA_VLI_VALUE_MAX + || i_new->uncompressed_size + > LZMA_VLI_VALUE_MAX) { + if (eat_index) + lzma_index_free(i_new, allocator); + + return LZMA_PROG_ERROR; + } + + // Compare the values from the new Index with the old + // Index. The old Index may be incomplete; in that + // case we + // - use the value from the new Index as is; + // - update the appropriate info->index.foo_size; and + // - decrease the count of incomplete Index Records. + bool was_incomplete = false; + + if (i_old->total_size == LZMA_VLI_VALUE_UNKNOWN) { + assert(!info->index.is_final); + was_incomplete = true; + + i_old->total_size = i_new->total_size; + + if (lzma_vli_add(info->index.total_size, + i_new->total_size)) { + if (eat_index) + lzma_index_free(i_new, + allocator); + + return LZMA_PROG_ERROR; + } + } else if (i_old->total_size != i_new->total_size) { + if (eat_index) + lzma_index_free(i_new, allocator); + + return LZMA_DATA_ERROR; + } + + if (i_old->uncompressed_size + == LZMA_VLI_VALUE_UNKNOWN) { + assert(!info->index.is_final); + was_incomplete = true; + + i_old->uncompressed_size + = i_new->uncompressed_size; + + if (lzma_vli_add(info->index.uncompressed_size, + i_new->uncompressed_size)) { + if (eat_index) + lzma_index_free(i_new, + allocator); + + return LZMA_PROG_ERROR; + } + } else if (i_old->uncompressed_size + != i_new->uncompressed_size) { + if (eat_index) + lzma_index_free(i_new, allocator); + + return LZMA_DATA_ERROR; + } + + if (was_incomplete) { + assert(!info->index.is_final); + assert(info->index.incomplete_count > 0); + --info->index.incomplete_count; + } + + // Get rid of *i_new. It's now identical with *i_old. + lzma_index *tmp = i_new->next; + if (eat_index) + lzma_free(i_new, allocator); + + i_new = tmp; + + // We want to leave i_old pointing to the last + // Index Record in the old Index. This way we can + // concatenate the possible new Records from i_new. + if (i_old->next == NULL) + break; + + i_old = i_old->next; + } + } + + assert(info->index.incomplete_count == 0); + + // If Index was already known to be final, i_new must be NULL now. + // The new Index cannot contain more Records that we already have. + if (info->index.is_final) { + assert(info->index.head != NULL); + + if (i_new != NULL) { + if (eat_index) + lzma_index_free(i_new, allocator); + + return LZMA_DATA_ERROR; + } + + return LZMA_OK; + } + + // The rest of the new Index is merged to the old Index. Keep the + // current i_new pointer in available. We need it when merging the + // new Index with the old one, and if an error occurs so we can + // get rid of the broken part of the new Index. + lzma_index *i_start = i_new; + while (i_new != NULL) { + // The new Index must be complete i.e. no unknown values. + if (i_new->total_size > LZMA_VLI_VALUE_MAX + || i_new->uncompressed_size + > LZMA_VLI_VALUE_MAX) { + if (eat_index) + lzma_index_free(i_start, allocator); + + return LZMA_PROG_ERROR; + } + + // Update info->index.foo_sizes. + if (lzma_vli_add(info->index.total_size, i_new->total_size) + || lzma_vli_add(info->index.uncompressed_size, + i_new->uncompressed_size)) { + if (eat_index) + lzma_index_free(i_start, allocator); + + return LZMA_PROG_ERROR; + } + + ++info->index.record_count; + i_new = i_new->next; + } + + // All the Records in the new Index are good, and info->index.foo_sizes + // were successfully updated. + if (lzma_info_index_finish(info) != LZMA_OK) { + if (eat_index) + lzma_index_free(i_start, allocator); + + return LZMA_DATA_ERROR; + } + + // The Index is ready to be merged. If we aren't supposed to eat + // the Index, make a copy of it first. + if (!eat_index && i_start != NULL) { + i_start = lzma_index_dup(i_start, allocator); + if (i_start == NULL) + return LZMA_MEM_ERROR; + } + + // Concatenate the new Index with the old one. Note that it is + // possible that we don't have any old Index. + if (info->index.head == NULL) + info->index.head = i_start; + else + i_old->next = i_start; + + return LZMA_OK; +} + + +extern LZMA_API lzma_ret +lzma_info_metadata_set(lzma_info *info, lzma_allocator *allocator, + lzma_metadata *metadata, lzma_bool is_header_metadata, + lzma_bool eat_index) +{ + // Validate *metadata. + if (!lzma_vli_is_valid(metadata->header_metadata_size) + || !lzma_vli_is_valid(metadata->total_size) + || !lzma_vli_is_valid(metadata->uncompressed_size)) { + if (eat_index) { + lzma_index_free(metadata->index, allocator); + metadata->index = NULL; + } + + return LZMA_PROG_ERROR; + } + + // Index + if (metadata->index != NULL) { + if (is_header_metadata) + info->has_index_in_header_metadata = true; + + const lzma_ret ret = lzma_info_index_set( + info, allocator, metadata->index, eat_index); + if (ret != LZMA_OK) + return ret; + + } else if (!is_header_metadata + && (metadata->total_size == LZMA_VLI_VALUE_UNKNOWN + || !info->has_index_in_header_metadata)) { + // Either Total Size or Index must be present in Footer + // Metadata Block. If Index is not present, it must have + // already been in the Header Metadata Block. Since we + // got here, these conditions weren't met. + return LZMA_DATA_ERROR; + } + + // Size of Header Metadata + if (!is_header_metadata) { + // If it is marked unknown in Metadata, it means that + // it's not present. + const lzma_vli size = metadata->header_metadata_size + != LZMA_VLI_VALUE_UNKNOWN + ? metadata->header_metadata_size : 0; + const lzma_ret ret = lzma_info_size_set( + info, LZMA_INFO_HEADER_METADATA, size); + if (ret != LZMA_OK) + return ret; + } + + // Total Size + if (metadata->total_size != LZMA_VLI_VALUE_UNKNOWN) { + const lzma_ret ret = lzma_info_size_set(info, + LZMA_INFO_TOTAL, metadata->total_size); + if (ret != LZMA_OK) + return ret; + } + + // Uncompressed Size + if (metadata->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) { + const lzma_ret ret = lzma_info_size_set(info, + LZMA_INFO_UNCOMPRESSED, + metadata->uncompressed_size); + if (ret != LZMA_OK) + return ret; + } + + return LZMA_OK; +} + + +///////// +// Get // +///////// + +extern LZMA_API lzma_vli +lzma_info_size_get(const lzma_info *info, lzma_info_size type) +{ + switch (type) { + case LZMA_INFO_STREAM_START: + return info->stream_start_offset; + + case LZMA_INFO_HEADER_METADATA: + return info->known.header_metadata_size; + + case LZMA_INFO_TOTAL: + return info->known.total_size; + + case LZMA_INFO_UNCOMPRESSED: + return info->known.uncompressed_size; + + case LZMA_INFO_FOOTER_METADATA: + return info->known.footer_metadata_size; + } + + return LZMA_VLI_VALUE_UNKNOWN; +} + + +extern LZMA_API lzma_index * +lzma_info_index_get(lzma_info *info, lzma_bool detach) +{ + lzma_index *i = info->index.head; + + if (detach) + index_init(info); + + return i; +} + + +extern LZMA_API size_t +lzma_info_index_count_get(const lzma_info *info) +{ + return info->index.record_count; +} + + +///////////////// +// Incremental // +///////////////// + +enum { + ITER_INFO, + ITER_INDEX, + ITER_RESERVED_1, + ITER_RESERVED_2, +}; + + +#define iter_info ((lzma_info *)(iter->internal[ITER_INFO])) + +#define iter_index ((lzma_index *)(iter->internal[ITER_INDEX])) + + +extern LZMA_API void +lzma_info_iter_begin(lzma_info *info, lzma_info_iter *iter) +{ + *iter = (lzma_info_iter){ + .total_size = LZMA_VLI_VALUE_UNKNOWN, + .uncompressed_size = LZMA_VLI_VALUE_UNKNOWN, + .stream_offset = LZMA_VLI_VALUE_UNKNOWN, + .uncompressed_offset = LZMA_VLI_VALUE_UNKNOWN, + .internal = { info, NULL, NULL, NULL }, + }; + + return; +} + + +extern LZMA_API lzma_ret +lzma_info_iter_next(lzma_info_iter *iter, lzma_allocator *allocator) +{ + // FIXME debug remove + lzma_info *info = iter_info; + (void)info; + + if (iter_index == NULL) { + // The first call after lzma_info_iter_begin(). + if (iter_info->known.header_metadata_size + == LZMA_VLI_VALUE_UNKNOWN) + iter->stream_offset = LZMA_VLI_VALUE_UNKNOWN; + else if (lzma_vli_sum3(iter->stream_offset, + iter_info->stream_start_offset, + LZMA_STREAM_HEADER_SIZE, + iter_info->known.header_metadata_size)) + return LZMA_PROG_ERROR; + + iter->uncompressed_offset = 0; + + if (iter_info->index.head != NULL) { + // The first Index Record has already been allocated. + iter->internal[ITER_INDEX] = iter_info->index.head; + iter->total_size = iter_index->total_size; + iter->uncompressed_size + = iter_index->uncompressed_size; + return LZMA_OK; + } + } else { + // Update iter->*_offsets. + if (iter->stream_offset != LZMA_VLI_VALUE_UNKNOWN) { + if (iter_index->total_size == LZMA_VLI_VALUE_UNKNOWN) + iter->stream_offset = LZMA_VLI_VALUE_UNKNOWN; + else if (lzma_vli_add(iter->stream_offset, + iter_index->total_size)) + return LZMA_DATA_ERROR; + } + + if (iter->uncompressed_offset != LZMA_VLI_VALUE_UNKNOWN) { + if (iter_index->uncompressed_size + == LZMA_VLI_VALUE_UNKNOWN) + iter->uncompressed_offset + = LZMA_VLI_VALUE_UNKNOWN; + else if (lzma_vli_add(iter->uncompressed_offset, + iter_index->uncompressed_size)) + return LZMA_DATA_ERROR; + } + + if (iter_index->next != NULL) { + // The next Record has already been allocated. + iter->internal[ITER_INDEX] = iter_index->next; + iter->total_size = iter_index->total_size; + iter->uncompressed_size + = iter_index->uncompressed_size; + return LZMA_OK; + } + } + + // Don't add new Records to a final Index. + if (iter_info->index.is_final) + return LZMA_DATA_ERROR; + + // Allocate and initialize a new Index Record. + lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator); + if (i == NULL) + return LZMA_MEM_ERROR; + + i->total_size = LZMA_VLI_VALUE_UNKNOWN; + i->uncompressed_size = LZMA_VLI_VALUE_UNKNOWN; + i->next = NULL; + + iter->total_size = LZMA_VLI_VALUE_UNKNOWN; + iter->uncompressed_size = LZMA_VLI_VALUE_UNKNOWN; + + // Decide where to put the new Index Record. + if (iter_info->index.head == NULL) + iter_info->index.head = i; + + if (iter_index != NULL) + iter_index->next = i; + + iter->internal[ITER_INDEX] = i; + + ++iter_info->index.record_count; + ++iter_info->index.incomplete_count; + + return LZMA_OK; +} + + +extern LZMA_API lzma_ret +lzma_info_iter_set(lzma_info_iter *iter, + lzma_vli total_size, lzma_vli uncompressed_size) +{ + // FIXME debug remove + lzma_info *info = iter_info; + (void)info; + + if (iter_index == NULL || !lzma_vli_is_valid(total_size) + || !lzma_vli_is_valid(uncompressed_size)) + return LZMA_PROG_ERROR; + + const bool was_incomplete = iter_index->total_size + == LZMA_VLI_VALUE_UNKNOWN + || iter_index->uncompressed_size + == LZMA_VLI_VALUE_UNKNOWN; + + if (total_size != LZMA_VLI_VALUE_UNKNOWN) { + if (iter_index->total_size == LZMA_VLI_VALUE_UNKNOWN) { + iter_index->total_size = total_size; + + if (lzma_vli_add(iter_info->index.total_size, + total_size) + || iter_info->index.total_size + > iter_info->known.total_size) + return LZMA_DATA_ERROR; + + } else if (iter_index->total_size != total_size) { + return LZMA_DATA_ERROR; + } + } + + if (uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) { + if (iter_index->uncompressed_size == LZMA_VLI_VALUE_UNKNOWN) { + iter_index->uncompressed_size = uncompressed_size; + + if (lzma_vli_add(iter_info->index.uncompressed_size, + uncompressed_size) + || iter_info->index.uncompressed_size + > iter_info->known.uncompressed_size) + return LZMA_DATA_ERROR; + + } else if (iter_index->uncompressed_size + != uncompressed_size) { + return LZMA_DATA_ERROR; + } + } + + // Check if the new information we got managed to finish this + // Index Record. If so, update the count of incomplete Index Records. + if (was_incomplete && iter_index->total_size + != LZMA_VLI_VALUE_UNKNOWN + && iter_index->uncompressed_size + != LZMA_VLI_VALUE_UNKNOWN) { + assert(iter_info->index.incomplete_count > 0); + --iter_info->index.incomplete_count; + } + + // Make sure that the known sizes are now available in *iter. + iter->total_size = iter_index->total_size; + iter->uncompressed_size = iter_index->uncompressed_size; + + return LZMA_OK; +} + + +extern LZMA_API lzma_ret +lzma_info_index_finish(lzma_info *info) +{ + if (info->index.record_count == 0 || info->index.incomplete_count > 0 + || lzma_info_size_set(info, LZMA_INFO_TOTAL, + info->index.total_size) + || lzma_info_size_set(info, LZMA_INFO_UNCOMPRESSED, + info->index.uncompressed_size)) + return LZMA_DATA_ERROR; + + info->index.is_final = true; + + return LZMA_OK; +} + + +////////////// +// Locating // +////////////// + +extern LZMA_API lzma_vli +lzma_info_metadata_locate(const lzma_info *info, lzma_bool is_header_metadata) +{ + bool error = false; + lzma_vli size = 0; + + if (info->known.header_metadata_size == LZMA_VLI_VALUE_UNKNOWN) { + // We don't know if Header Metadata Block is present, thus + // we cannot locate it either. + // + // Well, you could say that just assume that it is present. + // I'm not sure if this is useful. But it can be useful to + // be able to use this function and get LZMA_VLI_VALUE_UNKNOWN + // to detect that Header Metadata Block wasn't present. + error = true; + } else if (is_header_metadata) { + error = lzma_vli_sum(size, info->stream_start_offset, + LZMA_STREAM_HEADER_SIZE); + } else if (!info->index.is_final) { + // Since we don't know if we have all the Index Records yet, + // we cannot know where the Footer Metadata Block is. + error = true; + } else { + error = lzma_vli_sum4(size, info->stream_start_offset, + LZMA_STREAM_HEADER_SIZE, + info->known.header_metadata_size, + info->known.total_size); + } + + return error ? LZMA_VLI_VALUE_UNKNOWN : size; +} + + +extern LZMA_API uint32_t +lzma_info_metadata_alignment_get( + const lzma_info *info, lzma_bool is_header_metadata) +{ + uint32_t alignment; + + if (is_header_metadata) { + alignment = info->stream_start_offset + + LZMA_STREAM_HEADER_SIZE; + } else { + alignment = info->stream_start_offset + LZMA_STREAM_HEADER_SIZE + + info->known.header_metadata_size + + info->known.total_size; + } + + return alignment; +} + + +extern LZMA_API lzma_ret +lzma_info_iter_locate(lzma_info_iter *iter, lzma_allocator *allocator, + lzma_vli uncompressed_offset, lzma_bool allow_alloc) +{ + if (iter == NULL || uncompressed_offset > LZMA_VLI_VALUE_MAX) + return LZMA_PROG_ERROR; + + // Quick check in case Index is final. + if (iter_info->index.is_final) { + assert(iter_info->known.uncompressed_size + == iter_info->index.uncompressed_size); + if (uncompressed_offset >= iter_info->index.uncompressed_size) + return LZMA_DATA_ERROR; + } + + // TODO: Optimize so that it uses existing info from *iter when + // seeking forward. + + // Initialize *iter + if (iter_info->known.header_metadata_size != LZMA_VLI_VALUE_UNKNOWN) { + if (lzma_vli_sum3(iter->stream_offset, + iter_info->stream_start_offset, + LZMA_STREAM_HEADER_SIZE, + iter_info->known.header_metadata_size)) + return LZMA_PROG_ERROR; + } else { + // We don't know the Size of Header Metadata Block, thus + // we cannot calculate the Stream offset either. + iter->stream_offset = LZMA_VLI_VALUE_UNKNOWN; + } + + iter->uncompressed_offset = 0; + + // If we have no Index Records, it's obvious that we need to + // add a new one. + if (iter_info->index.head == NULL) { + assert(!iter_info->index.is_final); + if (!allow_alloc) + return LZMA_DATA_ERROR; + + return lzma_info_iter_next(iter, allocator); + } + + // Locate an appropriate Index Record. + lzma_index *i = iter_info->index.head; + while (true) { + // - If Uncompressed Size in the Record is unknown, + // we have no chance to search further. + // - If the next Record would go past the requested offset, + // we have found our target Data Block. + if (i->uncompressed_size == LZMA_VLI_VALUE_UNKNOWN + || iter->uncompressed_offset + + i->uncompressed_size > uncompressed_offset) { + iter->total_size = i->total_size; + iter->uncompressed_size = i->uncompressed_size; + iter->internal[ITER_INDEX] = i; + return LZMA_OK; + } + + // Update the stream offset. It may be unknown if we didn't + // know the size of Header Metadata Block. + if (iter->stream_offset != LZMA_VLI_VALUE_UNKNOWN) + if (lzma_vli_add(iter->stream_offset, i->total_size)) + return LZMA_PROG_ERROR; + + // Update the uncompressed offset. This cannot overflow since + // the Index is known to be valid. + iter->uncompressed_offset += i->uncompressed_size; + + // Move to the next Block. + if (i->next == NULL) { + assert(!iter_info->index.is_final); + if (!allow_alloc) + return LZMA_DATA_ERROR; + + iter->internal[ITER_INDEX] = i; + return lzma_info_iter_next(iter, allocator); + } + + i = i->next; + } +} |