path: root/aoc-2025/day5.asm

; Advent of Code 2025 - Day 5

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   1048576  ; 1 MiB scratch for the raw file
%define MAX_RANGES 8192     ; plenty for the ~177 input ranges

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

    newline    db 10

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

section .bss
    raw           resb RAW_SIZE
    starts        resq MAX_RANGES  ; range/merged-interval starts
    ends          resq MAX_RANGES  ; range/merged-interval ends

    raw_len       resq 1
    n_ranges      resq 1  ; ranges parsed in section 1
    n_merged      resq 1  ; disjoint intervals after merge
    phase         resq 1  ; 0 = ranges, 1 = available IDs

    part1         resq 1
    part2         resq 1

    number_buffer resb 32

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
read_loop:
    mov     rax, SYS_READ
    mov     rdi, r12
    lea     rsi, [raw + r13]
    mov     rdx, RAW_SIZE
    sub     rdx, r13
    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

    ; RSI = cursor, R14 = end pointer (both preserved across helper calls)
    lea     rsi, [raw]
    mov     rax, [raw_len]
    lea     r14, [raw + rax]
    mov     qword [phase], 0

scan_line:
    cmp     rsi, r14
    jae     scan_done
    mov     al, [rsi]
    cmp     al, 10  ; LF  -> blank line
    je      got_blank
    cmp     al, 13  ; CR  -> blank line
    je      got_blank

    cmp     qword [phase], 0
    jne     do_avail

    call    parse_u64  ; RAX = start
    mov     rcx, [n_ranges]
    mov     [starts + rcx*8], rax
    inc     rsi        ; skip '-'
    call    parse_u64  ; RAX = end
    mov     rcx, [n_ranges]
    mov     [ends + rcx*8], rax
    inc     qword [n_ranges]
    jmp     skip_eol

do_avail:
    call    parse_u64
    mov     rdi, rax
    call    is_fresh  ; RAX = 1 if fresh
    test    rax, rax
    jz      skip_eol
    inc     qword [part1]
    jmp     skip_eol

got_blank:
    ; the blank line separates the two sections
    cmp     qword [phase], 0
    jne     skip_eol
    call    finalize_ranges  ; sort + merge, compute part2
    mov     qword [phase], 1
    ; fall through

skip_eol:
    cmp     rsi, r14
    jae     scan_done
    mov     al, [rsi]
    inc     rsi
    cmp     al, 10  ; consume through the LF
    jne     skip_eol
    jmp     scan_line

scan_done:
    ; safety: if there was no blank line, still finalize the ranges
    cmp     qword [phase], 0
    jne     print_results
    call    finalize_ranges

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

; parse_u64: read decimal digits at [RSI], advancing RSI past them.
;   Output: RAX = value. Stops on the first non-digit. Clobbers RAX, RDX.
parse_u64:
    xor     rax, rax
.digit:
    mov     dl, [rsi]
    cmp     dl, '0'
    jl      .done
    cmp     dl, '9'
    jg      .done
    sub     dl, '0'
    movzx   rdx, dl
    imul    rax, rax, 10
    add     rax, rdx
    inc     rsi
    jmp     .digit
.done:
    ret

; is_fresh: test membership of an ID in the merged intervals.
;   Input:  RDI = id
;   Output: RAX = 1 if the id lies in any interval, else 0
;   Intervals are sorted ascending and disjoint, so we can stop early.
;   Clobbers: RAX, RCX
is_fresh:
    xor     rcx, rcx
.loop:
    cmp     rcx, [n_merged]
    jge     .no
    mov     rax, [starts + rcx*8]
    cmp     rdi, rax
    jl      .no  ; id below this start -> below all later ones
    mov     rax, [ends + rcx*8]
    cmp     rdi, rax
    jle     .yes  ; start <= id <= end
    inc     rcx
    jmp     .loop
.no:
    xor     eax, eax
    ret
.yes:
    mov     eax, 1
    ret

; finalize_ranges: insertion-sort the ranges by start, merge overlapping /
; touching ones in place, store the disjoint intervals back into starts/ends,
; set n_merged, and accumulate their total size into part2.
;   Clobbers: RAX, RCX, RDX, R8, R9, R10, R11, R12, R13
finalize_ranges:
    mov     r8, 1  ; i
.sort_i:
    cmp     r8, [n_ranges]
    jge     .sorted
    mov     r10, [starts + r8*8]  ; key_s
    mov     r11, [ends + r8*8]    ; key_e
    mov     r9, r8
    dec     r9  ; j = i - 1
.sort_j:
    cmp     r9, 0
    jl      .sort_place
    mov     rax, [starts + r9*8]
    cmp     rax, r10
    jle     .sort_place  ; starts[j] <= key -> in place
    mov     rdx, r9
    inc     rdx                    ; j + 1
    mov     [starts + rdx*8], rax  ; shift start
    mov     rcx, [ends + r9*8]
    mov     [ends + rdx*8], rcx  ; shift end
    dec     r9
    jmp     .sort_j
.sort_place:
    mov     rdx, r9
    inc     rdx
    mov     [starts + rdx*8], r10
    mov     [ends + rdx*8], r11
    inc     r8
    jmp     .sort_i
.sorted:

    cmp     qword [n_ranges], 0
    je      .empty

    mov     r10, [starts]  ; cur_lo
    mov     r11, [ends]    ; cur_hi
    mov     r8, 1          ; i
    xor     r12, r12       ; part2 accumulator
    xor     r13, r13       ; write index
.merge_loop:
    cmp     r8, [n_ranges]
    jge     .flush
    mov     rax, [starts + r8*8]  ; s
    mov     rcx, [ends + r8*8]    ; e
    cmp     rax, r11
    jg      .gap      ; s > cur_hi -> disjoint
    cmp     rcx, r11  ; overlap: cur_hi = max(cur_hi, e)
    jle     .no_extend
    mov     r11, rcx
.no_extend:
    inc     r8
    jmp     .merge_loop
.gap:
    call    .emit
    mov     r10, rax  ; begin new interval
    mov     r11, rcx
    inc     r8
    jmp     .merge_loop
.flush:
    call    .emit
    mov     [n_merged], r13
    mov     [part2], r12
    ret
.empty:
    mov     qword [n_merged], 0
    mov     qword [part2], 0
    ret

; local helper: emit [r10, r11] as merged interval r13, add its size to r12
.emit:
    mov     [starts + r13*8], r10
    mov     [ends + r13*8], r11
    inc     r13
    mov     rdx, r11
    sub     rdx, r10
    inc     rdx  ; end - start + 1
    add     r12, rdx
    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