div16.py

# this builds on https://gist.github.com/acdimalev/ff75aa864e49a41231d19c921132faf1

# double-word division takes three input parameters and outputs two
# for ALU-type usage, it makes sense to re-use two of the input registers as output registers

# A : dividend high-word -> remainder
# B : dividend low-word -> quotient
# C : divisor

# long-division is accomplished by zeroing out the dividend high-word,
# and then successively loading the multi-word dividend into the dividend low-word in big-endian order


# reference function

def _div16(a, b, c):
  d = a << 16 | b
  e = 0
  for f in reversed(range(16)):
    g = c << f
    if d >= g:
      e |= 1 << f
      d -= g
  a = d & (1 << 16) - 1
  b = e & (1 << 16) - 1
  return (a, b)


# re-implemented with abstracted sub-blocks

def sub16(a, b):
  d = (a - b) % (1 << 16)
  c = a > b
  return (c, d)


def condsub16(a, b):
  (c, d) = sub16(a, b)
  e = d if c else a
  return (c, e)


def div16(a, b, c):
  e = 0
  for _ in range(16):
    a = a << 1 | b >> 15
    b = b << 1 & (1 << 16) - 1
    (p, a) = condsub16(a, c)
    e = e << 1 | p
  b = e & (1 << 16) - 1
  return (a, b)