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