/src/CMake/Utilities/cmliblzma/liblzma/common/index.c

Source
// SPDX-License-Identifier: 0BSD

///////////////////////////////////////////////////////////////////////////////
//
/// \file       index.c
/// \brief      Handling of .xz Indexes and some other Stream information
//
//  Author:     Lasse Collin
//
///////////////////////////////////////////////////////////////////////////////

#include "common.h"
#include "index.h"
#include "stream_flags_common.h"


/// \brief      How many Records to allocate at once
///
/// This should be big enough to avoid making lots of tiny allocations
/// but small enough to avoid too much unused memory at once.
#define INDEX_GROUP_SIZE 512


/// \brief      How many Records can be allocated at once at maximum
#define PREALLOC_MAX ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))


/// \brief      Base structure for index_stream and index_group structures
typedef struct index_tree_node_s index_tree_node;
struct index_tree_node_s {
  /// Uncompressed start offset of this Stream (relative to the
  /// beginning of the file) or Block (relative to the beginning
  /// of the Stream)
  lzma_vli uncompressed_base;

  /// Compressed start offset of this Stream or Block
  lzma_vli compressed_base;

  index_tree_node *parent;
  index_tree_node *left;
  index_tree_node *right;
};


/// \brief      AVL tree to hold index_stream or index_group structures
typedef struct {
  /// Root node
  index_tree_node *root;

  /// Leftmost node. Since the tree will be filled sequentially,
  /// this won't change after the first node has been added to
  /// the tree.
  index_tree_node *leftmost;

  /// The rightmost node in the tree. Since the tree is filled
  /// sequentially, this is always the node where to add the new data.
  index_tree_node *rightmost;

  /// Number of nodes in the tree
  uint32_t count;

} index_tree;


typedef struct {
  lzma_vli uncompressed_sum;
  lzma_vli unpadded_sum;
} index_record;


typedef struct {
  /// Every Record group is part of index_stream.groups tree.
  index_tree_node node;

  /// Number of Blocks in this Stream before this group.
  lzma_vli number_base;

  /// Number of Records that can be put in records[].
  size_t allocated;

  /// Index of the last Record in use.
  size_t last;

  /// The sizes in this array are stored as cumulative sums relative
  /// to the beginning of the Stream. This makes it possible to
  /// use binary search in lzma_index_locate().
  ///
  /// Note that the cumulative summing is done specially for
  /// unpadded_sum: The previous value is rounded up to the next
  /// multiple of four before adding the Unpadded Size of the new
  /// Block. The total encoded size of the Blocks in the Stream
  /// is records[last].unpadded_sum in the last Record group of
  /// the Stream.
  ///
  /// For example, if the Unpadded Sizes are 39, 57, and 81, the
  /// stored values are 39, 97 (40 + 57), and 181 (100 + 181).
  /// The total encoded size of these Blocks is 184.
  ///
  /// This is a flexible array, because it makes easy to optimize
  /// memory usage in case someone concatenates many Streams that
  /// have only one or few Blocks.
  index_record records[];

} index_group;


typedef struct {
  /// Every index_stream is a node in the tree of Streams.
  index_tree_node node;

  /// Number of this Stream (first one is 1)
  uint32_t number;

  /// Total number of Blocks before this Stream
  lzma_vli block_number_base;

  /// Record groups of this Stream are stored in a tree.
  /// It's a T-tree with AVL-tree balancing. There are
  /// INDEX_GROUP_SIZE Records per node by default.
  /// This keeps the number of memory allocations reasonable
  /// and finding a Record is fast.
  index_tree groups;

  /// Number of Records in this Stream
  lzma_vli record_count;

  /// Size of the List of Records field in this Stream. This is used
  /// together with record_count to calculate the size of the Index
  /// field and thus the total size of the Stream.
  lzma_vli index_list_size;

  /// Stream Flags of this Stream. This is meaningful only if
  /// the Stream Flags have been told us with lzma_index_stream_flags().
  /// Initially stream_flags.version is set to UINT32_MAX to indicate
  /// that the Stream Flags are unknown.
  lzma_stream_flags stream_flags;

  /// Amount of Stream Padding after this Stream. This defaults to
  /// zero and can be set with lzma_index_stream_padding().
  lzma_vli stream_padding;

} index_stream;


struct lzma_index_s {
  /// AVL-tree containing the Stream(s). Often there is just one
  /// Stream, but using a tree keeps lookups fast even when there
  /// are many concatenated Streams.
  index_tree streams;

  /// Uncompressed size of all the Blocks in the Stream(s)
  lzma_vli uncompressed_size;

  /// Total size of all the Blocks in the Stream(s)
  lzma_vli total_size;

  /// Total number of Records in all Streams in this lzma_index
  lzma_vli record_count;

  /// Size of the List of Records field if all the Streams in this
  /// lzma_index were packed into a single Stream (makes it simpler to
  /// take many .xz files and combine them into a single Stream).
  ///
  /// This value together with record_count is needed to calculate
  /// Backward Size that is stored into Stream Footer.
  lzma_vli index_list_size;

  /// How many Records to allocate at once in lzma_index_append().
  /// This defaults to INDEX_GROUP_SIZE but can be overridden with
  /// lzma_index_prealloc().
  size_t prealloc;

  /// Bitmask indicating what integrity check types have been used
  /// as set by lzma_index_stream_flags(). The bit of the last Stream
  /// is not included here, since it is possible to change it by
  /// calling lzma_index_stream_flags() again.
  uint32_t checks;
};


static void
index_tree_init(index_tree *tree)
{
  tree->root = NULL;
  tree->leftmost = NULL;
  tree->rightmost = NULL;
  tree->count = 0;
  return;
}


/// Helper for index_tree_end()
static void
index_tree_node_end(index_tree_node *node, const lzma_allocator *allocator,
    void (*free_func)(void *node, const lzma_allocator *allocator))
{
  // The tree won't ever be very huge, so recursion should be fine.
  // 20 levels in the tree is likely quite a lot already in practice.
  if (node->left != NULL)
    index_tree_node_end(node->left, allocator, free_func);

  if (node->right != NULL)
    index_tree_node_end(node->right, allocator, free_func);

  free_func(node, allocator);
  return;
}


/// Free the memory allocated for a tree. Each node is freed using the
/// given free_func which is either &lzma_free or &index_stream_end.
/// The latter is used to free the Record groups from each index_stream
/// before freeing the index_stream itself.
static void
index_tree_end(index_tree *tree, const lzma_allocator *allocator,
    void (*free_func)(void *node, const lzma_allocator *allocator))
{
  assert(free_func != NULL);

  if (tree->root != NULL)
    index_tree_node_end(tree->root, allocator, free_func);

  return;
}


/// Add a new node to the tree. node->uncompressed_base and
/// node->compressed_base must have been set by the caller already.
static void
index_tree_append(index_tree *tree, index_tree_node *node)
{
  node->parent = tree->rightmost;
  node->left = NULL;
  node->right = NULL;

  ++tree->count;

  // Handle the special case of adding the first node.
  if (tree->root == NULL) {
    tree->root = node;
    tree->leftmost = node;
    tree->rightmost = node;
    return;
  }

  // The tree is always filled sequentially.
  assert(tree->rightmost->uncompressed_base <= node->uncompressed_base);
  assert(tree->rightmost->compressed_base < node->compressed_base);

  // Add the new node after the rightmost node. It's the correct
  // place due to the reason above.
  tree->rightmost->right = node;
  tree->rightmost = node;

  // Balance the AVL-tree if needed. We don't need to keep the balance
  // factors in nodes, because we always fill the tree sequentially,
  // and thus know the state of the tree just by looking at the node
  // count. From the node count we can calculate how many steps to go
  // up in the tree to find the rotation root.
  uint32_t up = tree->count ^ (UINT32_C(1) << bsr32(tree->count));
  if (up != 0) {
    // Locate the root node for the rotation.
    up = ctz32(tree->count) + 2;
    do {
      node = node->parent;
      #ifdef __clang_analyzer__
      assert(node);
      #endif
    } while (--up > 0);

    // Rotate left using node as the rotation root.
    index_tree_node *pivot = node->right;

    if (node->parent == NULL) {
      tree->root = pivot;
    } else {
      assert(node->parent->right == node);
      node->parent->right = pivot;
    }

    pivot->parent = node->parent;

    node->right = pivot->left;
    if (node->right != NULL)
      node->right->parent = node;

    pivot->left = node;
    node->parent = pivot;
  }

  return;
}


/// Get the next node in the tree. Return NULL if there are no more nodes.
static void *
index_tree_next(const index_tree_node *node)
{
  if (node->right != NULL) {
    node = node->right;
    while (node->left != NULL)
      node = node->left;

    return (void *)(node);
  }

  while (node->parent != NULL && node->parent->right == node)
    node = node->parent;

  return (void *)(node->parent);
}


/// Locate a node that contains the given uncompressed offset. It is
/// caller's job to check that target is not bigger than the uncompressed
/// size of the tree (the last node would be returned in that case still).
static void *
index_tree_locate(const index_tree *tree, lzma_vli target)
{
  const index_tree_node *result = NULL;
  const index_tree_node *node = tree->root;

  assert(tree->leftmost == NULL
      || tree->leftmost->uncompressed_base == 0);

  // Consecutive nodes may have the same uncompressed_base.
  // We must pick the rightmost one.
  while (node != NULL) {
    if (node->uncompressed_base > target) {
      node = node->left;
    } else {
      result = node;
      node = node->right;
    }
  }

  return (void *)(result);
}


/// Allocate and initialize a new Stream using the given base offsets.
static index_stream *
index_stream_init(lzma_vli compressed_base, lzma_vli uncompressed_base,
    uint32_t stream_number, lzma_vli block_number_base,
    const lzma_allocator *allocator)
{
  index_stream *s = lzma_alloc(sizeof(index_stream), allocator);
  if (s == NULL)
    return NULL;

  s->node.uncompressed_base = uncompressed_base;
  s->node.compressed_base = compressed_base;
  s->node.parent = NULL;
  s->node.left = NULL;
  s->node.right = NULL;

  s->number = stream_number;
  s->block_number_base = block_number_base;

  index_tree_init(&s->groups);

  s->record_count = 0;
  s->index_list_size = 0;
  s->stream_flags.version = UINT32_MAX;
  s->stream_padding = 0;

  return s;
}


/// Free the memory allocated for a Stream and its Record groups.
static void
index_stream_end(void *node, const lzma_allocator *allocator)
{
  index_stream *s = node;
  index_tree_end(&s->groups, allocator, &lzma_free);
  lzma_free(s, allocator);
  return;
}


static lzma_index *
index_init_plain(const lzma_allocator *allocator)
{
  lzma_index *i = lzma_alloc(sizeof(lzma_index), allocator);
  if (i != NULL) {
    index_tree_init(&i->streams);
    i->uncompressed_size = 0;
    i->total_size = 0;
    i->record_count = 0;
    i->index_list_size = 0;
    i->prealloc = INDEX_GROUP_SIZE;
    i->checks = 0;
  }

  return i;
}


extern LZMA_API(lzma_index *)
lzma_index_init(const lzma_allocator *allocator)
{
  lzma_index *i = index_init_plain(allocator);
  if (i == NULL)
    return NULL;

  index_stream *s = index_stream_init(0, 0, 1, 0, allocator);
  if (s == NULL) {
    lzma_free(i, allocator);
    return NULL;
  }

  index_tree_append(&i->streams, &s->node);

  return i;
}


extern LZMA_API(void)
lzma_index_end(lzma_index *i, const lzma_allocator *allocator)
{
  // NOTE: If you modify this function, check also the bottom
  // of lzma_index_cat().
  if (i != NULL) {
    index_tree_end(&i->streams, allocator, &index_stream_end);
    lzma_free(i, allocator);
  }

  return;
}


extern void
lzma_index_prealloc(lzma_index *i, lzma_vli records)
{
  if (records > PREALLOC_MAX)
    records = PREALLOC_MAX;

  i->prealloc = (size_t)(records);
  return;
}


extern LZMA_API(uint64_t)
lzma_index_memusage(lzma_vli streams, lzma_vli blocks)
{
  // This calculates an upper bound that is only a little bit
  // bigger than the exact maximum memory usage with the given
  // parameters.

  // Typical malloc() overhead is 2 * sizeof(void *) but we take
  // a little bit extra just in case. Using LZMA_MEMUSAGE_BASE
  // instead would give too inaccurate estimate.
  const size_t alloc_overhead = 4 * sizeof(void *);

  // Amount of memory needed for each Stream base structures.
  // We assume that every Stream has at least one Block and
  // thus at least one group.
  const size_t stream_base = sizeof(index_stream)
      + sizeof(index_group) + 2 * alloc_overhead;

  // Amount of memory needed per group.
  const size_t group_base = sizeof(index_group)
      + INDEX_GROUP_SIZE * sizeof(index_record)
      + alloc_overhead;

  // Number of groups. There may actually be more, but that overhead
  // has been taken into account in stream_base already.
  const lzma_vli groups
      = (blocks + INDEX_GROUP_SIZE - 1) / INDEX_GROUP_SIZE;

  // Memory used by index_stream and index_group structures.
  const uint64_t streams_mem = streams * stream_base;
  const uint64_t groups_mem = groups * group_base;

  // Memory used by the base structure.
  const uint64_t index_base = sizeof(lzma_index) + alloc_overhead;

  // Validate the arguments and catch integer overflows.
  // Maximum number of Streams is "only" UINT32_MAX, because
  // that limit is used by the tree containing the Streams.
  const uint64_t limit = UINT64_MAX - index_base;
  if (streams == 0 || streams > UINT32_MAX || blocks > LZMA_VLI_MAX
      || streams > limit / stream_base
      || groups > limit / group_base
      || limit - streams_mem < groups_mem)
    return UINT64_MAX;

  return index_base + streams_mem + groups_mem;
}


extern LZMA_API(uint64_t)
lzma_index_memused(const lzma_index *i)
{
  return lzma_index_memusage(i->streams.count, i->record_count);
}


extern LZMA_API(lzma_vli)
lzma_index_block_count(const lzma_index *i)
{
  return i->record_count;
}


extern LZMA_API(lzma_vli)
lzma_index_stream_count(const lzma_index *i)
{
  return i->streams.count;
}


extern LZMA_API(lzma_vli)
lzma_index_size(const lzma_index *i)
{
  return index_size(i->record_count, i->index_list_size);
}


extern LZMA_API(lzma_vli)
lzma_index_total_size(const lzma_index *i)
{
  return i->total_size;
}


extern LZMA_API(lzma_vli)
lzma_index_stream_size(const lzma_index *i)
{
  // Stream Header + Blocks + Index + Stream Footer
  return LZMA_STREAM_HEADER_SIZE + i->total_size
      + index_size(i->record_count, i->index_list_size)
      + LZMA_STREAM_HEADER_SIZE;
}


static lzma_vli
index_file_size(lzma_vli compressed_base, lzma_vli unpadded_sum,
    lzma_vli record_count, lzma_vli index_list_size,
    lzma_vli stream_padding)
{
  // Earlier Streams and Stream Paddings + Stream Header
  // + Blocks + Index + Stream Footer + Stream Padding
  //
  // This might go over LZMA_VLI_MAX due to too big unpadded_sum
  // when this function is used in lzma_index_append().
  lzma_vli file_size = compressed_base + 2 * LZMA_STREAM_HEADER_SIZE
      + stream_padding + vli_ceil4(unpadded_sum);
  if (file_size > LZMA_VLI_MAX)
    return LZMA_VLI_UNKNOWN;

  // The same applies here.
  file_size += index_size(record_count, index_list_size);
  if (file_size > LZMA_VLI_MAX)
    return LZMA_VLI_UNKNOWN;

  return file_size;
}


extern LZMA_API(lzma_vli)
lzma_index_file_size(const lzma_index *i)
{
  const index_stream *s = (const index_stream *)(i->streams.rightmost);
  const index_group *g = (const index_group *)(s->groups.rightmost);
  return index_file_size(s->node.compressed_base,
      g == NULL ? 0 : g->records[g->last].unpadded_sum,
      s->record_count, s->index_list_size,
      s->stream_padding);
}


extern LZMA_API(lzma_vli)
lzma_index_uncompressed_size(const lzma_index *i)
{
  return i->uncompressed_size;
}


extern LZMA_API(uint32_t)
lzma_index_checks(const lzma_index *i)
{
  uint32_t checks = i->checks;

  // Get the type of the Check of the last Stream too.
  const index_stream *s = (const index_stream *)(i->streams.rightmost);
  if (s->stream_flags.version != UINT32_MAX)
    checks |= UINT32_C(1) << s->stream_flags.check;

  return checks;
}


extern uint32_t
lzma_index_padding_size(const lzma_index *i)
{
  return (LZMA_VLI_C(4) - index_size_unpadded(
      i->record_count, i->index_list_size)) & 3;
}


extern LZMA_API(lzma_ret)
lzma_index_stream_flags(lzma_index *i, const lzma_stream_flags *stream_flags)
{
  if (i == NULL || stream_flags == NULL)
    return LZMA_PROG_ERROR;

  // Validate the Stream Flags.
  return_if_error(lzma_stream_flags_compare(
      stream_flags, stream_flags));

  index_stream *s = (index_stream *)(i->streams.rightmost);
  s->stream_flags = *stream_flags;

  return LZMA_OK;
}


extern LZMA_API(lzma_ret)
lzma_index_stream_padding(lzma_index *i, lzma_vli stream_padding)
{
  if (i == NULL || stream_padding > LZMA_VLI_MAX
      || (stream_padding & 3) != 0)
    return LZMA_PROG_ERROR;

  index_stream *s = (index_stream *)(i->streams.rightmost);

  // Check that the new value won't make the file grow too big.
  const lzma_vli old_stream_padding = s->stream_padding;
  s->stream_padding = 0;
  if (lzma_index_file_size(i) + stream_padding > LZMA_VLI_MAX) {
    s->stream_padding = old_stream_padding;
    return LZMA_DATA_ERROR;
  }

  s->stream_padding = stream_padding;
  return LZMA_OK;
}


extern LZMA_API(lzma_ret)
lzma_index_append(lzma_index *i, const lzma_allocator *allocator,
    lzma_vli unpadded_size, lzma_vli uncompressed_size)
{
  // Validate.
  if (i == NULL || unpadded_size < UNPADDED_SIZE_MIN
      || unpadded_size > UNPADDED_SIZE_MAX
      || uncompressed_size > LZMA_VLI_MAX)
    return LZMA_PROG_ERROR;

  index_stream *s = (index_stream *)(i->streams.rightmost);
  index_group *g = (index_group *)(s->groups.rightmost);

  const lzma_vli compressed_base = g == NULL ? 0
      : vli_ceil4(g->records[g->last].unpadded_sum);
  const lzma_vli uncompressed_base = g == NULL ? 0
      : g->records[g->last].uncompressed_sum;
  const uint32_t index_list_size_add = lzma_vli_size(unpadded_size)
      + lzma_vli_size(uncompressed_size);

  // Check that uncompressed size will not overflow.
  if (uncompressed_base + uncompressed_size > LZMA_VLI_MAX)
    return LZMA_DATA_ERROR;

  // Check that the new unpadded sum will not overflow. This is
  // checked again in index_file_size(), but the unpadded sum is
  // passed to vli_ceil4() which expects a valid lzma_vli value.
  if (compressed_base + unpadded_size > UNPADDED_SIZE_MAX)
    return LZMA_DATA_ERROR;

  // Check that the file size will stay within limits.
  if (index_file_size(s->node.compressed_base,
      compressed_base + unpadded_size, s->record_count + 1,
      s->index_list_size + index_list_size_add,
      s->stream_padding) == LZMA_VLI_UNKNOWN)
    return LZMA_DATA_ERROR;

  // The size of the Index field must not exceed the maximum value
  // that can be stored in the Backward Size field.
  if (index_size(i->record_count + 1,
      i->index_list_size + index_list_size_add)
      > LZMA_BACKWARD_SIZE_MAX)
    return LZMA_DATA_ERROR;

  if (g != NULL && g->last + 1 < g->allocated) {
    // There is space in the last group at least for one Record.
    ++g->last;
  } else {
    // We need to allocate a new group.
    g = lzma_alloc(sizeof(index_group)
        + i->prealloc * sizeof(index_record),
        allocator);
    if (g == NULL)
      return LZMA_MEM_ERROR;

    g->last = 0;
    g->allocated = i->prealloc;

    // Reset prealloc so that if the application happens to
    // add new Records, the allocation size will be sane.
    i->prealloc = INDEX_GROUP_SIZE;

    // Set the start offsets of this group.
    g->node.uncompressed_base = uncompressed_base;
    g->node.compressed_base = compressed_base;
    g->number_base = s->record_count + 1;

    // Add the new group to the Stream.
    index_tree_append(&s->groups, &g->node);
  }

  // Add the new Record to the group.
  g->records[g->last].uncompressed_sum
      = uncompressed_base + uncompressed_size;
  g->records[g->last].unpadded_sum
      = compressed_base + unpadded_size;

  // Update the totals.
  ++s->record_count;
  s->index_list_size += index_list_size_add;

  i->total_size += vli_ceil4(unpadded_size);
  i->uncompressed_size += uncompressed_size;
  ++i->record_count;
  i->index_list_size += index_list_size_add;

  return LZMA_OK;
}


/// Structure to pass info to index_cat_helper()
typedef struct {
  /// Uncompressed size of the destination
  lzma_vli uncompressed_size;

  /// Compressed file size of the destination
  lzma_vli file_size;

  /// Same as above but for Block numbers
  lzma_vli block_number_add;

  /// Number of Streams that were in the destination index before we
  /// started appending new Streams from the source index. This is
  /// used to fix the Stream numbering.
  uint32_t stream_number_add;

  /// Destination index' Stream tree
  index_tree *streams;

} index_cat_info;


/// Add the Stream nodes from the source index to dest using recursion.
/// Simplest iterative traversal of the source tree wouldn't work, because
/// we update the pointers in nodes when moving them to the destination tree.
static void
index_cat_helper(const index_cat_info *info, index_stream *this)
{
  index_stream *left = (index_stream *)(this->node.left);
  index_stream *right = (index_stream *)(this->node.right);

  if (left != NULL)
    index_cat_helper(info, left);

  this->node.uncompressed_base += info->uncompressed_size;
  this->node.compressed_base += info->file_size;
  this->number += info->stream_number_add;
  this->block_number_base += info->block_number_add;
  index_tree_append(info->streams, &this->node);

  if (right != NULL)
    index_cat_helper(info, right);

  return;
}


extern LZMA_API(lzma_ret)
lzma_index_cat(lzma_index *restrict dest, lzma_index *restrict src,
    const lzma_allocator *allocator)
{
  if (dest == NULL || src == NULL)
    return LZMA_PROG_ERROR;

  const lzma_vli dest_file_size = lzma_index_file_size(dest);

  // Check that we don't exceed the file size limits.
  if (dest_file_size + lzma_index_file_size(src) > LZMA_VLI_MAX
      || dest->uncompressed_size + src->uncompressed_size
        > LZMA_VLI_MAX)
    return LZMA_DATA_ERROR;

  // Check that the encoded size of the combined lzma_indexes stays
  // within limits. In theory, this should be done only if we know
  // that the user plans to actually combine the Streams and thus
  // construct a single Index (probably rare). However, exceeding
  // this limit is quite theoretical, so we do this check always
  // to simplify things elsewhere.
  {
    const lzma_vli dest_size = index_size_unpadded(
        dest->record_count, dest->index_list_size);
    const lzma_vli src_size = index_size_unpadded(
        src->record_count, src->index_list_size);
    if (vli_ceil4(dest_size + src_size) > LZMA_BACKWARD_SIZE_MAX)
      return LZMA_DATA_ERROR;
  }

  // Optimize the last group to minimize memory usage. Allocation has
  // to be done before modifying dest or src.
  {
    index_stream *s = (index_stream *)(dest->streams.rightmost);
    index_group *g = (index_group *)(s->groups.rightmost);
    if (g != NULL && g->last + 1 < g->allocated) {
      assert(g->node.left == NULL);
      assert(g->node.right == NULL);

      index_group *newg = lzma_alloc(sizeof(index_group)
          + (g->last + 1)
          * sizeof(index_record),
          allocator);
      if (newg == NULL)
        return LZMA_MEM_ERROR;

      newg->node = g->node;
      newg->allocated = g->last + 1;
      newg->last = g->last;
      newg->number_base = g->number_base;

      memcpy(newg->records, g->records, newg->allocated
          * sizeof(index_record));

      if (g->node.parent != NULL) {
        assert(g->node.parent->right == &g->node);
        g->node.parent->right = &newg->node;
      }

      if (s->groups.leftmost == &g->node) {
        assert(s->groups.root == &g->node);
        s->groups.leftmost = &newg->node;
        s->groups.root = &newg->node;
      }

      assert(s->groups.rightmost == &g->node);
      s->groups.rightmost = &newg->node;

      lzma_free(g, allocator);

      // NOTE: newg isn't leaked here because
      // newg == (void *)&newg->node.
    }
  }

  // dest->checks includes the check types of all except the last Stream
  // in dest. Set the bit for the check type of the last Stream now so
  // that it won't get lost when Stream(s) from src are appended to dest.
  dest->checks = lzma_index_checks(dest);

  // Add all the Streams from src to dest. Update the base offsets
  // of each Stream from src.
  const index_cat_info info = {
    .uncompressed_size = dest->uncompressed_size,
    .file_size = dest_file_size,
    .stream_number_add = dest->streams.count,
    .block_number_add = dest->record_count,
    .streams = &dest->streams,
  };
  index_cat_helper(&info, (index_stream *)(src->streams.root));

  // Update info about all the combined Streams.
  dest->uncompressed_size += src->uncompressed_size;
  dest->total_size += src->total_size;
  dest->record_count += src->record_count;
  dest->index_list_size += src->index_list_size;
  dest->checks |= src->checks;

  // There's nothing else left in src than the base structure.
  lzma_free(src, allocator);

  return LZMA_OK;
}


/// Duplicate an index_stream.
static index_stream *
index_dup_stream(const index_stream *src, const lzma_allocator *allocator)
{
  // Catch a somewhat theoretical integer overflow.
  if (src->record_count > PREALLOC_MAX)
    return NULL;

  // Allocate and initialize a new Stream.
  index_stream *dest = index_stream_init(src->node.compressed_base,
      src->node.uncompressed_base, src->number,
      src->block_number_base, allocator);
  if (dest == NULL)
    return NULL;

  // Copy the overall information.
  dest->record_count = src->record_count;
  dest->index_list_size = src->index_list_size;
  dest->stream_flags = src->stream_flags;
  dest->stream_padding = src->stream_padding;

  // Return if there are no groups to duplicate.
  if (src->groups.leftmost == NULL)
    return dest;

  // Allocate memory for the Records. We put all the Records into
  // a single group. It's simplest and also tends to make
  // lzma_index_locate() a little bit faster with very big Indexes.
  index_group *destg = lzma_alloc(sizeof(index_group)
      + src->record_count * sizeof(index_record),
      allocator);
  if (destg == NULL) {
    index_stream_end(dest, allocator);
    return NULL;
  }

  // Initialize destg.
  destg->node.uncompressed_base = 0;
  destg->node.compressed_base = 0;
  destg->number_base = 1;
  destg->allocated = src->record_count;
  destg->last = src->record_count - 1;

  // Go through all the groups in src and copy the Records into destg.
  const index_group *srcg = (const index_group *)(src->groups.leftmost);
  size_t i = 0;
  do {
    memcpy(destg->records + i, srcg->records,
        (srcg->last + 1) * sizeof(index_record));
    i += srcg->last + 1;
    srcg = index_tree_next(&srcg->node);
  } while (srcg != NULL);

  assert(i == destg->allocated);

  // Add the group to the new Stream.
  index_tree_append(&dest->groups, &destg->node);

  return dest;
}


extern LZMA_API(lzma_index *)
lzma_index_dup(const lzma_index *src, const lzma_allocator *allocator)
{
  // Allocate the base structure (no initial Stream).
  lzma_index *dest = index_init_plain(allocator);
  if (dest == NULL)
    return NULL;

  // Copy the totals.
  dest->uncompressed_size = src->uncompressed_size;
  dest->total_size = src->total_size;
  dest->record_count = src->record_count;
  dest->index_list_size = src->index_list_size;

  // Copy the Streams and the groups in them.
  const index_stream *srcstream
      = (const index_stream *)(src->streams.leftmost);
  do {
    index_stream *deststream = index_dup_stream(
        srcstream, allocator);
    if (deststream == NULL) {
      lzma_index_end(dest, allocator);
      return NULL;
    }

    index_tree_append(&dest->streams, &deststream->node);

    srcstream = index_tree_next(&srcstream->node);
  } while (srcstream != NULL);

  return dest;
}


/// Indexing for lzma_index_iter.internal[]
enum {
  ITER_INDEX,
  ITER_STREAM,
  ITER_GROUP,
  ITER_RECORD,
  ITER_METHOD,
};


/// Values for lzma_index_iter.internal[ITER_METHOD].s
enum {
  ITER_METHOD_NORMAL,
  ITER_METHOD_NEXT,
  ITER_METHOD_LEFTMOST,
};


static void
iter_set_info(lzma_index_iter *iter)
{
  const lzma_index *i = iter->internal[ITER_INDEX].p;
  const index_stream *stream = iter->internal[ITER_STREAM].p;
  const index_group *group = iter->internal[ITER_GROUP].p;
  const size_t record = iter->internal[ITER_RECORD].s;

  // lzma_index_iter.internal must not contain a pointer to the last
  // group in the index, because that may be reallocated by
  // lzma_index_cat().
  if (group == NULL) {
    // There are no groups.
    assert(stream->groups.root == NULL);
    iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;

  } else if (i->streams.rightmost != &stream->node
      || stream->groups.rightmost != &group->node) {
    // The group is not not the last group in the index.
    iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;

  } else if (stream->groups.leftmost != &group->node) {
    // The group isn't the only group in the Stream, thus we
    // know that it must have a parent group i.e. it's not
    // the root node.
    assert(stream->groups.root != &group->node);
    assert(group->node.parent->right == &group->node);
    iter->internal[ITER_METHOD].s = ITER_METHOD_NEXT;
    iter->internal[ITER_GROUP].p = group->node.parent;

  } else {
    // The Stream has only one group.
    assert(stream->groups.root == &group->node);
    assert(group->node.parent == NULL);
    iter->internal[ITER_METHOD].s = ITER_METHOD_LEFTMOST;
    iter->internal[ITER_GROUP].p = NULL;
  }

  // NOTE: lzma_index_iter.stream.number is lzma_vli but we use uint32_t
  // internally.
  iter->stream.number = stream->number;
  iter->stream.block_count = stream->record_count;
  iter->stream.compressed_offset = stream->node.compressed_base;
  iter->stream.uncompressed_offset = stream->node.uncompressed_base;

  // iter->stream.flags will be NULL if the Stream Flags haven't been
  // set with lzma_index_stream_flags().
  iter->stream.flags = stream->stream_flags.version == UINT32_MAX
      ? NULL : &stream->stream_flags;
  iter->stream.padding = stream->stream_padding;

  if (stream->groups.rightmost == NULL) {
    // Stream has no Blocks.
    iter->stream.compressed_size = index_size(0, 0)
        + 2 * LZMA_STREAM_HEADER_SIZE;
    iter->stream.uncompressed_size = 0;
  } else {
    const index_group *g = (const index_group *)(
        stream->groups.rightmost);

    // Stream Header + Stream Footer + Index + Blocks
    iter->stream.compressed_size = 2 * LZMA_STREAM_HEADER_SIZE
        + index_size(stream->record_count,
          stream->index_list_size)
        + vli_ceil4(g->records[g->last].unpadded_sum);
    iter->stream.uncompressed_size
        = g->records[g->last].uncompressed_sum;
  }

  if (group != NULL) {
    iter->block.number_in_stream = group->number_base + record;
    iter->block.number_in_file = iter->block.number_in_stream
        + stream->block_number_base;

    iter->block.compressed_stream_offset
        = record == 0 ? group->node.compressed_base
        : vli_ceil4(group->records[
          record - 1].unpadded_sum);
    iter->block.uncompressed_stream_offset
        = record == 0 ? group->node.uncompressed_base
        : group->records[record - 1].uncompressed_sum;

    iter->block.uncompressed_size
        = group->records[record].uncompressed_sum
        - iter->block.uncompressed_stream_offset;
    iter->block.unpadded_size
        = group->records[record].unpadded_sum
        - iter->block.compressed_stream_offset;
    iter->block.total_size = vli_ceil4(iter->block.unpadded_size);

    iter->block.compressed_stream_offset
        += LZMA_STREAM_HEADER_SIZE;

    iter->block.compressed_file_offset
        = iter->block.compressed_stream_offset
        + iter->stream.compressed_offset;
    iter->block.uncompressed_file_offset
        = iter->block.uncompressed_stream_offset
        + iter->stream.uncompressed_offset;
  }

  return;
}


extern LZMA_API(void)
lzma_index_iter_init(lzma_index_iter *iter, const lzma_index *i)
{
  iter->internal[ITER_INDEX].p = i;
  lzma_index_iter_rewind(iter);
  return;
}


extern LZMA_API(void)
lzma_index_iter_rewind(lzma_index_iter *iter)
{
  iter->internal[ITER_STREAM].p = NULL;
  iter->internal[ITER_GROUP].p = NULL;
  iter->internal[ITER_RECORD].s = 0;
  iter->internal[ITER_METHOD].s = ITER_METHOD_NORMAL;
  return;
}


extern LZMA_API(lzma_bool)
lzma_index_iter_next(lzma_index_iter *iter, lzma_index_iter_mode mode)
{
  // Catch unsupported mode values.
  if ((unsigned int)(mode) > LZMA_INDEX_ITER_NONEMPTY_BLOCK)
    return true;

  const lzma_index *i = iter->internal[ITER_INDEX].p;
  const index_stream *stream = iter->internal[ITER_STREAM].p;
  const index_group *group = NULL;
  size_t record = iter->internal[ITER_RECORD].s;

  // If we are being asked for the next Stream, leave group to NULL
  // so that the rest of the this function thinks that this Stream
  // has no groups and will thus go to the next Stream.
  if (mode != LZMA_INDEX_ITER_STREAM) {
    // Get the pointer to the current group. See iter_set_inf()
    // for explanation.
    switch (iter->internal[ITER_METHOD].s) {
    case ITER_METHOD_NORMAL:
      group = iter->internal[ITER_GROUP].p;
      break;

    case ITER_METHOD_NEXT:
      group = index_tree_next(iter->internal[ITER_GROUP].p);
      break;

    case ITER_METHOD_LEFTMOST:
      group = (const index_group *)(
          stream->groups.leftmost);
      break;
    }
  }

again:
  if (stream == NULL) {
    // We at the beginning of the lzma_index.
    // Locate the first Stream.
    stream = (const index_stream *)(i->streams.leftmost);
    if (mode >= LZMA_INDEX_ITER_BLOCK) {
      // Since we are being asked to return information
      // about the first a Block, skip Streams that have
      // no Blocks.
      while (stream->groups.leftmost == NULL) {
        stream = index_tree_next(&stream->node);
        if (stream == NULL)
          return true;
      }
    }

    // Start from the first Record in the Stream.
    group = (const index_group *)(stream->groups.leftmost);
    record = 0;

  } else if (group != NULL && record < group->last) {
    // The next Record is in the same group.
    ++record;

  } else {
    // This group has no more Records or this Stream has
    // no Blocks at all.
    record = 0;

    // If group is not NULL, this Stream has at least one Block
    // and thus at least one group. Find the next group.
    if (group != NULL)
      group = index_tree_next(&group->node);

    if (group == NULL) {
      // This Stream has no more Records. Find the next
      // Stream. If we are being asked to return information
      // about a Block, we skip empty Streams.
      do {
        stream = index_tree_next(&stream->node);
        if (stream == NULL)
          return true;
      } while (mode >= LZMA_INDEX_ITER_BLOCK
          && stream->groups.leftmost == NULL);

      group = (const index_group *)(
          stream->groups.leftmost);
    }
  }

  if (mode == LZMA_INDEX_ITER_NONEMPTY_BLOCK) {
    // We need to look for the next Block again if this Block
    // is empty.
    if (record == 0) {
      if (group->node.uncompressed_base
          == group->records[0].uncompressed_sum)
        goto again;
    } else if (group->records[record - 1].uncompressed_sum
        == group->records[record].uncompressed_sum) {
      goto again;
    }
  }

  iter->internal[ITER_STREAM].p = stream;
  iter->internal[ITER_GROUP].p = group;
  iter->internal[ITER_RECORD].s = record;

  iter_set_info(iter);

  return false;
}


extern LZMA_API(lzma_bool)
lzma_index_iter_locate(lzma_index_iter *iter, lzma_vli target)
{
  const lzma_index *i = iter->internal[ITER_INDEX].p;

  // If the target is past the end of the file, return immediately.
  if (i->uncompressed_size <= target)
    return true;

  // Locate the Stream containing the target offset.
  const index_stream *stream = index_tree_locate(&i->streams, target);
  assert(stream != NULL);
  target -= stream->node.uncompressed_base;

  // Locate the group containing the target offset.
  const index_group *group = index_tree_locate(&stream->groups, target);
  assert(group != NULL);

  // Use binary search to locate the exact Record. It is the first
  // Record whose uncompressed_sum is greater than target.
  // This is because we want the rightmost Record that fulfills the
  // search criterion. It is possible that there are empty Blocks;
  // we don't want to return them.
  size_t left = 0;
  size_t right = group->last;

  while (left < right) {
    const size_t pos = left + (right - left) / 2;
    if (group->records[pos].uncompressed_sum <= target)
      left = pos + 1;
    else
      right = pos;
  }

  iter->internal[ITER_STREAM].p = stream;
  iter->internal[ITER_GROUP].p = group;
  iter->internal[ITER_RECORD].s = left;

  iter_set_info(iter);

  return false;
}

Coverage Report

Created: 2026-02-09 06:05