src/liblzma/common/index.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       index.c
   4 /// \brief      Handling of Index
   5 //
   6 //  Copyright (C) 2007 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 "index.h"
  21
  22
  23 /// Number of Records to allocate at once in the unrolled list.
  24 #define INDEX_GROUP_SIZE 256
  25
  26
  27 typedef struct lzma_index_group_s lzma_index_group;
  28 struct lzma_index_group_s {
  29         /// Previous group
  30         lzma_index_group *prev;
  31
  32         /// Next group
  33         lzma_index_group *next;
  34
  35         /// Index of the last Record in this group
  36         size_t last;
  37
  38         /// Unpadded Size fields as special cumulative sum relative to the
  39         /// beginning of the group. It's special in sense that the previous
  40         /// value is rounded up the next multiple of four with before
  41         /// calculating the new value. The total encoded size of the Blocks
  42         /// in the group is unpadded_sums[last] rounded up to the next
  43         /// multiple of four.
  44         ///
  45         /// For example, if the Unpadded Sizes are 39, 57, and 81, the stored
  46         /// values are 39, 97 (40 + 57), and 181 (100 + 181). The total
  47         /// encoded size of these Blocks is 184.
  48         ///
  49         /// This encoding is nice from point of view of lzma_index_locate().
  50         lzma_vli unpadded_sums[INDEX_GROUP_SIZE];
  51
  52         /// Uncompressed Size fields as cumulative sum relative to the
  53         /// beginning of the group. The uncompressed size of the group is
  54         /// uncompressed_sums[last].
  55         lzma_vli uncompressed_sums[INDEX_GROUP_SIZE];
  56
  57         /// True if the Record is padding
  58         bool paddings[INDEX_GROUP_SIZE];
  59 };
  60
  61
  62 struct lzma_index_s {
  63         /// Total size of the Blocks and padding
  64         lzma_vli total_size;
  65
  66         /// Uncompressed size of the Stream
  67         lzma_vli uncompressed_size;
  68
  69         /// Number of non-padding records. This is needed for Index encoder.
  70         lzma_vli count;
  71
  72         /// Size of the List of Records field; this is updated every time
  73         /// a new non-padding Record is added.
  74         lzma_vli index_list_size;
  75
  76         /// First group of Records
  77         lzma_index_group *head;
  78
  79         /// Last group of Records
  80         lzma_index_group *tail;
  81
  82         /// Tracking the read position
  83         struct {
  84                 /// Group where the current read position is.
  85                 lzma_index_group *group;
  86
  87                 /// The most recently read Record in *group
  88                 size_t record;
  89
  90                 /// Uncompressed offset of the beginning of *group relative
  91                 /// to the beginning of the Stream
  92                 lzma_vli uncompressed_offset;
  93
  94                 /// Compressed offset of the beginning of *group relative
  95                 /// to the beginning of the Stream
  96                 lzma_vli stream_offset;
  97         } current;
  98
  99         /// Information about earlier Indexes when multiple Indexes have
 100         /// been combined.
 101         struct {
 102                 /// Sum of the Record counts of the all but the last Stream.
 103                 lzma_vli count;
 104
 105                 /// Sum of the List of Records fields of all but the last
 106                 /// Stream. This is needed when a new Index is concatenated
 107                 /// to this lzma_index structure.
 108                 lzma_vli index_list_size;
 109
 110                 /// Total size of all but the last Stream and all Stream
 111                 /// Padding fields.
 112                 lzma_vli streams_size;
 113         } old;
 114 };
 115
 116
 117 static void
 118 free_index_list(lzma_index *i, lzma_allocator *allocator)
 119 {
 120         lzma_index_group *g = i->head;
 121
 122         while (g != NULL) {
 123                 lzma_index_group *tmp = g->next;
 124                 lzma_free(g, allocator);
 125                 g = tmp;
 126         }
 127
 128         return;
 129 }
 130
 131
 132 extern LZMA_API lzma_index *
 133 lzma_index_init(lzma_index *i, lzma_allocator *allocator)
 134 {
 135         if (i == NULL) {
 136                 i = lzma_alloc(sizeof(lzma_index), allocator);
 137                 if (i == NULL)
 138                         return NULL;
 139         } else {
 140                 free_index_list(i, allocator);
 141         }
 142
 143         i->total_size = 0;
 144         i->uncompressed_size = 0;
 145         i->count = 0;
 146         i->index_list_size = 0;
 147         i->head = NULL;
 148         i->tail = NULL;
 149         i->current.group = NULL;
 150         i->old.count = 0;
 151         i->old.index_list_size = 0;
 152         i->old.streams_size = 0;
 153
 154         return i;
 155 }
 156
 157
 158 extern LZMA_API void
 159 lzma_index_end(lzma_index *i, lzma_allocator *allocator)
 160 {
 161         if (i != NULL) {
 162                 free_index_list(i, allocator);
 163                 lzma_free(i, allocator);
 164         }
 165
 166         return;
 167 }
 168
 169
 170 extern LZMA_API lzma_vli
 171 lzma_index_count(const lzma_index *i)
 172 {
 173         return i->count;
 174 }
 175
 176
 177 extern LZMA_API lzma_vli
 178 lzma_index_size(const lzma_index *i)
 179 {
 180         return index_size(i->count, i->index_list_size);
 181 }
 182
 183
 184 extern LZMA_API lzma_vli
 185 lzma_index_total_size(const lzma_index *i)
 186 {
 187         return i->total_size;
 188 }
 189
 190
 191 extern LZMA_API lzma_vli
 192 lzma_index_stream_size(const lzma_index *i)
 193 {
 194         // Stream Header + Blocks + Index + Stream Footer
 195         return LZMA_STREAM_HEADER_SIZE + i->total_size
 196                         + index_size(i->count, i->index_list_size)
 197                         + LZMA_STREAM_HEADER_SIZE;
 198 }
 199
 200
 201 extern LZMA_API lzma_vli
 202 lzma_index_file_size(const lzma_index *i)
 203 {
 204         // If multiple Streams are concatenated, the Stream Header, Index,
 205         // and Stream Footer fields of all but the last Stream are already
 206         // included in old.streams_size. Thus, we need to calculate only the
 207         // size of the last Index, not all Indexes.
 208         return i->old.streams_size + LZMA_STREAM_HEADER_SIZE + i->total_size
 209                         + index_size(i->count - i->old.count,
 210                                 i->index_list_size - i->old.index_list_size)
 211                         + LZMA_STREAM_HEADER_SIZE;
 212 }
 213
 214
 215 extern LZMA_API lzma_vli
 216 lzma_index_uncompressed_size(const lzma_index *i)
 217 {
 218         return i->uncompressed_size;
 219 }
 220
 221
 222 extern uint32_t
 223 lzma_index_padding_size(const lzma_index *i)
 224 {
 225         return (LZMA_VLI_C(4)
 226                 - index_size_unpadded(i->count, i->index_list_size)) & 3;
 227 }
 228
 229
 230 /// Appends a new Record to the Index. If needed, this allocates a new
 231 /// Record group.
 232 static lzma_ret
 233 index_append_real(lzma_index *i, lzma_allocator *allocator,
 234                 lzma_vli unpadded_size, lzma_vli uncompressed_size,
 235                 bool is_padding)
 236 {
 237         // Add the new record.
 238         if (i->tail == NULL || i->tail->last == INDEX_GROUP_SIZE - 1) {
 239                 // Allocate a new group.
 240                 lzma_index_group *g = lzma_alloc(sizeof(lzma_index_group),
 241                                 allocator);
 242                 if (g == NULL)
 243                         return LZMA_MEM_ERROR;
 244
 245                 // Initialize the group and set its first record.
 246                 g->prev = i->tail;
 247                 g->next = NULL;
 248                 g->last = 0;
 249                 g->unpadded_sums[0] = unpadded_size;
 250                 g->uncompressed_sums[0] = uncompressed_size;
 251                 g->paddings[0] = is_padding;
 252
 253                 // If this is the first group, make it the head.
 254                 if (i->head == NULL)
 255                         i->head = g;
 256                 else
 257                         i->tail->next = g;
 258
 259                 // Make it the new tail.
 260                 i->tail = g;
 261
 262         } else {
 263                 // i->tail has space left for at least one record.
 264                 i->tail->unpadded_sums[i->tail->last + 1]
 265                                 = unpadded_size + vli_ceil4(
 266                                         i->tail->unpadded_sums[i->tail->last]);
 267                 i->tail->uncompressed_sums[i->tail->last + 1]
 268                                 = i->tail->uncompressed_sums[i->tail->last]
 269                                         + uncompressed_size;
 270                 i->tail->paddings[i->tail->last + 1] = is_padding;
 271                 ++i->tail->last;
 272         }
 273
 274         return LZMA_OK;
 275 }
 276
 277
 278 extern LZMA_API lzma_ret
 279 lzma_index_append(lzma_index *i, lzma_allocator *allocator,
 280                 lzma_vli unpadded_size, lzma_vli uncompressed_size)
 281 {
 282         if (unpadded_size < UNPADDED_SIZE_MIN
 283                         || unpadded_size > UNPADDED_SIZE_MAX
 284                         || uncompressed_size > LZMA_VLI_MAX)
 285                 return LZMA_PROG_ERROR;
 286
 287         // This looks a bit ugly. We want to first validate that the Index
 288         // and Stream stay in valid limits after adding this Record. After
 289         // validating, we may need to allocate a new lzma_index_group (it's
 290         // slightly more correct to validate before allocating, YMMV).
 291         lzma_ret ret;
 292
 293         // First update the overall info so we can validate it.
 294         const lzma_vli index_list_size_add = lzma_vli_size(unpadded_size)
 295                         + lzma_vli_size(uncompressed_size);
 296
 297         const lzma_vli total_size = vli_ceil4(unpadded_size);
 298
 299         i->total_size += total_size;
 300         i->uncompressed_size += uncompressed_size;
 301         ++i->count;
 302         i->index_list_size += index_list_size_add;
 303
 304         if (i->total_size > LZMA_VLI_MAX
 305                         || i->uncompressed_size > LZMA_VLI_MAX
 306                         || lzma_index_size(i) > LZMA_BACKWARD_SIZE_MAX
 307                         || lzma_index_file_size(i) > LZMA_VLI_MAX)
 308                 ret = LZMA_DATA_ERROR; // Would grow past the limits.
 309         else
 310                 ret = index_append_real(i, allocator, unpadded_size,
 311                                 uncompressed_size, false);
 312
 313         if (ret != LZMA_OK) {
 314                 // Something went wrong. Undo the updates.
 315                 i->total_size -= total_size;
 316                 i->uncompressed_size -= uncompressed_size;
 317                 --i->count;
 318                 i->index_list_size -= index_list_size_add;
 319         }
 320
 321         return ret;
 322 }
 323
 324
 325 /// Initialize i->current to point to the first Record.
 326 static bool
 327 init_current(lzma_index *i)
 328 {
 329         if (i->head == NULL) {
 330                 assert(i->count == 0);
 331                 return true;
 332         }
 333
 334         assert(i->count > 0);
 335
 336         i->current.group = i->head;
 337         i->current.record = 0;
 338         i->current.stream_offset = LZMA_STREAM_HEADER_SIZE;
 339         i->current.uncompressed_offset = 0;
 340
 341         return false;
 342 }
 343
 344
 345 /// Go backward to the previous group.
 346 static void
 347 previous_group(lzma_index *i)
 348 {
 349         assert(i->current.group->prev != NULL);
 350
 351         // Go to the previous group first.
 352         i->current.group = i->current.group->prev;
 353         i->current.record = i->current.group->last;
 354
 355         // Then update the offsets.
 356         i->current.stream_offset -= vli_ceil4(i->current.group->unpadded_sums[
 357                         i->current.group->last]);
 358         i->current.uncompressed_offset -= i->current.group->uncompressed_sums[
 359                         i->current.group->last];
 360
 361         return;
 362 }
 363
 364
 365 /// Go forward to the next group.
 366 static void
 367 next_group(lzma_index *i)
 368 {
 369         assert(i->current.group->next != NULL);
 370
 371         // Update the offsets first.
 372         i->current.stream_offset += vli_ceil4(i->current.group->unpadded_sums[
 373                         i->current.group->last]);
 374         i->current.uncompressed_offset += i->current.group
 375                         ->uncompressed_sums[i->current.group->last];
 376
 377         // Then go to the next group.
 378         i->current.record = 0;
 379         i->current.group = i->current.group->next;
 380
 381         return;
 382 }
 383
 384
 385 /// Set *info from i->current.
 386 static void
 387 set_info(const lzma_index *i, lzma_index_record *info)
 388 {
 389         // First copy the cumulative sizes from the current Record of the
 390         // current group.
 391         info->unpadded_size
 392                         = i->current.group->unpadded_sums[i->current.record];
 393         info->total_size = vli_ceil4(info->unpadded_size);
 394         info->uncompressed_size = i->current.group->uncompressed_sums[
 395                         i->current.record];
 396
 397         // Copy the start offsets of this group.
 398         info->stream_offset = i->current.stream_offset;
 399         info->uncompressed_offset = i->current.uncompressed_offset;
 400
 401         // If it's not the first Record in this group, we need to do some
 402         // adjustements.
 403         if (i->current.record > 0) {
 404                 // Since the _sums[] are cumulative, we substract the sums of
 405                 // the previous Record to get the sizes of the current Record,
 406                 // and add the sums of the previous Record to the offsets.
 407                 // With unpadded_sums[] we need to take into account that it
 408                 // uses a bit weird way to do the cumulative summing
 409                 const lzma_vli total_sum
 410                                 = vli_ceil4(i->current.group->unpadded_sums[
 411                                         i->current.record - 1]);
 412
 413                 const lzma_vli uncompressed_sum = i->current.group
 414                                 ->uncompressed_sums[i->current.record - 1];
 415
 416                 info->total_size -= total_sum;
 417                 info->unpadded_size -= total_sum;
 418                 info->uncompressed_size -= uncompressed_sum;
 419
 420                 info->stream_offset += total_sum;
 421                 info->uncompressed_offset += uncompressed_sum;
 422         }
 423
 424         return;
 425 }
 426
 427
 428 extern LZMA_API lzma_bool
 429 lzma_index_read(lzma_index *i, lzma_index_record *info)
 430 {
 431         if (i->current.group == NULL) {
 432                 // We are at the beginning of the Record list. Set up
 433                 // i->current point at the first Record. Return if there
 434                 // are no Records.
 435                 if (init_current(i))
 436                         return true;
 437         } else do {
 438                 // Try to go the next Record.
 439                 if (i->current.record < i->current.group->last)
 440                         ++i->current.record;
 441                 else if (i->current.group->next == NULL)
 442                         return true;
 443                 else
 444                         next_group(i);
 445         } while (i->current.group->paddings[i->current.record]);
 446
 447         // We found a new Record. Set the information to *info.
 448         set_info(i, info);
 449
 450         return false;
 451 }
 452
 453
 454 extern LZMA_API void
 455 lzma_index_rewind(lzma_index *i)
 456 {
 457         i->current.group = NULL;
 458         return;
 459 }
 460
 461
 462 extern LZMA_API lzma_bool
 463 lzma_index_locate(lzma_index *i, lzma_index_record *info, lzma_vli target)
 464 {
 465         // Check if it is possible to fullfill the request.
 466         if (target >= i->uncompressed_size)
 467                 return true;
 468
 469         // Now we know that we will have an answer. Initialize the current
 470         // read position if needed.
 471         if (i->current.group == NULL && init_current(i))
 472                 return true;
 473
 474         // Locate the group where the wanted Block is. First search forward.
 475         while (i->current.uncompressed_offset <= target) {
 476                 // If the first uncompressed byte of the next group is past
 477                 // the target offset, it has to be this or an earlier group.
 478                 if (i->current.uncompressed_offset + i->current.group
 479                                 ->uncompressed_sums[i->current.group->last]
 480                                 > target)
 481                         break;
 482
 483                 // Go forward to the next group.
 484                 next_group(i);
 485         }
 486
 487         // Then search backward.
 488         while (i->current.uncompressed_offset > target)
 489                 previous_group(i);
 490
 491         // Now the target Block is somewhere in i->current.group. Offsets
 492         // in groups are relative to the beginning of the group, thus
 493         // we must adjust the target before starting the search loop.
 494         assert(target >= i->current.uncompressed_offset);
 495         target -= i->current.uncompressed_offset;
 496
 497         // Use binary search to locate the exact Record. It is the first
 498         // Record whose uncompressed_sums[] value is greater than target.
 499         // This is because we want the rightmost Record that fullfills the
 500         // search criterion. It is possible that there are empty Blocks or
 501         // padding, we don't want to return them.
 502         size_t left = 0;
 503         size_t right = i->current.group->last;
 504
 505         while (left < right) {
 506                 const size_t pos = left + (right - left) / 2;
 507                 if (i->current.group->uncompressed_sums[pos] <= target)
 508                         left = pos + 1;
 509                 else
 510                         right = pos;
 511         }
 512
 513         i->current.record = left;
 514
 515 #ifndef NDEBUG
 516         // The found Record must not be padding or have zero uncompressed size.
 517         assert(!i->current.group->paddings[i->current.record]);
 518
 519         if (i->current.record == 0)
 520                 assert(i->current.group->uncompressed_sums[0] > 0);
 521         else
 522                 assert(i->current.group->uncompressed_sums[i->current.record]
 523                                 - i->current.group->uncompressed_sums[
 524                                         i->current.record - 1] > 0);
 525 #endif
 526
 527         set_info(i, info);
 528
 529         return false;
 530 }
 531
 532
 533 extern LZMA_API lzma_ret
 534 lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,
 535                 lzma_allocator *allocator, lzma_vli padding)
 536 {
 537         if (dest == NULL || src == NULL || dest == src
 538                         || padding > LZMA_VLI_MAX)
 539                 return LZMA_PROG_ERROR;
 540
 541         // Check that the combined size of the Indexes stays within limits.
 542         {
 543                 const lzma_vli dest_size = index_size_unpadded(
 544                                 dest->count, dest->index_list_size);
 545                 const lzma_vli src_size = index_size_unpadded(
 546                                 src->count, src->index_list_size);
 547                 if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX)
 548                         return LZMA_DATA_ERROR;
 549         }
 550
 551         // Check that the combined size of the "files" (combined total
 552         // encoded sizes) stays within limits.
 553         {
 554                 const lzma_vli dest_size = lzma_index_file_size(dest);
 555                 const lzma_vli src_size = lzma_index_file_size(src);
 556                 if (dest_size + src_size > LZMA_VLI_MAX
 557                                 || dest_size + src_size + padding
 558                                         > LZMA_VLI_MAX)
 559                         return LZMA_DATA_ERROR;
 560         }
 561
 562         // Add a padding Record to take into account the size of
 563         // Index + Stream Footer + Stream Padding + Stream Header.
 564         //
 565         // NOTE: This cannot overflow, because Index Size is always
 566         // far smaller than LZMA_VLI_MAX, and adding two VLIs
 567         // (Index Size and padding) doesn't overflow.
 568         padding += index_size(dest->count - dest->old.count,
 569                                 dest->index_list_size
 570                                         - dest->old.index_list_size)
 571                         + LZMA_STREAM_HEADER_SIZE * 2;
 572
 573         // While the above cannot overflow, but it may become an invalid VLI.
 574         if (padding > LZMA_VLI_MAX)
 575                 return LZMA_DATA_ERROR;
 576
 577         // Add the padding Record.
 578         {
 579                 lzma_ret ret;
 580
 581                 // First update the info so we can validate it.
 582                 dest->old.streams_size += padding;
 583
 584                 if (dest->old.streams_size > LZMA_VLI_MAX
 585                                 || lzma_index_file_size(dest) > LZMA_VLI_MAX)
 586                         ret = LZMA_DATA_ERROR; // Would grow past the limits.
 587                 else
 588                         ret = index_append_real(dest, allocator,
 589                                         padding, 0, true);
 590
 591                 // If something went wrong, undo the updated value and return
 592                 // the error.
 593                 if (ret != LZMA_OK) {
 594                         dest->old.streams_size -= padding;
 595                         return ret;
 596                 }
 597         }
 598
 599         // Avoid wasting lots of memory if src->head has only a few records
 600         // that fit into dest->tail. That is, combine two groups if possible.
 601         //
 602         // NOTE: We know that dest->tail != NULL since we just appended
 603         // a padding Record. But we don't know about src->head.
 604         if (src->head != NULL && src->head->last + 1
 605                         <= INDEX_GROUP_SIZE - dest->tail->last - 1) {
 606                 // Copy the first Record.
 607                 dest->tail->unpadded_sums[dest->tail->last + 1]
 608                                 = vli_ceil4(dest->tail->unpadded_sums[
 609                                         dest->tail->last])
 610                                 + src->head->unpadded_sums[0];
 611
 612                 dest->tail->uncompressed_sums[dest->tail->last + 1]
 613                         = dest->tail->uncompressed_sums[dest->tail->last]
 614                                 + src->head->uncompressed_sums[0];
 615
 616                 dest->tail->paddings[dest->tail->last + 1]
 617                                 = src->head->paddings[0];
 618
 619                 ++dest->tail->last;
 620
 621                 // Copy the rest.
 622                 for (size_t i = 1; i < src->head->last; ++i) {
 623                         dest->tail->unpadded_sums[dest->tail->last + 1]
 624                                 = vli_ceil4(dest->tail->unpadded_sums[
 625                                                 dest->tail->last])
 626                                         + src->head->unpadded_sums[i + 1]
 627                                         - src->head->unpadded_sums[i];
 628
 629                         dest->tail->uncompressed_sums[dest->tail->last + 1]
 630                                 = dest->tail->uncompressed_sums[
 631                                                 dest->tail->last]
 632                                         + src->head->uncompressed_sums[i + 1]
 633                                         - src->head->uncompressed_sums[i];
 634
 635                         dest->tail->paddings[dest->tail->last + 1]
 636                                 = src->head->paddings[i + 1];
 637
 638                         ++dest->tail->last;
 639                 }
 640
 641                 // Free the head group of *src. Don't bother updating prev
 642                 // pointers since those won't be used for anything before
 643                 // we deallocate the whole *src structure.
 644                 lzma_index_group *tmp = src->head;
 645                 src->head = src->head->next;
 646                 lzma_free(tmp, allocator);
 647         }
 648
 649         // If there are groups left in *src, join them as is. Note that if we
 650         // are combining already combined Indexes, src->head can be non-NULL
 651         // even if we just combined the old src->head to dest->tail.
 652         if (src->head != NULL) {
 653                 src->head->prev = dest->tail;
 654                 dest->tail->next = src->head;
 655                 dest->tail = src->tail;
 656         }
 657
 658         // Update information about earlier Indexes. Only the last Index
 659         // from *src won't be counted in dest->old. The last Index is left
 660         // open and can be even appended with lzma_index_append().
 661         dest->old.count = dest->count + src->old.count;
 662         dest->old.index_list_size
 663                         = dest->index_list_size + src->old.index_list_size;
 664         dest->old.streams_size += src->old.streams_size;
 665
 666         // Update overall information.
 667         dest->total_size += src->total_size;
 668         dest->uncompressed_size += src->uncompressed_size;
 669         dest->count += src->count;
 670         dest->index_list_size += src->index_list_size;
 671
 672         // *src has nothing left but the base structure.
 673         lzma_free(src, allocator);
 674
 675         return LZMA_OK;
 676 }
 677
 678
 679 extern LZMA_API lzma_index *
 680 lzma_index_dup(const lzma_index *src, lzma_allocator *allocator)
 681 {
 682         lzma_index *dest = lzma_alloc(sizeof(lzma_index), allocator);
 683         if (dest == NULL)
 684                 return NULL;
 685
 686         // Copy the base structure except the pointers.
 687         *dest = *src;
 688         dest->head = NULL;
 689         dest->tail = NULL;
 690         dest->current.group = NULL;
 691
 692         // Copy the Records.
 693         const lzma_index_group *src_group = src->head;
 694         while (src_group != NULL) {
 695                 // Allocate a new group.
 696                 lzma_index_group *dest_group = lzma_alloc(
 697                                 sizeof(lzma_index_group), allocator);
 698                 if (dest_group == NULL) {
 699                         lzma_index_end(dest, allocator);
 700                         return NULL;
 701                 }
 702
 703                 // Set the pointers.
 704                 dest_group->prev = dest->tail;
 705                 dest_group->next = NULL;
 706
 707                 if (dest->head == NULL)
 708                         dest->head = dest_group;
 709                 else
 710                         dest->tail->next = dest_group;
 711
 712                 dest->tail = dest_group;
 713
 714                 dest_group->last = src_group->last;
 715
 716                 // Copy the arrays so that we don't read uninitialized memory.
 717                 const size_t count = src_group->last + 1;
 718                 memcpy(dest_group->unpadded_sums, src_group->unpadded_sums,
 719                                 sizeof(lzma_vli) * count);
 720                 memcpy(dest_group->uncompressed_sums,
 721                                 src_group->uncompressed_sums,
 722                                 sizeof(lzma_vli) * count);
 723                 memcpy(dest_group->paddings, src_group->paddings,
 724                                 sizeof(bool) * count);
 725
 726                 // Copy also the read position.
 727                 if (src_group == src->current.group)
 728                         dest->current.group = dest->tail;
 729
 730                 src_group = src_group->next;
 731         }
 732
 733         return dest;
 734 }
 735
 736
 737 extern LZMA_API lzma_bool
 738 lzma_index_equal(const lzma_index *a, const lzma_index *b)
 739 {
 740         // No point to compare more if the pointers are the same.
 741         if (a == b)
 742                 return true;
 743
 744         // Compare the basic properties.
 745         if (a->total_size != b->total_size
 746                         || a->uncompressed_size != b->uncompressed_size
 747                         || a->index_list_size != b->index_list_size
 748                         || a->count != b->count)
 749                 return false;
 750
 751         // Compare the Records.
 752         const lzma_index_group *ag = a->head;
 753         const lzma_index_group *bg = b->head;
 754         while (ag != NULL && bg != NULL) {
 755                 const size_t count = ag->last + 1;
 756                 if (ag->last != bg->last
 757                                 || memcmp(ag->unpadded_sums,
 758                                         bg->unpadded_sums,
 759                                         sizeof(lzma_vli) * count) != 0
 760                                 || memcmp(ag->uncompressed_sums,
 761                                         bg->uncompressed_sums,
 762                                         sizeof(lzma_vli) * count) != 0
 763                                 || memcmp(ag->paddings, bg->paddings,
 764                                         sizeof(bool) * count) != 0)
 765                         return false;
 766
 767                 ag = ag->next;
 768                 bg = bg->next;
 769         }
 770
 771         return ag == NULL && bg == NULL;
 772 }