;----------------------------------------------------------------------------
; mul.src
; David Boozer
; 2 November 2007
;----------------------------------------------------------------------------
; Test input file for Turing machine compiler, compiles to mul.fsm
;----------------------------------------------------------------------------
;
; The structure of the tape is as follows:
;
; +-----+---+-----+---+-----+
; |  a  | 0 |  b  | 0 |  p  |
; +-----+---+-----+---+-----+
;
; Initially a and b are the two numbers to be multiplied, and p is zero.
;
; Algorithm:
;
; 1. mark a
; 2. add b to p by marking b and adding 1's to rhs of x
; 3. check marking on a to see if we're done
;
; bugs: crashes if either a or b is zero
;----------------------------------------------------------------------------

mark_a:

000 0 --> 000 0 R
000 1 --> 001 0 R
001 0 --> jmp 0 R > add_b_to_p
001 1 --> 001 1 R

;----------------------------------------------------------------------------

add_b_to_p:

; add b to p by marking b and appending 1's to rhs of p
000 0 --> nop
000 1 --> 001 0 R
001 0 --> 002 0 R
001 1 --> 001 1 R
002 0 --> 003 1 L
002 1 --> 002 1 R
003 0 --> 004 0 L
003 1 --> 003 1 L
004 0 --> jmp 1 L > check_a
004 1 --> 005 1 L
005 0 --> 000 1 R
005 1 --> 005 1 L

;----------------------------------------------------------------------------

check_a:

; check marking on a to see if we're done multiplying
000 0 --> 001 0 L
000 1 --> 000 1 L
001 0 --> jmp 0 L > exit
001 1 --> 002 1 L
002 0 --> jmp 1 R > mark_a
002 1 --> 002 1 L

;----------------------------------------------------------------------------

exit:

; we're done; erase b and move head to right side of p
000 0 --> 001 0 L
000 1 --> 000 0 L
001 0 --> 001 0 R
001 1 --> 002 0 R
002 0 --> 003 0 R
002 1 --> 002 0 R
003 0 --> 004 0 R
003 1 --> 003 1 R
004 0 --> hlt 0 L
004 1 --> nop