1 /* -*- mode: C; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: expandtab:ts=8:sw=4:softtabstop=4:
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file test_index.c
6 /// \brief Tests functions handling the lzma_index structure
7 //
8 // Author: Lasse Collin
9 //
10 // This file has been put into the public domain.
11 // You can do whatever you want with this file.
12 //
13 ///////////////////////////////////////////////////////////////////////////////
14
15 #include "tests.h"
16
17 #define MEMLIMIT (LZMA_VLI_C(1) << 20)
18
19
20 static lzma_index *
create_empty(void)21 create_empty(void)
22 {
23 lzma_index *i = lzma_index_init(NULL, NULL);
24 expect(i != NULL);
25 return i;
26 }
27
28
29 static lzma_index *
create_small(void)30 create_small(void)
31 {
32 lzma_index *i = lzma_index_init(NULL, NULL);
33 expect(i != NULL);
34 expect(lzma_index_append(i, NULL, 101, 555) == LZMA_OK);
35 expect(lzma_index_append(i, NULL, 602, 777) == LZMA_OK);
36 expect(lzma_index_append(i, NULL, 804, 999) == LZMA_OK);
37 return i;
38 }
39
40
41 static lzma_index *
create_big(void)42 create_big(void)
43 {
44 lzma_index *i = lzma_index_init(NULL, NULL);
45 expect(i != NULL);
46
47 lzma_vli total_size = 0;
48 lzma_vli uncompressed_size = 0;
49
50 // Add pseudo-random sizes (but always the same size values).
51 const size_t count = 5555;
52 uint32_t n = 11;
53 for (size_t j = 0; j < count; ++j) {
54 n = 7019 * n + 7607;
55 const uint32_t t = n * 3011;
56 expect(lzma_index_append(i, NULL, t, n) == LZMA_OK);
57 total_size += (t + 3) & ~LZMA_VLI_C(3);
58 uncompressed_size += n;
59 }
60
61 expect(lzma_index_count(i) == count);
62 expect(lzma_index_total_size(i) == total_size);
63 expect(lzma_index_uncompressed_size(i) == uncompressed_size);
64 expect(lzma_index_total_size(i) + lzma_index_size(i)
65 + 2 * LZMA_STREAM_HEADER_SIZE
66 == lzma_index_stream_size(i));
67
68 return i;
69 }
70
71
72 static void
test_equal(void)73 test_equal(void)
74 {
75 lzma_index *a = create_empty();
76 lzma_index *b = create_small();
77 lzma_index *c = create_big();
78 expect(a && b && c);
79
80 expect(lzma_index_equal(a, a));
81 expect(lzma_index_equal(b, b));
82 expect(lzma_index_equal(c, c));
83
84 expect(!lzma_index_equal(a, b));
85 expect(!lzma_index_equal(a, c));
86 expect(!lzma_index_equal(b, c));
87
88 lzma_index_end(a, NULL);
89 lzma_index_end(b, NULL);
90 lzma_index_end(c, NULL);
91 }
92
93
94 static void
test_overflow(void)95 test_overflow(void)
96 {
97 // Integer overflow tests
98 lzma_index *i = create_empty();
99
100 expect(lzma_index_append(i, NULL, LZMA_VLI_MAX - 5, 1234)
101 == LZMA_DATA_ERROR);
102
103 // TODO
104
105 lzma_index_end(i, NULL);
106 }
107
108
109 static void
test_copy(const lzma_index * i)110 test_copy(const lzma_index *i)
111 {
112 lzma_index *d = lzma_index_dup(i, NULL);
113 expect(d != NULL);
114 lzma_index_end(d, NULL);
115 }
116
117
118 static void
test_read(lzma_index * i)119 test_read(lzma_index *i)
120 {
121 lzma_index_record record;
122
123 // Try twice so we see that rewinding works.
124 for (size_t j = 0; j < 2; ++j) {
125 lzma_vli total_size = 0;
126 lzma_vli uncompressed_size = 0;
127 lzma_vli stream_offset = LZMA_STREAM_HEADER_SIZE;
128 lzma_vli uncompressed_offset = 0;
129 uint32_t count = 0;
130
131 while (!lzma_index_read(i, &record)) {
132 ++count;
133
134 total_size += record.total_size;
135 uncompressed_size += record.uncompressed_size;
136
137 expect(record.stream_offset == stream_offset);
138 expect(record.uncompressed_offset
139 == uncompressed_offset);
140
141 stream_offset += record.total_size;
142 uncompressed_offset += record.uncompressed_size;
143 }
144
145 expect(lzma_index_total_size(i) == total_size);
146 expect(lzma_index_uncompressed_size(i) == uncompressed_size);
147 expect(lzma_index_count(i) == count);
148
149 lzma_index_rewind(i);
150 }
151 }
152
153
154 static void
test_code(lzma_index * i)155 test_code(lzma_index *i)
156 {
157 const size_t alloc_size = 128 * 1024;
158 uint8_t *buf = malloc(alloc_size);
159 expect(buf != NULL);
160
161 // Encode
162 lzma_stream strm = LZMA_STREAM_INIT;
163 expect(lzma_index_encoder(&strm, i) == LZMA_OK);
164 const lzma_vli index_size = lzma_index_size(i);
165 succeed(coder_loop(&strm, NULL, 0, buf, index_size,
166 LZMA_STREAM_END, LZMA_RUN));
167
168 // Decode
169 lzma_index *d;
170 expect(lzma_index_decoder(&strm, &d, MEMLIMIT) == LZMA_OK);
171 succeed(decoder_loop(&strm, buf, index_size));
172
173 expect(lzma_index_equal(i, d));
174
175 lzma_index_end(d, NULL);
176 lzma_end(&strm);
177
178 // Decode with hashing
179 lzma_index_hash *h = lzma_index_hash_init(NULL, NULL);
180 expect(h != NULL);
181 lzma_index_rewind(i);
182 lzma_index_record r;
183 while (!lzma_index_read(i, &r))
184 expect(lzma_index_hash_append(h, r.unpadded_size,
185 r.uncompressed_size) == LZMA_OK);
186 size_t pos = 0;
187 while (pos < index_size - 1)
188 expect(lzma_index_hash_decode(h, buf, &pos, pos + 1)
189 == LZMA_OK);
190 expect(lzma_index_hash_decode(h, buf, &pos, pos + 1)
191 == LZMA_STREAM_END);
192
193 lzma_index_hash_end(h, NULL);
194
195 // Encode buffer
196 size_t buf_pos = 1;
197 expect(lzma_index_buffer_encode(i, buf, &buf_pos, index_size)
198 == LZMA_BUF_ERROR);
199 expect(buf_pos == 1);
200
201 succeed(lzma_index_buffer_encode(i, buf, &buf_pos, index_size + 1));
202 expect(buf_pos == index_size + 1);
203
204 // Decode buffer
205 buf_pos = 1;
206 uint64_t memlimit = MEMLIMIT;
207 expect(lzma_index_buffer_decode(&d, &memlimit, NULL, buf, &buf_pos,
208 index_size) == LZMA_DATA_ERROR);
209 expect(buf_pos == 1);
210 expect(d == NULL);
211
212 succeed(lzma_index_buffer_decode(&d, &memlimit, NULL, buf, &buf_pos,
213 index_size + 1));
214 expect(buf_pos == index_size + 1);
215 expect(lzma_index_equal(i, d));
216
217 lzma_index_end(d, NULL);
218
219 free(buf);
220 }
221
222
223 static void
test_many(lzma_index * i)224 test_many(lzma_index *i)
225 {
226 test_copy(i);
227 test_read(i);
228 test_code(i);
229 }
230
231
232 static void
test_cat(void)233 test_cat(void)
234 {
235 lzma_index *a, *b, *c;
236
237 // Empty Indexes
238 a = create_empty();
239 b = create_empty();
240 expect(lzma_index_cat(a, b, NULL, 0) == 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 == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
245
246 b = create_empty();
247 expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
248 expect(lzma_index_count(a) == 0);
249 expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
250 expect(lzma_index_file_size(a)
251 == 3 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
252
253 b = create_empty();
254 c = create_empty();
255 expect(lzma_index_cat(b, c, NULL, 4) == LZMA_OK);
256 expect(lzma_index_count(b) == 0);
257 expect(lzma_index_stream_size(b) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
258 expect(lzma_index_file_size(b)
259 == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4);
260
261 expect(lzma_index_cat(a, b, NULL, 8) == LZMA_OK);
262 expect(lzma_index_count(a) == 0);
263 expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
264 expect(lzma_index_file_size(a)
265 == 5 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4 + 8);
266
267 lzma_index_end(a, NULL);
268
269 // Small Indexes
270 a = create_small();
271 lzma_vli stream_size = lzma_index_stream_size(a);
272 b = create_small();
273 expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
274 expect(lzma_index_file_size(a) == stream_size * 2 + 4);
275 expect(lzma_index_stream_size(a) > stream_size);
276 expect(lzma_index_stream_size(a) < stream_size * 2);
277
278 b = create_small();
279 c = create_small();
280 expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
281 expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
282 expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
283
284 lzma_index_end(a, NULL);
285
286 // Big Indexes
287 a = create_big();
288 stream_size = lzma_index_stream_size(a);
289 b = create_big();
290 expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
291 expect(lzma_index_file_size(a) == stream_size * 2 + 4);
292 expect(lzma_index_stream_size(a) > stream_size);
293 expect(lzma_index_stream_size(a) < stream_size * 2);
294
295 b = create_big();
296 c = create_big();
297 expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
298 expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
299 expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
300
301 lzma_index_end(a, NULL);
302 }
303
304
305 static void
test_locate(void)306 test_locate(void)
307 {
308 lzma_index_record r;
309 lzma_index *i = lzma_index_init(NULL, NULL);
310 expect(i != NULL);
311
312 // Cannot locate anything from an empty Index.
313 expect(lzma_index_locate(i, &r, 0));
314 expect(lzma_index_locate(i, &r, 555));
315
316 // One empty Record: nothing is found since there's no uncompressed
317 // data.
318 expect(lzma_index_append(i, NULL, 16, 0) == LZMA_OK);
319 expect(lzma_index_locate(i, &r, 0));
320
321 // Non-empty Record and we can find something.
322 expect(lzma_index_append(i, NULL, 32, 5) == LZMA_OK);
323 expect(!lzma_index_locate(i, &r, 0));
324 expect(r.total_size == 32);
325 expect(r.uncompressed_size == 5);
326 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
327 expect(r.uncompressed_offset == 0);
328
329 // Still cannot find anything past the end.
330 expect(lzma_index_locate(i, &r, 5));
331
332 // Add the third Record.
333 expect(lzma_index_append(i, NULL, 40, 11) == LZMA_OK);
334
335 expect(!lzma_index_locate(i, &r, 0));
336 expect(r.total_size == 32);
337 expect(r.uncompressed_size == 5);
338 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
339 expect(r.uncompressed_offset == 0);
340
341 expect(!lzma_index_read(i, &r));
342 expect(r.total_size == 40);
343 expect(r.uncompressed_size == 11);
344 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
345 expect(r.uncompressed_offset == 5);
346
347 expect(!lzma_index_locate(i, &r, 2));
348 expect(r.total_size == 32);
349 expect(r.uncompressed_size == 5);
350 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
351 expect(r.uncompressed_offset == 0);
352
353 expect(!lzma_index_locate(i, &r, 5));
354 expect(r.total_size == 40);
355 expect(r.uncompressed_size == 11);
356 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
357 expect(r.uncompressed_offset == 5);
358
359 expect(!lzma_index_locate(i, &r, 5 + 11 - 1));
360 expect(r.total_size == 40);
361 expect(r.uncompressed_size == 11);
362 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
363 expect(r.uncompressed_offset == 5);
364
365 expect(lzma_index_locate(i, &r, 5 + 11));
366 expect(lzma_index_locate(i, &r, 5 + 15));
367
368 // Large Index
369 i = lzma_index_init(i, NULL);
370 expect(i != NULL);
371
372 for (size_t n = 4; n <= 4 * 5555; n += 4)
373 expect(lzma_index_append(i, NULL, n + 8, n) == LZMA_OK);
374
375 expect(lzma_index_count(i) == 5555);
376
377 // First Record
378 expect(!lzma_index_locate(i, &r, 0));
379 expect(r.total_size == 4 + 8);
380 expect(r.uncompressed_size == 4);
381 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
382 expect(r.uncompressed_offset == 0);
383
384 expect(!lzma_index_locate(i, &r, 3));
385 expect(r.total_size == 4 + 8);
386 expect(r.uncompressed_size == 4);
387 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
388 expect(r.uncompressed_offset == 0);
389
390 // Second Record
391 expect(!lzma_index_locate(i, &r, 4));
392 expect(r.total_size == 2 * 4 + 8);
393 expect(r.uncompressed_size == 2 * 4);
394 expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 4 + 8);
395 expect(r.uncompressed_offset == 4);
396
397 // Last Record
398 expect(!lzma_index_locate(i, &r, lzma_index_uncompressed_size(i) - 1));
399 expect(r.total_size == 4 * 5555 + 8);
400 expect(r.uncompressed_size == 4 * 5555);
401 expect(r.stream_offset == lzma_index_total_size(i)
402 + LZMA_STREAM_HEADER_SIZE - 4 * 5555 - 8);
403 expect(r.uncompressed_offset
404 == lzma_index_uncompressed_size(i) - 4 * 5555);
405
406 // Allocation chunk boundaries. See INDEX_GROUP_SIZE in
407 // liblzma/common/index.c.
408 const size_t group_multiple = 256 * 4;
409 const size_t radius = 8;
410 const size_t start = group_multiple - radius;
411 lzma_vli ubase = 0;
412 lzma_vli tbase = 0;
413 size_t n;
414 for (n = 1; n < start; ++n) {
415 ubase += n * 4;
416 tbase += n * 4 + 8;
417 }
418
419 while (n < start + 2 * radius) {
420 expect(!lzma_index_locate(i, &r, ubase + n * 4));
421
422 expect(r.stream_offset == tbase + n * 4 + 8
423 + LZMA_STREAM_HEADER_SIZE);
424 expect(r.uncompressed_offset == ubase + n * 4);
425
426 tbase += n * 4 + 8;
427 ubase += n * 4;
428 ++n;
429
430 expect(r.total_size == n * 4 + 8);
431 expect(r.uncompressed_size == n * 4);
432 }
433
434 // Do it also backwards since lzma_index_locate() uses relative search.
435 while (n > start) {
436 expect(!lzma_index_locate(i, &r, ubase + (n - 1) * 4));
437
438 expect(r.total_size == n * 4 + 8);
439 expect(r.uncompressed_size == n * 4);
440
441 --n;
442 tbase -= n * 4 + 8;
443 ubase -= n * 4;
444
445 expect(r.stream_offset == tbase + n * 4 + 8
446 + LZMA_STREAM_HEADER_SIZE);
447 expect(r.uncompressed_offset == ubase + n * 4);
448 }
449
450 // Test locating in concatend Index.
451 i = lzma_index_init(i, NULL);
452 expect(i != NULL);
453 for (n = 0; n < group_multiple; ++n)
454 expect(lzma_index_append(i, NULL, 8, 0) == LZMA_OK);
455 expect(lzma_index_append(i, NULL, 16, 1) == LZMA_OK);
456 expect(!lzma_index_locate(i, &r, 0));
457 expect(r.total_size == 16);
458 expect(r.uncompressed_size == 1);
459 expect(r.stream_offset
460 == LZMA_STREAM_HEADER_SIZE + group_multiple * 8);
461 expect(r.uncompressed_offset == 0);
462
463 lzma_index_end(i, NULL);
464 }
465
466
467 static void
test_corrupt(void)468 test_corrupt(void)
469 {
470 const size_t alloc_size = 128 * 1024;
471 uint8_t *buf = malloc(alloc_size);
472 expect(buf != NULL);
473 lzma_stream strm = LZMA_STREAM_INIT;
474
475 lzma_index *i = create_empty();
476 expect(lzma_index_append(i, NULL, 0, 1) == LZMA_PROG_ERROR);
477 lzma_index_end(i, NULL);
478
479 // Create a valid Index and corrupt it in different ways.
480 i = create_small();
481 expect(lzma_index_encoder(&strm, i) == LZMA_OK);
482 succeed(coder_loop(&strm, NULL, 0, buf, 20,
483 LZMA_STREAM_END, LZMA_RUN));
484 lzma_index_end(i, NULL);
485
486 // Wrong Index Indicator
487 buf[0] ^= 1;
488 expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
489 succeed(decoder_loop_ret(&strm, buf, 1, LZMA_DATA_ERROR));
490 buf[0] ^= 1;
491
492 // Wrong Number of Records and thus CRC32 fails.
493 --buf[1];
494 expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
495 succeed(decoder_loop_ret(&strm, buf, 10, LZMA_DATA_ERROR));
496 ++buf[1];
497
498 // Padding not NULs
499 buf[15] ^= 1;
500 expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
501 succeed(decoder_loop_ret(&strm, buf, 16, LZMA_DATA_ERROR));
502
503 lzma_end(&strm);
504 free(buf);
505 }
506
507
508 int
main(void)509 main(void)
510 {
511 test_equal();
512
513 test_overflow();
514
515 lzma_index *i = create_empty();
516 test_many(i);
517 lzma_index_end(i, NULL);
518
519 i = create_small();
520 test_many(i);
521 lzma_index_end(i, NULL);
522
523 i = create_big();
524 test_many(i);
525 lzma_index_end(i, NULL);
526
527 test_cat();
528
529 test_locate();
530
531 test_corrupt();
532
533 return 0;
534 }
535