; bitRAKE
; 2008.12.31

format PE64 Console 5.0 at $100000

include 'Win64W.inc'

section '' code readable writeable executable

entry $
; Instead of creating a state transition table, itterate through the command
; line parameters and respond based on current state and tape value. This is
; slower, but less code.
	push rsp rsp rsp
	pop rcx rdx r8
	enter 8*20,0
	xor r9,r9		; globbing = FALSE
	lea rax,[rbp-8*15]
	mov [rbp-8*16],rax	; STARTUPINFO
	mov dword[rax],0	; STARTUPINFO.cb set to zero
	call [MSVCRT.__getmainargs]
	mov rsi,[rbp]
	lodsq   ; skip program name
	lodsq
	xchg eax,ecx ; #32#
	call [MSVCRT.atol]
	mov ebp,eax	; starting bit, in the middle
	mov [max_steps],eax
	add eax,7	; round up
	shr eax,3	; one bit for each step, converted to bytes
	lea ecx,[rax*2]	; in each direction
	mov edx,1
	call [MSVCRT.calloc] ; because it zeroes the memory
	xchg rax,rdi

	mov ecx,ebp	; min
	mov edx,ebp	; max


	mov bl,'1'	; starting state is "1"
.outer:
	; retrieve tape symbol: '0' or '1'
	mov bh,0
	bt [rdi],ebp
	adc bh,"0"
	push rsi
	jmp .inner

.next:	pop rsi
	add esi,5*8
	
; this should never happen...
	cmp qword [rsi],0
	jne .inner
	; early out, no transition from current state/tape
	mov eax,[max_steps]
	mov [steps],eax
	jmp .fail

.inner:
	push rsi
	; does state match?
	lodsq
	cmp [rax],bl
	jne .next
	; does tape match?
	lodsq
	cmp [rax],bh
	jne .next

	; new state: allow any byte, '0' is HALT state
	lodsq
	mov bl,[rax]

	; update tape: only two state tape initialized to zero
	lodsq
	btr [rdi],ebp ; assume zero
	cmp byte [rax],"1"
	jne @F
	bts [rdi],ebp ; set to one
@@:
	; move tape position: -1, 0, 1
	lodsq
	cmp byte [rax],"0"
	je @F
	sbb eax,eax
	add ebp,eax
	not eax
	sub ebp,eax
@@:

	pop rsi
	pop rsi

	; update tape bounds
	cmp ebp,ecx
	cmovc ecx,ebp ; update lower bound
	cmp edx,ebp
	cmovc edx,ebp ; update upper bound

	; count steps
	inc [steps]

	; end if HALT state
	cmp bl,'0'
	je .output

	; end if MAX_STEPS has been reached
	mov eax,[steps]
	cmp eax,[max_steps]
	jc .outer

.fail:	mov ecx,'2'
	; force carry to exit loop
	xor ebx,ebx
	xchg eax,esi
	jmp .two

.output:

	; read a bit and output zero or one
	mov ebp,ecx
	mov ebx,edx
@@:	xor ecx,ecx
	bt [edi],ebp
	adc ecx,"0"
	inc ebp
.two:	call [MSVCRT.putchar]
	cmp ebx,ebp
	jnc @B

	; output step count
	mov rcx,step_count
	mov edx,[steps]
	call [MSVCRT.printf]
	
	call [MSVCRT.exit]

data import
	library	MSVCRT,'MSVCRT'

	import	MSVCRT,\
		MSVCRT.__getmainargs,'__getmainargs',\
		MSVCRT.atol,'atol',\
		MSVCRT.calloc,'calloc',\
		MSVCRT.exit,'exit',\
		MSVCRT.printf,'printf',\
		MSVCRT.putchar,'putchar'
end data

step_count db 10,13,'%d',10,13,?
max_steps	dd ?
steps		dd ?