xref: /freebsd/contrib/xz/src/liblzma/common/index.c (revision 7ffc4ec4860d01414b493cdf43738878a9ede538)

// SPDX-License-Identifier: 0BSD

///////////////////////////////////////////////////////////////////////////////
//
/// \file       index.c
/// \brief      Handling of .xz Indexes and some other Stream information
//
//  Author:     Lasse Collin
//
///////////////////////////////////////////////////////////////////////////////

#include "common.h"
#include "index.h"
#include "stream_flags_common.h"


/// \brief      Maximum number of Streams supported in lzma_index
///
/// The maximum number of Streams is UINT32_MAX, because index_tree.count
/// is uint32_t. This is unlikely to be reached in practice because it
/// would require allocating hundreds of gigabytes of memory.
#define STREAMS_MAX UINT32_MAX


/// \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 512


/// \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
	/// lzma_index.uncompressed_bias) or Block (relative to
	/// the beginning of the Stream)
	lzma_vli uncompressed_base;

	/// Compressed start offset of this Stream (relative to
	/// lzma_index.compressed_bias) or Block (relative to
	/// the beginning of the Stream)
	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 (first) node
	index_tree_node *leftmost;

	/// Rightmost (last) node
	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 Streams.
	index_tree_node node;

	/// Number of this Stream counted in reverse: the last Stream
	/// in the lzma_index has .number == 0. In the API, the first
	/// Stream is 1, so the real number of this Stream is
	/// lzma_index.streams.count - .number.
	uint32_t number;

	/// Total number of Blocks before this Stream relative to
	/// lzma_index.block_number_base.
	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;

	/// In index_stream, node.uncompressed_base, node.compressed_base,
	/// and block_number_base are relative to these _bias members
	/// instead of being relative to 0. If a new index_stream is
	/// prepended before the existing index_streams, the offsets of all
	/// existing index_streams can be changed by updating these _biases.
	lzma_vli uncompressed_bias;
	lzma_vli compressed_bias;
	lzma_vli block_number_bias;

	/// 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 overridden 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, const lzma_allocator *allocator,
		void (*free_func)(void *node, const 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);

	free_func(node, allocator);
	return;
}


/// Free the memory allocated for a tree. Each node is freed using the
/// given free_func which is either &lzma_free or &index_stream_end.
/// The latter 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, const lzma_allocator *allocator,
		void (*free_func)(void *node, const lzma_allocator *allocator))
{
	assert(free_func != NULL);

	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.
///
/// The tree is always filled sequentially: index_streams are prepended
/// and index_groups are appended.
static void
index_tree_append(index_tree *tree, index_tree_node *node, bool prepend)
{
	node->parent = prepend ? tree->leftmost : 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;
	}

	// Add the new node before the leftmost or after the rightmost node.
	if (prepend) {
		assert(tree->leftmost->uncompressed_base
				>= node->uncompressed_base);
		assert(tree->leftmost->compressed_base
				> node->compressed_base);
		tree->leftmost->left = node;
		tree->leftmost = node;
	} else {
		assert(tree->rightmost->uncompressed_base
				<= node->uncompressed_base);
		assert(tree->rightmost->compressed_base
				< node->compressed_base);
		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 right/left using node as the rotation root.
		index_tree_node *pivot = prepend ? node->left : node->right;

		if (node->parent == NULL) {
			tree->root = pivot;
		} else if (prepend) {
			assert(node->parent->left == node);
			node->parent->left = pivot;
		} else {
			assert(node->parent->right == node);
			node->parent->right = pivot;
		}

		pivot->parent = node->parent;

		if (prepend) {
			node->left = pivot->right;
			if (node->left != NULL)
				node->left->parent = node;

			pivot->right = node;
		} else {
			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);
}


/// Get the previous node in the tree. Return NULL if there are no more nodes.
static void *
index_tree_prev(const index_tree_node *node)
{
	if (node->left != NULL) {
		node = node->left;
		while (node->right != NULL)
			node = node->right;

		return (void *)(node);
	}

	while (node->parent != NULL && node->parent->left == 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;

	// 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,
		uint32_t stream_number, lzma_vli block_number_base,
		const 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, const lzma_allocator *allocator)
{
	index_stream *s = node;
	index_tree_end(&s->groups, allocator, &lzma_free);
	lzma_free(s, allocator);
	return;
}


static lzma_index *
index_init_plain(const lzma_allocator *allocator)
{
	lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);
	if (i != NULL) {
		index_tree_init(&i->streams);
		i->uncompressed_bias = LZMA_VLI_MAX;
		i->compressed_bias = LZMA_VLI_MAX;
		i->block_number_bias = LZMA_VLI_MAX;
		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(const lzma_allocator *allocator)
{
	lzma_index *i = index_init_plain(allocator);
	if (i == NULL)
		return NULL;

	index_stream *s = index_stream_init(
			i->compressed_bias, i->uncompressed_bias,
			0, i->block_number_bias, allocator);
	if (s == NULL) {
		lzma_free(i, allocator);
		return NULL;
	}

	index_tree_append(&i->streams, &s->node, true);

	return i;
}


extern LZMA_API(void)
lzma_index_end(lzma_index *i, const 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 bool
lzma_index_prealloc(lzma_index *i, lzma_vli records)
{
	if (records > PREALLOC_MAX)
		return true;

	// If index_decoder.c calls us with records == 0, it's decoding
	// an Index that has no Records. In that case the decoder won't call
	// lzma_index_append() at all, and i->prealloc isn't used during
	// the Index decoding either.
	//
	// Normally the first lzma_index_append() call from the Index decoder
	// would reset i->prealloc to INDEX_GROUP_SIZE. With no Records,
	// lzma_index_append() isn't called and the resetting of prealloc
	// won't occur either. Thus, if records == 0, use the default value
	// INDEX_GROUP_SIZE instead.
	//
	// NOTE: lzma_index_append() assumes i->prealloc > 0. liblzma <= 5.8.2
	// didn't have this check and could set i->prealloc = 0, which would
	// result in a buffer overflow if the application called
	// lzma_index_append() after decoding an empty Index. Appending
	// Records after decoding an Index is a rare thing to do, but
	// it is supposed to work.
	if (records == 0)
		records = INDEX_GROUP_SIZE;

	i->prealloc = (size_t)(records);
	return false;
}


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.
	const uint64_t limit = UINT64_MAX - index_base;
	if (streams == 0 || streams > STREAMS_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 - i->compressed_bias,
			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, const 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 uncompressed size will not overflow.
	if (uncompressed_base + uncompressed_size > LZMA_VLI_MAX)
		return LZMA_DATA_ERROR;

	// Check that the new unpadded sum will not overflow. This is
	// checked again in index_file_size(), but the unpadded sum is
	// passed to vli_ceil4() which expects a valid lzma_vli value.
	if (compressed_base + unpadded_size > UNPADDED_SIZE_MAX)
		return LZMA_DATA_ERROR;

	// Check that the file size will stay within limits.
	if (index_file_size(s->node.compressed_base - i->compressed_bias,
			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.
		assert(i->prealloc > 0);
		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, false);
	}

	// 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 {
	lzma_vli uncompressed_adjust;
	lzma_vli compressed_adjust;
	lzma_vli block_number_adjust;
	uint32_t stream_number_adjust;
	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 (right != NULL)
		index_cat_helper(info, right);

	// The Stream number counts in reverse, thus += instead of -=.
	this->node.uncompressed_base -= info->uncompressed_adjust;
	this->node.compressed_base -= info->compressed_adjust;
	this->number += info->stream_number_adjust;
	this->block_number_base -= info->block_number_adjust;
	index_tree_append(info->streams, &this->node, true);

	if (left != NULL)
		index_cat_helper(info, left);

	return;
}


extern LZMA_API(lzma_ret)
lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,
		const lzma_allocator *allocator)
{
	if (dest == NULL || src == NULL)
		return LZMA_PROG_ERROR;

	// Check that we don't exceed the maximum number of Streams
	// per lzma_index.
	if (STREAMS_MAX - dest->streams.count < src->streams.count)
		return LZMA_DATA_ERROR;

	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;
			}

			assert(s->groups.rightmost == &g->node);
			s->groups.rightmost = &newg->node;

			lzma_free(g, allocator);

			// NOTE: newg isn't leaked here because
			// newg == (void *)&newg->node.
		}
	}

	// dest->checks includes the check types of all except the last Stream
	// in dest. Use lzma_index_checks() to get the check type of the
	// last Stream too. This needs to be done before the Streams are
	// moved from dest to src.
	src->checks |= lzma_index_checks(dest);

	// Update the biases.
	src->uncompressed_bias -= dest->uncompressed_size;
	src->compressed_bias -= dest_file_size;
	src->block_number_bias -= dest->record_count;

	// Prepend all the Streams from dest to src.
	const index_cat_info info = {
		.uncompressed_adjust = dest->uncompressed_bias
				- src->uncompressed_bias,
		.compressed_adjust = dest->compressed_bias
				- src->compressed_bias,
		.block_number_adjust = dest->block_number_bias
				- src->block_number_bias,
		.stream_number_adjust = src->streams.count,
		.streams = &src->streams,
	};
	index_cat_helper(&info, (index_stream *)(dest->streams.root));

	// Update info about all the combined Streams.
	src->uncompressed_size += dest->uncompressed_size;
	src->total_size += dest->total_size;
	src->record_count += dest->record_count;
	src->index_list_size += dest->index_list_size;

	// There's nothing else left in dest than the base structure.
	// The API is defined so that dest is modified and src is freed,
	// so copy src to dest and free the base struct of src.
	*dest = *src;
	lzma_free(src, allocator);

	return LZMA_OK;
}


/// Duplicate an index_stream.
static index_stream *
index_dup_stream(const index_stream *src, const 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);
	if (dest == NULL)
		return NULL;

	// 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;

	// Return if there are no groups to duplicate.
	if (src->groups.leftmost == NULL)
		return dest;

	// 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, false);

	return dest;
}


extern LZMA_API(lzma_index *)
lzma_index_dup(const lzma_index *src, const 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_bias = src->uncompressed_bias;
	dest->compressed_bias = src->compressed_bias;
	dest->block_number_bias = src->block_number_bias;
	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 = src->checks;

	// Copy the Streams and the groups in them.
	const index_stream *srcstream
			= (const index_stream *)(src->streams.rightmost);
	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, true);

		srcstream = index_tree_prev(&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;
	}

	// NOTE: lzma_index_iter.stream.number is lzma_vli but we use uint32_t
	// internally. The internal value counts in reverse (last one is 0)
	// but in lzma_index_iter.stream.number the first Stream is 1.
	iter->stream.number = i->streams.count - stream->number;
	iter->stream.block_count = stream->record_count;
	iter->stream.compressed_offset = stream->node.compressed_base
			- i->compressed_bias;
	iter->stream.uncompressed_offset = stream->node.uncompressed_base
			- i->uncompressed_bias;

	// 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 - i->block_number_bias);

		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;

	assert(i->uncompressed_size <= LZMA_VLI_MAX);

	// If the target is past the end of the file, return immediately.
	if (i->uncompressed_size <= target)
		return true;

	assert(target < LZMA_VLI_MAX);

	// Locate the Stream containing the target offset.
	// NOTE: Adding the bias can make target >= LZMA_VLI_MAX.
	target += i->uncompressed_bias;
	const index_stream *stream = index_tree_locate(&i->streams, target);
	assert(stream != NULL);
	target -= stream->node.uncompressed_base;
	assert(target < LZMA_VLI_MAX);

	// 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 fulfills 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;
}