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         free(buf);
 201 }
 202
 203
 204 static void
 205 test_many(lzma_index *i)
 206 {
 207         test_copy(i);
 208         test_read(i);
 209         test_code(i);
 210 }
 211
 212
 213 static void
 214 test_cat(void)
 215 {
 216         lzma_index *a, *b, *c;
 217
 218         // Empty Indexes
 219         a = create_empty();
 220         b = create_empty();
 221         expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
 222         expect(lzma_index_count(a) == 0);
 223         expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 224         expect(lzma_index_file_size(a)
 225                         == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
 226
 227         b = create_empty();
 228         expect(lzma_index_cat(a, b, NULL, 0) == LZMA_OK);
 229         expect(lzma_index_count(a) == 0);
 230         expect(lzma_index_stream_size(a) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 231         expect(lzma_index_file_size(a)
 232                         == 3 * (2 * LZMA_STREAM_HEADER_SIZE + 8));
 233
 234         b = create_empty();
 235         c = create_empty();
 236         expect(lzma_index_cat(b, c, NULL, 4) == LZMA_OK);
 237         expect(lzma_index_count(b) == 0);
 238         expect(lzma_index_stream_size(b) == 2 * LZMA_STREAM_HEADER_SIZE + 8);
 239         expect(lzma_index_file_size(b)
 240                         == 2 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4);
 241
 242         expect(lzma_index_cat(a, b, NULL, 8) == 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                         == 5 * (2 * LZMA_STREAM_HEADER_SIZE + 8) + 4 + 8);
 247
 248         lzma_index_end(a, NULL);
 249
 250         // Small Indexes
 251         a = create_small();
 252         lzma_vli stream_size = lzma_index_stream_size(a);
 253         b = create_small();
 254         expect(lzma_index_cat(a, b, NULL, 4) == LZMA_OK);
 255         expect(lzma_index_file_size(a) == stream_size * 2 + 4);
 256         expect(lzma_index_stream_size(a) > stream_size);
 257         expect(lzma_index_stream_size(a) < stream_size * 2);
 258
 259         b = create_small();
 260         c = create_small();
 261         expect(lzma_index_cat(b, c, NULL, 8) == LZMA_OK);
 262         expect(lzma_index_cat(a, b, NULL, 12) == LZMA_OK);
 263         expect(lzma_index_file_size(a) == stream_size * 4 + 4 + 8 + 12);
 264
 265         lzma_index_end(a, NULL);
 266
 267         // Big Indexes
 268         a = create_big();
 269         stream_size = lzma_index_stream_size(a);
 270         b = create_big();
 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_big();
 277         c = create_big();
 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
 285
 286 static void
 287 test_locate(void)
 288 {
 289         lzma_index_record r;
 290         lzma_index *i = lzma_index_init(NULL, NULL);
 291         expect(i != NULL);
 292
 293         // Cannot locate anything from an empty Index.
 294         expect(lzma_index_locate(i, &r, 0));
 295         expect(lzma_index_locate(i, &r, 555));
 296
 297         // One empty Record: nothing is found since there's no uncompressed
 298         // data.
 299         expect(lzma_index_append(i, NULL, 16, 0) == LZMA_OK);
 300         expect(lzma_index_locate(i, &r, 0));
 301
 302         // Non-empty Record and we can find something.
 303         expect(lzma_index_append(i, NULL, 32, 5) == LZMA_OK);
 304         expect(!lzma_index_locate(i, &r, 0));
 305         expect(r.total_size == 32);
 306         expect(r.uncompressed_size == 5);
 307         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
 308         expect(r.uncompressed_offset == 0);
 309
 310         // Still cannot find anything past the end.
 311         expect(lzma_index_locate(i, &r, 5));
 312
 313         // Add the third Record.
 314         expect(lzma_index_append(i, NULL, 40, 11) == LZMA_OK);
 315
 316         expect(!lzma_index_locate(i, &r, 0));
 317         expect(r.total_size == 32);
 318         expect(r.uncompressed_size == 5);
 319         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16);
 320         expect(r.uncompressed_offset == 0);
 321
 322         expect(!lzma_index_read(i, &r));
 323         expect(r.total_size == 40);
 324         expect(r.uncompressed_size == 11);
 325         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
 326         expect(r.uncompressed_offset == 5);
 327
 328         expect(!lzma_index_locate(i, &r, 2));
 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         expect(!lzma_index_locate(i, &r, 5));
 335         expect(r.total_size == 40);
 336         expect(r.uncompressed_size == 11);
 337         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
 338         expect(r.uncompressed_offset == 5);
 339
 340         expect(!lzma_index_locate(i, &r, 5 + 11 - 1));
 341         expect(r.total_size == 40);
 342         expect(r.uncompressed_size == 11);
 343         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 16 + 32);
 344         expect(r.uncompressed_offset == 5);
 345
 346         expect(lzma_index_locate(i, &r, 5 + 11));
 347         expect(lzma_index_locate(i, &r, 5 + 15));
 348
 349         // Large Index
 350         i = lzma_index_init(i, NULL);
 351         expect(i != NULL);
 352
 353         for (size_t n = 4; n <= 4 * 5555; n += 4)
 354                 expect(lzma_index_append(i, NULL, n + 8, n) == LZMA_OK);
 355
 356         expect(lzma_index_count(i) == 5555);
 357
 358         // First Record
 359         expect(!lzma_index_locate(i, &r, 0));
 360         expect(r.total_size == 4 + 8);
 361         expect(r.uncompressed_size == 4);
 362         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
 363         expect(r.uncompressed_offset == 0);
 364
 365         expect(!lzma_index_locate(i, &r, 3));
 366         expect(r.total_size == 4 + 8);
 367         expect(r.uncompressed_size == 4);
 368         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE);
 369         expect(r.uncompressed_offset == 0);
 370
 371         // Second Record
 372         expect(!lzma_index_locate(i, &r, 4));
 373         expect(r.total_size == 2 * 4 + 8);
 374         expect(r.uncompressed_size == 2 * 4);
 375         expect(r.stream_offset == LZMA_STREAM_HEADER_SIZE + 4 + 8);
 376         expect(r.uncompressed_offset == 4);
 377
 378         // Last Record
 379         expect(!lzma_index_locate(i, &r, lzma_index_uncompressed_size(i) - 1));
 380         expect(r.total_size == 4 * 5555 + 8);
 381         expect(r.uncompressed_size == 4 * 5555);
 382         expect(r.stream_offset == lzma_index_total_size(i)
 383                         + LZMA_STREAM_HEADER_SIZE - 4 * 5555 - 8);
 384         expect(r.uncompressed_offset
 385                         == lzma_index_uncompressed_size(i) - 4 * 5555);
 386
 387         // Allocation chunk boundaries. See INDEX_GROUP_SIZE in
 388         // liblzma/common/index.c.
 389         const size_t group_multiple = 256 * 4;
 390         const size_t radius = 8;
 391         const size_t start = group_multiple - radius;
 392         lzma_vli ubase = 0;
 393         lzma_vli tbase = 0;
 394         size_t n;
 395         for (n = 1; n < start; ++n) {
 396                 ubase += n * 4;
 397                 tbase += n * 4 + 8;
 398         }
 399
 400         while (n < start + 2 * radius) {
 401                 expect(!lzma_index_locate(i, &r, ubase + n * 4));
 402
 403                 expect(r.stream_offset == tbase + n * 4 + 8
 404                                 + LZMA_STREAM_HEADER_SIZE);
 405                 expect(r.uncompressed_offset == ubase + n * 4);
 406
 407                 tbase += n * 4 + 8;
 408                 ubase += n * 4;
 409                 ++n;
 410
 411                 expect(r.total_size == n * 4 + 8);
 412                 expect(r.uncompressed_size == n * 4);
 413         }
 414
 415         // Do it also backwards since lzma_index_locate() uses relative search.
 416         while (n > start) {
 417                 expect(!lzma_index_locate(i, &r, ubase + (n - 1) * 4));
 418
 419                 expect(r.total_size == n * 4 + 8);
 420                 expect(r.uncompressed_size == n * 4);
 421
 422                 --n;
 423                 tbase -= n * 4 + 8;
 424                 ubase -= n * 4;
 425
 426                 expect(r.stream_offset == tbase + n * 4 + 8
 427                                 + LZMA_STREAM_HEADER_SIZE);
 428                 expect(r.uncompressed_offset == ubase + n * 4);
 429         }
 430
 431         // Test locating in concatend Index.
 432         i = lzma_index_init(i, NULL);
 433         expect(i != NULL);
 434         for (n = 0; n < group_multiple; ++n)
 435                 expect(lzma_index_append(i, NULL, 8, 0) == LZMA_OK);
 436         expect(lzma_index_append(i, NULL, 16, 1) == LZMA_OK);
 437         expect(!lzma_index_locate(i, &r, 0));
 438         expect(r.total_size == 16);
 439         expect(r.uncompressed_size == 1);
 440         expect(r.stream_offset
 441                         == LZMA_STREAM_HEADER_SIZE + group_multiple * 8);
 442         expect(r.uncompressed_offset == 0);
 443
 444         lzma_index_end(i, NULL);
 445 }
 446
 447
 448 static void
 449 test_corrupt(void)
 450 {
 451         const size_t alloc_size = 128 * 1024;
 452         uint8_t *buf = malloc(alloc_size);
 453         expect(buf != NULL);
 454         lzma_stream strm = LZMA_STREAM_INIT;
 455
 456         lzma_index *i = create_empty();
 457         expect(lzma_index_append(i, NULL, 0, 1) == LZMA_PROG_ERROR);
 458         lzma_index_end(i, NULL);
 459
 460         // Create a valid Index and corrupt it in different ways.
 461         i = create_small();
 462         expect(lzma_index_encoder(&strm, i) == LZMA_OK);
 463         succeed(coder_loop(&strm, NULL, 0, buf, 20,
 464                         LZMA_STREAM_END, LZMA_RUN));
 465         lzma_index_end(i, NULL);
 466
 467         // Wrong Index Indicator
 468         buf[0] ^= 1;
 469         expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
 470         succeed(decoder_loop_ret(&strm, buf, 1, LZMA_DATA_ERROR));
 471         buf[0] ^= 1;
 472
 473         // Wrong Number of Records and thus CRC32 fails.
 474         --buf[1];
 475         expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
 476         succeed(decoder_loop_ret(&strm, buf, 10, LZMA_DATA_ERROR));
 477         ++buf[1];
 478
 479         // Padding not NULs
 480         buf[15] ^= 1;
 481         expect(lzma_index_decoder(&strm, &i, MEMLIMIT) == LZMA_OK);
 482         succeed(decoder_loop_ret(&strm, buf, 16, LZMA_DATA_ERROR));
 483
 484         lzma_end(&strm);
 485         free(buf);
 486 }
 487
 488
 489 int
 490 main(void)
 491 {
 492         test_equal();
 493
 494         test_overflow();
 495
 496         lzma_index *i = create_empty();
 497         test_many(i);
 498         lzma_index_end(i, NULL);
 499
 500         i = create_small();
 501         test_many(i);
 502         lzma_index_end(i, NULL);
 503
 504         i = create_big();
 505         test_many(i);
 506         lzma_index_end(i, NULL);
 507
 508         test_cat();
 509
 510         test_locate();
 511
 512         test_corrupt();
 513
 514         return 0;
 515 }