12940b44dSPeter Avalos ///////////////////////////////////////////////////////////////////////////////
22940b44dSPeter Avalos //
32940b44dSPeter Avalos /// \file index.c
42940b44dSPeter Avalos /// \brief Handling of .xz Indexes and some other Stream information
52940b44dSPeter Avalos //
62940b44dSPeter Avalos // Author: Lasse Collin
72940b44dSPeter Avalos //
82940b44dSPeter Avalos // This file has been put into the public domain.
92940b44dSPeter Avalos // You can do whatever you want with this file.
102940b44dSPeter Avalos //
112940b44dSPeter Avalos ///////////////////////////////////////////////////////////////////////////////
122940b44dSPeter Avalos
132940b44dSPeter Avalos #include "index.h"
142940b44dSPeter Avalos #include "stream_flags_common.h"
152940b44dSPeter Avalos
162940b44dSPeter Avalos
172940b44dSPeter Avalos /// \brief How many Records to allocate at once
182940b44dSPeter Avalos ///
192940b44dSPeter Avalos /// This should be big enough to avoid making lots of tiny allocations
202940b44dSPeter Avalos /// but small enough to avoid too much unused memory at once.
212940b44dSPeter Avalos #define INDEX_GROUP_SIZE 512
222940b44dSPeter Avalos
232940b44dSPeter Avalos
242940b44dSPeter Avalos /// \brief How many Records can be allocated at once at maximum
252940b44dSPeter Avalos #define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))
262940b44dSPeter Avalos
272940b44dSPeter Avalos
282940b44dSPeter Avalos /// \brief Base structure for index_stream and index_group structures
292940b44dSPeter Avalos typedef struct index_tree_node_s index_tree_node;
302940b44dSPeter Avalos struct index_tree_node_s {
312940b44dSPeter Avalos /// Uncompressed start offset of this Stream (relative to the
322940b44dSPeter Avalos /// beginning of the file) or Block (relative to the beginning
332940b44dSPeter Avalos /// of the Stream)
342940b44dSPeter Avalos lzma_vli uncompressed_base;
352940b44dSPeter Avalos
362940b44dSPeter Avalos /// Compressed start offset of this Stream or Block
372940b44dSPeter Avalos lzma_vli compressed_base;
382940b44dSPeter Avalos
392940b44dSPeter Avalos index_tree_node *parent;
402940b44dSPeter Avalos index_tree_node *left;
412940b44dSPeter Avalos index_tree_node *right;
422940b44dSPeter Avalos };
432940b44dSPeter Avalos
442940b44dSPeter Avalos
452940b44dSPeter Avalos /// \brief AVL tree to hold index_stream or index_group structures
462940b44dSPeter Avalos typedef struct {
472940b44dSPeter Avalos /// Root node
482940b44dSPeter Avalos index_tree_node *root;
492940b44dSPeter Avalos
502940b44dSPeter Avalos /// Leftmost node. Since the tree will be filled sequentially,
512940b44dSPeter Avalos /// this won't change after the first node has been added to
522940b44dSPeter Avalos /// the tree.
532940b44dSPeter Avalos index_tree_node *leftmost;
542940b44dSPeter Avalos
552940b44dSPeter Avalos /// The rightmost node in the tree. Since the tree is filled
562940b44dSPeter Avalos /// sequentially, this is always the node where to add the new data.
572940b44dSPeter Avalos index_tree_node *rightmost;
582940b44dSPeter Avalos
592940b44dSPeter Avalos /// Number of nodes in the tree
602940b44dSPeter Avalos uint32_t count;
612940b44dSPeter Avalos
622940b44dSPeter Avalos } index_tree;
632940b44dSPeter Avalos
642940b44dSPeter Avalos
652940b44dSPeter Avalos typedef struct {
662940b44dSPeter Avalos lzma_vli uncompressed_sum;
672940b44dSPeter Avalos lzma_vli unpadded_sum;
682940b44dSPeter Avalos } index_record;
692940b44dSPeter Avalos
702940b44dSPeter Avalos
712940b44dSPeter Avalos typedef struct {
722940b44dSPeter Avalos /// Every Record group is part of index_stream.groups tree.
732940b44dSPeter Avalos index_tree_node node;
742940b44dSPeter Avalos
752940b44dSPeter Avalos /// Number of Blocks in this Stream before this group.
762940b44dSPeter Avalos lzma_vli number_base;
772940b44dSPeter Avalos
782940b44dSPeter Avalos /// Number of Records that can be put in records[].
792940b44dSPeter Avalos size_t allocated;
802940b44dSPeter Avalos
812940b44dSPeter Avalos /// Index of the last Record in use.
822940b44dSPeter Avalos size_t last;
832940b44dSPeter Avalos
842940b44dSPeter Avalos /// The sizes in this array are stored as cumulative sums relative
852940b44dSPeter Avalos /// to the beginning of the Stream. This makes it possible to
862940b44dSPeter Avalos /// use binary search in lzma_index_locate().
872940b44dSPeter Avalos ///
882940b44dSPeter Avalos /// Note that the cumulative summing is done specially for
892940b44dSPeter Avalos /// unpadded_sum: The previous value is rounded up to the next
902940b44dSPeter Avalos /// multiple of four before adding the Unpadded Size of the new
912940b44dSPeter Avalos /// Block. The total encoded size of the Blocks in the Stream
922940b44dSPeter Avalos /// is records[last].unpadded_sum in the last Record group of
932940b44dSPeter Avalos /// the Stream.
942940b44dSPeter Avalos ///
952940b44dSPeter Avalos /// For example, if the Unpadded Sizes are 39, 57, and 81, the
962940b44dSPeter Avalos /// stored values are 39, 97 (40 + 57), and 181 (100 + 181).
972940b44dSPeter Avalos /// The total encoded size of these Blocks is 184.
982940b44dSPeter Avalos ///
992940b44dSPeter Avalos /// This is a flexible array, because it makes easy to optimize
1002940b44dSPeter Avalos /// memory usage in case someone concatenates many Streams that
1012940b44dSPeter Avalos /// have only one or few Blocks.
1022940b44dSPeter Avalos index_record records[];
1032940b44dSPeter Avalos
1042940b44dSPeter Avalos } index_group;
1052940b44dSPeter Avalos
1062940b44dSPeter Avalos
1072940b44dSPeter Avalos typedef struct {
108*e151908bSDaniel Fojt /// Every index_stream is a node in the tree of Streams.
1092940b44dSPeter Avalos index_tree_node node;
1102940b44dSPeter Avalos
1112940b44dSPeter Avalos /// Number of this Stream (first one is 1)
1122940b44dSPeter Avalos uint32_t number;
1132940b44dSPeter Avalos
1142940b44dSPeter Avalos /// Total number of Blocks before this Stream
1152940b44dSPeter Avalos lzma_vli block_number_base;
1162940b44dSPeter Avalos
1172940b44dSPeter Avalos /// Record groups of this Stream are stored in a tree.
1182940b44dSPeter Avalos /// It's a T-tree with AVL-tree balancing. There are
1192940b44dSPeter Avalos /// INDEX_GROUP_SIZE Records per node by default.
1202940b44dSPeter Avalos /// This keeps the number of memory allocations reasonable
1212940b44dSPeter Avalos /// and finding a Record is fast.
1222940b44dSPeter Avalos index_tree groups;
1232940b44dSPeter Avalos
1242940b44dSPeter Avalos /// Number of Records in this Stream
1252940b44dSPeter Avalos lzma_vli record_count;
1262940b44dSPeter Avalos
1272940b44dSPeter Avalos /// Size of the List of Records field in this Stream. This is used
1282940b44dSPeter Avalos /// together with record_count to calculate the size of the Index
1292940b44dSPeter Avalos /// field and thus the total size of the Stream.
1302940b44dSPeter Avalos lzma_vli index_list_size;
1312940b44dSPeter Avalos
1322940b44dSPeter Avalos /// Stream Flags of this Stream. This is meaningful only if
1332940b44dSPeter Avalos /// the Stream Flags have been told us with lzma_index_stream_flags().
1342940b44dSPeter Avalos /// Initially stream_flags.version is set to UINT32_MAX to indicate
1352940b44dSPeter Avalos /// that the Stream Flags are unknown.
1362940b44dSPeter Avalos lzma_stream_flags stream_flags;
1372940b44dSPeter Avalos
1382940b44dSPeter Avalos /// Amount of Stream Padding after this Stream. This defaults to
1392940b44dSPeter Avalos /// zero and can be set with lzma_index_stream_padding().
1402940b44dSPeter Avalos lzma_vli stream_padding;
1412940b44dSPeter Avalos
1422940b44dSPeter Avalos } index_stream;
1432940b44dSPeter Avalos
1442940b44dSPeter Avalos
1452940b44dSPeter Avalos struct lzma_index_s {
1462940b44dSPeter Avalos /// AVL-tree containing the Stream(s). Often there is just one
1472940b44dSPeter Avalos /// Stream, but using a tree keeps lookups fast even when there
1482940b44dSPeter Avalos /// are many concatenated Streams.
1492940b44dSPeter Avalos index_tree streams;
1502940b44dSPeter Avalos
1512940b44dSPeter Avalos /// Uncompressed size of all the Blocks in the Stream(s)
1522940b44dSPeter Avalos lzma_vli uncompressed_size;
1532940b44dSPeter Avalos
1542940b44dSPeter Avalos /// Total size of all the Blocks in the Stream(s)
1552940b44dSPeter Avalos lzma_vli total_size;
1562940b44dSPeter Avalos
1572940b44dSPeter Avalos /// Total number of Records in all Streams in this lzma_index
1582940b44dSPeter Avalos lzma_vli record_count;
1592940b44dSPeter Avalos
1602940b44dSPeter Avalos /// Size of the List of Records field if all the Streams in this
1612940b44dSPeter Avalos /// lzma_index were packed into a single Stream (makes it simpler to
1622940b44dSPeter Avalos /// take many .xz files and combine them into a single Stream).
1632940b44dSPeter Avalos ///
1642940b44dSPeter Avalos /// This value together with record_count is needed to calculate
1652940b44dSPeter Avalos /// Backward Size that is stored into Stream Footer.
1662940b44dSPeter Avalos lzma_vli index_list_size;
1672940b44dSPeter Avalos
1682940b44dSPeter Avalos /// How many Records to allocate at once in lzma_index_append().
169*e151908bSDaniel Fojt /// This defaults to INDEX_GROUP_SIZE but can be overridden with
1702940b44dSPeter Avalos /// lzma_index_prealloc().
1712940b44dSPeter Avalos size_t prealloc;
1722940b44dSPeter Avalos
1732940b44dSPeter Avalos /// Bitmask indicating what integrity check types have been used
1742940b44dSPeter Avalos /// as set by lzma_index_stream_flags(). The bit of the last Stream
1752940b44dSPeter Avalos /// is not included here, since it is possible to change it by
1762940b44dSPeter Avalos /// calling lzma_index_stream_flags() again.
1772940b44dSPeter Avalos uint32_t checks;
1782940b44dSPeter Avalos };
1792940b44dSPeter Avalos
1802940b44dSPeter Avalos
1812940b44dSPeter Avalos static void
index_tree_init(index_tree * tree)1822940b44dSPeter Avalos index_tree_init(index_tree *tree)
1832940b44dSPeter Avalos {
1842940b44dSPeter Avalos tree->root = NULL;
1852940b44dSPeter Avalos tree->leftmost = NULL;
1862940b44dSPeter Avalos tree->rightmost = NULL;
1872940b44dSPeter Avalos tree->count = 0;
1882940b44dSPeter Avalos return;
1892940b44dSPeter Avalos }
1902940b44dSPeter Avalos
1912940b44dSPeter Avalos
1922940b44dSPeter Avalos /// Helper for index_tree_end()
1932940b44dSPeter Avalos static void
index_tree_node_end(index_tree_node * node,const lzma_allocator * allocator,void (* free_func)(void * node,const lzma_allocator * allocator))19415ab8c86SJohn Marino index_tree_node_end(index_tree_node *node, const lzma_allocator *allocator,
19515ab8c86SJohn Marino void (*free_func)(void *node, const lzma_allocator *allocator))
1962940b44dSPeter Avalos {
1972940b44dSPeter Avalos // The tree won't ever be very huge, so recursion should be fine.
1982940b44dSPeter Avalos // 20 levels in the tree is likely quite a lot already in practice.
1992940b44dSPeter Avalos if (node->left != NULL)
2002940b44dSPeter Avalos index_tree_node_end(node->left, allocator, free_func);
2012940b44dSPeter Avalos
2022940b44dSPeter Avalos if (node->right != NULL)
2032940b44dSPeter Avalos index_tree_node_end(node->right, allocator, free_func);
2042940b44dSPeter Avalos
2052940b44dSPeter Avalos free_func(node, allocator);
2062940b44dSPeter Avalos return;
2072940b44dSPeter Avalos }
2082940b44dSPeter Avalos
2092940b44dSPeter Avalos
21046a2189dSzrj /// Free the memory allocated for a tree. Each node is freed using the
21146a2189dSzrj /// given free_func which is either &lzma_free or &index_stream_end.
21246a2189dSzrj /// The latter is used to free the Record groups from each index_stream
21346a2189dSzrj /// before freeing the index_stream itself.
2142940b44dSPeter Avalos static void
index_tree_end(index_tree * tree,const lzma_allocator * allocator,void (* free_func)(void * node,const lzma_allocator * allocator))21515ab8c86SJohn Marino index_tree_end(index_tree *tree, const lzma_allocator *allocator,
21615ab8c86SJohn Marino void (*free_func)(void *node, const lzma_allocator *allocator))
2172940b44dSPeter Avalos {
21846a2189dSzrj assert(free_func != NULL);
21946a2189dSzrj
2202940b44dSPeter Avalos if (tree->root != NULL)
2212940b44dSPeter Avalos index_tree_node_end(tree->root, allocator, free_func);
2222940b44dSPeter Avalos
2232940b44dSPeter Avalos return;
2242940b44dSPeter Avalos }
2252940b44dSPeter Avalos
2262940b44dSPeter Avalos
2272940b44dSPeter Avalos /// Add a new node to the tree. node->uncompressed_base and
2282940b44dSPeter Avalos /// node->compressed_base must have been set by the caller already.
2292940b44dSPeter Avalos static void
index_tree_append(index_tree * tree,index_tree_node * node)2302940b44dSPeter Avalos index_tree_append(index_tree *tree, index_tree_node *node)
2312940b44dSPeter Avalos {
2322940b44dSPeter Avalos node->parent = tree->rightmost;
2332940b44dSPeter Avalos node->left = NULL;
2342940b44dSPeter Avalos node->right = NULL;
2352940b44dSPeter Avalos
2362940b44dSPeter Avalos ++tree->count;
2372940b44dSPeter Avalos
2382940b44dSPeter Avalos // Handle the special case of adding the first node.
2392940b44dSPeter Avalos if (tree->root == NULL) {
2402940b44dSPeter Avalos tree->root = node;
2412940b44dSPeter Avalos tree->leftmost = node;
2422940b44dSPeter Avalos tree->rightmost = node;
2432940b44dSPeter Avalos return;
2442940b44dSPeter Avalos }
2452940b44dSPeter Avalos
2462940b44dSPeter Avalos // The tree is always filled sequentially.
2472940b44dSPeter Avalos assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);
2482940b44dSPeter Avalos assert(tree->rightmost->compressed_base < node->compressed_base);
2492940b44dSPeter Avalos
2502940b44dSPeter Avalos // Add the new node after the rightmost node. It's the correct
2512940b44dSPeter Avalos // place due to the reason above.
2522940b44dSPeter Avalos tree->rightmost->right = node;
2532940b44dSPeter Avalos tree->rightmost = node;
2542940b44dSPeter Avalos
2552940b44dSPeter Avalos // Balance the AVL-tree if needed. We don't need to keep the balance
2562940b44dSPeter Avalos // factors in nodes, because we always fill the tree sequentially,
2572940b44dSPeter Avalos // and thus know the state of the tree just by looking at the node
2582940b44dSPeter Avalos // count. From the node count we can calculate how many steps to go
2592940b44dSPeter Avalos // up in the tree to find the rotation root.
2602940b44dSPeter Avalos uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count));
2612940b44dSPeter Avalos if (up != 0) {
2622940b44dSPeter Avalos // Locate the root node for the rotation.
2632940b44dSPeter Avalos up = ctz32(tree->count) + 2;
2642940b44dSPeter Avalos do {
2652940b44dSPeter Avalos node = node->parent;
2662940b44dSPeter Avalos } while (--up > 0);
2672940b44dSPeter Avalos
2682940b44dSPeter Avalos // Rotate left using node as the rotation root.
2692940b44dSPeter Avalos index_tree_node *pivot = node->right;
2702940b44dSPeter Avalos
2712940b44dSPeter Avalos if (node->parent == NULL) {
2722940b44dSPeter Avalos tree->root = pivot;
2732940b44dSPeter Avalos } else {
2742940b44dSPeter Avalos assert(node->parent->right == node);
2752940b44dSPeter Avalos node->parent->right = pivot;
2762940b44dSPeter Avalos }
2772940b44dSPeter Avalos
2782940b44dSPeter Avalos pivot->parent = node->parent;
2792940b44dSPeter Avalos
2802940b44dSPeter Avalos node->right = pivot->left;
2812940b44dSPeter Avalos if (node->right != NULL)
2822940b44dSPeter Avalos node->right->parent = node;
2832940b44dSPeter Avalos
2842940b44dSPeter Avalos pivot->left = node;
2852940b44dSPeter Avalos node->parent = pivot;
2862940b44dSPeter Avalos }
2872940b44dSPeter Avalos
2882940b44dSPeter Avalos return;
2892940b44dSPeter Avalos }
2902940b44dSPeter Avalos
2912940b44dSPeter Avalos
2922940b44dSPeter Avalos /// Get the next node in the tree. Return NULL if there are no more nodes.
2932940b44dSPeter Avalos static void *
index_tree_next(const index_tree_node * node)2942940b44dSPeter Avalos index_tree_next(const index_tree_node *node)
2952940b44dSPeter Avalos {
2962940b44dSPeter Avalos if (node->right != NULL) {
2972940b44dSPeter Avalos node = node->right;
2982940b44dSPeter Avalos while (node->left != NULL)
2992940b44dSPeter Avalos node = node->left;
3002940b44dSPeter Avalos
3012940b44dSPeter Avalos return (void *)(node);
3022940b44dSPeter Avalos }
3032940b44dSPeter Avalos
3042940b44dSPeter Avalos while (node->parent != NULL && node->parent->right == node)
3052940b44dSPeter Avalos node = node->parent;
3062940b44dSPeter Avalos
3072940b44dSPeter Avalos return (void *)(node->parent);
3082940b44dSPeter Avalos }
3092940b44dSPeter Avalos
3102940b44dSPeter Avalos
3112940b44dSPeter Avalos /// Locate a node that contains the given uncompressed offset. It is
3122940b44dSPeter Avalos /// caller's job to check that target is not bigger than the uncompressed
3132940b44dSPeter Avalos /// size of the tree (the last node would be returned in that case still).
3142940b44dSPeter Avalos static void *
index_tree_locate(const index_tree * tree,lzma_vli target)3152940b44dSPeter Avalos index_tree_locate(const index_tree *tree, lzma_vli target)
3162940b44dSPeter Avalos {
3172940b44dSPeter Avalos const index_tree_node *result = NULL;
3182940b44dSPeter Avalos const index_tree_node *node = tree->root;
3192940b44dSPeter Avalos
3202940b44dSPeter Avalos assert(tree->leftmost == NULL
3212940b44dSPeter Avalos || tree->leftmost->uncompressed_base == 0);
3222940b44dSPeter Avalos
3232940b44dSPeter Avalos // Consecutive nodes may have the same uncompressed_base.
3242940b44dSPeter Avalos // We must pick the rightmost one.
3252940b44dSPeter Avalos while (node != NULL) {
3262940b44dSPeter Avalos if (node->uncompressed_base > target) {
3272940b44dSPeter Avalos node = node->left;
3282940b44dSPeter Avalos } else {
3292940b44dSPeter Avalos result = node;
3302940b44dSPeter Avalos node = node->right;
3312940b44dSPeter Avalos }
3322940b44dSPeter Avalos }
3332940b44dSPeter Avalos
3342940b44dSPeter Avalos return (void *)(result);
3352940b44dSPeter Avalos }
3362940b44dSPeter Avalos
3372940b44dSPeter Avalos
3382940b44dSPeter Avalos /// Allocate and initialize a new Stream using the given base offsets.
3392940b44dSPeter Avalos 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)3402940b44dSPeter Avalos index_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base,
34115ab8c86SJohn Marino uint32_t stream_number, lzma_vli block_number_base,
34215ab8c86SJohn Marino const lzma_allocator *allocator)
3432940b44dSPeter Avalos {
3442940b44dSPeter Avalos index_stream *s = lzma_alloc(sizeof(index_stream), allocator);
3452940b44dSPeter Avalos if (s == NULL)
3462940b44dSPeter Avalos return NULL;
3472940b44dSPeter Avalos
3482940b44dSPeter Avalos s->node.uncompressed_base = uncompressed_base;
3492940b44dSPeter Avalos s->node.compressed_base = compressed_base;
3502940b44dSPeter Avalos s->node.parent = NULL;
3512940b44dSPeter Avalos s->node.left = NULL;
3522940b44dSPeter Avalos s->node.right = NULL;
3532940b44dSPeter Avalos
3542940b44dSPeter Avalos s->number = stream_number;
3552940b44dSPeter Avalos s->block_number_base = block_number_base;
3562940b44dSPeter Avalos
3572940b44dSPeter Avalos index_tree_init(&s->groups);
3582940b44dSPeter Avalos
3592940b44dSPeter Avalos s->record_count = 0;
3602940b44dSPeter Avalos s->index_list_size = 0;
3612940b44dSPeter Avalos s->stream_flags.version = UINT32_MAX;
3622940b44dSPeter Avalos s->stream_padding = 0;
3632940b44dSPeter Avalos
3642940b44dSPeter Avalos return s;
3652940b44dSPeter Avalos }
3662940b44dSPeter Avalos
3672940b44dSPeter Avalos
3682940b44dSPeter Avalos /// Free the memory allocated for a Stream and its Record groups.
3692940b44dSPeter Avalos static void
index_stream_end(void * node,const lzma_allocator * allocator)37015ab8c86SJohn Marino index_stream_end(void *node, const lzma_allocator *allocator)
3712940b44dSPeter Avalos {
3722940b44dSPeter Avalos index_stream *s = node;
37346a2189dSzrj index_tree_end(&s->groups, allocator, &lzma_free);
37446a2189dSzrj lzma_free(s, allocator);
3752940b44dSPeter Avalos return;
3762940b44dSPeter Avalos }
3772940b44dSPeter Avalos
3782940b44dSPeter Avalos
3792940b44dSPeter Avalos static lzma_index *
index_init_plain(const lzma_allocator * allocator)38015ab8c86SJohn Marino index_init_plain(const lzma_allocator *allocator)
3812940b44dSPeter Avalos {
3822940b44dSPeter Avalos lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);
3832940b44dSPeter Avalos if (i != NULL) {
3842940b44dSPeter Avalos index_tree_init(&i->streams);
3852940b44dSPeter Avalos i->uncompressed_size = 0;
3862940b44dSPeter Avalos i->total_size = 0;
3872940b44dSPeter Avalos i->record_count = 0;
3882940b44dSPeter Avalos i->index_list_size = 0;
3892940b44dSPeter Avalos i->prealloc = INDEX_GROUP_SIZE;
3902940b44dSPeter Avalos i->checks = 0;
3912940b44dSPeter Avalos }
3922940b44dSPeter Avalos
3932940b44dSPeter Avalos return i;
3942940b44dSPeter Avalos }
3952940b44dSPeter Avalos
3962940b44dSPeter Avalos
3972940b44dSPeter Avalos extern LZMA_API(lzma_index *)
lzma_index_init(const lzma_allocator * allocator)39815ab8c86SJohn Marino lzma_index_init(const lzma_allocator *allocator)
3992940b44dSPeter Avalos {
4002940b44dSPeter Avalos lzma_index *i = index_init_plain(allocator);
401b892b6baSPeter Avalos if (i == NULL)
402b892b6baSPeter Avalos return NULL;
403b892b6baSPeter Avalos
4042940b44dSPeter Avalos index_stream *s = index_stream_init(0, 0, 1, 0, allocator);
405b892b6baSPeter Avalos if (s == NULL) {
4062940b44dSPeter Avalos lzma_free(i, allocator);
407b892b6baSPeter Avalos return NULL;
4082940b44dSPeter Avalos }
4092940b44dSPeter Avalos
4102940b44dSPeter Avalos index_tree_append(&i->streams, &s->node);
4112940b44dSPeter Avalos
4122940b44dSPeter Avalos return i;
4132940b44dSPeter Avalos }
4142940b44dSPeter Avalos
4152940b44dSPeter Avalos
4162940b44dSPeter Avalos extern LZMA_API(void)
lzma_index_end(lzma_index * i,const lzma_allocator * allocator)41715ab8c86SJohn Marino lzma_index_end(lzma_index *i, const lzma_allocator *allocator)
4182940b44dSPeter Avalos {
4192940b44dSPeter Avalos // NOTE: If you modify this function, check also the bottom
4202940b44dSPeter Avalos // of lzma_index_cat().
4212940b44dSPeter Avalos if (i != NULL) {
4222940b44dSPeter Avalos index_tree_end(&i->streams, allocator, &index_stream_end);
4232940b44dSPeter Avalos lzma_free(i, allocator);
4242940b44dSPeter Avalos }
4252940b44dSPeter Avalos
4262940b44dSPeter Avalos return;
4272940b44dSPeter Avalos }
4282940b44dSPeter Avalos
4292940b44dSPeter Avalos
4302940b44dSPeter Avalos extern void
lzma_index_prealloc(lzma_index * i,lzma_vli records)4312940b44dSPeter Avalos lzma_index_prealloc(lzma_index *i, lzma_vli records)
4322940b44dSPeter Avalos {
4332940b44dSPeter Avalos if (records > PREALLOC_MAX)
4342940b44dSPeter Avalos records = PREALLOC_MAX;
4352940b44dSPeter Avalos
4362940b44dSPeter Avalos i->prealloc = (size_t)(records);
4372940b44dSPeter Avalos return;
4382940b44dSPeter Avalos }
4392940b44dSPeter Avalos
4402940b44dSPeter Avalos
4412940b44dSPeter Avalos extern LZMA_API(uint64_t)
lzma_index_memusage(lzma_vli streams,lzma_vli blocks)4422940b44dSPeter Avalos lzma_index_memusage(lzma_vli streams, lzma_vli blocks)
4432940b44dSPeter Avalos {
4442940b44dSPeter Avalos // This calculates an upper bound that is only a little bit
4452940b44dSPeter Avalos // bigger than the exact maximum memory usage with the given
4462940b44dSPeter Avalos // parameters.
4472940b44dSPeter Avalos
4482940b44dSPeter Avalos // Typical malloc() overhead is 2 * sizeof(void *) but we take
4492940b44dSPeter Avalos // a little bit extra just in case. Using LZMA_MEMUSAGE_BASE
4502940b44dSPeter Avalos // instead would give too inaccurate estimate.
4512940b44dSPeter Avalos const size_t alloc_overhead = 4 * sizeof(void *);
4522940b44dSPeter Avalos
4532940b44dSPeter Avalos // Amount of memory needed for each Stream base structures.
4542940b44dSPeter Avalos // We assume that every Stream has at least one Block and
4552940b44dSPeter Avalos // thus at least one group.
4562940b44dSPeter Avalos const size_t stream_base = sizeof(index_stream)
4572940b44dSPeter Avalos + sizeof(index_group) + 2 * alloc_overhead;
4582940b44dSPeter Avalos
4592940b44dSPeter Avalos // Amount of memory needed per group.
4602940b44dSPeter Avalos const size_t group_base = sizeof(index_group)
4612940b44dSPeter Avalos + INDEX_GROUP_SIZE * sizeof(index_record)
4622940b44dSPeter Avalos + alloc_overhead;
4632940b44dSPeter Avalos
4642940b44dSPeter Avalos // Number of groups. There may actually be more, but that overhead
4652940b44dSPeter Avalos // has been taken into account in stream_base already.
4662940b44dSPeter Avalos const lzma_vli groups
4672940b44dSPeter Avalos = (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE;
4682940b44dSPeter Avalos
4692940b44dSPeter Avalos // Memory used by index_stream and index_group structures.
4702940b44dSPeter Avalos const uint64_t streams_mem = streams * stream_base;
4712940b44dSPeter Avalos const uint64_t groups_mem = groups * group_base;
4722940b44dSPeter Avalos
4732940b44dSPeter Avalos // Memory used by the base structure.
4742940b44dSPeter Avalos const uint64_t index_base = sizeof(lzma_index) + alloc_overhead;
4752940b44dSPeter Avalos
4762940b44dSPeter Avalos // Validate the arguments and catch integer overflows.
4772940b44dSPeter Avalos // Maximum number of Streams is "only" UINT32_MAX, because
4782940b44dSPeter Avalos // that limit is used by the tree containing the Streams.
4792940b44dSPeter Avalos const uint64_t limit = UINT64_MAX - index_base;
4802940b44dSPeter Avalos if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX
4812940b44dSPeter Avalos || streams > limit / stream_base
4822940b44dSPeter Avalos || groups > limit / group_base
4832940b44dSPeter Avalos || limit - streams_mem < groups_mem)
4842940b44dSPeter Avalos return UINT64_MAX;
4852940b44dSPeter Avalos
4862940b44dSPeter Avalos return index_base + streams_mem + groups_mem;
4872940b44dSPeter Avalos }
4882940b44dSPeter Avalos
4892940b44dSPeter Avalos
4902940b44dSPeter Avalos extern LZMA_API(uint64_t)
lzma_index_memused(const lzma_index * i)4912940b44dSPeter Avalos lzma_index_memused(const lzma_index *i)
4922940b44dSPeter Avalos {
4932940b44dSPeter Avalos return lzma_index_memusage(i->streams.count, i->record_count);
4942940b44dSPeter Avalos }
4952940b44dSPeter Avalos
4962940b44dSPeter Avalos
4972940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_block_count(const lzma_index * i)4982940b44dSPeter Avalos lzma_index_block_count(const lzma_index *i)
4992940b44dSPeter Avalos {
5002940b44dSPeter Avalos return i->record_count;
5012940b44dSPeter Avalos }
5022940b44dSPeter Avalos
5032940b44dSPeter Avalos
5042940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_stream_count(const lzma_index * i)5052940b44dSPeter Avalos lzma_index_stream_count(const lzma_index *i)
5062940b44dSPeter Avalos {
5072940b44dSPeter Avalos return i->streams.count;
5082940b44dSPeter Avalos }
5092940b44dSPeter Avalos
5102940b44dSPeter Avalos
5112940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_size(const lzma_index * i)5122940b44dSPeter Avalos lzma_index_size(const lzma_index *i)
5132940b44dSPeter Avalos {
5142940b44dSPeter Avalos return index_size(i->record_count, i->index_list_size);
5152940b44dSPeter Avalos }
5162940b44dSPeter Avalos
5172940b44dSPeter Avalos
5182940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_total_size(const lzma_index * i)5192940b44dSPeter Avalos lzma_index_total_size(const lzma_index *i)
5202940b44dSPeter Avalos {
5212940b44dSPeter Avalos return i->total_size;
5222940b44dSPeter Avalos }
5232940b44dSPeter Avalos
5242940b44dSPeter Avalos
5252940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_stream_size(const lzma_index * i)5262940b44dSPeter Avalos lzma_index_stream_size(const lzma_index *i)
5272940b44dSPeter Avalos {
5282940b44dSPeter Avalos // Stream Header + Blocks + Index + Stream Footer
5292940b44dSPeter Avalos return LZMA_STREAM_HEADER_SIZE + i->total_size
5302940b44dSPeter Avalos + index_size(i->record_count, i->index_list_size)
5312940b44dSPeter Avalos + LZMA_STREAM_HEADER_SIZE;
5322940b44dSPeter Avalos }
5332940b44dSPeter Avalos
5342940b44dSPeter Avalos
5352940b44dSPeter Avalos 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)5362940b44dSPeter Avalos index_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum,
5372940b44dSPeter Avalos lzma_vli record_count, lzma_vli index_list_size,
5382940b44dSPeter Avalos lzma_vli stream_padding)
5392940b44dSPeter Avalos {
5402940b44dSPeter Avalos // Earlier Streams and Stream Paddings + Stream Header
5412940b44dSPeter Avalos // + Blocks + Index + Stream Footer + Stream Padding
5422940b44dSPeter Avalos //
5432940b44dSPeter Avalos // This might go over LZMA_VLI_MAX due to too big unpadded_sum
5442940b44dSPeter Avalos // when this function is used in lzma_index_append().
5452940b44dSPeter Avalos lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE
5462940b44dSPeter Avalos + stream_padding + vli_ceil4(unpadded_sum);
5472940b44dSPeter Avalos if (file_size > LZMA_VLI_MAX)
5482940b44dSPeter Avalos return LZMA_VLI_UNKNOWN;
5492940b44dSPeter Avalos
5502940b44dSPeter Avalos // The same applies here.
5512940b44dSPeter Avalos file_size += index_size(record_count, index_list_size);
5522940b44dSPeter Avalos if (file_size > LZMA_VLI_MAX)
5532940b44dSPeter Avalos return LZMA_VLI_UNKNOWN;
5542940b44dSPeter Avalos
5552940b44dSPeter Avalos return file_size;
5562940b44dSPeter Avalos }
5572940b44dSPeter Avalos
5582940b44dSPeter Avalos
5592940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_file_size(const lzma_index * i)5602940b44dSPeter Avalos lzma_index_file_size(const lzma_index *i)
5612940b44dSPeter Avalos {
5622940b44dSPeter Avalos const index_stream *s = (const index_stream *)(i->streams.rightmost);
5632940b44dSPeter Avalos const index_group *g = (const index_group *)(s->groups.rightmost);
5642940b44dSPeter Avalos return index_file_size(s->node.compressed_base,
5652940b44dSPeter Avalos g == NULL ? 0 : g->records[g->last].unpadded_sum,
5662940b44dSPeter Avalos s->record_count, s->index_list_size,
5672940b44dSPeter Avalos s->stream_padding);
5682940b44dSPeter Avalos }
5692940b44dSPeter Avalos
5702940b44dSPeter Avalos
5712940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_uncompressed_size(const lzma_index * i)5722940b44dSPeter Avalos lzma_index_uncompressed_size(const lzma_index *i)
5732940b44dSPeter Avalos {
5742940b44dSPeter Avalos return i->uncompressed_size;
5752940b44dSPeter Avalos }
5762940b44dSPeter Avalos
5772940b44dSPeter Avalos
5782940b44dSPeter Avalos extern LZMA_API(uint32_t)
lzma_index_checks(const lzma_index * i)5792940b44dSPeter Avalos lzma_index_checks(const lzma_index *i)
5802940b44dSPeter Avalos {
5812940b44dSPeter Avalos uint32_t checks = i->checks;
5822940b44dSPeter Avalos
5832940b44dSPeter Avalos // Get the type of the Check of the last Stream too.
5842940b44dSPeter Avalos const index_stream *s = (const index_stream *)(i->streams.rightmost);
5852940b44dSPeter Avalos if (s->stream_flags.version != UINT32_MAX)
5862940b44dSPeter Avalos checks |= UINT32_C(1) << s->stream_flags.check;
5872940b44dSPeter Avalos
5882940b44dSPeter Avalos return checks;
5892940b44dSPeter Avalos }
5902940b44dSPeter Avalos
5912940b44dSPeter Avalos
5922940b44dSPeter Avalos extern uint32_t
lzma_index_padding_size(const lzma_index * i)5932940b44dSPeter Avalos lzma_index_padding_size(const lzma_index *i)
5942940b44dSPeter Avalos {
5952940b44dSPeter Avalos return (LZMA_VLI_C(4) - index_size_unpadded(
5962940b44dSPeter Avalos i->record_count, i->index_list_size)) & 3;
5972940b44dSPeter Avalos }
5982940b44dSPeter Avalos
5992940b44dSPeter Avalos
6002940b44dSPeter Avalos extern LZMA_API(lzma_ret)
lzma_index_stream_flags(lzma_index * i,const lzma_stream_flags * stream_flags)6012940b44dSPeter Avalos lzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags)
6022940b44dSPeter Avalos {
6032940b44dSPeter Avalos if (i == NULL || stream_flags == NULL)
6042940b44dSPeter Avalos return LZMA_PROG_ERROR;
6052940b44dSPeter Avalos
6062940b44dSPeter Avalos // Validate the Stream Flags.
6072940b44dSPeter Avalos return_if_error(lzma_stream_flags_compare(
6082940b44dSPeter Avalos stream_flags, stream_flags));
6092940b44dSPeter Avalos
6102940b44dSPeter Avalos index_stream *s = (index_stream *)(i->streams.rightmost);
6112940b44dSPeter Avalos s->stream_flags = *stream_flags;
6122940b44dSPeter Avalos
6132940b44dSPeter Avalos return LZMA_OK;
6142940b44dSPeter Avalos }
6152940b44dSPeter Avalos
6162940b44dSPeter Avalos
6172940b44dSPeter Avalos extern LZMA_API(lzma_ret)
lzma_index_stream_padding(lzma_index * i,lzma_vli stream_padding)6182940b44dSPeter Avalos lzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding)
6192940b44dSPeter Avalos {
6202940b44dSPeter Avalos if (i == NULL || stream_padding > LZMA_VLI_MAX
6212940b44dSPeter Avalos || (stream_padding & 3) != 0)
6222940b44dSPeter Avalos return LZMA_PROG_ERROR;
6232940b44dSPeter Avalos
6242940b44dSPeter Avalos index_stream *s = (index_stream *)(i->streams.rightmost);
6252940b44dSPeter Avalos
6262940b44dSPeter Avalos // Check that the new value won't make the file grow too big.
6272940b44dSPeter Avalos const lzma_vli old_stream_padding = s->stream_padding;
6282940b44dSPeter Avalos s->stream_padding = 0;
6292940b44dSPeter Avalos if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) {
6302940b44dSPeter Avalos s->stream_padding = old_stream_padding;
6312940b44dSPeter Avalos return LZMA_DATA_ERROR;
6322940b44dSPeter Avalos }
6332940b44dSPeter Avalos
6342940b44dSPeter Avalos s->stream_padding = stream_padding;
6352940b44dSPeter Avalos return LZMA_OK;
6362940b44dSPeter Avalos }
6372940b44dSPeter Avalos
6382940b44dSPeter Avalos
6392940b44dSPeter Avalos extern LZMA_API(lzma_ret)
lzma_index_append(lzma_index * i,const lzma_allocator * allocator,lzma_vli unpadded_size,lzma_vli uncompressed_size)64015ab8c86SJohn Marino lzma_index_append(lzma_index *i, const lzma_allocator *allocator,
6412940b44dSPeter Avalos lzma_vli unpadded_size, lzma_vli uncompressed_size)
6422940b44dSPeter Avalos {
6432940b44dSPeter Avalos // Validate.
6442940b44dSPeter Avalos if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN
6452940b44dSPeter Avalos || unpadded_size > UNPADDED_SIZE_MAX
6462940b44dSPeter Avalos || uncompressed_size > LZMA_VLI_MAX)
6472940b44dSPeter Avalos return LZMA_PROG_ERROR;
6482940b44dSPeter Avalos
6492940b44dSPeter Avalos index_stream *s = (index_stream *)(i->streams.rightmost);
6502940b44dSPeter Avalos index_group *g = (index_group *)(s->groups.rightmost);
6512940b44dSPeter Avalos
6522940b44dSPeter Avalos const lzma_vli compressed_base = g == NULL ? 0
6532940b44dSPeter Avalos : vli_ceil4(g->records[g->last].unpadded_sum);
6542940b44dSPeter Avalos const lzma_vli uncompressed_base = g == NULL ? 0
6552940b44dSPeter Avalos : g->records[g->last].uncompressed_sum;
6562940b44dSPeter Avalos const uint32_t index_list_size_add = lzma_vli_size(unpadded_size)
6572940b44dSPeter Avalos + lzma_vli_size(uncompressed_size);
6582940b44dSPeter Avalos
6592940b44dSPeter Avalos // Check that the file size will stay within limits.
6602940b44dSPeter Avalos if (index_file_size(s->node.compressed_base,
6612940b44dSPeter Avalos compressed_base + unpadded_size, s->record_count + 1,
6622940b44dSPeter Avalos s->index_list_size + index_list_size_add,
6632940b44dSPeter Avalos s->stream_padding) == LZMA_VLI_UNKNOWN)
6642940b44dSPeter Avalos return LZMA_DATA_ERROR;
6652940b44dSPeter Avalos
6662940b44dSPeter Avalos // The size of the Index field must not exceed the maximum value
6672940b44dSPeter Avalos // that can be stored in the Backward Size field.
6682940b44dSPeter Avalos if (index_size(i->record_count + 1,
6692940b44dSPeter Avalos i->index_list_size + index_list_size_add)
6702940b44dSPeter Avalos > LZMA_BACKWARD_SIZE_MAX)
6712940b44dSPeter Avalos return LZMA_DATA_ERROR;
6722940b44dSPeter Avalos
6732940b44dSPeter Avalos if (g != NULL && g->last + 1 < g->allocated) {
6742940b44dSPeter Avalos // There is space in the last group at least for one Record.
6752940b44dSPeter Avalos ++g->last;
6762940b44dSPeter Avalos } else {
6772940b44dSPeter Avalos // We need to allocate a new group.
6782940b44dSPeter Avalos g = lzma_alloc(sizeof(index_group)
6792940b44dSPeter Avalos + i->prealloc * sizeof(index_record),
6802940b44dSPeter Avalos allocator);
6812940b44dSPeter Avalos if (g == NULL)
6822940b44dSPeter Avalos return LZMA_MEM_ERROR;
6832940b44dSPeter Avalos
6842940b44dSPeter Avalos g->last = 0;
6852940b44dSPeter Avalos g->allocated = i->prealloc;
6862940b44dSPeter Avalos
6872940b44dSPeter Avalos // Reset prealloc so that if the application happens to
6882940b44dSPeter Avalos // add new Records, the allocation size will be sane.
6892940b44dSPeter Avalos i->prealloc = INDEX_GROUP_SIZE;
6902940b44dSPeter Avalos
6912940b44dSPeter Avalos // Set the start offsets of this group.
6922940b44dSPeter Avalos g->node.uncompressed_base = uncompressed_base;
6932940b44dSPeter Avalos g->node.compressed_base = compressed_base;
6942940b44dSPeter Avalos g->number_base = s->record_count + 1;
6952940b44dSPeter Avalos
6962940b44dSPeter Avalos // Add the new group to the Stream.
6972940b44dSPeter Avalos index_tree_append(&s->groups, &g->node);
6982940b44dSPeter Avalos }
6992940b44dSPeter Avalos
7002940b44dSPeter Avalos // Add the new Record to the group.
7012940b44dSPeter Avalos g->records[g->last].uncompressed_sum
7022940b44dSPeter Avalos = uncompressed_base + uncompressed_size;
7032940b44dSPeter Avalos g->records[g->last].unpadded_sum
7042940b44dSPeter Avalos = compressed_base + unpadded_size;
7052940b44dSPeter Avalos
7062940b44dSPeter Avalos // Update the totals.
7072940b44dSPeter Avalos ++s->record_count;
7082940b44dSPeter Avalos s->index_list_size += index_list_size_add;
7092940b44dSPeter Avalos
7102940b44dSPeter Avalos i->total_size += vli_ceil4(unpadded_size);
7112940b44dSPeter Avalos i->uncompressed_size += uncompressed_size;
7122940b44dSPeter Avalos ++i->record_count;
7132940b44dSPeter Avalos i->index_list_size += index_list_size_add;
7142940b44dSPeter Avalos
7152940b44dSPeter Avalos return LZMA_OK;
7162940b44dSPeter Avalos }
7172940b44dSPeter Avalos
7182940b44dSPeter Avalos
7192940b44dSPeter Avalos /// Structure to pass info to index_cat_helper()
7202940b44dSPeter Avalos typedef struct {
7212940b44dSPeter Avalos /// Uncompressed size of the destination
7222940b44dSPeter Avalos lzma_vli uncompressed_size;
7232940b44dSPeter Avalos
7242940b44dSPeter Avalos /// Compressed file size of the destination
7252940b44dSPeter Avalos lzma_vli file_size;
7262940b44dSPeter Avalos
7272940b44dSPeter Avalos /// Same as above but for Block numbers
7282940b44dSPeter Avalos lzma_vli block_number_add;
7292940b44dSPeter Avalos
7302940b44dSPeter Avalos /// Number of Streams that were in the destination index before we
7312940b44dSPeter Avalos /// started appending new Streams from the source index. This is
7322940b44dSPeter Avalos /// used to fix the Stream numbering.
7332940b44dSPeter Avalos uint32_t stream_number_add;
7342940b44dSPeter Avalos
7352940b44dSPeter Avalos /// Destination index' Stream tree
7362940b44dSPeter Avalos index_tree *streams;
7372940b44dSPeter Avalos
7382940b44dSPeter Avalos } index_cat_info;
7392940b44dSPeter Avalos
7402940b44dSPeter Avalos
7412940b44dSPeter Avalos /// Add the Stream nodes from the source index to dest using recursion.
7422940b44dSPeter Avalos /// Simplest iterative traversal of the source tree wouldn't work, because
7432940b44dSPeter Avalos /// we update the pointers in nodes when moving them to the destination tree.
7442940b44dSPeter Avalos static void
index_cat_helper(const index_cat_info * info,index_stream * this)7452940b44dSPeter Avalos index_cat_helper(const index_cat_info *info, index_stream *this)
7462940b44dSPeter Avalos {
7472940b44dSPeter Avalos index_stream *left = (index_stream *)(this->node.left);
7482940b44dSPeter Avalos index_stream *right = (index_stream *)(this->node.right);
7492940b44dSPeter Avalos
7502940b44dSPeter Avalos if (left != NULL)
7512940b44dSPeter Avalos index_cat_helper(info, left);
7522940b44dSPeter Avalos
7532940b44dSPeter Avalos this->node.uncompressed_base += info->uncompressed_size;
7542940b44dSPeter Avalos this->node.compressed_base += info->file_size;
7552940b44dSPeter Avalos this->number += info->stream_number_add;
7562940b44dSPeter Avalos this->block_number_base += info->block_number_add;
7572940b44dSPeter Avalos index_tree_append(info->streams, &this->node);
7582940b44dSPeter Avalos
7592940b44dSPeter Avalos if (right != NULL)
7602940b44dSPeter Avalos index_cat_helper(info, right);
7612940b44dSPeter Avalos
7622940b44dSPeter Avalos return;
7632940b44dSPeter Avalos }
7642940b44dSPeter Avalos
7652940b44dSPeter Avalos
7662940b44dSPeter Avalos extern LZMA_API(lzma_ret)
lzma_index_cat(lzma_index * restrict dest,lzma_index * restrict src,const lzma_allocator * allocator)7672940b44dSPeter Avalos lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,
76815ab8c86SJohn Marino const lzma_allocator *allocator)
7692940b44dSPeter Avalos {
7702940b44dSPeter Avalos const lzma_vli dest_file_size = lzma_index_file_size(dest);
7712940b44dSPeter Avalos
7722940b44dSPeter Avalos // Check that we don't exceed the file size limits.
7732940b44dSPeter Avalos if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX
7742940b44dSPeter Avalos || dest->uncompressed_size + src->uncompressed_size
7752940b44dSPeter Avalos > LZMA_VLI_MAX)
7762940b44dSPeter Avalos return LZMA_DATA_ERROR;
7772940b44dSPeter Avalos
7782940b44dSPeter Avalos // Check that the encoded size of the combined lzma_indexes stays
7792940b44dSPeter Avalos // within limits. In theory, this should be done only if we know
7802940b44dSPeter Avalos // that the user plans to actually combine the Streams and thus
7812940b44dSPeter Avalos // construct a single Index (probably rare). However, exceeding
7822940b44dSPeter Avalos // this limit is quite theoretical, so we do this check always
7832940b44dSPeter Avalos // to simplify things elsewhere.
7842940b44dSPeter Avalos {
7852940b44dSPeter Avalos const lzma_vli dest_size = index_size_unpadded(
7862940b44dSPeter Avalos dest->record_count, dest->index_list_size);
7872940b44dSPeter Avalos const lzma_vli src_size = index_size_unpadded(
7882940b44dSPeter Avalos src->record_count, src->index_list_size);
7892940b44dSPeter Avalos if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX)
7902940b44dSPeter Avalos return LZMA_DATA_ERROR;
7912940b44dSPeter Avalos }
7922940b44dSPeter Avalos
7932940b44dSPeter Avalos // Optimize the last group to minimize memory usage. Allocation has
7942940b44dSPeter Avalos // to be done before modifying dest or src.
7952940b44dSPeter Avalos {
7962940b44dSPeter Avalos index_stream *s = (index_stream *)(dest->streams.rightmost);
7972940b44dSPeter Avalos index_group *g = (index_group *)(s->groups.rightmost);
7982940b44dSPeter Avalos if (g != NULL && g->last + 1 < g->allocated) {
7992940b44dSPeter Avalos assert(g->node.left == NULL);
8002940b44dSPeter Avalos assert(g->node.right == NULL);
8012940b44dSPeter Avalos
8022940b44dSPeter Avalos index_group *newg = lzma_alloc(sizeof(index_group)
8032940b44dSPeter Avalos + (g->last + 1)
8042940b44dSPeter Avalos * sizeof(index_record),
8052940b44dSPeter Avalos allocator);
8062940b44dSPeter Avalos if (newg == NULL)
8072940b44dSPeter Avalos return LZMA_MEM_ERROR;
8082940b44dSPeter Avalos
8092940b44dSPeter Avalos newg->node = g->node;
8102940b44dSPeter Avalos newg->allocated = g->last + 1;
8112940b44dSPeter Avalos newg->last = g->last;
8122940b44dSPeter Avalos newg->number_base = g->number_base;
8132940b44dSPeter Avalos
8142940b44dSPeter Avalos memcpy(newg->records, g->records, newg->allocated
8152940b44dSPeter Avalos * sizeof(index_record));
8162940b44dSPeter Avalos
8172940b44dSPeter Avalos if (g->node.parent != NULL) {
8182940b44dSPeter Avalos assert(g->node.parent->right == &g->node);
8192940b44dSPeter Avalos g->node.parent->right = &newg->node;
8202940b44dSPeter Avalos }
8212940b44dSPeter Avalos
8222940b44dSPeter Avalos if (s->groups.leftmost == &g->node) {
8232940b44dSPeter Avalos assert(s->groups.root == &g->node);
8242940b44dSPeter Avalos s->groups.leftmost = &newg->node;
8252940b44dSPeter Avalos s->groups.root = &newg->node;
8262940b44dSPeter Avalos }
8272940b44dSPeter Avalos
828*e151908bSDaniel Fojt assert(s->groups.rightmost == &g->node);
8292940b44dSPeter Avalos s->groups.rightmost = &newg->node;
8302940b44dSPeter Avalos
8312940b44dSPeter Avalos lzma_free(g, allocator);
83246a2189dSzrj
83346a2189dSzrj // NOTE: newg isn't leaked here because
83446a2189dSzrj // newg == (void *)&newg->node.
8352940b44dSPeter Avalos }
8362940b44dSPeter Avalos }
8372940b44dSPeter Avalos
8382940b44dSPeter Avalos // Add all the Streams from src to dest. Update the base offsets
8392940b44dSPeter Avalos // of each Stream from src.
8402940b44dSPeter Avalos const index_cat_info info = {
8412940b44dSPeter Avalos .uncompressed_size = dest->uncompressed_size,
8422940b44dSPeter Avalos .file_size = dest_file_size,
8432940b44dSPeter Avalos .stream_number_add = dest->streams.count,
8442940b44dSPeter Avalos .block_number_add = dest->record_count,
8452940b44dSPeter Avalos .streams = &dest->streams,
8462940b44dSPeter Avalos };
8472940b44dSPeter Avalos index_cat_helper(&info, (index_stream *)(src->streams.root));
8482940b44dSPeter Avalos
8492940b44dSPeter Avalos // Update info about all the combined Streams.
8502940b44dSPeter Avalos dest->uncompressed_size += src->uncompressed_size;
8512940b44dSPeter Avalos dest->total_size += src->total_size;
8522940b44dSPeter Avalos dest->record_count += src->record_count;
8532940b44dSPeter Avalos dest->index_list_size += src->index_list_size;
8542940b44dSPeter Avalos dest->checks = lzma_index_checks(dest) | src->checks;
8552940b44dSPeter Avalos
8562940b44dSPeter Avalos // There's nothing else left in src than the base structure.
8572940b44dSPeter Avalos lzma_free(src, allocator);
8582940b44dSPeter Avalos
8592940b44dSPeter Avalos return LZMA_OK;
8602940b44dSPeter Avalos }
8612940b44dSPeter Avalos
8622940b44dSPeter Avalos
8632940b44dSPeter Avalos /// Duplicate an index_stream.
8642940b44dSPeter Avalos static index_stream *
index_dup_stream(const index_stream * src,const lzma_allocator * allocator)86515ab8c86SJohn Marino index_dup_stream(const index_stream *src, const lzma_allocator *allocator)
8662940b44dSPeter Avalos {
8672940b44dSPeter Avalos // Catch a somewhat theoretical integer overflow.
8682940b44dSPeter Avalos if (src->record_count > PREALLOC_MAX)
8692940b44dSPeter Avalos return NULL;
8702940b44dSPeter Avalos
8712940b44dSPeter Avalos // Allocate and initialize a new Stream.
8722940b44dSPeter Avalos index_stream *dest = index_stream_init(src->node.compressed_base,
8732940b44dSPeter Avalos src->node.uncompressed_base, src->number,
8742940b44dSPeter Avalos src->block_number_base, allocator);
87546a2189dSzrj if (dest == NULL)
87646a2189dSzrj return NULL;
8772940b44dSPeter Avalos
8782940b44dSPeter Avalos // Copy the overall information.
8792940b44dSPeter Avalos dest->record_count = src->record_count;
8802940b44dSPeter Avalos dest->index_list_size = src->index_list_size;
8812940b44dSPeter Avalos dest->stream_flags = src->stream_flags;
8822940b44dSPeter Avalos dest->stream_padding = src->stream_padding;
8832940b44dSPeter Avalos
88446a2189dSzrj // Return if there are no groups to duplicate.
88546a2189dSzrj if (src->groups.leftmost == NULL)
88646a2189dSzrj return dest;
88746a2189dSzrj
8882940b44dSPeter Avalos // Allocate memory for the Records. We put all the Records into
8892940b44dSPeter Avalos // a single group. It's simplest and also tends to make
8902940b44dSPeter Avalos // lzma_index_locate() a little bit faster with very big Indexes.
8912940b44dSPeter Avalos index_group *destg = lzma_alloc(sizeof(index_group)
8922940b44dSPeter Avalos + src->record_count * sizeof(index_record),
8932940b44dSPeter Avalos allocator);
8942940b44dSPeter Avalos if (destg == NULL) {
8952940b44dSPeter Avalos index_stream_end(dest, allocator);
8962940b44dSPeter Avalos return NULL;
8972940b44dSPeter Avalos }
8982940b44dSPeter Avalos
8992940b44dSPeter Avalos // Initialize destg.
9002940b44dSPeter Avalos destg->node.uncompressed_base = 0;
9012940b44dSPeter Avalos destg->node.compressed_base = 0;
9022940b44dSPeter Avalos destg->number_base = 1;
9032940b44dSPeter Avalos destg->allocated = src->record_count;
9042940b44dSPeter Avalos destg->last = src->record_count - 1;
9052940b44dSPeter Avalos
9062940b44dSPeter Avalos // Go through all the groups in src and copy the Records into destg.
9072940b44dSPeter Avalos const index_group *srcg = (const index_group *)(src->groups.leftmost);
9082940b44dSPeter Avalos size_t i = 0;
9092940b44dSPeter Avalos do {
9102940b44dSPeter Avalos memcpy(destg->records + i, srcg->records,
9112940b44dSPeter Avalos (srcg->last + 1) * sizeof(index_record));
9122940b44dSPeter Avalos i += srcg->last + 1;
9132940b44dSPeter Avalos srcg = index_tree_next(&srcg->node);
9142940b44dSPeter Avalos } while (srcg != NULL);
9152940b44dSPeter Avalos
9162940b44dSPeter Avalos assert(i == destg->allocated);
9172940b44dSPeter Avalos
9182940b44dSPeter Avalos // Add the group to the new Stream.
9192940b44dSPeter Avalos index_tree_append(&dest->groups, &destg->node);
9202940b44dSPeter Avalos
9212940b44dSPeter Avalos return dest;
9222940b44dSPeter Avalos }
9232940b44dSPeter Avalos
9242940b44dSPeter Avalos
9252940b44dSPeter Avalos extern LZMA_API(lzma_index *)
lzma_index_dup(const lzma_index * src,const lzma_allocator * allocator)92615ab8c86SJohn Marino lzma_index_dup(const lzma_index *src, const lzma_allocator *allocator)
9272940b44dSPeter Avalos {
9282940b44dSPeter Avalos // Allocate the base structure (no initial Stream).
9292940b44dSPeter Avalos lzma_index *dest = index_init_plain(allocator);
9302940b44dSPeter Avalos if (dest == NULL)
9312940b44dSPeter Avalos return NULL;
9322940b44dSPeter Avalos
9332940b44dSPeter Avalos // Copy the totals.
9342940b44dSPeter Avalos dest->uncompressed_size = src->uncompressed_size;
9352940b44dSPeter Avalos dest->total_size = src->total_size;
9362940b44dSPeter Avalos dest->record_count = src->record_count;
9372940b44dSPeter Avalos dest->index_list_size = src->index_list_size;
9382940b44dSPeter Avalos
9392940b44dSPeter Avalos // Copy the Streams and the groups in them.
9402940b44dSPeter Avalos const index_stream *srcstream
9412940b44dSPeter Avalos = (const index_stream *)(src->streams.leftmost);
9422940b44dSPeter Avalos do {
9432940b44dSPeter Avalos index_stream *deststream = index_dup_stream(
9442940b44dSPeter Avalos srcstream, allocator);
9452940b44dSPeter Avalos if (deststream == NULL) {
9462940b44dSPeter Avalos lzma_index_end(dest, allocator);
9472940b44dSPeter Avalos return NULL;
9482940b44dSPeter Avalos }
9492940b44dSPeter Avalos
9502940b44dSPeter Avalos index_tree_append(&dest->streams, &deststream->node);
9512940b44dSPeter Avalos
9522940b44dSPeter Avalos srcstream = index_tree_next(&srcstream->node);
9532940b44dSPeter Avalos } while (srcstream != NULL);
9542940b44dSPeter Avalos
9552940b44dSPeter Avalos return dest;
9562940b44dSPeter Avalos }
9572940b44dSPeter Avalos
9582940b44dSPeter Avalos
9592940b44dSPeter Avalos /// Indexing for lzma_index_iter.internal[]
9602940b44dSPeter Avalos enum {
9612940b44dSPeter Avalos ITER_INDEX,
9622940b44dSPeter Avalos ITER_STREAM,
9632940b44dSPeter Avalos ITER_GROUP,
9642940b44dSPeter Avalos ITER_RECORD,
9652940b44dSPeter Avalos ITER_METHOD,
9662940b44dSPeter Avalos };
9672940b44dSPeter Avalos
9682940b44dSPeter Avalos
9692940b44dSPeter Avalos /// Values for lzma_index_iter.internal[ITER_METHOD].s
9702940b44dSPeter Avalos enum {
9712940b44dSPeter Avalos ITER_METHOD_NORMAL,
9722940b44dSPeter Avalos ITER_METHOD_NEXT,
9732940b44dSPeter Avalos ITER_METHOD_LEFTMOST,
9742940b44dSPeter Avalos };
9752940b44dSPeter Avalos
9762940b44dSPeter Avalos
9772940b44dSPeter Avalos static void
iter_set_info(lzma_index_iter * iter)9782940b44dSPeter Avalos iter_set_info(lzma_index_iter *iter)
9792940b44dSPeter Avalos {
9802940b44dSPeter Avalos const lzma_index *i = iter->internal[ITER_INDEX].p;
9812940b44dSPeter Avalos const index_stream *stream = iter->internal[ITER_STREAM].p;
9822940b44dSPeter Avalos const index_group *group = iter->internal[ITER_GROUP].p;
9832940b44dSPeter Avalos const size_t record = iter->internal[ITER_RECORD].s;
9842940b44dSPeter Avalos
9852940b44dSPeter Avalos // lzma_index_iter.internal must not contain a pointer to the last
9862940b44dSPeter Avalos // group in the index, because that may be reallocated by
9872940b44dSPeter Avalos // lzma_index_cat().
9882940b44dSPeter Avalos if (group == NULL) {
9892940b44dSPeter Avalos // There are no groups.
9902940b44dSPeter Avalos assert(stream->groups.root == NULL);
9912940b44dSPeter Avalos iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
9922940b44dSPeter Avalos
9932940b44dSPeter Avalos } else if (i->streams.rightmost != &stream->node
9942940b44dSPeter Avalos || stream->groups.rightmost != &group->node) {
9952940b44dSPeter Avalos // The group is not not the last group in the index.
9962940b44dSPeter Avalos iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
9972940b44dSPeter Avalos
9982940b44dSPeter Avalos } else if (stream->groups.leftmost != &group->node) {
9992940b44dSPeter Avalos // The group isn't the only group in the Stream, thus we
10002940b44dSPeter Avalos // know that it must have a parent group i.e. it's not
10012940b44dSPeter Avalos // the root node.
10022940b44dSPeter Avalos assert(stream->groups.root != &group->node);
10032940b44dSPeter Avalos assert(group->node.parent->right == &group->node);
10042940b44dSPeter Avalos iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT;
10052940b44dSPeter Avalos iter->internal[ITER_GROUP].p = group->node.parent;
10062940b44dSPeter Avalos
10072940b44dSPeter Avalos } else {
10082940b44dSPeter Avalos // The Stream has only one group.
10092940b44dSPeter Avalos assert(stream->groups.root == &group->node);
10102940b44dSPeter Avalos assert(group->node.parent == NULL);
10112940b44dSPeter Avalos iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
10122940b44dSPeter Avalos iter->internal[ITER_GROUP].p = NULL;
10132940b44dSPeter Avalos }
10142940b44dSPeter Avalos
101515ab8c86SJohn Marino // NOTE: lzma_index_iter.stream.number is lzma_vli but we use uint32_t
101615ab8c86SJohn Marino // internally.
10172940b44dSPeter Avalos iter->stream.number = stream->number;
10182940b44dSPeter Avalos iter->stream.block_count = stream->record_count;
10192940b44dSPeter Avalos iter->stream.compressed_offset = stream->node.compressed_base;
10202940b44dSPeter Avalos iter->stream.uncompressed_offset = stream->node.uncompressed_base;
10212940b44dSPeter Avalos
10222940b44dSPeter Avalos // iter->stream.flags will be NULL if the Stream Flags haven't been
10232940b44dSPeter Avalos // set with lzma_index_stream_flags().
10242940b44dSPeter Avalos iter->stream.flags = stream->stream_flags.version == UINT32_MAX
10252940b44dSPeter Avalos ? NULL : &stream->stream_flags;
10262940b44dSPeter Avalos iter->stream.padding = stream->stream_padding;
10272940b44dSPeter Avalos
10282940b44dSPeter Avalos if (stream->groups.rightmost == NULL) {
10292940b44dSPeter Avalos // Stream has no Blocks.
10302940b44dSPeter Avalos iter->stream.compressed_size = index_size(0, 0)
10312940b44dSPeter Avalos + 2 * LZMA_STREAM_HEADER_SIZE;
10322940b44dSPeter Avalos iter->stream.uncompressed_size = 0;
10332940b44dSPeter Avalos } else {
10342940b44dSPeter Avalos const index_group *g = (const index_group *)(
10352940b44dSPeter Avalos stream->groups.rightmost);
10362940b44dSPeter Avalos
10372940b44dSPeter Avalos // Stream Header + Stream Footer + Index + Blocks
10382940b44dSPeter Avalos iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE
10392940b44dSPeter Avalos + index_size(stream->record_count,
10402940b44dSPeter Avalos stream->index_list_size)
10412940b44dSPeter Avalos + vli_ceil4(g->records[g->last].unpadded_sum);
10422940b44dSPeter Avalos iter->stream.uncompressed_size
10432940b44dSPeter Avalos = g->records[g->last].uncompressed_sum;
10442940b44dSPeter Avalos }
10452940b44dSPeter Avalos
10462940b44dSPeter Avalos if (group != NULL) {
10472940b44dSPeter Avalos iter->block.number_in_stream = group->number_base + record;
10482940b44dSPeter Avalos iter->block.number_in_file = iter->block.number_in_stream
10492940b44dSPeter Avalos + stream->block_number_base;
10502940b44dSPeter Avalos
10512940b44dSPeter Avalos iter->block.compressed_stream_offset
10522940b44dSPeter Avalos = record == 0 ? group->node.compressed_base
10532940b44dSPeter Avalos : vli_ceil4(group->records[
10542940b44dSPeter Avalos record - 1].unpadded_sum);
10552940b44dSPeter Avalos iter->block.uncompressed_stream_offset
10562940b44dSPeter Avalos = record == 0 ? group->node.uncompressed_base
10572940b44dSPeter Avalos : group->records[record - 1].uncompressed_sum;
10582940b44dSPeter Avalos
10592940b44dSPeter Avalos iter->block.uncompressed_size
10602940b44dSPeter Avalos = group->records[record].uncompressed_sum
10612940b44dSPeter Avalos - iter->block.uncompressed_stream_offset;
10622940b44dSPeter Avalos iter->block.unpadded_size
10632940b44dSPeter Avalos = group->records[record].unpadded_sum
10642940b44dSPeter Avalos - iter->block.compressed_stream_offset;
10652940b44dSPeter Avalos iter->block.total_size = vli_ceil4(iter->block.unpadded_size);
10662940b44dSPeter Avalos
10672940b44dSPeter Avalos iter->block.compressed_stream_offset
10682940b44dSPeter Avalos += LZMA_STREAM_HEADER_SIZE;
10692940b44dSPeter Avalos
10702940b44dSPeter Avalos iter->block.compressed_file_offset
10712940b44dSPeter Avalos = iter->block.compressed_stream_offset
10722940b44dSPeter Avalos + iter->stream.compressed_offset;
10732940b44dSPeter Avalos iter->block.uncompressed_file_offset
10742940b44dSPeter Avalos = iter->block.uncompressed_stream_offset
10752940b44dSPeter Avalos + iter->stream.uncompressed_offset;
10762940b44dSPeter Avalos }
10772940b44dSPeter Avalos
10782940b44dSPeter Avalos return;
10792940b44dSPeter Avalos }
10802940b44dSPeter Avalos
10812940b44dSPeter Avalos
10822940b44dSPeter Avalos extern LZMA_API(void)
lzma_index_iter_init(lzma_index_iter * iter,const lzma_index * i)10832940b44dSPeter Avalos lzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i)
10842940b44dSPeter Avalos {
10852940b44dSPeter Avalos iter->internal[ITER_INDEX].p = i;
10862940b44dSPeter Avalos lzma_index_iter_rewind(iter);
10872940b44dSPeter Avalos return;
10882940b44dSPeter Avalos }
10892940b44dSPeter Avalos
10902940b44dSPeter Avalos
10912940b44dSPeter Avalos extern LZMA_API(void)
lzma_index_iter_rewind(lzma_index_iter * iter)10922940b44dSPeter Avalos lzma_index_iter_rewind(lzma_index_iter *iter)
10932940b44dSPeter Avalos {
10942940b44dSPeter Avalos iter->internal[ITER_STREAM].p = NULL;
10952940b44dSPeter Avalos iter->internal[ITER_GROUP].p = NULL;
10962940b44dSPeter Avalos iter->internal[ITER_RECORD].s = 0;
10972940b44dSPeter Avalos iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
10982940b44dSPeter Avalos return;
10992940b44dSPeter Avalos }
11002940b44dSPeter Avalos
11012940b44dSPeter Avalos
11022940b44dSPeter Avalos extern LZMA_API(lzma_bool)
lzma_index_iter_next(lzma_index_iter * iter,lzma_index_iter_mode mode)11032940b44dSPeter Avalos lzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode)
11042940b44dSPeter Avalos {
11052940b44dSPeter Avalos // Catch unsupported mode values.
11062940b44dSPeter Avalos if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK)
11072940b44dSPeter Avalos return true;
11082940b44dSPeter Avalos
11092940b44dSPeter Avalos const lzma_index *i = iter->internal[ITER_INDEX].p;
11102940b44dSPeter Avalos const index_stream *stream = iter->internal[ITER_STREAM].p;
11112940b44dSPeter Avalos const index_group *group = NULL;
11122940b44dSPeter Avalos size_t record = iter->internal[ITER_RECORD].s;
11132940b44dSPeter Avalos
11142940b44dSPeter Avalos // If we are being asked for the next Stream, leave group to NULL
11152940b44dSPeter Avalos // so that the rest of the this function thinks that this Stream
11162940b44dSPeter Avalos // has no groups and will thus go to the next Stream.
11172940b44dSPeter Avalos if (mode != LZMA_INDEX_ITER_STREAM) {
11182940b44dSPeter Avalos // Get the pointer to the current group. See iter_set_inf()
11192940b44dSPeter Avalos // for explanation.
11202940b44dSPeter Avalos switch (iter->internal[ITER_METHOD].s) {
11212940b44dSPeter Avalos case ITER_METHOD_NORMAL:
11222940b44dSPeter Avalos group = iter->internal[ITER_GROUP].p;
11232940b44dSPeter Avalos break;
11242940b44dSPeter Avalos
11252940b44dSPeter Avalos case ITER_METHOD_NEXT:
11262940b44dSPeter Avalos group = index_tree_next(iter->internal[ITER_GROUP].p);
11272940b44dSPeter Avalos break;
11282940b44dSPeter Avalos
11292940b44dSPeter Avalos case ITER_METHOD_LEFTMOST:
11302940b44dSPeter Avalos group = (const index_group *)(
11312940b44dSPeter Avalos stream->groups.leftmost);
11322940b44dSPeter Avalos break;
11332940b44dSPeter Avalos }
11342940b44dSPeter Avalos }
11352940b44dSPeter Avalos
11362940b44dSPeter Avalos again:
11372940b44dSPeter Avalos if (stream == NULL) {
11382940b44dSPeter Avalos // We at the beginning of the lzma_index.
11392940b44dSPeter Avalos // Locate the first Stream.
11402940b44dSPeter Avalos stream = (const index_stream *)(i->streams.leftmost);
11412940b44dSPeter Avalos if (mode >= LZMA_INDEX_ITER_BLOCK) {
11422940b44dSPeter Avalos // Since we are being asked to return information
11432940b44dSPeter Avalos // about the first a Block, skip Streams that have
11442940b44dSPeter Avalos // no Blocks.
11452940b44dSPeter Avalos while (stream->groups.leftmost == NULL) {
11462940b44dSPeter Avalos stream = index_tree_next(&stream->node);
11472940b44dSPeter Avalos if (stream == NULL)
11482940b44dSPeter Avalos return true;
11492940b44dSPeter Avalos }
11502940b44dSPeter Avalos }
11512940b44dSPeter Avalos
11522940b44dSPeter Avalos // Start from the first Record in the Stream.
11532940b44dSPeter Avalos group = (const index_group *)(stream->groups.leftmost);
11542940b44dSPeter Avalos record = 0;
11552940b44dSPeter Avalos
11562940b44dSPeter Avalos } else if (group != NULL && record < group->last) {
11572940b44dSPeter Avalos // The next Record is in the same group.
11582940b44dSPeter Avalos ++record;
11592940b44dSPeter Avalos
11602940b44dSPeter Avalos } else {
11612940b44dSPeter Avalos // This group has no more Records or this Stream has
11622940b44dSPeter Avalos // no Blocks at all.
11632940b44dSPeter Avalos record = 0;
11642940b44dSPeter Avalos
11652940b44dSPeter Avalos // If group is not NULL, this Stream has at least one Block
11662940b44dSPeter Avalos // and thus at least one group. Find the next group.
11672940b44dSPeter Avalos if (group != NULL)
11682940b44dSPeter Avalos group = index_tree_next(&group->node);
11692940b44dSPeter Avalos
11702940b44dSPeter Avalos if (group == NULL) {
11712940b44dSPeter Avalos // This Stream has no more Records. Find the next
11722940b44dSPeter Avalos // Stream. If we are being asked to return information
11732940b44dSPeter Avalos // about a Block, we skip empty Streams.
11742940b44dSPeter Avalos do {
11752940b44dSPeter Avalos stream = index_tree_next(&stream->node);
11762940b44dSPeter Avalos if (stream == NULL)
11772940b44dSPeter Avalos return true;
11782940b44dSPeter Avalos } while (mode >= LZMA_INDEX_ITER_BLOCK
11792940b44dSPeter Avalos && stream->groups.leftmost == NULL);
11802940b44dSPeter Avalos
11812940b44dSPeter Avalos group = (const index_group *)(
11822940b44dSPeter Avalos stream->groups.leftmost);
11832940b44dSPeter Avalos }
11842940b44dSPeter Avalos }
11852940b44dSPeter Avalos
11862940b44dSPeter Avalos if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) {
11872940b44dSPeter Avalos // We need to look for the next Block again if this Block
11882940b44dSPeter Avalos // is empty.
11892940b44dSPeter Avalos if (record == 0) {
11902940b44dSPeter Avalos if (group->node.uncompressed_base
11912940b44dSPeter Avalos == group->records[0].uncompressed_sum)
11922940b44dSPeter Avalos goto again;
11932940b44dSPeter Avalos } else if (group->records[record - 1].uncompressed_sum
11942940b44dSPeter Avalos == group->records[record].uncompressed_sum) {
11952940b44dSPeter Avalos goto again;
11962940b44dSPeter Avalos }
11972940b44dSPeter Avalos }
11982940b44dSPeter Avalos
11992940b44dSPeter Avalos iter->internal[ITER_STREAM].p = stream;
12002940b44dSPeter Avalos iter->internal[ITER_GROUP].p = group;
12012940b44dSPeter Avalos iter->internal[ITER_RECORD].s = record;
12022940b44dSPeter Avalos
12032940b44dSPeter Avalos iter_set_info(iter);
12042940b44dSPeter Avalos
12052940b44dSPeter Avalos return false;
12062940b44dSPeter Avalos }
12072940b44dSPeter Avalos
12082940b44dSPeter Avalos
12092940b44dSPeter Avalos extern LZMA_API(lzma_bool)
lzma_index_iter_locate(lzma_index_iter * iter,lzma_vli target)12102940b44dSPeter Avalos lzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target)
12112940b44dSPeter Avalos {
12122940b44dSPeter Avalos const lzma_index *i = iter->internal[ITER_INDEX].p;
12132940b44dSPeter Avalos
12142940b44dSPeter Avalos // If the target is past the end of the file, return immediately.
12152940b44dSPeter Avalos if (i->uncompressed_size <= target)
12162940b44dSPeter Avalos return true;
12172940b44dSPeter Avalos
12182940b44dSPeter Avalos // Locate the Stream containing the target offset.
12192940b44dSPeter Avalos const index_stream *stream = index_tree_locate(&i->streams, target);
12202940b44dSPeter Avalos assert(stream != NULL);
12212940b44dSPeter Avalos target -= stream->node.uncompressed_base;
12222940b44dSPeter Avalos
12232940b44dSPeter Avalos // Locate the group containing the target offset.
12242940b44dSPeter Avalos const index_group *group = index_tree_locate(&stream->groups, target);
12252940b44dSPeter Avalos assert(group != NULL);
12262940b44dSPeter Avalos
12272940b44dSPeter Avalos // Use binary search to locate the exact Record. It is the first
12282940b44dSPeter Avalos // Record whose uncompressed_sum is greater than target.
12292940b44dSPeter Avalos // This is because we want the rightmost Record that fullfills the
12302940b44dSPeter Avalos // search criterion. It is possible that there are empty Blocks;
12312940b44dSPeter Avalos // we don't want to return them.
12322940b44dSPeter Avalos size_t left = 0;
12332940b44dSPeter Avalos size_t right = group->last;
12342940b44dSPeter Avalos
12352940b44dSPeter Avalos while (left < right) {
12362940b44dSPeter Avalos const size_t pos = left + (right - left) / 2;
12372940b44dSPeter Avalos if (group->records[pos].uncompressed_sum <= target)
12382940b44dSPeter Avalos left = pos + 1;
12392940b44dSPeter Avalos else
12402940b44dSPeter Avalos right = pos;
12412940b44dSPeter Avalos }
12422940b44dSPeter Avalos
12432940b44dSPeter Avalos iter->internal[ITER_STREAM].p = stream;
12442940b44dSPeter Avalos iter->internal[ITER_GROUP].p = group;
12452940b44dSPeter Avalos iter->internal[ITER_RECORD].s = left;
12462940b44dSPeter Avalos
12472940b44dSPeter Avalos iter_set_info(iter);
12482940b44dSPeter Avalos
12492940b44dSPeter Avalos return false;
12502940b44dSPeter Avalos }
1251