tests/test_index.c

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