1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief Tests functions handling the lzma_index structure
6 // Copyright (C) 2007-2008 Lasse Collin
8 // This library is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Lesser General Public
10 // License as published by the Free Software Foundation; either
11 // version 2.1 of the License, or (at your option) any later version.
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 // Lesser General Public License for more details.
18 ///////////////////////////////////////////////////////////////////////////////
26 lzma_index *i = lzma_index_init(NULL, NULL);
35 lzma_index *i = lzma_index_init(NULL, NULL);
37 expect(lzma_index_append(i, NULL, 101, 555) == LZMA_OK);
38 expect(lzma_index_append(i, NULL, 602, 777) == LZMA_OK);
39 expect(lzma_index_append(i, NULL, 804, 999) == LZMA_OK);
47 lzma_index *i = lzma_index_init(NULL, NULL);
50 lzma_vli total_size = 0;
51 lzma_vli uncompressed_size = 0;
53 // Add pseudo-random sizes (but always the same size values).
54 const size_t count = 5555;
56 for (size_t j = 0; j < count; ++j) {
58 const uint32_t t = n * 3011;
59 expect(lzma_index_append(i, NULL, t, n) == LZMA_OK);
60 total_size += (t + 3) & ~LZMA_VLI_C(3);
61 uncompressed_size += n;
64 expect(lzma_index_count(i) == count);
65 expect(lzma_index_total_size(i) == total_size);
66 expect(lzma_index_uncompressed_size(i) == uncompressed_size);
67 expect(lzma_index_total_size(i) + lzma_index_size(i)
68 + 2 * LZMA_STREAM_HEADER_SIZE
69 == lzma_index_stream_size(i));
78 lzma_index *a = create_empty();
79 lzma_index *b = create_small();
80 lzma_index *c = create_big();
83 expect(lzma_index_equal(a, a));
84 expect(lzma_index_equal(b, b));
85 expect(lzma_index_equal(c, c));
87 expect(!lzma_index_equal(a, b));
88 expect(!lzma_index_equal(a, c));
89 expect(!lzma_index_equal(b, c));
91 lzma_index_end(a, NULL);
92 lzma_index_end(b, NULL);
93 lzma_index_end(c, NULL);
100 // Integer overflow tests
101 lzma_index *i = create_empty();
103 expect(lzma_index_append(i, NULL, LZMA_VLI_MAX - 5, 1234)
108 lzma_index_end(i, NULL);
113 test_copy(const lzma_index *i)
115 lzma_index *d = lzma_index_dup(i, NULL);
117 lzma_index_end(d, NULL);
122 test_read(lzma_index *i)
124 lzma_index_record record;
126 // Try twice so we see that rewinding works.
127 for (size_t j = 0; j < 2; ++j) {
128 lzma_vli total_size = 0;
129 lzma_vli uncompressed_size = 0;
130 lzma_vli stream_offset = LZMA_STREAM_HEADER_SIZE;
131 lzma_vli uncompressed_offset = 0;
134 while (!lzma_index_read(i, &record)) {
137 total_size += record.total_size;
138 uncompressed_size += record.uncompressed_size;
140 expect(record.stream_offset == stream_offset);
141 expect(record.uncompressed_offset
142 == uncompressed_offset);
144 stream_offset += record.total_size;
145 uncompressed_offset += record.uncompressed_size;
148 expect(lzma_index_total_size(i) == total_size);
149 expect(lzma_index_uncompressed_size(i) == uncompressed_size);
150 expect(lzma_index_count(i) == count);
152 lzma_index_rewind(i);
158 test_code(lzma_index *i)
160 const size_t alloc_size = 128 * 1024;
161 uint8_t *buf = malloc(alloc_size);
165 lzma_stream strm = LZMA_STREAM_INIT;
166 expect(lzma_index_encoder(&strm, i) == LZMA_OK);
167 const lzma_vli index_size = lzma_index_size(i);
168 succeed(coder_loop(&strm, NULL, 0, buf, index_size,
169 LZMA_STREAM_END, LZMA_RUN));
173 expect(lzma_index_decoder(&strm, &d) == LZMA_OK);
174 succeed(decoder_loop(&strm, buf, index_size));
176 expect(lzma_index_equal(i, d));
178 lzma_index_end(d, NULL);
181 // Decode with hashing
182 lzma_index_hash *h = lzma_index_hash_init(NULL, NULL);
184 lzma_index_rewind(i);
186 while (!lzma_index_read(i, &r))
187 expect(lzma_index_hash_append(h, r.unpadded_size,
188 r.uncompressed_size) == LZMA_OK);
190 while (pos < index_size - 1)
191 expect(lzma_index_hash_decode(h, buf, &pos, pos + 1)
193 expect(lzma_index_hash_decode(h, buf, &pos, pos + 1)
196 lzma_index_hash_end(h, NULL);
203 test_many(lzma_index *i)
214 lzma_index *a, *b, *c;
219 expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
220 expect(lzma_index_count(a) == 0);
221 expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
222 expect(lzma_index_file_size(a)
223 == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
226 expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
227 expect(lzma_index_count(a) == 0);
228 expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
229 expect(lzma_index_file_size(a)
230 == 3 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
234 expect(lzma_index_cat(b, c, NULL, 4) == LZMA_OK);
235 expect(lzma_index_count(b) == 0);
236 expect(lzma_index_stream_size(b) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
237 expect(lzma_index_file_size(b)
238 == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4);
240 expect(lzma_index_cat(a, b, NULL, 8) == LZMA_OK);
241 expect(lzma_index_count(a) == 0);
242 expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
243 expect(lzma_index_file_size(a)
244 == 5 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4 + 8);
246 lzma_index_end(a, NULL);
250 lzma_vli stream_size = lzma_index_stream_size(a);
252 expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
253 expect(lzma_index_file_size(a) == stream_size * 2 + 4);
254 expect(lzma_index_stream_size(a) > stream_size);
255 expect(lzma_index_stream_size(a) < stream_size * 2);
259 expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
260 expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
261 expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
263 lzma_index_end(a, NULL);
267 stream_size = lzma_index_stream_size(a);
269 expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
270 expect(lzma_index_file_size(a) == stream_size * 2 + 4);
271 expect(lzma_index_stream_size(a) > stream_size);
272 expect(lzma_index_stream_size(a) < stream_size * 2);
276 expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
277 expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
278 expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
280 lzma_index_end(a, NULL);
288 lzma_index *i = lzma_index_init(NULL, NULL);
291 // Cannot locate anything from an empty Index.
292 expect(lzma_index_locate(i, &r, 0));
293 expect(lzma_index_locate(i, &r, 555));
295 // One empty Record: nothing is found since there's no uncompressed
297 expect(lzma_index_append(i, NULL, 16, 0) == LZMA_OK);
298 expect(lzma_index_locate(i, &r, 0));
300 // Non-empty Record and we can find something.
301 expect(lzma_index_append(i, NULL, 32, 5) == LZMA_OK);
302 expect(!lzma_index_locate(i, &r, 0));
303 expect(r.total_size == 32);
304 expect(r.uncompressed_size == 5);
305 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
306 expect(r.uncompressed_offset == 0);
308 // Still cannot find anything past the end.
309 expect(lzma_index_locate(i, &r, 5));
311 // Add the third Record.
312 expect(lzma_index_append(i, NULL, 40, 11) == LZMA_OK);
314 expect(!lzma_index_locate(i, &r, 0));
315 expect(r.total_size == 32);
316 expect(r.uncompressed_size == 5);
317 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
318 expect(r.uncompressed_offset == 0);
320 expect(!lzma_index_read(i, &r));
321 expect(r.total_size == 40);
322 expect(r.uncompressed_size == 11);
323 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
324 expect(r.uncompressed_offset == 5);
326 expect(!lzma_index_locate(i, &r, 2));
327 expect(r.total_size == 32);
328 expect(r.uncompressed_size == 5);
329 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
330 expect(r.uncompressed_offset == 0);
332 expect(!lzma_index_locate(i, &r, 5));
333 expect(r.total_size == 40);
334 expect(r.uncompressed_size == 11);
335 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
336 expect(r.uncompressed_offset == 5);
338 expect(!lzma_index_locate(i, &r, 5 + 11 - 1));
339 expect(r.total_size == 40);
340 expect(r.uncompressed_size == 11);
341 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
342 expect(r.uncompressed_offset == 5);
344 expect(lzma_index_locate(i, &r, 5 + 11));
345 expect(lzma_index_locate(i, &r, 5 + 15));
348 i = lzma_index_init(i, NULL);
351 for (size_t n = 4; n <= 4 * 5555; n += 4)
352 expect(lzma_index_append(i, NULL, n + 8, n) == LZMA_OK);
354 expect(lzma_index_count(i) == 5555);
357 expect(!lzma_index_locate(i, &r, 0));
358 expect(r.total_size == 4 + 8);
359 expect(r.uncompressed_size == 4);
360 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
361 expect(r.uncompressed_offset == 0);
363 expect(!lzma_index_locate(i, &r, 3));
364 expect(r.total_size == 4 + 8);
365 expect(r.uncompressed_size == 4);
366 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
367 expect(r.uncompressed_offset == 0);
370 expect(!lzma_index_locate(i, &r, 4));
371 expect(r.total_size == 2 * 4 + 8);
372 expect(r.uncompressed_size == 2 * 4);
373 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 4 + 8);
374 expect(r.uncompressed_offset == 4);
377 expect(!lzma_index_locate(i, &r, lzma_index_uncompressed_size(i) - 1));
378 expect(r.total_size == 4 * 5555 + 8);
379 expect(r.uncompressed_size == 4 * 5555);
380 expect(r.stream_offset == lzma_index_total_size(i)
381 + LZMA_STREAM_HEADER_SIZE - 4 * 5555 - 8);
382 expect(r.uncompressed_offset
383 == lzma_index_uncompressed_size(i) - 4 * 5555);
385 // Allocation chunk boundaries. See INDEX_GROUP_SIZE in
386 // liblzma/common/index.c.
387 const size_t group_multiple = 256 * 4;
388 const size_t radius = 8;
389 const size_t start = group_multiple - radius;
393 for (n = 1; n < start; ++n) {
398 while (n < start + 2 * radius) {
399 expect(!lzma_index_locate(i, &r, ubase + n * 4));
401 expect(r.stream_offset == tbase + n * 4 + 8
402 + LZMA_STREAM_HEADER_SIZE);
403 expect(r.uncompressed_offset == ubase + n * 4);
409 expect(r.total_size == n * 4 + 8);
410 expect(r.uncompressed_size == n * 4);
413 // Do it also backwards since lzma_index_locate() uses relative search.
415 expect(!lzma_index_locate(i, &r, ubase + (n - 1) * 4));
417 expect(r.total_size == n * 4 + 8);
418 expect(r.uncompressed_size == n * 4);
424 expect(r.stream_offset == tbase + n * 4 + 8
425 + LZMA_STREAM_HEADER_SIZE);
426 expect(r.uncompressed_offset == ubase + n * 4);
429 // Test locating in concatend Index.
430 i = lzma_index_init(i, NULL);
432 for (n = 0; n < group_multiple; ++n)
433 expect(lzma_index_append(i, NULL, 8, 0) == LZMA_OK);
434 expect(lzma_index_append(i, NULL, 16, 1) == LZMA_OK);
435 expect(!lzma_index_locate(i, &r, 0));
436 expect(r.total_size == 16);
437 expect(r.uncompressed_size == 1);
438 expect(r.stream_offset
439 == LZMA_STREAM_HEADER_SIZE + group_multiple * 8);
440 expect(r.uncompressed_offset == 0);
442 lzma_index_end(i, NULL);
449 const size_t alloc_size = 128 * 1024;
450 uint8_t *buf = malloc(alloc_size);
452 lzma_stream strm = LZMA_STREAM_INIT;
454 lzma_index *i = create_empty();
455 expect(lzma_index_append(i, NULL, 0, 1) == LZMA_PROG_ERROR);
456 lzma_index_end(i, NULL);
458 // Create a valid Index and corrupt it in different ways.
460 expect(lzma_index_encoder(&strm, i) == LZMA_OK);
461 succeed(coder_loop(&strm, NULL, 0, buf, 20,
462 LZMA_STREAM_END, LZMA_RUN));
463 lzma_index_end(i, NULL);
465 // Wrong Index Indicator
467 expect(lzma_index_decoder(&strm, &i) == LZMA_OK);
468 succeed(decoder_loop_ret(&strm, buf, 1, LZMA_DATA_ERROR));
471 // Wrong Number of Records and thus CRC32 fails.
473 expect(lzma_index_decoder(&strm, &i) == LZMA_OK);
474 succeed(decoder_loop_ret(&strm, buf, 10, LZMA_DATA_ERROR));
479 expect(lzma_index_decoder(&strm, &i) == LZMA_OK);
480 succeed(decoder_loop_ret(&strm, buf, 16, LZMA_DATA_ERROR));
496 lzma_index *i = create_empty();
498 lzma_index_end(i, NULL);
502 lzma_index_end(i, NULL);
506 lzma_index_end(i, NULL);