ra8_rar5_tables.c

Go to the documentation of this file.

#include <string.h>
 
#include "ra8_attributes.h"
#include "ra8_rar5.h"
#include "ra8_rar5_internal.h"
 
/* ---- streaming MSB-first bit reader ------------------------------------- */

RA8_INTERNAL static uint8_t internal_fetch_byte(ra8_rar5_state_t* st)
{
  if (st->refill_pos >= st->refill_len) {
    if (st->fetched >= st->packlen) {
      st->overrun = true;
      return 0U;
    }
    const uint64_t remain = st->packlen - st->fetched;
    const size_t   want   = (remain < (uint64_t)k_ra8_rar5_refill_bytes)
                              ? (size_t)remain
                              : (size_t)k_ra8_rar5_refill_bytes;
    const size_t   r      = st->rar->read(st->rar->ctx, st->base + st->fetched, st->refill, want);
    if (r == 0U) {
      st->overrun = true;
      return 0U;
    }
    st->refill_len = (uint32_t)r;
    st->refill_pos = 0U;
    st->fetched += (uint64_t)r;
  }
  const uint8_t b = st->refill[st->refill_pos];
  st->refill_pos += 1U;
  return b;
}

RA8_INTERNAL static void internal_ensure(ra8_rar5_state_t* st, uint32_t n)
{
  while (st->nbits < n) { /* bound: n<=32, +8 bits per pass -> <=4 passes */
    const uint8_t b = internal_fetch_byte(st);
    st->acc         = (st->acc << k_r5_byte_bits) | (uint64_t)b;
    st->nbits += (uint32_t)k_r5_byte_bits;
  }
}

RA8_INTERNAL static uint32_t internal_peek(ra8_rar5_state_t* st, uint32_t n)
{
  internal_ensure(st, n);
  const uint64_t mask = ((uint64_t)1U << n) - (uint64_t)1U;
  return (uint32_t)((st->acc >> (st->nbits - n)) & mask);
}

RA8_INTERNAL static void internal_drop(ra8_rar5_state_t* st, uint32_t n)
{
  st->nbits -= n;
  st->consumed += (uint64_t)n;
  const uint64_t mask = (st->nbits >= (uint32_t)k_r5_acc_bits)
                          ? ~(uint64_t)0U
                          : (((uint64_t)1U << st->nbits) - (uint64_t)1U);
  st->acc &= mask;
}

RA8_PRIV uint32_t priv_rar5_get(ra8_rar5_state_t* st, uint32_t n)
{
  const uint32_t v = internal_peek(st, n);
  internal_drop(st, n);
  return v;
}

RA8_INTERNAL static void internal_align(ra8_rar5_state_t* st)
{
  internal_drop(st, st->nbits & (uint32_t)k_r5_low3_mask);
}
 
/* ---- canonical Huffman decode tables ------------------------------------ */

RA8_INTERNAL static void internal_tab_limits(ra8_rar5_dtab_t* d, const uint32_t* count)
{
  d->len[0]      = 0U;
  d->pos[0]      = 0U;
  uint32_t upper = 0U;
  for (uint32_t i = 1U; i < (uint32_t)(k_r5_maxbits + 1U); ++i) { /* bound: 15 lengths */
    upper += count[i];
    d->len[i] = upper << ((uint32_t)k_r5_bf_bits - i);
    upper <<= 1U;
    d->pos[i] = d->pos[i - 1U] + count[i - 1U];
  }
}

RA8_INTERNAL static void
internal_make_tables(ra8_rar5_dtab_t* d, const uint8_t* lengths, uint16_t size)
{
  uint32_t count[k_r5_maxbits + 1U] = {};
  for (uint16_t i = 0U; i < size; ++i) { /* bound: size <= k_ra8_rar5_nc */
    count[lengths[i] & (uint8_t)k_r5_nibble_mask] += 1U;
  }
  count[0] = 0U;
  internal_tab_limits(d, count);
  (void)memset(d->num, 0, (size_t)size * sizeof(d->num[0]));
  uint32_t copypos[k_r5_maxbits + 1U];
  for (uint32_t i = 0U; i < (uint32_t)(k_r5_maxbits + 1U); ++i) { /* bound: 16 */
    copypos[i] = d->pos[i];
  }
  for (uint16_t i = 0U; i < size; ++i) { /* bound: size */
    const uint8_t bl = lengths[i] & (uint8_t)k_r5_nibble_mask;
    if (bl != 0U) {
      d->num[copypos[bl]] = i;
      copypos[bl] += 1U;
    }
  }
  d->max = size;
}

RA8_PRIV uint32_t priv_rar5_decode_num(ra8_rar5_state_t* st, const ra8_rar5_dtab_t* d)
{
  const uint32_t bf   = internal_peek(st, (uint32_t)k_r5_bf_bits) & (uint32_t)k_r5_bf_mask;
  uint32_t       bits = (uint32_t)k_r5_maxbits;
  for (uint32_t i = 1U; i < (uint32_t)k_r5_maxbits; ++i) { /* bound: 14 lengths */
    if (bf < d->len[i]) {
      bits = i;
      break;
    }
  }
  internal_drop(st, bits);
  const uint32_t dist = (bf - d->len[bits - 1U]) >> ((uint32_t)k_r5_bf_bits - bits);
  uint32_t       pos  = d->pos[bits] + dist;
  if (pos >= (uint32_t)d->max) {
    pos = 0U;
  }
  return d->num[pos];
}
 
/* ---- block header + Huffman tables -------------------------------------- */

RA8_INTERNAL static uint8_t internal_checksum(uint32_t flags, uint64_t blocksize)
{
  uint32_t x = (uint32_t)k_r5_hdr_chk_seed ^ flags;
  x ^= (uint32_t)(blocksize & (uint64_t)k_r5_byte_mask);
  x ^= (uint32_t)((blocksize >> k_r5_byte_bits) & (uint64_t)k_r5_byte_mask);
  x ^= (uint32_t)((blocksize >> (k_r5_byte_bits * 2U)) & (uint64_t)k_r5_byte_mask);
  return (uint8_t)(x & (uint32_t)k_r5_byte_mask);
}

RA8_PRIV ra8_err_t priv_rar5_read_block_header(ra8_rar5_state_t* st, r5_block_t* b)
{
  internal_align(st);
  const uint32_t flags = priv_rar5_get(st, (uint32_t)k_r5_byte_bits);
  const uint32_t bytecount =
    ((flags >> (uint32_t)k_r5_bf_bcount_shift) & (uint32_t)k_r5_bf_bcount_mask) + 1U;
  uint64_t bsz = 0U;
  for (uint32_t i = 0U; i < bytecount; ++i) { /* bound: bytecount <= 4 */
    bsz |= (uint64_t)priv_rar5_get(st, (uint32_t)k_r5_byte_bits)
           << ((uint32_t)i * (uint32_t)k_r5_byte_bits);
  }
  const uint32_t saved = priv_rar5_get(st, (uint32_t)k_r5_byte_bits);
  if ((uint32_t)internal_checksum(flags, bsz) != saved) {
    return k_ra8_err_validation_failed;
  }
  b->size      = bsz;
  b->last_bits = (flags & (uint32_t)k_r5_bf_bitsize_mask) + 1U;
  b->tables    = (flags & (uint32_t)k_r5_bf_tables) != 0U;
  b->last      = (flags & (uint32_t)k_r5_bf_last) != 0U;
  return k_ra8_ok;
}

RA8_PRIV uint32_t priv_rar5_fill_zeros(uint8_t* out, uint32_t start, uint32_t count, uint32_t max)
{
  uint32_t i = start;
  for (uint32_t c = 0U; (c < count) && (i < max); ++c) { /* bound: count, i<max */
    out[i] = 0U;
    i += 1U;
  }
  return i;
}

RA8_INTERNAL static ra8_err_t internal_read_bd_lengths(ra8_rar5_state_t* st, uint8_t* out)
{
  uint32_t i = 0U;
  while (i < (uint32_t)k_ra8_rar5_bc) { /* bound: i advances toward k_ra8_rar5_bc */
    const uint32_t len = priv_rar5_get(st, 4U);
    if (len != (uint32_t)k_r5_len_escape) {
      out[i] = (uint8_t)len;
      i += 1U;
      continue;
    }
    const uint32_t zc = priv_rar5_get(st, 4U);
    if (zc == 0U) {
      out[i] = (uint8_t)k_r5_len_escape;
      i += 1U;
    } else {
      i = priv_rar5_fill_zeros(out, i, zc + (uint32_t)k_r5_zeros_extra, (uint32_t)k_ra8_rar5_bc);
    }
  }
  return k_ra8_ok;
}

RA8_PRIV ra8_err_t priv_rar5_apply_run(ra8_rar5_state_t* st,
                                       uint8_t*          tbl,
                                       uint32_t*         idx,
                                       uint32_t          num)
{
  const bool is_long =
    (num == (uint32_t)k_r5_tbl_copy_long) || (num == (uint32_t)k_r5_tbl_zero_long);
  const bool is_zero =
    (num == (uint32_t)k_r5_tbl_zero_short) || (num == (uint32_t)k_r5_tbl_zero_long);
  const uint32_t count =
    is_long ? (priv_rar5_get(st, (uint32_t)k_r5_run_long_bits) + (uint32_t)k_r5_run_long_add)
            : (priv_rar5_get(st, 3U) + 3U);
  if ((!is_zero) && (*idx == 0U)) {
    return k_ra8_err_validation_failed;
  }
  const uint8_t prev = (*idx > 0U) ? tbl[*idx - 1U] : 0U;
  const uint8_t fill = is_zero ? 0U : prev;
  uint32_t      i    = *idx;
  for (uint32_t c = 0U; (c < count) && (i < (uint32_t)k_ra8_rar5_huff_total);
       ++c) { /* bound: count */
    tbl[i] = fill;
    i += 1U;
  }
  *idx = i;
  return k_ra8_ok;
}

RA8_INTERNAL static ra8_err_t internal_read_full_table(ra8_rar5_state_t* st, uint8_t* tbl)
{
  uint32_t i = 0U;
  while (i < (uint32_t)k_ra8_rar5_huff_total) { /* bound: i advances each pass */
    const uint32_t num = priv_rar5_decode_num(st, &st->bd);
    if (num < 16U) {
      tbl[i] = (uint8_t)num;
      i += 1U;
      continue;
    }
    const ra8_err_t e = priv_rar5_apply_run(st, tbl, &i, num);
    if (e != k_ra8_ok) {
      return e;
    }
  }
  return k_ra8_ok;
}

RA8_PRIV ra8_err_t priv_rar5_read_tables(ra8_rar5_state_t* st)
{
  uint8_t   bdlen[k_ra8_rar5_bc] = {};
  ra8_err_t e                    = internal_read_bd_lengths(st, bdlen);
  if (e != k_ra8_ok) {
    return e;
  }
  internal_make_tables(&st->bd, bdlen, (uint16_t)k_ra8_rar5_bc);
  uint8_t tbl[k_ra8_rar5_huff_total] = {};
  e                                  = internal_read_full_table(st, tbl);
  if (e != k_ra8_ok) {
    return e;
  }
  internal_make_tables(&st->ld, &tbl[0], (uint16_t)k_ra8_rar5_nc);
  internal_make_tables(&st->dd, &tbl[k_ra8_rar5_nc], (uint16_t)k_ra8_rar5_dc);
  internal_make_tables(&st->ldd, &tbl[k_ra8_rar5_nc + k_ra8_rar5_dc], (uint16_t)k_ra8_rar5_ldc);
  internal_make_tables(&st->rd,
                       &tbl[k_ra8_rar5_nc + k_ra8_rar5_dc + k_ra8_rar5_ldc],
                       (uint16_t)k_ra8_rar5_rc);
  st->tables_ready = true;
  return k_ra8_ok;
}