tests/net.mograsim.logic.model.am2900.tests/src/net/mograsim/logic/model/am2900/gcd-mpm-doc.txt

   1 Register allocation:
   2
   3 R0: a1 (Euclid)
   4 R2: a2 (Euclid)
   5 R1: b (Euclid) / result
   6 Q: c (copy of b)
   7
   8 Most of the time, a1 holds the actual value of a, and a2 holds some garbage. But in the main subtract-and-half loop, it sometimes is the other way around for speed reasons.
   9
  10 Idea for calculating the remainder (we always calculate a%b):
  11 A copy of b (c) is l-shifted until it is bigger than or equal to a (or it can't be l-shifted further without losing the most significant 1).
  12 Then, repeatedly, if c is smaller than a, a is assigned a-c; then c is r-shifted; until c is again equal to b.
  13
  14 MPM:
  15 0x00: put the address of the first argument (0x0000) on the address bus; load the address of the second argument (0x0001) into a2 by lshifting a 1 into a2; load the address of the version of the second subtract-and-half loop cycle where a1 and a2 are swapped (0x08) into Am2910's Reg/Cntr
  16 0x01: load the first argument from RAM into c, load muSR accordingly
  17 0x02: put a2 (the address of the second argument (0x0001)) on the address bus; copy c to b; if c==0 (stored in muSR.Z), jump to the end saving the D bus (from RAM) to b (0x0e)
  18 0x03: load the second argument from RAM into a1; if the new a1==0, jump to the end (0x12)
  19 0x04: caluclate c-0x8000, if c>=0x8000, jump to the main subtract-and-half loop (0x07)
  20 0x05: lshift c; calculate (old c)-a, if c<a, jump back to the loop lshifting c (The result of (old c)-a is stored in a2, but never used)
  21 0x06: rshift c; calculate b-(old c); if b>(old c), jump to swapping a / b where a1 and a2 are not swapped (0x0a)
  22 0x07: store a1-c in a2; if a1<c, jump to the version of the second subtract-and-half loop cycle where a1 and a2 are not swapped (0x06)
  23 0x08: rshift c; calculate b-(old c); if b>(old c), jump to swapping a / b where a1 and a2 are swapped (0x0b)
  24 0x09: store a2-c in a1; if a2<c, jump to the version of the second subtract-and-half loop cycle where a1 and a2 are not swapped (0x06), else jump to where they are swapped (0x07)
  25 0x0a: copy a1 to c; load the muSR accordingly; jump to copying b to a1 (0x0c)
  26 0x0b: copy a2 to c; load the muSR accordingly
  27 0x0c: copy b to a1; if c==0 (stored in muSR.Z), jump to the end (0x12)
  28 0x0d: copy c to b; jump back to the start of Euclid's algorithm (0x04)
  29 0x0e: load the second argument from RAM into b; jump to the end (0x12)