/src/htslib/cram/cram_codecs.c

Source
/*
Copyright (c) 2012-2021,2023, 2025, 2026 Genome Research Ltd.
Author: James Bonfield <jkb@sanger.ac.uk>

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

   1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

   2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.

   3. Neither the names Genome Research Ltd and Wellcome Trust Sanger
Institute nor the names of its contributors may be used to endorse or promote
products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY GENOME RESEARCH LTD AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL GENOME RESEARCH LTD OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/*
 * FIXME: add checking of cram_external_type to return NULL on unsupported
 * {codec,type} tuples.
 */

#define HTS_BUILDING_LIBRARY // Enables HTSLIB_EXPORT, see htslib/hts_defs.h
#include <config.h>

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <stdint.h>
#include <errno.h>
#include <stddef.h>

#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
#include "../fuzz_settings.h"
#endif

#include "../htslib/hts_alloc.h"
#include "../htslib/hts_endian.h"

#if defined(HAVE_EXTERNAL_LIBHTSCODECS)
#include <htscodecs/varint.h>
#include <htscodecs/pack.h>
#include <htscodecs/rle.h>
#else
#include "../htscodecs/htscodecs/varint.h"
#include "../htscodecs/htscodecs/pack.h"
#include "../htscodecs/htscodecs/rle.h"
#endif

#include "cram.h"

/*
 * ---------------------------------------------------------------------------
 * Block bit-level I/O functions.
 * All defined static here to promote easy inlining by the compiler.
 */

#if 0
/* Get a single bit, MSB first */
static signed int get_bit_MSB(cram_block *block) {
    unsigned int val;

    if (block->byte > block->alloc)
        return -1;

    val = block->data[block->byte] >> block->bit;
    if (--block->bit == -1) {
        block->bit = 7;
        block->byte++;
        //printf("(%02X)", block->data[block->byte]);
    }

    //printf("-B%d-", val&1);

    return val & 1;
}
#endif

/*
 * Count number of successive 0 and 1 bits
 */
static int get_one_bits_MSB(cram_block *block) {
    int n = 0, b;
    if (block->byte >= block->uncomp_size)
        return -1;
    do {
        b = block->data[block->byte] >> block->bit;
        if (--block->bit == -1) {
            block->bit = 7;
            block->byte++;
            if (block->byte == block->uncomp_size && (b&1))
                return -1;
        }
        n++;
    } while (b&1);

    return n-1;
}

static int get_zero_bits_MSB(cram_block *block) {
    int n = 0, b;
    if (block->byte >= block->uncomp_size)
        return -1;
    do {
        b = block->data[block->byte] >> block->bit;
        if (--block->bit == -1) {
            block->bit = 7;
            block->byte++;
            if (block->byte == block->uncomp_size && !(b&1))
                return -1;
        }
        n++;
    } while (!(b&1));

    return n-1;
}

#if 0
/* Stores a single bit */
static void store_bit_MSB(cram_block *block, unsigned int bit) {
    if (block->byte >= block->alloc) {
        block->alloc = block->alloc ? block->alloc*2 : 1024;
        block->data = realloc(block->data, block->alloc);
    }

    if (bit)
        block->data[block->byte] |= (1 << block->bit);

    if (--block->bit == -1) {
        block->bit = 7;
        block->byte++;
        block->data[block->byte] = 0;
    }
}
#endif

#if 0
/* Rounds to the next whole byte boundary first */
static void store_bytes_MSB(cram_block *block, char *bytes, int len) {
    if (block->bit != 7) {
        block->bit = 7;
        block->byte++;
    }

    while (block->byte + len >= block->alloc) {
        block->alloc = block->alloc ? block->alloc*2 : 1024;
        block->data = realloc(block->data, block->alloc);
    }

    memcpy(&block->data[block->byte], bytes, len);
    block->byte += len;
}
#endif

/* Local optimised copy for inlining */
static inline int64_t get_bits_MSB(cram_block *block, int nbits) {
    uint64_t val = 0;
    int i;

#if 0
    // Fits within the current byte */
    if (nbits <= block->bit+1) {
        val = (block->data[block->byte]>>(block->bit-(nbits-1))) & ((1<<nbits)-1);
        if ((block->bit -= nbits) == -1) {
            block->bit = 7;
            block->byte++;
        }
        return val;
    }

    // partial first byte
    val = block->data[block->byte] & ((1<<(block->bit+1))-1);
    nbits -= block->bit+1;
    block->bit = 7;
    block->byte++;

    // whole middle bytes
    while (nbits >= 8) {
        val = (val << 8) | block->data[block->byte++];
        nbits -= 8;
    }

    val <<= nbits;
    val |= (block->data[block->byte]>>(block->bit-(nbits-1))) & ((1<<nbits)-1);
    block->bit -= nbits;
    return val;
#endif

#if 0
    /* Inefficient implementation! */
    //printf("{");
    for (i = 0; i < nbits; i++)
        //val = (val << 1) | get_bit_MSB(block);
        GET_BIT_MSB(block, val);
#endif

#if 1
    /* Combination of 1st two methods */
    if (nbits <= block->bit+1) {
        val = (block->data[block->byte]>>(block->bit-(nbits-1))) & ((1<<nbits)-1);
        if ((block->bit -= nbits) == -1) {
            block->bit = 7;
            block->byte++;
        }
        return val;
    }

    switch(nbits) {
//  case 15: GET_BIT_MSB(block, val); // fall through
//  case 14: GET_BIT_MSB(block, val); // fall through
//  case 13: GET_BIT_MSB(block, val); // fall through
//  case 12: GET_BIT_MSB(block, val); // fall through
//  case 11: GET_BIT_MSB(block, val); // fall through
//  case 10: GET_BIT_MSB(block, val); // fall through
//  case  9: GET_BIT_MSB(block, val); // fall through
    case  8: GET_BIT_MSB(block, val); // fall through
    case  7: GET_BIT_MSB(block, val); // fall through
    case  6: GET_BIT_MSB(block, val); // fall through
    case  5: GET_BIT_MSB(block, val); // fall through
    case  4: GET_BIT_MSB(block, val); // fall through
    case  3: GET_BIT_MSB(block, val); // fall through
    case  2: GET_BIT_MSB(block, val); // fall through
    case  1: GET_BIT_MSB(block, val);
        break;

    default:
        for (i = 0; i < nbits; i++)
            //val = (val << 1) | get_bit_MSB(block);
            GET_BIT_MSB(block, val);
    }
#endif

    //printf("=0x%x}", val);

    return val;
}

/*
 * Can store up to 24-bits worth of data encoded in an integer value
 * Possibly we'd want to have a less optimal store_bits function when dealing
 * with nbits > 24, but for now we assume the codes generated are never
 * that big. (Given this is only possible with 121392 or more
 * characters with exactly the correct frequency distribution we check
 * for it elsewhere.)
 */
static int store_bits_MSB(cram_block *block, uint64_t val, int nbits) {
    //fprintf(stderr, " store_bits: %02x %d\n", val, nbits);

    /*
     * Use slow mode until we tweak the huffman generator to never generate
     * codes longer than 24-bits.
     */
    unsigned int mask;

    if (block->byte+8 >= block->alloc) {
        if (block->byte) {
            block->alloc *= 2;
            block->data = hts_realloc_ps(block->data, sizeof(*block->data),
                                         block->alloc, 8);
            if (!block->data)
                return -1;
        } else {
            block->alloc = 1024;
            block->data = hts_realloc_ps(block->data, sizeof(*block->data),
                                         block->alloc, 8);
            if (!block->data)
                return -1;
            block->data[0] = 0; // initialise first byte of buffer
        }
    }

    /* fits in current bit-field */
    if (nbits <= block->bit+1) {
        block->data[block->byte] |= (val << (block->bit+1-nbits));
        if ((block->bit-=nbits) == -1) {
            block->bit = 7;
            block->byte++;
            block->data[block->byte] = 0;
        }
        return 0;
    }

    block->data[block->byte] |= (val >> (nbits -= block->bit+1));
    block->bit = 7;
    block->byte++;
    block->data[block->byte] = 0;

    mask = 1<<(nbits-1);
    do {
        if (val & mask)
            block->data[block->byte] |= (1 << block->bit);
        if (--block->bit == -1) {
            block->bit = 7;
            block->byte++;
            block->data[block->byte] = 0;
        }
        mask >>= 1;
    } while(--nbits);

    return 0;
}

/*
 * Returns the next 'size' bytes from a block, or NULL if insufficient
 * data left.This is just a pointer into the block data and not an
 * allocated object, so do not free the result.
 */
static char *cram_extract_block(cram_block *b, int size) {
    char *cp = (char *)b->data + b->idx;
    b->idx += size;
    if (b->idx > b->uncomp_size)
        return NULL;

    return cp;
}

/*
 * ---------------------------------------------------------------------------
 * EXTERNAL
 *
 * In CRAM 3.0 and earlier, E_EXTERNAL use the data type to determine the
 * size of the object being returned.  This type is hard coded in the
 * spec document (changing from uint32 to uint64 requires a spec change)
 * and there is no data format introspection so implementations have
 * to determine which size to use based on version numbers.   It also
 * doesn't support signed data.
 *
 * For simplicity we use the same encode and decode functions for
 * bytes (CRAM4) and external (CRAM3). Given we already had code to
 * replace codec + type into a function pointer it makes little
 * difference how we ended up at that function.  However we disallow
 * this codec to operate on integer data for CRAM4 onwards.
 */
int cram_external_decode_int(cram_slice *slice, cram_codec *c,
                             cram_block *in, char *out, int *out_size) {
    char *cp;
    cram_block *b;

    /* Find the external block */
    b = cram_get_block_by_id(slice, c->u.external.content_id);
    if (!b)
        return *out_size?-1:0;

    cp = (char *)b->data + b->idx;
    // E_INT and E_LONG are guaranteed single item queries
    int err = 0;
    *(int32_t *)out = c->vv->varint_get32(&cp, (char *)b->data + b->uncomp_size, &err);
    b->idx = cp - (char *)b->data;
    *out_size = 1;

    return err ? -1 : 0;
}

int cram_external_decode_long(cram_slice *slice, cram_codec *c,
                              cram_block *in, char *out, int *out_size) {
    char *cp;
    cram_block *b;

    /* Find the external block */
    b = cram_get_block_by_id(slice, c->u.external.content_id);
    if (!b)
        return *out_size?-1:0;

    cp = (char *)b->data + b->idx;
    // E_INT and E_LONG are guaranteed single item queries
    int err = 0;
    *(int64_t *)out = c->vv->varint_get64(&cp, (char *)b->data + b->uncomp_size, &err);
    b->idx = cp - (char *)b->data;
    *out_size = 1;

    return err ? -1 : 0;
}

int cram_external_decode_char(cram_slice *slice, cram_codec *c,
                              cram_block *in, char *out,
                              int *out_size) {
    char *cp;
    cram_block *b;

    /* Find the external block */
    b = cram_get_block_by_id(slice, c->u.external.content_id);
    if (!b)
        return *out_size?-1:0;

    cp = cram_extract_block(b, *out_size);
    if (!cp)
        return -1;

    if (out)
        memcpy(out, cp, *out_size);
    return 0;
}

static int cram_external_decode_block(cram_slice *slice, cram_codec *c,
                                      cram_block *in, char *out_,
                                      int *out_size) {
    char *cp;
    cram_block *out = (cram_block *)out_;
    cram_block *b = NULL;

    /* Find the external block */
    b = cram_get_block_by_id(slice, c->u.external.content_id);
    if (!b)
        return *out_size?-1:0;

    cp = cram_extract_block(b, *out_size);
    if (!cp)
        return -1;

    BLOCK_APPEND(out, cp, *out_size);
    return 0;

 block_err:
    return -1;
}

void cram_external_decode_free(cram_codec *c) {
    if (c)
        free(c);
}


int cram_external_decode_size(cram_slice *slice, cram_codec *c) {
    cram_block *b;

    /* Find the external block */
    b = cram_get_block_by_id(slice, c->u.external.content_id);
    if (!b)
        return -1;

    return b->uncomp_size;
}

cram_block *cram_external_get_block(cram_slice *slice, cram_codec *c) {
    return cram_get_block_by_id(slice, c->u.external.content_id);
}

int cram_external_describe(cram_codec *c, kstring_t *ks) {
    return ksprintf(ks, "EXTERNAL(id=%d)",
                    c->u.external.content_id) < 0 ? -1 : 0;
}

cram_codec *cram_external_decode_init(cram_block_compression_hdr *hdr,
                                      char *data, int size,
                                      enum cram_encoding codec,
                                      enum cram_external_type option,
                                      int version, varint_vec *vv) {
    cram_codec *c = NULL;
    char *cp = data;

    if (size < 1)
        goto malformed;

    if (!(c = malloc(sizeof(*c))))
        return NULL;

    c->codec  = E_EXTERNAL;
    // CRAM 3 and earlier encodes integers as EXTERNAL.  We need
    // use the option field to indicate the input data format so
    // we know which serialisation format to use.
    if (option == E_INT)
        c->decode = cram_external_decode_int;
    else if (option == E_LONG)
        c->decode = cram_external_decode_long;
    else if (option == E_BYTE_ARRAY || option == E_BYTE)
        c->decode = cram_external_decode_char;
    else
        c->decode = cram_external_decode_block;

    c->free   = cram_external_decode_free;
    c->size   = cram_external_decode_size;
    c->get_block = cram_external_get_block;
    c->describe = cram_external_describe;

    c->u.external.content_id = vv->varint_get32(&cp, data+size, NULL);

    if (cp - data != size)
        goto malformed;

    c->u.external.type = option;

    return c;

 malformed:
    hts_log_error("Malformed external header stream");
    free(c);
    return NULL;
}

int cram_external_encode_int(cram_slice *slice, cram_codec *c,
                             char *in, int in_size) {
    uint32_t *i32 = (uint32_t *)in;
    return c->vv->varint_put32_blk(c->out, *i32) >= 0 ? 0 : -1;
}

int cram_external_encode_sint(cram_slice *slice, cram_codec *c,
                             char *in, int in_size) {
    int32_t *i32 = (int32_t *)in;
    return c->vv->varint_put32s_blk(c->out, *i32) >= 0 ? 0 : -1;
}

int cram_external_encode_long(cram_slice *slice, cram_codec *c,
                             char *in, int in_size) {
    uint64_t *i64 = (uint64_t *)in;
    return c->vv->varint_put64_blk(c->out, *i64) >= 0 ? 0 : -1;
}

int cram_external_encode_slong(cram_slice *slice, cram_codec *c,
                               char *in, int in_size) {
    int64_t *i64 = (int64_t *)in;
    return c->vv->varint_put64s_blk(c->out, *i64) >= 0 ? 0 : -1;
}

int cram_external_encode_char(cram_slice *slice, cram_codec *c,
                              char *in, int in_size) {
    BLOCK_APPEND(c->out, in, in_size);
    return 0;

 block_err:
    return -1;
}

void cram_external_encode_free(cram_codec *c) {
    if (!c)
        return;
    free(c);
}

int cram_external_encode_store(cram_codec *c, cram_block *b, char *prefix,
                               int version) {
    char tmp[99], *tp = tmp, *tpend = tmp+99;
    int len = 0, r = 0, n;

    if (prefix) {
        size_t l = strlen(prefix);
        BLOCK_APPEND(b, prefix, l);
        len += l;
    }

    tp += c->vv->varint_put32(tp, tpend, c->u.e_external.content_id);
    len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
    len += (n = c->vv->varint_put32_blk(b, tp-tmp));   r |= n;
    BLOCK_APPEND(b, tmp, tp-tmp);
    len += tp-tmp;

    if (r > 0)
        return len;

 block_err:
    return -1;
}

cram_codec *cram_external_encode_init(cram_stats *st,
                                      enum cram_encoding codec,
                                      enum cram_external_type option,
                                      void *dat,
                                      int version, varint_vec *vv) {
    cram_codec *c;

    c = malloc(sizeof(*c));
    if (!c)
        return NULL;
    c->codec = E_EXTERNAL;
    c->free = cram_external_encode_free;
    // CRAM 3 and earlier encodes integers as EXTERNAL.  We need
    // use the option field to indicate the input data format so
    // we know which serialisation format to use.
    if (option == E_INT)
        c->encode = cram_external_encode_int;
    else if (option == E_LONG)
        c->encode = cram_external_encode_long;
    else if (option == E_BYTE_ARRAY || option == E_BYTE)
        c->encode = cram_external_encode_char;
    else
        abort();
    c->store = cram_external_encode_store;
    c->flush = NULL;

    c->u.e_external.content_id = (size_t)dat;

    return c;
}

/*
 * ---------------------------------------------------------------------------
 * BETA
 */
int cram_beta_decode_long(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
    int64_t *out_i = (int64_t *)out;
    int i, n = *out_size;

    if (c->u.beta.nbits) {
        if (cram_not_enough_bits(in, c->u.beta.nbits * n))
            return -1;

        for (i = 0; i < n; i++)
            out_i[i] = get_bits_MSB(in, c->u.beta.nbits) - c->u.beta.offset;
    } else {
        for (i = 0; i < n; i++)
            out_i[i] = -c->u.beta.offset;
    }

    return 0;
}

int cram_beta_decode_int(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
    int32_t *out_i = (int32_t *)out;
    int i, n = *out_size;

    if (c->u.beta.nbits) {
        if (cram_not_enough_bits(in, c->u.beta.nbits * n))
            return -1;

        for (i = 0; i < n; i++)
            out_i[i] = get_bits_MSB(in, c->u.beta.nbits) - c->u.beta.offset;
    } else {
        for (i = 0; i < n; i++)
            out_i[i] = -c->u.beta.offset;
    }

    return 0;
}

int cram_beta_decode_char(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
    int i, n = *out_size;


    if (c->u.beta.nbits) {
        if (cram_not_enough_bits(in, c->u.beta.nbits * n))
            return -1;

        if (out)
            for (i = 0; i < n; i++)
                out[i] = get_bits_MSB(in, c->u.beta.nbits) - c->u.beta.offset;
        else
            for (i = 0; i < n; i++)
                get_bits_MSB(in, c->u.beta.nbits);
    } else {
        if (out)
            for (i = 0; i < n; i++)
                out[i] = -c->u.beta.offset;
    }

    return 0;
}

void cram_beta_decode_free(cram_codec *c) {
    if (c)
        free(c);
}

int cram_beta_describe(cram_codec *c, kstring_t *ks) {
    return ksprintf(ks, "BETA(offset=%d, nbits=%d)",
                    c->u.beta.offset, c->u.beta.nbits)
        < 0 ? -1 : 0;
}

cram_codec *cram_beta_decode_init(cram_block_compression_hdr *hdr,
                                  char *data, int size,
                                  enum cram_encoding codec,
                                  enum cram_external_type option,
                                  int version, varint_vec *vv) {
    cram_codec *c;
    char *cp = data;

    if (!(c = malloc(sizeof(*c))))
        return NULL;

    c->codec  = E_BETA;
    if (option == E_INT)
        c->decode = cram_beta_decode_int;
    else if (option == E_LONG)
        c->decode = cram_beta_decode_long;
    else if (option == E_BYTE_ARRAY || option == E_BYTE)
        c->decode = cram_beta_decode_char;
    else {
        hts_log_error("BYTE_ARRAYs not supported by this codec");
        free(c);
        return NULL;
    }
    c->free   = cram_beta_decode_free;
    c->describe = cram_beta_describe;

    c->u.beta.nbits = -1;
    c->u.beta.offset = vv->varint_get32(&cp, data + size, NULL);
    if (cp < data + size) // Ensure test below works
        c->u.beta.nbits  = vv->varint_get32(&cp, data + size, NULL);

    if (cp - data != size
        || c->u.beta.nbits < 0 || c->u.beta.nbits > 8 * sizeof(int)) {
        hts_log_error("Malformed beta header stream");
        free(c);
        return NULL;
    }

    return c;
}

int cram_beta_encode_store(cram_codec *c, cram_block *b,
                           char *prefix, int version) {
    int len = 0, r = 0, n;

    if (prefix) {
        size_t l = strlen(prefix);
        BLOCK_APPEND(b, prefix, l);
        len += l;
    }

    len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
    // codec length
    len += (n = c->vv->varint_put32_blk(b, c->vv->varint_size(c->u.e_beta.offset)
                                         + c->vv->varint_size(c->u.e_beta.nbits)));
    r |= n;
    len += (n = c->vv->varint_put32_blk(b, c->u.e_beta.offset)); r |= n;
    len += (n = c->vv->varint_put32_blk(b, c->u.e_beta.nbits));  r |= n;

    if (r > 0) return len;

 block_err:
    return -1;
}

int cram_beta_encode_long(cram_slice *slice, cram_codec *c,
                          char *in, int in_size) {
    int64_t *syms = (int64_t *)in;
    int i, r = 0;

    for (i = 0; i < in_size; i++)
        r |= store_bits_MSB(c->out, syms[i] + c->u.e_beta.offset,
                            c->u.e_beta.nbits);

    return r;
}

int cram_beta_encode_int(cram_slice *slice, cram_codec *c,
                         char *in, int in_size) {
    int *syms = (int *)in;
    int i, r = 0;

    for (i = 0; i < in_size; i++)
        r |= store_bits_MSB(c->out, syms[i] + c->u.e_beta.offset,
                            c->u.e_beta.nbits);

    return r;
}

int cram_beta_encode_char(cram_slice *slice, cram_codec *c,
                          char *in, int in_size) {
    unsigned char *syms = (unsigned char *)in;
    int i, r = 0;

    for (i = 0; i < in_size; i++)
        r |= store_bits_MSB(c->out, syms[i] + c->u.e_beta.offset,
                            c->u.e_beta.nbits);

    return r;
}

void cram_beta_encode_free(cram_codec *c) {
    if (c) free(c);
}

cram_codec *cram_beta_encode_init(cram_stats *st,
                                  enum cram_encoding codec,
                                  enum cram_external_type option,
                                  void *dat,
                                  int version, varint_vec *vv) {
    cram_codec *c;
    hts_pos_t min_val, max_val;
    int len = 0;
    int64_t range;

    c = malloc(sizeof(*c));
    if (!c)
        return NULL;
    c->codec  = E_BETA;
    c->free   = cram_beta_encode_free;
    if (option == E_INT)
        c->encode = cram_beta_encode_int;
    else if (option == E_LONG)
        c->encode = cram_beta_encode_long;
    else
        c->encode = cram_beta_encode_char;
    c->store  = cram_beta_encode_store;
    c->flush = NULL;

    if (dat) {
        min_val = ((hts_pos_t *)dat)[0];
        max_val = ((hts_pos_t *)dat)[1];
    } else {
        min_val = INT_MAX;
        max_val = INT_MIN;
        int i;
        for (i = 0; i < MAX_STAT_VAL; i++) {
            if (!st->freqs[i])
                continue;
            if (min_val > i)
                min_val = i;
            max_val = i;
        }
        if (st->h) {
            khint_t k;

            for (k = kh_begin(st->h); k != kh_end(st->h); k++) {
                if (!kh_exist(st->h, k))
                    continue;

                i = kh_key(st->h, k);
                if (min_val > i)
                    min_val = i;
                if (max_val < i)
                    max_val = i;
            }
        }
    }

    if (max_val < min_val)
        goto err;

    range = (int64_t) max_val - min_val;
    switch (option) {
    case E_INT:
        if (max_val > UINT_MAX || range > UINT_MAX)
            goto err;
        break;

    default:
        break;
    }

    c->u.e_beta.offset = -min_val;
    while (range) {
        len++;
        range >>= 1;
    }
    c->u.e_beta.nbits = len;

    return c;

 err:
    free(c);
    return NULL;
}

/*
 * ---------------------------------------------------------------------------
 * SUBEXP
 */
int cram_subexp_decode(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
    int32_t *out_i = (int32_t *)out;
    int n, count;
    int k = c->u.subexp.k;

    for (count = 0, n = *out_size; count < n; count++) {
        int u = 0, tail;
        int val;

        /* Get number of 1s: u */
        u = get_one_bits_MSB(in);
        if (u < 0 || cram_not_enough_bits(in, u > 0 ? u + k - 1 : k))
            return -1;
        /*
         * Val is
         * u > 0:  2^(k+u-1) + k+u-1 bits
         * u = 0:  k bits
         */
        if (u) {
            if (u > 31-k)
                return -1;
            tail = u + k-1;
            val = 0;
            while (tail) {
                GET_BIT_MSB(in, val);
                tail--;
            }
            val += 1 << (u + k-1);
        } else {
            tail = k;
            val = 0;
            while (tail) {
                GET_BIT_MSB(in, val);
                tail--;
            }
        }

        out_i[count] = val - c->u.subexp.offset;
    }

    return 0;
}

void cram_subexp_decode_free(cram_codec *c) {
    if (c)
        free(c);
}

int cram_subexp_describe(cram_codec *c, kstring_t *ks) {
    return ksprintf(ks, "SUBEXP(offset=%d,k=%d)",
                    c->u.subexp.offset,
                    c->u.subexp.k)
        < 0 ? -1 : 0;
}

cram_codec *cram_subexp_decode_init(cram_block_compression_hdr *hdr,
                                    char *data, int size,
                                    enum cram_encoding codec,
                                    enum cram_external_type option,
                                    int version, varint_vec *vv) {
    cram_codec *c;
    char *cp = data;

    if (option != E_INT) {
        hts_log_error("This codec only supports INT encodings");
        return NULL;
    }

    if (!(c = malloc(sizeof(*c))))
        return NULL;

    c->codec  = E_SUBEXP;
    c->decode = cram_subexp_decode;
    c->free   = cram_subexp_decode_free;
    c->describe = cram_subexp_describe;
    c->u.subexp.k = -1;

    c->u.subexp.offset = vv->varint_get32(&cp, data + size, NULL);
    c->u.subexp.k      = vv->varint_get32(&cp, data + size, NULL);

    if (cp - data != size || c->u.subexp.k < 0 || c->u.subexp.k > 31) {
        hts_log_error("Malformed subexp header stream");
        free(c);
        return NULL;
    }

    return c;
}

/*
 * ---------------------------------------------------------------------------
 * GAMMA
 */
int cram_gamma_decode(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
    int32_t *out_i = (int32_t *)out;
    int i, n;

    for (i = 0, n = *out_size; i < n; i++) {
        int nz = 0;
        int val;
        //while (get_bit_MSB(in) == 0) nz++;
        nz = get_zero_bits_MSB(in);
        if (cram_not_enough_bits(in, nz))
            return -1;
        val = 1;
        while (nz > 0) {
            //val <<= 1; val |= get_bit_MSB(in);
            GET_BIT_MSB(in, val);
            nz--;
        }

        out_i[i] = val - c->u.gamma.offset;
    }

    return 0;
}

void cram_gamma_decode_free(cram_codec *c) {
    if (c)
        free(c);
}

int cram_gamma_describe(cram_codec *c, kstring_t *ks) {
    return ksprintf(ks, "GAMMA(offset=%d)", c->u.subexp.offset)
        < 0 ? -1 : 0;
}

cram_codec *cram_gamma_decode_init(cram_block_compression_hdr *hdr,
                                   char *data, int size,
                                   enum cram_encoding codec,
                                   enum cram_external_type option,
                                   int version, varint_vec *vv) {
    cram_codec *c = NULL;
    char *cp = data;

    if (option != E_INT) {
        hts_log_error("This codec only supports INT encodings");
        return NULL;
    }

    if (size < 1)
        goto malformed;

    if (!(c = malloc(sizeof(*c))))
        return NULL;

    c->codec  = E_GAMMA;
    c->decode = cram_gamma_decode;
    c->free   = cram_gamma_decode_free;
    c->describe = cram_gamma_describe;

    c->u.gamma.offset = vv->varint_get32(&cp, data+size, NULL);

    if (cp - data != size)
        goto malformed;

    return c;

 malformed:
    hts_log_error("Malformed gamma header stream");
    free(c);
    return NULL;
}

/*
 * ---------------------------------------------------------------------------
 * HUFFMAN
 */

static int code_sort(const void *vp1, const void *vp2) {
    const cram_huffman_code *c1 = (const cram_huffman_code *)vp1;
    const cram_huffman_code *c2 = (const cram_huffman_code *)vp2;

    if (c1->len != c2->len)
        return c1->len - c2->len;
    else
        return c1->symbol < c2->symbol ? -1 : (c1->symbol > c2->symbol ? 1 : 0);
}

void cram_huffman_decode_free(cram_codec *c) {
    if (!c)
        return;

    if (c->u.huffman.codes)
        free(c->u.huffman.codes);
    free(c);
}

int cram_huffman_decode_null(cram_slice *slice, cram_codec *c,
                             cram_block *in, char *out, int *out_size) {
    return -1;
}

int cram_huffman_decode_char0(cram_slice *slice, cram_codec *c,
                              cram_block *in, char *out, int *out_size) {
    int i, n;

    if (!out)
        return 0;

    /* Special case of 0 length codes */
    for (i = 0, n = *out_size; i < n; i++) {
        out[i] = c->u.huffman.codes[0].symbol;
    }
    return 0;
}

int cram_huffman_decode_char(cram_slice *slice, cram_codec *c,
                             cram_block *in, char *out, int *out_size) {
    int i, n, ncodes = c->u.huffman.ncodes;
    const cram_huffman_code * const codes = c->u.huffman.codes;

    for (i = 0, n = *out_size; i < n; i++) {
        int idx = 0;
        int val = 0, len = 0, last_len = 0;

        for (;;) {
            int dlen = codes[idx].len - last_len;
            if (cram_not_enough_bits(in, dlen))
                return -1;

            //val <<= dlen;
            //val  |= get_bits_MSB(in, dlen);
            //last_len = (len += dlen);

            last_len = (len += dlen);
            for (; dlen; dlen--) GET_BIT_MSB(in, val);

            idx = val - codes[idx].p;
            if (idx >= ncodes || idx < 0)
                return -1;

            if (codes[idx].code == val && codes[idx].len == len) {
                if (out) out[i] = codes[idx].symbol;
                break;
            }
        }
    }

    return 0;
}

int cram_huffman_decode_int0(cram_slice *slice, cram_codec *c,
                             cram_block *in, char *out, int *out_size) {
    int32_t *out_i = (int32_t *)out;
    int i, n;
    const cram_huffman_code * const codes = c->u.huffman.codes;

    /* Special case of 0 length codes */
    for (i = 0, n = *out_size; i < n; i++) {
        out_i[i] = codes[0].symbol;
    }
    return 0;
}

int cram_huffman_decode_int(cram_slice *slice, cram_codec *c,
                            cram_block *in, char *out, int *out_size) {
    int32_t *out_i = (int32_t *)out;
    int i, n, ncodes = c->u.huffman.ncodes;
    const cram_huffman_code * const codes = c->u.huffman.codes;

    for (i = 0, n = *out_size; i < n; i++) {
        int idx = 0;
        int val = 0, len = 0, last_len = 0;

        // Now one bit at a time for remaining checks
        for (;;) {
            int dlen = codes[idx].len - last_len;
            if (cram_not_enough_bits(in, dlen))
                return -1;

            //val <<= dlen;
            //val  |= get_bits_MSB(in, dlen);
            //last_len = (len += dlen);

            last_len = (len += dlen);
            for (; dlen; dlen--) GET_BIT_MSB(in, val);

            idx = val - codes[idx].p;
            if (idx >= ncodes || idx < 0)
                return -1;

            if (codes[idx].code == val && codes[idx].len == len) {
                out_i[i] = codes[idx].symbol;
                break;
            }
        }
    }

    return 0;
}

int cram_huffman_decode_long0(cram_slice *slice, cram_codec *c,
                              cram_block *in, char *out, int *out_size) {
    int64_t *out_i = (int64_t *)out;
    int i, n;
    const cram_huffman_code * const codes = c->u.huffman.codes;

    /* Special case of 0 length codes */
    for (i = 0, n = *out_size; i < n; i++) {
        out_i[i] = codes[0].symbol;
    }
    return 0;
}

int cram_huffman_decode_long(cram_slice *slice, cram_codec *c,
                             cram_block *in, char *out, int *out_size) {
    int64_t *out_i = (int64_t *)out;
    int i, n, ncodes = c->u.huffman.ncodes;
    const cram_huffman_code * const codes = c->u.huffman.codes;

    for (i = 0, n = *out_size; i < n; i++) {
        int idx = 0;
        int val = 0, len = 0, last_len = 0;

        // Now one bit at a time for remaining checks
        for (;;) {
            int dlen = codes[idx].len - last_len;
            if (cram_not_enough_bits(in, dlen))
                return -1;

            //val <<= dlen;
            //val  |= get_bits_MSB(in, dlen);
            //last_len = (len += dlen);

            last_len = (len += dlen);
            for (; dlen; dlen--) GET_BIT_MSB(in, val);

            idx = val - codes[idx].p;
            if (idx >= ncodes || idx < 0)
                return -1;

            if (codes[idx].code == val && codes[idx].len == len) {
                out_i[i] = codes[idx].symbol;
                break;
            }
        }
    }

    return 0;
}

int cram_huffman_describe(cram_codec *c, kstring_t *ks) {
    int r = 0, n;
    r |= ksprintf(ks, "HUFFMAN(codes={") < 0;
    for (n = 0; n < c->u.huffman.ncodes; n++) {
        r |= ksprintf(ks, "%s%"PRId64, n?",":"",
                      c->u.huffman.codes[n].symbol);
    }
    r |= ksprintf(ks, "},lengths={") < 0;
    for (n = 0; n < c->u.huffman.ncodes; n++) {
        r |= ksprintf(ks, "%s%d", n?",":"",
                      c->u.huffman.codes[n].len);
    }
    r |= ksprintf(ks, "})") < 0;
    return r;
}

/*
 * Initialises a huffman decoder from an encoding data stream.
 */
cram_codec *cram_huffman_decode_init(cram_block_compression_hdr *hdr,
                                     char *data, int size,
                                     enum cram_encoding codec,
                                     enum cram_external_type option,
                                     int version, varint_vec *vv) {
    int32_t ncodes = 0, i, j;
    char *cp = data, *data_end = &data[size];
    cram_codec *h;
    cram_huffman_code *codes = NULL;
    int32_t val, last_len, max_len = 0;
    uint32_t max_val; // needs one more bit than val
    const int max_code_bits = sizeof(val) * 8 - 1;
    int err = 0;

    if (option == E_BYTE_ARRAY_BLOCK) {
        hts_log_error("BYTE_ARRAYs not supported by this codec");
        return NULL;
    }

    ncodes = vv->varint_get32(&cp, data_end, &err);
    if (ncodes < 0) {
        hts_log_error("Invalid number of symbols in huffman stream");
        return NULL;
    }
    if (ncodes >= SIZE_MAX / sizeof(*codes)) {
        errno = ENOMEM;
        return NULL;
    }
#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
    if (ncodes > FUZZ_ALLOC_LIMIT / sizeof(*codes)) {
        errno = ENOMEM;
        return NULL;
    }
#endif
    h = calloc(1, sizeof(*h));
    if (!h)
        return NULL;

    h->codec  = E_HUFFMAN;
    h->free   = cram_huffman_decode_free;

    h->u.huffman.ncodes = ncodes;
    h->u.huffman.option = option;
    if (ncodes) {
        codes = h->u.huffman.codes = malloc(ncodes * sizeof(*codes));
        if (!codes) {
            free(h);
            return NULL;
        }
    } else {
        codes = h->u.huffman.codes = NULL;
    }

    /* Read symbols and bit-lengths */
    if (option == E_LONG) {
        for (i = 0; i < ncodes; i++)
            codes[i].symbol = vv->varint_get64(&cp, data_end, &err);
    } else if (option == E_INT || option == E_BYTE) {
        for (i = 0; i < ncodes; i++)
            codes[i].symbol = vv->varint_get32(&cp, data_end, &err);
    } else {
        goto malformed;
    }

    if (err)
        goto malformed;

    i = vv->varint_get32(&cp, data_end, &err);
    if (i != ncodes)
        goto malformed;

    if (ncodes == 0) {
        /* NULL huffman stream.  Ensure it returns an error if
           anything tries to use it. */
        h->decode = cram_huffman_decode_null;
        return h;
    }

    for (i = 0; i < ncodes; i++) {
        codes[i].len = vv->varint_get32(&cp, data_end, &err);
        if (err)
            break;
        if (codes[i].len < 0) {
            hts_log_error("Huffman code length (%d) is negative", codes[i].len);
            goto malformed;
        }
        if (max_len < codes[i].len)
            max_len = codes[i].len;
    }
    if (err || cp - data != size || max_len >= ncodes)
        goto malformed;

    /* 31 is max. bits available in val */
    if (max_len > max_code_bits) {
        hts_log_error("Huffman code length (%d) is greater "
                      "than maximum supported (%d)", max_len, max_code_bits);
        goto malformed;
    }

    /* Sort by bit length and then by symbol value */
    qsort(codes, ncodes, sizeof(*codes), code_sort);

    /* Assign canonical codes */
    val = -1, last_len = 0, max_val = 0;
    for (i = 0; i < ncodes; i++) {
        val++;
        if (val > max_val)
            goto malformed;

        if (codes[i].len > last_len) {
            val <<= (codes[i].len - last_len);
            last_len = codes[i].len;
            max_val = (1U << codes[i].len) - 1;
        }
        codes[i].code = val;
    }

    /*
     * Compute the next starting point, offset by the i'th value.
     * For example if codes 10, 11, 12, 13 are 30, 31, 32, 33 then
     * codes[10..13].p = 30 - 10.
     */
    last_len = 0;
    for (i = j = 0; i < ncodes; i++) {
        if (codes[i].len > last_len) {
            j = codes[i].code - i;
            last_len = codes[i].len;
        }
        codes[i].p = j;
    }

    // puts("==HUFF LEN==");
    // for (i = 0; i <= last_len+1; i++) {
    //     printf("len %d=%d prefix %d\n", i, h->u.huffman.lengths[i], h->u.huffman.prefix[i]);
    // }
    // puts("===HUFFMAN CODES===");
    // for (i = 0; i < ncodes; i++) {
    //     int j;
    //     printf("%d: %d %d %d ", i, codes[i].symbol, codes[i].len, codes[i].code);
    //     j = codes[i].len;
    //     while (j) {
    //         putchar(codes[i].code & (1 << --j) ? '1' : '0');
    //     }
    //     printf(" %d\n", codes[i].code);
    // }

    if (option == E_BYTE || option == E_BYTE_ARRAY) {
        if (h->u.huffman.codes[0].len == 0)
            h->decode = cram_huffman_decode_char0;
        else
            h->decode = cram_huffman_decode_char;
    } else if (option == E_LONG) {
        if (h->u.huffman.codes[0].len == 0)
            h->decode = cram_huffman_decode_long0;
        else
            h->decode = cram_huffman_decode_long;
    } else if (option == E_INT || option == E_BYTE) {
        if (h->u.huffman.codes[0].len == 0)
            h->decode = cram_huffman_decode_int0;
        else
            h->decode = cram_huffman_decode_int;
    } else {
        return NULL;
    }
    h->describe = cram_huffman_describe;

    return (cram_codec *)h;

 malformed:
    hts_log_error("Malformed huffman header stream");
    free(codes);
    free(h);
    return NULL;
}

int cram_huffman_encode_char0(cram_slice *slice, cram_codec *c,
                              char *in, int in_size) {
    return 0;
}

int cram_huffman_encode_char(cram_slice *slice, cram_codec *c,
                             char *in, int in_size) {
    int i, code, len, r = 0;
    unsigned char *syms = (unsigned char *)in;

    while (in_size--) {
        int sym = *syms++;
        if (sym >= -1 && sym < MAX_HUFF) {
            i = c->u.e_huffman.val2code[sym+1];
            assert(c->u.e_huffman.codes[i].symbol == sym);
            code = c->u.e_huffman.codes[i].code;
            len  = c->u.e_huffman.codes[i].len;
        } else {
            /* Slow - use a lookup table for when sym < MAX_HUFF? */
            for (i = 0; i < c->u.e_huffman.nvals; i++) {
                if (c->u.e_huffman.codes[i].symbol == sym)
                    break;
            }
            if (i == c->u.e_huffman.nvals)
                return -1;

            code = c->u.e_huffman.codes[i].code;
            len  = c->u.e_huffman.codes[i].len;
        }

        r |= store_bits_MSB(c->out, code, len);
    }

    return r;
}

int cram_huffman_encode_int0(cram_slice *slice, cram_codec *c,
                             char *in, int in_size) {
    return 0;
}

int cram_huffman_encode_int(cram_slice *slice, cram_codec *c,
                            char *in, int in_size) {
    int i, code, len, r = 0;
    int *syms = (int *)in;

    while (in_size--) {
        int sym = *syms++;

        if (sym >= -1 && sym < MAX_HUFF) {
            i = c->u.e_huffman.val2code[sym+1];
            assert(c->u.e_huffman.codes[i].symbol == sym);
            code = c->u.e_huffman.codes[i].code;
            len  = c->u.e_huffman.codes[i].len;
        } else {
            /* Slow - use a lookup table for when sym < MAX_HUFFMAN_SYM? */
            for (i = 0; i < c->u.e_huffman.nvals; i++) {
                if (c->u.e_huffman.codes[i].symbol == sym)
                    break;
            }
            if (i == c->u.e_huffman.nvals)
                return -1;

            code = c->u.e_huffman.codes[i].code;
            len  = c->u.e_huffman.codes[i].len;
        }

        r |= store_bits_MSB(c->out, code, len);
    }

    return r;
}

int cram_huffman_encode_long0(cram_slice *slice, cram_codec *c,
                              char *in, int in_size) {
    return 0;
}

int cram_huffman_encode_long(cram_slice *slice, cram_codec *c,
                             char *in, int in_size) {
    int i, code, len, r = 0;
    int64_t *syms = (int64_t *)in;

    while (in_size--) {
        int sym = *syms++;

        if (sym >= -1 && sym < MAX_HUFF) {
            i = c->u.e_huffman.val2code[sym+1];
            assert(c->u.e_huffman.codes[i].symbol == sym);
            code = c->u.e_huffman.codes[i].code;
            len  = c->u.e_huffman.codes[i].len;
        } else {
            /* Slow - use a lookup table for when sym < MAX_HUFFMAN_SYM? */
            for (i = 0; i < c->u.e_huffman.nvals; i++) {
                if (c->u.e_huffman.codes[i].symbol == sym)
                    break;
            }
            if (i == c->u.e_huffman.nvals)
                return -1;

            code = c->u.e_huffman.codes[i].code;
            len  = c->u.e_huffman.codes[i].len;
        }

        r |= store_bits_MSB(c->out, code, len);
    }

    return r;
}

void cram_huffman_encode_free(cram_codec *c) {
    if (!c)
        return;

    if (c->u.e_huffman.codes)
        free(c->u.e_huffman.codes);
    free(c);
}

/*
 * Encodes a huffman tree.
 * Returns number of bytes written.
 */
int cram_huffman_encode_store(cram_codec *c, cram_block *b, char *prefix,
                              int version) {
    int i, len = 0, r = 0, n;
    cram_huffman_code *codes = c->u.e_huffman.codes;
    /*
     * Up to code length 127 means 2.5e+26 bytes of data required (worst
     * case huffman tree needs symbols with freqs matching the Fibonacci
     * series). So guaranteed 1 byte per code.
     *
     * Symbols themselves could be 5 bytes (eg -1 is 5 bytes in itf8).
     *
     * Therefore 6*ncodes + 5 + 5 + 1 + 5 is max memory
     */
    char *tmp = hts_malloc_pse(6, c->u.e_huffman.nvals, 0, 16);
    char *tp = tmp, *tpend = tmp+6*c->u.e_huffman.nvals+16;

    if (!tmp)
        return -1;

    if (prefix) {
        size_t l = strlen(prefix);
        BLOCK_APPEND(b, prefix, l);
        len += l;
    }

    tp += c->vv->varint_put32(tp, tpend, c->u.e_huffman.nvals);
    if (c->u.e_huffman.option == E_LONG) {
        for (i = 0; i < c->u.e_huffman.nvals; i++) {
            tp += c->vv->varint_put64(tp, tpend, codes[i].symbol);
        }
    } else if (c->u.e_huffman.option == E_INT || c->u.e_huffman.option == E_BYTE) {
        for (i = 0; i < c->u.e_huffman.nvals; i++) {
            tp += c->vv->varint_put32(tp, tpend, codes[i].symbol);
        }
    } else {
        return -1;
    }

    tp += c->vv->varint_put32(tp, tpend, c->u.e_huffman.nvals);
    for (i = 0; i < c->u.e_huffman.nvals; i++)
        tp += c->vv->varint_put32(tp, tpend, codes[i].len);

    len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
    len += (n = c->vv->varint_put32_blk(b, tp-tmp));   r |= n;
    BLOCK_APPEND(b, tmp, tp-tmp);
    len += tp-tmp;

    free(tmp);

    if (r > 0)
        return len;

 block_err:
    return -1;
}

cram_codec *cram_huffman_encode_init(cram_stats *st,
                                     enum cram_encoding codec,
                                     enum cram_external_type option,
                                     void *dat,
                                     int version, varint_vec *vv) {
    int *vals = NULL, *freqs = NULL, *lens = NULL, code, len;
    int *new_vals, *new_freqs;
    int i, max_val = 0, min_val = INT_MAX, k;
    size_t nvals, vals_alloc = 0;
    cram_codec *c;
    cram_huffman_code *codes;

    c = malloc(sizeof(*c));
    if (!c)
        return NULL;
    c->codec = E_HUFFMAN;

    /* Count number of unique symbols */
    for (nvals = i = 0; i < MAX_STAT_VAL; i++) {
        if (!st->freqs[i])
            continue;
        if (nvals >= vals_alloc) {
            vals_alloc = vals_alloc ? vals_alloc*2 : 1024;
            new_vals  = hts_realloc_p(vals, sizeof(*vals), vals_alloc);
            if (!new_vals) goto nomem;
            vals = new_vals;
            new_freqs = hts_realloc_p(freqs, sizeof(*freqs), vals_alloc);
            if (!new_freqs) goto nomem;
            freqs = new_freqs;
        }
        vals[nvals] = i;
        freqs[nvals] = st->freqs[i];
        assert(st->freqs[i] > 0);
        if (max_val < i) max_val = i;
        if (min_val > i) min_val = i;
        nvals++;
    }
    if (st->h) {
        khint_t k;

        for (k = kh_begin(st->h); k != kh_end(st->h); k++) {
            if (!kh_exist(st->h, k))
                continue;
            if (nvals >= vals_alloc) {
                vals_alloc = vals_alloc ? vals_alloc*2 : 1024;
                new_vals  = hts_realloc_p(vals, sizeof(*vals), vals_alloc);
                if (!new_vals) goto nomem;
                vals = new_vals;
                new_freqs = hts_realloc_p(freqs, sizeof(*freqs), vals_alloc);
                if (!new_freqs) goto nomem;
                freqs = new_freqs;
            }
            vals[nvals]= kh_key(st->h, k);
            freqs[nvals] = kh_val(st->h, k);
            assert(freqs[nvals] > 0);
            if (max_val < i) max_val = i;
            if (min_val > i) min_val = i;
            nvals++;
        }
    }

    assert(nvals > 0);

    new_freqs = hts_realloc_p(freqs, 2 * sizeof(*freqs), nvals);
    if (!new_freqs) goto nomem;
    freqs = new_freqs;
    lens = calloc(nvals, 2 * sizeof(*lens));
    if (!lens) goto nomem;

    /* Inefficient, use pointers to form chain so we can insert and maintain
     * a sorted list? This is currently O(nvals^2) complexity.
     */
    for (;;) {
        int low1 = INT_MAX, low2 = INT_MAX;
        int ind1 = 0, ind2 = 0;
        for (i = 0; i < nvals; i++) {
            if (freqs[i] < 0)
                continue;
            if (low1 > freqs[i])
                low2 = low1, ind2 = ind1, low1 = freqs[i], ind1 = i;
            else if (low2 > freqs[i])
                low2 = freqs[i], ind2 = i;
        }
        if (low2 == INT_MAX)
            break;

        freqs[nvals] = low1 + low2;
        lens[ind1] = nvals;
        lens[ind2] = nvals;
        freqs[ind1] *= -1;
        freqs[ind2] *= -1;
        nvals++;
    }
    nvals = nvals/2+1;

    /* Assign lengths */
    for (i = 0; i < nvals; i++) {
        int code_len = 0;
        for (k = lens[i]; k; k = lens[k])
            code_len++;
        lens[i] = code_len;
        freqs[i] *= -1;
        //fprintf(stderr, "%d / %d => %d\n", vals[i], freqs[i], lens[i]);
    }


    /* Sort, need in a struct */
    if (!(codes = hts_malloc_p(sizeof(*codes), nvals)))
        goto nomem;
    for (i = 0; i < nvals; i++) {
        codes[i].symbol = vals[i];
        codes[i].len = lens[i];
    }
    qsort(codes, nvals, sizeof(*codes), code_sort);

    /*
     * Generate canonical codes from lengths.
     * Sort by length.
     * Start with 0.
     * Every new code of same length is +1.
     * Every new code of new length is +1 then <<1 per extra length.
     *
     * /\
     * a/\
     * /\/\
     * bcd/\
     *    ef
     *
     * a 1  0
     * b 3  4 (0+1)<<2
     * c 3  5
     * d 3  6
     * e 4  14  (6+1)<<1
     * f 5  15
     */
    code = 0; len = codes[0].len;
    for (i = 0; i < nvals; i++) {
        while (len != codes[i].len) {
            code<<=1;
            len++;
        }
        codes[i].code = code++;

        if (codes[i].symbol >= -1 && codes[i].symbol < MAX_HUFF)
            c->u.e_huffman.val2code[codes[i].symbol+1] = i;

        //fprintf(stderr, "sym %d, code %d, len %d\n",
        //      codes[i].symbol, codes[i].code, codes[i].len);
    }

    free(lens);
    free(vals);
    free(freqs);

    c->u.e_huffman.codes = codes;
    c->u.e_huffman.nvals = nvals;
    c->u.e_huffman.option = option;

    c->free = cram_huffman_encode_free;
    if (option == E_BYTE || option == E_BYTE_ARRAY) {
        if (c->u.e_huffman.codes[0].len == 0)
            c->encode = cram_huffman_encode_char0;
        else
            c->encode = cram_huffman_encode_char;
    } else if (option == E_INT) {
        if (c->u.e_huffman.codes[0].len == 0)
            c->encode = cram_huffman_encode_int0;
        else
            c->encode = cram_huffman_encode_int;
    } else if (option == E_LONG) {
        if (c->u.e_huffman.codes[0].len == 0)
            c->encode = cram_huffman_encode_long0;
        else
            c->encode = cram_huffman_encode_long;
    } else {
        return NULL;
    }
    c->store = cram_huffman_encode_store;
    c->flush = NULL;

    return c;

 nomem:
    hts_log_error("Out of memory");
    free(vals);
    free(freqs);
    free(lens);
    free(c);
    return NULL;
}

/*
 * ---------------------------------------------------------------------------
 * BYTE_ARRAY_LEN
 */
int cram_byte_array_len_decode(cram_slice *slice, cram_codec *c,
                               cram_block *in, char *out,
                               int *out_size) {
    /* Fetch length */
    int32_t len = 0, one = 1;
    int r;

    cram_codec *len_codec = c->u.byte_array_len.len_codec;
    cram_codec *val_codec = c->u.byte_array_len.val_codec;

    r = len_codec->decode(slice, len_codec, in, (char *)&len, &one);
    if (len < 0 || (len > *out_size &&
                    !(val_codec->codec == E_EXTERNAL &&
                      val_codec->u.external.type == E_BYTE_ARRAY_BLOCK))) {
        fprintf(stderr, "Error: overflow in cram_byte_array_len_decode.\n");
        return -1;
    }

    if (!r && val_codec) {
        r = val_codec->decode(slice, val_codec, in, out, &len);
    } else {
        return -1;
    }

    *out_size = len;

    return r;
}

void cram_byte_array_len_decode_free(cram_codec *c) {
    if (!c) return;

    if (c->u.byte_array_len.len_codec)
        c->u.byte_array_len.len_codec->free(c->u.byte_array_len.len_codec);

    if (c->u.byte_array_len.val_codec)
        c->u.byte_array_len.val_codec->free(c->u.byte_array_len.val_codec);

    free(c);
}

int cram_byte_array_len_describe(cram_codec *c, kstring_t *ks) {
    int r = 0;
    r |= ksprintf(ks, "BYTE_ARRAY_LEN(len_codec={") < 0;
    cram_byte_array_len_decoder *l = &c->u.byte_array_len;
    r |=  l->len_codec->describe
        ? l->len_codec->describe(l->len_codec, ks)
        : (ksprintf(ks, "?")<0);
    r |= ksprintf(ks, "},val_codec={") < 0;
    r |=  l->val_codec->describe
        ? l->val_codec->describe(l->val_codec, ks)
        : (ksprintf(ks, "?")<0);
    r |= ksprintf(ks, "}") < 0;

    return r;
}

cram_codec *cram_byte_array_len_decode_init(cram_block_compression_hdr *hdr,
                                            char *data, int size,
                                            enum cram_encoding codec,
                                            enum cram_external_type option,
                                            int version, varint_vec *vv) {
    cram_codec *c;
    char *cp   = data;
    char *endp = data + size;

    if (!(c = malloc(sizeof(*c))))
        return NULL;

    c->codec  = E_BYTE_ARRAY_LEN;
    c->decode = cram_byte_array_len_decode;
    c->free   = cram_byte_array_len_decode_free;
    c->describe = cram_byte_array_len_describe;
    c->u.byte_array_len.len_codec = NULL;
    c->u.byte_array_len.val_codec = NULL;

    int encoding = vv->varint_get32(&cp, endp, NULL);
    int sub_size = vv->varint_get32(&cp, endp, NULL);
    if (sub_size < 0 || endp - cp < sub_size)
        goto malformed;
    c->u.byte_array_len.len_codec = cram_decoder_init(hdr, encoding, cp, sub_size,
                                                      E_INT, version, vv);
    if (c->u.byte_array_len.len_codec == NULL)
        goto no_codec;
    cp += sub_size;

    encoding = vv->varint_get32(&cp, endp, NULL);
    sub_size = vv->varint_get32(&cp, endp, NULL);
    if (sub_size < 0 || endp - cp < sub_size)
        goto malformed;
    c->u.byte_array_len.val_codec = cram_decoder_init(hdr, encoding, cp, sub_size,
                                                      option, version, vv);
    if (c->u.byte_array_len.val_codec == NULL)
        goto no_codec;
    cp += sub_size;

    if (cp - data != size)
        goto malformed;

    return c;

 malformed:
    hts_log_error("Malformed byte_array_len header stream");
 no_codec:
    cram_byte_array_len_decode_free(c);
    return NULL;
}

int cram_byte_array_len_encode(cram_slice *slice, cram_codec *c,
                               char *in, int in_size) {
    int32_t i32 = in_size;
    int r = 0;

    r |= c->u.e_byte_array_len.len_codec->encode(slice,
                                                 c->u.e_byte_array_len.len_codec,
                                                 (char *)&i32, 1);
    r |= c->u.e_byte_array_len.val_codec->encode(slice,
                                                 c->u.e_byte_array_len.val_codec,
                                                 in, in_size);
    return r;
}

void cram_byte_array_len_encode_free(cram_codec *c) {
    if (!c)
        return;

    if (c->u.e_byte_array_len.len_codec)
        c->u.e_byte_array_len.len_codec->free(c->u.e_byte_array_len.len_codec);

    if (c->u.e_byte_array_len.val_codec)
        c->u.e_byte_array_len.val_codec->free(c->u.e_byte_array_len.val_codec);

    free(c);
}

int cram_byte_array_len_encode_store(cram_codec *c, cram_block *b,
                                     char *prefix, int version) {
    int len = 0, len2, len3, r = 0, n;
    cram_codec *tc;
    cram_block *b_len = NULL, *b_val = NULL;

    if (prefix) {
        size_t l = strlen(prefix);
        BLOCK_APPEND(b, prefix, l);
        len += l;
    }

    tc = c->u.e_byte_array_len.len_codec;
    b_len = cram_new_block(0, 0);
    if (!b_len) goto block_err;
    len2 = tc->store(tc, b_len, NULL, version);
    if (len2 < 0) goto block_err;

    tc = c->u.e_byte_array_len.val_codec;
    b_val = cram_new_block(0, 0);
    if (!b_val) goto block_err;
    len3 = tc->store(tc, b_val, NULL, version);
    if (len3 < 0) goto block_err;

    len += (n = c->vv->varint_put32_blk(b, c->codec));  r |= n;
    len += (n = c->vv->varint_put32_blk(b, len2+len3)); r |= n;
    BLOCK_APPEND(b, BLOCK_DATA(b_len), BLOCK_SIZE(b_len));
    BLOCK_APPEND(b, BLOCK_DATA(b_val), BLOCK_SIZE(b_val));

    cram_free_block(b_len);
    cram_free_block(b_val);

    if (r > 0)
        return len + len2 + len3;

 block_err:
    if (b_len) cram_free_block(b_len);
    if (b_val) cram_free_block(b_val);
    return -1;
}

cram_codec *cram_byte_array_len_encode_init(cram_stats *st,
                                            enum cram_encoding codec,
                                            enum cram_external_type option,
                                            void *dat,
                                            int version, varint_vec *vv) {
    cram_codec *c;
    cram_byte_array_len_encoder *e = (cram_byte_array_len_encoder *)dat;

    c = malloc(sizeof(*c));
    if (!c)
        return NULL;
    c->codec = E_BYTE_ARRAY_LEN;
    c->free = cram_byte_array_len_encode_free;
    c->encode = cram_byte_array_len_encode;
    c->store = cram_byte_array_len_encode_store;
    c->flush = NULL;

    c->u.e_byte_array_len.len_codec = cram_encoder_init(e->len_encoding,
                                                        st, E_INT,
                                                        e->len_dat,
                                                        version, vv);
    c->u.e_byte_array_len.val_codec = cram_encoder_init(e->val_encoding,
                                                        NULL, E_BYTE_ARRAY,
                                                        e->val_dat,
                                                        version, vv);

    if (!c->u.e_byte_array_len.len_codec ||
        !c->u.e_byte_array_len.val_codec) {
        cram_byte_array_len_encode_free(c);
        return NULL;
    }

    return c;
}

/*
 * ---------------------------------------------------------------------------
 * BYTE_ARRAY_STOP
 */
static int cram_byte_array_stop_decode_char(cram_slice *slice, cram_codec *c,
                                            cram_block *in, char *out,
                                            int *out_size) {
    uint8_t *cp;
    cram_block *b = NULL;

    b = cram_get_block_by_id(slice, c->u.byte_array_stop.content_id);
    if (!b)
        return *out_size?-1:0;

    if (b->idx >= b->uncomp_size)
        return -1;

    ssize_t term = b->uncomp_size - b->idx;
    cp = b->data + b->idx;
    if (out) {
       // memccpy equivalent but without copying the terminating byte
        if (term > *out_size)
            term = *out_size;
        while (--term >= 0 && *cp != c->u.byte_array_stop.stop) {
            *out++ = *cp++;
        }

    } else {
        // Consume input, but produce no output
        while (--term >= 0 && *cp != c->u.byte_array_stop.stop) {
            cp++;
        }
    }

    // Attempted overrun on input or output
    if (cp >= b->data + b->uncomp_size || *cp != c->u.byte_array_stop.stop)
        return -1;

    *out_size = cp - (b->data + b->idx);
    b->idx = cp - b->data + 1;

    return 0;
}

int cram_byte_array_stop_decode_block(cram_slice *slice, cram_codec *c,
                                      cram_block *in, char *out_,
                                      int *out_size) {
    cram_block *b;
    cram_block *out = (cram_block *)out_;
    unsigned char *cp, *cp_end;
    unsigned char stop;

    b = cram_get_block_by_id(slice, c->u.byte_array_stop.content_id);
    if (!b)
        return *out_size?-1:0;

    if (b->idx >= b->uncomp_size)
        return -1;
    cp = b->data + b->idx;
    cp_end = b->data + b->uncomp_size;

    // STOP byte is hard-coded as zero by our name tokeniser decoder
    // implementation, so we may ignore what was requested.
    stop = b->orig_method == TOK3 ? 0 : c->u.byte_array_stop.stop;

    if (cp_end - cp < out->alloc - out->byte) {
        unsigned char *out_cp = BLOCK_END(out);
        while (cp != cp_end && *cp != stop)
            *out_cp++ = *cp++;
        BLOCK_SIZE(out) = out_cp - BLOCK_DATA(out);
    } else {
        unsigned char *cp_start;
        for (cp_start = cp; cp != cp_end && *cp != stop; cp++)
            ;
        BLOCK_APPEND(out, cp_start, cp - cp_start);
        BLOCK_GROW(out, cp - cp_start);
    }

    *out_size = cp - (b->data + b->idx);
    b->idx = cp - b->data + 1;

    return 0;

 block_err:
    return -1;
}

void cram_byte_array_stop_decode_free(cram_codec *c) {
    if (!c) return;

    free(c);
}

int cram_byte_array_stop_describe(cram_codec *c, kstring_t *ks) {
    return ksprintf(ks, "BYTE_ARRAY_STOP(stop=%d,id=%d)",
                    c->u.byte_array_stop.stop,
                    c->u.byte_array_stop.content_id)
        < 0 ? -1 : 0;
}

cram_codec *cram_byte_array_stop_decode_init(cram_block_compression_hdr *hdr,
                                             char *data, int size,
                                             enum cram_encoding codec,
                                             enum cram_external_type option,
                                             int version, varint_vec *vv) {
    cram_codec *c = NULL;
    unsigned char *cp = (unsigned char *)data;
    int err = 0;

    if (size < (CRAM_MAJOR_VERS(version) == 1 ? 5 : 2))
        goto malformed;

    if (!(c = malloc(sizeof(*c))))
        return NULL;

    c->codec  = E_BYTE_ARRAY_STOP;
    switch (option) {
    case E_BYTE_ARRAY_BLOCK:
        c->decode = cram_byte_array_stop_decode_block;
        break;
    case E_BYTE_ARRAY:
        c->decode = cram_byte_array_stop_decode_char;
        break;
    default:
        hts_log_error("The byte_array_stop codec only supports BYTE_ARRAYs");
        free(c);
        return NULL;
    }
    c->free   = cram_byte_array_stop_decode_free;
    c->describe = cram_byte_array_stop_describe;

    c->u.byte_array_stop.stop = *cp++;
    if (CRAM_MAJOR_VERS(version) == 1) {
        c->u.byte_array_stop.content_id = cp[0] + (cp[1]<<8) + (cp[2]<<16)
            + ((unsigned int) cp[3]<<24);
        cp += 4;
    } else {
        c->u.byte_array_stop.content_id = vv->varint_get32((char **)&cp, data+size, &err);
    }

    if ((char *)cp - data != size || err)
        goto malformed;

    return c;

 malformed:
    hts_log_error("Malformed byte_array_stop header stream");
    free(c);
    return NULL;
}

int cram_byte_array_stop_encode(cram_slice *slice, cram_codec *c,
                                char *in, int in_size) {
    BLOCK_APPEND(c->out, in, in_size);
    BLOCK_APPEND_CHAR(c->out, c->u.e_byte_array_stop.stop);
    return 0;

 block_err:
    return -1;
}

void cram_byte_array_stop_encode_free(cram_codec *c) {
    if (!c)
        return;
    free(c);
}

int cram_byte_array_stop_encode_store(cram_codec *c, cram_block *b,
                                      char *prefix, int version) {
    int len = 0;
    char buf[20], *cp = buf;

    if (prefix) {
        size_t l = strlen(prefix);
        BLOCK_APPEND(b, prefix, l);
        len += l;
    }

    cp += c->vv->varint_put32(cp, buf+20, c->codec);

    if (CRAM_MAJOR_VERS(version) == 1) {
        cp += c->vv->varint_put32(cp, buf+20, 5);
        *cp++ = c->u.e_byte_array_stop.stop;
        *cp++ = (c->u.e_byte_array_stop.content_id >>  0) & 0xff;
        *cp++ = (c->u.e_byte_array_stop.content_id >>  8) & 0xff;
        *cp++ = (c->u.e_byte_array_stop.content_id >> 16) & 0xff;
        *cp++ = (c->u.e_byte_array_stop.content_id >> 24) & 0xff;
    } else {
        cp += c->vv->varint_put32(cp, buf+20, 1 +
                                  c->vv->varint_size(c->u.e_byte_array_stop.content_id));
        *cp++ = c->u.e_byte_array_stop.stop;
        cp += c->vv->varint_put32(cp, buf+20, c->u.e_byte_array_stop.content_id);
    }

    BLOCK_APPEND(b, buf, cp-buf);
    len += cp-buf;

    return len;

 block_err:
    return -1;
}

cram_codec *cram_byte_array_stop_encode_init(cram_stats *st,
                                             enum cram_encoding codec,
                                             enum cram_external_type option,
                                             void *dat,
                                             int version, varint_vec *vv) {
    cram_codec *c;

    c = malloc(sizeof(*c));
    if (!c)
        return NULL;
    c->codec = E_BYTE_ARRAY_STOP;
    c->free = cram_byte_array_stop_encode_free;
    c->encode = cram_byte_array_stop_encode;
    c->store = cram_byte_array_stop_encode_store;
    c->flush = NULL;

    c->u.e_byte_array_stop.stop = ((int *)dat)[0];
    c->u.e_byte_array_stop.content_id = ((int *)dat)[1];

    return c;
}

/*
 * ---------------------------------------------------------------------------
 */

const char *cram_encoding2str(enum cram_encoding t) {
    switch (t) {
    case E_NULL:            return "NULL";
    case E_EXTERNAL:        return "EXTERNAL";
    case E_GOLOMB:          return "GOLOMB";
    case E_HUFFMAN:         return "HUFFMAN";
    case E_BYTE_ARRAY_LEN:  return "BYTE_ARRAY_LEN";
    case E_BYTE_ARRAY_STOP: return "BYTE_ARRAY_STOP";
    case E_BETA:            return "BETA";
    case E_SUBEXP:          return "SUBEXP";
    case E_GOLOMB_RICE:     return "GOLOMB_RICE";
    case E_GAMMA:           return "GAMMA";

    case E_NUM_CODECS:
    default:                return "?";
    }
}

static cram_codec *(*decode_init[E_NUM_CODECS])(cram_block_compression_hdr *hdr,
                                                char *data,
                                                int size,
                                                enum cram_encoding codec,
                                                enum cram_external_type option,
                                                int version, varint_vec *vv) = {
    // CRAM 3.0 valid codecs
    NULL, // null codec
    cram_external_decode_init,
    NULL, // golomb
    cram_huffman_decode_init,
    cram_byte_array_len_decode_init,
    cram_byte_array_stop_decode_init,
    cram_beta_decode_init,
    cram_subexp_decode_init,
    NULL, // golomb rice
    cram_gamma_decode_init,
};

cram_codec *cram_decoder_init(cram_block_compression_hdr *hdr,
                              enum cram_encoding codec,
                              char *data, int size,
                              enum cram_external_type option,
                              int version, varint_vec *vv) {
    if (codec >= E_NULL && codec < E_NUM_CODECS && decode_init[codec]) {
        cram_codec *r = decode_init[codec](hdr, data, size, codec,
                                           option, version, vv);
        if (r) {
            r->vv = vv;
            r->codec_id = hdr->ncodecs++;
        }
        return r;
    } else {
        hts_log_error("Unimplemented codec of type %s", cram_encoding2str(codec));
        return NULL;
    }
}

static cram_codec *(*encode_init[E_NUM_CODECS])(cram_stats *stx,
                                                enum cram_encoding codec,
                                                enum cram_external_type option,
                                                void *opt,
                                                int version, varint_vec *vv) = {
    // CRAM 3.0 valid codecs
    NULL, // null codec
    cram_external_encode_init, // int/bytes in cram 3, byte only in cram 4
    NULL, // golomb
    cram_huffman_encode_init,
    cram_byte_array_len_encode_init,
    cram_byte_array_stop_encode_init,
    cram_beta_encode_init,
    NULL, // subexponential (we support decode only)
    NULL, // golomb rice
    NULL, // gamma (we support decode only)
};

cram_codec *cram_encoder_init(enum cram_encoding codec,
                              cram_stats *st,
                              enum cram_external_type option,
                              void *dat,
                              int version, varint_vec *vv) {
    if (st && !st->nvals)
        return NULL;

    if (encode_init[codec]) {
        cram_codec *r;
        if ((r = encode_init[codec](st, codec, option, dat, version, vv)))
            r->out = NULL;
        if (!r) {
            hts_log_error("Unable to initialise codec of type %s", cram_encoding2str(codec));
            return NULL;
        }
        r->vv = vv;
        return r;
    } else {
        hts_log_error("Unimplemented codec of type %s", cram_encoding2str(codec));
        abort();
    }
}

/*
 * Returns the content_id used by this codec, also in id2 if byte_array_len.
 * Returns -1 for the CORE block and -2 for unneeded.
 * id2 is only filled out for BYTE_ARRAY_LEN which uses 2 codecs.
 */
int cram_codec_to_id(cram_codec *c, int *id2) {
    int bnum1, bnum2 = -2;

    switch (c->codec) {
    case E_HUFFMAN:
        bnum1 = c->u.huffman.ncodes == 1 ? -2 : -1;
        break;

    case E_GOLOMB:
    case E_BETA:
    case E_SUBEXP:
    case E_GOLOMB_RICE:
    case E_GAMMA:
        // CORE block
        bnum1 = -1;
        break;

    case E_EXTERNAL:
        bnum1 = c->u.external.content_id;
        break;

    case E_BYTE_ARRAY_LEN:
        bnum1 = cram_codec_to_id(c->u.byte_array_len.len_codec, NULL);
        bnum2 = cram_codec_to_id(c->u.byte_array_len.val_codec, NULL);
        break;

    case E_BYTE_ARRAY_STOP:
        bnum1 = c->u.byte_array_stop.content_id;
        break;

    case E_NULL:
        bnum1 = -2;
        break;

    default:
        hts_log_error("Unknown codec type %d", c->codec);
        bnum1 = -1;
    }

    if (id2)
        *id2 = bnum2;
    return bnum1;
}


/*
 * cram_codec structures are specialised for decoding or encoding.
 * Unfortunately this makes turning a decoder into an encoder (such as
 * when transcoding files) problematic.
 *
 * This function converts a cram decoder codec into an encoder version
 * in-place (ie it modifiers the codec itself).
 *
 * Returns 0 on success;
 *        -1 on failure.
 */
int cram_codec_decoder2encoder(cram_fd *fd, cram_codec *c) {
    int j;

    switch (c->codec) {
    case E_EXTERNAL:
        // shares struct with decode
        c->free = cram_external_encode_free;
        c->store = cram_external_encode_store;
        if (c->decode == cram_external_decode_int)
            c->encode = cram_external_encode_int;
        else if (c->decode == cram_external_decode_long)
            c->encode = cram_external_encode_long;
        else if (c->decode == cram_external_decode_char)
            c->encode = cram_external_encode_char;
        else if (c->decode == cram_external_decode_block)
            c->encode = cram_external_encode_char;
        else
            return -1;
        break;

    case E_HUFFMAN: {
        // New structure, so switch.
        // FIXME: we huffman and e_huffman structs amended, we could
        // unify this.
        cram_codec *t = malloc(sizeof(*t));
        if (!t) return -1;
        t->vv     = c->vv;
        t->codec = E_HUFFMAN;
        t->free = cram_huffman_encode_free;
        t->store = cram_huffman_encode_store;
        t->u.e_huffman.codes = c->u.huffman.codes;
        t->u.e_huffman.nvals = c->u.huffman.ncodes;
        t->u.e_huffman.option = c->u.huffman.option;
        for (j = 0; j < t->u.e_huffman.nvals; j++) {
            int32_t sym = t->u.e_huffman.codes[j].symbol;
            if (sym >= -1 && sym < MAX_HUFF)
                t->u.e_huffman.val2code[sym+1] = j;
        }

        if (c->decode == cram_huffman_decode_char0)
            t->encode = cram_huffman_encode_char0;
        else if (c->decode == cram_huffman_decode_char)
            t->encode = cram_huffman_encode_char;
        else if (c->decode == cram_huffman_decode_int0)
            t->encode = cram_huffman_encode_int0;
        else if (c->decode == cram_huffman_decode_int)
            t->encode = cram_huffman_encode_int;
        else if (c->decode == cram_huffman_decode_long0)
            t->encode = cram_huffman_encode_long0;
        else if (c->decode == cram_huffman_decode_long)
            t->encode = cram_huffman_encode_long;
        else {
            free(t);
            return -1;
        }
        *c = *t;
        free(t);
        break;
    }

    case E_BETA:
        // shares struct with decode
        c->free = cram_beta_encode_free;
        c->store = cram_beta_encode_store;
        if (c->decode == cram_beta_decode_int)
            c->encode = cram_beta_encode_int;
        else if (c->decode == cram_beta_decode_long)
            c->encode = cram_beta_encode_long;
        else if (c->decode == cram_beta_decode_char)
            c->encode = cram_beta_encode_char;
        else
            return -1;
        break;

    case E_BYTE_ARRAY_LEN: {
        cram_codec *t = malloc(sizeof(*t));
        if (!t) return -1;
        t->vv     = c->vv;
        t->codec  = E_BYTE_ARRAY_LEN;
        t->free   = cram_byte_array_len_encode_free;
        t->store  = cram_byte_array_len_encode_store;
        t->encode = cram_byte_array_len_encode;
        t->u.e_byte_array_len.len_codec = c->u.byte_array_len.len_codec;
        t->u.e_byte_array_len.val_codec = c->u.byte_array_len.val_codec;
        if (cram_codec_decoder2encoder(fd, t->u.e_byte_array_len.len_codec) == -1 ||
            cram_codec_decoder2encoder(fd, t->u.e_byte_array_len.val_codec) == -1) {
            t->free(t);
            return -1;
        }

        // {len,val}_{encoding,dat} are undefined, but unused.
        // Leaving them unset here means we can test that assertion.
        *c = *t;
        free(t);
        break;
    }

    case E_BYTE_ARRAY_STOP:
        // shares struct with decode
        c->free   = cram_byte_array_stop_encode_free;
        c->store  = cram_byte_array_stop_encode_store;
        c->encode = cram_byte_array_stop_encode;
        break;

    default:
        return -1;
    }

    return 0;
}

int cram_codec_describe(cram_codec *c, kstring_t *ks) {
    if (c && c->describe)
        return c->describe(c, ks);
    else
        return ksprintf(ks, "?");
}

Coverage Report

Created: 2026-06-30 06:18