diff options
Diffstat (limited to 'aoc-2025/day5.asm')
| -rw-r--r-- | aoc-2025/day5.asm | 331 |
1 files changed, 331 insertions, 0 deletions
diff --git a/aoc-2025/day5.asm b/aoc-2025/day5.asm new file mode 100644 index 0000000..4f395a0 --- /dev/null +++ b/aoc-2025/day5.asm @@ -0,0 +1,331 @@ +; 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 |