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