Bootable, real mode, NIM game (also works on DOS)

nim.S

#
# MIT License
#
# Copyright (c) 2021 Davidson Francis <davidsondfgl@gmail.com>
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
#

.code16

.macro dbg
	xchgw %bx, %bx
.endm

#
# Build instructions:
# gcc nim.S -o nim.img -Xlinker -T linker.ld -nostdinc -nostdlib
#
# linker.ld content:
# 	OUTPUT_FORMAT(binary)
#	SECTIONS
# 	{
#		. = 0x7c00;
#		.text :
#		{
#			*(.*)
#		}
# 	}
#
# For DOS builds, append -DDOS in the GCC line and edit the
# start address in the linker from 0x7C00 to 0x100. Also,
# the extension *must* be .COM.
#

#
# 'Relocate' the label for the address on the second stage.
#
# We 'relocate' here so that we can use the 512 bytes of the
# first sector for something useful, instead of leaving much
# of it empty.
#
#ifdef DOS
	#define L(l) \
		((l))
#else
	#define L(l) \
		((l) - _start + SEC_STAGE_ADDR)
#endif

#
# Make the image size multiple of 512
#
#define ROUND_SIZE(size) \
	(((size) + (512)-1) & -(512))

#
# VirtualBox requires the image to be multiple of 512-bytes/sector.
#
#define MAKE_VBOX_HAPPY 1

.global _start
.section .text,"ax",@progbits

###############################################################################
#                     System Helpers & Boot stuff                             #
###############################################################################

_start:
#ifdef DOS
	jmp 	main_screen
#endif

#ifndef DOS
	# Setup stack
	xor 	%ax, %ax
	mov 	%ax, %ss
	mov 	%ax, %ds
	mov 	$0x7C00, %sp

	# Read remaining sectors
	xor 	%ax, %ax
	mov 	%ax, %es
	mov 	$SEC_STAGE_ADDR, %bx
	mov 	$SEC_STAGE_SIZE, %al
	call 	read_sectors

	# Jump to ther
	jmp 	$0x100, $main_screen - _start

# -----------------------------------------------
# read_sectors: Reads a given amount of sectors
# from the bootable media.
#
# Parameters:
#   al     = number of sectors to be read
#   dl     = drive number
#   es:bx  = target address
#
# Return:
#   ah     = Status operation
#   al     = Number of sectors read
#   CF     = Carry flag set if error
#
# Note: This function do not take care about the
# media geometry and assumes that the sector
# number is correct (i.e: 6 bits) and fits
# accordingly with the number of heads
# and tracks.
# -----------------------------------------------
read_sectors:
	mov 	$2, %ah
	mov 	$0, %ch
	mov 	$1, %cl
	mov 	$0, %dh
	int 	$0x13
	jc 		1f
	ret
1:
	xor 	%ax, %ax
	int 	$0x13
	jmp 	read_sectors
	ret
#endif

# ----------------------------------------------------
# read_number: Read a number with the arrow keys (up
# and down) from 0 to 7, Enter selects the number.
#
# Returns:
#   cx: Number read.
# ----------------------------------------------------
read_number:
	call 	read_kbd
	cmp		$KBD_UP, %ah
	jne		1f
	add 	$1, %cx
	and 	$7, %cx
	jmp		3f
1:
	cmp		$KBD_DOWN, %ah
	jne		2f
	sub 	$1, %cx
	and 	$7, %cx
	jmp 	3f
2:
	cmp 	$KBD_ENTER, %ah
	jne 	read_number
	jmp 	4f
3:
	# Get cursor position
	push 	%cx
	xor		%bx, %bx
	mov 	$3, %ah
	int 	$0x10
	# Adjust column
	sub 	$1, %dl
	mov 	$2, %ah
	int 	$0x10
	# Draw again
	pop 	%cx
	mov 	%cl,  %al
	add 	$'0', %al
	call 	print_char

	jmp 	read_number
4:
	ret

# ---------------------------------------------
# read_kbd: Reads a keypress from the keyboard
#
# Returns:
#   ah: Scan code
#   al: ASCII Character code
# ---------------------------------------------
read_kbd:
	xor %ax, %ax
	int $0x16
	ret

# ---------------------------------------
# print: Print a string to screen
#
# Parameters:
#   si: pointer to string
# ---------------------------------------
print:
	mov 	$0xE, %ah
	mov 	0x0007, %bx
.print_char:
	lodsb
	cmp 	$0, %al
	je 		.done
	int 	$0x10
	jmp		.print_char
.done:
	ret

# ---------------------------------------------
# print_char: Print a character to the screen
#
# Parameters:
#   al: character
# ---------------------------------------------
print_char:
	mov 	$0xE, %ah
	mov 	0x0007, %bx
	int 	$0x10
	ret

# ---------------------------------------------
# clear_screen: Clear the screen
# ---------------------------------------------
clear_screen:
	# Clear screen
	push 	%ax
	push 	%bx
	push 	%cx
	push	%dx
	mov 	$0x0700, %ax # Scroll down, whole window
	mov 	$0x07,   %bh # White on black
	mov 	$0x0000, %cx # Row 0,  Col 0
	mov 	$0x184f, %dx # Row 24, Col 79
	int 	$0x10
	# Set cursor to top
	mov 	$0x2,    %ah
	mov 	$0x0,    %bh
	mov 	$0x0000, %dx
	int 	$0x10
	pop 	%ax
	pop 	%bx
	pop 	%cx
	pop 	%dx
	ret

###############################################################################
# Game helpers                                                                #
###############################################################################
# --------------------------------------------
# draw_title: Draw game title
# --------------------------------------------
draw_title:
	call 	clear_screen
	mov 	$L(str_game_title), %si
	call	print
	ret

# --------------------------------------------
# draw_sticks: Draw the sticks remaining
# --------------------------------------------
draw_sticks:
	xor		%cx, %cx
1:
	mov 	%cl, %al
	add 	$49, %al
	call 	print_char
	mov 	$L(str_stick_ddots), %si
	call 	print
	mov 	%cx, %si
	shl 	$1,  %si
	add 	$L(sticks), %si
	mov 	(%si), %si
	cmp 	$0, %si
	je 		2f
	sub 	$1, %si
	shl 	$1, %si
	add 	$L(str_sticks_vec), %si
	mov 	(%si), %si
	mov 	%si,   %dx
	call 	print
	mov 	%dx, %si
	call 	print
	mov 	%dx, %si
	call 	print
2:
	add 	$1, %cl
	cmp 	$4, %cl
	jl 		1b
	ret

###############################################################################
# Game entry point                                                            #
###############################################################################
main_screen:
	mov 	$L(str_game_title), %si
	call	print
	mov 	$L(str_game_explanation), %si
	call	print

	mov 	$L(str_who_starts), %si
	call 	print
	mov 	$L(str_arrow), %si
	call	print
	mov 	$L(str_you), %si
	call	print
	mov 	$L(str_empty_space), %si
	call	print
	mov 	$L(str_me), %si
	call 	print

# Reads who starts
	xor		%dx, %dx
who_starts:
	call 	read_kbd
	cmp		$KBD_UP, %ah
	jne		1f
	sub 	$1, %dx
	and 	$1, %dx
	jmp		3f
1:
	cmp		$KBD_DOWN, %ah
	jne		2f
	add 	$1, %dx
	and 	$1, %dx
	jmp 	3f
2:
	cmp 	$KBD_ENTER, %ah
	jne 	who_starts
	jmp 	.out_who_starts
3:
	# Get cursor position
	push 	%dx
	xor		%bx, %bx
	mov 	$3, %ah
	int 	$0x10
	# Adjust row
	sub 	$2, %dh
	mov 	$2, %ah
	int 	$0x10
	# Draw again
	pop 	%dx
	mov 	%dx, %si
	shl 	$2, %si
	add 	$L(str_arrow), %si
	call 	print
	mov 	$L(str_you), %si
	call 	print
	mov 	%dx, %si
	add 	$1, %si
	and 	$1, %si
	shl 	$2, %si
	add 	$L(str_arrow), %si
	call 	print
	mov 	$L(str_me), %si
	call 	print
	jmp 	who_starts
.out_who_starts:

	# Save current turn
	movb 	%dl, (L(curr_turn))

game_loop:
	movb 	(L(sticks_count)), %dl
	cmp 	$0, %dl
	jle 	game_loop_end
	call 	think
	jmp 	game_loop
game_loop_end:

	# Elects who win
	call 	draw_title
	movb 	(L(curr_turn)), %dl
lose:
	cmp 	$COMPUTER_TURN, %dl
	jne 	win
	mov 	$L(str_lose), %si
	call 	print
	jmp 	wait_key
win:
	mov 	$L(str_win), %si
	call 	print
wait_key:
	mov 	$L(str_play_again), %si
	call 	print
	call 	read_kbd

	# Reset everything
	movb 	$16, (L(sticks_count))
	mov 	$L(sticks), %si
	movw 	$1, 0(%si)
	movw 	$3, 2(%si)
	movw 	$5, 4(%si)
	movw 	$7, 6(%si)

	# Start again
	call 	clear_screen
	jmp 	main_screen

# Fill remaining bytes
.fill 510-(.-_start), 1, 0
.word 0xAA55

###############################################################################
# 2stage boot: PC and Player movements                                        #
###############################################################################
# --------------------------------------------
# think: PC and Player movements
# --------------------------------------------
think:
	call 	draw_title
	call 	draw_sticks

.computer_turn:
	mov 	(L(curr_turn)), %dl
	cmp 	$COMPUTER_TURN, %dl
	jne 	.player_turn

	mov 	$L(str_think_pc), %si
	call 	print

	call 	read_kbd

	# Count amnt of heaps > 1
	xor 	%cx, %cx
	xor 	%dx, %dx
	mov 	$L(sticks), %si
.count_sticks:
	cmp 	$1, 0(%si)
	jg 		1f
	jmp 	2f
1:
	add 	$1, %dx
2:
	add 	$1, %cx
	add 	$2, %si
	cmp 	$4, %cx
	jl 		.count_sticks
	push 	%dx
	mov 	%sp, %bp

.nim_sum:
	# Calculate NIM sum
	mov 	$L(sticks), %si
	mov 	0(%si),  %dx
	xor		2(%si),  %dx
	xor		4(%si),  %dx
	xor		6(%si),  %dx

	# Check if there is a good movement or not
	cmp 	$0, %dx
	jne 	.recalculate_nim_sum

.only_one:
	#
	# Too bad, if the player keeps playing like this the
	# computer will lose.
	#
	xor 	%cx, %cx
1:
	mov 	(%si), %ax
	cmp 	$0,    %ax
	jne 	2f
	add 	$1,    %cx
	add 	$2,    %si
	cmp 	$4,    %cx
	jl      1b
2:
	sub 	$1,    (%si)
	sub 	$1,    (L(sticks_count))
	jmp 	.finish

	#
	# If NIM sum differs from 0, great, we *will* win. We just
	# need to recalculate the amount of pieces.
	#
.recalculate_nim_sum:
	xor 	%cx, %cx
	mov 	$L(sticks), %si
1:
	mov 	(%si), %ax
	mov 	%ax, %bx
	xor 	%dx, %bx    # bx = p ^ nimsum, ax = p, dx = nimsum
	cmp 	%ax, %bx
	jl 		2f
	add 	$1,  %cx
	add 	$2,  %si
	cmp 	$4,  %cx
	jl      1b
2:
	#
	# We have 2 options here:
	# a) More than one heap with more than one stick
	# b) Exactly one heap with more than one stick
	#
	# The option b) do not conforms with the maths as
	# expected and we fall in a case were we remove
	# n or n-1 sticks from that column. So is necessary
	# to bifurcate these two scenarios here.
	#
	cmp 	$1, (%bp)
	jne 	.scenario_a

.scenario_b:
	movb 	(L(sticks_count)), %bl
	subb 	%al, %bl
	mov 	%bx, %ax

	#
	# We need to leave a odd numbers of stickers to the player
	# If odd: remove all the sticks from the line
	# If even: remove all but one sticks from the line
	#
	andb 	$1, %al
	cmpb 	$0, %al
	je 		.even
.odd:
	movw 	$0,  (%si)
	movb 	%bl, (L(sticks_count))
	jmp 	.finish
.even:
	movw 	$1, (%si)
	addb 	$1, %bl
	movb 	%bl, (L(sticks_count))
	jmp 	.finish

.scenario_a:
	# Now we proceed as usual
	mov 	%bx, (%si)
	sub 	%bx, %ax
	sub 	%ax, (L(sticks_count))

	# Set turn to player
.finish:
	movb 	$PLAYER_TURN, (L(curr_turn))
	add 	$2, %sp
	ret

.player_turn:
	mov 	$L(str_think_askrow), %si
	call 	print

	# Read rows
.read_rows:
	mov 	$1,   %cx
	mov 	$'1', %al
	call 	print_char
1:
	call 	read_number
	# Check if selected row is valid
	cmp 	$0, %cx
	je 		1b
	cmp 	$4, %cx
	jg		1b
	# Check if selected row is not empty
	mov 	%cx, %si
	sub 	$1,  %si
	shl 	$1,  %si
	add 	$L(sticks), %si
	mov 	(%si), %si
	cmp 	$0, %si
	je 		1b
	sub 	$1, %cx # make row 0 based
	push 	%cx
	mov 	%sp, %bp

	# Read sticks amount
.read_amnt:
	mov 	$L(str_newline), %si
	call 	print
	mov 	$L(str_think_askstick), %si
	call 	print
	mov 	$1,   %cx
	mov 	$'1', %al
	call 	print_char
2:
	call 	read_number
	# Check if selected amount is valid
	cmp 	$0, %cx
	je 		2b
	# Check if selected amount not exceeds the sticks amnt
	mov 	(%bp), %dx
	mov 	%dx, %si
	shl 	$1,  %si
	add 	$L(sticks), %si
	mov 	(%si), %si
	cmp 	%si, %cx
	jg 		2b

	# Decrement the row sticks
	mov 	(%bp), %dx
	mov 	%dx, %si
	shl 	$1,  %si
	add 	$L(sticks), %si
	sub 	%cx, (%si)

	# Decrement sticks count
	sub 	%cx, (L(sticks_count))

	# Set turn to computer
	movb 	$COMPUTER_TURN, (L(curr_turn))

	# 'Pop' cx and return
	add 	$2, %sp
	ret

#
# Strings
#
str_game_title:
	.ascii " _______  _______  _______ \r\n"
	.ascii "|    |  ||_     _||   |   |\r\n"
	.ascii "|       | _|   |_ |       |\r\n"
	.asciz "|__|____||_______||__|_|__| by Theldus\r\n\r\n"

str_game_explanation:
	.ascii "The NIM game consists of removing the sticks from the table, \r\n"
	.ascii "the amount you want, a single row at a time. The last to \r\n"
	.asciz "remove the sticks LOSES!! Good luck!!!\r\n\r\n"

str_who_starts:
	.asciz "Who starts? (UP/DOWN, Enter select): \r\n"
str_you:
	.asciz "You\r\n"
str_me:
	.asciz "Me\r\n"
str_arrow:
	.asciz "-> "
str_empty_space:
	.asciz "   "

str_stick_ddots:
	.asciz ": \r\n"
str_stick_1: .asciz "      \xdb\xdb\r\n"
str_stick_2: .asciz "      \xdb\xdb \xdb\xdb\r\n"
str_stick_3: .asciz "      \xdb\xdb \xdb\xdb \xdb\xdb\r\n"
str_stick_4: .asciz "      \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb\r\n"
str_stick_5: .asciz "      \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb\r\n"
str_stick_6: .asciz "      \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb\r\n"
str_stick_7: .asciz "      \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb \xdb\xdb\r\n"
str_sticks_vec:
	.word L(str_stick_1), L(str_stick_2), L(str_stick_3), L(str_stick_4)
	.word L(str_stick_5), L(str_stick_6), L(str_stick_7)

str_think_pc:
	.asciz "\r\nThats my turn, can I play? (press any key) "
str_think_askrow:
	.asciz "\r\nChoose the row you want (Up/Down arrows, Enter to select): "
str_think_askstick:
	.asciz "How many sticks you want to remove? (Up/Down arrows, Enter to select): "

str_newline:
	.asciz "\r\n"

str_lose:
	.ascii "        @@@ @@@  @@@@@@  @@@  @@@      @@@       @@@@@@   @@@@@@ @@@@@@@@\r\n"
	.ascii "         @@! !@@ @@!  @@@ @@!  @@@      @@!      @@!  @@@ !@@     @@!\r\n"
	.ascii "          !@!@!  @!@  !@! @!@  !@!      @!!      @!@  !@!  !@@!!  @!!!:!\r\n"
	.ascii "           !!:   !!:  !!! !!:  !!!      !!:      !!:  !!!     !:! !!:\r\n"
	.asciz "           .:     : :. :   :.:: :       : ::.: :  : :. :  ::.: :  : :: :::\r\n\r\n"
str_win:
	.ascii "                   __ __  ___  __ __      __    __ ____ ____  \r\n"
	.ascii "                  |  |  |/   \\|  |  |    |  |__|  |    |    \\ \r\n"
	.ascii "                  |  |  |     |  |  |    |  |  |  ||  ||  _  |\r\n"
	.ascii "                  |  ~  |  O  |  |  |    |  |  |  ||  ||  |  |\r\n"
	.ascii "                  |___, |     |  :  |    |  `  '  ||  ||  |  |\r\n"
	.ascii "                  |     |     |     |     \\      / |  ||  |  |\r\n"
	.asciz "                  |____/ \\___/ \\__,_|      \\_/\\_/ |____|__|__|\r\n\r\n"
str_play_again:
	.asciz "                     =-=- Press any key to play again -=-="

#
# Game data
#
curr_turn:    .byte 0xF
sticks_count: .byte 16
sticks:       .word 1,3,5,7

#
# Constants
#

# Game
.equ PLAYER_TURN,   0
.equ COMPUTER_TURN, 1

# 2 Stage
.equ SEC_STAGE_SEG,  0x100
.equ SEC_STAGE_ADDR, 0x1000
.equ SEC_STAGE_SIZE, ROUND_SIZE(.-_start) >> 9

# Keyboard scan codes
.equ KBD_UP,    0x48
.equ KBD_DOWN,  0x50
.equ KBD_ENTER, 0x1C

#if MAKE_VBOX_HAPPY == 1
	.fill ROUND_SIZE(.-_start)-(.-_start), 1, 0
#endif