xref: /freebsd/contrib/xz/src/liblzma/common/index.c (revision 9a14aa017b21c292740c00ee098195cd46642730)
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