#   crc's _ _
#        (_) | ___
#        | | |/ _ \  a tiny virtual computer
#        | | | (_) | 64kw RAM, 32-bit, Dual Stack, MISC
#        |_|_|\___/  ilo.awk (c) charles childers
#
# Run in the C locale so that %c writes single bytes:
#   LC_ALL=C awk -f ilo.awk [ilo.rom [ilo.blocks]]
#
# GNU awk may also be run with -b:
#   gawk -b -f ilo.awk -- [ilo.rom [ilo.blocks]]
#
# Requires: POSIX awk, od, dd
#
# The C locale is important: it makes %c and string handling
# byte-oriented, which is required when writing little-endian
# binary image/block files.

BEGIN {
  MEM_CELLS = 65536
  DATA_CELLS = 32
  ADDR_CELLS = 256
  BLOCK_CELLS = 1024
  BLOCK_BYTES = 4096
  U32 = 4294967296
  S32 = 2147483648

  argi = 1
  # Accept gawk's conventional `--` separator while keeping
  # the portable invocation above suitable for awks that do
  # not recognize that option.
  if (ARGV[argi] == "--") argi++
  image_file = (ARGC > argi ? ARGV[argi] : "ilo.rom")
  block_file = (ARGC > argi + 1 ? ARGV[argi + 1] : "ilo.blocks")

  if (image_file == "") {
    print "usage: LC_ALL=C awk -f ilo.awk [IMAGE [BLOCKS]]" > "/dev/stderr"
    exit 64
  }

  init_ord()
  clear_memory()
  load_image(image_file)
  clear_stacks()

  ip = 0
  halted = 0

  while (!halted && ip >= 0 && ip < MEM_CELLS) {
    process_bundle(memory[ip])
    ip++
  }

  exit exit_status
}

# ---------- numeric helpers ----------

function u32(n) {
  n %= U32
  if (n < 0) n += U32
  return n
}

function s32(n) {
  n = u32(n)
  return (n >= S32) ? n - U32 : n
}

function boolv(v) {
  return v ? -1 : 0
}

function pow2(n,  p, i) {
  p = 1
  for (i = 0; i < n; i++) p *= 2
  return p
}

# Portable 32-bit bit operations. This avoids depending on
# gawk's bitwise builtins and keeps all intermediate values
# within exact IEEE-754 integer range.
function bit_and(a, b,  ua, ub, p, r, i, aa, bb) {
  ua = u32(a); ub = u32(b); p = 1; r = 0
  for (i = 0; i < 32; i++) {
    aa = int(ua / p) % 2
    bb = int(ub / p) % 2
    if (aa && bb) r += p
    p *= 2
  }
  return s32(r)
}

function bit_or(a, b,  ua, ub, p, r, i, aa, bb) {
  ua = u32(a); ub = u32(b); p = 1; r = 0
  for (i = 0; i < 32; i++) {
    aa = int(ua / p) % 2
    bb = int(ub / p) % 2
    if (aa || bb) r += p
    p *= 2
  }
  return s32(r)
}

function bit_xor(a, b,  ua, ub, p, r, i, aa, bb) {
  ua = u32(a); ub = u32(b); p = 1; r = 0
  for (i = 0; i < 32; i++) {
    aa = int(ua / p) % 2
    bb = int(ub / p) % 2
    if (aa != bb) r += p
    p *= 2
  }
  return s32(r)
}

function shift_left(a, b,  m, x) {
  if (b < 0 || b >= 32) vm_error("invalid left shift: " b)
  if (b == 0) return s32(a)
  m = pow2(32 - b)
  x = u32(a) % m
  return s32(x * pow2(b))
}

function shift_right(a, b,  q, iq) {
  if (b < 0 || b >= 32) vm_error("invalid right shift: " b)
  if (b == 0) return s32(a)

  # ilo requires arithmetic (sign-extending) right shift.
  q = s32(a) / pow2(b)
  iq = int(q)
  if (q < 0 && q != iq) iq--
  return s32(iq)
}

function mul32(a, b,  ua, ub, al, ah, bl, bh, cross, r) {
  # Compute the low 32 bits without ever forming a ~2^62
  # product, which awk's usual IEEE-754 number representation
  # cannot represent exactly. Split both operands into 16-bit
  # parts.
  ua = u32(a); ub = u32(b)
  al = ua % 65536; ah = int(ua / 65536)
  bl = ub % 65536; bh = int(ub / 65536)
  cross = (ah * bl + al * bh) % 65536
  r = al * bl + cross * 65536
  return s32(r)
}

function trunc_div(a, b) {
  if (b == 0) vm_error("division by zero")
  if (a == -2147483648 && b == -1)
    vm_error("division overflow")
  return int(a / b)
}

function trunc_rem(a, b, q) {
  q = trunc_div(a, b)
  return a - q * b
}

# ---------- stack helpers ----------

function clear_stacks(  i) {
  delete data
  delete address
  sp = 0
  rp = 0
}

function push(v) {
  if (sp >= DATA_CELLS) vm_error("data stack overflow")
  data[sp++] = s32(v)
}

function pop(  v) {
  if (sp <= 0) vm_error("data stack underflow")
  v = data[--sp]
  delete data[sp]
  return v
}

function rpush(v) {
  if (rp >= ADDR_CELLS) vm_error("address stack overflow")
  address[rp++] = s32(v)
}

function rpop(  v) {
  if (rp <= 0) vm_error("address stack underflow")
  v = address[--rp]
  delete address[rp]
  return v
}

function require_data(n) {
  if (sp < n) vm_error("data stack underflow")
}

function require_addr(n) {
  if (rp < n) vm_error("address stack underflow")
}

# ---------- memory helpers ----------

function clear_memory(  i) {
  delete memory
  for (i = 0; i < MEM_CELLS; i++) memory[i] = 0
}

function check_addr(a) {
  if (a < 0 || a >= MEM_CELLS || a != int(a))
    vm_error("memory address out of bounds: " a)
}

function check_region(a, n) {
  if (n < 0 || n != int(n)) vm_error("invalid region length: " n)
  if (n == 0) {
    if (a < 0 || a > MEM_CELLS) vm_error("memory region out of bounds")
    return
  }
  if (a < 0 || a >= MEM_CELLS || a + n > MEM_CELLS)
    vm_error("memory region out of bounds")
}

# ---------- binary file helpers ----------

function shquote(s,  q) {
  q = s
  gsub(/'/, "'\\''", q)
  return "'" q "'"
}

function load_image(file,  cmd, line, n, i, byte, bc, cell, shift, cells, rc) {
  clear_memory()
  cmd = "od -An -v -tx1 " shquote(file) " 2>/dev/null"
  bc = 0; cell = 0; shift = 1; cells = 0

  while ((cmd | getline line) > 0) {
    n = split(line, f, /[[:space:]]+/)
    for (i = 1; i <= n; i++) {
      if (f[i] == "") continue
      if (f[i] !~ /^[0-9a-fA-F][0-9a-fA-F]$/)
        vm_error("bad image byte while reading " file)

      byte = hexbyte(f[i])
      cell += byte * shift
      shift *= 256
      bc++

      if (bc == 4) {
        if (cells >= MEM_CELLS)
          vm_error("image is larger than 65536 cells")
        memory[cells++] = s32(cell)
        bc = 0; cell = 0; shift = 1
      }
    }
  }
  rc = close(cmd)

  if (rc != 0) vm_error("unable to read image: " file)
  if (bc != 0) vm_error("image size is not a multiple of four bytes")
  return cells
}

function save_image(file,  i) {
  # First write opens with truncation; subsequent writes reuse the stream.
  for (i = 0; i < MEM_CELLS; i++) write_cell(file, memory[i])
  if (close(file) != 0) vm_error("unable to write image: " file)
}

function write_cell(file, value,  u, i, byte) {
  u = u32(value)
  for (i = 0; i < 4; i++) {
    byte = int(u % 256)
    printf "%c", byte > file
    u = int(u / 256)
  }
}

function hexbyte(h,  i, c, v, d) {
  v = 0
  h = tolower(h)
  for (i = 1; i <= 2; i++) {
    c = substr(h, i, 1)
    d = index("0123456789abcdef", c) - 1
    if (d < 0) vm_error("invalid hexadecimal byte: " h)
    v = v * 16 + d
  }
  return v
}

function read_block(block, dest,  cmd, line, n, i, bc, cell, shift, cells, byte, rc) {
  if (block < 0 || block != int(block)) vm_error("invalid block number: " block)
  check_region(dest, BLOCK_CELLS)

  cmd = "dd if=" shquote(block_file) " bs=4096 skip=" block \
      " count=1 2>/dev/null | od -An -v -tx1"

  bc = 0; cell = 0; shift = 1; cells = 0
  while ((cmd | getline line) > 0) {
    n = split(line, f, /[[:space:]]+/)
    for (i = 1; i <= n; i++) {
      if (f[i] == "") continue
      byte = hexbyte(f[i])
      cell += byte * shift
      shift *= 256
      bc++
      if (bc == 4) {
        if (cells >= BLOCK_CELLS) vm_error("block read overflow")
        memory[dest + cells] = s32(cell)
        cells++
        bc = 0; cell = 0; shift = 1
      }
    }
  }
  rc = close(cmd)

  if (rc != 0) vm_error("unable to read block " block)
  if (bc != 0 || cells != BLOCK_CELLS)
    vm_error("short block read: " block)
}

function write_block(block, src,  tmp, i, cmd, rc) {
  if (block < 0 || block != int(block)) vm_error("invalid block number: " block)
  check_region(src, BLOCK_CELLS)

  tmp = "/tmp/ilo-awk-block." systime() "." int(rand() * 1000000000)
  for (i = 0; i < BLOCK_CELLS; i++) write_cell(tmp, memory[src + i])
  if (close(tmp) != 0) vm_error("unable to create temporary block")

  cmd = "dd if=" shquote(tmp) " of=" shquote(block_file) \
      " bs=4096 seek=" block " count=1 conv=notrunc 2>/dev/null"
  rc = system(cmd)
  system("rm -f " shquote(tmp))
  if (rc != 0) vm_error("unable to write block " block)
}

# ---------- terminal helpers ----------

function init_ord(  i, c) {
  delete ord
  for (i = 0; i < 256; i++) {
    c = sprintf("%c", i)
    ord[c] = i
  }
  input_buffer = ""
  input_pos = 1
}

function read_char(  line, rc, c) {
  if (input_pos > length(input_buffer)) {
    rc = getline line < "/dev/stdin"
    if (rc < 0) vm_error("terminal input error")
    if (rc == 0) return -1
    input_buffer = line "\n"
    input_pos = 1
  }

  c = substr(input_buffer, input_pos++, 1)
  return ord[c]
}

# ---------- I/O devices ----------

function perform_io(  op, ch, block, addr) {
  op = pop()

  if (op == 0) {
    ch = pop()
    printf "%c", u32(ch) % 256
    fflush()
  }
  else if (op == 1) {
    push(read_char())
  }
  else if (op == 2) {
    addr = pop()
    block = pop()
    read_block(block, addr)
  }
  else if (op == 3) {
    addr = pop()
    block = pop()
    write_block(block, addr)
  }
  else if (op == 4) {
    save_image(image_file)
  }
  else if (op == 5) {
    load_image(image_file)
    clear_stacks()
    ip = -1
    abort_bundle = 1
  }
  else if (op == 6) {
    halted = 1
    abort_bundle = 1
  }
  else if (op == 7) {
    push(sp)
    push(rp)
  }
  else if (op >= 8 && op <= 11) {
    vm_error("reserved I/O device: " op)
  }
  else {
    vm_error("unsupported I/O device: " op)
  }
}

# ---------- instruction processor ----------

function process_bundle(bundle,  u, i, op) {
  u = u32(bundle)
  abort_bundle = 0

  for (i = 0; i < 4 && !abort_bundle && !halted; i++) {
    op = int(u % 256)
    process_op(op)
    u = int(u / 256)
  }
}

function process_op(op,  a, b, target, flag, src, dest, len, i, q, r, t) {
  if (op == 0) {         # ..
    return
  }
  else if (op == 1) {      # li
    ip++
    check_addr(ip)
    push(memory[ip])
  }
  else if (op == 2) {      # du
    require_data(1)
    push(data[sp - 1])
  }
  else if (op == 3) {      # dr
    pop()
  }
  else if (op == 4) {      # sw
    require_data(2)
    t = data[sp - 1]
    data[sp - 1] = data[sp - 2]
    data[sp - 2] = t
  }
  else if (op == 5) {      # pu
    rpush(pop())
  }
  else if (op == 6) {      # po
    push(rpop())
  }
  else if (op == 7) {      # ju
    target = pop()
    ip = target - 1
    abort_bundle = 1
  }
  else if (op == 8) {      # ca
    target = pop()
    rpush(ip)
    ip = target - 1
    abort_bundle = 1
  }
  else if (op == 9) {      # cc
    target = pop()
    flag = pop()
    if (flag != 0) {
      rpush(ip)
      ip = target - 1
      abort_bundle = 1
    }
  }
  else if (op == 10) {       # cj
    target = pop()
    flag = pop()
    if (flag != 0) {
      ip = target - 1
      abort_bundle = 1
    }
  }
  else if (op == 11) {       # re
    ip = rpop()
    abort_bundle = 1
  }
  else if (op == 12) {       # eq
    b = pop(); a = pop(); push(boolv(a == b))
  }
  else if (op == 13) {       # ne
    b = pop(); a = pop(); push(boolv(a != b))
  }
  else if (op == 14) {       # lt
    b = pop(); a = pop(); push(boolv(a < b))
  }
  else if (op == 15) {       # gt
    b = pop(); a = pop(); push(boolv(a > b))
  }
  else if (op == 16) {       # fe
    require_data(1)
    a = data[sp - 1]
    check_addr(a)
    data[sp - 1] = memory[a]
  }
  else if (op == 17) {       # st
    dest = pop(); a = pop()
    check_addr(dest)
    memory[dest] = s32(a)
  }
  else if (op == 18) {       # ad
    b = pop(); a = pop(); push(s32(a + b))
  }
  else if (op == 19) {       # su
    b = pop(); a = pop(); push(s32(a - b))
  }
  else if (op == 20) {       # mu
    b = pop(); a = pop(); push(mul32(a, b))
  }
  else if (op == 21) {       # di
    b = pop(); a = pop()
    q = trunc_div(a, b)
    r = a - q * b
    push(r)
    push(q)
  }
  else if (op == 22) {       # an
    b = pop(); a = pop(); push(bit_and(a, b))
  }
  else if (op == 23) {       # or
    b = pop(); a = pop(); push(bit_or(a, b))
  }
  else if (op == 24) {       # xo
    b = pop(); a = pop(); push(bit_xor(a, b))
  }
  else if (op == 25) {       # sl
    b = pop(); a = pop(); push(shift_left(a, b))
  }
  else if (op == 26) {       # sr
    b = pop(); a = pop(); push(shift_right(a, b))
  }
  else if (op == 27) {       # cp
    len = pop(); dest = pop(); src = pop()
    check_region(src, len)
    check_region(dest, len)
    flag = -1
    for (i = 0; i < len; i++)
      if (memory[dest + i] != memory[src + i]) flag = 0
    push(flag)
  }
  else if (op == 28) {       # cy
    len = pop(); dest = pop(); src = pop()
    check_region(src, len)
    check_region(dest, len)
    for (i = 0; i < len; i++)
      memory[dest + i] = memory[src + i]
  }
  else if (op == 29) {       # io
    perform_io()
  }
  else {
    vm_error("invalid opcode " op " at ip " ip)
  }
}

# ---------- fatal errors ----------

function vm_error(msg) {
  print "ilo.awk: " msg > "/dev/stderr"
  exit_status = 1
  halted = 1
  exit 1
}