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, const lzma_allocator *allocator, |
195 |
void (*free_func)(void *node, const 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, const lzma_allocator *allocator, |
219 |
void (*free_func)(void *node, const 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 |
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, NULL); |
375 |
return; |
376 |
} |
377 |
|
378 |
|
379 |
static lzma_index * |
380 |
index_init_plain(const 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(const 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, const 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, const 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 |
const 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, const 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, const 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 |
// NOTE: lzma_index_iter.stream.number is lzma_vli but we use uint32_t |
1012 |
// internally. |
1013 |
iter->stream.number = stream->number; |
1014 |
iter->stream.block_count = stream->record_count; |
1015 |
iter->stream.compressed_offset = stream->node.compressed_base; |
1016 |
iter->stream.uncompressed_offset = stream->node.uncompressed_base; |
1017 |
|
1018 |
// iter->stream.flags will be NULL if the Stream Flags haven't been |
1019 |
// set with lzma_index_stream_flags(). |
1020 |
iter->stream.flags = stream->stream_flags.version == UINT32_MAX |
1021 |
? NULL : &stream->stream_flags; |
1022 |
iter->stream.padding = stream->stream_padding; |
1023 |
|
1024 |
if (stream->groups.rightmost == NULL) { |
1025 |
// Stream has no Blocks. |
1026 |
iter->stream.compressed_size = index_size(0, 0) |
1027 |
+ 2 * LZMA_STREAM_HEADER_SIZE; |
1028 |
iter->stream.uncompressed_size = 0; |
1029 |
} else { |
1030 |
const index_group *g = (const index_group *)( |
1031 |
stream->groups.rightmost); |
1032 |
|
1033 |
// Stream Header + Stream Footer + Index + Blocks |
1034 |
iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE |
1035 |
+ index_size(stream->record_count, |
1036 |
stream->index_list_size) |
1037 |
+ vli_ceil4(g->records[g->last].unpadded_sum); |
1038 |
iter->stream.uncompressed_size |
1039 |
= g->records[g->last].uncompressed_sum; |
1040 |
} |
1041 |
|
1042 |
if (group != NULL) { |
1043 |
iter->block.number_in_stream = group->number_base + record; |
1044 |
iter->block.number_in_file = iter->block.number_in_stream |
1045 |
+ stream->block_number_base; |
1046 |
|
1047 |
iter->block.compressed_stream_offset |
1048 |
= record == 0 ? group->node.compressed_base |
1049 |
: vli_ceil4(group->records[ |
1050 |
record - 1].unpadded_sum); |
1051 |
iter->block.uncompressed_stream_offset |
1052 |
= record == 0 ? group->node.uncompressed_base |
1053 |
: group->records[record - 1].uncompressed_sum; |
1054 |
|
1055 |
iter->block.uncompressed_size |
1056 |
= group->records[record].uncompressed_sum |
1057 |
- iter->block.uncompressed_stream_offset; |
1058 |
iter->block.unpadded_size |
1059 |
= group->records[record].unpadded_sum |
1060 |
- iter->block.compressed_stream_offset; |
1061 |
iter->block.total_size = vli_ceil4(iter->block.unpadded_size); |
1062 |
|
1063 |
iter->block.compressed_stream_offset |
1064 |
+= LZMA_STREAM_HEADER_SIZE; |
1065 |
|
1066 |
iter->block.compressed_file_offset |
1067 |
= iter->block.compressed_stream_offset |
1068 |
+ iter->stream.compressed_offset; |
1069 |
iter->block.uncompressed_file_offset |
1070 |
= iter->block.uncompressed_stream_offset |
1071 |
+ iter->stream.uncompressed_offset; |
1072 |
} |
1073 |
|
1074 |
return; |
1075 |
} |
1076 |
|
1077 |
|
1078 |
extern LZMA_API(void) |
1079 |
lzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i) |
1080 |
{ |
1081 |
iter->internal[ITER_INDEX].p = i; |
1082 |
lzma_index_iter_rewind(iter); |
1083 |
return; |
1084 |
} |
1085 |
|
1086 |
|
1087 |
extern LZMA_API(void) |
1088 |
lzma_index_iter_rewind(lzma_index_iter *iter) |
1089 |
{ |
1090 |
iter->internal[ITER_STREAM].p = NULL; |
1091 |
iter->internal[ITER_GROUP].p = NULL; |
1092 |
iter->internal[ITER_RECORD].s = 0; |
1093 |
iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL; |
1094 |
return; |
1095 |
} |
1096 |
|
1097 |
|
1098 |
extern LZMA_API(lzma_bool) |
1099 |
lzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode) |
1100 |
{ |
1101 |
// Catch unsupported mode values. |
1102 |
if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK) |
1103 |
return true; |
1104 |
|
1105 |
const lzma_index *i = iter->internal[ITER_INDEX].p; |
1106 |
const index_stream *stream = iter->internal[ITER_STREAM].p; |
1107 |
const index_group *group = NULL; |
1108 |
size_t record = iter->internal[ITER_RECORD].s; |
1109 |
|
1110 |
// If we are being asked for the next Stream, leave group to NULL |
1111 |
// so that the rest of the this function thinks that this Stream |
1112 |
// has no groups and will thus go to the next Stream. |
1113 |
if (mode != LZMA_INDEX_ITER_STREAM) { |
1114 |
// Get the pointer to the current group. See iter_set_inf() |
1115 |
// for explanation. |
1116 |
switch (iter->internal[ITER_METHOD].s) { |
1117 |
case ITER_METHOD_NORMAL: |
1118 |
group = iter->internal[ITER_GROUP].p; |
1119 |
break; |
1120 |
|
1121 |
case ITER_METHOD_NEXT: |
1122 |
group = index_tree_next(iter->internal[ITER_GROUP].p); |
1123 |
break; |
1124 |
|
1125 |
case ITER_METHOD_LEFTMOST: |
1126 |
group = (const index_group *)( |
1127 |
stream->groups.leftmost); |
1128 |
break; |
1129 |
} |
1130 |
} |
1131 |
|
1132 |
again: |
1133 |
if (stream == NULL) { |
1134 |
// We at the beginning of the lzma_index. |
1135 |
// Locate the first Stream. |
1136 |
stream = (const index_stream *)(i->streams.leftmost); |
1137 |
if (mode >= LZMA_INDEX_ITER_BLOCK) { |
1138 |
// Since we are being asked to return information |
1139 |
// about the first a Block, skip Streams that have |
1140 |
// no Blocks. |
1141 |
while (stream->groups.leftmost == NULL) { |
1142 |
stream = index_tree_next(&stream->node); |
1143 |
if (stream == NULL) |
1144 |
return true; |
1145 |
} |
1146 |
} |
1147 |
|
1148 |
// Start from the first Record in the Stream. |
1149 |
group = (const index_group *)(stream->groups.leftmost); |
1150 |
record = 0; |
1151 |
|
1152 |
} else if (group != NULL && record < group->last) { |
1153 |
// The next Record is in the same group. |
1154 |
++record; |
1155 |
|
1156 |
} else { |
1157 |
// This group has no more Records or this Stream has |
1158 |
// no Blocks at all. |
1159 |
record = 0; |
1160 |
|
1161 |
// If group is not NULL, this Stream has at least one Block |
1162 |
// and thus at least one group. Find the next group. |
1163 |
if (group != NULL) |
1164 |
group = index_tree_next(&group->node); |
1165 |
|
1166 |
if (group == NULL) { |
1167 |
// This Stream has no more Records. Find the next |
1168 |
// Stream. If we are being asked to return information |
1169 |
// about a Block, we skip empty Streams. |
1170 |
do { |
1171 |
stream = index_tree_next(&stream->node); |
1172 |
if (stream == NULL) |
1173 |
return true; |
1174 |
} while (mode >= LZMA_INDEX_ITER_BLOCK |
1175 |
&& stream->groups.leftmost == NULL); |
1176 |
|
1177 |
group = (const index_group *)( |
1178 |
stream->groups.leftmost); |
1179 |
} |
1180 |
} |
1181 |
|
1182 |
if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) { |
1183 |
// We need to look for the next Block again if this Block |
1184 |
// is empty. |
1185 |
if (record == 0) { |
1186 |
if (group->node.uncompressed_base |
1187 |
== group->records[0].uncompressed_sum) |
1188 |
goto again; |
1189 |
} else if (group->records[record - 1].uncompressed_sum |
1190 |
== group->records[record].uncompressed_sum) { |
1191 |
goto again; |
1192 |
} |
1193 |
} |
1194 |
|
1195 |
iter->internal[ITER_STREAM].p = stream; |
1196 |
iter->internal[ITER_GROUP].p = group; |
1197 |
iter->internal[ITER_RECORD].s = record; |
1198 |
|
1199 |
iter_set_info(iter); |
1200 |
|
1201 |
return false; |
1202 |
} |
1203 |
|
1204 |
|
1205 |
extern LZMA_API(lzma_bool) |
1206 |
lzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target) |
1207 |
{ |
1208 |
const lzma_index *i = iter->internal[ITER_INDEX].p; |
1209 |
|
1210 |
// If the target is past the end of the file, return immediately. |
1211 |
if (i->uncompressed_size <= target) |
1212 |
return true; |
1213 |
|
1214 |
// Locate the Stream containing the target offset. |
1215 |
const index_stream *stream = index_tree_locate(&i->streams, target); |
1216 |
assert(stream != NULL); |
1217 |
target -= stream->node.uncompressed_base; |
1218 |
|
1219 |
// Locate the group containing the target offset. |
1220 |
const index_group *group = index_tree_locate(&stream->groups, target); |
1221 |
assert(group != NULL); |
1222 |
|
1223 |
// Use binary search to locate the exact Record. It is the first |
1224 |
// Record whose uncompressed_sum is greater than target. |
1225 |
// This is because we want the rightmost Record that fullfills the |
1226 |
// search criterion. It is possible that there are empty Blocks; |
1227 |
// we don't want to return them. |
1228 |
size_t left = 0; |
1229 |
size_t right = group->last; |
1230 |
|
1231 |
while (left < right) { |
1232 |
const size_t pos = left + (right - left) / 2; |
1233 |
if (group->records[pos].uncompressed_sum <= target) |
1234 |
left = pos + 1; |
1235 |
else |
1236 |
right = pos; |
1237 |
} |
1238 |
|
1239 |
iter->internal[ITER_STREAM].p = stream; |
1240 |
iter->internal[ITER_GROUP].p = group; |
1241 |
iter->internal[ITER_RECORD].s = left; |
1242 |
|
1243 |
iter_set_info(iter); |
1244 |
|
1245 |
return false; |
1246 |
} |