Add an unpatched version of xz, XZ Utils, to /trunk/deps/third_party

xz/src/liblzma/common/index.c

+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       index.c
+/// \brief      Handling of .xz Indexes and some other Stream information
+//
+//  Author:     Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "index.h"
+#include "stream_flags_common.h"
+
+
+/// \brief      How many Records to allocate at once
+///
+/// This should be big enough to avoid making lots of tiny allocations
+/// but small enough to avoid too much unused memory at once.
+#define INDEX_GROUP_SIZE 500
+
+
+/// \brief      How many Records can be allocated at once at maximum
+#define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))
+
+
+/// \brief      Base structure for index_stream and index_group structures
+typedef struct index_tree_node_s index_tree_node;
+struct index_tree_node_s {
+        /// Uncompressed start offset of this Stream (relative to the
+        /// beginning of the file) or Block (relative to the beginning
+        /// of the Stream)
+        lzma_vli uncompressed_base;
+
+        /// Compressed start offset of this Stream or Block
+        lzma_vli compressed_base;
+
+        index_tree_node *parent;
+        index_tree_node *left;
+        index_tree_node *right;
+};
+
+
+/// \brief      AVL tree to hold index_stream or index_group structures
+typedef struct {
+        /// Root node
+        index_tree_node *root;
+
+        /// Leftmost node. Since the tree will be filled sequentially,
+        /// this won't change after the first node has been added to
+        /// the tree.
+        index_tree_node *leftmost;
+
+        /// The rightmost node in the tree. Since the tree is filled
+        /// sequentially, this is always the node where to add the new data.
+        index_tree_node *rightmost;
+
+        /// Number of nodes in the tree
+        uint32_t count;
+
+} index_tree;
+
+
+typedef struct {
+        lzma_vli uncompressed_sum;
+        lzma_vli unpadded_sum;
+} index_record;
+
+
+typedef struct {
+        /// Every Record group is part of index_stream.groups tree.
+        index_tree_node node;
+
+        /// Number of Blocks in this Stream before this group.
+        lzma_vli number_base;
+
+        /// Number of Records that can be put in records[].
+        size_t allocated;
+
+        /// Index of the last Record in use.
+        size_t last;
+
+        /// The sizes in this array are stored as cumulative sums relative
+        /// to the beginning of the Stream. This makes it possible to
+        /// use binary search in lzma_index_locate().
+        ///
+        /// Note that the cumulative summing is done specially for
+        /// unpadded_sum: The previous value is rounded up to the next
+        /// multiple of four before adding the Unpadded Size of the new
+        /// Block. The total encoded size of the Blocks in the Stream
+        /// is records[last].unpadded_sum in the last Record group of
+        /// the Stream.
+        ///
+        /// For example, if the Unpadded Sizes are 39, 57, and 81, the
+        /// stored values are 39, 97 (40 + 57), and 181 (100 + 181).
+        /// The total encoded size of these Blocks is 184.
+        ///
+        /// This is a flexible array, because it makes easy to optimize
+        /// memory usage in case someone concatenates many Streams that
+        /// have only one or few Blocks.
+        index_record records[];
+
+} index_group;
+
+
+typedef struct {
+        /// Every index_stream is a node in the tree of Sreams.
+        index_tree_node node;
+
+        /// Number of this Stream (first one is 1)
+        uint32_t number;
+
+        /// Total number of Blocks before this Stream
+        lzma_vli block_number_base;
+
+        /// Record groups of this Stream are stored in a tree.
+        /// It's a T-tree with AVL-tree balancing. There are
+        /// INDEX_GROUP_SIZE Records per node by default.
+        /// This keeps the number of memory allocations reasonable
+        /// and finding a Record is fast.
+        index_tree groups;
+
+        /// Number of Records in this Stream
+        lzma_vli record_count;
+
+        /// Size of the List of Records field in this Stream. This is used
+        /// together with record_count to calculate the size of the Index
+        /// field and thus the total size of the Stream.
+        lzma_vli index_list_size;
+
+        /// Stream Flags of this Stream. This is meaningful only if
+        /// the Stream Flags have been told us with lzma_index_stream_flags().
+        /// Initially stream_flags.version is set to UINT32_MAX to indicate
+        /// that the Stream Flags are unknown.
+        lzma_stream_flags stream_flags;
+
+        /// Amount of Stream Padding after this Stream. This defaults to
+        /// zero and can be set with lzma_index_stream_padding().
+        lzma_vli stream_padding;
+
+} index_stream;
+
+
+struct lzma_index_s {
+        /// AVL-tree containing the Stream(s). Often there is just one
+        /// Stream, but using a tree keeps lookups fast even when there
+        /// are many concatenated Streams.
+        index_tree streams;
+
+        /// Uncompressed size of all the Blocks in the Stream(s)
+        lzma_vli uncompressed_size;
+
+        /// Total size of all the Blocks in the Stream(s)
+        lzma_vli total_size;
+
+        /// Total number of Records in all Streams in this lzma_index
+        lzma_vli record_count;
+
+        /// Size of the List of Records field if all the Streams in this
+        /// lzma_index were packed into a single Stream (makes it simpler to
+        /// take many .xz files and combine them into a single Stream).
+        ///
+        /// This value together with record_count is needed to calculate
+        /// Backward Size that is stored into Stream Footer.
+        lzma_vli index_list_size;
+
+        /// How many Records to allocate at once in lzma_index_append().
+        /// This defaults to INDEX_GROUP_SIZE but can be overriden with
+        /// lzma_index_prealloc().
+        size_t prealloc;
+
+        /// Bitmask indicating what integrity check types have been used
+        /// as set by lzma_index_stream_flags(). The bit of the last Stream
+        /// is not included here, since it is possible to change it by
+        /// calling lzma_index_stream_flags() again.
+        uint32_t checks;
+};
+
+
+static void
+index_tree_init(index_tree *tree)
+{
+        tree->root = NULL;
+        tree->leftmost = NULL;
+        tree->rightmost = NULL;
+        tree->count = 0;
+        return;
+}
+
+
+/// Helper for index_tree_end()
+static void
+index_tree_node_end(index_tree_node *node, lzma_allocator *allocator,
+                void (*free_func)(void *node, lzma_allocator *allocator))
+{
+        // The tree won't ever be very huge, so recursion should be fine.
+        // 20 levels in the tree is likely quite a lot already in practice.
+        if (node->left != NULL)
+                index_tree_node_end(node->left, allocator, free_func);
+
+        if (node->right != NULL)
+                index_tree_node_end(node->right, allocator, free_func);
+
+        if (free_func != NULL)
+                free_func(node, allocator);
+
+        lzma_free(node, allocator);
+        return;
+}
+
+
+/// Free the meory allocated for a tree. If free_func is not NULL,
+/// it is called on each node before freeing the node. This is used
+/// to free the Record groups from each index_stream before freeing
+/// the index_stream itself.
+static void
+index_tree_end(index_tree *tree, lzma_allocator *allocator,
+                void (*free_func)(void *node, lzma_allocator *allocator))
+{
+        if (tree->root != NULL)
+                index_tree_node_end(tree->root, allocator, free_func);
+
+        return;
+}
+
+
+/// Add a new node to the tree. node->uncompressed_base and
+/// node->compressed_base must have been set by the caller already.
+static void
+index_tree_append(index_tree *tree, index_tree_node *node)
+{
+        node->parent = tree->rightmost;
+        node->left = NULL;
+        node->right = NULL;
+
+        ++tree->count;
+
+        // Handle the special case of adding the first node.
+        if (tree->root == NULL) {
+                tree->root = node;
+                tree->leftmost = node;
+                tree->rightmost = node;
+                return;
+        }
+
+        // The tree is always filled sequentially.
+        assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);
+        assert(tree->rightmost->compressed_base < node->compressed_base);
+
+        // Add the new node after the rightmost node. It's the correct
+        // place due to the reason above.
+        tree->rightmost->right = node;
+        tree->rightmost = node;
+
+        // Balance the AVL-tree if needed. We don't need to keep the balance
+        // factors in nodes, because we always fill the tree sequentially,
+        // and thus know the state of the tree just by looking at the node
+        // count. From the node count we can calculate how many steps to go
+        // up in the tree to find the rotation root.
+        uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count));
+        if (up != 0) {
+                // Locate the root node for the rotation.
+                up = ctz32(tree->count) + 2;
+                do {
+                        node = node->parent;
+                } while (--up > 0);
+
+                // Rotate left using node as the rotation root.
+                index_tree_node *pivot = node->right;
+
+                if (node->parent == NULL) {
+                        tree->root = pivot;
+                } else {
+                        assert(node->parent->right == node);
+                        node->parent->right = pivot;
+                }
+
+                pivot->parent = node->parent;
+
+                node->right = pivot->left;
+                if (node->right != NULL)
+                        node->right->parent = node;
+
+                pivot->left = node;
+                node->parent = pivot;
+        }
+
+        return;
+}
+
+
+/// Get the next node in the tree. Return NULL if there are no more nodes.
+static void *
+index_tree_next(const index_tree_node *node)
+{
+        if (node->right != NULL) {
+                node = node->right;
+                while (node->left != NULL)
+                        node = node->left;
+
+                return (void *)(node);
+        }
+
+        while (node->parent != NULL && node->parent->right == node)
+                node = node->parent;
+
+        return (void *)(node->parent);
+}
+
+
+/// Locate a node that contains the given uncompressed offset. It is
+/// caller's job to check that target is not bigger than the uncompressed
+/// size of the tree (the last node would be returned in that case still).
+static void *
+index_tree_locate(const index_tree *tree, lzma_vli target)
+{
+        const index_tree_node *result = NULL;
+        const index_tree_node *node = tree->root;
+
+        assert(tree->leftmost == NULL
+                        || tree->leftmost->uncompressed_base == 0);
+
+        // Consecutive nodes may have the same uncompressed_base.
+        // We must pick the rightmost one.
+        while (node != NULL) {
+                if (node->uncompressed_base > target) {
+                        node = node->left;
+                } else {
+                        result = node;
+                        node = node->right;
+                }
+        }
+
+        return (void *)(result);
+}
+
+
+/// Allocate and initialize a new Stream using the given base offsets.
+static index_stream *
+index_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base,
+                lzma_vli stream_number, lzma_vli block_number_base,
+                lzma_allocator *allocator)
+{
+        index_stream *s = lzma_alloc(sizeof(index_stream), allocator);
+        if (s == NULL)
+                return NULL;
+
+        s->node.uncompressed_base = uncompressed_base;
+        s->node.compressed_base = compressed_base;
+        s->node.parent = NULL;
+        s->node.left = NULL;
+        s->node.right = NULL;
+
+        s->number = stream_number;
+        s->block_number_base = block_number_base;
+
+        index_tree_init(&s->groups);
+
+        s->record_count = 0;
+        s->index_list_size = 0;
+        s->stream_flags.version = UINT32_MAX;
+        s->stream_padding = 0;
+
+        return s;
+}
+
+
+/// Free the memory allocated for a Stream and its Record groups.
+static void
+index_stream_end(void *node, lzma_allocator *allocator)
+{
+        index_stream *s = node;
+        index_tree_end(&s->groups, allocator, NULL);
+        return;
+}
+
+
+static lzma_index *
+index_init_plain(lzma_allocator *allocator)
+{
+        lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);
+        if (i != NULL) {
+                index_tree_init(&i->streams);
+                i->uncompressed_size = 0;
+                i->total_size = 0;
+                i->record_count = 0;
+                i->index_list_size = 0;
+                i->prealloc = INDEX_GROUP_SIZE;
+                i->checks = 0;
+        }
+
+        return i;
+}
+
+
+extern LZMA_API(lzma_index *)
+lzma_index_init(lzma_allocator *allocator)
+{
+        lzma_index *i = index_init_plain(allocator);
+        index_stream *s = index_stream_init(0, 0, 1, 0, allocator);
+        if (i == NULL || s == NULL) {
+                index_stream_end(s, allocator);
+                lzma_free(i, allocator);
+        }
+
+        index_tree_append(&i->streams, &s->node);
+
+        return i;
+}
+
+
+extern LZMA_API(void)
+lzma_index_end(lzma_index *i, lzma_allocator *allocator)
+{
+        // NOTE: If you modify this function, check also the bottom
+        // of lzma_index_cat().
+        if (i != NULL) {
+                index_tree_end(&i->streams, allocator, &index_stream_end);
+                lzma_free(i, allocator);
+        }
+
+        return;
+}
+
+
+extern void
+lzma_index_prealloc(lzma_index *i, lzma_vli records)
+{
+        if (records > PREALLOC_MAX)
+                records = PREALLOC_MAX;
+
+        i->prealloc = (size_t)(records);
+        return;
+}
+
+
+extern LZMA_API(uint64_t)
+lzma_index_memusage(lzma_vli streams, lzma_vli blocks)
+{
+        // This calculates an upper bound that is only a little bit
+        // bigger than the exact maximum memory usage with the given
+        // parameters.
+
+        // Typical malloc() overhead is 2 * sizeof(void *) but we take
+        // a little bit extra just in case. Using LZMA_MEMUSAGE_BASE
+        // instead would give too inaccurate estimate.
+        const size_t alloc_overhead = 4 * sizeof(void *);
+
+        // Amount of memory needed for each Stream base structures.
+        // We assume that every Stream has at least one Block and
+        // thus at least one group.
+        const size_t stream_base = sizeof(index_stream)
+                        + sizeof(index_group) + 2 * alloc_overhead;
+
+        // Amount of memory needed per group.
+        const size_t group_base = sizeof(index_group)
+                        + INDEX_GROUP_SIZE * sizeof(index_record)
+                        + alloc_overhead;
+
+        // Number of groups. There may actually be more, but that overhead
+        // has been taken into account in stream_base already.
+        const lzma_vli groups
+                        = (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE;
+
+        // Memory used by index_stream and index_group structures.
+        const uint64_t streams_mem = streams * stream_base;
+        const uint64_t groups_mem = groups * group_base;
+
+        // Memory used by the base structure.
+        const uint64_t index_base = sizeof(lzma_index) + alloc_overhead;
+
+        // Validate the arguments and catch integer overflows.
+        // Maximum number of Streams is "only" UINT32_MAX, because
+        // that limit is used by the tree containing the Streams.
+        const uint64_t limit = UINT64_MAX - index_base;
+        if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX
+                        || streams > limit / stream_base
+                        || groups > limit / group_base
+                        || limit - streams_mem < groups_mem)
+                return UINT64_MAX;
+
+        return index_base + streams_mem + groups_mem;
+}
+
+
+extern LZMA_API(uint64_t)
+lzma_index_memused(const lzma_index *i)
+{
+        return lzma_index_memusage(i->streams.count, i->record_count);
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_block_count(const lzma_index *i)
+{
+        return i->record_count;
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_stream_count(const lzma_index *i)
+{
+        return i->streams.count;
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_size(const lzma_index *i)
+{
+        return index_size(i->record_count, i->index_list_size);
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_total_size(const lzma_index *i)
+{
+        return i->total_size;
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_stream_size(const lzma_index *i)
+{
+        // Stream Header + Blocks + Index + Stream Footer
+        return LZMA_STREAM_HEADER_SIZE + i->total_size
+                        + index_size(i->record_count, i->index_list_size)
+                        + LZMA_STREAM_HEADER_SIZE;
+}
+
+
+static lzma_vli
+index_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum,
+                lzma_vli record_count, lzma_vli index_list_size,
+                lzma_vli stream_padding)
+{
+        // Earlier Streams and Stream Paddings + Stream Header
+        // + Blocks + Index + Stream Footer + Stream Padding
+        //
+        // This might go over LZMA_VLI_MAX due to too big unpadded_sum
+        // when this function is used in lzma_index_append().
+        lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE
+                        + stream_padding + vli_ceil4(unpadded_sum);
+        if (file_size > LZMA_VLI_MAX)
+                return LZMA_VLI_UNKNOWN;
+
+        // The same applies here.
+        file_size += index_size(record_count, index_list_size);
+        if (file_size > LZMA_VLI_MAX)
+                return LZMA_VLI_UNKNOWN;
+
+        return file_size;
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_file_size(const lzma_index *i)
+{
+        const index_stream *s = (const index_stream *)(i->streams.rightmost);
+        const index_group *g = (const index_group *)(s->groups.rightmost);
+        return index_file_size(s->node.compressed_base,
+                        g == NULL ? 0 : g->records[g->last].unpadded_sum,
+                        s->record_count, s->index_list_size,
+                        s->stream_padding);
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_uncompressed_size(const lzma_index *i)
+{
+        return i->uncompressed_size;
+}
+
+
+extern LZMA_API(uint32_t)
+lzma_index_checks(const lzma_index *i)
+{
+        uint32_t checks = i->checks;
+
+        // Get the type of the Check of the last Stream too.
+        const index_stream *s = (const index_stream *)(i->streams.rightmost);
+        if (s->stream_flags.version != UINT32_MAX)
+                checks |= UINT32_C(1) << s->stream_flags.check;
+
+        return checks;
+}
+
+
+extern uint32_t
+lzma_index_padding_size(const lzma_index *i)
+{
+        return (LZMA_VLI_C(4) - index_size_unpadded(
+                        i->record_count, i->index_list_size)) & 3;
+}
+
+
+extern LZMA_API(lzma_ret)
+lzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags)
+{
+        if (i == NULL || stream_flags == NULL)
+                return LZMA_PROG_ERROR;
+
+        // Validate the Stream Flags.
+        return_if_error(lzma_stream_flags_compare(
+                        stream_flags, stream_flags));
+
+        index_stream *s = (index_stream *)(i->streams.rightmost);
+        s->stream_flags = *stream_flags;
+
+        return LZMA_OK;
+}
+
+
+extern LZMA_API(lzma_ret)
+lzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding)
+{
+        if (i == NULL || stream_padding > LZMA_VLI_MAX
+                        || (stream_padding & 3) != 0)
+                return LZMA_PROG_ERROR;
+
+        index_stream *s = (index_stream *)(i->streams.rightmost);
+
+        // Check that the new value won't make the file grow too big.
+        const lzma_vli old_stream_padding = s->stream_padding;
+        s->stream_padding = 0;
+        if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) {
+                s->stream_padding = old_stream_padding;
+                return LZMA_DATA_ERROR;
+        }
+
+        s->stream_padding = stream_padding;
+        return LZMA_OK;
+}
+
+
+extern LZMA_API(lzma_ret)
+lzma_index_append(lzma_index *i, lzma_allocator *allocator,
+                lzma_vli unpadded_size, lzma_vli uncompressed_size)
+{
+        // Validate.
+        if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN
+                        || unpadded_size > UNPADDED_SIZE_MAX
+                        || uncompressed_size > LZMA_VLI_MAX)
+                return LZMA_PROG_ERROR;
+
+        index_stream *s = (index_stream *)(i->streams.rightmost);
+        index_group *g = (index_group *)(s->groups.rightmost);
+
+        const lzma_vli compressed_base = g == NULL ? 0
+                        : vli_ceil4(g->records[g->last].unpadded_sum);
+        const lzma_vli uncompressed_base = g == NULL ? 0
+                        : g->records[g->last].uncompressed_sum;
+        const uint32_t index_list_size_add = lzma_vli_size(unpadded_size)
+                        + lzma_vli_size(uncompressed_size);
+
+        // Check that the file size will stay within limits.
+        if (index_file_size(s->node.compressed_base,
+                        compressed_base + unpadded_size, s->record_count + 1,
+                        s->index_list_size + index_list_size_add,
+                        s->stream_padding) == LZMA_VLI_UNKNOWN)
+                return LZMA_DATA_ERROR;
+
+        // The size of the Index field must not exceed the maximum value
+        // that can be stored in the Backward Size field.
+        if (index_size(i->record_count + 1,
+                        i->index_list_size + index_list_size_add)
+                        > LZMA_BACKWARD_SIZE_MAX)
+                return LZMA_DATA_ERROR;
+
+        if (g != NULL && g->last + 1 < g->allocated) {
+                // There is space in the last group at least for one Record.
+                ++g->last;
+        } else {
+                // We need to allocate a new group.
+                g = lzma_alloc(sizeof(index_group)
+                                + i->prealloc * sizeof(index_record),
+                                allocator);
+                if (g == NULL)
+                        return LZMA_MEM_ERROR;
+
+                g->last = 0;
+                g->allocated = i->prealloc;
+
+                // Reset prealloc so that if the application happens to
+                // add new Records, the allocation size will be sane.
+                i->prealloc = INDEX_GROUP_SIZE;
+
+                // Set the start offsets of this group.
+                g->node.uncompressed_base = uncompressed_base;
+                g->node.compressed_base = compressed_base;
+                g->number_base = s->record_count + 1;
+
+                // Add the new group to the Stream.
+                index_tree_append(&s->groups, &g->node);
+        }
+
+        // Add the new Record to the group.
+        g->records[g->last].uncompressed_sum
+                        = uncompressed_base + uncompressed_size;
+        g->records[g->last].unpadded_sum
+                        = compressed_base + unpadded_size;
+
+        // Update the totals.
+        ++s->record_count;
+        s->index_list_size += index_list_size_add;
+
+        i->total_size += vli_ceil4(unpadded_size);
+        i->uncompressed_size += uncompressed_size;
+        ++i->record_count;
+        i->index_list_size += index_list_size_add;
+
+        return LZMA_OK;
+}
+
+
+/// Structure to pass info to index_cat_helper()
+typedef struct {
+        /// Uncompressed size of the destination
+        lzma_vli uncompressed_size;
+
+        /// Compressed file size of the destination
+        lzma_vli file_size;
+
+        /// Same as above but for Block numbers
+        lzma_vli block_number_add;
+
+        /// Number of Streams that were in the destination index before we
+        /// started appending new Streams from the source index. This is
+        /// used to fix the Stream numbering.
+        uint32_t stream_number_add;
+
+        /// Destination index' Stream tree
+        index_tree *streams;
+
+} index_cat_info;
+
+
+/// Add the Stream nodes from the source index to dest using recursion.
+/// Simplest iterative traversal of the source tree wouldn't work, because
+/// we update the pointers in nodes when moving them to the destination tree.
+static void
+index_cat_helper(const index_cat_info *info, index_stream *this)
+{
+        index_stream *left = (index_stream *)(this->node.left);
+        index_stream *right = (index_stream *)(this->node.right);
+
+        if (left != NULL)
+                index_cat_helper(info, left);
+
+        this->node.uncompressed_base += info->uncompressed_size;
+        this->node.compressed_base += info->file_size;
+        this->number += info->stream_number_add;
+        this->block_number_base += info->block_number_add;
+        index_tree_append(info->streams, &this->node);
+
+        if (right != NULL)
+                index_cat_helper(info, right);
+
+        return;
+}
+
+
+extern LZMA_API(lzma_ret)
+lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,
+                lzma_allocator *allocator)
+{
+        const lzma_vli dest_file_size = lzma_index_file_size(dest);
+
+        // Check that we don't exceed the file size limits.
+        if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX
+                        || dest->uncompressed_size + src->uncompressed_size
+                                > LZMA_VLI_MAX)
+                return LZMA_DATA_ERROR;
+
+        // Check that the encoded size of the combined lzma_indexes stays
+        // within limits. In theory, this should be done only if we know
+        // that the user plans to actually combine the Streams and thus
+        // construct a single Index (probably rare). However, exceeding
+        // this limit is quite theoretical, so we do this check always
+        // to simplify things elsewhere.
+        {
+                const lzma_vli dest_size = index_size_unpadded(
+                                dest->record_count, dest->index_list_size);
+                const lzma_vli src_size = index_size_unpadded(
+                                src->record_count, src->index_list_size);
+                if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX)
+                        return LZMA_DATA_ERROR;
+        }
+
+        // Optimize the last group to minimize memory usage. Allocation has
+        // to be done before modifying dest or src.
+        {
+                index_stream *s = (index_stream *)(dest->streams.rightmost);
+                index_group *g = (index_group *)(s->groups.rightmost);
+                if (g != NULL && g->last + 1 < g->allocated) {
+                        assert(g->node.left == NULL);
+                        assert(g->node.right == NULL);
+
+                        index_group *newg = lzma_alloc(sizeof(index_group)
+                                        + (g->last + 1)
+                                        * sizeof(index_record),
+                                        allocator);
+                        if (newg == NULL)
+                                return LZMA_MEM_ERROR;
+
+                        newg->node = g->node;
+                        newg->allocated = g->last + 1;
+                        newg->last = g->last;
+                        newg->number_base = g->number_base;
+
+                        memcpy(newg->records, g->records, newg->allocated
+                                        * sizeof(index_record));
+
+                        if (g->node.parent != NULL) {
+                                assert(g->node.parent->right == &g->node);
+                                g->node.parent->right = &newg->node;
+                        }
+
+                        if (s->groups.leftmost == &g->node) {
+                                assert(s->groups.root == &g->node);
+                                s->groups.leftmost = &newg->node;
+                                s->groups.root = &newg->node;
+                        }
+
+                        if (s->groups.rightmost == &g->node)
+                                s->groups.rightmost = &newg->node;
+
+                        lzma_free(g, allocator);
+                }
+        }
+
+        // Add all the Streams from src to dest. Update the base offsets
+        // of each Stream from src.
+        const index_cat_info info = {
+                .uncompressed_size = dest->uncompressed_size,
+                .file_size = dest_file_size,
+                .stream_number_add = dest->streams.count,
+                .block_number_add = dest->record_count,
+                .streams = &dest->streams,
+        };
+        index_cat_helper(&info, (index_stream *)(src->streams.root));
+
+        // Update info about all the combined Streams.
+        dest->uncompressed_size += src->uncompressed_size;
+        dest->total_size += src->total_size;
+        dest->record_count += src->record_count;
+        dest->index_list_size += src->index_list_size;
+        dest->checks = lzma_index_checks(dest) | src->checks;
+
+        // There's nothing else left in src than the base structure.
+        lzma_free(src, allocator);
+
+        return LZMA_OK;
+}
+
+
+/// Duplicate an index_stream.
+static index_stream *
+index_dup_stream(const index_stream *src, lzma_allocator *allocator)
+{
+        // Catch a somewhat theoretical integer overflow.
+        if (src->record_count > PREALLOC_MAX)
+                return NULL;
+
+        // Allocate and initialize a new Stream.
+        index_stream *dest = index_stream_init(src->node.compressed_base,
+                        src->node.uncompressed_base, src->number,
+                        src->block_number_base, allocator);
+
+        // Return immediately if allocation failed or if there are
+        // no groups to duplicate.
+        if (dest == NULL || src->groups.leftmost == NULL)
+                return dest;
+
+        // Copy the overall information.
+        dest->record_count = src->record_count;
+        dest->index_list_size = src->index_list_size;
+        dest->stream_flags = src->stream_flags;
+        dest->stream_padding = src->stream_padding;
+
+        // Allocate memory for the Records. We put all the Records into
+        // a single group. It's simplest and also tends to make
+        // lzma_index_locate() a little bit faster with very big Indexes.
+        index_group *destg = lzma_alloc(sizeof(index_group)
+                        + src->record_count * sizeof(index_record),
+                        allocator);
+        if (destg == NULL) {
+                index_stream_end(dest, allocator);
+                return NULL;
+        }
+
+        // Initialize destg.
+        destg->node.uncompressed_base = 0;
+        destg->node.compressed_base = 0;
+        destg->number_base = 1;
+        destg->allocated = src->record_count;
+        destg->last = src->record_count - 1;
+
+        // Go through all the groups in src and copy the Records into destg.
+        const index_group *srcg = (const index_group *)(src->groups.leftmost);
+        size_t i = 0;
+        do {
+                memcpy(destg->records + i, srcg->records,
+                                (srcg->last + 1) * sizeof(index_record));
+                i += srcg->last + 1;
+                srcg = index_tree_next(&srcg->node);
+        } while (srcg != NULL);
+
+        assert(i == destg->allocated);
+
+        // Add the group to the new Stream.
+        index_tree_append(&dest->groups, &destg->node);
+
+        return dest;
+}
+
+
+extern LZMA_API(lzma_index *)
+lzma_index_dup(const lzma_index *src, lzma_allocator *allocator)
+{
+        // Allocate the base structure (no initial Stream).
+        lzma_index *dest = index_init_plain(allocator);
+        if (dest == NULL)
+                return NULL;
+
+        // Copy the totals.
+        dest->uncompressed_size = src->uncompressed_size;
+        dest->total_size = src->total_size;
+        dest->record_count = src->record_count;
+        dest->index_list_size = src->index_list_size;
+
+        // Copy the Streams and the groups in them.
+        const index_stream *srcstream
+                        = (const index_stream *)(src->streams.leftmost);
+        do {
+                index_stream *deststream = index_dup_stream(
+                                srcstream, allocator);
+                if (deststream == NULL) {
+                        lzma_index_end(dest, allocator);
+                        return NULL;
+                }
+
+                index_tree_append(&dest->streams, &deststream->node);
+
+                srcstream = index_tree_next(&srcstream->node);
+        } while (srcstream != NULL);
+
+        return dest;
+}
+
+
+/// Indexing for lzma_index_iter.internal[]
+enum {
+        ITER_INDEX,
+        ITER_STREAM,
+        ITER_GROUP,
+        ITER_RECORD,
+        ITER_METHOD,
+};
+
+
+/// Values for lzma_index_iter.internal[ITER_METHOD].s
+enum {
+        ITER_METHOD_NORMAL,
+        ITER_METHOD_NEXT,
+        ITER_METHOD_LEFTMOST,
+};
+
+
+static void
+iter_set_info(lzma_index_iter *iter)
+{
+        const lzma_index *i = iter->internal[ITER_INDEX].p;
+        const index_stream *stream = iter->internal[ITER_STREAM].p;
+        const index_group *group = iter->internal[ITER_GROUP].p;
+        const size_t record = iter->internal[ITER_RECORD].s;
+
+        // lzma_index_iter.internal must not contain a pointer to the last
+        // group in the index, because that may be reallocated by
+        // lzma_index_cat().
+        if (group == NULL) {
+                // There are no groups.
+                assert(stream->groups.root == NULL);
+                iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
+
+        } else if (i->streams.rightmost != &stream->node
+                        || stream->groups.rightmost != &group->node) {
+                // The group is not not the last group in the index.
+                iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
+
+        } else if (stream->groups.leftmost != &group->node) {
+                // The group isn't the only group in the Stream, thus we
+                // know that it must have a parent group i.e. it's not
+                // the root node.
+                assert(stream->groups.root != &group->node);
+                assert(group->node.parent->right == &group->node);
+                iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT;
+                iter->internal[ITER_GROUP].p = group->node.parent;
+
+        } else {
+                // The Stream has only one group.
+                assert(stream->groups.root == &group->node);
+                assert(group->node.parent == NULL);
+                iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
+                iter->internal[ITER_GROUP].p = NULL;
+        }
+
+        iter->stream.number = stream->number;
+        iter->stream.block_count = stream->record_count;
+        iter->stream.compressed_offset = stream->node.compressed_base;
+        iter->stream.uncompressed_offset = stream->node.uncompressed_base;
+
+        // iter->stream.flags will be NULL if the Stream Flags haven't been
+        // set with lzma_index_stream_flags().
+        iter->stream.flags = stream->stream_flags.version == UINT32_MAX
+                        ? NULL : &stream->stream_flags;
+        iter->stream.padding = stream->stream_padding;
+
+        if (stream->groups.rightmost == NULL) {
+                // Stream has no Blocks.
+                iter->stream.compressed_size = index_size(0, 0)
+                                + 2 * LZMA_STREAM_HEADER_SIZE;
+                iter->stream.uncompressed_size = 0;
+        } else {
+                const index_group *g = (const index_group *)(
+                                stream->groups.rightmost);
+
+                // Stream Header + Stream Footer + Index + Blocks
+                iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE
+                                + index_size(stream->record_count,
+                                        stream->index_list_size)
+                                + vli_ceil4(g->records[g->last].unpadded_sum);
+                iter->stream.uncompressed_size
+                                = g->records[g->last].uncompressed_sum;
+        }
+
+        if (group != NULL) {
+                iter->block.number_in_stream = group->number_base + record;
+                iter->block.number_in_file = iter->block.number_in_stream
+                                + stream->block_number_base;
+
+                iter->block.compressed_stream_offset
+                                = record == 0 ? group->node.compressed_base
+                                : vli_ceil4(group->records[
+                                        record - 1].unpadded_sum);
+                iter->block.uncompressed_stream_offset
+                                = record == 0 ? group->node.uncompressed_base
+                                : group->records[record - 1].uncompressed_sum;
+
+                iter->block.uncompressed_size
+                                = group->records[record].uncompressed_sum
+                                - iter->block.uncompressed_stream_offset;
+                iter->block.unpadded_size
+                                = group->records[record].unpadded_sum
+                                - iter->block.compressed_stream_offset;
+                iter->block.total_size = vli_ceil4(iter->block.unpadded_size);
+
+                iter->block.compressed_stream_offset
+                                += LZMA_STREAM_HEADER_SIZE;
+
+                iter->block.compressed_file_offset
+                                = iter->block.compressed_stream_offset
+                                + iter->stream.compressed_offset;
+                iter->block.uncompressed_file_offset
+                                = iter->block.uncompressed_stream_offset
+                                + iter->stream.uncompressed_offset;
+        }
+
+        return;
+}
+
+
+extern LZMA_API(void)
+lzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i)
+{
+        iter->internal[ITER_INDEX].p = i;
+        lzma_index_iter_rewind(iter);
+        return;
+}
+
+
+extern LZMA_API(void)
+lzma_index_iter_rewind(lzma_index_iter *iter)
+{
+        iter->internal[ITER_STREAM].p = NULL;
+        iter->internal[ITER_GROUP].p = NULL;
+        iter->internal[ITER_RECORD].s = 0;
+        iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
+        return;
+}
+
+
+extern LZMA_API(lzma_bool)
+lzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode)
+{
+        // Catch unsupported mode values.
+        if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK)
+                return true;
+
+        const lzma_index *i = iter->internal[ITER_INDEX].p;
+        const index_stream *stream = iter->internal[ITER_STREAM].p;
+        const index_group *group = NULL;
+        size_t record = iter->internal[ITER_RECORD].s;
+
+        // If we are being asked for the next Stream, leave group to NULL
+        // so that the rest of the this function thinks that this Stream
+        // has no groups and will thus go to the next Stream.
+        if (mode != LZMA_INDEX_ITER_STREAM) {
+                // Get the pointer to the current group. See iter_set_inf()
+                // for explanation.
+                switch (iter->internal[ITER_METHOD].s) {
+                case ITER_METHOD_NORMAL:
+                        group = iter->internal[ITER_GROUP].p;
+                        break;
+
+                case ITER_METHOD_NEXT:
+                        group = index_tree_next(iter->internal[ITER_GROUP].p);
+                        break;
+
+                case ITER_METHOD_LEFTMOST:
+                        group = (const index_group *)(
+                                        stream->groups.leftmost);
+                        break;
+                }
+        }
+
+again:
+        if (stream == NULL) {
+                // We at the beginning of the lzma_index.
+                // Locate the first Stream.
+                stream = (const index_stream *)(i->streams.leftmost);
+                if (mode >= LZMA_INDEX_ITER_BLOCK) {
+                        // Since we are being asked to return information
+                        // about the first a Block, skip Streams that have
+                        // no Blocks.
+                        while (stream->groups.leftmost == NULL) {
+                                stream = index_tree_next(&stream->node);
+                                if (stream == NULL)
+                                        return true;
+                        }
+                }
+
+                // Start from the first Record in the Stream.
+                group = (const index_group *)(stream->groups.leftmost);
+                record = 0;
+
+        } else if (group != NULL && record < group->last) {
+                // The next Record is in the same group.
+                ++record;
+
+        } else {
+                // This group has no more Records or this Stream has
+                // no Blocks at all.
+                record = 0;
+
+                // If group is not NULL, this Stream has at least one Block
+                // and thus at least one group. Find the next group.
+                if (group != NULL)
+                        group = index_tree_next(&group->node);
+
+                if (group == NULL) {
+                        // This Stream has no more Records. Find the next
+                        // Stream. If we are being asked to return information
+                        // about a Block, we skip empty Streams.
+                        do {
+                                stream = index_tree_next(&stream->node);
+                                if (stream == NULL)
+                                        return true;
+                        } while (mode >= LZMA_INDEX_ITER_BLOCK
+                                        && stream->groups.leftmost == NULL);
+
+                        group = (const index_group *)(
+                                        stream->groups.leftmost);
+                }
+        }
+
+        if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) {
+                // We need to look for the next Block again if this Block
+                // is empty.
+                if (record == 0) {
+                        if (group->node.uncompressed_base
+                                        == group->records[0].uncompressed_sum)
+                                goto again;
+                } else if (group->records[record - 1].uncompressed_sum
+                                == group->records[record].uncompressed_sum) {
+                        goto again;
+                }
+        }
+
+        iter->internal[ITER_STREAM].p = stream;
+        iter->internal[ITER_GROUP].p = group;
+        iter->internal[ITER_RECORD].s = record;
+
+        iter_set_info(iter);
+
+        return false;
+}
+
+
+extern LZMA_API(lzma_bool)
+lzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target)
+{
+        const lzma_index *i = iter->internal[ITER_INDEX].p;
+
+        // If the target is past the end of the file, return immediately.
+        if (i->uncompressed_size <= target)
+                return true;
+
+        // Locate the Stream containing the target offset.
+        const index_stream *stream = index_tree_locate(&i->streams, target);
+        assert(stream != NULL);
+        target -= stream->node.uncompressed_base;
+
+        // Locate the group containing the target offset.
+        const index_group *group = index_tree_locate(&stream->groups, target);
+        assert(group != NULL);
+
+        // Use binary search to locate the exact Record. It is the first
+        // Record whose uncompressed_sum is greater than target.
+        // This is because we want the rightmost Record that fullfills the
+        // search criterion. It is possible that there are empty Blocks;
+        // we don't want to return them.
+        size_t left = 0;
+        size_t right = group->last;
+
+        while (left < right) {
+                const size_t pos = left + (right - left) / 2;
+                if (group->records[pos].uncompressed_sum <= target)
+                        left = pos + 1;
+                else
+                        right = pos;
+        }
+
+        iter->internal[ITER_STREAM].p = stream;
+        iter->internal[ITER_GROUP].p = group;
+        iter->internal[ITER_RECORD].s = left;
+
+        iter_set_info(iter);
+
+        return false;
+}