/* Copyright (C) 2001-2023 Artifex Software, Inc.

   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or

   implied.

   This software is distributed under license and may not be copied,

   modified or distributed except as expressly authorized under the terms

   of the license contained in the file LICENSE in this distribution.

   Refer to licensing information at http://www.artifex.com or contact

   Artifex Software, Inc.,  39 Mesa Street, Suite 108A, San Francisco,

   CA 94129, USA, for further information.

*/

/*

    jbig2dec

*/

/* Huffman table decoding procedures

    -- See Annex B of the JBIG2 specification */

#ifdef HAVE_CONFIG_H

#include "config.h"

#endif

#include "os_types.h"

#include <stdlib.h>

#include <string.h>

#ifdef JBIG2_DEBUG

#include <stdio.h>

#endif

#include "jbig2.h"

#include "jbig2_priv.h"

#include "jbig2_huffman.h"

#include "jbig2_hufftab.h"

#include "jbig2_image.h"

#include "jbig2_segment.h"

#define JBIG2_HUFFMAN_FLAGS_ISOOB 1

#define JBIG2_HUFFMAN_FLAGS_ISLOW 2

#define JBIG2_HUFFMAN_FLAGS_ISEXT 4

struct _Jbig2HuffmanState {

    /* The current bit offset is equal to (offset * 8) + offset_bits.

       The MSB of this_word is the current bit offset. The MSB of next_word

       is (offset + 4) * 8. */

    uint32_t this_word;

    uint32_t next_word;

    uint32_t offset_bits;

    uint32_t offset;

    uint32_t offset_limit;

    Jbig2WordStream *ws;

    Jbig2Ctx *ctx;

};

#define huff_get_next_word(hs, offset, word) \

    (hs)->ws->get_next_word((hs)->ctx, (hs)->ws, (offset), (word))

/** Allocate and initialize a new huffman coding state

 *  the returned pointer can simply be freed; this does

 *  not affect the associated Jbig2WordStream.

 */

Jbig2HuffmanState *

jbig2_huffman_new(Jbig2Ctx *ctx, Jbig2WordStream *ws)

{

    Jbig2HuffmanState *result = NULL;

    int code;

    result = jbig2_new(ctx, Jbig2HuffmanState, 1);

    if (result != NULL) {

        result->offset = 0;

        result->offset_bits = 0;

        result->offset_limit = 0;

        result->ws = ws;

        result->ctx = ctx;

        code = huff_get_next_word(result, 0, &result->this_word);

        if (code < 0) {

            jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read first huffman word");

            jbig2_huffman_free(ctx, result);

            return NULL;

        }

        code = huff_get_next_word(result, 4, &result->next_word);

        if (code < 0) {

            jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read second huffman word");

            jbig2_huffman_free(ctx, result);

            return NULL;

        }

    } else {

        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate new huffman coding state");

        return NULL;

    }

    return result;

}

/** Free an allocated huffman coding state.

 *  This just calls jbig2_free() if the pointer is not NULL

 */

void

jbig2_huffman_free(Jbig2Ctx *ctx, Jbig2HuffmanState *hs)

{

    jbig2_free(ctx->allocator, hs);

}

/** debug routines **/

#ifdef JBIG2_DEBUG

/** print current huffman state */

void

jbig2_dump_huffman_state(Jbig2HuffmanState *hs)

{

    fprintf(stderr, "huffman state %08x %08x offset %d.%d\n", hs->this_word, hs->next_word, hs->offset, hs->offset_bits);

}

/** print the binary string we're reading from */

void

jbig2_dump_huffman_binary(Jbig2HuffmanState *hs)

{

    const uint32_t word = hs->this_word;

    int i;

    fprintf(stderr, "huffman binary ");

    for (i = 31; i >= 0; i--)

        fprintf(stderr, ((word >> i) & 1) ? "1" : "0");

    fprintf(stderr, "\n");

}

/** print huffman table */

void

jbig2_dump_huffman_table(const Jbig2HuffmanTable *table)

{

    int i;

    int table_size = (1 << table->log_table_size);

    fprintf(stderr, "huffman table %p (log_table_size=%d, %d entries, entries=%p):\n", table, table->log_table_size, table_size, table->entries);

    for (i = 0; i < table_size; i++) {

        fprintf(stderr, "%6d: PREFLEN=%d, RANGELEN=%d, ", i, table->entries[i].PREFLEN, table->entries[i].RANGELEN);

        if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISEXT) {

            fprintf(stderr, "ext=%p", table->entries[i].u.ext_table);

        } else {

            fprintf(stderr, "RANGELOW=%d", table->entries[i].u.RANGELOW);

        }

        if (table->entries[i].flags) {

            int need_comma = 0;

            fprintf(stderr, ", flags=0x%x(", table->entries[i].flags);

            if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISOOB) {

                fprintf(stderr, "OOB");

                need_comma = 1;

            }

            if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISLOW) {

                if (need_comma)

                    fprintf(stderr, ",");

                fprintf(stderr, "LOW");

                need_comma = 1;

            }

            if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISEXT) {

                if (need_comma)

                    fprintf(stderr, ",");

                fprintf(stderr, "EXT");

            }

            fprintf(stderr, ")");

        }

        fprintf(stderr, "\n");

    }

    fprintf(stderr, "\n");

}

#endif /* JBIG2_DEBUG */

/** Skip bits up to the next byte boundary

 */

int

jbig2_huffman_skip(Jbig2HuffmanState *hs)

{

    uint32_t bits = hs->offset_bits & 7;

    int code;

    if (bits) {

        bits = 8 - bits;

        hs->offset_bits += bits;

        hs->this_word = (hs->this_word << bits) | (hs->next_word >> (32 - hs->offset_bits));

    }

    if (hs->offset_bits >= 32) {

        hs->this_word = hs->next_word;

        hs->offset += 4;

        code = huff_get_next_word(hs, hs->offset + 4, &hs->next_word);

        if (code < 0) {

            return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read next huffman word when skipping");

        }

        hs->offset_bits -= 32;

        if (hs->offset_bits) {

            hs->this_word = (hs->this_word << hs->offset_bits) | (hs->next_word >> (32 - hs->offset_bits));

        }

    }

    return 0;

}

/* skip ahead a specified number of bytes in the word stream

 */

int

jbig2_huffman_advance(Jbig2HuffmanState *hs, size_t advance)

{

    int code;

    hs->offset += advance & ~3;

    hs->offset_bits += (advance & 3) << 3;

    if (hs->offset_bits >= 32) {

        hs->offset += 4;

        hs->offset_bits -= 32;

    }

    code = huff_get_next_word(hs, hs->offset, &hs->this_word);

    if (code < 0) {

        return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get first huffman word after advancing");

    }

    code = huff_get_next_word(hs, hs->offset + 4, &hs->next_word);

    if (code < 0) {

        return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get second huffman word after advancing");

    }

    if (hs->offset_bits > 0)

        hs->this_word = (hs->this_word << hs->offset_bits) | (hs->next_word >> (32 - hs->offset_bits));

    return 0;

}

/* return the offset of the huffman decode pointer (in bytes)

 * from the beginning of the WordStream

 */

uint32_t

jbig2_huffman_offset(Jbig2HuffmanState *hs)

{

    return hs->offset + (hs->offset_bits >> 3);

}

/* read a number of bits directly from the huffman state

 * without decoding against a table

 */

int32_t

jbig2_huffman_get_bits(Jbig2HuffmanState *hs, const int bits, int *err)

{

    uint32_t this_word = hs->this_word;

    int32_t result;

    int code;

    if (hs->offset_limit && hs->offset >= hs->offset_limit) {

        *err = -1;

        return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "end of jbig2 buffer reached at offset %d", hs->offset);

    }

    result = this_word >> (32 - bits);

    hs->offset_bits += bits;

    if (hs->offset_bits >= 32) {

        hs->offset += 4;

        hs->offset_bits -= 32;

        hs->this_word = hs->next_word;

        code = huff_get_next_word(hs, hs->offset + 4, &hs->next_word);

        if (code < 0) {

            return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get next huffman word");

        }

        if (hs->offset_bits) {

            hs->this_word = (hs->this_word << hs->offset_bits) | (hs->next_word >> (32 - hs->offset_bits));

        } else {

            hs->this_word = (hs->this_word << hs->offset_bits);

        }

    } else {

        hs->this_word = (this_word << bits) | (hs->next_word >> (32 - hs->offset_bits));

    }

    return result;

}

int32_t

jbig2_huffman_get(Jbig2HuffmanState *hs, const Jbig2HuffmanTable *table, bool *oob)

{

    Jbig2HuffmanEntry *entry;

    byte flags;

    int offset_bits = hs->offset_bits;

    uint32_t this_word = hs->this_word;

    uint32_t next_word;

    int RANGELEN;

    int32_t result;

    if (hs->offset_limit && hs->offset >= hs->offset_limit) {

        if (oob)

            *oob = -1;

        return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "end of Jbig2WordStream reached at offset %d", hs->offset);

    }

    for (;;) {

        int log_table_size = table->log_table_size;

        int PREFLEN;

        int code;

        /* SumatraPDF: shifting by the size of the operand is undefined */

        entry = &table->entries[log_table_size > 0 ? this_word >> (32 - log_table_size) : 0];

        flags = entry->flags;

        PREFLEN = entry->PREFLEN;

        if (flags == (byte) -1 || PREFLEN == (byte) -1) {

            if (oob)

                *oob = -1;

            return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "encountered unpopulated huffman table entry");

        }

        next_word = hs->next_word;

        offset_bits += PREFLEN;

        if (offset_bits >= 32) {

            this_word = next_word;

            hs->offset += 4;

            code = huff_get_next_word(hs, hs->offset + 4, &next_word);

            if (code < 0) {

                return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get next huffman word");

            }

            offset_bits -= 32;

            hs->next_word = next_word;

            PREFLEN = offset_bits;

        }

        if (PREFLEN)

            this_word = (this_word << PREFLEN) | (next_word >> (32 - offset_bits));

        if (flags & JBIG2_HUFFMAN_FLAGS_ISEXT) {

            table = entry->u.ext_table;

        } else

            break;

    }

    result = entry->u.RANGELOW;

    RANGELEN = entry->RANGELEN;

    if (RANGELEN > 0) {

        int32_t HTOFFSET;

        int code;

        HTOFFSET = this_word >> (32 - RANGELEN);

        if (flags & JBIG2_HUFFMAN_FLAGS_ISLOW)

            result -= HTOFFSET;

        else

            result += HTOFFSET;

        offset_bits += RANGELEN;

        if (offset_bits >= 32) {

            this_word = next_word;

            hs->offset += 4;

            code = huff_get_next_word(hs, hs->offset + 4, &next_word);

            if (code < 0) {

                return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get next huffman word");

            }

            offset_bits -= 32;

            hs->next_word = next_word;

            RANGELEN = offset_bits;

        }

        if (RANGELEN)

            this_word = (this_word << RANGELEN) | (next_word >> (32 - offset_bits));

    }

    hs->this_word = this_word;

    hs->offset_bits = offset_bits;

    if (oob != NULL)

        *oob = (flags & JBIG2_HUFFMAN_FLAGS_ISOOB);

    return result;

}

/* TODO: more than 8 bits here is wasteful of memory. We have support

   for sub-trees in jbig2_huffman_get() above, but don't use it here.

   We should, and then revert to 8 bits */

#define LOG_TABLE_SIZE_MAX 16

/** Build an in-memory representation of a Huffman table from the

 *  set of template params provided by the spec or a table segment

 */

Jbig2HuffmanTable *

jbig2_build_huffman_table(Jbig2Ctx *ctx, const Jbig2HuffmanParams *params)

{

    int *LENCOUNT;

    int LENMAX = -1;

    const int lencountcount = 256;

    const Jbig2HuffmanLine *lines = params->lines;

    int n_lines = params->n_lines;

    int i, j;

    uint32_t max_j;

    int log_table_size = 0;

    Jbig2HuffmanTable *result;

    Jbig2HuffmanEntry *entries;

    int CURLEN;

    int firstcode = 0;

    int CURCODE;

    int CURTEMP;

    LENCOUNT = jbig2_new(ctx, int, lencountcount);

    if (LENCOUNT == NULL) {

        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate huffman histogram");

        return NULL;

    }

    memset(LENCOUNT, 0, sizeof(int) * lencountcount);

    /* B.3, 1. */

    for (i = 0; i < params->n_lines; i++) {

        int PREFLEN = lines[i].PREFLEN;

        int lts;

        if (PREFLEN > LENMAX) {

            for (j = LENMAX + 1; j < PREFLEN + 1; j++)

                LENCOUNT[j] = 0;

            LENMAX = PREFLEN;

        }

        LENCOUNT[PREFLEN]++;

        lts = PREFLEN + lines[i].RANGELEN;

        if (lts > LOG_TABLE_SIZE_MAX)

            lts = PREFLEN;

        if (lts <= LOG_TABLE_SIZE_MAX && log_table_size < lts)

            log_table_size = lts;

    }

    jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, JBIG2_UNKNOWN_SEGMENT_NUMBER, "constructing huffman table log size %d", log_table_size);

    max_j = 1 << log_table_size;

    result = jbig2_new(ctx, Jbig2HuffmanTable, 1);

    if (result == NULL) {

        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate result");

        jbig2_free(ctx->allocator, LENCOUNT);

        return NULL;

    }

    result->log_table_size = log_table_size;

    entries = jbig2_new(ctx, Jbig2HuffmanEntry, max_j);

    if (entries == NULL) {

        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate result entries");

        jbig2_free(ctx->allocator, result);

        jbig2_free(ctx->allocator, LENCOUNT);

        return NULL;

    }

    /* fill now to catch missing JBIG2Globals later */

    memset(entries, 0xFF, sizeof(Jbig2HuffmanEntry) * max_j);

    result->entries = entries;

    LENCOUNT[0] = 0;

    for (CURLEN = 1; CURLEN <= LENMAX; CURLEN++) {

        int shift = log_table_size - CURLEN;

        /* B.3 3.(a) */

        firstcode = (firstcode + LENCOUNT[CURLEN - 1]) << 1;

        CURCODE = firstcode;

        /* B.3 3.(b) */

        for (CURTEMP = 0; CURTEMP < n_lines; CURTEMP++) {

            int PREFLEN = lines[CURTEMP].PREFLEN;

            if (PREFLEN == CURLEN) {

                int RANGELEN = lines[CURTEMP].RANGELEN;

                uint32_t start_j = CURCODE << shift;

                uint32_t end_j = (CURCODE + 1) << shift;

                uint32_t cur_j;

                byte eflags = 0;

                if (end_j > max_j) {

                    jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "ran off the end of the entries table! (%d >= %d)", end_j, max_j);

                    jbig2_free(ctx->allocator, result->entries);

                    jbig2_free(ctx->allocator, result);

                    jbig2_free(ctx->allocator, LENCOUNT);

                    return NULL;

                }

                /* todo: build extension tables */

                if (params->HTOOB && CURTEMP == n_lines - 1)

                    eflags |= JBIG2_HUFFMAN_FLAGS_ISOOB;

                if (CURTEMP == n_lines - (params->HTOOB ? 3 : 2))

                    eflags |= JBIG2_HUFFMAN_FLAGS_ISLOW;

                if (PREFLEN + RANGELEN > LOG_TABLE_SIZE_MAX) {

                    for (cur_j = start_j; cur_j < end_j; cur_j++) {

                        entries[cur_j].u.RANGELOW = lines[CURTEMP].RANGELOW;

                        entries[cur_j].PREFLEN = PREFLEN;

                        entries[cur_j].RANGELEN = RANGELEN;

                        entries[cur_j].flags = eflags;

                    }

                } else {

                    for (cur_j = start_j; cur_j < end_j; cur_j++) {

                        int32_t HTOFFSET = (cur_j >> (shift - RANGELEN)) & ((1 << RANGELEN) - 1);

                        if (eflags & JBIG2_HUFFMAN_FLAGS_ISLOW)

                            entries[cur_j].u.RANGELOW = lines[CURTEMP].RANGELOW - HTOFFSET;

                        else

                            entries[cur_j].u.RANGELOW = lines[CURTEMP].RANGELOW + HTOFFSET;

                        entries[cur_j].PREFLEN = PREFLEN + RANGELEN;

                        entries[cur_j].RANGELEN = 0;

                        entries[cur_j].flags = eflags;

                    }

                }

                CURCODE++;

            }

        }

    }

    jbig2_free(ctx->allocator, LENCOUNT);

    return result;

}

/** Free the memory associated with the representation of table */

void

jbig2_release_huffman_table(Jbig2Ctx *ctx, Jbig2HuffmanTable *table)

{

    if (table != NULL) {

        jbig2_free(ctx->allocator, table->entries);

        jbig2_free(ctx->allocator, table);

    }

}

/* Routines to handle "code table segment (53)" */

/* return 'bitlen' bits from 'bitoffset' of 'data' */

static uint32_t

jbig2_table_read_bits(const byte *data, size_t *bitoffset, const int bitlen)

{

    uint32_t result = 0;

    uint32_t byte_offset = *bitoffset / 8;

    const int endbit = (*bitoffset & 7) + bitlen;

    const int n_proc_bytes = (endbit + 7) / 8;

    const int rshift = n_proc_bytes * 8 - endbit;

    int i;

    for (i = n_proc_bytes - 1; i >= 0; i--) {

        uint32_t d = data[byte_offset++];

        const int nshift = i * 8 - rshift;

        if (nshift > 0)

            d <<= nshift;

        else if (nshift < 0)

            d >>= -nshift;

        result |= d;

    }

    result &= ~(-1 << bitlen);

    *bitoffset += bitlen;

    return result;

}

/* Parse a code table segment, store Jbig2HuffmanParams in segment->result */

int

jbig2_table(Jbig2Ctx *ctx, Jbig2Segment *segment, const byte *segment_data)

{

    Jbig2HuffmanParams *params = NULL;

    Jbig2HuffmanLine *line = NULL;

    segment->result = NULL;

    if (segment->data_length < 10)

        goto too_short;

    {

        /* B.2 1) (B.2.1) Code table flags */

        const int code_table_flags = segment_data[0];

        const int HTOOB = code_table_flags & 0x01;      /* Bit 0: HTOOB */

        /* Bits 1-3: Number of bits used in code table line prefix size fields */

        const int HTPS = (code_table_flags >> 1 & 0x07) + 1;

        /* Bits 4-6: Number of bits used in code table line range size fields */

        const int HTRS = (code_table_flags >> 4 & 0x07) + 1;

        /* B.2 2) (B.2.2) The lower bound of the first table line in the encoded table */

        const int32_t HTLOW = jbig2_get_int32(segment_data + 1);

        /* B.2 3) (B.2.3) One larger than the upper bound of

           the last normal table line in the encoded table */

        const int32_t HTHIGH = jbig2_get_int32(segment_data + 5);

        /* estimated number of lines in this table, used for allocating memory for lines */

        const size_t lines_max = (segment->data_length * 8 - HTPS * (HTOOB ? 3 : 2)) / (HTPS + HTRS) + (HTOOB ? 3 : 2);

        /* points to a first table line data */

        const byte *lines_data = segment_data + 9;

        const size_t lines_data_bitlen = (segment->data_length - 9) * 8;        /* length in bit */

        /* bit offset: controls bit reading */

        size_t boffset = 0;

        /* B.2 4) */

        int32_t CURRANGELOW = HTLOW;

        size_t NTEMP = 0;

#ifdef JBIG2_DEBUG

        jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, segment->number,

                    "DECODING USER TABLE... Flags: %d, HTOOB: %d, HTPS: %d, HTRS: %d, HTLOW: %d, HTHIGH: %d",

                    code_table_flags, HTOOB, HTPS, HTRS, HTLOW, HTHIGH);

#endif

        if (HTLOW >= HTHIGH) {

            jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "invalid Huffman Table range");

            goto error_exit;

        }

        /* allocate HuffmanParams & HuffmanLine */

        params = jbig2_new(ctx, Jbig2HuffmanParams, 1);

        if (params == NULL) {

            jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to allocate Huffman Table Parameter");

            goto error_exit;

        }

        line = jbig2_new(ctx, Jbig2HuffmanLine, lines_max);

        if (line == NULL) {

            jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to allocate huffman table lines");

            goto error_exit;

        }

        /* B.2 5) */

        while (CURRANGELOW < HTHIGH) {

            /* B.2 5) a) */

            if (boffset + HTPS >= lines_data_bitlen)

                goto too_short;

            line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);

            /* B.2 5) b) */

            if (boffset + HTRS >= lines_data_bitlen)

                goto too_short;

            line[NTEMP].RANGELEN = jbig2_table_read_bits(lines_data, &boffset, HTRS);

            /* B.2 5) c) */

            line[NTEMP].RANGELOW = CURRANGELOW;

            CURRANGELOW += (1 << line[NTEMP].RANGELEN);

            NTEMP++;

        }

        /* B.2 6), B.2 7) lower range table line */

        if (boffset + HTPS >= lines_data_bitlen)

            goto too_short;

        line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);

        line[NTEMP].RANGELEN = 32;

        line[NTEMP].RANGELOW = HTLOW - 1;

        NTEMP++;

        /* B.2 8), B.2 9) upper range table line */

        if (boffset + HTPS >= lines_data_bitlen)

            goto too_short;

        line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);

        line[NTEMP].RANGELEN = 32;

        line[NTEMP].RANGELOW = HTHIGH;

        NTEMP++;

        /* B.2 10) */

        if (HTOOB) {

            /* B.2 10) a), B.2 10) b) out-of-bound table line */

            if (boffset + HTPS >= lines_data_bitlen)

                goto too_short;

            line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);

            line[NTEMP].RANGELEN = 0;

            line[NTEMP].RANGELOW = 0;

            NTEMP++;

        }

        if (NTEMP != lines_max) {

            Jbig2HuffmanLine *new_line = jbig2_renew(ctx, line,

                                                     Jbig2HuffmanLine, NTEMP);

            if (new_line == NULL) {

                jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to reallocate huffman table lines");

                goto error_exit;

            }

            line = new_line;

        }

        params->HTOOB = HTOOB;

        params->n_lines = NTEMP;

        params->lines = line;

        segment->result = params;

#ifdef JBIG2_DEBUG

        {

            int i;

            for (i = 0; i < NTEMP; i++) {

                jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, segment->number,

                            "Line: %d, PREFLEN: %d, RANGELEN: %d, RANGELOW: %d",

                            i, params->lines[i].PREFLEN, params->lines[i].RANGELEN, params->lines[i].RANGELOW);

            }

        }

#endif

    }

    return 0;

too_short:

    jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "segment too short");

error_exit:

    jbig2_free(ctx->allocator, line);

    jbig2_free(ctx->allocator, params);

    return -1;

}

/* free Jbig2HuffmanParams allocated by jbig2_huffman_table() */

void

jbig2_table_free(Jbig2Ctx *ctx, Jbig2HuffmanParams *params)

{

    if (params != NULL) {

        jbig2_free(ctx->allocator, (void *)params->lines);

        jbig2_free(ctx->allocator, params);

    }

}

/* find a user supplied table used by 'segment' and by 'index' */

const Jbig2HuffmanParams *

jbig2_find_table(Jbig2Ctx *ctx, Jbig2Segment *segment, int index)

{

    int i, table_index = 0;

    for (i = 0; i < segment->referred_to_segment_count; i++) {

        const Jbig2Segment *const rsegment = jbig2_find_segment(ctx, segment->referred_to_segments[i]);

        if (rsegment && (rsegment->flags & 63) == 53) {

            if (table_index == index)

                return (const Jbig2HuffmanParams *)rsegment->result;

            ++table_index;

        }

    }

    jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "huffman table not found (%d)", index);

    return NULL;

}

#ifdef TEST

#include <stdio.h>

/* cc -g -o jbig2_huffman.test1 -DTEST jbig2_huffman.c .libs/libjbig2dec.a */

/* a test bitstream, and a list of the table indices

   to use in decoding it. 1 = table B.1 (A), 2 = table B.2 (B), and so on */

/* this test stream should decode to { 8, 5, oob, 8 } */

static const byte test_stream[] = { 0xe9, 0xcb, 0xf4, 0x00 };

static const byte test_tabindex[] = { 4, 2, 2, 1 };

static int

test_get_word1(Jbig2Ctx *ctx, Jbig2WordStream *self, size_t offset, uint32_t *word)

{

    uint32_t val = 0;

    int ret = 0;

    if (self == NULL || word == NULL)

        return -1;

    if (offset >= sizeof (test_stream))

        return 0;

    if (offset < sizeof(test_stream)) {

        val |= test_stream[offset] << 24;

        ret++;

    }

    if (offset + 1 < sizeof(test_stream)) {

        val |= test_stream[offset + 1] << 16;

        ret++;

    }

    if (offset + 2 < sizeof(test_stream)) {

        val |= test_stream[offset + 2] << 8;

        ret++;

    }

    if (offset + 3 < sizeof(test_stream)) {

        val |= test_stream[offset + 3];

        ret++;

    }

    *word = val;

    return ret;

}

static int test1()

{

    Jbig2Ctx *ctx;

    Jbig2HuffmanTable *tables[5];

    Jbig2HuffmanState *hs = NULL;

    Jbig2WordStream ws;

    bool oob;

    int32_t code;

    int i;

    int success = 0;

    ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);

    if (ctx == NULL) {

        fprintf(stderr, "Failed to allocate jbig2 context\n");

        goto cleanup;

    }

    tables[0] = NULL;

    tables[1] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_A);

    tables[2] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_B);

    tables[3] = NULL;

    tables[4] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_D);

    if (tables[1] == NULL || tables[2] == NULL || tables[4] == NULL)

    {

        fprintf(stderr, "Failed to build huffman tables");

        goto cleanup;

    }

    ws.get_next_word = test_get_word1;

    hs = jbig2_huffman_new(ctx, &ws);

    if (hs == NULL) {

        fprintf(stderr, "Failed to allocate huffman state");

        goto cleanup;

    }

    printf("testing jbig2 huffman decoding...");

    printf("\t(should be 8 5 (oob) 8)\n");

    {

        int i;

        int sequence_length = sizeof(test_tabindex);

        for (i = 0; i < sequence_length; i++) {

            code = jbig2_huffman_get(hs, tables[test_tabindex[i]], &oob);

            if (oob)

                printf("(oob) ");

            else

                printf("%d ", code);

        }

    }

    printf("\n");

    success = 1;

cleanup:

    jbig2_huffman_free(ctx, hs);

    for (i = 0; i < 5; i++)

        jbig2_release_huffman_table(ctx, tables[i]);

    jbig2_ctx_free(ctx);

    return success;

}

#include <stdio.h>

/* a decoding test of each line from each standard table */

/* test code for Table B.1 - Standard Huffman table A */

const int32_t test_output_A[] = {

    /* line 0, PREFLEN=1, RANGELEN=4, VAL=0..15, 0+VAL */

    0,      /* 0 0000 */

    1,      /* 0 0001 */

    14,     /* 0 1110 */

    15,     /* 0 1111 */

    /* line 1, PREFLEN=2, RANGELEN=8, VAL=16..271, 10+(VAL-16) */

    16,     /* 10 00000000 */

    17,     /* 10 00000001 */

    270,    /* 10 11111110 */

    271,    /* 10 11111111 */

    /* line 2, PREFLEN=3, RANGELEN=16, VAL=272..65807, 110+(VAL-272) */

    272,    /* 110 00000000 00000000 */

    273,    /* 110 00000000 00000001 */

    65806,  /* 110 11111111 11111110 */

    65807,  /* 110 11111111 11111111 */

    /* line 3, PREFLEN=3, RANGELEN=32, VAL=65808..INF, 111+(VAL-65808) */

    65808,  /* 111 00000000 00000000 00000000 00000000 */

    65809,  /* 111 00000000 00000000 00000000 00000001 */

};

const byte test_input_A[] = {

    /* 0000 0000 0101 1100 1111 1000 0000 0010 */

       0x00,     0x5c,     0xf8,     0x02,

    /* 0000 0001 1011 1111 1010 1111 1111 1100 */

       0x01,     0xbf,     0xaf,     0xfc,

    /* 0000 0000 0000 0001 1000 0000 0000 0000 */

       0x00,     0x01,     0x80,     0x00,

    /* 0111 0111 1111 1111 1111 0110 1111 1111 */

       0x77,     0xff,     0xf6,     0xff,

    /* 1111 1111 1110 0000 0000 0000 0000 0000 */

       0xff,     0xe0,     0x00,     0x00,

    /* 0000 0000 0001 1100 0000 0000 0000 0000 */

       0x00,     0x1c,     0x00,     0x00,

    /* 0000 0000 0000 01 */

       0x00,     0x04,

};

/* test code for Table B.2 - Standard Huffman table B */

const int32_t test_output_B[] = {

    /* line 0, PREFLEN=1, RANGELEN=0, VAL=0, 0 */

    0,      /* 0 */

    /* line 1, PREFLEN=2, RANGELEN=0, VAL=1, 10 */

    1,      /* 10 */

    /* line 2, PREFLEN=3, RANGELEN=0, VAL=2, 110 */

    2,      /* 110 */

    /* line 3, PREFLEN=4, RANGELEN=3, VAL=3..10, 1110+(VAL-3) */

    3,      /* 1110 000 */

    4,      /* 1110 001 */

    9,      /* 1110 110 */

    10,     /* 1110 111 */

    /* line 4, PREFLEN=5, RANGELEN=6, VAL=11..74, 11110+(VAL-11) */

    11,     /* 11110 000000 */

    12,     /* 11110 000001 */

    73,     /* 11110 111110 */

    74,     /* 11110 111111 */

    /* line 5, PREFLEN=6, RANGELEN=32, VAL=75..INF, 111110+(VAL-75) */

    75,     /* 111110 00000000 00000000 00000000 00000000 */

    76,     /* 111110 00000000 00000000 00000000 00000001 */

    /* line 6, PREFLEN=6, VAL=OOB, 111111 */

    /*OOB*/ /* 111111 */

};

const byte test_input_B[] = {

    /* 0101 1011 1000 0111 0001 1110 1101 1101 */

       0x5b,     0x87,     0x1e,     0xdd,

    /* 1111 1100 0000 0111 1000 0001 1111 0111 */

       0xfc,     0x07,     0x81,     0xf7,

    /* 1101 1110 1111 1111 1110 0000 0000 0000 */

       0xde,     0xff,     0xe0,     0x00,

    /* 0000 0000 0000 0000 0000 1111 1000 0000 */

       0x00,     0x00,     0x0f,     0x80,

    /* 0000 0000 0000 0000 0000 0000 0111 1111 */

       0x00,     0x00,     0x00,     0x7f,

};

/* test code for Table B.3 - Standard Huffman table C */

const int32_t test_output_C[] = {

    /* line 0, PREFLEN=8, RANGELEN=8, VAL=-256..-1, 11111110+(VAL+256) */

    -256,   /* 11111110 00000000 */

    -255,   /* 11111110 00000001 */

    -2,     /* 11111110 11111110 */

    -1,     /* 11111110 11111111 */

    /* line 1, PREFLEN=1, RANGELEN=0, VAL=0, 0 */

    0,      /* 0 */

    /* line 2, PREFLEN=2, RANGELEN=0, VAL=1, 10 */

    1,      /* 10 */

    /* line 3, PREFLEN=3, RANGELEN=0, VAL=2, 110 */

    2,      /* 110 */

    /* line 4, PREFLEN=4, RANGELEN=3, VAL=3..10, 1110+(VAL-3) */

    3,      /* 1110 000 */

    4,      /* 1110 001 */

    9,      /* 1110 110 */

    10,     /* 1110 111 */

    /* line 5, PREFLEN=5, RANGELEN=6, VAL=11..74, 11110+(VAL-11) */

    11,     /* 11110 000000 */

    12,     /* 11110 000001 */

    73,     /* 11110 111110 */

    74,     /* 11110 111111 */

    /* line 6, PREFLEN=8, RANGELEN=32, VAL=-INF..-257, 11111111+(-257-VAL) */

    -257,   /* 11111111 00000000 00000000 00000000 00000000 */

    -258,   /* 11111111 00000000 00000000 00000000 00000001 */

    /* line 7, PREFLEN=7, RANGELEN=32, VAL=75..INF, 1111110+(VAL-75) */

    75,     /* 1111110 00000000 00000000 00000000 00000000 */

    76,     /* 1111110 00000000 00000000 00000000 00000001 */

    /* line 8, PREFLEN=6, VAL=OOB, 111110 */

    /*OOB*/ /* 111110 */

};

const byte test_input_C[] = {

    /* 1111 1110 0000 0000 1111 1110 0000 0001 */

       0xfe,     0x00,     0xfe,     0x01,

    /* 1111 1110 1111 1110 1111 1110 1111 1111 */

       0xfe,     0xfe,     0xfe,     0xff,

    /* 0101 1011 1000 0111 0001 1110 1101 1101 */

       0x5b,     0x87,     0x1e,     0xdd,

    /* 1111 1100 0000 0111 1000 0001 1111 0111 */

       0xfc,     0x07,     0x81,     0xf7,

    /* 1101 1110 1111 1111 1111 1100 0000 0000 */

       0xde,     0xff,     0xfc,     0x00,

    /* 0000 0000 0000 0000 0000 0011 1111 1100 */

       0x00,     0x00,     0x03,     0xfc,

    /* 0000 0000 0000 0000 0000 0000 0000 0111 */

       0x00,     0x00,     0x00,     0x07,

    /* 1111 0000 0000 0000 0000 0000 0000 0000 */

       0xf0,     0x00,     0x00,     0x00,

    /* 0000 0111 1110 0000 0000 0000 0000 0000 */

       0x07,     0xe0,     0x00,     0x00,

    /* 0000 0000 0001 1111 10 */

       0x00,     0x1f,     0x80,

};

/* test code for Table B.4 - Standard Huffman table D */

const int32_t test_output_D[] = {

    /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */

    1,      /* 0 */

    /* line 1, PREFLEN=2, RANGELEN=0, VAL=2, 10 */

    2,      /* 10 */

    /* line 2, PREFLEN=3, RANGELEN=0, VAL=3, 110 */

    3,      /* 110 */