path: root/aoc-2025/day4.asm

; Advent of Code 2025 - Day 4

bits 64
default rel

global _start

%define SYS_EXIT   60
%define SYS_READ   0
%define SYS_WRITE  1
%define SYS_OPEN   2
%define SYS_CLOSE  3

%define O_RDONLY   0
%define STDOUT     1

%define RAW_SIZE   4194304  ; 4 MiB scratch for the raw file
%define GRID_SIZE  4194304  ; 4 MiB for the padded grid / mark buffers

section .data
    input_path db "input/day4.txt", 0

    newline    db 10

    label1     db "Part 1: ", 0
    label2     db "Part 2: ", 0

section .bss
    raw           resb RAW_SIZE   ; raw file bytes
    grid          resb GRID_SIZE  ; padded grid: 1 = roll, 0 = empty
    mark          resb GRID_SIZE  ; per-round removal marks

    raw_len       resq 1
    width         resq 1  ; real columns per row
    height        resq 1  ; real rows
    stride        resq 1  ; width + 2 (padding on both sides)

    part1         resq 1
    part2         resq 1

    number_buffer resb 32  ; for printing

section .text

_start:
    mov     rax, SYS_OPEN
    mov     rdi, input_path
    mov     rsi, O_RDONLY
    xor     rdx, rdx
    syscall
    mov     r12, rax  ; fd

    xor     r13, r13  ; bytes read so far
read_loop:
    mov     rax, SYS_READ
    mov     rdi, r12
    lea     rsi, [raw + r13]
    mov     rdx, RAW_SIZE
    sub     rdx, r13  ; remaining capacity
    syscall

    cmp     rax, 0
    jle     read_done
    add     r13, rax
    jmp     read_loop
read_done:
    mov     [raw_len], r13

    mov     rax, SYS_CLOSE
    mov     rdi, r12
    syscall

    xor     rcx, rcx  ; column scanner
width_scan:
    cmp     rcx, [raw_len]
    jge     width_done
    mov     al, [raw + rcx]
    cmp     al, 13  ; CR
    je      width_done
    cmp     al, 10  ; LF
    je      width_done
    inc     rcx
    jmp     width_scan
width_done:
    mov     [width], rcx
    add     rcx, 2  ; padding on left + right
    mov     [stride], rcx

    ; real cell (r, c) lives at grid[(r+1)*stride + (c+1)]
    mov     r10, [raw_len]
    xor     r8, r8    ; i  (raw index)
    xor     r9, r9    ; r  (row, 0-based)
    xor     r11, r11  ; c  (col, 0-based)
fill_loop:
    cmp     r8, r10
    jge     fill_end
    mov     al, [raw + r8]
    inc     r8

    cmp     al, 13  ; CR -> ignore
    je      fill_loop
    cmp     al, 10  ; LF -> end of line
    je      fill_newline

    cmp     al, '@'
    jne     fill_next_col  ; '.' leaves the zeroed cell alone

    ; grid[(r9+1)*stride + (r11+1)] = 1
    mov     rbx, r9
    inc     rbx
    imul    rbx, [stride]
    add     rbx, r11
    add     rbx, 1
    mov     byte [grid + rbx], 1
fill_next_col:
    inc     r11
    jmp     fill_loop
fill_newline:
    cmp     r11, 0  ; blank line -> skip (e.g. trailing newline)
    je      fill_loop
    inc     r9
    xor     r11, r11
    jmp     fill_loop
fill_end:
    cmp     r11, 0  ; last line had no trailing newline
    je      fill_height
    inc     r9
fill_height:
    mov     [height], r9

    mov     r13, 1  ; row = 1..height
p1_row:
    cmp     r13, [height]
    jg      p1_done
    mov     rbx, r13
    imul    rbx, [stride]
    inc     rbx     ; idx of (row, col=1)
    mov     r12, 1  ; col = 1..width
p1_col:
    cmp     r12, [width]
    jg      p1_row_next
    movzx   eax, byte [grid + rbx]
    test    eax, eax
    jz      p1_next  ; not a roll
    mov     rdi, rbx
    call    count_neighbors
    cmp     rax, 4
    jge     p1_next  ; 4 or more neighbors -> blocked
    inc     qword [part1]
p1_next:
    inc     rbx
    inc     r12
    jmp     p1_col
p1_row_next:
    inc     r13
    jmp     p1_row
p1_done:

peel_loop:
    mov     r13, 1
mark_row:
    cmp     r13, [height]
    jg      mark_done
    mov     rbx, r13
    imul    rbx, [stride]
    inc     rbx
    mov     r12, 1
mark_col:
    cmp     r12, [width]
    jg      mark_row_next
    movzx   eax, byte [grid + rbx]
    test    eax, eax
    jz      mark_zero  ; empty cell
    mov     rdi, rbx
    call    count_neighbors
    cmp     rax, 4
    jl      mark_one  ; accessible
mark_zero:
    mov     byte [mark + rbx], 0
    jmp     mark_next
mark_one:
    mov     byte [mark + rbx], 1
mark_next:
    inc     rbx
    inc     r12
    jmp     mark_col
mark_row_next:
    inc     r13
    jmp     mark_row
mark_done:

    xor     r11, r11  ; removed this round
    mov     r13, 1
apply_row:
    cmp     r13, [height]
    jg      apply_done
    mov     rbx, r13
    imul    rbx, [stride]
    inc     rbx
    mov     r12, 1
apply_col:
    cmp     r12, [width]
    jg      apply_row_next
    movzx   eax, byte [mark + rbx]
    test    eax, eax
    jz      apply_next
    mov     byte [grid + rbx], 0
    inc     r11
apply_next:
    inc     rbx
    inc     r12
    jmp     apply_col
apply_row_next:
    inc     r13
    jmp     apply_row
apply_done:
    add     [part2], r11
    test    r11, r11
    jnz     peel_loop  ; something changed -> another round

print_results:
    mov     rcx, label1
    call    print_string
    mov     rax, [part1]
    call    print_int64
    call    print_newline

    mov     rcx, label2
    call    print_string
    mov     rax, [part2]
    call    print_int64
    call    print_newline

    mov     rax, SYS_EXIT
    xor     rdi, rdi
    syscall

; count_neighbors: sum of the 8 cells around a padded index
;   Input:  RDI = grid index
;   Output: RAX = number of neighboring rolls (0..8)
;   Clobbers: RAX, RCX, RDX, R8
count_neighbors:
    mov     rcx, [stride]
    xor     eax, eax

    mov     rdx, rdi
    sub     rdx, rcx  ; row above
    movzx   r8d, byte [grid + rdx - 1]
    add     eax, r8d
    movzx   r8d, byte [grid + rdx]
    add     eax, r8d
    movzx   r8d, byte [grid + rdx + 1]
    add     eax, r8d

    movzx   r8d, byte [grid + rdi - 1]  ; same row, sides
    add     eax, r8d
    movzx   r8d, byte [grid + rdi + 1]
    add     eax, r8d

    mov     rdx, rdi
    add     rdx, rcx  ; row below
    movzx   r8d, byte [grid + rdx - 1]
    add     eax, r8d
    movzx   r8d, byte [grid + rdx]
    add     eax, r8d
    movzx   r8d, byte [grid + rdx + 1]
    add     eax, r8d
    ret

print_newline:
    mov     rax, SYS_WRITE
    mov     rdi, STDOUT
    mov     rsi, newline
    mov     rdx, 1
    syscall
    ret

print_int64:
    mov     rdi, number_buffer+31
    mov     byte [rdi], 0
    dec     rdi

    cmp     rax, 0
    jne     .conv

    mov     byte [rdi], '0'
    jmp     .done
.conv:
    mov     rbx, 10
.next:
    xor     rdx, rdx
    div     rbx
    add     dl, '0'
    mov     [rdi], dl
    dec     rdi
    test    rax, rax
    jnz     .next

    inc     rdi
.done:
    mov     rax, SYS_WRITE
    mov     rsi, rdi
    mov     rdi, STDOUT
    mov     rdx, number_buffer+31
    sub     rdx, rsi
    syscall
    ret

print_string:
    push    rcx
    push    rdx
    mov     rdx, 0
.length:
    cmp     byte [rcx+rdx], 0
    je      .submit
    inc     rdx
    jmp     .length
.submit:
    mov     rax, SYS_WRITE
    mov     rdi, STDOUT
    mov     rsi, rcx
    syscall
    pop     rdx
    pop     rcx
    ret