contrib/xz/src/liblzma/common/index.c

   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 }