tests/test_index.c

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