; assembly korvaa rubyn, eikö?
section .bss
input resb 10
output resb 50
A resb 2000000
B resb 2000000
section .text
global _start
_start:
; Read and parse input
mov rax, 0
mov rdi, 0
mov rsi, input
mov rdx, 10
syscall
call parse
; rdi = rax/2+rax%2
mov rdi, rax
shr rdi, 1
mov rsi, 1
and rsi, rax
add rdi, rsi
call solve
mov rax, 1
mov rdi, 1
; rsi and rdx retained from solve
; Swap rdx <-> rsi
xor rdx, rsi
xor rsi, rdx
xor rdx, rsi
syscall
; Exit
mov rax, 60
mov rdi, 0
syscall
parse:
mov rax, 0
mov rdi, input
mov rsi, 0
.loop:
mov sil, [rdi]
sub rsi, '0'
cmp rsi, 0
jl .done
cmp rsi, 9
jg .done
mov rdx, 10
imul rax, rdx
add rax, rsi
inc rdi
jmp .loop
.done:
ret
solve:
; rax = n, rdi = n/2+n%2
; Fill A and B
mov rsi, 0
.fill_loop:
mov rbx, A
mov [rbx,rsi*4], eax
mov rbx, B
mov [rbx,rsi*4], esi
inc rsi
; if rsi < rdi: continue
cmp rsi, rdi
jl .fill_loop
; Iterate until some m bit string ends
.iterate:
mov rsi, 0
.it_loop:
mov rbx, A
mov ecx, [rbx + rsi*4]
mov rbx, B
mov edx, [rbx + rsi*4]
mov rbp, rcx
shr rbp, 1
cmp rdx, rbp
jg .it_greater
.it_less:
sub rcx, rdx
dec rcx
jmp .it_over
.it_greater:
mov rbx, rdx
mov rdx, rcx
sub rdx, rbx
mov rcx, rbx
dec rcx
.it_over:
cmp rcx, 0
jne .skip
cmp rdx, 0
je .iterate_over
.skip:
mov rbx, A
mov [rbx + rsi*4], ecx
mov rbx, B
mov [rbx + rsi*4], edx
inc rsi
cmp rsi, rdi
jl .it_loop
jmp .iterate
.iterate_over:
; rsi contains optimal m
mov rbx, rsi
mov rsi, 0 ; string index
mov rcx, 0 ; current bit
.result_loop:
mov rbp, rax
shr rbp, 1
cmp rbx, rbp
jg .rs_greater
.rs_less:
sub rax, rbx
dec rax
jmp .rs_over
.rs_greater:
mov rdx, rbx
mov rbx, rax
sub rbx, rdx
mov rax, rdx
dec rax
xor rcx, 1
.rs_over:
add rcx, '0'
mov rdx, output
mov [rdx + rsi], cl
sub rcx, '0'
inc rsi
cmp rax, 0
jg .result_loop
mov rdx, output
mov [rdx + rsi], byte `\n`
inc rsi
ret
