1*3b35e7eeSXin LI // SPDX-License-Identifier: 0BSD
2*3b35e7eeSXin LI
381ad8388SMartin Matuska ///////////////////////////////////////////////////////////////////////////////
481ad8388SMartin Matuska //
581ad8388SMartin Matuska /// \file index.c
681ad8388SMartin Matuska /// \brief Handling of .xz Indexes and some other Stream information
781ad8388SMartin Matuska //
881ad8388SMartin Matuska // Author: Lasse Collin
981ad8388SMartin Matuska //
1081ad8388SMartin Matuska ///////////////////////////////////////////////////////////////////////////////
1181ad8388SMartin Matuska
12047153b4SXin LI #include "common.h"
1381ad8388SMartin Matuska #include "index.h"
1481ad8388SMartin Matuska #include "stream_flags_common.h"
1581ad8388SMartin Matuska
1681ad8388SMartin Matuska
1781ad8388SMartin Matuska /// \brief How many Records to allocate at once
1881ad8388SMartin Matuska ///
1981ad8388SMartin Matuska /// This should be big enough to avoid making lots of tiny allocations
2081ad8388SMartin Matuska /// but small enough to avoid too much unused memory at once.
21542aef48SMartin Matuska #define INDEX_GROUP_SIZE 512
2281ad8388SMartin Matuska
2381ad8388SMartin Matuska
2481ad8388SMartin Matuska /// \brief How many Records can be allocated at once at maximum
2581ad8388SMartin Matuska #define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))
2681ad8388SMartin Matuska
2781ad8388SMartin Matuska
2881ad8388SMartin Matuska /// \brief Base structure for index_stream and index_group structures
2981ad8388SMartin Matuska typedef struct index_tree_node_s index_tree_node;
3081ad8388SMartin Matuska struct index_tree_node_s {
3181ad8388SMartin Matuska /// Uncompressed start offset of this Stream (relative to the
3281ad8388SMartin Matuska /// beginning of the file) or Block (relative to the beginning
3381ad8388SMartin Matuska /// of the Stream)
3481ad8388SMartin Matuska lzma_vli uncompressed_base;
3581ad8388SMartin Matuska
3681ad8388SMartin Matuska /// Compressed start offset of this Stream or Block
3781ad8388SMartin Matuska lzma_vli compressed_base;
3881ad8388SMartin Matuska
3981ad8388SMartin Matuska index_tree_node *parent;
4081ad8388SMartin Matuska index_tree_node *left;
4181ad8388SMartin Matuska index_tree_node *right;
4281ad8388SMartin Matuska };
4381ad8388SMartin Matuska
4481ad8388SMartin Matuska
4581ad8388SMartin Matuska /// \brief AVL tree to hold index_stream or index_group structures
4681ad8388SMartin Matuska typedef struct {
4781ad8388SMartin Matuska /// Root node
4881ad8388SMartin Matuska index_tree_node *root;
4981ad8388SMartin Matuska
5081ad8388SMartin Matuska /// Leftmost node. Since the tree will be filled sequentially,
5181ad8388SMartin Matuska /// this won't change after the first node has been added to
5281ad8388SMartin Matuska /// the tree.
5381ad8388SMartin Matuska index_tree_node *leftmost;
5481ad8388SMartin Matuska
5581ad8388SMartin Matuska /// The rightmost node in the tree. Since the tree is filled
5681ad8388SMartin Matuska /// sequentially, this is always the node where to add the new data.
5781ad8388SMartin Matuska index_tree_node *rightmost;
5881ad8388SMartin Matuska
5981ad8388SMartin Matuska /// Number of nodes in the tree
6081ad8388SMartin Matuska uint32_t count;
6181ad8388SMartin Matuska
6281ad8388SMartin Matuska } index_tree;
6381ad8388SMartin Matuska
6481ad8388SMartin Matuska
6581ad8388SMartin Matuska typedef struct {
6681ad8388SMartin Matuska lzma_vli uncompressed_sum;
6781ad8388SMartin Matuska lzma_vli unpadded_sum;
6881ad8388SMartin Matuska } index_record;
6981ad8388SMartin Matuska
7081ad8388SMartin Matuska
7181ad8388SMartin Matuska typedef struct {
7281ad8388SMartin Matuska /// Every Record group is part of index_stream.groups tree.
7381ad8388SMartin Matuska index_tree_node node;
7481ad8388SMartin Matuska
7581ad8388SMartin Matuska /// Number of Blocks in this Stream before this group.
7681ad8388SMartin Matuska lzma_vli number_base;
7781ad8388SMartin Matuska
7881ad8388SMartin Matuska /// Number of Records that can be put in records[].
7981ad8388SMartin Matuska size_t allocated;
8081ad8388SMartin Matuska
8181ad8388SMartin Matuska /// Index of the last Record in use.
8281ad8388SMartin Matuska size_t last;
8381ad8388SMartin Matuska
8481ad8388SMartin Matuska /// The sizes in this array are stored as cumulative sums relative
8581ad8388SMartin Matuska /// to the beginning of the Stream. This makes it possible to
8681ad8388SMartin Matuska /// use binary search in lzma_index_locate().
8781ad8388SMartin Matuska ///
8881ad8388SMartin Matuska /// Note that the cumulative summing is done specially for
8981ad8388SMartin Matuska /// unpadded_sum: The previous value is rounded up to the next
9081ad8388SMartin Matuska /// multiple of four before adding the Unpadded Size of the new
9181ad8388SMartin Matuska /// Block. The total encoded size of the Blocks in the Stream
9281ad8388SMartin Matuska /// is records[last].unpadded_sum in the last Record group of
9381ad8388SMartin Matuska /// the Stream.
9481ad8388SMartin Matuska ///
9581ad8388SMartin Matuska /// For example, if the Unpadded Sizes are 39, 57, and 81, the
9681ad8388SMartin Matuska /// stored values are 39, 97 (40 + 57), and 181 (100 + 181).
9781ad8388SMartin Matuska /// The total encoded size of these Blocks is 184.
9881ad8388SMartin Matuska ///
9981ad8388SMartin Matuska /// This is a flexible array, because it makes easy to optimize
10081ad8388SMartin Matuska /// memory usage in case someone concatenates many Streams that
10181ad8388SMartin Matuska /// have only one or few Blocks.
10281ad8388SMartin Matuska index_record records[];
10381ad8388SMartin Matuska
10481ad8388SMartin Matuska } index_group;
10581ad8388SMartin Matuska
10681ad8388SMartin Matuska
10781ad8388SMartin Matuska typedef struct {
108a8675d92SXin LI /// Every index_stream is a node in the tree of Streams.
10981ad8388SMartin Matuska index_tree_node node;
11081ad8388SMartin Matuska
11181ad8388SMartin Matuska /// Number of this Stream (first one is 1)
11281ad8388SMartin Matuska uint32_t number;
11381ad8388SMartin Matuska
11481ad8388SMartin Matuska /// Total number of Blocks before this Stream
11581ad8388SMartin Matuska lzma_vli block_number_base;
11681ad8388SMartin Matuska
11781ad8388SMartin Matuska /// Record groups of this Stream are stored in a tree.
11881ad8388SMartin Matuska /// It's a T-tree with AVL-tree balancing. There are
11981ad8388SMartin Matuska /// INDEX_GROUP_SIZE Records per node by default.
12081ad8388SMartin Matuska /// This keeps the number of memory allocations reasonable
12181ad8388SMartin Matuska /// and finding a Record is fast.
12281ad8388SMartin Matuska index_tree groups;
12381ad8388SMartin Matuska
12481ad8388SMartin Matuska /// Number of Records in this Stream
12581ad8388SMartin Matuska lzma_vli record_count;
12681ad8388SMartin Matuska
12781ad8388SMartin Matuska /// Size of the List of Records field in this Stream. This is used
12881ad8388SMartin Matuska /// together with record_count to calculate the size of the Index
12981ad8388SMartin Matuska /// field and thus the total size of the Stream.
13081ad8388SMartin Matuska lzma_vli index_list_size;
13181ad8388SMartin Matuska
13281ad8388SMartin Matuska /// Stream Flags of this Stream. This is meaningful only if
13381ad8388SMartin Matuska /// the Stream Flags have been told us with lzma_index_stream_flags().
13481ad8388SMartin Matuska /// Initially stream_flags.version is set to UINT32_MAX to indicate
13581ad8388SMartin Matuska /// that the Stream Flags are unknown.
13681ad8388SMartin Matuska lzma_stream_flags stream_flags;
13781ad8388SMartin Matuska
13881ad8388SMartin Matuska /// Amount of Stream Padding after this Stream. This defaults to
13981ad8388SMartin Matuska /// zero and can be set with lzma_index_stream_padding().
14081ad8388SMartin Matuska lzma_vli stream_padding;
14181ad8388SMartin Matuska
14281ad8388SMartin Matuska } index_stream;
14381ad8388SMartin Matuska
14481ad8388SMartin Matuska
14581ad8388SMartin Matuska struct lzma_index_s {
14681ad8388SMartin Matuska /// AVL-tree containing the Stream(s). Often there is just one
14781ad8388SMartin Matuska /// Stream, but using a tree keeps lookups fast even when there
14881ad8388SMartin Matuska /// are many concatenated Streams.
14981ad8388SMartin Matuska index_tree streams;
15081ad8388SMartin Matuska
15181ad8388SMartin Matuska /// Uncompressed size of all the Blocks in the Stream(s)
15281ad8388SMartin Matuska lzma_vli uncompressed_size;
15381ad8388SMartin Matuska
15481ad8388SMartin Matuska /// Total size of all the Blocks in the Stream(s)
15581ad8388SMartin Matuska lzma_vli total_size;
15681ad8388SMartin Matuska
15781ad8388SMartin Matuska /// Total number of Records in all Streams in this lzma_index
15881ad8388SMartin Matuska lzma_vli record_count;
15981ad8388SMartin Matuska
16081ad8388SMartin Matuska /// Size of the List of Records field if all the Streams in this
16181ad8388SMartin Matuska /// lzma_index were packed into a single Stream (makes it simpler to
16281ad8388SMartin Matuska /// take many .xz files and combine them into a single Stream).
16381ad8388SMartin Matuska ///
16481ad8388SMartin Matuska /// This value together with record_count is needed to calculate
16581ad8388SMartin Matuska /// Backward Size that is stored into Stream Footer.
16681ad8388SMartin Matuska lzma_vli index_list_size;
16781ad8388SMartin Matuska
16881ad8388SMartin Matuska /// How many Records to allocate at once in lzma_index_append().
169a8675d92SXin LI /// This defaults to INDEX_GROUP_SIZE but can be overridden with
17081ad8388SMartin Matuska /// lzma_index_prealloc().
17181ad8388SMartin Matuska size_t prealloc;
17281ad8388SMartin Matuska
17381ad8388SMartin Matuska /// Bitmask indicating what integrity check types have been used
17481ad8388SMartin Matuska /// as set by lzma_index_stream_flags(). The bit of the last Stream
17581ad8388SMartin Matuska /// is not included here, since it is possible to change it by
17681ad8388SMartin Matuska /// calling lzma_index_stream_flags() again.
17781ad8388SMartin Matuska uint32_t checks;
17881ad8388SMartin Matuska };
17981ad8388SMartin Matuska
18081ad8388SMartin Matuska
18181ad8388SMartin Matuska static void
index_tree_init(index_tree * tree)18281ad8388SMartin Matuska index_tree_init(index_tree *tree)
18381ad8388SMartin Matuska {
18481ad8388SMartin Matuska tree->root = NULL;
18581ad8388SMartin Matuska tree->leftmost = NULL;
18681ad8388SMartin Matuska tree->rightmost = NULL;
18781ad8388SMartin Matuska tree->count = 0;
18881ad8388SMartin Matuska return;
18981ad8388SMartin Matuska }
19081ad8388SMartin Matuska
19181ad8388SMartin Matuska
19281ad8388SMartin Matuska /// Helper for index_tree_end()
19381ad8388SMartin Matuska static void
index_tree_node_end(index_tree_node * node,const lzma_allocator * allocator,void (* free_func)(void * node,const lzma_allocator * allocator))19453200025SRui Paulo index_tree_node_end(index_tree_node *node, const lzma_allocator *allocator,
19553200025SRui Paulo void (*free_func)(void *node, const lzma_allocator *allocator))
19681ad8388SMartin Matuska {
19781ad8388SMartin Matuska // The tree won't ever be very huge, so recursion should be fine.
19881ad8388SMartin Matuska // 20 levels in the tree is likely quite a lot already in practice.
19981ad8388SMartin Matuska if (node->left != NULL)
20081ad8388SMartin Matuska index_tree_node_end(node->left, allocator, free_func);
20181ad8388SMartin Matuska
20281ad8388SMartin Matuska if (node->right != NULL)
20381ad8388SMartin Matuska index_tree_node_end(node->right, allocator, free_func);
20481ad8388SMartin Matuska
20581ad8388SMartin Matuska free_func(node, allocator);
20681ad8388SMartin Matuska return;
20781ad8388SMartin Matuska }
20881ad8388SMartin Matuska
20981ad8388SMartin Matuska
2101456f0f9SXin LI /// Free the memory allocated for a tree. Each node is freed using the
2111456f0f9SXin LI /// given free_func which is either &lzma_free or &index_stream_end.
2121456f0f9SXin LI /// The latter is used to free the Record groups from each index_stream
2131456f0f9SXin LI /// before freeing the index_stream itself.
21481ad8388SMartin Matuska static void
index_tree_end(index_tree * tree,const lzma_allocator * allocator,void (* free_func)(void * node,const lzma_allocator * allocator))21553200025SRui Paulo index_tree_end(index_tree *tree, const lzma_allocator *allocator,
21653200025SRui Paulo void (*free_func)(void *node, const lzma_allocator *allocator))
21781ad8388SMartin Matuska {
2181456f0f9SXin LI assert(free_func != NULL);
2191456f0f9SXin LI
22081ad8388SMartin Matuska if (tree->root != NULL)
22181ad8388SMartin Matuska index_tree_node_end(tree->root, allocator, free_func);
22281ad8388SMartin Matuska
22381ad8388SMartin Matuska return;
22481ad8388SMartin Matuska }
22581ad8388SMartin Matuska
22681ad8388SMartin Matuska
22781ad8388SMartin Matuska /// Add a new node to the tree. node->uncompressed_base and
22881ad8388SMartin Matuska /// node->compressed_base must have been set by the caller already.
22981ad8388SMartin Matuska static void
index_tree_append(index_tree * tree,index_tree_node * node)23081ad8388SMartin Matuska index_tree_append(index_tree *tree, index_tree_node *node)
23181ad8388SMartin Matuska {
23281ad8388SMartin Matuska node->parent = tree->rightmost;
23381ad8388SMartin Matuska node->left = NULL;
23481ad8388SMartin Matuska node->right = NULL;
23581ad8388SMartin Matuska
23681ad8388SMartin Matuska ++tree->count;
23781ad8388SMartin Matuska
23881ad8388SMartin Matuska // Handle the special case of adding the first node.
23981ad8388SMartin Matuska if (tree->root == NULL) {
24081ad8388SMartin Matuska tree->root = node;
24181ad8388SMartin Matuska tree->leftmost = node;
24281ad8388SMartin Matuska tree->rightmost = node;
24381ad8388SMartin Matuska return;
24481ad8388SMartin Matuska }
24581ad8388SMartin Matuska
24681ad8388SMartin Matuska // The tree is always filled sequentially.
24781ad8388SMartin Matuska assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);
24881ad8388SMartin Matuska assert(tree->rightmost->compressed_base < node->compressed_base);
24981ad8388SMartin Matuska
25081ad8388SMartin Matuska // Add the new node after the rightmost node. It's the correct
25181ad8388SMartin Matuska // place due to the reason above.
25281ad8388SMartin Matuska tree->rightmost->right = node;
25381ad8388SMartin Matuska tree->rightmost = node;
25481ad8388SMartin Matuska
25581ad8388SMartin Matuska // Balance the AVL-tree if needed. We don't need to keep the balance
25681ad8388SMartin Matuska // factors in nodes, because we always fill the tree sequentially,
25781ad8388SMartin Matuska // and thus know the state of the tree just by looking at the node
25881ad8388SMartin Matuska // count. From the node count we can calculate how many steps to go
25981ad8388SMartin Matuska // up in the tree to find the rotation root.
26081ad8388SMartin Matuska uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count));
26181ad8388SMartin Matuska if (up != 0) {
26281ad8388SMartin Matuska // Locate the root node for the rotation.
26381ad8388SMartin Matuska up = ctz32(tree->count) + 2;
26481ad8388SMartin Matuska do {
26581ad8388SMartin Matuska node = node->parent;
26681ad8388SMartin Matuska } while (--up > 0);
26781ad8388SMartin Matuska
26881ad8388SMartin Matuska // Rotate left using node as the rotation root.
26981ad8388SMartin Matuska index_tree_node *pivot = node->right;
27081ad8388SMartin Matuska
27181ad8388SMartin Matuska if (node->parent == NULL) {
27281ad8388SMartin Matuska tree->root = pivot;
27381ad8388SMartin Matuska } else {
27481ad8388SMartin Matuska assert(node->parent->right == node);
27581ad8388SMartin Matuska node->parent->right = pivot;
27681ad8388SMartin Matuska }
27781ad8388SMartin Matuska
27881ad8388SMartin Matuska pivot->parent = node->parent;
27981ad8388SMartin Matuska
28081ad8388SMartin Matuska node->right = pivot->left;
28181ad8388SMartin Matuska if (node->right != NULL)
28281ad8388SMartin Matuska node->right->parent = node;
28381ad8388SMartin Matuska
28481ad8388SMartin Matuska pivot->left = node;
28581ad8388SMartin Matuska node->parent = pivot;
28681ad8388SMartin Matuska }
28781ad8388SMartin Matuska
28881ad8388SMartin Matuska return;
28981ad8388SMartin Matuska }
29081ad8388SMartin Matuska
29181ad8388SMartin Matuska
29281ad8388SMartin Matuska /// Get the next node in the tree. Return NULL if there are no more nodes.
29381ad8388SMartin Matuska static void *
index_tree_next(const index_tree_node * node)29481ad8388SMartin Matuska index_tree_next(const index_tree_node *node)
29581ad8388SMartin Matuska {
29681ad8388SMartin Matuska if (node->right != NULL) {
29781ad8388SMartin Matuska node = node->right;
29881ad8388SMartin Matuska while (node->left != NULL)
29981ad8388SMartin Matuska node = node->left;
30081ad8388SMartin Matuska
30181ad8388SMartin Matuska return (void *)(node);
30281ad8388SMartin Matuska }
30381ad8388SMartin Matuska
30481ad8388SMartin Matuska while (node->parent != NULL && node->parent->right == node)
30581ad8388SMartin Matuska node = node->parent;
30681ad8388SMartin Matuska
30781ad8388SMartin Matuska return (void *)(node->parent);
30881ad8388SMartin Matuska }
30981ad8388SMartin Matuska
31081ad8388SMartin Matuska
31181ad8388SMartin Matuska /// Locate a node that contains the given uncompressed offset. It is
31281ad8388SMartin Matuska /// caller's job to check that target is not bigger than the uncompressed
31381ad8388SMartin Matuska /// size of the tree (the last node would be returned in that case still).
31481ad8388SMartin Matuska static void *
index_tree_locate(const index_tree * tree,lzma_vli target)31581ad8388SMartin Matuska index_tree_locate(const index_tree *tree, lzma_vli target)
31681ad8388SMartin Matuska {
31781ad8388SMartin Matuska const index_tree_node *result = NULL;
31881ad8388SMartin Matuska const index_tree_node *node = tree->root;
31981ad8388SMartin Matuska
32081ad8388SMartin Matuska assert(tree->leftmost == NULL
32181ad8388SMartin Matuska || tree->leftmost->uncompressed_base == 0);
32281ad8388SMartin Matuska
32381ad8388SMartin Matuska // Consecutive nodes may have the same uncompressed_base.
32481ad8388SMartin Matuska // We must pick the rightmost one.
32581ad8388SMartin Matuska while (node != NULL) {
32681ad8388SMartin Matuska if (node->uncompressed_base > target) {
32781ad8388SMartin Matuska node = node->left;
32881ad8388SMartin Matuska } else {
32981ad8388SMartin Matuska result = node;
33081ad8388SMartin Matuska node = node->right;
33181ad8388SMartin Matuska }
33281ad8388SMartin Matuska }
33381ad8388SMartin Matuska
33481ad8388SMartin Matuska return (void *)(result);
33581ad8388SMartin Matuska }
33681ad8388SMartin Matuska
33781ad8388SMartin Matuska
33881ad8388SMartin Matuska /// Allocate and initialize a new Stream using the given base offsets.
33981ad8388SMartin Matuska 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)34081ad8388SMartin Matuska index_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base,
341fe50a38eSXin LI uint32_t stream_number, lzma_vli block_number_base,
34253200025SRui Paulo const lzma_allocator *allocator)
34381ad8388SMartin Matuska {
34481ad8388SMartin Matuska index_stream *s = lzma_alloc(sizeof(index_stream), allocator);
34581ad8388SMartin Matuska if (s == NULL)
34681ad8388SMartin Matuska return NULL;
34781ad8388SMartin Matuska
34881ad8388SMartin Matuska s->node.uncompressed_base = uncompressed_base;
34981ad8388SMartin Matuska s->node.compressed_base = compressed_base;
35081ad8388SMartin Matuska s->node.parent = NULL;
35181ad8388SMartin Matuska s->node.left = NULL;
35281ad8388SMartin Matuska s->node.right = NULL;
35381ad8388SMartin Matuska
35481ad8388SMartin Matuska s->number = stream_number;
35581ad8388SMartin Matuska s->block_number_base = block_number_base;
35681ad8388SMartin Matuska
35781ad8388SMartin Matuska index_tree_init(&s->groups);
35881ad8388SMartin Matuska
35981ad8388SMartin Matuska s->record_count = 0;
36081ad8388SMartin Matuska s->index_list_size = 0;
36181ad8388SMartin Matuska s->stream_flags.version = UINT32_MAX;
36281ad8388SMartin Matuska s->stream_padding = 0;
36381ad8388SMartin Matuska
36481ad8388SMartin Matuska return s;
36581ad8388SMartin Matuska }
36681ad8388SMartin Matuska
36781ad8388SMartin Matuska
36881ad8388SMartin Matuska /// Free the memory allocated for a Stream and its Record groups.
36981ad8388SMartin Matuska static void
index_stream_end(void * node,const lzma_allocator * allocator)37053200025SRui Paulo index_stream_end(void *node, const lzma_allocator *allocator)
37181ad8388SMartin Matuska {
37281ad8388SMartin Matuska index_stream *s = node;
3731456f0f9SXin LI index_tree_end(&s->groups, allocator, &lzma_free);
3741456f0f9SXin LI lzma_free(s, allocator);
37581ad8388SMartin Matuska return;
37681ad8388SMartin Matuska }
37781ad8388SMartin Matuska
37881ad8388SMartin Matuska
37981ad8388SMartin Matuska static lzma_index *
index_init_plain(const lzma_allocator * allocator)38053200025SRui Paulo index_init_plain(const lzma_allocator *allocator)
38181ad8388SMartin Matuska {
38281ad8388SMartin Matuska lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);
38381ad8388SMartin Matuska if (i != NULL) {
38481ad8388SMartin Matuska index_tree_init(&i->streams);
38581ad8388SMartin Matuska i->uncompressed_size = 0;
38681ad8388SMartin Matuska i->total_size = 0;
38781ad8388SMartin Matuska i->record_count = 0;
38881ad8388SMartin Matuska i->index_list_size = 0;
38981ad8388SMartin Matuska i->prealloc = INDEX_GROUP_SIZE;
39081ad8388SMartin Matuska i->checks = 0;
39181ad8388SMartin Matuska }
39281ad8388SMartin Matuska
39381ad8388SMartin Matuska return i;
39481ad8388SMartin Matuska }
39581ad8388SMartin Matuska
39681ad8388SMartin Matuska
39781ad8388SMartin Matuska extern LZMA_API(lzma_index *)
lzma_index_init(const lzma_allocator * allocator)39853200025SRui Paulo lzma_index_init(const lzma_allocator *allocator)
39981ad8388SMartin Matuska {
40081ad8388SMartin Matuska lzma_index *i = index_init_plain(allocator);
401e24134bcSMartin Matuska if (i == NULL)
402e24134bcSMartin Matuska return NULL;
403e24134bcSMartin Matuska
40481ad8388SMartin Matuska index_stream *s = index_stream_init(0, 0, 1, 0, allocator);
405e24134bcSMartin Matuska if (s == NULL) {
40681ad8388SMartin Matuska lzma_free(i, allocator);
407e24134bcSMartin Matuska return NULL;
40881ad8388SMartin Matuska }
40981ad8388SMartin Matuska
41081ad8388SMartin Matuska index_tree_append(&i->streams, &s->node);
41181ad8388SMartin Matuska
41281ad8388SMartin Matuska return i;
41381ad8388SMartin Matuska }
41481ad8388SMartin Matuska
41581ad8388SMartin Matuska
41681ad8388SMartin Matuska extern LZMA_API(void)
lzma_index_end(lzma_index * i,const lzma_allocator * allocator)41753200025SRui Paulo lzma_index_end(lzma_index *i, const lzma_allocator *allocator)
41881ad8388SMartin Matuska {
41981ad8388SMartin Matuska // NOTE: If you modify this function, check also the bottom
42081ad8388SMartin Matuska // of lzma_index_cat().
42181ad8388SMartin Matuska if (i != NULL) {
42281ad8388SMartin Matuska index_tree_end(&i->streams, allocator, &index_stream_end);
42381ad8388SMartin Matuska lzma_free(i, allocator);
42481ad8388SMartin Matuska }
42581ad8388SMartin Matuska
42681ad8388SMartin Matuska return;
42781ad8388SMartin Matuska }
42881ad8388SMartin Matuska
42981ad8388SMartin Matuska
43081ad8388SMartin Matuska extern void
lzma_index_prealloc(lzma_index * i,lzma_vli records)43181ad8388SMartin Matuska lzma_index_prealloc(lzma_index *i, lzma_vli records)
43281ad8388SMartin Matuska {
43381ad8388SMartin Matuska if (records > PREALLOC_MAX)
43481ad8388SMartin Matuska records = PREALLOC_MAX;
43581ad8388SMartin Matuska
43681ad8388SMartin Matuska i->prealloc = (size_t)(records);
43781ad8388SMartin Matuska return;
43881ad8388SMartin Matuska }
43981ad8388SMartin Matuska
44081ad8388SMartin Matuska
44181ad8388SMartin Matuska extern LZMA_API(uint64_t)
lzma_index_memusage(lzma_vli streams,lzma_vli blocks)44281ad8388SMartin Matuska lzma_index_memusage(lzma_vli streams, lzma_vli blocks)
44381ad8388SMartin Matuska {
44481ad8388SMartin Matuska // This calculates an upper bound that is only a little bit
44581ad8388SMartin Matuska // bigger than the exact maximum memory usage with the given
44681ad8388SMartin Matuska // parameters.
44781ad8388SMartin Matuska
44881ad8388SMartin Matuska // Typical malloc() overhead is 2 * sizeof(void *) but we take
44981ad8388SMartin Matuska // a little bit extra just in case. Using LZMA_MEMUSAGE_BASE
45081ad8388SMartin Matuska // instead would give too inaccurate estimate.
45181ad8388SMartin Matuska const size_t alloc_overhead = 4 * sizeof(void *);
45281ad8388SMartin Matuska
45381ad8388SMartin Matuska // Amount of memory needed for each Stream base structures.
45481ad8388SMartin Matuska // We assume that every Stream has at least one Block and
45581ad8388SMartin Matuska // thus at least one group.
45681ad8388SMartin Matuska const size_t stream_base = sizeof(index_stream)
45781ad8388SMartin Matuska + sizeof(index_group) + 2 * alloc_overhead;
45881ad8388SMartin Matuska
45981ad8388SMartin Matuska // Amount of memory needed per group.
46081ad8388SMartin Matuska const size_t group_base = sizeof(index_group)
46181ad8388SMartin Matuska + INDEX_GROUP_SIZE * sizeof(index_record)
46281ad8388SMartin Matuska + alloc_overhead;
46381ad8388SMartin Matuska
46481ad8388SMartin Matuska // Number of groups. There may actually be more, but that overhead
46581ad8388SMartin Matuska // has been taken into account in stream_base already.
46681ad8388SMartin Matuska const lzma_vli groups
46781ad8388SMartin Matuska = (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE;
46881ad8388SMartin Matuska
46981ad8388SMartin Matuska // Memory used by index_stream and index_group structures.
47081ad8388SMartin Matuska const uint64_t streams_mem = streams * stream_base;
47181ad8388SMartin Matuska const uint64_t groups_mem = groups * group_base;
47281ad8388SMartin Matuska
47381ad8388SMartin Matuska // Memory used by the base structure.
47481ad8388SMartin Matuska const uint64_t index_base = sizeof(lzma_index) + alloc_overhead;
47581ad8388SMartin Matuska
47681ad8388SMartin Matuska // Validate the arguments and catch integer overflows.
47781ad8388SMartin Matuska // Maximum number of Streams is "only" UINT32_MAX, because
47881ad8388SMartin Matuska // that limit is used by the tree containing the Streams.
47981ad8388SMartin Matuska const uint64_t limit = UINT64_MAX - index_base;
48081ad8388SMartin Matuska if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX
48181ad8388SMartin Matuska || streams > limit / stream_base
48281ad8388SMartin Matuska || groups > limit / group_base
48381ad8388SMartin Matuska || limit - streams_mem < groups_mem)
48481ad8388SMartin Matuska return UINT64_MAX;
48581ad8388SMartin Matuska
48681ad8388SMartin Matuska return index_base + streams_mem + groups_mem;
48781ad8388SMartin Matuska }
48881ad8388SMartin Matuska
48981ad8388SMartin Matuska
49081ad8388SMartin Matuska extern LZMA_API(uint64_t)
lzma_index_memused(const lzma_index * i)49181ad8388SMartin Matuska lzma_index_memused(const lzma_index *i)
49281ad8388SMartin Matuska {
49381ad8388SMartin Matuska return lzma_index_memusage(i->streams.count, i->record_count);
49481ad8388SMartin Matuska }
49581ad8388SMartin Matuska
49681ad8388SMartin Matuska
49781ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_block_count(const lzma_index * i)49881ad8388SMartin Matuska lzma_index_block_count(const lzma_index *i)
49981ad8388SMartin Matuska {
50081ad8388SMartin Matuska return i->record_count;
50181ad8388SMartin Matuska }
50281ad8388SMartin Matuska
50381ad8388SMartin Matuska
50481ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_stream_count(const lzma_index * i)50581ad8388SMartin Matuska lzma_index_stream_count(const lzma_index *i)
50681ad8388SMartin Matuska {
50781ad8388SMartin Matuska return i->streams.count;
50881ad8388SMartin Matuska }
50981ad8388SMartin Matuska
51081ad8388SMartin Matuska
51181ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_size(const lzma_index * i)51281ad8388SMartin Matuska lzma_index_size(const lzma_index *i)
51381ad8388SMartin Matuska {
51481ad8388SMartin Matuska return index_size(i->record_count, i->index_list_size);
51581ad8388SMartin Matuska }
51681ad8388SMartin Matuska
51781ad8388SMartin Matuska
51881ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_total_size(const lzma_index * i)51981ad8388SMartin Matuska lzma_index_total_size(const lzma_index *i)
52081ad8388SMartin Matuska {
52181ad8388SMartin Matuska return i->total_size;
52281ad8388SMartin Matuska }
52381ad8388SMartin Matuska
52481ad8388SMartin Matuska
52581ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_stream_size(const lzma_index * i)52681ad8388SMartin Matuska lzma_index_stream_size(const lzma_index *i)
52781ad8388SMartin Matuska {
52881ad8388SMartin Matuska // Stream Header + Blocks + Index + Stream Footer
52981ad8388SMartin Matuska return LZMA_STREAM_HEADER_SIZE + i->total_size
53081ad8388SMartin Matuska + index_size(i->record_count, i->index_list_size)
53181ad8388SMartin Matuska + LZMA_STREAM_HEADER_SIZE;
53281ad8388SMartin Matuska }
53381ad8388SMartin Matuska
53481ad8388SMartin Matuska
53581ad8388SMartin Matuska 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)53681ad8388SMartin Matuska index_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum,
53781ad8388SMartin Matuska lzma_vli record_count, lzma_vli index_list_size,
53881ad8388SMartin Matuska lzma_vli stream_padding)
53981ad8388SMartin Matuska {
54081ad8388SMartin Matuska // Earlier Streams and Stream Paddings + Stream Header
54181ad8388SMartin Matuska // + Blocks + Index + Stream Footer + Stream Padding
54281ad8388SMartin Matuska //
54381ad8388SMartin Matuska // This might go over LZMA_VLI_MAX due to too big unpadded_sum
54481ad8388SMartin Matuska // when this function is used in lzma_index_append().
54581ad8388SMartin Matuska lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE
54681ad8388SMartin Matuska + stream_padding + vli_ceil4(unpadded_sum);
54781ad8388SMartin Matuska if (file_size > LZMA_VLI_MAX)
54881ad8388SMartin Matuska return LZMA_VLI_UNKNOWN;
54981ad8388SMartin Matuska
55081ad8388SMartin Matuska // The same applies here.
55181ad8388SMartin Matuska file_size += index_size(record_count, index_list_size);
55281ad8388SMartin Matuska if (file_size > LZMA_VLI_MAX)
55381ad8388SMartin Matuska return LZMA_VLI_UNKNOWN;
55481ad8388SMartin Matuska
55581ad8388SMartin Matuska return file_size;
55681ad8388SMartin Matuska }
55781ad8388SMartin Matuska
55881ad8388SMartin Matuska
55981ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_file_size(const lzma_index * i)56081ad8388SMartin Matuska lzma_index_file_size(const lzma_index *i)
56181ad8388SMartin Matuska {
56281ad8388SMartin Matuska const index_stream *s = (const index_stream *)(i->streams.rightmost);
56381ad8388SMartin Matuska const index_group *g = (const index_group *)(s->groups.rightmost);
56481ad8388SMartin Matuska return index_file_size(s->node.compressed_base,
56581ad8388SMartin Matuska g == NULL ? 0 : g->records[g->last].unpadded_sum,
56681ad8388SMartin Matuska s->record_count, s->index_list_size,
56781ad8388SMartin Matuska s->stream_padding);
56881ad8388SMartin Matuska }
56981ad8388SMartin Matuska
57081ad8388SMartin Matuska
57181ad8388SMartin Matuska extern LZMA_API(lzma_vli)
lzma_index_uncompressed_size(const lzma_index * i)57281ad8388SMartin Matuska lzma_index_uncompressed_size(const lzma_index *i)
57381ad8388SMartin Matuska {
57481ad8388SMartin Matuska return i->uncompressed_size;
57581ad8388SMartin Matuska }
57681ad8388SMartin Matuska
57781ad8388SMartin Matuska
57881ad8388SMartin Matuska extern LZMA_API(uint32_t)
lzma_index_checks(const lzma_index * i)57981ad8388SMartin Matuska lzma_index_checks(const lzma_index *i)
58081ad8388SMartin Matuska {
58181ad8388SMartin Matuska uint32_t checks = i->checks;
58281ad8388SMartin Matuska
58381ad8388SMartin Matuska // Get the type of the Check of the last Stream too.
58481ad8388SMartin Matuska const index_stream *s = (const index_stream *)(i->streams.rightmost);
58581ad8388SMartin Matuska if (s->stream_flags.version != UINT32_MAX)
58681ad8388SMartin Matuska checks |= UINT32_C(1) << s->stream_flags.check;
58781ad8388SMartin Matuska
58881ad8388SMartin Matuska return checks;
58981ad8388SMartin Matuska }
59081ad8388SMartin Matuska
59181ad8388SMartin Matuska
59281ad8388SMartin Matuska extern uint32_t
lzma_index_padding_size(const lzma_index * i)59381ad8388SMartin Matuska lzma_index_padding_size(const lzma_index *i)
59481ad8388SMartin Matuska {
59581ad8388SMartin Matuska return (LZMA_VLI_C(4) - index_size_unpadded(
59681ad8388SMartin Matuska i->record_count, i->index_list_size)) & 3;
59781ad8388SMartin Matuska }
59881ad8388SMartin Matuska
59981ad8388SMartin Matuska
60081ad8388SMartin Matuska extern LZMA_API(lzma_ret)
lzma_index_stream_flags(lzma_index * i,const lzma_stream_flags * stream_flags)60181ad8388SMartin Matuska lzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags)
60281ad8388SMartin Matuska {
60381ad8388SMartin Matuska if (i == NULL || stream_flags == NULL)
60481ad8388SMartin Matuska return LZMA_PROG_ERROR;
60581ad8388SMartin Matuska
60681ad8388SMartin Matuska // Validate the Stream Flags.
60781ad8388SMartin Matuska return_if_error(lzma_stream_flags_compare(
60881ad8388SMartin Matuska stream_flags, stream_flags));
60981ad8388SMartin Matuska
61081ad8388SMartin Matuska index_stream *s = (index_stream *)(i->streams.rightmost);
61181ad8388SMartin Matuska s->stream_flags = *stream_flags;
61281ad8388SMartin Matuska
61381ad8388SMartin Matuska return LZMA_OK;
61481ad8388SMartin Matuska }
61581ad8388SMartin Matuska
61681ad8388SMartin Matuska
61781ad8388SMartin Matuska extern LZMA_API(lzma_ret)
lzma_index_stream_padding(lzma_index * i,lzma_vli stream_padding)61881ad8388SMartin Matuska lzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding)
61981ad8388SMartin Matuska {
62081ad8388SMartin Matuska if (i == NULL || stream_padding > LZMA_VLI_MAX
62181ad8388SMartin Matuska || (stream_padding & 3) != 0)
62281ad8388SMartin Matuska return LZMA_PROG_ERROR;
62381ad8388SMartin Matuska
62481ad8388SMartin Matuska index_stream *s = (index_stream *)(i->streams.rightmost);
62581ad8388SMartin Matuska
62681ad8388SMartin Matuska // Check that the new value won't make the file grow too big.
62781ad8388SMartin Matuska const lzma_vli old_stream_padding = s->stream_padding;
62881ad8388SMartin Matuska s->stream_padding = 0;
62981ad8388SMartin Matuska if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) {
63081ad8388SMartin Matuska s->stream_padding = old_stream_padding;
63181ad8388SMartin Matuska return LZMA_DATA_ERROR;
63281ad8388SMartin Matuska }
63381ad8388SMartin Matuska
63481ad8388SMartin Matuska s->stream_padding = stream_padding;
63581ad8388SMartin Matuska return LZMA_OK;
63681ad8388SMartin Matuska }
63781ad8388SMartin Matuska
63881ad8388SMartin Matuska
63981ad8388SMartin Matuska extern LZMA_API(lzma_ret)
lzma_index_append(lzma_index * i,const lzma_allocator * allocator,lzma_vli unpadded_size,lzma_vli uncompressed_size)64053200025SRui Paulo lzma_index_append(lzma_index *i, const lzma_allocator *allocator,
64181ad8388SMartin Matuska lzma_vli unpadded_size, lzma_vli uncompressed_size)
64281ad8388SMartin Matuska {
64381ad8388SMartin Matuska // Validate.
64481ad8388SMartin Matuska if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN
64581ad8388SMartin Matuska || unpadded_size > UNPADDED_SIZE_MAX
64681ad8388SMartin Matuska || uncompressed_size > LZMA_VLI_MAX)
64781ad8388SMartin Matuska return LZMA_PROG_ERROR;
64881ad8388SMartin Matuska
64981ad8388SMartin Matuska index_stream *s = (index_stream *)(i->streams.rightmost);
65081ad8388SMartin Matuska index_group *g = (index_group *)(s->groups.rightmost);
65181ad8388SMartin Matuska
65281ad8388SMartin Matuska const lzma_vli compressed_base = g == NULL ? 0
65381ad8388SMartin Matuska : vli_ceil4(g->records[g->last].unpadded_sum);
65481ad8388SMartin Matuska const lzma_vli uncompressed_base = g == NULL ? 0
65581ad8388SMartin Matuska : g->records[g->last].uncompressed_sum;
65681ad8388SMartin Matuska const uint32_t index_list_size_add = lzma_vli_size(unpadded_size)
65781ad8388SMartin Matuska + lzma_vli_size(uncompressed_size);
65881ad8388SMartin Matuska
6599e6bbe47SXin LI // Check that uncompressed size will not overflow.
6609e6bbe47SXin LI if (uncompressed_base + uncompressed_size > LZMA_VLI_MAX)
6619e6bbe47SXin LI return LZMA_DATA_ERROR;
6629e6bbe47SXin LI
663ca6a6373SXin LI // Check that the new unpadded sum will not overflow. This is
664ca6a6373SXin LI // checked again in index_file_size(), but the unpadded sum is
665ca6a6373SXin LI // passed to vli_ceil4() which expects a valid lzma_vli value.
666ca6a6373SXin LI if (compressed_base + unpadded_size > UNPADDED_SIZE_MAX)
667ca6a6373SXin LI return LZMA_DATA_ERROR;
668ca6a6373SXin LI
66981ad8388SMartin Matuska // Check that the file size will stay within limits.
67081ad8388SMartin Matuska if (index_file_size(s->node.compressed_base,
67181ad8388SMartin Matuska compressed_base + unpadded_size, s->record_count + 1,
67281ad8388SMartin Matuska s->index_list_size + index_list_size_add,
67381ad8388SMartin Matuska s->stream_padding) == LZMA_VLI_UNKNOWN)
67481ad8388SMartin Matuska return LZMA_DATA_ERROR;
67581ad8388SMartin Matuska
67681ad8388SMartin Matuska // The size of the Index field must not exceed the maximum value
67781ad8388SMartin Matuska // that can be stored in the Backward Size field.
67881ad8388SMartin Matuska if (index_size(i->record_count + 1,
67981ad8388SMartin Matuska i->index_list_size + index_list_size_add)
68081ad8388SMartin Matuska > LZMA_BACKWARD_SIZE_MAX)
68181ad8388SMartin Matuska return LZMA_DATA_ERROR;
68281ad8388SMartin Matuska
68381ad8388SMartin Matuska if (g != NULL && g->last + 1 < g->allocated) {
68481ad8388SMartin Matuska // There is space in the last group at least for one Record.
68581ad8388SMartin Matuska ++g->last;
68681ad8388SMartin Matuska } else {
68781ad8388SMartin Matuska // We need to allocate a new group.
68881ad8388SMartin Matuska g = lzma_alloc(sizeof(index_group)
68981ad8388SMartin Matuska + i->prealloc * sizeof(index_record),
69081ad8388SMartin Matuska allocator);
69181ad8388SMartin Matuska if (g == NULL)
69281ad8388SMartin Matuska return LZMA_MEM_ERROR;
69381ad8388SMartin Matuska
69481ad8388SMartin Matuska g->last = 0;
69581ad8388SMartin Matuska g->allocated = i->prealloc;
69681ad8388SMartin Matuska
69781ad8388SMartin Matuska // Reset prealloc so that if the application happens to
69881ad8388SMartin Matuska // add new Records, the allocation size will be sane.
69981ad8388SMartin Matuska i->prealloc = INDEX_GROUP_SIZE;
70081ad8388SMartin Matuska
70181ad8388SMartin Matuska // Set the start offsets of this group.
70281ad8388SMartin Matuska g->node.uncompressed_base = uncompressed_base;
70381ad8388SMartin Matuska g->node.compressed_base = compressed_base;
70481ad8388SMartin Matuska g->number_base = s->record_count + 1;
70581ad8388SMartin Matuska
70681ad8388SMartin Matuska // Add the new group to the Stream.
70781ad8388SMartin Matuska index_tree_append(&s->groups, &g->node);
70881ad8388SMartin Matuska }
70981ad8388SMartin Matuska
71081ad8388SMartin Matuska // Add the new Record to the group.
71181ad8388SMartin Matuska g->records[g->last].uncompressed_sum
71281ad8388SMartin Matuska = uncompressed_base + uncompressed_size;
71381ad8388SMartin Matuska g->records[g->last].unpadded_sum
71481ad8388SMartin Matuska = compressed_base + unpadded_size;
71581ad8388SMartin Matuska
71681ad8388SMartin Matuska // Update the totals.
71781ad8388SMartin Matuska ++s->record_count;
71881ad8388SMartin Matuska s->index_list_size += index_list_size_add;
71981ad8388SMartin Matuska
72081ad8388SMartin Matuska i->total_size += vli_ceil4(unpadded_size);
72181ad8388SMartin Matuska i->uncompressed_size += uncompressed_size;
72281ad8388SMartin Matuska ++i->record_count;
72381ad8388SMartin Matuska i->index_list_size += index_list_size_add;
72481ad8388SMartin Matuska
72581ad8388SMartin Matuska return LZMA_OK;
72681ad8388SMartin Matuska }
72781ad8388SMartin Matuska
72881ad8388SMartin Matuska
72981ad8388SMartin Matuska /// Structure to pass info to index_cat_helper()
73081ad8388SMartin Matuska typedef struct {
73181ad8388SMartin Matuska /// Uncompressed size of the destination
73281ad8388SMartin Matuska lzma_vli uncompressed_size;
73381ad8388SMartin Matuska
73481ad8388SMartin Matuska /// Compressed file size of the destination
73581ad8388SMartin Matuska lzma_vli file_size;
73681ad8388SMartin Matuska
73781ad8388SMartin Matuska /// Same as above but for Block numbers
73881ad8388SMartin Matuska lzma_vli block_number_add;
73981ad8388SMartin Matuska
74081ad8388SMartin Matuska /// Number of Streams that were in the destination index before we
74181ad8388SMartin Matuska /// started appending new Streams from the source index. This is
74281ad8388SMartin Matuska /// used to fix the Stream numbering.
74381ad8388SMartin Matuska uint32_t stream_number_add;
74481ad8388SMartin Matuska
74581ad8388SMartin Matuska /// Destination index' Stream tree
74681ad8388SMartin Matuska index_tree *streams;
74781ad8388SMartin Matuska
74881ad8388SMartin Matuska } index_cat_info;
74981ad8388SMartin Matuska
75081ad8388SMartin Matuska
75181ad8388SMartin Matuska /// Add the Stream nodes from the source index to dest using recursion.
75281ad8388SMartin Matuska /// Simplest iterative traversal of the source tree wouldn't work, because
75381ad8388SMartin Matuska /// we update the pointers in nodes when moving them to the destination tree.
75481ad8388SMartin Matuska static void
index_cat_helper(const index_cat_info * info,index_stream * this)75581ad8388SMartin Matuska index_cat_helper(const index_cat_info *info, index_stream *this)
75681ad8388SMartin Matuska {
75781ad8388SMartin Matuska index_stream *left = (index_stream *)(this->node.left);
75881ad8388SMartin Matuska index_stream *right = (index_stream *)(this->node.right);
75981ad8388SMartin Matuska
76081ad8388SMartin Matuska if (left != NULL)
76181ad8388SMartin Matuska index_cat_helper(info, left);
76281ad8388SMartin Matuska
76381ad8388SMartin Matuska this->node.uncompressed_base += info->uncompressed_size;
76481ad8388SMartin Matuska this->node.compressed_base += info->file_size;
76581ad8388SMartin Matuska this->number += info->stream_number_add;
76681ad8388SMartin Matuska this->block_number_base += info->block_number_add;
76781ad8388SMartin Matuska index_tree_append(info->streams, &this->node);
76881ad8388SMartin Matuska
76981ad8388SMartin Matuska if (right != NULL)
77081ad8388SMartin Matuska index_cat_helper(info, right);
77181ad8388SMartin Matuska
77281ad8388SMartin Matuska return;
77381ad8388SMartin Matuska }
77481ad8388SMartin Matuska
77581ad8388SMartin Matuska
77681ad8388SMartin Matuska extern LZMA_API(lzma_ret)
lzma_index_cat(lzma_index * restrict dest,lzma_index * restrict src,const lzma_allocator * allocator)77781ad8388SMartin Matuska lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,
77853200025SRui Paulo const lzma_allocator *allocator)
77981ad8388SMartin Matuska {
7809e6bbe47SXin LI if (dest == NULL || src == NULL)
7819e6bbe47SXin LI return LZMA_PROG_ERROR;
7829e6bbe47SXin LI
78381ad8388SMartin Matuska const lzma_vli dest_file_size = lzma_index_file_size(dest);
78481ad8388SMartin Matuska
78581ad8388SMartin Matuska // Check that we don't exceed the file size limits.
78681ad8388SMartin Matuska if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX
78781ad8388SMartin Matuska || dest->uncompressed_size + src->uncompressed_size
78881ad8388SMartin Matuska > LZMA_VLI_MAX)
78981ad8388SMartin Matuska return LZMA_DATA_ERROR;
79081ad8388SMartin Matuska
79181ad8388SMartin Matuska // Check that the encoded size of the combined lzma_indexes stays
79281ad8388SMartin Matuska // within limits. In theory, this should be done only if we know
79381ad8388SMartin Matuska // that the user plans to actually combine the Streams and thus
79481ad8388SMartin Matuska // construct a single Index (probably rare). However, exceeding
79581ad8388SMartin Matuska // this limit is quite theoretical, so we do this check always
79681ad8388SMartin Matuska // to simplify things elsewhere.
79781ad8388SMartin Matuska {
79881ad8388SMartin Matuska const lzma_vli dest_size = index_size_unpadded(
79981ad8388SMartin Matuska dest->record_count, dest->index_list_size);
80081ad8388SMartin Matuska const lzma_vli src_size = index_size_unpadded(
80181ad8388SMartin Matuska src->record_count, src->index_list_size);
80281ad8388SMartin Matuska if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX)
80381ad8388SMartin Matuska return LZMA_DATA_ERROR;
80481ad8388SMartin Matuska }
80581ad8388SMartin Matuska
80681ad8388SMartin Matuska // Optimize the last group to minimize memory usage. Allocation has
80781ad8388SMartin Matuska // to be done before modifying dest or src.
80881ad8388SMartin Matuska {
80981ad8388SMartin Matuska index_stream *s = (index_stream *)(dest->streams.rightmost);
81081ad8388SMartin Matuska index_group *g = (index_group *)(s->groups.rightmost);
81181ad8388SMartin Matuska if (g != NULL && g->last + 1 < g->allocated) {
81281ad8388SMartin Matuska assert(g->node.left == NULL);
81381ad8388SMartin Matuska assert(g->node.right == NULL);
81481ad8388SMartin Matuska
81581ad8388SMartin Matuska index_group *newg = lzma_alloc(sizeof(index_group)
81681ad8388SMartin Matuska + (g->last + 1)
81781ad8388SMartin Matuska * sizeof(index_record),
81881ad8388SMartin Matuska allocator);
81981ad8388SMartin Matuska if (newg == NULL)
82081ad8388SMartin Matuska return LZMA_MEM_ERROR;
82181ad8388SMartin Matuska
82281ad8388SMartin Matuska newg->node = g->node;
82381ad8388SMartin Matuska newg->allocated = g->last + 1;
82481ad8388SMartin Matuska newg->last = g->last;
82581ad8388SMartin Matuska newg->number_base = g->number_base;
82681ad8388SMartin Matuska
82781ad8388SMartin Matuska memcpy(newg->records, g->records, newg->allocated
82881ad8388SMartin Matuska * sizeof(index_record));
82981ad8388SMartin Matuska
83081ad8388SMartin Matuska if (g->node.parent != NULL) {
83181ad8388SMartin Matuska assert(g->node.parent->right == &g->node);
83281ad8388SMartin Matuska g->node.parent->right = &newg->node;
83381ad8388SMartin Matuska }
83481ad8388SMartin Matuska
83581ad8388SMartin Matuska if (s->groups.leftmost == &g->node) {
83681ad8388SMartin Matuska assert(s->groups.root == &g->node);
83781ad8388SMartin Matuska s->groups.leftmost = &newg->node;
83881ad8388SMartin Matuska s->groups.root = &newg->node;
83981ad8388SMartin Matuska }
84081ad8388SMartin Matuska
841a8675d92SXin LI assert(s->groups.rightmost == &g->node);
84281ad8388SMartin Matuska s->groups.rightmost = &newg->node;
84381ad8388SMartin Matuska
84481ad8388SMartin Matuska lzma_free(g, allocator);
8451456f0f9SXin LI
8461456f0f9SXin LI // NOTE: newg isn't leaked here because
8471456f0f9SXin LI // newg == (void *)&newg->node.
84881ad8388SMartin Matuska }
84981ad8388SMartin Matuska }
85081ad8388SMartin Matuska
8519e6bbe47SXin LI // dest->checks includes the check types of all except the last Stream
8529e6bbe47SXin LI // in dest. Set the bit for the check type of the last Stream now so
8539e6bbe47SXin LI // that it won't get lost when Stream(s) from src are appended to dest.
8549e6bbe47SXin LI dest->checks = lzma_index_checks(dest);
8559e6bbe47SXin LI
85681ad8388SMartin Matuska // Add all the Streams from src to dest. Update the base offsets
85781ad8388SMartin Matuska // of each Stream from src.
85881ad8388SMartin Matuska const index_cat_info info = {
85981ad8388SMartin Matuska .uncompressed_size = dest->uncompressed_size,
86081ad8388SMartin Matuska .file_size = dest_file_size,
86181ad8388SMartin Matuska .stream_number_add = dest->streams.count,
86281ad8388SMartin Matuska .block_number_add = dest->record_count,
86381ad8388SMartin Matuska .streams = &dest->streams,
86481ad8388SMartin Matuska };
86581ad8388SMartin Matuska index_cat_helper(&info, (index_stream *)(src->streams.root));
86681ad8388SMartin Matuska
86781ad8388SMartin Matuska // Update info about all the combined Streams.
86881ad8388SMartin Matuska dest->uncompressed_size += src->uncompressed_size;
86981ad8388SMartin Matuska dest->total_size += src->total_size;
87081ad8388SMartin Matuska dest->record_count += src->record_count;
87181ad8388SMartin Matuska dest->index_list_size += src->index_list_size;
8729e6bbe47SXin LI dest->checks |= src->checks;
87381ad8388SMartin Matuska
87481ad8388SMartin Matuska // There's nothing else left in src than the base structure.
87581ad8388SMartin Matuska lzma_free(src, allocator);
87681ad8388SMartin Matuska
87781ad8388SMartin Matuska return LZMA_OK;
87881ad8388SMartin Matuska }
87981ad8388SMartin Matuska
88081ad8388SMartin Matuska
88181ad8388SMartin Matuska /// Duplicate an index_stream.
88281ad8388SMartin Matuska static index_stream *
index_dup_stream(const index_stream * src,const lzma_allocator * allocator)88353200025SRui Paulo index_dup_stream(const index_stream *src, const lzma_allocator *allocator)
88481ad8388SMartin Matuska {
88581ad8388SMartin Matuska // Catch a somewhat theoretical integer overflow.
88681ad8388SMartin Matuska if (src->record_count > PREALLOC_MAX)
88781ad8388SMartin Matuska return NULL;
88881ad8388SMartin Matuska
88981ad8388SMartin Matuska // Allocate and initialize a new Stream.
89081ad8388SMartin Matuska index_stream *dest = index_stream_init(src->node.compressed_base,
89181ad8388SMartin Matuska src->node.uncompressed_base, src->number,
89281ad8388SMartin Matuska src->block_number_base, allocator);
8931456f0f9SXin LI if (dest == NULL)
8941456f0f9SXin LI return NULL;
89581ad8388SMartin Matuska
89681ad8388SMartin Matuska // Copy the overall information.
89781ad8388SMartin Matuska dest->record_count = src->record_count;
89881ad8388SMartin Matuska dest->index_list_size = src->index_list_size;
89981ad8388SMartin Matuska dest->stream_flags = src->stream_flags;
90081ad8388SMartin Matuska dest->stream_padding = src->stream_padding;
90181ad8388SMartin Matuska
9021456f0f9SXin LI // Return if there are no groups to duplicate.
9031456f0f9SXin LI if (src->groups.leftmost == NULL)
9041456f0f9SXin LI return dest;
9051456f0f9SXin LI
90681ad8388SMartin Matuska // Allocate memory for the Records. We put all the Records into
90781ad8388SMartin Matuska // a single group. It's simplest and also tends to make
90881ad8388SMartin Matuska // lzma_index_locate() a little bit faster with very big Indexes.
90981ad8388SMartin Matuska index_group *destg = lzma_alloc(sizeof(index_group)
91081ad8388SMartin Matuska + src->record_count * sizeof(index_record),
91181ad8388SMartin Matuska allocator);
91281ad8388SMartin Matuska if (destg == NULL) {
91381ad8388SMartin Matuska index_stream_end(dest, allocator);
91481ad8388SMartin Matuska return NULL;
91581ad8388SMartin Matuska }
91681ad8388SMartin Matuska
91781ad8388SMartin Matuska // Initialize destg.
91881ad8388SMartin Matuska destg->node.uncompressed_base = 0;
91981ad8388SMartin Matuska destg->node.compressed_base = 0;
92081ad8388SMartin Matuska destg->number_base = 1;
92181ad8388SMartin Matuska destg->allocated = src->record_count;
92281ad8388SMartin Matuska destg->last = src->record_count - 1;
92381ad8388SMartin Matuska
92481ad8388SMartin Matuska // Go through all the groups in src and copy the Records into destg.
92581ad8388SMartin Matuska const index_group *srcg = (const index_group *)(src->groups.leftmost);
92681ad8388SMartin Matuska size_t i = 0;
92781ad8388SMartin Matuska do {
92881ad8388SMartin Matuska memcpy(destg->records + i, srcg->records,
92981ad8388SMartin Matuska (srcg->last + 1) * sizeof(index_record));
93081ad8388SMartin Matuska i += srcg->last + 1;
93181ad8388SMartin Matuska srcg = index_tree_next(&srcg->node);
93281ad8388SMartin Matuska } while (srcg != NULL);
93381ad8388SMartin Matuska
93481ad8388SMartin Matuska assert(i == destg->allocated);
93581ad8388SMartin Matuska
93681ad8388SMartin Matuska // Add the group to the new Stream.
93781ad8388SMartin Matuska index_tree_append(&dest->groups, &destg->node);
93881ad8388SMartin Matuska
93981ad8388SMartin Matuska return dest;
94081ad8388SMartin Matuska }
94181ad8388SMartin Matuska
94281ad8388SMartin Matuska
94381ad8388SMartin Matuska extern LZMA_API(lzma_index *)
lzma_index_dup(const lzma_index * src,const lzma_allocator * allocator)94453200025SRui Paulo lzma_index_dup(const lzma_index *src, const lzma_allocator *allocator)
94581ad8388SMartin Matuska {
94681ad8388SMartin Matuska // Allocate the base structure (no initial Stream).
94781ad8388SMartin Matuska lzma_index *dest = index_init_plain(allocator);
94881ad8388SMartin Matuska if (dest == NULL)
94981ad8388SMartin Matuska return NULL;
95081ad8388SMartin Matuska
95181ad8388SMartin Matuska // Copy the totals.
95281ad8388SMartin Matuska dest->uncompressed_size = src->uncompressed_size;
95381ad8388SMartin Matuska dest->total_size = src->total_size;
95481ad8388SMartin Matuska dest->record_count = src->record_count;
95581ad8388SMartin Matuska dest->index_list_size = src->index_list_size;
95681ad8388SMartin Matuska
95781ad8388SMartin Matuska // Copy the Streams and the groups in them.
95881ad8388SMartin Matuska const index_stream *srcstream
95981ad8388SMartin Matuska = (const index_stream *)(src->streams.leftmost);
96081ad8388SMartin Matuska do {
96181ad8388SMartin Matuska index_stream *deststream = index_dup_stream(
96281ad8388SMartin Matuska srcstream, allocator);
96381ad8388SMartin Matuska if (deststream == NULL) {
96481ad8388SMartin Matuska lzma_index_end(dest, allocator);
96581ad8388SMartin Matuska return NULL;
96681ad8388SMartin Matuska }
96781ad8388SMartin Matuska
96881ad8388SMartin Matuska index_tree_append(&dest->streams, &deststream->node);
96981ad8388SMartin Matuska
97081ad8388SMartin Matuska srcstream = index_tree_next(&srcstream->node);
97181ad8388SMartin Matuska } while (srcstream != NULL);
97281ad8388SMartin Matuska
97381ad8388SMartin Matuska return dest;
97481ad8388SMartin Matuska }
97581ad8388SMartin Matuska
97681ad8388SMartin Matuska
97781ad8388SMartin Matuska /// Indexing for lzma_index_iter.internal[]
97881ad8388SMartin Matuska enum {
97981ad8388SMartin Matuska ITER_INDEX,
98081ad8388SMartin Matuska ITER_STREAM,
98181ad8388SMartin Matuska ITER_GROUP,
98281ad8388SMartin Matuska ITER_RECORD,
98381ad8388SMartin Matuska ITER_METHOD,
98481ad8388SMartin Matuska };
98581ad8388SMartin Matuska
98681ad8388SMartin Matuska
98781ad8388SMartin Matuska /// Values for lzma_index_iter.internal[ITER_METHOD].s
98881ad8388SMartin Matuska enum {
98981ad8388SMartin Matuska ITER_METHOD_NORMAL,
99081ad8388SMartin Matuska ITER_METHOD_NEXT,
99181ad8388SMartin Matuska ITER_METHOD_LEFTMOST,
99281ad8388SMartin Matuska };
99381ad8388SMartin Matuska
99481ad8388SMartin Matuska
99581ad8388SMartin Matuska static void
iter_set_info(lzma_index_iter * iter)99681ad8388SMartin Matuska iter_set_info(lzma_index_iter *iter)
99781ad8388SMartin Matuska {
99881ad8388SMartin Matuska const lzma_index *i = iter->internal[ITER_INDEX].p;
99981ad8388SMartin Matuska const index_stream *stream = iter->internal[ITER_STREAM].p;
100081ad8388SMartin Matuska const index_group *group = iter->internal[ITER_GROUP].p;
100181ad8388SMartin Matuska const size_t record = iter->internal[ITER_RECORD].s;
100281ad8388SMartin Matuska
100381ad8388SMartin Matuska // lzma_index_iter.internal must not contain a pointer to the last
100481ad8388SMartin Matuska // group in the index, because that may be reallocated by
100581ad8388SMartin Matuska // lzma_index_cat().
100681ad8388SMartin Matuska if (group == NULL) {
100781ad8388SMartin Matuska // There are no groups.
100881ad8388SMartin Matuska assert(stream->groups.root == NULL);
100981ad8388SMartin Matuska iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
101081ad8388SMartin Matuska
101181ad8388SMartin Matuska } else if (i->streams.rightmost != &stream->node
101281ad8388SMartin Matuska || stream->groups.rightmost != &group->node) {
101381ad8388SMartin Matuska // The group is not not the last group in the index.
101481ad8388SMartin Matuska iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
101581ad8388SMartin Matuska
101681ad8388SMartin Matuska } else if (stream->groups.leftmost != &group->node) {
101781ad8388SMartin Matuska // The group isn't the only group in the Stream, thus we
101881ad8388SMartin Matuska // know that it must have a parent group i.e. it's not
101981ad8388SMartin Matuska // the root node.
102081ad8388SMartin Matuska assert(stream->groups.root != &group->node);
102181ad8388SMartin Matuska assert(group->node.parent->right == &group->node);
102281ad8388SMartin Matuska iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT;
102381ad8388SMartin Matuska iter->internal[ITER_GROUP].p = group->node.parent;
102481ad8388SMartin Matuska
102581ad8388SMartin Matuska } else {
102681ad8388SMartin Matuska // The Stream has only one group.
102781ad8388SMartin Matuska assert(stream->groups.root == &group->node);
102881ad8388SMartin Matuska assert(group->node.parent == NULL);
102981ad8388SMartin Matuska iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
103081ad8388SMartin Matuska iter->internal[ITER_GROUP].p = NULL;
103181ad8388SMartin Matuska }
103281ad8388SMartin Matuska
1033fe50a38eSXin LI // NOTE: lzma_index_iter.stream.number is lzma_vli but we use uint32_t
1034fe50a38eSXin LI // internally.
103581ad8388SMartin Matuska iter->stream.number = stream->number;
103681ad8388SMartin Matuska iter->stream.block_count = stream->record_count;
103781ad8388SMartin Matuska iter->stream.compressed_offset = stream->node.compressed_base;
103881ad8388SMartin Matuska iter->stream.uncompressed_offset = stream->node.uncompressed_base;
103981ad8388SMartin Matuska
104081ad8388SMartin Matuska // iter->stream.flags will be NULL if the Stream Flags haven't been
104181ad8388SMartin Matuska // set with lzma_index_stream_flags().
104281ad8388SMartin Matuska iter->stream.flags = stream->stream_flags.version == UINT32_MAX
104381ad8388SMartin Matuska ? NULL : &stream->stream_flags;
104481ad8388SMartin Matuska iter->stream.padding = stream->stream_padding;
104581ad8388SMartin Matuska
104681ad8388SMartin Matuska if (stream->groups.rightmost == NULL) {
104781ad8388SMartin Matuska // Stream has no Blocks.
104881ad8388SMartin Matuska iter->stream.compressed_size = index_size(0, 0)
104981ad8388SMartin Matuska + 2 * LZMA_STREAM_HEADER_SIZE;
105081ad8388SMartin Matuska iter->stream.uncompressed_size = 0;
105181ad8388SMartin Matuska } else {
105281ad8388SMartin Matuska const index_group *g = (const index_group *)(
105381ad8388SMartin Matuska stream->groups.rightmost);
105481ad8388SMartin Matuska
105581ad8388SMartin Matuska // Stream Header + Stream Footer + Index + Blocks
105681ad8388SMartin Matuska iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE
105781ad8388SMartin Matuska + index_size(stream->record_count,
105881ad8388SMartin Matuska stream->index_list_size)
105981ad8388SMartin Matuska + vli_ceil4(g->records[g->last].unpadded_sum);
106081ad8388SMartin Matuska iter->stream.uncompressed_size
106181ad8388SMartin Matuska = g->records[g->last].uncompressed_sum;
106281ad8388SMartin Matuska }
106381ad8388SMartin Matuska
106481ad8388SMartin Matuska if (group != NULL) {
106581ad8388SMartin Matuska iter->block.number_in_stream = group->number_base + record;
106681ad8388SMartin Matuska iter->block.number_in_file = iter->block.number_in_stream
106781ad8388SMartin Matuska + stream->block_number_base;
106881ad8388SMartin Matuska
106981ad8388SMartin Matuska iter->block.compressed_stream_offset
107081ad8388SMartin Matuska = record == 0 ? group->node.compressed_base
107181ad8388SMartin Matuska : vli_ceil4(group->records[
107281ad8388SMartin Matuska record - 1].unpadded_sum);
107381ad8388SMartin Matuska iter->block.uncompressed_stream_offset
107481ad8388SMartin Matuska = record == 0 ? group->node.uncompressed_base
107581ad8388SMartin Matuska : group->records[record - 1].uncompressed_sum;
107681ad8388SMartin Matuska
107781ad8388SMartin Matuska iter->block.uncompressed_size
107881ad8388SMartin Matuska = group->records[record].uncompressed_sum
107981ad8388SMartin Matuska - iter->block.uncompressed_stream_offset;
108081ad8388SMartin Matuska iter->block.unpadded_size
108181ad8388SMartin Matuska = group->records[record].unpadded_sum
108281ad8388SMartin Matuska - iter->block.compressed_stream_offset;
108381ad8388SMartin Matuska iter->block.total_size = vli_ceil4(iter->block.unpadded_size);
108481ad8388SMartin Matuska
108581ad8388SMartin Matuska iter->block.compressed_stream_offset
108681ad8388SMartin Matuska += LZMA_STREAM_HEADER_SIZE;
108781ad8388SMartin Matuska
108881ad8388SMartin Matuska iter->block.compressed_file_offset
108981ad8388SMartin Matuska = iter->block.compressed_stream_offset
109081ad8388SMartin Matuska + iter->stream.compressed_offset;
109181ad8388SMartin Matuska iter->block.uncompressed_file_offset
109281ad8388SMartin Matuska = iter->block.uncompressed_stream_offset
109381ad8388SMartin Matuska + iter->stream.uncompressed_offset;
109481ad8388SMartin Matuska }
109581ad8388SMartin Matuska
109681ad8388SMartin Matuska return;
109781ad8388SMartin Matuska }
109881ad8388SMartin Matuska
109981ad8388SMartin Matuska
110081ad8388SMartin Matuska extern LZMA_API(void)
lzma_index_iter_init(lzma_index_iter * iter,const lzma_index * i)110181ad8388SMartin Matuska lzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i)
110281ad8388SMartin Matuska {
110381ad8388SMartin Matuska iter->internal[ITER_INDEX].p = i;
110481ad8388SMartin Matuska lzma_index_iter_rewind(iter);
110581ad8388SMartin Matuska return;
110681ad8388SMartin Matuska }
110781ad8388SMartin Matuska
110881ad8388SMartin Matuska
110981ad8388SMartin Matuska extern LZMA_API(void)
lzma_index_iter_rewind(lzma_index_iter * iter)111081ad8388SMartin Matuska lzma_index_iter_rewind(lzma_index_iter *iter)
111181ad8388SMartin Matuska {
111281ad8388SMartin Matuska iter->internal[ITER_STREAM].p = NULL;
111381ad8388SMartin Matuska iter->internal[ITER_GROUP].p = NULL;
111481ad8388SMartin Matuska iter->internal[ITER_RECORD].s = 0;
111581ad8388SMartin Matuska iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
111681ad8388SMartin Matuska return;
111781ad8388SMartin Matuska }
111881ad8388SMartin Matuska
111981ad8388SMartin Matuska
112081ad8388SMartin Matuska extern LZMA_API(lzma_bool)
lzma_index_iter_next(lzma_index_iter * iter,lzma_index_iter_mode mode)112181ad8388SMartin Matuska lzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode)
112281ad8388SMartin Matuska {
112381ad8388SMartin Matuska // Catch unsupported mode values.
112481ad8388SMartin Matuska if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK)
112581ad8388SMartin Matuska return true;
112681ad8388SMartin Matuska
112781ad8388SMartin Matuska const lzma_index *i = iter->internal[ITER_INDEX].p;
112881ad8388SMartin Matuska const index_stream *stream = iter->internal[ITER_STREAM].p;
112981ad8388SMartin Matuska const index_group *group = NULL;
113081ad8388SMartin Matuska size_t record = iter->internal[ITER_RECORD].s;
113181ad8388SMartin Matuska
113281ad8388SMartin Matuska // If we are being asked for the next Stream, leave group to NULL
113381ad8388SMartin Matuska // so that the rest of the this function thinks that this Stream
113481ad8388SMartin Matuska // has no groups and will thus go to the next Stream.
113581ad8388SMartin Matuska if (mode != LZMA_INDEX_ITER_STREAM) {
113681ad8388SMartin Matuska // Get the pointer to the current group. See iter_set_inf()
113781ad8388SMartin Matuska // for explanation.
113881ad8388SMartin Matuska switch (iter->internal[ITER_METHOD].s) {
113981ad8388SMartin Matuska case ITER_METHOD_NORMAL:
114081ad8388SMartin Matuska group = iter->internal[ITER_GROUP].p;
114181ad8388SMartin Matuska break;
114281ad8388SMartin Matuska
114381ad8388SMartin Matuska case ITER_METHOD_NEXT:
114481ad8388SMartin Matuska group = index_tree_next(iter->internal[ITER_GROUP].p);
114581ad8388SMartin Matuska break;
114681ad8388SMartin Matuska
114781ad8388SMartin Matuska case ITER_METHOD_LEFTMOST:
114881ad8388SMartin Matuska group = (const index_group *)(
114981ad8388SMartin Matuska stream->groups.leftmost);
115081ad8388SMartin Matuska break;
115181ad8388SMartin Matuska }
115281ad8388SMartin Matuska }
115381ad8388SMartin Matuska
115481ad8388SMartin Matuska again:
115581ad8388SMartin Matuska if (stream == NULL) {
115681ad8388SMartin Matuska // We at the beginning of the lzma_index.
115781ad8388SMartin Matuska // Locate the first Stream.
115881ad8388SMartin Matuska stream = (const index_stream *)(i->streams.leftmost);
115981ad8388SMartin Matuska if (mode >= LZMA_INDEX_ITER_BLOCK) {
116081ad8388SMartin Matuska // Since we are being asked to return information
116181ad8388SMartin Matuska // about the first a Block, skip Streams that have
116281ad8388SMartin Matuska // no Blocks.
116381ad8388SMartin Matuska while (stream->groups.leftmost == NULL) {
116481ad8388SMartin Matuska stream = index_tree_next(&stream->node);
116581ad8388SMartin Matuska if (stream == NULL)
116681ad8388SMartin Matuska return true;
116781ad8388SMartin Matuska }
116881ad8388SMartin Matuska }
116981ad8388SMartin Matuska
117081ad8388SMartin Matuska // Start from the first Record in the Stream.
117181ad8388SMartin Matuska group = (const index_group *)(stream->groups.leftmost);
117281ad8388SMartin Matuska record = 0;
117381ad8388SMartin Matuska
117481ad8388SMartin Matuska } else if (group != NULL && record < group->last) {
117581ad8388SMartin Matuska // The next Record is in the same group.
117681ad8388SMartin Matuska ++record;
117781ad8388SMartin Matuska
117881ad8388SMartin Matuska } else {
117981ad8388SMartin Matuska // This group has no more Records or this Stream has
118081ad8388SMartin Matuska // no Blocks at all.
118181ad8388SMartin Matuska record = 0;
118281ad8388SMartin Matuska
118381ad8388SMartin Matuska // If group is not NULL, this Stream has at least one Block
118481ad8388SMartin Matuska // and thus at least one group. Find the next group.
118581ad8388SMartin Matuska if (group != NULL)
118681ad8388SMartin Matuska group = index_tree_next(&group->node);
118781ad8388SMartin Matuska
118881ad8388SMartin Matuska if (group == NULL) {
118981ad8388SMartin Matuska // This Stream has no more Records. Find the next
119081ad8388SMartin Matuska // Stream. If we are being asked to return information
119181ad8388SMartin Matuska // about a Block, we skip empty Streams.
119281ad8388SMartin Matuska do {
119381ad8388SMartin Matuska stream = index_tree_next(&stream->node);
119481ad8388SMartin Matuska if (stream == NULL)
119581ad8388SMartin Matuska return true;
119681ad8388SMartin Matuska } while (mode >= LZMA_INDEX_ITER_BLOCK
119781ad8388SMartin Matuska && stream->groups.leftmost == NULL);
119881ad8388SMartin Matuska
119981ad8388SMartin Matuska group = (const index_group *)(
120081ad8388SMartin Matuska stream->groups.leftmost);
120181ad8388SMartin Matuska }
120281ad8388SMartin Matuska }
120381ad8388SMartin Matuska
120481ad8388SMartin Matuska if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) {
120581ad8388SMartin Matuska // We need to look for the next Block again if this Block
120681ad8388SMartin Matuska // is empty.
120781ad8388SMartin Matuska if (record == 0) {
120881ad8388SMartin Matuska if (group->node.uncompressed_base
120981ad8388SMartin Matuska == group->records[0].uncompressed_sum)
121081ad8388SMartin Matuska goto again;
121181ad8388SMartin Matuska } else if (group->records[record - 1].uncompressed_sum
121281ad8388SMartin Matuska == group->records[record].uncompressed_sum) {
121381ad8388SMartin Matuska goto again;
121481ad8388SMartin Matuska }
121581ad8388SMartin Matuska }
121681ad8388SMartin Matuska
121781ad8388SMartin Matuska iter->internal[ITER_STREAM].p = stream;
121881ad8388SMartin Matuska iter->internal[ITER_GROUP].p = group;
121981ad8388SMartin Matuska iter->internal[ITER_RECORD].s = record;
122081ad8388SMartin Matuska
122181ad8388SMartin Matuska iter_set_info(iter);
122281ad8388SMartin Matuska
122381ad8388SMartin Matuska return false;
122481ad8388SMartin Matuska }
122581ad8388SMartin Matuska
122681ad8388SMartin Matuska
122781ad8388SMartin Matuska extern LZMA_API(lzma_bool)
lzma_index_iter_locate(lzma_index_iter * iter,lzma_vli target)122881ad8388SMartin Matuska lzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target)
122981ad8388SMartin Matuska {
123081ad8388SMartin Matuska const lzma_index *i = iter->internal[ITER_INDEX].p;
123181ad8388SMartin Matuska
123281ad8388SMartin Matuska // If the target is past the end of the file, return immediately.
123381ad8388SMartin Matuska if (i->uncompressed_size <= target)
123481ad8388SMartin Matuska return true;
123581ad8388SMartin Matuska
123681ad8388SMartin Matuska // Locate the Stream containing the target offset.
123781ad8388SMartin Matuska const index_stream *stream = index_tree_locate(&i->streams, target);
123881ad8388SMartin Matuska assert(stream != NULL);
123981ad8388SMartin Matuska target -= stream->node.uncompressed_base;
124081ad8388SMartin Matuska
124181ad8388SMartin Matuska // Locate the group containing the target offset.
124281ad8388SMartin Matuska const index_group *group = index_tree_locate(&stream->groups, target);
124381ad8388SMartin Matuska assert(group != NULL);
124481ad8388SMartin Matuska
124581ad8388SMartin Matuska // Use binary search to locate the exact Record. It is the first
124681ad8388SMartin Matuska // Record whose uncompressed_sum is greater than target.
12479e6bbe47SXin LI // This is because we want the rightmost Record that fulfills the
124881ad8388SMartin Matuska // search criterion. It is possible that there are empty Blocks;
124981ad8388SMartin Matuska // we don't want to return them.
125081ad8388SMartin Matuska size_t left = 0;
125181ad8388SMartin Matuska size_t right = group->last;
125281ad8388SMartin Matuska
125381ad8388SMartin Matuska while (left < right) {
125481ad8388SMartin Matuska const size_t pos = left + (right - left) / 2;
125581ad8388SMartin Matuska if (group->records[pos].uncompressed_sum <= target)
125681ad8388SMartin Matuska left = pos + 1;
125781ad8388SMartin Matuska else
125881ad8388SMartin Matuska right = pos;
125981ad8388SMartin Matuska }
126081ad8388SMartin Matuska
126181ad8388SMartin Matuska iter->internal[ITER_STREAM].p = stream;
126281ad8388SMartin Matuska iter->internal[ITER_GROUP].p = group;
126381ad8388SMartin Matuska iter->internal[ITER_RECORD].s = left;
126481ad8388SMartin Matuska
126581ad8388SMartin Matuska iter_set_info(iter);
126681ad8388SMartin Matuska
126781ad8388SMartin Matuska return false;
126881ad8388SMartin Matuska }
1269