ra8_rar5.c

Go to the documentation of this file.

#include "ra8_rar5.h"
 
#include <string.h>
 
#include "ra8_attributes.h"
#include "ra8_check.h"
#include "ra8_rar5_internal.h"

static const char* const s_tag_rar5 = "ra8_rar5";

RA8_INTERNAL static void internal_copy_object(void* dst, const void* src, size_t len)
{
  (void)memcpy(dst, src, len);
}
 
/* ---- little-endian scalar reads/writes ---------------------------------- */

RA8_INTERNAL static uint32_t internal_rd_le32(const uint8_t* p)
{
  uint32_t v = 0U;
  internal_copy_object(&v, p, sizeof(v));
  return v;
}

RA8_INTERNAL static void internal_wr_le32(uint8_t* p, uint32_t v)
{
  internal_copy_object(p, &v, sizeof(v));
}
 
/* ---- LZ token decode ---------------------------------------------------- */

RA8_INTERNAL static uint32_t internal_slot_to_length(ra8_rar5_state_t* st, uint32_t slot)
{
  uint32_t length = 2U;
  if (slot < 8U) {
    return length + slot;
  }
  const uint32_t lbits = (slot / 4U) - 1U;
  length += (4U | (slot & 3U)) << lbits;
  length += priv_rar5_get(st, lbits);
  return length;
}

RA8_INTERNAL static uint64_t internal_decode_distance(ra8_rar5_state_t* st)
{
  const uint32_t slot = priv_rar5_decode_num(st, &st->dd);
  if (slot < 4U) {
    return (uint64_t)1U + slot;
  }
  const uint32_t dbits = (slot / 2U) - 1U;
  uint64_t       dist  = UINT64_C(1) + ((UINT64_C(2) | (uint64_t)(slot & 1U)) << dbits);
  if (dbits < 4U) {
    return dist + priv_rar5_get(st, dbits);
  }
  if (dbits > 4U) {
    dist += (uint64_t)priv_rar5_get(st, dbits - 4U) << 4U;
  }
  dist += priv_rar5_decode_num(st, &st->ldd);
  return dist;
}

RA8_INTERNAL static uint32_t internal_adjust_length(uint32_t length, uint64_t dist)
{
  uint32_t adjusted = length;
  if (dist > (uint64_t)k_r5_dist_th1) {
    adjusted += 1U;
    if (dist > (uint64_t)k_r5_dist_th2) {
      adjusted += 1U;
      if (dist > (uint64_t)k_r5_dist_th3) {
        adjusted += 1U;
      }
    }
  }
  return adjusted;
}

RA8_INTERNAL static void internal_push_dist(ra8_rar5_state_t* st, uint64_t dist)
{
  for (uint32_t i = (uint32_t)k_ra8_rar5_old_dist - 1U; i > 0U; --i) { /* bound: ring size */
    st->old_dist[i] = st->old_dist[i - 1U];
  }
  st->old_dist[0] = dist;
}

RA8_PRIV bool
priv_rar5_copy_match(uint8_t* out, size_t* out_pos, size_t unp, uint32_t length, uint64_t dist)
{
  size_t pos = *out_pos;
  if ((dist == 0U) || (dist > (uint64_t)pos)) {
    return false;
  }
  const size_t back = (size_t)dist;
  for (uint32_t k = 0U; (k < length) && (pos < unp); ++k) { /* bound: length, pos<unp */
    out[pos] = out[pos - back];
    pos += 1U;
  }
  *out_pos = pos;
  return true;
}
 
/* ---- in-stream data filters --------------------------------------------- */

RA8_INTERNAL static uint32_t internal_read_filter_data(ra8_rar5_state_t* st)
{
  const uint32_t bc   = priv_rar5_get(st, 2U) + 1U;
  uint32_t       data = 0U;
  for (uint32_t i = 0U; i < bc; ++i) { /* bound: bc <= 4 */
    data |= priv_rar5_get(st, (uint32_t)k_r5_byte_bits) << (i * (uint32_t)k_r5_byte_bits);
  }
  return data;
}

RA8_INTERNAL static ra8_err_t internal_read_filter(ra8_rar5_state_t* st, size_t out_pos)
{
  if (st->filter_count >= (uint16_t)k_ra8_rar5_max_filters) {
    return k_ra8_err_validation_failed;
  }
  const uint32_t rel  = internal_read_filter_data(st);
  const uint32_t len  = internal_read_filter_data(st);
  const uint32_t type = priv_rar5_get(st, (uint32_t)k_r5_ftype_bits);
  if (type > (uint32_t)k_ra8_rar5_filter_arm) {
    return k_ra8_err_validation_failed;
  }
  uint32_t channels = 1U;
  if (type == (uint32_t)k_ra8_rar5_filter_delta) {
    channels = priv_rar5_get(st, (uint32_t)k_r5_fchan_bits) + 1U;
  }
  ra8_rar5_filter_t* f = &st->filters[st->filter_count];
  f->start             = (uint64_t)out_pos + (uint64_t)rel;
  f->len               = len;
  f->type              = (uint8_t)type;
  f->channels          = (uint8_t)channels;
  st->filter_count += 1U;
  return k_ra8_ok;
}

RA8_PRIV void
priv_rar5_filter_delta(ra8_rar5_state_t* st, uint8_t* d, uint32_t len, uint32_t channels)
{
  if ((len > (uint32_t)k_ra8_rar5_delta_scratch) || (channels == 0U)) {
    return;
  }
  (void)memcpy(st->delta, d, (size_t)len);
  uint32_t dpos = 0U;
  for (uint32_t ch = 0U; ch < channels; ++ch) { /* bound: channels <= 32 */
    uint8_t prev = 0U;
    for (uint32_t i = ch; i < len; i += channels) { /* bound: i < len */
      prev = (uint8_t)(prev - st->delta[dpos]);
      dpos += 1U;
      d[i] = prev;
    }
  }
}

RA8_INTERNAL static bool internal_x86_is_op(uint8_t op, bool e9)
{
  if (op == (uint8_t)k_r5_x86_call) {
    return true;
  }
  return e9 && (op == (uint8_t)k_r5_x86_jmp);
}

RA8_INTERNAL static void internal_filter_x86(uint8_t* d, uint32_t len, uint64_t filepos, bool e9)
{
  if (len < (uint32_t)k_r5_x86_ilen) {
    return;
  }
  const uint32_t limit = len - (uint32_t)k_r5_x86_ilen;
  uint32_t       i     = 0U;
  while (i <= limit) { /* bound: i <= limit < len */
    if (internal_x86_is_op(d[i], e9)) {
      const uint32_t off = i + 1U;
      const uint32_t pos = (uint32_t)(filepos + (uint64_t)off);
      internal_wr_le32(&d[off], internal_rd_le32(&d[off]) - pos);
      i += (uint32_t)k_r5_x86_ilen;
    } else {
      i += 1U;
    }
  }
}

RA8_INTERNAL static void internal_filter_arm(uint8_t* d, uint32_t len, uint64_t filepos)
{
  if (len < 4U) {
    return;
  }
  const uint32_t limit = len - 4U;
  uint32_t       i     = 0U;
  while (i <= limit) { /* bound: i steps by 4 to limit */
    if (d[i + 3U] == (uint8_t)k_r5_arm_bl) {
      uint32_t       v = (uint32_t)d[i] | ((uint32_t)d[i + 1U] << k_r5_byte_bits) |
                         ((uint32_t)d[i + 2U] << (k_r5_byte_bits * 2U));
      const uint32_t p = (uint32_t)((filepos + (uint64_t)i) >> 2U);
      v                = (v - p) & (uint32_t)k_r5_arm_off_mask;
      d[i]             = (uint8_t)(v & (uint32_t)k_r5_byte_mask);
      d[i + 1U]        = (uint8_t)((v >> k_r5_byte_bits) & (uint32_t)k_r5_byte_mask);
      d[i + 2U]        = (uint8_t)((v >> (k_r5_byte_bits * 2U)) & (uint32_t)k_r5_byte_mask);
    }
    i += 4U;
  }
}

RA8_INTERNAL static void internal_apply_one_filter(ra8_rar5_state_t*        st,
                                                   uint8_t*                 out,
                                                   size_t                   unp,
                                                   const ra8_rar5_filter_t* f)
{
  if (f->start >= (uint64_t)unp) {
    return;
  }
  const uint64_t avail = (uint64_t)unp - f->start;
  const uint32_t len   = ((uint64_t)f->len > avail) ? (uint32_t)avail : f->len;
  if (len == 0U) {
    return;
  }
  uint8_t* d = &out[(size_t)f->start];
  if (f->type == (uint8_t)k_ra8_rar5_filter_delta) {
    priv_rar5_filter_delta(st, d, len, f->channels);
  } else if (f->type == (uint8_t)k_ra8_rar5_filter_e8) {
    internal_filter_x86(d, len, f->start, false);
  } else if (f->type == (uint8_t)k_ra8_rar5_filter_e8e9) {
    internal_filter_x86(d, len, f->start, true);
  } else {
    internal_filter_arm(d, len, f->start);
  }
}

RA8_INTERNAL static void internal_apply_filters(ra8_rar5_state_t* st, uint8_t* out, size_t unp)
{
  for (uint16_t f = 0U; f < st->filter_count; ++f) { /* bound: filter_count */
    internal_apply_one_filter(st, out, unp, &st->filters[f]);
  }
}
 
/* ---- token dispatch + block/stream loops -------------------------------- */

RA8_INTERNAL
static ra8_err_t
internal_do_match(ra8_rar5_state_t* st, uint32_t slot, uint8_t* out, size_t* out_pos, size_t unp)
{
  uint32_t       length = internal_slot_to_length(st, slot - (uint32_t)k_r5_sym_lenbase);
  const uint64_t dist   = internal_decode_distance(st);
  length                = internal_adjust_length(length, dist);
  internal_push_dist(st, dist);
  st->last_length = length;
  if (!priv_rar5_copy_match(out, out_pos, unp, length, dist)) {
    return k_ra8_err_validation_failed;
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t
internal_do_repdist(ra8_rar5_state_t* st, uint32_t slot, uint8_t* out, size_t* out_pos, size_t unp)
{
  const uint32_t idx  = slot - (uint32_t)k_r5_sym_repdist0;
  const uint64_t dist = st->old_dist[idx];
  for (uint32_t i = idx; i > 0U; --i) { /* bound: idx <= 3 */
    st->old_dist[i] = st->old_dist[i - 1U];
  }
  st->old_dist[0]        = dist;
  const uint32_t lenslot = priv_rar5_decode_num(st, &st->rd);
  const uint32_t length  = internal_slot_to_length(st, lenslot);
  st->last_length        = length;
  if (!priv_rar5_copy_match(out, out_pos, unp, length, dist)) {
    return k_ra8_err_validation_failed;
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t
internal_do_replast(ra8_rar5_state_t* st, uint8_t* out, size_t* out_pos, size_t unp)
{
  if (st->last_length == 0U) {
    return k_ra8_ok;
  }
  if (!priv_rar5_copy_match(out, out_pos, unp, st->last_length, st->old_dist[0])) {
    return k_ra8_err_validation_failed;
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t
internal_decode_token(ra8_rar5_state_t* st, uint8_t* out, size_t* out_pos, size_t unp)
{
  const uint32_t slot = priv_rar5_decode_num(st, &st->ld);
  if (slot < (uint32_t)k_r5_sym_filter) {
    out[*out_pos] = (uint8_t)slot;
    *out_pos += 1U;
    return k_ra8_ok;
  }
  if (slot == (uint32_t)k_r5_sym_filter) {
    return internal_read_filter(st, *out_pos);
  }
  if (slot == (uint32_t)k_r5_sym_replast) {
    return internal_do_replast(st, out, out_pos, unp);
  }
  if (slot < (uint32_t)k_r5_sym_lenbase) {
    return internal_do_repdist(st, slot, out, out_pos, unp);
  }
  return internal_do_match(st, slot, out, out_pos, unp);
}

RA8_INTERNAL static ra8_err_t
internal_open_block(ra8_rar5_state_t* st, uint64_t* end_bit, bool* last)
{
  r5_block_t      blk = {};
  const ra8_err_t e   = priv_rar5_read_block_header(st, &blk);
  if (e != k_ra8_ok) {
    return e;
  }
  if (blk.size == 0U) {
    return k_ra8_err_validation_failed;
  }
  const uint64_t start = st->consumed;
  *end_bit = start + ((blk.size - 1U) * (uint64_t)k_r5_byte_bits) + (uint64_t)blk.last_bits;
  *last    = blk.last;
  if (blk.tables) {
    return priv_rar5_read_tables(st);
  }
  if (!st->tables_ready) {
    return k_ra8_err_validation_failed;
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t
internal_decode_stream(ra8_rar5_state_t* st, uint8_t* out, size_t out_cap, size_t unp)
{
  (void)out_cap;
  size_t         out_pos   = 0U;
  bool           last      = false;
  uint64_t       block_end = 0U;
  const uint64_t cap_bits  = (st->packlen * (uint64_t)k_r5_byte_bits) + (uint64_t)k_r5_max_pad_bits;
  ra8_err_t      e         = internal_open_block(st, &block_end, &last);
  if (e != k_ra8_ok) {
    return e;
  }
  while ((out_pos < unp) && (st->consumed <= cap_bits)) { /* bound: consumed strictly rises */
    if (st->consumed >= block_end) {
      if (last) {
        break;
      }
      e = internal_open_block(st, &block_end, &last);
      if (e != k_ra8_ok) {
        return e;
      }
      continue;
    }
    e = internal_decode_token(st, out, &out_pos, unp);
    if (e != k_ra8_ok) {
      return e;
    }
  }
  if (out_pos != unp) {
    return k_ra8_err_validation_failed;
  }
  return k_ra8_ok;
}

RA8_INTERNAL static ra8_err_t internal_decompress_check(const ra8_rar_t*        rar,
                                                        const uint8_t*          out,
                                                        const ra8_rar5_state_t* st,
                                                        size_t                  out_cap,
                                                        uint64_t                unp_size,
                                                        uint64_t                pack_size)
{
  RA8_CHECK_NULL_PTR(rar, s_tag_rar5, "decompress: null rar");
  RA8_CHECK_NULL_PTR(out, s_tag_rar5, "decompress: null out");
  RA8_CHECK_NULL_PTR(st, s_tag_rar5, "decompress: null st");
  if (rar->version != k_ra8_rar_ver_5) {
    return k_ra8_err_invalid_state;
  }
  if (unp_size > (uint64_t)out_cap) {
    return k_ra8_err_no_mem;
  }
  if (pack_size == 0U) {
    return k_ra8_err_validation_failed;
  }
  return k_ra8_ok;
}
 
ra8_err_t ra8_rar5_decompress(const ra8_rar_t*  rar,
                              uint64_t          data_off,
                              uint64_t          pack_size,
                              uint8_t*          out,
                              size_t            out_cap,
                              uint64_t          unp_size,
                              ra8_rar5_state_t* st,
                              size_t*           got)
{
  RA8_CHECK_NULL_PTR(got, s_tag_rar5, "decompress: null got");
  *got                   = 0U;
  const ra8_err_t vcheck = internal_decompress_check(rar, out, st, out_cap, unp_size, pack_size);
  if (vcheck != k_ra8_ok) {
    return vcheck;
  }
  *st         = (ra8_rar5_state_t){};
  st->rar     = rar;
  st->base    = data_off;
  st->packlen = pack_size;
  if (unp_size == 0U) {
    return k_ra8_ok;
  }
  const ra8_err_t e = internal_decode_stream(st, out, out_cap, (size_t)unp_size);
  if (e != k_ra8_ok) {
    return e;
  }
  internal_apply_filters(st, out, (size_t)unp_size);
  *got = (size_t)unp_size;
  return k_ra8_ok;
}