1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file index.c 4207753Smm/// \brief Handling of .xz Indexes and some other Stream information 5207753Smm// 6207753Smm// Author: Lasse Collin 7207753Smm// 8207753Smm// This file has been put into the public domain. 9207753Smm// You can do whatever you want with this file. 10207753Smm// 11207753Smm/////////////////////////////////////////////////////////////////////////////// 12207753Smm 13207753Smm#include "index.h" 14207753Smm#include "stream_flags_common.h" 15207753Smm 16207753Smm 17207753Smm/// \brief How many Records to allocate at once 18207753Smm/// 19207753Smm/// This should be big enough to avoid making lots of tiny allocations 20207753Smm/// but small enough to avoid too much unused memory at once. 21215187Smm#define INDEX_GROUP_SIZE 512 22207753Smm 23207753Smm 24207753Smm/// \brief How many Records can be allocated at once at maximum 25207753Smm#define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record)) 26207753Smm 27207753Smm 28207753Smm/// \brief Base structure for index_stream and index_group structures 29207753Smmtypedef struct index_tree_node_s index_tree_node; 30207753Smmstruct index_tree_node_s { 31207753Smm /// Uncompressed start offset of this Stream (relative to the 32207753Smm /// beginning of the file) or Block (relative to the beginning 33207753Smm /// of the Stream) 34207753Smm lzma_vli uncompressed_base; 35207753Smm 36207753Smm /// Compressed start offset of this Stream or Block 37207753Smm lzma_vli compressed_base; 38207753Smm 39207753Smm index_tree_node *parent; 40207753Smm index_tree_node *left; 41207753Smm index_tree_node *right; 42207753Smm}; 43207753Smm 44207753Smm 45207753Smm/// \brief AVL tree to hold index_stream or index_group structures 46207753Smmtypedef struct { 47207753Smm /// Root node 48207753Smm index_tree_node *root; 49207753Smm 50207753Smm /// Leftmost node. Since the tree will be filled sequentially, 51207753Smm /// this won't change after the first node has been added to 52207753Smm /// the tree. 53207753Smm index_tree_node *leftmost; 54207753Smm 55207753Smm /// The rightmost node in the tree. Since the tree is filled 56207753Smm /// sequentially, this is always the node where to add the new data. 57207753Smm index_tree_node *rightmost; 58207753Smm 59207753Smm /// Number of nodes in the tree 60207753Smm uint32_t count; 61207753Smm 62207753Smm} index_tree; 63207753Smm 64207753Smm 65207753Smmtypedef struct { 66207753Smm lzma_vli uncompressed_sum; 67207753Smm lzma_vli unpadded_sum; 68207753Smm} index_record; 69207753Smm 70207753Smm 71207753Smmtypedef struct { 72207753Smm /// Every Record group is part of index_stream.groups tree. 73207753Smm index_tree_node node; 74207753Smm 75207753Smm /// Number of Blocks in this Stream before this group. 76207753Smm lzma_vli number_base; 77207753Smm 78207753Smm /// Number of Records that can be put in records[]. 79207753Smm size_t allocated; 80207753Smm 81207753Smm /// Index of the last Record in use. 82207753Smm size_t last; 83207753Smm 84207753Smm /// The sizes in this array are stored as cumulative sums relative 85207753Smm /// to the beginning of the Stream. This makes it possible to 86207753Smm /// use binary search in lzma_index_locate(). 87207753Smm /// 88207753Smm /// Note that the cumulative summing is done specially for 89207753Smm /// unpadded_sum: The previous value is rounded up to the next 90207753Smm /// multiple of four before adding the Unpadded Size of the new 91207753Smm /// Block. The total encoded size of the Blocks in the Stream 92207753Smm /// is records[last].unpadded_sum in the last Record group of 93207753Smm /// the Stream. 94207753Smm /// 95207753Smm /// For example, if the Unpadded Sizes are 39, 57, and 81, the 96207753Smm /// stored values are 39, 97 (40 + 57), and 181 (100 + 181). 97207753Smm /// The total encoded size of these Blocks is 184. 98207753Smm /// 99207753Smm /// This is a flexible array, because it makes easy to optimize 100207753Smm /// memory usage in case someone concatenates many Streams that 101207753Smm /// have only one or few Blocks. 102207753Smm index_record records[]; 103207753Smm 104207753Smm} index_group; 105207753Smm 106207753Smm 107207753Smmtypedef struct { 108207753Smm /// Every index_stream is a node in the tree of Sreams. 109207753Smm index_tree_node node; 110207753Smm 111207753Smm /// Number of this Stream (first one is 1) 112207753Smm uint32_t number; 113207753Smm 114207753Smm /// Total number of Blocks before this Stream 115207753Smm lzma_vli block_number_base; 116207753Smm 117207753Smm /// Record groups of this Stream are stored in a tree. 118207753Smm /// It's a T-tree with AVL-tree balancing. There are 119207753Smm /// INDEX_GROUP_SIZE Records per node by default. 120207753Smm /// This keeps the number of memory allocations reasonable 121207753Smm /// and finding a Record is fast. 122207753Smm index_tree groups; 123207753Smm 124207753Smm /// Number of Records in this Stream 125207753Smm lzma_vli record_count; 126207753Smm 127207753Smm /// Size of the List of Records field in this Stream. This is used 128207753Smm /// together with record_count to calculate the size of the Index 129207753Smm /// field and thus the total size of the Stream. 130207753Smm lzma_vli index_list_size; 131207753Smm 132207753Smm /// Stream Flags of this Stream. This is meaningful only if 133207753Smm /// the Stream Flags have been told us with lzma_index_stream_flags(). 134207753Smm /// Initially stream_flags.version is set to UINT32_MAX to indicate 135207753Smm /// that the Stream Flags are unknown. 136207753Smm lzma_stream_flags stream_flags; 137207753Smm 138207753Smm /// Amount of Stream Padding after this Stream. This defaults to 139207753Smm /// zero and can be set with lzma_index_stream_padding(). 140207753Smm lzma_vli stream_padding; 141207753Smm 142207753Smm} index_stream; 143207753Smm 144207753Smm 145207753Smmstruct lzma_index_s { 146207753Smm /// AVL-tree containing the Stream(s). Often there is just one 147207753Smm /// Stream, but using a tree keeps lookups fast even when there 148207753Smm /// are many concatenated Streams. 149207753Smm index_tree streams; 150207753Smm 151207753Smm /// Uncompressed size of all the Blocks in the Stream(s) 152207753Smm lzma_vli uncompressed_size; 153207753Smm 154207753Smm /// Total size of all the Blocks in the Stream(s) 155207753Smm lzma_vli total_size; 156207753Smm 157207753Smm /// Total number of Records in all Streams in this lzma_index 158207753Smm lzma_vli record_count; 159207753Smm 160207753Smm /// Size of the List of Records field if all the Streams in this 161207753Smm /// lzma_index were packed into a single Stream (makes it simpler to 162207753Smm /// take many .xz files and combine them into a single Stream). 163207753Smm /// 164207753Smm /// This value together with record_count is needed to calculate 165207753Smm /// Backward Size that is stored into Stream Footer. 166207753Smm lzma_vli index_list_size; 167207753Smm 168207753Smm /// How many Records to allocate at once in lzma_index_append(). 169207753Smm /// This defaults to INDEX_GROUP_SIZE but can be overriden with 170207753Smm /// lzma_index_prealloc(). 171207753Smm size_t prealloc; 172207753Smm 173207753Smm /// Bitmask indicating what integrity check types have been used 174207753Smm /// as set by lzma_index_stream_flags(). The bit of the last Stream 175207753Smm /// is not included here, since it is possible to change it by 176207753Smm /// calling lzma_index_stream_flags() again. 177207753Smm uint32_t checks; 178207753Smm}; 179207753Smm 180207753Smm 181207753Smmstatic void 182207753Smmindex_tree_init(index_tree *tree) 183207753Smm{ 184207753Smm tree->root = NULL; 185207753Smm tree->leftmost = NULL; 186207753Smm tree->rightmost = NULL; 187207753Smm tree->count = 0; 188207753Smm return; 189207753Smm} 190207753Smm 191207753Smm 192207753Smm/// Helper for index_tree_end() 193207753Smmstatic void 194292588Sdelphijindex_tree_node_end(index_tree_node *node, const lzma_allocator *allocator, 195292588Sdelphij void (*free_func)(void *node, const lzma_allocator *allocator)) 196207753Smm{ 197207753Smm // The tree won't ever be very huge, so recursion should be fine. 198207753Smm // 20 levels in the tree is likely quite a lot already in practice. 199207753Smm if (node->left != NULL) 200207753Smm index_tree_node_end(node->left, allocator, free_func); 201207753Smm 202207753Smm if (node->right != NULL) 203207753Smm index_tree_node_end(node->right, allocator, free_func); 204207753Smm 205312518Sdelphij free_func(node, allocator); 206207753Smm return; 207207753Smm} 208207753Smm 209207753Smm 210312518Sdelphij/// Free the memory allocated for a tree. Each node is freed using the 211312518Sdelphij/// given free_func which is either &lzma_free or &index_stream_end. 212312518Sdelphij/// The latter is used to free the Record groups from each index_stream 213312518Sdelphij/// before freeing the index_stream itself. 214207753Smmstatic void 215292588Sdelphijindex_tree_end(index_tree *tree, const lzma_allocator *allocator, 216292588Sdelphij void (*free_func)(void *node, const lzma_allocator *allocator)) 217207753Smm{ 218312518Sdelphij assert(free_func != NULL); 219312518Sdelphij 220207753Smm if (tree->root != NULL) 221207753Smm index_tree_node_end(tree->root, allocator, free_func); 222207753Smm 223207753Smm return; 224207753Smm} 225207753Smm 226207753Smm 227207753Smm/// Add a new node to the tree. node->uncompressed_base and 228207753Smm/// node->compressed_base must have been set by the caller already. 229207753Smmstatic void 230207753Smmindex_tree_append(index_tree *tree, index_tree_node *node) 231207753Smm{ 232207753Smm node->parent = tree->rightmost; 233207753Smm node->left = NULL; 234207753Smm node->right = NULL; 235207753Smm 236207753Smm ++tree->count; 237207753Smm 238207753Smm // Handle the special case of adding the first node. 239207753Smm if (tree->root == NULL) { 240207753Smm tree->root = node; 241207753Smm tree->leftmost = node; 242207753Smm tree->rightmost = node; 243207753Smm return; 244207753Smm } 245207753Smm 246207753Smm // The tree is always filled sequentially. 247207753Smm assert(tree->rightmost->uncompressed_base <= node->uncompressed_base); 248207753Smm assert(tree->rightmost->compressed_base < node->compressed_base); 249207753Smm 250207753Smm // Add the new node after the rightmost node. It's the correct 251207753Smm // place due to the reason above. 252207753Smm tree->rightmost->right = node; 253207753Smm tree->rightmost = node; 254207753Smm 255207753Smm // Balance the AVL-tree if needed. We don't need to keep the balance 256207753Smm // factors in nodes, because we always fill the tree sequentially, 257207753Smm // and thus know the state of the tree just by looking at the node 258207753Smm // count. From the node count we can calculate how many steps to go 259207753Smm // up in the tree to find the rotation root. 260207753Smm uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count)); 261207753Smm if (up != 0) { 262207753Smm // Locate the root node for the rotation. 263207753Smm up = ctz32(tree->count) + 2; 264207753Smm do { 265207753Smm node = node->parent; 266207753Smm } while (--up > 0); 267207753Smm 268207753Smm // Rotate left using node as the rotation root. 269207753Smm index_tree_node *pivot = node->right; 270207753Smm 271207753Smm if (node->parent == NULL) { 272207753Smm tree->root = pivot; 273207753Smm } else { 274207753Smm assert(node->parent->right == node); 275207753Smm node->parent->right = pivot; 276207753Smm } 277207753Smm 278207753Smm pivot->parent = node->parent; 279207753Smm 280207753Smm node->right = pivot->left; 281207753Smm if (node->right != NULL) 282207753Smm node->right->parent = node; 283207753Smm 284207753Smm pivot->left = node; 285207753Smm node->parent = pivot; 286207753Smm } 287207753Smm 288207753Smm return; 289207753Smm} 290207753Smm 291207753Smm 292207753Smm/// Get the next node in the tree. Return NULL if there are no more nodes. 293207753Smmstatic void * 294207753Smmindex_tree_next(const index_tree_node *node) 295207753Smm{ 296207753Smm if (node->right != NULL) { 297207753Smm node = node->right; 298207753Smm while (node->left != NULL) 299207753Smm node = node->left; 300207753Smm 301207753Smm return (void *)(node); 302207753Smm } 303207753Smm 304207753Smm while (node->parent != NULL && node->parent->right == node) 305207753Smm node = node->parent; 306207753Smm 307207753Smm return (void *)(node->parent); 308207753Smm} 309207753Smm 310207753Smm 311207753Smm/// Locate a node that contains the given uncompressed offset. It is 312207753Smm/// caller's job to check that target is not bigger than the uncompressed 313207753Smm/// size of the tree (the last node would be returned in that case still). 314207753Smmstatic void * 315207753Smmindex_tree_locate(const index_tree *tree, lzma_vli target) 316207753Smm{ 317207753Smm const index_tree_node *result = NULL; 318207753Smm const index_tree_node *node = tree->root; 319207753Smm 320207753Smm assert(tree->leftmost == NULL 321207753Smm || tree->leftmost->uncompressed_base == 0); 322207753Smm 323207753Smm // Consecutive nodes may have the same uncompressed_base. 324207753Smm // We must pick the rightmost one. 325207753Smm while (node != NULL) { 326207753Smm if (node->uncompressed_base > target) { 327207753Smm node = node->left; 328207753Smm } else { 329207753Smm result = node; 330207753Smm node = node->right; 331207753Smm } 332207753Smm } 333207753Smm 334207753Smm return (void *)(result); 335207753Smm} 336207753Smm 337207753Smm 338207753Smm/// Allocate and initialize a new Stream using the given base offsets. 339207753Smmstatic index_stream * 340207753Smmindex_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base, 341292588Sdelphij uint32_t stream_number, lzma_vli block_number_base, 342292588Sdelphij const lzma_allocator *allocator) 343207753Smm{ 344207753Smm index_stream *s = lzma_alloc(sizeof(index_stream), allocator); 345207753Smm if (s == NULL) 346207753Smm return NULL; 347207753Smm 348207753Smm s->node.uncompressed_base = uncompressed_base; 349207753Smm s->node.compressed_base = compressed_base; 350207753Smm s->node.parent = NULL; 351207753Smm s->node.left = NULL; 352207753Smm s->node.right = NULL; 353207753Smm 354207753Smm s->number = stream_number; 355207753Smm s->block_number_base = block_number_base; 356207753Smm 357207753Smm index_tree_init(&s->groups); 358207753Smm 359207753Smm s->record_count = 0; 360207753Smm s->index_list_size = 0; 361207753Smm s->stream_flags.version = UINT32_MAX; 362207753Smm s->stream_padding = 0; 363207753Smm 364207753Smm return s; 365207753Smm} 366207753Smm 367207753Smm 368207753Smm/// Free the memory allocated for a Stream and its Record groups. 369207753Smmstatic void 370292588Sdelphijindex_stream_end(void *node, const lzma_allocator *allocator) 371207753Smm{ 372207753Smm index_stream *s = node; 373312518Sdelphij index_tree_end(&s->groups, allocator, &lzma_free); 374312518Sdelphij lzma_free(s, allocator); 375207753Smm return; 376207753Smm} 377207753Smm 378207753Smm 379207753Smmstatic lzma_index * 380292588Sdelphijindex_init_plain(const lzma_allocator *allocator) 381207753Smm{ 382207753Smm lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator); 383207753Smm if (i != NULL) { 384207753Smm index_tree_init(&i->streams); 385207753Smm i->uncompressed_size = 0; 386207753Smm i->total_size = 0; 387207753Smm i->record_count = 0; 388207753Smm i->index_list_size = 0; 389207753Smm i->prealloc = INDEX_GROUP_SIZE; 390207753Smm i->checks = 0; 391207753Smm } 392207753Smm 393207753Smm return i; 394207753Smm} 395207753Smm 396207753Smm 397207753Smmextern LZMA_API(lzma_index *) 398292588Sdelphijlzma_index_init(const lzma_allocator *allocator) 399207753Smm{ 400207753Smm lzma_index *i = index_init_plain(allocator); 401223935Smm if (i == NULL) 402223935Smm return NULL; 403223935Smm 404207753Smm index_stream *s = index_stream_init(0, 0, 1, 0, allocator); 405223935Smm if (s == NULL) { 406207753Smm lzma_free(i, allocator); 407223935Smm return NULL; 408207753Smm } 409207753Smm 410207753Smm index_tree_append(&i->streams, &s->node); 411207753Smm 412207753Smm return i; 413207753Smm} 414207753Smm 415207753Smm 416207753Smmextern LZMA_API(void) 417292588Sdelphijlzma_index_end(lzma_index *i, const lzma_allocator *allocator) 418207753Smm{ 419207753Smm // NOTE: If you modify this function, check also the bottom 420207753Smm // of lzma_index_cat(). 421207753Smm if (i != NULL) { 422207753Smm index_tree_end(&i->streams, allocator, &index_stream_end); 423207753Smm lzma_free(i, allocator); 424207753Smm } 425207753Smm 426207753Smm return; 427207753Smm} 428207753Smm 429207753Smm 430207753Smmextern void 431207753Smmlzma_index_prealloc(lzma_index *i, lzma_vli records) 432207753Smm{ 433207753Smm if (records > PREALLOC_MAX) 434207753Smm records = PREALLOC_MAX; 435207753Smm 436207753Smm i->prealloc = (size_t)(records); 437207753Smm return; 438207753Smm} 439207753Smm 440207753Smm 441207753Smmextern LZMA_API(uint64_t) 442207753Smmlzma_index_memusage(lzma_vli streams, lzma_vli blocks) 443207753Smm{ 444207753Smm // This calculates an upper bound that is only a little bit 445207753Smm // bigger than the exact maximum memory usage with the given 446207753Smm // parameters. 447207753Smm 448207753Smm // Typical malloc() overhead is 2 * sizeof(void *) but we take 449207753Smm // a little bit extra just in case. Using LZMA_MEMUSAGE_BASE 450207753Smm // instead would give too inaccurate estimate. 451207753Smm const size_t alloc_overhead = 4 * sizeof(void *); 452207753Smm 453207753Smm // Amount of memory needed for each Stream base structures. 454207753Smm // We assume that every Stream has at least one Block and 455207753Smm // thus at least one group. 456207753Smm const size_t stream_base = sizeof(index_stream) 457207753Smm + sizeof(index_group) + 2 * alloc_overhead; 458207753Smm 459207753Smm // Amount of memory needed per group. 460207753Smm const size_t group_base = sizeof(index_group) 461207753Smm + INDEX_GROUP_SIZE * sizeof(index_record) 462207753Smm + alloc_overhead; 463207753Smm 464207753Smm // Number of groups. There may actually be more, but that overhead 465207753Smm // has been taken into account in stream_base already. 466207753Smm const lzma_vli groups 467207753Smm = (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE; 468207753Smm 469207753Smm // Memory used by index_stream and index_group structures. 470207753Smm const uint64_t streams_mem = streams * stream_base; 471207753Smm const uint64_t groups_mem = groups * group_base; 472207753Smm 473207753Smm // Memory used by the base structure. 474207753Smm const uint64_t index_base = sizeof(lzma_index) + alloc_overhead; 475207753Smm 476207753Smm // Validate the arguments and catch integer overflows. 477207753Smm // Maximum number of Streams is "only" UINT32_MAX, because 478207753Smm // that limit is used by the tree containing the Streams. 479207753Smm const uint64_t limit = UINT64_MAX - index_base; 480207753Smm if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX 481207753Smm || streams > limit / stream_base 482207753Smm || groups > limit / group_base 483207753Smm || limit - streams_mem < groups_mem) 484207753Smm return UINT64_MAX; 485207753Smm 486207753Smm return index_base + streams_mem + groups_mem; 487207753Smm} 488207753Smm 489207753Smm 490207753Smmextern LZMA_API(uint64_t) 491207753Smmlzma_index_memused(const lzma_index *i) 492207753Smm{ 493207753Smm return lzma_index_memusage(i->streams.count, i->record_count); 494207753Smm} 495207753Smm 496207753Smm 497207753Smmextern LZMA_API(lzma_vli) 498207753Smmlzma_index_block_count(const lzma_index *i) 499207753Smm{ 500207753Smm return i->record_count; 501207753Smm} 502207753Smm 503207753Smm 504207753Smmextern LZMA_API(lzma_vli) 505207753Smmlzma_index_stream_count(const lzma_index *i) 506207753Smm{ 507207753Smm return i->streams.count; 508207753Smm} 509207753Smm 510207753Smm 511207753Smmextern LZMA_API(lzma_vli) 512207753Smmlzma_index_size(const lzma_index *i) 513207753Smm{ 514207753Smm return index_size(i->record_count, i->index_list_size); 515207753Smm} 516207753Smm 517207753Smm 518207753Smmextern LZMA_API(lzma_vli) 519207753Smmlzma_index_total_size(const lzma_index *i) 520207753Smm{ 521207753Smm return i->total_size; 522207753Smm} 523207753Smm 524207753Smm 525207753Smmextern LZMA_API(lzma_vli) 526207753Smmlzma_index_stream_size(const lzma_index *i) 527207753Smm{ 528207753Smm // Stream Header + Blocks + Index + Stream Footer 529207753Smm return LZMA_STREAM_HEADER_SIZE + i->total_size 530207753Smm + index_size(i->record_count, i->index_list_size) 531207753Smm + LZMA_STREAM_HEADER_SIZE; 532207753Smm} 533207753Smm 534207753Smm 535207753Smmstatic lzma_vli 536207753Smmindex_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum, 537207753Smm lzma_vli record_count, lzma_vli index_list_size, 538207753Smm lzma_vli stream_padding) 539207753Smm{ 540207753Smm // Earlier Streams and Stream Paddings + Stream Header 541207753Smm // + Blocks + Index + Stream Footer + Stream Padding 542207753Smm // 543207753Smm // This might go over LZMA_VLI_MAX due to too big unpadded_sum 544207753Smm // when this function is used in lzma_index_append(). 545207753Smm lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE 546207753Smm + stream_padding + vli_ceil4(unpadded_sum); 547207753Smm if (file_size > LZMA_VLI_MAX) 548207753Smm return LZMA_VLI_UNKNOWN; 549207753Smm 550207753Smm // The same applies here. 551207753Smm file_size += index_size(record_count, index_list_size); 552207753Smm if (file_size > LZMA_VLI_MAX) 553207753Smm return LZMA_VLI_UNKNOWN; 554207753Smm 555207753Smm return file_size; 556207753Smm} 557207753Smm 558207753Smm 559207753Smmextern LZMA_API(lzma_vli) 560207753Smmlzma_index_file_size(const lzma_index *i) 561207753Smm{ 562207753Smm const index_stream *s = (const index_stream *)(i->streams.rightmost); 563207753Smm const index_group *g = (const index_group *)(s->groups.rightmost); 564207753Smm return index_file_size(s->node.compressed_base, 565207753Smm g == NULL ? 0 : g->records[g->last].unpadded_sum, 566207753Smm s->record_count, s->index_list_size, 567207753Smm s->stream_padding); 568207753Smm} 569207753Smm 570207753Smm 571207753Smmextern LZMA_API(lzma_vli) 572207753Smmlzma_index_uncompressed_size(const lzma_index *i) 573207753Smm{ 574207753Smm return i->uncompressed_size; 575207753Smm} 576207753Smm 577207753Smm 578207753Smmextern LZMA_API(uint32_t) 579207753Smmlzma_index_checks(const lzma_index *i) 580207753Smm{ 581207753Smm uint32_t checks = i->checks; 582207753Smm 583207753Smm // Get the type of the Check of the last Stream too. 584207753Smm const index_stream *s = (const index_stream *)(i->streams.rightmost); 585207753Smm if (s->stream_flags.version != UINT32_MAX) 586207753Smm checks |= UINT32_C(1) << s->stream_flags.check; 587207753Smm 588207753Smm return checks; 589207753Smm} 590207753Smm 591207753Smm 592207753Smmextern uint32_t 593207753Smmlzma_index_padding_size(const lzma_index *i) 594207753Smm{ 595207753Smm return (LZMA_VLI_C(4) - index_size_unpadded( 596207753Smm i->record_count, i->index_list_size)) & 3; 597207753Smm} 598207753Smm 599207753Smm 600207753Smmextern LZMA_API(lzma_ret) 601207753Smmlzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags) 602207753Smm{ 603207753Smm if (i == NULL || stream_flags == NULL) 604207753Smm return LZMA_PROG_ERROR; 605207753Smm 606207753Smm // Validate the Stream Flags. 607207753Smm return_if_error(lzma_stream_flags_compare( 608207753Smm stream_flags, stream_flags)); 609207753Smm 610207753Smm index_stream *s = (index_stream *)(i->streams.rightmost); 611207753Smm s->stream_flags = *stream_flags; 612207753Smm 613207753Smm return LZMA_OK; 614207753Smm} 615207753Smm 616207753Smm 617207753Smmextern LZMA_API(lzma_ret) 618207753Smmlzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding) 619207753Smm{ 620207753Smm if (i == NULL || stream_padding > LZMA_VLI_MAX 621207753Smm || (stream_padding & 3) != 0) 622207753Smm return LZMA_PROG_ERROR; 623207753Smm 624207753Smm index_stream *s = (index_stream *)(i->streams.rightmost); 625207753Smm 626207753Smm // Check that the new value won't make the file grow too big. 627207753Smm const lzma_vli old_stream_padding = s->stream_padding; 628207753Smm s->stream_padding = 0; 629207753Smm if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) { 630207753Smm s->stream_padding = old_stream_padding; 631207753Smm return LZMA_DATA_ERROR; 632207753Smm } 633207753Smm 634207753Smm s->stream_padding = stream_padding; 635207753Smm return LZMA_OK; 636207753Smm} 637207753Smm 638207753Smm 639207753Smmextern LZMA_API(lzma_ret) 640292588Sdelphijlzma_index_append(lzma_index *i, const lzma_allocator *allocator, 641207753Smm lzma_vli unpadded_size, lzma_vli uncompressed_size) 642207753Smm{ 643207753Smm // Validate. 644207753Smm if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN 645207753Smm || unpadded_size > UNPADDED_SIZE_MAX 646207753Smm || uncompressed_size > LZMA_VLI_MAX) 647207753Smm return LZMA_PROG_ERROR; 648207753Smm 649207753Smm index_stream *s = (index_stream *)(i->streams.rightmost); 650207753Smm index_group *g = (index_group *)(s->groups.rightmost); 651207753Smm 652207753Smm const lzma_vli compressed_base = g == NULL ? 0 653207753Smm : vli_ceil4(g->records[g->last].unpadded_sum); 654207753Smm const lzma_vli uncompressed_base = g == NULL ? 0 655207753Smm : g->records[g->last].uncompressed_sum; 656207753Smm const uint32_t index_list_size_add = lzma_vli_size(unpadded_size) 657207753Smm + lzma_vli_size(uncompressed_size); 658207753Smm 659207753Smm // Check that the file size will stay within limits. 660207753Smm if (index_file_size(s->node.compressed_base, 661207753Smm compressed_base + unpadded_size, s->record_count + 1, 662207753Smm s->index_list_size + index_list_size_add, 663207753Smm s->stream_padding) == LZMA_VLI_UNKNOWN) 664207753Smm return LZMA_DATA_ERROR; 665207753Smm 666207753Smm // The size of the Index field must not exceed the maximum value 667207753Smm // that can be stored in the Backward Size field. 668207753Smm if (index_size(i->record_count + 1, 669207753Smm i->index_list_size + index_list_size_add) 670207753Smm > LZMA_BACKWARD_SIZE_MAX) 671207753Smm return LZMA_DATA_ERROR; 672207753Smm 673207753Smm if (g != NULL && g->last + 1 < g->allocated) { 674207753Smm // There is space in the last group at least for one Record. 675207753Smm ++g->last; 676207753Smm } else { 677207753Smm // We need to allocate a new group. 678207753Smm g = lzma_alloc(sizeof(index_group) 679207753Smm + i->prealloc * sizeof(index_record), 680207753Smm allocator); 681207753Smm if (g == NULL) 682207753Smm return LZMA_MEM_ERROR; 683207753Smm 684207753Smm g->last = 0; 685207753Smm g->allocated = i->prealloc; 686207753Smm 687207753Smm // Reset prealloc so that if the application happens to 688207753Smm // add new Records, the allocation size will be sane. 689207753Smm i->prealloc = INDEX_GROUP_SIZE; 690207753Smm 691207753Smm // Set the start offsets of this group. 692207753Smm g->node.uncompressed_base = uncompressed_base; 693207753Smm g->node.compressed_base = compressed_base; 694207753Smm g->number_base = s->record_count + 1; 695207753Smm 696207753Smm // Add the new group to the Stream. 697207753Smm index_tree_append(&s->groups, &g->node); 698207753Smm } 699207753Smm 700207753Smm // Add the new Record to the group. 701207753Smm g->records[g->last].uncompressed_sum 702207753Smm = uncompressed_base + uncompressed_size; 703207753Smm g->records[g->last].unpadded_sum 704207753Smm = compressed_base + unpadded_size; 705207753Smm 706207753Smm // Update the totals. 707207753Smm ++s->record_count; 708207753Smm s->index_list_size += index_list_size_add; 709207753Smm 710207753Smm i->total_size += vli_ceil4(unpadded_size); 711207753Smm i->uncompressed_size += uncompressed_size; 712207753Smm ++i->record_count; 713207753Smm i->index_list_size += index_list_size_add; 714207753Smm 715207753Smm return LZMA_OK; 716207753Smm} 717207753Smm 718207753Smm 719207753Smm/// Structure to pass info to index_cat_helper() 720207753Smmtypedef struct { 721207753Smm /// Uncompressed size of the destination 722207753Smm lzma_vli uncompressed_size; 723207753Smm 724207753Smm /// Compressed file size of the destination 725207753Smm lzma_vli file_size; 726207753Smm 727207753Smm /// Same as above but for Block numbers 728207753Smm lzma_vli block_number_add; 729207753Smm 730207753Smm /// Number of Streams that were in the destination index before we 731207753Smm /// started appending new Streams from the source index. This is 732207753Smm /// used to fix the Stream numbering. 733207753Smm uint32_t stream_number_add; 734207753Smm 735207753Smm /// Destination index' Stream tree 736207753Smm index_tree *streams; 737207753Smm 738207753Smm} index_cat_info; 739207753Smm 740207753Smm 741207753Smm/// Add the Stream nodes from the source index to dest using recursion. 742207753Smm/// Simplest iterative traversal of the source tree wouldn't work, because 743207753Smm/// we update the pointers in nodes when moving them to the destination tree. 744207753Smmstatic void 745207753Smmindex_cat_helper(const index_cat_info *info, index_stream *this) 746207753Smm{ 747207753Smm index_stream *left = (index_stream *)(this->node.left); 748207753Smm index_stream *right = (index_stream *)(this->node.right); 749207753Smm 750207753Smm if (left != NULL) 751207753Smm index_cat_helper(info, left); 752207753Smm 753207753Smm this->node.uncompressed_base += info->uncompressed_size; 754207753Smm this->node.compressed_base += info->file_size; 755207753Smm this->number += info->stream_number_add; 756207753Smm this->block_number_base += info->block_number_add; 757207753Smm index_tree_append(info->streams, &this->node); 758207753Smm 759207753Smm if (right != NULL) 760207753Smm index_cat_helper(info, right); 761207753Smm 762207753Smm return; 763207753Smm} 764207753Smm 765207753Smm 766207753Smmextern LZMA_API(lzma_ret) 767207753Smmlzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src, 768292588Sdelphij const lzma_allocator *allocator) 769207753Smm{ 770207753Smm const lzma_vli dest_file_size = lzma_index_file_size(dest); 771207753Smm 772207753Smm // Check that we don't exceed the file size limits. 773207753Smm if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX 774207753Smm || dest->uncompressed_size + src->uncompressed_size 775207753Smm > LZMA_VLI_MAX) 776207753Smm return LZMA_DATA_ERROR; 777207753Smm 778207753Smm // Check that the encoded size of the combined lzma_indexes stays 779207753Smm // within limits. In theory, this should be done only if we know 780207753Smm // that the user plans to actually combine the Streams and thus 781207753Smm // construct a single Index (probably rare). However, exceeding 782207753Smm // this limit is quite theoretical, so we do this check always 783207753Smm // to simplify things elsewhere. 784207753Smm { 785207753Smm const lzma_vli dest_size = index_size_unpadded( 786207753Smm dest->record_count, dest->index_list_size); 787207753Smm const lzma_vli src_size = index_size_unpadded( 788207753Smm src->record_count, src->index_list_size); 789207753Smm if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX) 790207753Smm return LZMA_DATA_ERROR; 791207753Smm } 792207753Smm 793207753Smm // Optimize the last group to minimize memory usage. Allocation has 794207753Smm // to be done before modifying dest or src. 795207753Smm { 796207753Smm index_stream *s = (index_stream *)(dest->streams.rightmost); 797207753Smm index_group *g = (index_group *)(s->groups.rightmost); 798207753Smm if (g != NULL && g->last + 1 < g->allocated) { 799207753Smm assert(g->node.left == NULL); 800207753Smm assert(g->node.right == NULL); 801207753Smm 802207753Smm index_group *newg = lzma_alloc(sizeof(index_group) 803207753Smm + (g->last + 1) 804207753Smm * sizeof(index_record), 805207753Smm allocator); 806207753Smm if (newg == NULL) 807207753Smm return LZMA_MEM_ERROR; 808207753Smm 809207753Smm newg->node = g->node; 810207753Smm newg->allocated = g->last + 1; 811207753Smm newg->last = g->last; 812207753Smm newg->number_base = g->number_base; 813207753Smm 814207753Smm memcpy(newg->records, g->records, newg->allocated 815207753Smm * sizeof(index_record)); 816207753Smm 817207753Smm if (g->node.parent != NULL) { 818207753Smm assert(g->node.parent->right == &g->node); 819207753Smm g->node.parent->right = &newg->node; 820207753Smm } 821207753Smm 822207753Smm if (s->groups.leftmost == &g->node) { 823207753Smm assert(s->groups.root == &g->node); 824207753Smm s->groups.leftmost = &newg->node; 825207753Smm s->groups.root = &newg->node; 826207753Smm } 827207753Smm 828207753Smm if (s->groups.rightmost == &g->node) 829207753Smm s->groups.rightmost = &newg->node; 830207753Smm 831207753Smm lzma_free(g, allocator); 832312518Sdelphij 833312518Sdelphij // NOTE: newg isn't leaked here because 834312518Sdelphij // newg == (void *)&newg->node. 835207753Smm } 836207753Smm } 837207753Smm 838207753Smm // Add all the Streams from src to dest. Update the base offsets 839207753Smm // of each Stream from src. 840207753Smm const index_cat_info info = { 841207753Smm .uncompressed_size = dest->uncompressed_size, 842207753Smm .file_size = dest_file_size, 843207753Smm .stream_number_add = dest->streams.count, 844207753Smm .block_number_add = dest->record_count, 845207753Smm .streams = &dest->streams, 846207753Smm }; 847207753Smm index_cat_helper(&info, (index_stream *)(src->streams.root)); 848207753Smm 849207753Smm // Update info about all the combined Streams. 850207753Smm dest->uncompressed_size += src->uncompressed_size; 851207753Smm dest->total_size += src->total_size; 852207753Smm dest->record_count += src->record_count; 853207753Smm dest->index_list_size += src->index_list_size; 854207753Smm dest->checks = lzma_index_checks(dest) | src->checks; 855207753Smm 856207753Smm // There's nothing else left in src than the base structure. 857207753Smm lzma_free(src, allocator); 858207753Smm 859207753Smm return LZMA_OK; 860207753Smm} 861207753Smm 862207753Smm 863207753Smm/// Duplicate an index_stream. 864207753Smmstatic index_stream * 865292588Sdelphijindex_dup_stream(const index_stream *src, const lzma_allocator *allocator) 866207753Smm{ 867207753Smm // Catch a somewhat theoretical integer overflow. 868207753Smm if (src->record_count > PREALLOC_MAX) 869207753Smm return NULL; 870207753Smm 871207753Smm // Allocate and initialize a new Stream. 872207753Smm index_stream *dest = index_stream_init(src->node.compressed_base, 873207753Smm src->node.uncompressed_base, src->number, 874207753Smm src->block_number_base, allocator); 875312518Sdelphij if (dest == NULL) 876312518Sdelphij return NULL; 877207753Smm 878207753Smm // Copy the overall information. 879207753Smm dest->record_count = src->record_count; 880207753Smm dest->index_list_size = src->index_list_size; 881207753Smm dest->stream_flags = src->stream_flags; 882207753Smm dest->stream_padding = src->stream_padding; 883207753Smm 884312518Sdelphij // Return if there are no groups to duplicate. 885312518Sdelphij if (src->groups.leftmost == NULL) 886312518Sdelphij return dest; 887312518Sdelphij 888207753Smm // Allocate memory for the Records. We put all the Records into 889207753Smm // a single group. It's simplest and also tends to make 890207753Smm // lzma_index_locate() a little bit faster with very big Indexes. 891207753Smm index_group *destg = lzma_alloc(sizeof(index_group) 892207753Smm + src->record_count * sizeof(index_record), 893207753Smm allocator); 894207753Smm if (destg == NULL) { 895207753Smm index_stream_end(dest, allocator); 896207753Smm return NULL; 897207753Smm } 898207753Smm 899207753Smm // Initialize destg. 900207753Smm destg->node.uncompressed_base = 0; 901207753Smm destg->node.compressed_base = 0; 902207753Smm destg->number_base = 1; 903207753Smm destg->allocated = src->record_count; 904207753Smm destg->last = src->record_count - 1; 905207753Smm 906207753Smm // Go through all the groups in src and copy the Records into destg. 907207753Smm const index_group *srcg = (const index_group *)(src->groups.leftmost); 908207753Smm size_t i = 0; 909207753Smm do { 910207753Smm memcpy(destg->records + i, srcg->records, 911207753Smm (srcg->last + 1) * sizeof(index_record)); 912207753Smm i += srcg->last + 1; 913207753Smm srcg = index_tree_next(&srcg->node); 914207753Smm } while (srcg != NULL); 915207753Smm 916207753Smm assert(i == destg->allocated); 917207753Smm 918207753Smm // Add the group to the new Stream. 919207753Smm index_tree_append(&dest->groups, &destg->node); 920207753Smm 921207753Smm return dest; 922207753Smm} 923207753Smm 924207753Smm 925207753Smmextern LZMA_API(lzma_index *) 926292588Sdelphijlzma_index_dup(const lzma_index *src, const lzma_allocator *allocator) 927207753Smm{ 928207753Smm // Allocate the base structure (no initial Stream). 929207753Smm lzma_index *dest = index_init_plain(allocator); 930207753Smm if (dest == NULL) 931207753Smm return NULL; 932207753Smm 933207753Smm // Copy the totals. 934207753Smm dest->uncompressed_size = src->uncompressed_size; 935207753Smm dest->total_size = src->total_size; 936207753Smm dest->record_count = src->record_count; 937207753Smm dest->index_list_size = src->index_list_size; 938207753Smm 939207753Smm // Copy the Streams and the groups in them. 940207753Smm const index_stream *srcstream 941207753Smm = (const index_stream *)(src->streams.leftmost); 942207753Smm do { 943207753Smm index_stream *deststream = index_dup_stream( 944207753Smm srcstream, allocator); 945207753Smm if (deststream == NULL) { 946207753Smm lzma_index_end(dest, allocator); 947207753Smm return NULL; 948207753Smm } 949207753Smm 950207753Smm index_tree_append(&dest->streams, &deststream->node); 951207753Smm 952207753Smm srcstream = index_tree_next(&srcstream->node); 953207753Smm } while (srcstream != NULL); 954207753Smm 955207753Smm return dest; 956207753Smm} 957207753Smm 958207753Smm 959207753Smm/// Indexing for lzma_index_iter.internal[] 960207753Smmenum { 961207753Smm ITER_INDEX, 962207753Smm ITER_STREAM, 963207753Smm ITER_GROUP, 964207753Smm ITER_RECORD, 965207753Smm ITER_METHOD, 966207753Smm}; 967207753Smm 968207753Smm 969207753Smm/// Values for lzma_index_iter.internal[ITER_METHOD].s 970207753Smmenum { 971207753Smm ITER_METHOD_NORMAL, 972207753Smm ITER_METHOD_NEXT, 973207753Smm ITER_METHOD_LEFTMOST, 974207753Smm}; 975207753Smm 976207753Smm 977207753Smmstatic void 978207753Smmiter_set_info(lzma_index_iter *iter) 979207753Smm{ 980207753Smm const lzma_index *i = iter->internal[ITER_INDEX].p; 981207753Smm const index_stream *stream = iter->internal[ITER_STREAM].p; 982207753Smm const index_group *group = iter->internal[ITER_GROUP].p; 983207753Smm const size_t record = iter->internal[ITER_RECORD].s; 984207753Smm 985207753Smm // lzma_index_iter.internal must not contain a pointer to the last 986207753Smm // group in the index, because that may be reallocated by 987207753Smm // lzma_index_cat(). 988207753Smm if (group == NULL) { 989207753Smm // There are no groups. 990207753Smm assert(stream->groups.root == NULL); 991207753Smm iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST; 992207753Smm 993207753Smm } else if (i->streams.rightmost != &stream->node 994207753Smm || stream->groups.rightmost != &group->node) { 995207753Smm // The group is not not the last group in the index. 996207753Smm iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL; 997207753Smm 998207753Smm } else if (stream->groups.leftmost != &group->node) { 999207753Smm // The group isn't the only group in the Stream, thus we 1000207753Smm // know that it must have a parent group i.e. it's not 1001207753Smm // the root node. 1002207753Smm assert(stream->groups.root != &group->node); 1003207753Smm assert(group->node.parent->right == &group->node); 1004207753Smm iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT; 1005207753Smm iter->internal[ITER_GROUP].p = group->node.parent; 1006207753Smm 1007207753Smm } else { 1008207753Smm // The Stream has only one group. 1009207753Smm assert(stream->groups.root == &group->node); 1010207753Smm assert(group->node.parent == NULL); 1011207753Smm iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST; 1012207753Smm iter->internal[ITER_GROUP].p = NULL; 1013207753Smm } 1014207753Smm 1015292588Sdelphij // NOTE: lzma_index_iter.stream.number is lzma_vli but we use uint32_t 1016292588Sdelphij // internally. 1017207753Smm iter->stream.number = stream->number; 1018207753Smm iter->stream.block_count = stream->record_count; 1019207753Smm iter->stream.compressed_offset = stream->node.compressed_base; 1020207753Smm iter->stream.uncompressed_offset = stream->node.uncompressed_base; 1021207753Smm 1022207753Smm // iter->stream.flags will be NULL if the Stream Flags haven't been 1023207753Smm // set with lzma_index_stream_flags(). 1024207753Smm iter->stream.flags = stream->stream_flags.version == UINT32_MAX 1025207753Smm ? NULL : &stream->stream_flags; 1026207753Smm iter->stream.padding = stream->stream_padding; 1027207753Smm 1028207753Smm if (stream->groups.rightmost == NULL) { 1029207753Smm // Stream has no Blocks. 1030207753Smm iter->stream.compressed_size = index_size(0, 0) 1031207753Smm + 2 * LZMA_STREAM_HEADER_SIZE; 1032207753Smm iter->stream.uncompressed_size = 0; 1033207753Smm } else { 1034207753Smm const index_group *g = (const index_group *)( 1035207753Smm stream->groups.rightmost); 1036207753Smm 1037207753Smm // Stream Header + Stream Footer + Index + Blocks 1038207753Smm iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE 1039207753Smm + index_size(stream->record_count, 1040207753Smm stream->index_list_size) 1041207753Smm + vli_ceil4(g->records[g->last].unpadded_sum); 1042207753Smm iter->stream.uncompressed_size 1043207753Smm = g->records[g->last].uncompressed_sum; 1044207753Smm } 1045207753Smm 1046207753Smm if (group != NULL) { 1047207753Smm iter->block.number_in_stream = group->number_base + record; 1048207753Smm iter->block.number_in_file = iter->block.number_in_stream 1049207753Smm + stream->block_number_base; 1050207753Smm 1051207753Smm iter->block.compressed_stream_offset 1052207753Smm = record == 0 ? group->node.compressed_base 1053207753Smm : vli_ceil4(group->records[ 1054207753Smm record - 1].unpadded_sum); 1055207753Smm iter->block.uncompressed_stream_offset 1056207753Smm = record == 0 ? group->node.uncompressed_base 1057207753Smm : group->records[record - 1].uncompressed_sum; 1058207753Smm 1059207753Smm iter->block.uncompressed_size 1060207753Smm = group->records[record].uncompressed_sum 1061207753Smm - iter->block.uncompressed_stream_offset; 1062207753Smm iter->block.unpadded_size 1063207753Smm = group->records[record].unpadded_sum 1064207753Smm - iter->block.compressed_stream_offset; 1065207753Smm iter->block.total_size = vli_ceil4(iter->block.unpadded_size); 1066207753Smm 1067207753Smm iter->block.compressed_stream_offset 1068207753Smm += LZMA_STREAM_HEADER_SIZE; 1069207753Smm 1070207753Smm iter->block.compressed_file_offset 1071207753Smm = iter->block.compressed_stream_offset 1072207753Smm + iter->stream.compressed_offset; 1073207753Smm iter->block.uncompressed_file_offset 1074207753Smm = iter->block.uncompressed_stream_offset 1075207753Smm + iter->stream.uncompressed_offset; 1076207753Smm } 1077207753Smm 1078207753Smm return; 1079207753Smm} 1080207753Smm 1081207753Smm 1082207753Smmextern LZMA_API(void) 1083207753Smmlzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i) 1084207753Smm{ 1085207753Smm iter->internal[ITER_INDEX].p = i; 1086207753Smm lzma_index_iter_rewind(iter); 1087207753Smm return; 1088207753Smm} 1089207753Smm 1090207753Smm 1091207753Smmextern LZMA_API(void) 1092207753Smmlzma_index_iter_rewind(lzma_index_iter *iter) 1093207753Smm{ 1094207753Smm iter->internal[ITER_STREAM].p = NULL; 1095207753Smm iter->internal[ITER_GROUP].p = NULL; 1096207753Smm iter->internal[ITER_RECORD].s = 0; 1097207753Smm iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL; 1098207753Smm return; 1099207753Smm} 1100207753Smm 1101207753Smm 1102207753Smmextern LZMA_API(lzma_bool) 1103207753Smmlzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode) 1104207753Smm{ 1105207753Smm // Catch unsupported mode values. 1106207753Smm if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK) 1107207753Smm return true; 1108207753Smm 1109207753Smm const lzma_index *i = iter->internal[ITER_INDEX].p; 1110207753Smm const index_stream *stream = iter->internal[ITER_STREAM].p; 1111207753Smm const index_group *group = NULL; 1112207753Smm size_t record = iter->internal[ITER_RECORD].s; 1113207753Smm 1114207753Smm // If we are being asked for the next Stream, leave group to NULL 1115207753Smm // so that the rest of the this function thinks that this Stream 1116207753Smm // has no groups and will thus go to the next Stream. 1117207753Smm if (mode != LZMA_INDEX_ITER_STREAM) { 1118207753Smm // Get the pointer to the current group. See iter_set_inf() 1119207753Smm // for explanation. 1120207753Smm switch (iter->internal[ITER_METHOD].s) { 1121207753Smm case ITER_METHOD_NORMAL: 1122207753Smm group = iter->internal[ITER_GROUP].p; 1123207753Smm break; 1124207753Smm 1125207753Smm case ITER_METHOD_NEXT: 1126207753Smm group = index_tree_next(iter->internal[ITER_GROUP].p); 1127207753Smm break; 1128207753Smm 1129207753Smm case ITER_METHOD_LEFTMOST: 1130207753Smm group = (const index_group *)( 1131207753Smm stream->groups.leftmost); 1132207753Smm break; 1133207753Smm } 1134207753Smm } 1135207753Smm 1136207753Smmagain: 1137207753Smm if (stream == NULL) { 1138207753Smm // We at the beginning of the lzma_index. 1139207753Smm // Locate the first Stream. 1140207753Smm stream = (const index_stream *)(i->streams.leftmost); 1141207753Smm if (mode >= LZMA_INDEX_ITER_BLOCK) { 1142207753Smm // Since we are being asked to return information 1143207753Smm // about the first a Block, skip Streams that have 1144207753Smm // no Blocks. 1145207753Smm while (stream->groups.leftmost == NULL) { 1146207753Smm stream = index_tree_next(&stream->node); 1147207753Smm if (stream == NULL) 1148207753Smm return true; 1149207753Smm } 1150207753Smm } 1151207753Smm 1152207753Smm // Start from the first Record in the Stream. 1153207753Smm group = (const index_group *)(stream->groups.leftmost); 1154207753Smm record = 0; 1155207753Smm 1156207753Smm } else if (group != NULL && record < group->last) { 1157207753Smm // The next Record is in the same group. 1158207753Smm ++record; 1159207753Smm 1160207753Smm } else { 1161207753Smm // This group has no more Records or this Stream has 1162207753Smm // no Blocks at all. 1163207753Smm record = 0; 1164207753Smm 1165207753Smm // If group is not NULL, this Stream has at least one Block 1166207753Smm // and thus at least one group. Find the next group. 1167207753Smm if (group != NULL) 1168207753Smm group = index_tree_next(&group->node); 1169207753Smm 1170207753Smm if (group == NULL) { 1171207753Smm // This Stream has no more Records. Find the next 1172207753Smm // Stream. If we are being asked to return information 1173207753Smm // about a Block, we skip empty Streams. 1174207753Smm do { 1175207753Smm stream = index_tree_next(&stream->node); 1176207753Smm if (stream == NULL) 1177207753Smm return true; 1178207753Smm } while (mode >= LZMA_INDEX_ITER_BLOCK 1179207753Smm && stream->groups.leftmost == NULL); 1180207753Smm 1181207753Smm group = (const index_group *)( 1182207753Smm stream->groups.leftmost); 1183207753Smm } 1184207753Smm } 1185207753Smm 1186207753Smm if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) { 1187207753Smm // We need to look for the next Block again if this Block 1188207753Smm // is empty. 1189207753Smm if (record == 0) { 1190207753Smm if (group->node.uncompressed_base 1191207753Smm == group->records[0].uncompressed_sum) 1192207753Smm goto again; 1193207753Smm } else if (group->records[record - 1].uncompressed_sum 1194207753Smm == group->records[record].uncompressed_sum) { 1195207753Smm goto again; 1196207753Smm } 1197207753Smm } 1198207753Smm 1199207753Smm iter->internal[ITER_STREAM].p = stream; 1200207753Smm iter->internal[ITER_GROUP].p = group; 1201207753Smm iter->internal[ITER_RECORD].s = record; 1202207753Smm 1203207753Smm iter_set_info(iter); 1204207753Smm 1205207753Smm return false; 1206207753Smm} 1207207753Smm 1208207753Smm 1209207753Smmextern LZMA_API(lzma_bool) 1210207753Smmlzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target) 1211207753Smm{ 1212207753Smm const lzma_index *i = iter->internal[ITER_INDEX].p; 1213207753Smm 1214207753Smm // If the target is past the end of the file, return immediately. 1215207753Smm if (i->uncompressed_size <= target) 1216207753Smm return true; 1217207753Smm 1218207753Smm // Locate the Stream containing the target offset. 1219207753Smm const index_stream *stream = index_tree_locate(&i->streams, target); 1220207753Smm assert(stream != NULL); 1221207753Smm target -= stream->node.uncompressed_base; 1222207753Smm 1223207753Smm // Locate the group containing the target offset. 1224207753Smm const index_group *group = index_tree_locate(&stream->groups, target); 1225207753Smm assert(group != NULL); 1226207753Smm 1227207753Smm // Use binary search to locate the exact Record. It is the first 1228207753Smm // Record whose uncompressed_sum is greater than target. 1229207753Smm // This is because we want the rightmost Record that fullfills the 1230207753Smm // search criterion. It is possible that there are empty Blocks; 1231207753Smm // we don't want to return them. 1232207753Smm size_t left = 0; 1233207753Smm size_t right = group->last; 1234207753Smm 1235207753Smm while (left < right) { 1236207753Smm const size_t pos = left + (right - left) / 2; 1237207753Smm if (group->records[pos].uncompressed_sum <= target) 1238207753Smm left = pos + 1; 1239207753Smm else 1240207753Smm right = pos; 1241207753Smm } 1242207753Smm 1243207753Smm iter->internal[ITER_STREAM].p = stream; 1244207753Smm iter->internal[ITER_GROUP].p = group; 1245207753Smm iter->internal[ITER_RECORD].s = left; 1246207753Smm 1247207753Smm iter_set_info(iter); 1248207753Smm 1249207753Smm return false; 1250207753Smm} 1251