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 #define SMALL_COUNT 3
  18 #define BIG_COUNT 5555
  19
  20
  21 static lzma_index *
  22 create_empty(void)
  23 {
  24         lzma_index *i = lzma_index_init(NULL, NULL);
  25         expect(i != NULL);
  26         return i;
  27 }
  28
  29
  30 static lzma_index *
  31 create_small(void)
  32 {
  33         lzma_index *i = lzma_index_init(NULL, NULL);
  34         expect(i != NULL);
  35         expect(lzma_index_append(i, NULL, 101, 555) == LZMA_OK);
  36         expect(lzma_index_append(i, NULL, 602, 777) == LZMA_OK);
  37         expect(lzma_index_append(i, NULL, 804, 999) == LZMA_OK);
  38         return i;
  39 }
  40
  41
  42 static lzma_index *
  43 create_big(void)
  44 {
  45         lzma_index *i = lzma_index_init(NULL, NULL);
  46         expect(i != NULL);
  47
  48         lzma_vli total_size = 0;
  49         lzma_vli uncompressed_size = 0;
  50
  51         // Add pseudo-random sizes (but always the same size values).
  52         uint32_t n = 11;
  53         for (size_t j = 0; j < BIG_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) == BIG_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         expect(d == NULL);
 172         succeed(decoder_loop(&strm, buf, index_size));
 173
 174         expect(lzma_index_equal(i, d));
 175
 176         lzma_index_end(d, NULL);
 177         lzma_end(&strm);
 178
 179         // Decode with hashing
 180         lzma_index_hash *h = lzma_index_hash_init(NULL, NULL);
 181         expect(h != NULL);
 182         lzma_index_rewind(i);
 183         lzma_index_record r;
 184         while (!lzma_index_read(i, &r))
 185                 expect(lzma_index_hash_append(h, r.unpadded_size,
 186                                 r.uncompressed_size) == LZMA_OK);
 187         size_t pos = 0;
 188         while (pos < index_size - 1)
 189                 expect(lzma_index_hash_decode(h, buf, &pos, pos + 1)
 190                                 == LZMA_OK);
 191         expect(lzma_index_hash_decode(h, buf, &pos, pos + 1)
 192                         == LZMA_STREAM_END);
 193
 194         lzma_index_hash_end(h, NULL);
 195
 196         // Encode buffer
 197         size_t buf_pos = 1;
 198         expect(lzma_index_buffer_encode(i, buf, &buf_pos, index_size)
 199                         == LZMA_BUF_ERROR);
 200         expect(buf_pos == 1);
 201
 202         succeed(lzma_index_buffer_encode(i, buf, &buf_pos, index_size + 1));
 203         expect(buf_pos == index_size + 1);
 204
 205         // Decode buffer
 206         buf_pos = 1;
 207         uint64_t memlimit = MEMLIMIT;
 208         expect(lzma_index_buffer_decode(&d, &memlimit, NULL, buf, &buf_pos,
 209                         index_size) == LZMA_DATA_ERROR);
 210         expect(buf_pos == 1);
 211         expect(d == NULL);
 212
 213         succeed(lzma_index_buffer_decode(&d, &memlimit, NULL, buf, &buf_pos,
 214                         index_size + 1));
 215         expect(buf_pos == index_size + 1);
 216         expect(lzma_index_equal(i, d));
 217
 218         lzma_index_end(d, NULL);
 219
 220         free(buf);
 221 }
 222
 223
 224 static void
 225 test_many(lzma_index *i)
 226 {
 227         test_copy(i);
 228         test_read(i);
 229         test_code(i);
 230 }
 231
 232
 233 static void
 234 test_cat(void)
 235 {
 236         lzma_index *a, *b, *c;
 237         lzma_index_record r;
 238
 239         // Empty Indexes
 240         a = create_empty();
 241         b = create_empty();
 242         expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
 243         expect(lzma_index_count(a) == 0);
 244         expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 245         expect(lzma_index_file_size(a)
 246                         == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
 247         expect(lzma_index_read(a, &r));
 248
 249         b = create_empty();
 250         expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
 251         expect(lzma_index_count(a) == 0);
 252         expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 253         expect(lzma_index_file_size(a)
 254                         == 3 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
 255
 256         b = create_empty();
 257         c = create_empty();
 258         expect(lzma_index_cat(b, c, NULL, 4) == LZMA_OK);
 259         expect(lzma_index_count(b) == 0);
 260         expect(lzma_index_stream_size(b) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 261         expect(lzma_index_file_size(b)
 262                         == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4);
 263
 264         expect(lzma_index_cat(a, b, NULL, 8) == LZMA_OK);
 265         expect(lzma_index_count(a) == 0);
 266         expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 267         expect(lzma_index_file_size(a)
 268                         == 5 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4 + 8);
 269
 270         expect(lzma_index_read(a, &r));
 271         lzma_index_rewind(a);
 272         expect(lzma_index_read(a, &r));
 273         lzma_index_end(a, NULL);
 274
 275         // Small Indexes
 276         a = create_small();
 277         lzma_vli stream_size = lzma_index_stream_size(a);
 278         b = create_small();
 279         expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
 280         expect(lzma_index_file_size(a) == stream_size * 2 + 4);
 281         expect(lzma_index_stream_size(a) > stream_size);
 282         expect(lzma_index_stream_size(a) < stream_size * 2);
 283
 284         b = create_small();
 285         c = create_small();
 286         expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
 287         expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
 288         expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
 289
 290         expect(lzma_index_count(a) == SMALL_COUNT * 4);
 291         for (int i = SMALL_COUNT * 4; i >= 0; --i)
 292                 expect(!lzma_index_read(a, &r) ^ (i == 0));
 293
 294         lzma_index_end(a, NULL);
 295
 296         // Mix of empty and small
 297         a = create_empty();
 298         b = create_small();
 299         expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
 300         for (int i = SMALL_COUNT; i >= 0; --i)
 301                 expect(!lzma_index_read(a, &r) ^ (i == 0));
 302
 303         lzma_index_end(a, NULL);
 304
 305         // Big Indexes
 306         a = create_big();
 307         stream_size = lzma_index_stream_size(a);
 308         b = create_big();
 309         expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
 310         expect(lzma_index_file_size(a) == stream_size * 2 + 4);
 311         expect(lzma_index_stream_size(a) > stream_size);
 312         expect(lzma_index_stream_size(a) < stream_size * 2);
 313
 314         b = create_big();
 315         c = create_big();
 316         expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
 317         expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
 318         expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
 319
 320         for (int i = BIG_COUNT * 4; i >= 0; --i)
 321                 expect(!lzma_index_read(a, &r) ^ (i == 0));
 322
 323         lzma_index_end(a, NULL);
 324 }
 325
 326
 327 static void
 328 test_locate(void)
 329 {
 330         lzma_index_record r;
 331         lzma_index *i = lzma_index_init(NULL, NULL);
 332         expect(i != NULL);
 333
 334         // Cannot locate anything from an empty Index.
 335         expect(lzma_index_locate(i, &r, 0));
 336         expect(lzma_index_locate(i, &r, 555));
 337
 338         // One empty Record: nothing is found since there's no uncompressed
 339         // data.
 340         expect(lzma_index_append(i, NULL, 16, 0) == LZMA_OK);
 341         expect(lzma_index_locate(i, &r, 0));
 342
 343         // Non-empty Record and we can find something.
 344         expect(lzma_index_append(i, NULL, 32, 5) == LZMA_OK);
 345         expect(!lzma_index_locate(i, &r, 0));
 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         // Still cannot find anything past the end.
 352         expect(lzma_index_locate(i, &r, 5));
 353
 354         // Add the third Record.
 355         expect(lzma_index_append(i, NULL, 40, 11) == LZMA_OK);
 356
 357         expect(!lzma_index_locate(i, &r, 0));
 358         expect(r.total_size == 32);
 359         expect(r.uncompressed_size == 5);
 360         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
 361         expect(r.uncompressed_offset == 0);
 362
 363         expect(!lzma_index_read(i, &r));
 364         expect(r.total_size == 40);
 365         expect(r.uncompressed_size == 11);
 366         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
 367         expect(r.uncompressed_offset == 5);
 368
 369         expect(!lzma_index_locate(i, &r, 2));
 370         expect(r.total_size == 32);
 371         expect(r.uncompressed_size == 5);
 372         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
 373         expect(r.uncompressed_offset == 0);
 374
 375         expect(!lzma_index_locate(i, &r, 5));
 376         expect(r.total_size == 40);
 377         expect(r.uncompressed_size == 11);
 378         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
 379         expect(r.uncompressed_offset == 5);
 380
 381         expect(!lzma_index_locate(i, &r, 5 + 11 - 1));
 382         expect(r.total_size == 40);
 383         expect(r.uncompressed_size == 11);
 384         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
 385         expect(r.uncompressed_offset == 5);
 386
 387         expect(lzma_index_locate(i, &r, 5 + 11));
 388         expect(lzma_index_locate(i, &r, 5 + 15));
 389
 390         // Large Index
 391         i = lzma_index_init(i, NULL);
 392         expect(i != NULL);
 393
 394         for (size_t n = 4; n <= 4 * 5555; n += 4)
 395                 expect(lzma_index_append(i, NULL, n + 8, n) == LZMA_OK);
 396
 397         expect(lzma_index_count(i) == 5555);
 398
 399         // First Record
 400         expect(!lzma_index_locate(i, &r, 0));
 401         expect(r.total_size == 4 + 8);
 402         expect(r.uncompressed_size == 4);
 403         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
 404         expect(r.uncompressed_offset == 0);
 405
 406         expect(!lzma_index_locate(i, &r, 3));
 407         expect(r.total_size == 4 + 8);
 408         expect(r.uncompressed_size == 4);
 409         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
 410         expect(r.uncompressed_offset == 0);
 411
 412         // Second Record
 413         expect(!lzma_index_locate(i, &r, 4));
 414         expect(r.total_size == 2 * 4 + 8);
 415         expect(r.uncompressed_size == 2 * 4);
 416         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 4 + 8);
 417         expect(r.uncompressed_offset == 4);
 418
 419         // Last Record
 420         expect(!lzma_index_locate(i, &r, lzma_index_uncompressed_size(i) - 1));
 421         expect(r.total_size == 4 * 5555 + 8);
 422         expect(r.uncompressed_size == 4 * 5555);
 423         expect(r.stream_offset == lzma_index_total_size(i)
 424                         + LZMA_STREAM_HEADER_SIZE - 4 * 5555 - 8);
 425         expect(r.uncompressed_offset
 426                         == lzma_index_uncompressed_size(i) - 4 * 5555);
 427
 428         // Allocation chunk boundaries. See INDEX_GROUP_SIZE in
 429         // liblzma/common/index.c.
 430         const size_t group_multiple = 256 * 4;
 431         const size_t radius = 8;
 432         const size_t start = group_multiple - radius;
 433         lzma_vli ubase = 0;
 434         lzma_vli tbase = 0;
 435         size_t n;
 436         for (n = 1; n < start; ++n) {
 437                 ubase += n * 4;
 438                 tbase += n * 4 + 8;
 439         }
 440
 441         while (n < start + 2 * radius) {
 442                 expect(!lzma_index_locate(i, &r, ubase + n * 4));
 443
 444                 expect(r.stream_offset == tbase + n * 4 + 8
 445                                 + LZMA_STREAM_HEADER_SIZE);
 446                 expect(r.uncompressed_offset == ubase + n * 4);
 447
 448                 tbase += n * 4 + 8;
 449                 ubase += n * 4;
 450                 ++n;
 451
 452                 expect(r.total_size == n * 4 + 8);
 453                 expect(r.uncompressed_size == n * 4);
 454         }
 455
 456         // Do it also backwards since lzma_index_locate() uses relative search.
 457         while (n > start) {
 458                 expect(!lzma_index_locate(i, &r, ubase + (n - 1) * 4));
 459
 460                 expect(r.total_size == n * 4 + 8);
 461                 expect(r.uncompressed_size == n * 4);
 462
 463                 --n;
 464                 tbase -= n * 4 + 8;
 465                 ubase -= n * 4;
 466
 467                 expect(r.stream_offset == tbase + n * 4 + 8
 468                                 + LZMA_STREAM_HEADER_SIZE);
 469                 expect(r.uncompressed_offset == ubase + n * 4);
 470         }
 471
 472         // Test locating in concatend Index.
 473         i = lzma_index_init(i, NULL);
 474         expect(i != NULL);
 475         for (n = 0; n < group_multiple; ++n)
 476                 expect(lzma_index_append(i, NULL, 8, 0) == LZMA_OK);
 477         expect(lzma_index_append(i, NULL, 16, 1) == LZMA_OK);
 478         expect(!lzma_index_locate(i, &r, 0));
 479         expect(r.total_size == 16);
 480         expect(r.uncompressed_size == 1);
 481         expect(r.stream_offset
 482                         == LZMA_STREAM_HEADER_SIZE + group_multiple * 8);
 483         expect(r.uncompressed_offset == 0);
 484
 485         lzma_index_end(i, NULL);
 486 }
 487
 488
 489 static void
 490 test_corrupt(void)
 491 {
 492         const size_t alloc_size = 128 * 1024;
 493         uint8_t *buf = malloc(alloc_size);
 494         expect(buf != NULL);
 495         lzma_stream strm = LZMA_STREAM_INIT;
 496
 497         lzma_index *i = create_empty();
 498         expect(lzma_index_append(i, NULL, 0, 1) == LZMA_PROG_ERROR);
 499         lzma_index_end(i, NULL);
 500
 501         // Create a valid Index and corrupt it in different ways.
 502         i = create_small();
 503         expect(lzma_index_encoder(&strm, i) == LZMA_OK);
 504         succeed(coder_loop(&strm, NULL, 0, buf, 20,
 505                         LZMA_STREAM_END, LZMA_RUN));
 506         lzma_index_end(i, NULL);
 507
 508         // Wrong Index Indicator
 509         buf[0] ^= 1;
 510         expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
 511         succeed(decoder_loop_ret(&strm, buf, 1, LZMA_DATA_ERROR));
 512         buf[0] ^= 1;
 513
 514         // Wrong Number of Records and thus CRC32 fails.
 515         --buf[1];
 516         expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
 517         succeed(decoder_loop_ret(&strm, buf, 10, LZMA_DATA_ERROR));
 518         ++buf[1];
 519
 520         // Padding not NULs
 521         buf[15] ^= 1;
 522         expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
 523         succeed(decoder_loop_ret(&strm, buf, 16, LZMA_DATA_ERROR));
 524
 525         lzma_end(&strm);
 526         free(buf);
 527 }
 528
 529
 530 int
 531 main(void)
 532 {
 533         test_equal();
 534
 535         test_overflow();
 536
 537         lzma_index *i = create_empty();
 538         test_many(i);
 539         lzma_index_end(i, NULL);
 540
 541         i = create_small();
 542         test_many(i);
 543         lzma_index_end(i, NULL);
 544
 545         i = create_big();
 546         test_many(i);
 547         lzma_index_end(i, NULL);
 548
 549         test_cat();
 550
 551         test_locate();
 552
 553         test_corrupt();
 554
 555         return 0;
 556 }