lzw.cpp.hpp

Go to the documentation of this file.

/*
 * This file is part of NetSurf's LibNSGIF, http://www.netsurf-browser.org/
 * Licensed under the MIT License,
 *                http://www.opensource.org/licenses/mit-license.php
 *
 * Copyright 2017 Michael Drake <michael.drake@codethink.co.uk>
 * Copyright 2021 Michael Drake <tlsa@netsurf-browser.org>
 */
 
#include "fl/stl/cstddef.h"
#include "fl/stl/assert.h"
#include "fl/stl/int.h"
#include "fl/stl/allocator.h"
#include "fl/stl/noexcept.h"
 
#include "lzw.h"
 
namespace fl {
namespace third_party {


#define LZW_TABLE_ENTRY_MAX (1u << LZW_CODE_MAX)

struct lzw_read_ctx {
    const fl::u8 * data; 
    fl::size data_len;              
    fl::size data_sb_next;          
 
    const fl::u8 *sb_data; 
    fl::size sb_bit;          
    fl::u32 sb_bit_count;  
};

struct lzw_table_entry {
    fl::u8  value;   
    fl::u8  first;   
    fl::u16 count;   
    fl::u16 extends; 
};

struct lzw_ctx {
    struct lzw_read_ctx input; 
 
    fl::u16 prev_code;       
    fl::u16 prev_code_first; 
    fl::u16 prev_code_count; 
 
    fl::u8  initial_code_size; 
 
    fl::u8  code_size; 
    fl::u16 code_max;  
 
    fl::u16 clear_code; 
    fl::u16 eoi_code;   
 
    fl::u16 table_size; 
 
    fl::u16 output_code; 
    fl::u16 output_left; 
 
    bool     has_transparency;     
    fl::u8  transparency_idx;     
    const fl::u32 * colour_map; 

    struct lzw_table_entry table[LZW_TABLE_ENTRY_MAX];

    fl::u8 stack_base[LZW_TABLE_ENTRY_MAX];
};
 
/* Exported function, documented in lzw.h */
lzw_result lzw_context_create(struct lzw_ctx **ctx) FL_NOEXCEPT
{
    struct lzw_ctx *c = static_cast<struct lzw_ctx*>(fl::Malloc(sizeof(*c)));
    if (c == nullptr) {
        return LZW_NO_MEM;
    }
 
    *ctx = c;
    return LZW_OK;
}
 
/* Exported function, documented in lzw.h */
void lzw_context_destroy(struct lzw_ctx *ctx) FL_NOEXCEPT
{
    fl::Free(ctx);
}

static lzw_result lzw__block_advance(struct lzw_read_ctx * ctx) FL_NOEXCEPT
{
    fl::size block_size;
    fl::size next_block_pos = ctx->data_sb_next;
    const fl::u8 *data_next = ctx->data + next_block_pos;
 
    if (next_block_pos >= ctx->data_len) {
        return LZW_NO_DATA;
    }
 
    block_size = *data_next;
 
    if ((next_block_pos + block_size) >= ctx->data_len) {
        return LZW_NO_DATA;
    }
 
    ctx->sb_bit = 0;
    ctx->sb_bit_count = block_size * 8;
 
    if (block_size == 0) {
        ctx->data_sb_next += 1;
        return LZW_OK_EOD;
    }
 
    ctx->sb_data = data_next + 1;
    ctx->data_sb_next += block_size + 1;
 
    return LZW_OK;
}

static inline lzw_result lzw__read_code(
        struct lzw_read_ctx * ctx,
        fl::u16 code_size,
        fl::u16 * code_out) FL_NOEXCEPT
{
    fl::u32 code = 0;
    fl::u32 current_bit = ctx->sb_bit & 0x7;
 
    if (ctx->sb_bit + 24 <= ctx->sb_bit_count) {
        /* Fast path: read three bytes from this sub-block */
        const fl::u8 *data = ctx->sb_data + (ctx->sb_bit >> 3);
        code |= static_cast<fl::u32>(*data++) <<  0;
        code |= static_cast<fl::u32>(*data++) <<  8;
        code |= static_cast<fl::u32>(*data)   << 16;
        ctx->sb_bit += code_size;
    } else {
        /* Slow path: code spans sub-blocks */
        fl::u8 byte_advance = (current_bit + code_size) >> 3;
        fl::u8 byte = 0;
        fl::u8 bits_remaining_0 = (code_size < (8u - current_bit)) ?
                code_size : (8u - current_bit);
        fl::u8 bits_remaining_1 = code_size - bits_remaining_0;
        fl::u8 bits_used[3] = {
            bits_remaining_0,
            (fl::u8)(bits_remaining_1 < 8 ? bits_remaining_1 : 8),
            (fl::u8)(bits_remaining_1 - 8),
        };
 
        FL_ASSERT(byte_advance <= 2, "Byte advance too large");
 
        while (true) {
            const fl::u8 *data = ctx->sb_data;
            lzw_result res;
 
            /* Get any data from end of this sub-block */
            while (byte <= byte_advance &&
                    ctx->sb_bit < ctx->sb_bit_count) {
                code |= data[ctx->sb_bit >> 3] << (byte << 3);
                ctx->sb_bit += bits_used[byte];
                byte++;
            }
 
            /* Check if we have all we need */
            if (byte > byte_advance) {
                break;
            }
 
            /* Move to next sub-block */
            res = lzw__block_advance(ctx);
            if (res != LZW_OK) {
                return res;
            }
        }
    }
 
    *code_out = (code >> current_bit) & ((1 << code_size) - 1);
    return LZW_OK;
}

static inline lzw_result lzw__handle_clear(
        struct lzw_ctx *ctx,
        fl::u16 *code_out) FL_NOEXCEPT
{
    fl::u16 code = 0;
 
    /* Reset table building context */
    ctx->code_size = ctx->initial_code_size;
    ctx->code_max = (1 << ctx->initial_code_size) - 1;
    ctx->table_size = ctx->eoi_code + 1;
 
    /* There might be a sequence of clear codes, so process them all */
    do {
        lzw_result res = lzw__read_code(&ctx->input,
                ctx->code_size, &code);
        if (res != LZW_OK) {
            return res;
        }
    } while (code == ctx->clear_code);
 
    /* The initial code must be from the initial table. */
    if (code > ctx->clear_code) {
        return LZW_BAD_ICODE;
    }
 
    *code_out = code;
    return LZW_OK;
}
 
/* Exported function, documented in lzw.h */
lzw_result lzw_decode_init(
        struct lzw_ctx *ctx,
        fl::u8 minimum_code_size,
        const fl::u8 *input_data,
        fl::size input_length,
        fl::size input_pos) FL_NOEXCEPT
{
    struct lzw_table_entry *table = ctx->table;
    lzw_result res;
    fl::u16 code;
 
    if (minimum_code_size >= LZW_CODE_MAX) {
        return LZW_BAD_ICODE;
    }
 
    /* Initialise the input reading context */
    ctx->input.data = input_data;
    ctx->input.data_len = input_length;
    ctx->input.data_sb_next = input_pos;
 
    ctx->input.sb_bit = 0;
    ctx->input.sb_bit_count = 0;
 
    /* Initialise the table building context */
    ctx->initial_code_size = minimum_code_size + 1;
 
    ctx->clear_code = (1 << minimum_code_size) + 0;
    ctx->eoi_code   = (1 << minimum_code_size) + 1;
 
    ctx->output_left = 0;
 
    /* Initialise the standard table entries */
    for (fl::u16 i = 0; i < ctx->clear_code; i++) {
        table[i].first = i;
        table[i].value = i;
        table[i].count = 1;
    }
 
    res = lzw__handle_clear(ctx, &code);
    if (res != LZW_OK) {
        return res;
    }
 
    /* Store details of this code as "previous code" to the context. */
    ctx->prev_code_first = ctx->table[code].first;
    ctx->prev_code_count = ctx->table[code].count;
    ctx->prev_code = code;
 
    /* Add code to context for immediate output. */
    ctx->output_code = code;
    ctx->output_left = 1;
 
    ctx->has_transparency = false;
    ctx->transparency_idx = 0;
    ctx->colour_map = nullptr;
 
    return LZW_OK;
}
 
/* Exported function, documented in lzw.h */
lzw_result lzw_decode_init_map(
        struct lzw_ctx *ctx,
        fl::u8 minimum_code_size,
        fl::u32 transparency_idx,
        const fl::u32 *colour_table,
        const fl::u8 *input_data,
        fl::size input_length,
        fl::size input_pos) FL_NOEXCEPT
{
    lzw_result res;
 
    if (colour_table == nullptr) {
        return LZW_BAD_PARAM;
    }
 
    res = lzw_decode_init(ctx, minimum_code_size,
            input_data, input_length, input_pos);
    if (res != LZW_OK) {
        return res;
    }
 
    ctx->has_transparency = (transparency_idx <= 0xFF);
    ctx->transparency_idx = transparency_idx;
    ctx->colour_map = colour_table;
 
    return LZW_OK;
}

static inline void lzw__table_add_entry(
        struct lzw_ctx *ctx,
        fl::u16 code) FL_NOEXCEPT
{
    struct lzw_table_entry *entry = &ctx->table[ctx->table_size];
 
    entry->value = code;
    entry->first = ctx->prev_code_first;
    entry->count = ctx->prev_code_count + 1;
    entry->extends = ctx->prev_code;
 
    ctx->table_size++;
}
 
typedef fl::u32 (*lzw_writer_fn)(
        struct lzw_ctx *ctx,
        void * output_data,
        fl::u32 output_length,
        fl::u32 output_pos,
        fl::u16 code,
        fl::u16 left);

static inline lzw_result lzw__decode(
        struct lzw_ctx    *ctx,
        lzw_writer_fn      write_fn,
        void     * output_data,
        fl::u32          output_length,
        fl::u32 * output_written) FL_NOEXCEPT
{
    lzw_result res;
    fl::u16 code = 0;
 
    /* Get a new code from the input */
    res = lzw__read_code(&ctx->input, ctx->code_size, &code);
    if (res != LZW_OK) {
        return res;
    }
 
    /* Handle the new code */
    if (code == ctx->eoi_code) {
        /* Got End of Information code */
        return LZW_EOI_CODE;
 
    } else if (code > ctx->table_size) {
        /* Code is invalid */
        return LZW_BAD_CODE;
 
    } else if (code == ctx->clear_code) {
        res = lzw__handle_clear(ctx, &code);
        if (res != LZW_OK) {
            return res;
        }
 
    } else if (ctx->table_size < LZW_TABLE_ENTRY_MAX) {
        fl::u16 size = ctx->table_size;
        lzw__table_add_entry(ctx, (code < size) ?
                ctx->table[code].first :
                ctx->prev_code_first);
 
        /* Ensure code size is increased, if needed. */
        if (size == ctx->code_max && ctx->code_size < LZW_CODE_MAX) {
            ctx->code_size++;
            ctx->code_max = (1 << ctx->code_size) - 1;
        }
    }
 
    *output_written += write_fn(ctx,
            output_data, output_length, *output_written,
            code, ctx->table[code].count);
 
    /* Store details of this code as "previous code" to the context. */
    ctx->prev_code_first = ctx->table[code].first;
    ctx->prev_code_count = ctx->table[code].count;
    ctx->prev_code = code;
 
    return LZW_OK;
}

static inline fl::u32 lzw__write_fn(struct lzw_ctx *ctx,
        void * output_data,
        fl::u32 output_length,
        fl::u32 output_used,
        fl::u16 code,
        fl::u16 left) FL_NOEXCEPT
{
    fl::u8 * output_pos = (fl::u8 *)output_data + output_used;
    const struct lzw_table_entry * const table = ctx->table;
    fl::u32 space = output_length - output_used;
    fl::u16 count = left;
 
    if (count > space) {
        left = count - space;
        count = space;
    } else {
        left = 0;
    }
 
    ctx->output_code = code;
    ctx->output_left = left;
 
    /* Skip over any values we don't have space for. */
    for (unsigned i = left; i != 0; i--) {
        const struct lzw_table_entry *entry = table + code;
        code = entry->extends;
    }
 
    output_pos += count;
    for (unsigned i = count; i != 0; i--) {
        const struct lzw_table_entry *entry = table + code;
        *--output_pos = entry->value;
        code = entry->extends;
    }
 
    return count;
}
 
/* Exported function, documented in lzw.h */
lzw_result lzw_decode(struct lzw_ctx *ctx,
        const fl::u8 * *const output_data,
        fl::u32 * output_written) FL_NOEXCEPT
{
    const fl::u32 output_length = sizeof(ctx->stack_base);
 
    *output_written = 0;
    *output_data = ctx->stack_base;
 
    if (ctx->output_left != 0) {
        *output_written += lzw__write_fn(ctx,
                ctx->stack_base, output_length, *output_written,
                ctx->output_code, ctx->output_left);
    }
 
    while (*output_written != output_length) {
        lzw_result res = lzw__decode(ctx, lzw__write_fn,
                ctx->stack_base, output_length, output_written);
        if (res != LZW_OK) {
            return res;
        }
    }
 
    return LZW_OK;
}

static inline fl::u32 lzw__map_write_fn(struct lzw_ctx *ctx,
        void * output_data,
        fl::u32 output_length,
        fl::u32 output_used,
        fl::u16 code,
        fl::u16 left) FL_NOEXCEPT
{
    fl::u32 * output_pos = (fl::u32 *)output_data + output_used;
    const struct lzw_table_entry * const table = ctx->table;
    fl::u32 space = output_length - output_used;
    fl::u16 count = left;
 
    if (count > space) {
        left = count - space;
        count = space;
    } else {
        left = 0;
    }
 
    ctx->output_code = code;
    ctx->output_left = left;
 
    for (unsigned i = left; i != 0; i--) {
        const struct lzw_table_entry *entry = table + code;
        code = entry->extends;
    }
 
    output_pos += count;
    if (ctx->has_transparency) {
        for (unsigned i = count; i != 0; i--) {
            const struct lzw_table_entry *entry = table + code;
            --output_pos;
            if (entry->value != ctx->transparency_idx) {
                *output_pos = ctx->colour_map[entry->value];
            }
            code = entry->extends;
        }
    } else {
        for (unsigned i = count; i != 0; i--) {
            const struct lzw_table_entry *entry = table + code;
            *--output_pos = ctx->colour_map[entry->value];
            code = entry->extends;
        }
    }
 
    return count;
}
 
/* Exported function, documented in lzw.h */
lzw_result lzw_decode_map(struct lzw_ctx *ctx,
        fl::u32 * output_data,
        fl::u32 output_length,
        fl::u32 * output_written) FL_NOEXCEPT
{
    *output_written = 0;
 
    if (ctx->colour_map == nullptr) {
        return LZW_NO_COLOUR;
    }
 
    if (ctx->output_left != 0) {
        *output_written += lzw__map_write_fn(ctx,
                output_data, output_length, *output_written,
                ctx->output_code, ctx->output_left);
    }
 
    while (*output_written != output_length) {
        lzw_result res = lzw__decode(ctx, lzw__map_write_fn,
                output_data, output_length, output_written);
        if (res != LZW_OK) {
            return res;
        }
    }
 
    return LZW_OK;
}
 
} // namespace third_party
} // namespace fl