index.c File Reference

Handling of .xz Indexes and some other Stream information. More...

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

Go to the source code of this file.

Classes
struct	index_tree_node_s
struct	index_tree
	AVL tree to hold index_stream or index_group structures. More...
struct	index_record
struct	index_group
struct	index_stream
struct	lzma_index_s
struct	index_cat_info
	Structure to pass info to index_cat_helper() More...

Macros
#define	INDEX_GROUP_SIZE   512
	How many Records to allocate at once. More...
#define	PREALLOC_MAX   ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))
	How many Records can be allocated at once at maximum. More...

Typedefs
typedef struct index_tree_node_s	index_tree_node
	Base structure for index_stream and index_group structures. More...

Enumerations
enum	{   ITER_INDEX , ITER_STREAM , ITER_GROUP , ITER_RECORD ,   ITER_METHOD }
	Indexing for lzma_index_iter.internal[]. More...
enum	{ ITER_METHOD_NORMAL , ITER_METHOD_NEXT , ITER_METHOD_LEFTMOST }
	Values for lzma_index_iter.internal[ITER_METHOD].s. More...

Functions
static void	index_tree_init (index_tree *tree)
static void	index_tree_node_end (index_tree_node *node, const lzma_allocator *allocator, void(*free_func)(void *node, const lzma_allocator *allocator))
	Helper for index_tree_end() More...
static void	index_tree_end (index_tree *tree, const lzma_allocator *allocator, void(*free_func)(void *node, const lzma_allocator *allocator))
static void	index_tree_append (index_tree *tree, index_tree_node *node)
static void *	index_tree_next (const index_tree_node *node)
	Get the next node in the tree. Return NULL if there are no more nodes. More...
static void *	index_tree_locate (const index_tree *tree, lzma_vli target)
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)
	Allocate and initialize a new Stream using the given base offsets. More...
static void	index_stream_end (void *node, const lzma_allocator *allocator)
	Free the memory allocated for a Stream and its Record groups. More...
static lzma_index *	index_init_plain (const lzma_allocator *allocator)
	LZMA_API (lzma_index *)
	LZMA_API (void)
void	lzma_index_prealloc (lzma_index *i, lzma_vli records)
	LZMA_API (uint64_t)
	Calculate approximate memory usage of easy encoder. More...
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)
	LZMA_API (uint32_t)
uint32_t	lzma_index_padding_size (const lzma_index *i)
	LZMA_API (lzma_ret)
static void	index_cat_helper (const index_cat_info *info, index_stream *this)
static index_stream *	index_dup_stream (const index_stream *src, const lzma_allocator *allocator)
	Duplicate an index_stream. More...
static void	iter_set_info (lzma_index_iter *iter)
	LZMA_API (lzma_bool)

Detailed Description

Handling of .xz Indexes and some other Stream information.

Definition in file index.c.

Macro Definition Documentation

INDEX_GROUP_SIZE

#define INDEX_GROUP_SIZE   512

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.

Definition at line 21 of file index.c.

PREALLOC_MAX

#define PREALLOC_MAX   ((SIZE_MAX - sizeof(index_group)) / sizeof(index_record))

How many Records can be allocated at once at maximum.

Definition at line 25 of file index.c.

Typedef Documentation

index_tree_node

typedef struct index_tree_node_s index_tree_node

Base structure for index_stream and index_group structures.

Definition at line 1 of file index.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Indexing for lzma_index_iter.internal[].

Enumerator
ITER_INDEX
ITER_STREAM
ITER_GROUP
ITER_RECORD
ITER_METHOD

Definition at line 960 of file index.c.

     {
    ITER_INDEX,
    ITER_STREAM,
    ITER_GROUP,
    ITER_RECORD,
    ITER_METHOD,
};

anonymous enum

anonymous enum

Values for lzma_index_iter.internal[ITER_METHOD].s.

Enumerator
ITER_METHOD_NORMAL
ITER_METHOD_NEXT
ITER_METHOD_LEFTMOST

Definition at line 970 of file index.c.

     {
    ITER_METHOD_NORMAL,
    ITER_METHOD_NEXT,
    ITER_METHOD_LEFTMOST,
};

Function Documentation

index_cat_helper()

static void index_cat_helper ( const index_cat_info *  info, index_stream *  this  )

static

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.

Definition at line 745 of file index.c.

{
    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;
}

References index_tree_node_s::compressed_base, index_tree_append(), info(), index_tree_node_s::left, NULL, index_tree_node_s::right, and index_tree_node_s::uncompressed_base.

index_dup_stream()

static index_stream* index_dup_stream ( const index_stream *  src, const lzma_allocator *  allocator  )

static

Duplicate an index_stream.

Definition at line 865 of file index.c.

{
    // 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;
}

References index_group::allocated, allocator, assert(), index_tree_node_s::compressed_base, dest, i, lzma_index_s::index_list_size, index_stream_end(), index_stream_init(), index_tree_append(), index_tree_next(), index_group::last, lzma_alloc(), memcpy(), index_group::node, NULL, index_group::number_base, PREALLOC_MAX, lzma_index_s::record_count, index_group::records, src, and index_tree_node_s::uncompressed_base.

Referenced by LZMA_API().

index_file_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  )

static

Definition at line 536 of file index.c.

{
    // 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;
}

References index_size(), LZMA_STREAM_HEADER_SIZE, LZMA_VLI_MAX, LZMA_VLI_UNKNOWN, stream_padding, and vli_ceil4().

index_init_plain()

static lzma_index* index_init_plain ( const lzma_allocator *  allocator )

static

Definition at line 380 of file index.c.

{
    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;
}

References allocator, lzma_index_s::checks, i, INDEX_GROUP_SIZE, lzma_index_s::index_list_size, index_tree_init(), lzma_alloc(), NULL, lzma_index_s::prealloc, lzma_index_s::record_count, lzma_index_s::streams, lzma_index_s::total_size, and lzma_index_s::uncompressed_size.

Referenced by LZMA_API().

index_stream_end()

static void index_stream_end ( void *  node, const lzma_allocator *  allocator  )

static

Free the memory allocated for a Stream and its Record groups.

Definition at line 370 of file index.c.

{
    index_stream *s = node;
    index_tree_end(&s->groups, allocator, &lzma_free);
    lzma_free(s, allocator);
    return;
}

References allocator, index_tree_end(), lzma_free(), and s.

Referenced by index_dup_stream(), and LZMA_API().

index_stream_init()

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  )

static

Allocate and initialize a new Stream using the given base offsets.

Definition at line 340 of file index.c.

{
    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;
}

References allocator, index_tree_init(), lzma_alloc(), NULL, s, and UINT32_MAX.

Referenced by index_dup_stream(), and LZMA_API().

index_tree_append()

static void index_tree_append ( index_tree *  tree, index_tree_node *  node  )

static

Add a new node to the tree. node->uncompressed_base and node->compressed_base must have been set by the caller already.

Definition at line 230 of file index.c.

{
    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;
        } 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;
}

References assert(), bsr32(), index_tree_node_s::compressed_base, index_tree::count, ctz32(), index_tree_node_s::left, index_tree::leftmost, NULL, index_tree_node_s::parent, index_tree_node_s::right, index_tree::rightmost, index_tree::root, UINT32_C, and index_tree_node_s::uncompressed_base.

Referenced by index_cat_helper(), index_dup_stream(), and LZMA_API().

index_tree_end()

static void index_tree_end ( index_tree *  tree, const lzma_allocator *  allocator, void(*)(void *node, const lzma_allocator *allocator)  free_func  )

static

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.

Definition at line 215 of file index.c.

{
    assert(free_func != NULL);
 
    if (tree->root != NULL)
        index_tree_node_end(tree->root, allocator, free_func);
 
    return;
}

References allocator, assert(), index_tree_node_end(), NULL, and index_tree::root.

Referenced by index_stream_end(), and LZMA_API().

index_tree_init()

static void index_tree_init ( index_tree *  tree )

static

Definition at line 182 of file index.c.

{
    tree->root = NULL;
    tree->leftmost = NULL;
    tree->rightmost = NULL;
    tree->count = 0;
    return;
}

References index_tree::count, index_tree::leftmost, NULL, index_tree::rightmost, and index_tree::root.

Referenced by index_init_plain(), and index_stream_init().

index_tree_locate()

static void* index_tree_locate ( const index_tree *  tree, lzma_vli  target  )

static

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).

Definition at line 315 of file index.c.

{
    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);
}

References assert(), index_tree_node_s::left, index_tree::leftmost, NULL, index_tree_node_s::right, index_tree::root, and index_tree_node_s::uncompressed_base.

Referenced by LZMA_API().

index_tree_next()

static void* index_tree_next ( const index_tree_node *  node )

static

Get the next node in the tree. Return NULL if there are no more nodes.

Definition at line 294 of file index.c.

{
    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);
}

References index_tree_node_s::left, NULL, index_tree_node_s::parent, and index_tree_node_s::right.

Referenced by index_dup_stream(), and LZMA_API().

index_tree_node_end()

static void index_tree_node_end ( index_tree_node *  node, const lzma_allocator *  allocator, void(*)(void *node, const lzma_allocator *allocator)  free_func  )

static

Helper for index_tree_end()

Definition at line 194 of file index.c.

{
    // 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;
}

References allocator, and NULL.

Referenced by index_tree_end().

iter_set_info()

static void iter_set_info ( lzma_index_iter *  iter )

static

Definition at line 978 of file index.c.

{
    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;
}

References assert(), index_tree_node_s::compressed_base, g, i, index_size(), ITER_GROUP, ITER_INDEX, ITER_METHOD, ITER_METHOD_LEFTMOST, ITER_METHOD_NEXT, ITER_METHOD_NORMAL, ITER_RECORD, ITER_STREAM, LZMA_STREAM_HEADER_SIZE, index_group::node, NULL, index_group::number_base, index_tree_node_s::parent, index_group::records, index_tree_node_s::right, index_tree::rightmost, lzma_index_s::streams, UINT32_MAX, index_tree_node_s::uncompressed_base, index_record::uncompressed_sum, index_record::unpadded_sum, and vli_ceil4().

Referenced by LZMA_API().

LZMA_API() [1/6]

LZMA_API

(

lzma_bool

)

Definition at line 1102 of file index.c.

{
    // 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;
}

References i, index_tree_next(), ITER_GROUP, ITER_INDEX, ITER_METHOD, ITER_METHOD_LEFTMOST, ITER_METHOD_NEXT, ITER_METHOD_NORMAL, ITER_RECORD, iter_set_info(), ITER_STREAM, index_tree::leftmost, LZMA_INDEX_ITER_BLOCK, LZMA_INDEX_ITER_NONEMPTY_BLOCK, LZMA_INDEX_ITER_STREAM, index_group::node, NULL, index_group::records, lzma_index_s::streams, index_tree_node_s::uncompressed_base, and index_record::uncompressed_sum.

LZMA_API() [2/6]

LZMA_API

(

lzma_index *

)

Definition at line 397 of file index.c.

{
    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;
}

References allocator, i, index_init_plain(), index_stream_init(), index_tree_append(), lzma_free(), NULL, s, and lzma_index_s::streams.

LZMA_API() [3/6]

LZMA_API

(

lzma_ret

)

Definition at line 600 of file index.c.

{
    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;
}

References i, LZMA_OK, LZMA_PROG_ERROR, NULL, return_if_error, index_tree::rightmost, s, and lzma_index_s::streams.

LZMA_API() [4/6]

LZMA_API

(

uint32_t

)

Definition at line 578 of file index.c.

{
    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;
}

References lzma_index_s::checks, checks, i, index_tree::rightmost, s, lzma_index_s::streams, UINT32_C, and UINT32_MAX.

LZMA_API() [5/6]

LZMA_API

(

uint64_t

)

Calculate approximate memory usage of easy encoder.

Get the total amount of physical memory (RAM) in bytes.

Calculate approximate memory usage of multithreaded .xz encoder.

Calculate approximate decoder memory usage of a preset.

This function is a wrapper for lzma_raw_encoder_memusage().

Parameters

preset

Compression preset (level and possible flags)

Returns

Number of bytes of memory required for the given preset when encoding. If an error occurs, for example due to unsupported preset, UINT64_MAX is returned.

This function is a wrapper for lzma_raw_decoder_memusage().

Parameters

preset

Compression preset (level and possible flags)

Returns

Number of bytes of memory required to decompress a file that was compressed using the given preset. If an error occurs, for example due to unsupported preset, UINT64_MAX is returned.

Since doing the encoding in threaded mode doesn't affect the memory requirements of single-threaded decompressor, you can use lzma_easy_decoder_memusage(options->preset) or lzma_raw_decoder_memusage(options->filters) to calculate the decompressor memory requirements.

Parameters

options

Compression options

Returns

Number of bytes of memory required for encoding with the given options. If an error occurs, for example due to unsupported preset or filter chain, UINT64_MAX is returned.

Calculate approximate memory usage of easy encoder.

Get the uncompressed size of the file.

Get the total size of the file.

Get the total size of the Blocks.

Get the total size of the Stream.

Get the size of the Index field as bytes.

Get the number of Blocks.

Get the number of Streams.

Calculate the memory usage of an existing lzma_index.

On disk, the size of the Index field depends on both the number of Records stored and how big values the Records store (due to variable-length integer encoding). When the Index is kept in lzma_index structure, the memory usage depends only on the number of Records/Blocks stored in the Index(es), and in case of concatenated lzma_indexes, the number of Streams. The size in RAM is almost always significantly bigger than in the encoded form on disk.

This function calculates an approximate amount of memory needed hold the given number of Streams and Blocks in lzma_index structure. This value may vary between CPU architectures and also between liblzma versions if the internal implementation is modified.

This is a shorthand for lzma_index_memusage(lzma_index_stream_count(i), lzma_index_block_count(i)).

This returns the total number of Blocks in lzma_index. To get number of Blocks in individual Streams, use lzma_index_iter.

This is needed to verify the Backward Size field in the Stream Footer.

If multiple lzma_indexes have been combined, this works as if the Blocks were in a single Stream. This is useful if you are going to combine Blocks from multiple Streams into a single new Stream.

This doesn't include the Stream Header, Stream Footer, Stream Padding, or Index fields.

When no lzma_indexes have been combined with lzma_index_cat() and there is no Stream Padding, this function is identical to lzma_index_stream_size(). If multiple lzma_indexes have been combined, this includes also the headers of each separate Stream and the possible Stream Padding fields.

Definition at line 441 of file index.c.

{
    // 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;
}

References blocks, make_dist_html::groups, INDEX_GROUP_SIZE, limit, LZMA_VLI_MAX, streams, UINT32_MAX, and UINT64_MAX.

LZMA_API() [6/6]

LZMA_API

(

void

)

Definition at line 416 of file index.c.

{
    // 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;
}

References allocator, i, index_stream_end(), index_tree_end(), lzma_free(), NULL, and lzma_index_s::streams.

lzma_index_padding_size()

uint32_t lzma_index_padding_size

(

const lzma_index *

i

)

Get the size of the Index Padding field. This is needed by Index encoder and decoder, but applications should have no use for this.

Definition at line 593 of file index.c.

{
    return (LZMA_VLI_C(4) - index_size_unpadded(
            i->record_count, i->index_list_size)) & 3;
}

References i, lzma_index_s::index_list_size, index_size_unpadded(), LZMA_VLI_C, and lzma_index_s::record_count.

Referenced by index_decode(), and index_encode().

lzma_index_prealloc()

void lzma_index_prealloc	(	lzma_index *	i,
		lzma_vli	records
	)

Set for how many Records to allocate memory the next time lzma_index_append() needs to allocate space for a new Record. This is used only by the Index decoder.

Definition at line 431 of file index.c.

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

References i, lzma_index_s::prealloc, and PREALLOC_MAX.

Referenced by index_decode().