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 *
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 *
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 }
getRegisterInfo()39 
40 
41 static lzma_index *
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
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
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
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
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
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
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
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
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
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
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