1 /////////////////////////////////////////////////////////////////////////////// 2 // 3 /// \file index.c 4 /// \brief Handling of .xz Indexes and some other Stream information 5 // 6 // Author: Lasse Collin 7 // 8 // This file has been put into the public domain. 9 // You can do whatever you want with this file. 10 // 11 /////////////////////////////////////////////////////////////////////////////// 12 13 #include "index.h" 14 #include "stream_flags_common.h" 15 16 17 /// \brief How many Records to allocate at once 18 /// 19 /// This should be big enough to avoid making lots of tiny allocations 20 /// but small enough to avoid too much unused memory at once. 21 #define INDEX_GROUP_SIZE 512 22 23 24 /// \brief How many Records can be allocated at once at maximum 25 #define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record)) 26 27 28 /// \brief Base structure for index_stream and index_group structures 29 typedef struct index_tree_node_s index_tree_node; 30 struct index_tree_node_s { 31 /// Uncompressed start offset of this Stream (relative to the 32 /// beginning of the file) or Block (relative to the beginning 33 /// of the Stream) 34 lzma_vli uncompressed_base; 35 36 /// Compressed start offset of this Stream or Block 37 lzma_vli compressed_base; 38 39 index_tree_node *parent; 40 index_tree_node *left; 41 index_tree_node *right; 42 }; 43 44 45 /// \brief AVL tree to hold index_stream or index_group structures 46 typedef struct { 47 /// Root node 48 index_tree_node *root; 49 50 /// Leftmost node. Since the tree will be filled sequentially, 51 /// this won't change after the first node has been added to 52 /// the tree. 53 index_tree_node *leftmost; 54 55 /// The rightmost node in the tree. Since the tree is filled 56 /// sequentially, this is always the node where to add the new data. 57 index_tree_node *rightmost; 58 59 /// Number of nodes in the tree 60 uint32_t count; 61 62 } index_tree; 63 64 65 typedef struct { 66 lzma_vli uncompressed_sum; 67 lzma_vli unpadded_sum; 68 } index_record; 69 70 71 typedef struct { 72 /// Every Record group is part of index_stream.groups tree. 73 index_tree_node node; 74 75 /// Number of Blocks in this Stream before this group. 76 lzma_vli number_base; 77 78 /// Number of Records that can be put in records[]. 79 size_t allocated; 80 81 /// Index of the last Record in use. 82 size_t last; 83 84 /// The sizes in this array are stored as cumulative sums relative 85 /// to the beginning of the Stream. This makes it possible to 86 /// use binary search in lzma_index_locate(). 87 /// 88 /// Note that the cumulative summing is done specially for 89 /// unpadded_sum: The previous value is rounded up to the next 90 /// multiple of four before adding the Unpadded Size of the new 91 /// Block. The total encoded size of the Blocks in the Stream 92 /// is records[last].unpadded_sum in the last Record group of 93 /// the Stream. 94 /// 95 /// For example, if the Unpadded Sizes are 39, 57, and 81, the 96 /// stored values are 39, 97 (40 + 57), and 181 (100 + 181). 97 /// The total encoded size of these Blocks is 184. 98 /// 99 /// This is a flexible array, because it makes easy to optimize 100 /// memory usage in case someone concatenates many Streams that 101 /// have only one or few Blocks. 102 index_record records[]; 103 104 } index_group; 105 106 107 typedef struct { 108 /// Every index_stream is a node in the tree of Sreams. 109 index_tree_node node; 110 111 /// Number of this Stream (first one is 1) 112 uint32_t number; 113 114 /// Total number of Blocks before this Stream 115 lzma_vli block_number_base; 116 117 /// Record groups of this Stream are stored in a tree. 118 /// It's a T-tree with AVL-tree balancing. There are 119 /// INDEX_GROUP_SIZE Records per node by default. 120 /// This keeps the number of memory allocations reasonable 121 /// and finding a Record is fast. 122 index_tree groups; 123 124 /// Number of Records in this Stream 125 lzma_vli record_count; 126 127 /// Size of the List of Records field in this Stream. This is used 128 /// together with record_count to calculate the size of the Index 129 /// field and thus the total size of the Stream. 130 lzma_vli index_list_size; 131 132 /// Stream Flags of this Stream. This is meaningful only if 133 /// the Stream Flags have been told us with lzma_index_stream_flags(). 134 /// Initially stream_flags.version is set to UINT32_MAX to indicate 135 /// that the Stream Flags are unknown. 136 lzma_stream_flags stream_flags; 137 138 /// Amount of Stream Padding after this Stream. This defaults to 139 /// zero and can be set with lzma_index_stream_padding(). 140 lzma_vli stream_padding; 141 142 } index_stream; 143 144 145 struct lzma_index_s { 146 /// AVL-tree containing the Stream(s). Often there is just one 147 /// Stream, but using a tree keeps lookups fast even when there 148 /// are many concatenated Streams. 149 index_tree streams; 150 151 /// Uncompressed size of all the Blocks in the Stream(s) 152 lzma_vli uncompressed_size; 153 154 /// Total size of all the Blocks in the Stream(s) 155 lzma_vli total_size; 156 157 /// Total number of Records in all Streams in this lzma_index 158 lzma_vli record_count; 159 160 /// Size of the List of Records field if all the Streams in this 161 /// lzma_index were packed into a single Stream (makes it simpler to 162 /// take many .xz files and combine them into a single Stream). 163 /// 164 /// This value together with record_count is needed to calculate 165 /// Backward Size that is stored into Stream Footer. 166 lzma_vli index_list_size; 167 168 /// How many Records to allocate at once in lzma_index_append(). 169 /// This defaults to INDEX_GROUP_SIZE but can be overriden with 170 /// lzma_index_prealloc(). 171 size_t prealloc; 172 173 /// Bitmask indicating what integrity check types have been used 174 /// as set by lzma_index_stream_flags(). The bit of the last Stream 175 /// is not included here, since it is possible to change it by 176 /// calling lzma_index_stream_flags() again. 177 uint32_t checks; 178 }; 179 180 181 static void 182 index_tree_init(index_tree *tree) 183 { 184 tree->root = NULL; 185 tree->leftmost = NULL; 186 tree->rightmost = NULL; 187 tree->count = 0; 188 return; 189 } 190 191 192 /// Helper for index_tree_end() 193 static void 194 index_tree_node_end(index_tree_node *node, lzma_allocator *allocator, 195 void (*free_func)(void *node, lzma_allocator *allocator)) 196 { 197 // The tree won't ever be very huge, so recursion should be fine. 198 // 20 levels in the tree is likely quite a lot already in practice. 199 if (node->left != NULL) 200 index_tree_node_end(node->left, allocator, free_func); 201 202 if (node->right != NULL) 203 index_tree_node_end(node->right, allocator, free_func); 204 205 if (free_func != NULL) 206 free_func(node, allocator); 207 208 lzma_free(node, allocator); 209 return; 210 } 211 212 213 /// Free the meory allocated for a tree. If free_func is not NULL, 214 /// it is called on each node before freeing the node. This is used 215 /// to free the Record groups from each index_stream before freeing 216 /// the index_stream itself. 217 static void 218 index_tree_end(index_tree *tree, lzma_allocator *allocator, 219 void (*free_func)(void *node, lzma_allocator *allocator)) 220 { 221 if (tree->root != NULL) 222 index_tree_node_end(tree->root, allocator, free_func); 223 224 return; 225 } 226 227 228 /// Add a new node to the tree. node->uncompressed_base and 229 /// node->compressed_base must have been set by the caller already. 230 static void 231 index_tree_append(index_tree *tree, index_tree_node *node) 232 { 233 node->parent = tree->rightmost; 234 node->left = NULL; 235 node->right = NULL; 236 237 ++tree->count; 238 239 // Handle the special case of adding the first node. 240 if (tree->root == NULL) { 241 tree->root = node; 242 tree->leftmost = node; 243 tree->rightmost = node; 244 return; 245 } 246 247 // The tree is always filled sequentially. 248 assert(tree->rightmost->uncompressed_base <= node->uncompressed_base); 249 assert(tree->rightmost->compressed_base < node->compressed_base); 250 251 // Add the new node after the rightmost node. It's the correct 252 // place due to the reason above. 253 tree->rightmost->right = node; 254 tree->rightmost = node; 255 256 // Balance the AVL-tree if needed. We don't need to keep the balance 257 // factors in nodes, because we always fill the tree sequentially, 258 // and thus know the state of the tree just by looking at the node 259 // count. From the node count we can calculate how many steps to go 260 // up in the tree to find the rotation root. 261 uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count)); 262 if (up != 0) { 263 // Locate the root node for the rotation. 264 up = ctz32(tree->count) + 2; 265 do { 266 node = node->parent; 267 } while (--up > 0); 268 269 // Rotate left using node as the rotation root. 270 index_tree_node *pivot = node->right; 271 272 if (node->parent == NULL) { 273 tree->root = pivot; 274 } else { 275 assert(node->parent->right == node); 276 node->parent->right = pivot; 277 } 278 279 pivot->parent = node->parent; 280 281 node->right = pivot->left; 282 if (node->right != NULL) 283 node->right->parent = node; 284 285 pivot->left = node; 286 node->parent = pivot; 287 } 288 289 return; 290 } 291 292 293 /// Get the next node in the tree. Return NULL if there are no more nodes. 294 static void * 295 index_tree_next(const index_tree_node *node) 296 { 297 if (node->right != NULL) { 298 node = node->right; 299 while (node->left != NULL) 300 node = node->left; 301 302 return (void *)(node); 303 } 304 305 while (node->parent != NULL && node->parent->right == node) 306 node = node->parent; 307 308 return (void *)(node->parent); 309 } 310 311 312 /// Locate a node that contains the given uncompressed offset. It is 313 /// caller's job to check that target is not bigger than the uncompressed 314 /// size of the tree (the last node would be returned in that case still). 315 static void * 316 index_tree_locate(const index_tree *tree, lzma_vli target) 317 { 318 const index_tree_node *result = NULL; 319 const index_tree_node *node = tree->root; 320 321 assert(tree->leftmost == NULL 322 || tree->leftmost->uncompressed_base == 0); 323 324 // Consecutive nodes may have the same uncompressed_base. 325 // We must pick the rightmost one. 326 while (node != NULL) { 327 if (node->uncompressed_base > target) { 328 node = node->left; 329 } else { 330 result = node; 331 node = node->right; 332 } 333 } 334 335 return (void *)(result); 336 } 337 338 339 /// Allocate and initialize a new Stream using the given base offsets. 340 static index_stream * 341 index_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base, 342 lzma_vli stream_number, lzma_vli block_number_base, 343 lzma_allocator *allocator) 344 { 345 index_stream *s = lzma_alloc(sizeof(index_stream), allocator); 346 if (s == NULL) 347 return NULL; 348 349 s->node.uncompressed_base = uncompressed_base; 350 s->node.compressed_base = compressed_base; 351 s->node.parent = NULL; 352 s->node.left = NULL; 353 s->node.right = NULL; 354 355 s->number = stream_number; 356 s->block_number_base = block_number_base; 357 358 index_tree_init(&s->groups); 359 360 s->record_count = 0; 361 s->index_list_size = 0; 362 s->stream_flags.version = UINT32_MAX; 363 s->stream_padding = 0; 364 365 return s; 366 } 367 368 369 /// Free the memory allocated for a Stream and its Record groups. 370 static void 371 index_stream_end(void *node, lzma_allocator *allocator) 372 { 373 index_stream *s = node; 374 index_tree_end(&s->groups, allocator, NULL); 375 return; 376 } 377 378 379 static lzma_index * 380 index_init_plain(lzma_allocator *allocator) 381 { 382 lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator); 383 if (i != NULL) { 384 index_tree_init(&i->streams); 385 i->uncompressed_size = 0; 386 i->total_size = 0; 387 i->record_count = 0; 388 i->index_list_size = 0; 389 i->prealloc = INDEX_GROUP_SIZE; 390 i->checks = 0; 391 } 392 393 return i; 394 } 395 396 397 extern LZMA_API(lzma_index *) 398 lzma_index_init(lzma_allocator *allocator) 399 { 400 lzma_index *i = index_init_plain(allocator); 401 if (i == NULL) 402 return NULL; 403 404 index_stream *s = index_stream_init(0, 0, 1, 0, allocator); 405 if (s == NULL) { 406 lzma_free(i, allocator); 407 return NULL; 408 } 409 410 index_tree_append(&i->streams, &s->node); 411 412 return i; 413 } 414 415 416 extern LZMA_API(void) 417 lzma_index_end(lzma_index *i, lzma_allocator *allocator) 418 { 419 // NOTE: If you modify this function, check also the bottom 420 // of lzma_index_cat(). 421 if (i != NULL) { 422 index_tree_end(&i->streams, allocator, &index_stream_end); 423 lzma_free(i, allocator); 424 } 425 426 return; 427 } 428 429 430 extern void 431 lzma_index_prealloc(lzma_index *i, lzma_vli records) 432 { 433 if (records > PREALLOC_MAX) 434 records = PREALLOC_MAX; 435 436 i->prealloc = (size_t)(records); 437 return; 438 } 439 440 441 extern LZMA_API(uint64_t) 442 lzma_index_memusage(lzma_vli streams, lzma_vli blocks) 443 { 444 // This calculates an upper bound that is only a little bit 445 // bigger than the exact maximum memory usage with the given 446 // parameters. 447 448 // Typical malloc() overhead is 2 * sizeof(void *) but we take 449 // a little bit extra just in case. Using LZMA_MEMUSAGE_BASE 450 // instead would give too inaccurate estimate. 451 const size_t alloc_overhead = 4 * sizeof(void *); 452 453 // Amount of memory needed for each Stream base structures. 454 // We assume that every Stream has at least one Block and 455 // thus at least one group. 456 const size_t stream_base = sizeof(index_stream) 457 + sizeof(index_group) + 2 * alloc_overhead; 458 459 // Amount of memory needed per group. 460 const size_t group_base = sizeof(index_group) 461 + INDEX_GROUP_SIZE * sizeof(index_record) 462 + alloc_overhead; 463 464 // Number of groups. There may actually be more, but that overhead 465 // has been taken into account in stream_base already. 466 const lzma_vli groups 467 = (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE; 468 469 // Memory used by index_stream and index_group structures. 470 const uint64_t streams_mem = streams * stream_base; 471 const uint64_t groups_mem = groups * group_base; 472 473 // Memory used by the base structure. 474 const uint64_t index_base = sizeof(lzma_index) + alloc_overhead; 475 476 // Validate the arguments and catch integer overflows. 477 // Maximum number of Streams is "only" UINT32_MAX, because 478 // that limit is used by the tree containing the Streams. 479 const uint64_t limit = UINT64_MAX - index_base; 480 if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX 481 || streams > limit / stream_base 482 || groups > limit / group_base 483 || limit - streams_mem < groups_mem) 484 return UINT64_MAX; 485 486 return index_base + streams_mem + groups_mem; 487 } 488 489 490 extern LZMA_API(uint64_t) 491 lzma_index_memused(const lzma_index *i) 492 { 493 return lzma_index_memusage(i->streams.count, i->record_count); 494 } 495 496 497 extern LZMA_API(lzma_vli) 498 lzma_index_block_count(const lzma_index *i) 499 { 500 return i->record_count; 501 } 502 503 504 extern LZMA_API(lzma_vli) 505 lzma_index_stream_count(const lzma_index *i) 506 { 507 return i->streams.count; 508 } 509 510 511 extern LZMA_API(lzma_vli) 512 lzma_index_size(const lzma_index *i) 513 { 514 return index_size(i->record_count, i->index_list_size); 515 } 516 517 518 extern LZMA_API(lzma_vli) 519 lzma_index_total_size(const lzma_index *i) 520 { 521 return i->total_size; 522 } 523 524 525 extern LZMA_API(lzma_vli) 526 lzma_index_stream_size(const lzma_index *i) 527 { 528 // Stream Header + Blocks + Index + Stream Footer 529 return LZMA_STREAM_HEADER_SIZE + i->total_size 530 + index_size(i->record_count, i->index_list_size) 531 + LZMA_STREAM_HEADER_SIZE; 532 } 533 534 535 static lzma_vli 536 index_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum, 537 lzma_vli record_count, lzma_vli index_list_size, 538 lzma_vli stream_padding) 539 { 540 // Earlier Streams and Stream Paddings + Stream Header 541 // + Blocks + Index + Stream Footer + Stream Padding 542 // 543 // This might go over LZMA_VLI_MAX due to too big unpadded_sum 544 // when this function is used in lzma_index_append(). 545 lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE 546 + stream_padding + vli_ceil4(unpadded_sum); 547 if (file_size > LZMA_VLI_MAX) 548 return LZMA_VLI_UNKNOWN; 549 550 // The same applies here. 551 file_size += index_size(record_count, index_list_size); 552 if (file_size > LZMA_VLI_MAX) 553 return LZMA_VLI_UNKNOWN; 554 555 return file_size; 556 } 557 558 559 extern LZMA_API(lzma_vli) 560 lzma_index_file_size(const lzma_index *i) 561 { 562 const index_stream *s = (const index_stream *)(i->streams.rightmost); 563 const index_group *g = (const index_group *)(s->groups.rightmost); 564 return index_file_size(s->node.compressed_base, 565 g == NULL ? 0 : g->records[g->last].unpadded_sum, 566 s->record_count, s->index_list_size, 567 s->stream_padding); 568 } 569 570 571 extern LZMA_API(lzma_vli) 572 lzma_index_uncompressed_size(const lzma_index *i) 573 { 574 return i->uncompressed_size; 575 } 576 577 578 extern LZMA_API(uint32_t) 579 lzma_index_checks(const lzma_index *i) 580 { 581 uint32_t checks = i->checks; 582 583 // Get the type of the Check of the last Stream too. 584 const index_stream *s = (const index_stream *)(i->streams.rightmost); 585 if (s->stream_flags.version != UINT32_MAX) 586 checks |= UINT32_C(1) << s->stream_flags.check; 587 588 return checks; 589 } 590 591 592 extern uint32_t 593 lzma_index_padding_size(const lzma_index *i) 594 { 595 return (LZMA_VLI_C(4) - index_size_unpadded( 596 i->record_count, i->index_list_size)) & 3; 597 } 598 599 600 extern LZMA_API(lzma_ret) 601 lzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags) 602 { 603 if (i == NULL || stream_flags == NULL) 604 return LZMA_PROG_ERROR; 605 606 // Validate the Stream Flags. 607 return_if_error(lzma_stream_flags_compare( 608 stream_flags, stream_flags)); 609 610 index_stream *s = (index_stream *)(i->streams.rightmost); 611 s->stream_flags = *stream_flags; 612 613 return LZMA_OK; 614 } 615 616 617 extern LZMA_API(lzma_ret) 618 lzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding) 619 { 620 if (i == NULL || stream_padding > LZMA_VLI_MAX 621 || (stream_padding & 3) != 0) 622 return LZMA_PROG_ERROR; 623 624 index_stream *s = (index_stream *)(i->streams.rightmost); 625 626 // Check that the new value won't make the file grow too big. 627 const lzma_vli old_stream_padding = s->stream_padding; 628 s->stream_padding = 0; 629 if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) { 630 s->stream_padding = old_stream_padding; 631 return LZMA_DATA_ERROR; 632 } 633 634 s->stream_padding = stream_padding; 635 return LZMA_OK; 636 } 637 638 639 extern LZMA_API(lzma_ret) 640 lzma_index_append(lzma_index *i, lzma_allocator *allocator, 641 lzma_vli unpadded_size, lzma_vli uncompressed_size) 642 { 643 // Validate. 644 if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN 645 || unpadded_size > UNPADDED_SIZE_MAX 646 || uncompressed_size > LZMA_VLI_MAX) 647 return LZMA_PROG_ERROR; 648 649 index_stream *s = (index_stream *)(i->streams.rightmost); 650 index_group *g = (index_group *)(s->groups.rightmost); 651 652 const lzma_vli compressed_base = g == NULL ? 0 653 : vli_ceil4(g->records[g->last].unpadded_sum); 654 const lzma_vli uncompressed_base = g == NULL ? 0 655 : g->records[g->last].uncompressed_sum; 656 const uint32_t index_list_size_add = lzma_vli_size(unpadded_size) 657 + lzma_vli_size(uncompressed_size); 658 659 // Check that the file size will stay within limits. 660 if (index_file_size(s->node.compressed_base, 661 compressed_base + unpadded_size, s->record_count + 1, 662 s->index_list_size + index_list_size_add, 663 s->stream_padding) == LZMA_VLI_UNKNOWN) 664 return LZMA_DATA_ERROR; 665 666 // The size of the Index field must not exceed the maximum value 667 // that can be stored in the Backward Size field. 668 if (index_size(i->record_count + 1, 669 i->index_list_size + index_list_size_add) 670 > LZMA_BACKWARD_SIZE_MAX) 671 return LZMA_DATA_ERROR; 672 673 if (g != NULL && g->last + 1 < g->allocated) { 674 // There is space in the last group at least for one Record. 675 ++g->last; 676 } else { 677 // We need to allocate a new group. 678 g = lzma_alloc(sizeof(index_group) 679 + i->prealloc * sizeof(index_record), 680 allocator); 681 if (g == NULL) 682 return LZMA_MEM_ERROR; 683 684 g->last = 0; 685 g->allocated = i->prealloc; 686 687 // Reset prealloc so that if the application happens to 688 // add new Records, the allocation size will be sane. 689 i->prealloc = INDEX_GROUP_SIZE; 690 691 // Set the start offsets of this group. 692 g->node.uncompressed_base = uncompressed_base; 693 g->node.compressed_base = compressed_base; 694 g->number_base = s->record_count + 1; 695 696 // Add the new group to the Stream. 697 index_tree_append(&s->groups, &g->node); 698 } 699 700 // Add the new Record to the group. 701 g->records[g->last].uncompressed_sum 702 = uncompressed_base + uncompressed_size; 703 g->records[g->last].unpadded_sum 704 = compressed_base + unpadded_size; 705 706 // Update the totals. 707 ++s->record_count; 708 s->index_list_size += index_list_size_add; 709 710 i->total_size += vli_ceil4(unpadded_size); 711 i->uncompressed_size += uncompressed_size; 712 ++i->record_count; 713 i->index_list_size += index_list_size_add; 714 715 return LZMA_OK; 716 } 717 718 719 /// Structure to pass info to index_cat_helper() 720 typedef struct { 721 /// Uncompressed size of the destination 722 lzma_vli uncompressed_size; 723 724 /// Compressed file size of the destination 725 lzma_vli file_size; 726 727 /// Same as above but for Block numbers 728 lzma_vli block_number_add; 729 730 /// Number of Streams that were in the destination index before we 731 /// started appending new Streams from the source index. This is 732 /// used to fix the Stream numbering. 733 uint32_t stream_number_add; 734 735 /// Destination index' Stream tree 736 index_tree *streams; 737 738 } index_cat_info; 739 740 741 /// Add the Stream nodes from the source index to dest using recursion. 742 /// Simplest iterative traversal of the source tree wouldn't work, because 743 /// we update the pointers in nodes when moving them to the destination tree. 744 static void 745 index_cat_helper(const index_cat_info *info, index_stream *this) 746 { 747 index_stream *left = (index_stream *)(this->node.left); 748 index_stream *right = (index_stream *)(this->node.right); 749 750 if (left != NULL) 751 index_cat_helper(info, left); 752 753 this->node.uncompressed_base += info->uncompressed_size; 754 this->node.compressed_base += info->file_size; 755 this->number += info->stream_number_add; 756 this->block_number_base += info->block_number_add; 757 index_tree_append(info->streams, &this->node); 758 759 if (right != NULL) 760 index_cat_helper(info, right); 761 762 return; 763 } 764 765 766 extern LZMA_API(lzma_ret) 767 lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src, 768 lzma_allocator *allocator) 769 { 770 const lzma_vli dest_file_size = lzma_index_file_size(dest); 771 772 // Check that we don't exceed the file size limits. 773 if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX 774 || dest->uncompressed_size + src->uncompressed_size 775 > LZMA_VLI_MAX) 776 return LZMA_DATA_ERROR; 777 778 // Check that the encoded size of the combined lzma_indexes stays 779 // within limits. In theory, this should be done only if we know 780 // that the user plans to actually combine the Streams and thus 781 // construct a single Index (probably rare). However, exceeding 782 // this limit is quite theoretical, so we do this check always 783 // to simplify things elsewhere. 784 { 785 const lzma_vli dest_size = index_size_unpadded( 786 dest->record_count, dest->index_list_size); 787 const lzma_vli src_size = index_size_unpadded( 788 src->record_count, src->index_list_size); 789 if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX) 790 return LZMA_DATA_ERROR; 791 } 792 793 // Optimize the last group to minimize memory usage. Allocation has 794 // to be done before modifying dest or src. 795 { 796 index_stream *s = (index_stream *)(dest->streams.rightmost); 797 index_group *g = (index_group *)(s->groups.rightmost); 798 if (g != NULL && g->last + 1 < g->allocated) { 799 assert(g->node.left == NULL); 800 assert(g->node.right == NULL); 801 802 index_group *newg = lzma_alloc(sizeof(index_group) 803 + (g->last + 1) 804 * sizeof(index_record), 805 allocator); 806 if (newg == NULL) 807 return LZMA_MEM_ERROR; 808 809 newg->node = g->node; 810 newg->allocated = g->last + 1; 811 newg->last = g->last; 812 newg->number_base = g->number_base; 813 814 memcpy(newg->records, g->records, newg->allocated 815 * sizeof(index_record)); 816 817 if (g->node.parent != NULL) { 818 assert(g->node.parent->right == &g->node); 819 g->node.parent->right = &newg->node; 820 } 821 822 if (s->groups.leftmost == &g->node) { 823 assert(s->groups.root == &g->node); 824 s->groups.leftmost = &newg->node; 825 s->groups.root = &newg->node; 826 } 827 828 if (s->groups.rightmost == &g->node) 829 s->groups.rightmost = &newg->node; 830 831 lzma_free(g, allocator); 832 } 833 } 834 835 // Add all the Streams from src to dest. Update the base offsets 836 // of each Stream from src. 837 const index_cat_info info = { 838 .uncompressed_size = dest->uncompressed_size, 839 .file_size = dest_file_size, 840 .stream_number_add = dest->streams.count, 841 .block_number_add = dest->record_count, 842 .streams = &dest->streams, 843 }; 844 index_cat_helper(&info, (index_stream *)(src->streams.root)); 845 846 // Update info about all the combined Streams. 847 dest->uncompressed_size += src->uncompressed_size; 848 dest->total_size += src->total_size; 849 dest->record_count += src->record_count; 850 dest->index_list_size += src->index_list_size; 851 dest->checks = lzma_index_checks(dest) | src->checks; 852 853 // There's nothing else left in src than the base structure. 854 lzma_free(src, allocator); 855 856 return LZMA_OK; 857 } 858 859 860 /// Duplicate an index_stream. 861 static index_stream * 862 index_dup_stream(const index_stream *src, lzma_allocator *allocator) 863 { 864 // Catch a somewhat theoretical integer overflow. 865 if (src->record_count > PREALLOC_MAX) 866 return NULL; 867 868 // Allocate and initialize a new Stream. 869 index_stream *dest = index_stream_init(src->node.compressed_base, 870 src->node.uncompressed_base, src->number, 871 src->block_number_base, allocator); 872 873 // Return immediately if allocation failed or if there are 874 // no groups to duplicate. 875 if (dest == NULL || src->groups.leftmost == NULL) 876 return dest; 877 878 // Copy the overall information. 879 dest->record_count = src->record_count; 880 dest->index_list_size = src->index_list_size; 881 dest->stream_flags = src->stream_flags; 882 dest->stream_padding = src->stream_padding; 883 884 // Allocate memory for the Records. We put all the Records into 885 // a single group. It's simplest and also tends to make 886 // lzma_index_locate() a little bit faster with very big Indexes. 887 index_group *destg = lzma_alloc(sizeof(index_group) 888 + src->record_count * sizeof(index_record), 889 allocator); 890 if (destg == NULL) { 891 index_stream_end(dest, allocator); 892 return NULL; 893 } 894 895 // Initialize destg. 896 destg->node.uncompressed_base = 0; 897 destg->node.compressed_base = 0; 898 destg->number_base = 1; 899 destg->allocated = src->record_count; 900 destg->last = src->record_count - 1; 901 902 // Go through all the groups in src and copy the Records into destg. 903 const index_group *srcg = (const index_group *)(src->groups.leftmost); 904 size_t i = 0; 905 do { 906 memcpy(destg->records + i, srcg->records, 907 (srcg->last + 1) * sizeof(index_record)); 908 i += srcg->last + 1; 909 srcg = index_tree_next(&srcg->node); 910 } while (srcg != NULL); 911 912 assert(i == destg->allocated); 913 914 // Add the group to the new Stream. 915 index_tree_append(&dest->groups, &destg->node); 916 917 return dest; 918 } 919 920 921 extern LZMA_API(lzma_index *) 922 lzma_index_dup(const lzma_index *src, lzma_allocator *allocator) 923 { 924 // Allocate the base structure (no initial Stream). 925 lzma_index *dest = index_init_plain(allocator); 926 if (dest == NULL) 927 return NULL; 928 929 // Copy the totals. 930 dest->uncompressed_size = src->uncompressed_size; 931 dest->total_size = src->total_size; 932 dest->record_count = src->record_count; 933 dest->index_list_size = src->index_list_size; 934 935 // Copy the Streams and the groups in them. 936 const index_stream *srcstream 937 = (const index_stream *)(src->streams.leftmost); 938 do { 939 index_stream *deststream = index_dup_stream( 940 srcstream, allocator); 941 if (deststream == NULL) { 942 lzma_index_end(dest, allocator); 943 return NULL; 944 } 945 946 index_tree_append(&dest->streams, &deststream->node); 947 948 srcstream = index_tree_next(&srcstream->node); 949 } while (srcstream != NULL); 950 951 return dest; 952 } 953 954 955 /// Indexing for lzma_index_iter.internal[] 956 enum { 957 ITER_INDEX, 958 ITER_STREAM, 959 ITER_GROUP, 960 ITER_RECORD, 961 ITER_METHOD, 962 }; 963 964 965 /// Values for lzma_index_iter.internal[ITER_METHOD].s 966 enum { 967 ITER_METHOD_NORMAL, 968 ITER_METHOD_NEXT, 969 ITER_METHOD_LEFTMOST, 970 }; 971 972 973 static void 974 iter_set_info(lzma_index_iter *iter) 975 { 976 const lzma_index *i = iter->internal[ITER_INDEX].p; 977 const index_stream *stream = iter->internal[ITER_STREAM].p; 978 const index_group *group = iter->internal[ITER_GROUP].p; 979 const size_t record = iter->internal[ITER_RECORD].s; 980 981 // lzma_index_iter.internal must not contain a pointer to the last 982 // group in the index, because that may be reallocated by 983 // lzma_index_cat(). 984 if (group == NULL) { 985 // There are no groups. 986 assert(stream->groups.root == NULL); 987 iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST; 988 989 } else if (i->streams.rightmost != &stream->node 990 || stream->groups.rightmost != &group->node) { 991 // The group is not not the last group in the index. 992 iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL; 993 994 } else if (stream->groups.leftmost != &group->node) { 995 // The group isn't the only group in the Stream, thus we 996 // know that it must have a parent group i.e. it's not 997 // the root node. 998 assert(stream->groups.root != &group->node); 999 assert(group->node.parent->right == &group->node); 1000 iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT; 1001 iter->internal[ITER_GROUP].p = group->node.parent; 1002 1003 } else { 1004 // The Stream has only one group. 1005 assert(stream->groups.root == &group->node); 1006 assert(group->node.parent == NULL); 1007 iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST; 1008 iter->internal[ITER_GROUP].p = NULL; 1009 } 1010 1011 iter->stream.number = stream->number; 1012 iter->stream.block_count = stream->record_count; 1013 iter->stream.compressed_offset = stream->node.compressed_base; 1014 iter->stream.uncompressed_offset = stream->node.uncompressed_base; 1015 1016 // iter->stream.flags will be NULL if the Stream Flags haven't been 1017 // set with lzma_index_stream_flags(). 1018 iter->stream.flags = stream->stream_flags.version == UINT32_MAX 1019 ? NULL : &stream->stream_flags; 1020 iter->stream.padding = stream->stream_padding; 1021 1022 if (stream->groups.rightmost == NULL) { 1023 // Stream has no Blocks. 1024 iter->stream.compressed_size = index_size(0, 0) 1025 + 2 * LZMA_STREAM_HEADER_SIZE; 1026 iter->stream.uncompressed_size = 0; 1027 } else { 1028 const index_group *g = (const index_group *)( 1029 stream->groups.rightmost); 1030 1031 // Stream Header + Stream Footer + Index + Blocks 1032 iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE 1033 + index_size(stream->record_count, 1034 stream->index_list_size) 1035 + vli_ceil4(g->records[g->last].unpadded_sum); 1036 iter->stream.uncompressed_size 1037 = g->records[g->last].uncompressed_sum; 1038 } 1039 1040 if (group != NULL) { 1041 iter->block.number_in_stream = group->number_base + record; 1042 iter->block.number_in_file = iter->block.number_in_stream 1043 + stream->block_number_base; 1044 1045 iter->block.compressed_stream_offset 1046 = record == 0 ? group->node.compressed_base 1047 : vli_ceil4(group->records[ 1048 record - 1].unpadded_sum); 1049 iter->block.uncompressed_stream_offset 1050 = record == 0 ? group->node.uncompressed_base 1051 : group->records[record - 1].uncompressed_sum; 1052 1053 iter->block.uncompressed_size 1054 = group->records[record].uncompressed_sum 1055 - iter->block.uncompressed_stream_offset; 1056 iter->block.unpadded_size 1057 = group->records[record].unpadded_sum 1058 - iter->block.compressed_stream_offset; 1059 iter->block.total_size = vli_ceil4(iter->block.unpadded_size); 1060 1061 iter->block.compressed_stream_offset 1062 += LZMA_STREAM_HEADER_SIZE; 1063 1064 iter->block.compressed_file_offset 1065 = iter->block.compressed_stream_offset 1066 + iter->stream.compressed_offset; 1067 iter->block.uncompressed_file_offset 1068 = iter->block.uncompressed_stream_offset 1069 + iter->stream.uncompressed_offset; 1070 } 1071 1072 return; 1073 } 1074 1075 1076 extern LZMA_API(void) 1077 lzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i) 1078 { 1079 iter->internal[ITER_INDEX].p = i; 1080 lzma_index_iter_rewind(iter); 1081 return; 1082 } 1083 1084 1085 extern LZMA_API(void) 1086 lzma_index_iter_rewind(lzma_index_iter *iter) 1087 { 1088 iter->internal[ITER_STREAM].p = NULL; 1089 iter->internal[ITER_GROUP].p = NULL; 1090 iter->internal[ITER_RECORD].s = 0; 1091 iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL; 1092 return; 1093 } 1094 1095 1096 extern LZMA_API(lzma_bool) 1097 lzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode) 1098 { 1099 // Catch unsupported mode values. 1100 if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK) 1101 return true; 1102 1103 const lzma_index *i = iter->internal[ITER_INDEX].p; 1104 const index_stream *stream = iter->internal[ITER_STREAM].p; 1105 const index_group *group = NULL; 1106 size_t record = iter->internal[ITER_RECORD].s; 1107 1108 // If we are being asked for the next Stream, leave group to NULL 1109 // so that the rest of the this function thinks that this Stream 1110 // has no groups and will thus go to the next Stream. 1111 if (mode != LZMA_INDEX_ITER_STREAM) { 1112 // Get the pointer to the current group. See iter_set_inf() 1113 // for explanation. 1114 switch (iter->internal[ITER_METHOD].s) { 1115 case ITER_METHOD_NORMAL: 1116 group = iter->internal[ITER_GROUP].p; 1117 break; 1118 1119 case ITER_METHOD_NEXT: 1120 group = index_tree_next(iter->internal[ITER_GROUP].p); 1121 break; 1122 1123 case ITER_METHOD_LEFTMOST: 1124 group = (const index_group *)( 1125 stream->groups.leftmost); 1126 break; 1127 } 1128 } 1129 1130 again: 1131 if (stream == NULL) { 1132 // We at the beginning of the lzma_index. 1133 // Locate the first Stream. 1134 stream = (const index_stream *)(i->streams.leftmost); 1135 if (mode >= LZMA_INDEX_ITER_BLOCK) { 1136 // Since we are being asked to return information 1137 // about the first a Block, skip Streams that have 1138 // no Blocks. 1139 while (stream->groups.leftmost == NULL) { 1140 stream = index_tree_next(&stream->node); 1141 if (stream == NULL) 1142 return true; 1143 } 1144 } 1145 1146 // Start from the first Record in the Stream. 1147 group = (const index_group *)(stream->groups.leftmost); 1148 record = 0; 1149 1150 } else if (group != NULL && record < group->last) { 1151 // The next Record is in the same group. 1152 ++record; 1153 1154 } else { 1155 // This group has no more Records or this Stream has 1156 // no Blocks at all. 1157 record = 0; 1158 1159 // If group is not NULL, this Stream has at least one Block 1160 // and thus at least one group. Find the next group. 1161 if (group != NULL) 1162 group = index_tree_next(&group->node); 1163 1164 if (group == NULL) { 1165 // This Stream has no more Records. Find the next 1166 // Stream. If we are being asked to return information 1167 // about a Block, we skip empty Streams. 1168 do { 1169 stream = index_tree_next(&stream->node); 1170 if (stream == NULL) 1171 return true; 1172 } while (mode >= LZMA_INDEX_ITER_BLOCK 1173 && stream->groups.leftmost == NULL); 1174 1175 group = (const index_group *)( 1176 stream->groups.leftmost); 1177 } 1178 } 1179 1180 if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) { 1181 // We need to look for the next Block again if this Block 1182 // is empty. 1183 if (record == 0) { 1184 if (group->node.uncompressed_base 1185 == group->records[0].uncompressed_sum) 1186 goto again; 1187 } else if (group->records[record - 1].uncompressed_sum 1188 == group->records[record].uncompressed_sum) { 1189 goto again; 1190 } 1191 } 1192 1193 iter->internal[ITER_STREAM].p = stream; 1194 iter->internal[ITER_GROUP].p = group; 1195 iter->internal[ITER_RECORD].s = record; 1196 1197 iter_set_info(iter); 1198 1199 return false; 1200 } 1201 1202 1203 extern LZMA_API(lzma_bool) 1204 lzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target) 1205 { 1206 const lzma_index *i = iter->internal[ITER_INDEX].p; 1207 1208 // If the target is past the end of the file, return immediately. 1209 if (i->uncompressed_size <= target) 1210 return true; 1211 1212 // Locate the Stream containing the target offset. 1213 const index_stream *stream = index_tree_locate(&i->streams, target); 1214 assert(stream != NULL); 1215 target -= stream->node.uncompressed_base; 1216 1217 // Locate the group containing the target offset. 1218 const index_group *group = index_tree_locate(&stream->groups, target); 1219 assert(group != NULL); 1220 1221 // Use binary search to locate the exact Record. It is the first 1222 // Record whose uncompressed_sum is greater than target. 1223 // This is because we want the rightmost Record that fullfills the 1224 // search criterion. It is possible that there are empty Blocks; 1225 // we don't want to return them. 1226 size_t left = 0; 1227 size_t right = group->last; 1228 1229 while (left < right) { 1230 const size_t pos = left + (right - left) / 2; 1231 if (group->records[pos].uncompressed_sum <= target) 1232 left = pos + 1; 1233 else 1234 right = pos; 1235 } 1236 1237 iter->internal[ITER_STREAM].p = stream; 1238 iter->internal[ITER_GROUP].p = group; 1239 iter->internal[ITER_RECORD].s = left; 1240 1241 iter_set_info(iter); 1242 1243 return false; 1244 } 1245