;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Nim.asm
;;;;; by David Kosbie
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Program Description
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; This assembly language program plays the game of Nim against
; a human opponent.
;
; Nim is a children's game where there is a pile of sticks, and two
; players take turns picking up 1, 2, or 3 sticks.  The player who
; picks up the last stick wins.
;
; There is a winning strategy to Nim:  always try to leave a multiple
; of 4 sticks in the pile.  Think about why....

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Register and Memory Usage
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; R1 = Total number of sticks
; R2 = Number of sticks picked up (game over when R2 >= R1)
; R3 = Turn:  0 = computer, 1 (non-zero) = human
; R9 = user input:  number of sticks user picks up this turn

; RA = constant 0
; RB = constant 1

; RC thru RE = temporary registers
;              These may be used differently in each step.

; 0xFE = 1 if human goes first, 0 if computer goes first
; 0xFF = # of sticks initially in the pile

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 0:  Set initial register values
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

StartOfProgram:
  load R1,[TotalSticks]
  load R2, 0   ; initially, 0 sticks picked up
  load R3,[SecondTurn]
  load RA, 0
  load RB, 1

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 1:  Print Intro Message
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; This code is almost precisely that from helloWorld.asm,
;;; (though registers were modified, as were labels).

BeginStep1:
   load  RC,IntroText          ;the start of the string
   load  R0,0                  ;load R0 with string terminator
NextIntroText:
   load  RF,[RC]               ;get character and print it on screen
   addi  RC,RC,RB              ;increase address
   jmpEQ RF=R0,StartOfMainLoop ;when string-terminator, then ready
   jmp   NextIntroText         ;next character

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 2:  Start of Main Loop:  Check for Victory
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; Recall that:
; R1 = Total number of sticks
; R2 = Number of sticks picked up (game over when R2 >= R1)
; Hence, game is over if R1 <= R2

StartOfMainLoop:
  move  R0,R2            ; load R0 with R2 for comparison
  jmpLE R1<=R0,GameOver  ; If total sticks <= sticks picked up then game is over
  jmp   EndStep2
GameOver:
  load  R0,0
  jmpEQ R3=R0,IWin
  load  RC,YouWinText
  jmp   PrintFinishedMessage
IWin:
  load  RC,IWinText
  jmp   PrintFinishedMessage
EndStep2:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 3:  Print board status
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  load  RF,10    ; print a newline
  move  R0,R1    ; total # of sticks
  move  RC,R2    ; # of sticks picked up
  addi  RC,RC,RB ; add 1 to # of sticks picked up
  load  RD,0     ; Use RD to print a "*" every 4th character
                 ; by using it as an offset into a string of
                 ; length 4, and then resetting RD to 0 each
                 ; time it exceeds 4 (by mod'ing it against 4)
PrintStick:
  ;; increment RD,  but make sure it is not larger than 4
  addi  RD,RD,RB ; increment RD
  ;; set RD to RD mod 4
  load RE,0x03   ; use RE to store temporary value 0x03 for mod via and
  and  RD,RE,RD  ; this sets RD to (RD mod 4)

  ;; load RE with StickText + RD
  load  RE,StickText
  addi  RE,RE,RD

  ;; Print out [RE]
  load  RF,[RE]

  ;; Increment stick counter and loop
  addi  RC,RC,RB
  jmpLE RC<=R0,PrintStick;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 4:  Change turn (human->computer or computer->human)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  load  R0,0
  jmpEQ R3=R0,SetMoveToUser
SetMoveToComputer:
  load  R3,0
  jmp   DoneChangingTurn
SetMoveToUser:
  load  R3,1
DoneChangingTurn:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 5:  If User's turn, perform user's move
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;
;;; Step 5.0:  If Not User's Turn, go to computer's turn
;;;;;;;;;

  load  R0,0
  jmpEQ R3=R0,ComputersTurn

;;;;;;;;;
;;; Step 5.1:  Print user message
;;;;;;;;;

  load    RC,UsersTurnText         ;load message telling user how to move
  load    R0,0                     ;load R0 with string terminator
NextUsersTurnText:
  load    RF,[RC]                  ;get character and print it on screen
  addi    RC,RC,RB                 ;increase address
  jmpEQ   RF=R0,EndOfUsersTurnText ;when string-terminator, then ready
  jmp     NextUsersTurnText        ;next character
EndOfUsersTurnText:

;;;;;;;;;
;;; Step 5.2:  Halt, to allow for user input
;;;;;;;;;

  halt

;;;;;;;;;
;;; Step 5.3:  Verify user input is valid
;;;;;;;;;

  ;; first, check if R9 is too big (> 3)
  load  R0,3
  jmpLE R9<=R0,NotTooBig
  ;if we get here, R9 is too big, so set it equal to 3
  load  R9,3

NotTooBig:
  ;; second, check if R9 is too small (< 1)
  move  R0,R9
  jmpLE RB<=R0,NotTooSmall
  ;if we get here, R9 is too small, so set it equal to 1
  load  R9,1

NotTooSmall:

;;;;;;;;;
;;; Step 5.4:  Pick up user's sticks and continue game
;;;;;;;;;

  addi R2,R2,R9        ; Add user's sticks to R2 (# of sticks picked up)
  jmp  StartOfMainLoop ; And continue game's main loop

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 6:  If Computer's turn, perform computer's move
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Note:  We only get here if it is the computer's turn.

;; RE = # of sticks computer will pick up

ComputersTurn:

;;;;;;;;;
;;; Step 6.1:  Set RE to # of sticks computer will pick up
;;;;;;;;;

  ;; # of sticks to pick up = (# of sticks remaining) mod 4
  ;; So first set RD to # of sticks remaining
  ;; To do that, set RC to -(# of sticks picked up), then add R2 (total # of sticks)

  ;; load RC with -(# of sticks picked up)
  move RC,R2     ;; RC <- # of sticks remaining
  load RD,0xFF   ;; To negate RC, must complement
  xor  RC,RC,RD  ;; by xor'ing against 0xFF
  addi RC,RC,RB  ;; and then adding 1

  ;; set RD to R1+RC = (total # of sticks) - (# of sticks picked up)
  move RD,RC
  addi RD,RD,R1

  ;; set RE (# of sticks to pick up) to RD (# of sticks remaining) mod 4
  load RE,0x03
  and  RE,RE,RD

  ;; if RE equals 0 (so the human should win), then set RE to 1 (bummer)
  load R0,0
  jmpEQ RE=R0,UserShouldWinSoPickJustOne
  jmp SelectedSticksToPickUp
UserShouldWinSoPickJustOne:
  load RE,1
SelectedSticksToPickUp:  

;;;;;;;;;
;;; Step 6.2:  Pick up computer's sticks and continue game
;;;;;;;;;

  addi R2,R2,RE        ; Add computer's sticks to R2 (# of sticks picked up)
  jmp  StartOfMainLoop ; And continue game's main loop
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 7:  Print Finished Message
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; This code is almost precisely that from helloWorld.asm,
;;; (though registers were modified, as were labels).
;;; Also, RA is preloaded with the message (IWinText or YouWinText)

PrintFinishedMessage:
  load    R0,0               ;load R0 with string terminator
NextEndText:
  load    RF,[RC]            ;get character and print it on screen
  addi    RC,RC,RB           ;increase address
  jmpEQ   RF=R0,EndOfProgram ;when string-terminator, then ready
  jmp     NextEndText        ;next character

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Step 8:  End of Program
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

EndOfProgram:
  halt                 ; we are done, so halt
  jmp  StartOfProgram  ; but if user hits Run again, start over

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; Data
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

IntroText:
  db  10,10,"Nim:",10
  db  "Last stick wins!"
  db  0           ; string-terminator
UsersTurnText:
  db  10,"1/2/3->R9,Run"
  db  0           ; string-terminator
IWinText:
  db 10,"I win!!!",10
  db  0           ; string-terminator
YouWinText:
  db 10,"You win!!!",10
  db  0          ; string-terminator
StickText:
  db "*+++"      ; This does not need a string-terminator

org 0xFE  ;; Place SecondTurn and TotalSticks at end of memory
          ;; so they are easy for user to set on each run

SecondTurn:
  db  0    ; 0 = computer, 1 (non-zero) = human
TotalSticks:
  db  0x0C

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;; End of Nim.asm
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;