adventofcode2023/17/main.s

%include "utils.s"

global _start
[bits 32]
[section .text]

; len +2 for padding
%define LINE_LEN (141+2)
%define FILENAME "input"
;%define LINE_LEN (13+2)
;%define FILENAME "input_test"

%define DBG_PRINT

_start:

; convert input file to useful data
mov esi, file
mov edi, cost
convert_input:
lodsb
cmp al, 10 ; \n
je .cont
cmp al, '$'
jne .num
mov al, 0xFF
stosb
jmp .cont
.num:
sub al, '0'
stosb
.cont:
cmp esi, file.over
jb convert_input

; im lazy so doing dijkstra
; thanks wikipedia

; for each vertex v in Graph.Vertices:
;   dist[v] ← INFINITY
;   prev[v] ← UNDEFINED
;   add v to Q
mov ecx, LINE_LEN*LINE_LEN*32
mov eax, 0xffffffff
mov edi, dist
rep stosd
mov ecx, LINE_LEN*LINE_LEN*32
mov eax, 0xffffffff
mov edi, prev
rep stosd
mov ecx, LINE_LEN*LINE_LEN*32
mov eax, 1
mov edi, q
rep stosb

; for all real dir:
;     dist[source@dir] ← 0
mov dword [dist+((((LINE_LEN*32)+(32*1)))|0b00_000)*4], 0
mov dword [dist+((((1*(LINE_LEN*32))+(32*1)))|0b10_000)*4], 0



; while Q is not empty and any dist[u] in Q < inf:
;   u ← vertex in Q with min dist[u]
while_q:
xor ebp, ebp         ; test node
mov ecx, 0xffffffff  ; best dist
mov edx, 0xffffffff  ; best node
.find_min:
cmp byte [q+ebp], 1
jne .cont
cmp [dist+ebp*4], ecx
cmovb ecx, [dist+ebp*4]
cmovb edx, ebp
.cont:
inc ebp
cmp ebp, LINE_LEN*LINE_LEN*32
jb .find_min
cmp ecx, 0xffffffff
je while_q_done

%ifdef DBG_PRINT
pushad
call newline
mov ebp, edx
mov eax, edx
xor edx, edx
shr eax, 5
mov ebx, LINE_LEN
div ebx
call print_dec
call space
mov eax, edx
call print_dec
call space
mov eax, ebp
and eax, 0b11111
call print_dec
call space
mov eax, ecx
call print_dec
call newline
popad
%endif

; remove u from Q
mov byte [q+edx], 0

; for each neighbor v of u still in Q:
;   alt ← dist[u] + Graph.Edges(u, v)
;   if alt < dist[v]:
;       dist[v] ← alt
;       prev[v] ← u
mov ebp, LINE_LEN*32 ; whatever
for_neighbor:
; turning neighbor 0
neighbor_0:
; neighbors += v@dir(u, ~u.dir & 0b10_000)
mov ebx, edx
not ebx
and ebx, 0b10000
; tmp := 32
mov edi, 32
; bt dir, 4
bt ebx, 4
; if CF tmp := LINE_LEN
cmovc edi, ebp
; bt dir, 3
; if CF tmp := -tmp
mov esi, edi
neg esi
bt ebx, 3
cmovc edi, esi
mov eax, edi
; v.dir := dir
or edi, ebx
; v := u + tmp
; CheckBounds(v)
; Graph.Edges(u, v) := cost(v)
; v := v + tmp
; CheckBounds(v)
; Graph.Edges(u, v) += cost(v)
; v := v + tmp
; CheckBounds(v)
; Graph.Edges(u, v) += cost(v)
; v := v + tmp
; CheckBounds(v)
; Graph.Edges(u, v) += cost(v)
mov ebx, eax
mov esi, edx
and esi, ~0b11111
add edi, esi  ; v := u + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_1 ; off graph
mov esi, eax ; Graph.Edges(u, v) := cost(v)
add edi, ebx ; v := v + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_1 ; off graph
add esi, eax ; Graph.Edges(u, v) += cost(v)
add edi, ebx ; v := v + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_1 ; off graph
add esi, eax ; Graph.Edges(u, v) += cost(v)
add edi, ebx ; v := v + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_1 ; off graph
add esi, eax ; Graph.Edges(u, v) += cost(v)
; alt ← dist[u] + cost(v)
; if alt < dist[v]:
;     dist[v] ← alt
;     prev[v] ← u
add esi, ecx
%ifdef DBG_PRINT
pushad
call space
mov esi, eax
mov eax, edi
shr eax, 5
mov ecx, LINE_LEN
xor edx, edx
div ecx
call print_dec
call space
mov eax, edx
call print_dec
call space
mov eax, edi
and eax, 0x1f
call print_dec
call space
mov eax, esi
call print_dec
call newline
popad
%endif
cmp esi, [dist+edi*4]
jae neighbor_1 ; not better
mov [dist+edi*4], esi
mov [prev+edi*4], edx
; turning neighbor 1
neighbor_1:
; neighbors += v@dir(u, (~u.dir & 0b10_000) | 0b01_000)
mov ebx, edx
not ebx
and ebx, 0b10000
or ebx, 0b01000
; tmp := 32
mov edi, 32
; bt dir, 4
bt ebx, 4
; if CF tmp := LINE_LEN
cmovc edi, ebp
; bt dir, 3
; if CF tmp := -tmp
mov esi, edi
neg esi
bt ebx, 3
cmovc edi, esi
mov eax, edi
; v.dir := dir
or edi, ebx
; v := u + tmp
; CheckBounds(v)
; Graph.Edges(u, v) := cost(v)
; v := v + tmp
; CheckBounds(v)
; Graph.Edges(u, v) += cost(v)
; v := v + tmp
; CheckBounds(v)
; Graph.Edges(u, v) += cost(v)
; v := v + tmp
; CheckBounds(v)
; Graph.Edges(u, v) += cost(v)
mov ebx, eax
mov esi, edx
and esi, ~0b11111
add edi, esi  ; v := u + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_2 ; off graph
mov esi, eax ; Graph.Edges(u, v) := cost(v)
add edi, ebx ; v := v + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_2 ; off graph
add esi, eax ; Graph.Edges(u, v) += cost(v)
add edi, ebx ; v := v + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_2 ; off graph
add esi, eax ; Graph.Edges(u, v) += cost(v)
add edi, ebx ; v := v + tmp
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je neighbor_2 ; off graph
add esi, eax ; Graph.Edges(u, v) += cost(v)
; alt ← dist[u] + cost(v)
; if alt < dist[v]:
;     dist[v] ← alt
;     prev[v] ← u
add esi, ecx
%ifdef DBG_PRINT
pushad
call space
mov esi, eax
mov eax, edi
shr eax, 5
mov ecx, LINE_LEN
xor edx, edx
div ecx
call print_dec
call space
mov eax, edx
call print_dec
call space
mov eax, edi
and eax, 0x1f
call print_dec
call space
mov eax, esi
call print_dec
call newline
popad
%endif
cmp esi, [dist+edi*4]
jae neighbor_2 ; not better
mov [dist+edi*4], esi
mov [prev+edi*4], edx
; straight - neighbor 2
neighbor_2:
mov ebx, edx
and ebx, ~0b11111
cmp edx, (((LINE_LEN*32)+(32*1)))
je while_q_cont
; if u.dir & 0b00_111 < 6
;   neighbors += v@dir(u, u.dir + 1)
mov ebx, edx
and ebx, 0b00111
cmp ebx, 6
jae while_q_cont ; neighbors done
mov ebx, edx
and ebx, 0b11111
inc ebx
; tmp := 32
mov edi, 32
; bt dir, 4
bt ebx, 4
; if CF tmp := LINE_LEN
cmovc edi, ebp
; bt dir, 3
; if CF tmp := -tmp
mov esi, edi
neg esi
bt ebx, 3
cmovc edi, esi
; v := u + tmp
mov esi, edx
and esi, ~0b11111
add edi, esi
; v.dir := dir
or edi, ebx
; alt ← dist[u] + cost(v)
; if alt < dist[v]:
;     dist[v] ← alt
;     prev[v] ← u
mov eax, edi
shr eax, 5
movzx eax, byte [cost+eax]
cmp al, 0xff
je while_q_cont ; off graph
add eax, ecx
%ifdef DBG_PRINT
pushad
call space
mov esi, eax
mov eax, edi
shr eax, 5
mov ecx, LINE_LEN
xor edx, edx
div ecx
call print_dec
call space
mov eax, edx
call print_dec
call space
mov eax, edi
and eax, 0x1f
call print_dec
call space
mov eax, esi
call print_dec
call newline
popad
%endif
cmp eax, [dist+edi*4]
jae while_q_cont ; not better
mov [dist+edi*4], eax
mov [prev+edi*4], edx

while_q_cont:
jmp while_q

while_q_done:

call newline

; last dist values
mov ebx, ((((LINE_LEN-2)*(LINE_LEN*32))+((LINE_LEN-2)*32))+0b00000)
print_last_dist:
mov eax, [dist+ebx*4]
call print_sign_dec
inc ebx
mov ecx, ebx
and ecx, 0b111
cmp ecx, 0b111
jne .space
call newline
mov ecx, ebx
and ecx, 0b11111
cmp ecx, 0b11111
je .done
inc ebx
jmp .cont
.space:
call space
.cont:
jmp print_last_dist
.done:

game_over:
jmp exit

[section .data]
file: incbin FILENAME
.over:

[section .bss]
dist: resd LINE_LEN*LINE_LEN*32
prev: resd LINE_LEN*LINE_LEN*32
q:    resb LINE_LEN*LINE_LEN*32
cost: resb LINE_LEN*LINE_LEN
new_file: resb len(file)