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