diff options
| -rw-r--r-- | aoc-2025/day10.asm | 784 | ||||
| -rw-r--r-- | aoc-2025/day11.asm | 320 | ||||
| -rw-r--r-- | aoc-2025/day12.asm | 590 | ||||
| -rw-r--r-- | aoc-2025/day9.asm | 644 |
4 files changed, 2338 insertions, 0 deletions
diff --git a/aoc-2025/day10.asm b/aoc-2025/day10.asm new file mode 100644 index 0000000..02582b2 --- /dev/null +++ b/aoc-2025/day10.asm @@ -0,0 +1,784 @@ +; Advent of Code 2025 - Day 10 + +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 262144 +%define MAXB 16 +%define MAXL 12 +%define MNCOLS (MAXB + 1) ; matrix columns: buttons + rhs +%define CPFSTRIDE 8 ; free-coeff stride (free vars <= 3) + +section .data + input_path db "input/day10.txt", 0 + + newline db 10 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + + bmask resq MAXB ; part 1: button light masks + btn_ctrs resq (MAXB * MAXL) ; part 2: counters each button hits + btn_len resq MAXB + jolt resq MAXL ; part 2: target counter values + + Mnum resq (MAXL * MNCOLS) ; augmented matrix numerators + rowden resq MAXL ; per-row common denominators + pivcol resq MAXL + is_piv resb MAXB + free_cols resq MAXB + ub_free resq MAXB + x_free resq MAXB + RP resq MAXL ; scaled rhs per pivot row + CPF resq (MAXL * CPFSTRIDE); scaled free coeffs per pivot row + + raw_len resq 1 + cur_t resq 1 + nb resq 1 + nc resq 1 + npiv resq 1 + nfree resq 1 + Dval resq 1 + best resq 1 + total1 resq 1 + total2 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 + + 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 + + lea rsi, [raw] + mov rax, [raw_len] + lea r14, [raw + rax] + mov qword [cur_t], 0 + mov qword [nb], 0 + mov qword [nc], 0 +scan: + cmp rsi, r14 + jae finish_last + mov al, [rsi] + cmp al, '[' + je do_bracket + cmp al, '(' + je do_button + cmp al, '{' + je do_curly + cmp al, 10 + je end_line + inc rsi + jmp scan + +do_bracket: + inc rsi + xor r10, r10 ; light index + xor r11, r11 ; target mask +.loop: + mov al, [rsi] + cmp al, ']' + je .done + cmp al, '#' + jne .off + mov rcx, r10 + mov rdx, 1 + shl rdx, cl + or r11, rdx +.off: + inc r10 + inc rsi + jmp .loop +.done: + inc rsi + mov [cur_t], r11 + jmp scan + +do_button: + inc rsi + xor r11, r11 ; light mask + xor r10, r10 ; current index + xor r9, r9 ; counter list length +.loop: + mov al, [rsi] + cmp al, ')' + je .fin + cmp al, ',' + je .comma + sub al, '0' + movzx rax, al + imul r10, r10, 10 + add r10, rax + inc rsi + jmp .loop +.comma: + mov rcx, r10 + mov rdx, 1 + shl rdx, cl + or r11, rdx + mov rax, [nb] + imul rax, MAXL + add rax, r9 + mov [btn_ctrs + rax*8], r10 + inc r9 + xor r10, r10 + inc rsi + jmp .loop +.fin: + mov rcx, r10 + mov rdx, 1 + shl rdx, cl + or r11, rdx + mov rax, [nb] + imul rax, MAXL + add rax, r9 + mov [btn_ctrs + rax*8], r10 + inc r9 + inc rsi + mov rax, [nb] + mov [bmask + rax*8], r11 + mov [btn_len + rax*8], r9 + inc qword [nb] + jmp scan + +do_curly: + inc rsi + xor r10, r10 ; current number +.loop: + mov al, [rsi] + cmp al, '}' + je .fin + cmp al, ',' + je .comma + sub al, '0' + movzx rax, al + imul r10, r10, 10 + add r10, rax + inc rsi + jmp .loop +.comma: + mov rax, [nc] + mov [jolt + rax*8], r10 + inc qword [nc] + xor r10, r10 + inc rsi + jmp .loop +.fin: + mov rax, [nc] + mov [jolt + rax*8], r10 + inc qword [nc] + inc rsi + jmp scan + +end_line: + inc rsi + push rsi + push r14 + call solve1 + call solve2 + pop r14 + pop rsi + mov qword [cur_t], 0 + mov qword [nb], 0 + mov qword [nc], 0 + jmp scan + +finish_last: + cmp qword [nb], 0 + je all_done + push rsi + push r14 + call solve1 + call solve2 + pop r14 + pop rsi +all_done: + +print_results: + mov rcx, label1 + call print_string + mov rax, [total1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [total2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; solve1: part 1 - fewest button presses to match the light target (GF(2)). +solve1: + mov rcx, [nb] + mov r8, 1 + shl r8, cl + mov r9, 0x7fffffff + xor r10, r10 +.mask: + cmp r10, r8 + jge .done + xor r11, r11 + xor rbx, rbx + xor rcx, rcx +.bits: + cmp rcx, [nb] + jge .check + mov rdx, r10 + shr rdx, cl + test rdx, 1 + jz .bit_next + xor r11, [bmask + rcx*8] + inc rbx +.bit_next: + inc rcx + jmp .bits +.check: + cmp r11, [cur_t] + jne .next + cmp rbx, r9 + jge .next + mov r9, rbx +.next: + inc r10 + jmp .mask +.done: + cmp r9, 0x7fffffff + je .ret + add [total1], r9 +.ret: + ret + +; solve2: part 2 - fewest button presses to reach the joltage targets. +; Builds the incidence matrix, reduces it to RREF over the rationals (per-row +; denominators), then enumerates the free variables. +solve2: + ; clear matrix and set row denominators to 1 + mov rax, [nc] + imul rax, MNCOLS + mov rcx, rax + lea rdi, [Mnum] + xor rax, rax + rep stosq + xor rcx, rcx +.rd_init: + cmp rcx, [nc] + jge .rd_done + mov qword [rowden + rcx*8], 1 + inc rcx + jmp .rd_init +.rd_done: + ; A[counter][button] = 1 + xor r8, r8 +.fill_b: + cmp r8, [nb] + jge .fill_done + mov r9, [btn_len + r8*8] + xor rcx, rcx +.fill_k: + cmp rcx, r9 + jge .fill_k_done + mov r10, r8 + imul r10, MAXL + add r10, rcx + mov r11, [btn_ctrs + r10*8] + mov rax, r11 + imul rax, MNCOLS + add rax, r8 + mov qword [Mnum + rax*8], 1 + inc rcx + jmp .fill_k +.fill_k_done: + inc r8 + jmp .fill_b +.fill_done: + ; rhs column = jolt targets + xor rcx, rcx +.rhs: + cmp rcx, [nc] + jge .rhs_done + mov rax, rcx + imul rax, MNCOLS + add rax, [nb] + mov rdx, [jolt + rcx*8] + mov [Mnum + rax*8], rdx + inc rcx + jmp .rhs +.rhs_done: + + ; RREF + lea rdi, [is_piv] + mov rcx, [nb] + xor al, al + rep stosb + mov qword [npiv], 0 + xor r15, r15 ; column +.rref_c: + cmp r15, [nb] + jge .rref_done + ; find a pivot row in [npiv, nc) + mov r12, [npiv] + mov r13, -1 +.find_pr: + cmp r12, [nc] + jge .find_pr_done + mov rax, r12 + imul rax, MNCOLS + add rax, r15 + cmp qword [Mnum + rax*8], 0 + je .find_pr_next + mov r13, r12 + jmp .find_pr_done +.find_pr_next: + inc r12 + jmp .find_pr +.find_pr_done: + cmp r13, -1 + je .rref_c_next + mov r12, [npiv] + cmp r12, r13 + je .noswap + ; swap rows r12 and r13 + xor rcx, rcx +.swap_j: + cmp rcx, [nb] + jg .swap_done + mov rax, r12 + imul rax, MNCOLS + add rax, rcx + mov rbx, r13 + imul rbx, MNCOLS + add rbx, rcx + mov r8, [Mnum + rax*8] + mov r9, [Mnum + rbx*8] + mov [Mnum + rax*8], r9 + mov [Mnum + rbx*8], r8 + inc rcx + jmp .swap_j +.swap_done: + mov r8, [rowden + r12*8] + mov r9, [rowden + r13*8] + mov [rowden + r12*8], r9 + mov [rowden + r13*8], r8 +.noswap: + ; normalise pivot row: denominator = pivot numerator + mov r12, [npiv] + mov rax, r12 + imul rax, MNCOLS + add rax, r15 + mov rdx, [Mnum + rax*8] + mov [rowden + r12*8], rdx + mov rdi, r12 + call reduce_row + ; eliminate column from every other row + xor r13, r13 +.elim_rr: + cmp r13, [nc] + jge .elim_done + cmp r13, r12 + je .elim_next + mov rax, r13 + imul rax, MNCOLS + add rax, r15 + mov r8, [Mnum + rax*8] ; fc + test r8, r8 + jz .elim_next + mov r9, [rowden + r12*8] ; rd + xor rcx, rcx +.elim_j: + cmp rcx, [nb] + jg .elim_j_done + mov rax, r13 + imul rax, MNCOLS + add rax, rcx + mov r10, [Mnum + rax*8] + imul r10, r9 + mov rbx, r12 + imul rbx, MNCOLS + add rbx, rcx + mov r11, [Mnum + rbx*8] + imul r11, r8 + sub r10, r11 + mov [Mnum + rax*8], r10 + inc rcx + jmp .elim_j +.elim_j_done: + mov rax, [rowden + r13*8] + imul rax, r9 + mov [rowden + r13*8], rax + mov rdi, r13 + call reduce_row +.elim_next: + inc r13 + jmp .elim_rr +.elim_done: + mov r12, [npiv] + mov [pivcol + r12*8], r15 + mov byte [is_piv + r15], 1 + inc qword [npiv] +.rref_c_next: + inc r15 + jmp .rref_c +.rref_done: + + ; free columns + xor r12, r12 + xor r15, r15 +.free_scan: + cmp r15, [nb] + jge .free_done + cmp byte [is_piv + r15], 0 + jne .free_next + mov [free_cols + r12*8], r15 + inc r12 +.free_next: + inc r15 + jmp .free_scan +.free_done: + mov [nfree], r12 + + ; D = lcm of the pivot-row denominators + mov qword [Dval], 1 + xor r13, r13 +.lcm: + cmp r13, [npiv] + jge .lcm_done + mov rdi, [Dval] + mov rsi, [rowden + r13*8] + call gcd + mov rcx, rax + mov rax, [Dval] + xor rdx, rdx + div rcx + imul rax, [rowden + r13*8] + mov [Dval], rax + inc r13 + jmp .lcm +.lcm_done: + + ; scaled rhs and free coefficients per pivot row + xor r13, r13 +.setup_pr: + cmp r13, [npiv] + jge .setup_done + mov rax, [Dval] + xor rdx, rdx + div qword [rowden + r13*8] + mov r8, rax ; q = D / rowden + mov rax, r13 + imul rax, MNCOLS + add rax, [nb] + mov rcx, [Mnum + rax*8] + imul rcx, r8 + mov [RP + r13*8], rcx + xor r9, r9 +.setup_f: + cmp r9, [nfree] + jge .setup_f_done + mov r10, [free_cols + r9*8] + mov rax, r13 + imul rax, MNCOLS + add rax, r10 + mov rcx, [Mnum + rax*8] + imul rcx, r8 + mov rax, r13 + imul rax, CPFSTRIDE + add rax, r9 + mov [CPF + rax*8], rcx + inc r9 + jmp .setup_f +.setup_f_done: + inc r13 + jmp .setup_pr +.setup_done: + + ; free-variable upper bounds = min covered target + xor r9, r9 +.ub_loop: + cmp r9, [nfree] + jge .ub_done + mov r10, [free_cols + r9*8] + mov r11, [btn_len + r10*8] + mov r12, 0x7fffffff + xor rcx, rcx +.ub_k: + cmp rcx, r11 + jge .ub_k_done + mov rax, r10 + imul rax, MAXL + add rax, rcx + mov rbx, [btn_ctrs + rax*8] + mov rdx, [jolt + rbx*8] + cmp rdx, r12 + jge .ub_k_next + mov r12, rdx +.ub_k_next: + inc rcx + jmp .ub_k +.ub_k_done: + mov [ub_free + r9*8], r12 + inc r9 + jmp .ub_loop +.ub_done: + + mov qword [best], 0x3fffffff + xor rdi, rdi + xor rsi, rsi + call enum_free + mov rax, [best] + add [total2], rax + ret + +; enum_free: recurse over free variables (RDI=depth, RSI=partial presses), +; pruning branches that already reach the best. Preserves R12-R15. +enum_free: + cmp rsi, [best] + jae .ret + cmp rdi, [nfree] + je .leaf + push r12 + push r13 + push r14 + push r15 + mov r12, rdi + mov r13, rsi + mov r14, [ub_free + r12*8] + xor r15, r15 +.vloop: + mov rsi, r13 + add rsi, r15 + cmp rsi, [best] + jae .vdone + mov [x_free + r12*8], r15 + lea rdi, [r12 + 1] + call enum_free + inc r15 + cmp r15, r14 + jbe .vloop +.vdone: + pop r15 + pop r14 + pop r13 + pop r12 + ret +.leaf: + call eval_leaf +.ret: + ret + +; eval_leaf: with all free variables fixed, recover the basic variables and +; update best. RSI = presses used by free variables. Preserves R12-R15. +eval_leaf: + mov r11, rsi ; running total + xor r8, r8 ; pivot row +.pr: + cmp r8, [npiv] + jge .accept + mov rax, [RP + r8*8] + xor r9, r9 +.f: + cmp r9, [nfree] + jge .fd + mov rcx, r8 + imul rcx, CPFSTRIDE + add rcx, r9 + mov rdx, [CPF + rcx*8] + imul rdx, [x_free + r9*8] + sub rax, rdx + inc r9 + jmp .f +.fd: + test rax, rax + js .ret + cqo + idiv qword [Dval] + test rdx, rdx + jnz .ret + add r11, rax + cmp r11, [best] + jae .ret + inc r8 + jmp .pr +.accept: + mov [best], r11 +.ret: + ret + +; gcd(RDI, RSI) -> RAX, inputs non-negative. Clobbers RAX, RDX, RDI, RSI. +gcd: +.loop: + test rsi, rsi + jz .done + xor rdx, rdx + mov rax, rdi + div rsi + mov rdi, rsi + mov rsi, rdx + jmp .loop +.done: + mov rax, rdi + ret + +; reduce_row(RDI=row): make denominator positive and divide the row by the gcd +; of all its entries. Clobbers RAX, RCX, RDX, RSI, RDI, R8, R9, R10, R11. +reduce_row: + mov r11, rdi + mov r8, r11 + imul r8, MNCOLS + mov rax, [rowden + r11*8] + test rax, rax + jns .signok + neg qword [rowden + r11*8] + xor r10, r10 +.sneg: + cmp r10, [nb] + jg .signok + mov rax, r8 + add rax, r10 + neg qword [Mnum + rax*8] + inc r10 + jmp .sneg +.signok: + mov r9, [rowden + r11*8] ; g accumulator + xor r10, r10 +.gloop: + cmp r10, [nb] + jg .gdone + cmp r9, 1 + je .gdone + mov rax, r8 + add rax, r10 + mov rsi, [Mnum + rax*8] + mov rdx, rsi + sar rdx, 63 + xor rsi, rdx + sub rsi, rdx + test rsi, rsi + jz .gnext + mov rdi, r9 + call gcd + mov r9, rax +.gnext: + inc r10 + jmp .gloop +.gdone: + cmp r9, 1 + jle .done + mov rax, [rowden + r11*8] + xor rdx, rdx + div r9 + mov [rowden + r11*8], rax + xor r10, r10 +.divl: + cmp r10, [nb] + jg .done + mov rax, r8 + add rax, r10 + mov rcx, rax + mov rax, [Mnum + rcx*8] + cqo + idiv r9 + mov [Mnum + rcx*8], rax + inc r10 + jmp .divl +.done: + 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 + + diff --git a/aoc-2025/day11.asm b/aoc-2025/day11.asm new file mode 100644 index 0000000..bf92fad --- /dev/null +++ b/aoc-2025/day11.asm @@ -0,0 +1,320 @@ +; Advent of Code 2025 - Day 11 + +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 262144 +%define NCODES 17576 ; 26^3 possible 3-letter names +%define OUT_CODE 10003 ; encode("out") +%define YOU_CODE 16608 ; encode("you") +%define SVR_CODE 12731 ; encode("svr") +%define DAC_CODE 2030 ; encode("dac") +%define FFT_CODE 3529 ; encode("fft") +%define MAXEDGES 8192 + +section .data + input_path db "input/day11.txt", 0 + + newline db 10 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + adj_head resq NCODES ; first child index in `child` + adj_cnt resq NCODES ; number of children + child resq MAXEDGES ; flat child codes + memo resq NCODES ; path counts, -1 = not computed + blocked resb NCODES ; 1 = treat node as a dead end + + raw_len resq 1 + t1 resq 1 + t2 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 + + 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 + + ; memo = -1 everywhere + mov rax, -1 + lea rdi, [memo] + mov rcx, NCODES + rep stosq + + ; parse "name: a b c" adjacency lines + lea rsi, [raw] + mov rax, [raw_len] + lea r13, [raw + rax] ; end pointer + xor r12, r12 ; child write index +parse_line: + cmp rsi, r13 + jae parse_done + mov al, [rsi] + cmp al, 10 + je parse_skip + cmp al, 13 + je parse_skip + call encode3 ; RAX = node code + mov r10, rax + mov [adj_head + r10*8], r12 +skip_sep: + mov al, [rsi] + cmp al, ':' + je .adv + cmp al, ' ' + je .adv + jmp children +.adv: + inc rsi + jmp skip_sep +children: + xor r11, r11 ; child count +child_loop: + cmp rsi, r13 + jae child_done + mov al, [rsi] + cmp al, 10 + je child_done + cmp al, 13 + je child_done + cmp al, ' ' + je child_space + call encode3 + mov [child + r12*8], rax + inc r12 + inc r11 + jmp child_loop +child_space: + inc rsi + jmp child_loop +child_done: + mov [adj_cnt + r10*8], r11 +skip_eol: + cmp rsi, r13 + jae parse_done + mov al, [rsi] + inc rsi + cmp al, 10 + jne skip_eol + jmp parse_line +parse_skip: + inc rsi + jmp parse_line +parse_done: + + ; part 1: paths you -> out + call clear_memo + mov rdi, YOU_CODE + call count + mov [t1], rax + + ; part 2: paths svr -> out visiting both dac and fft, via inclusion-exclusion + call clear_memo + mov rdi, SVR_CODE + call count + mov r12, rax ; N(all) + + mov byte [blocked + DAC_CODE], 1 + call clear_memo + mov rdi, SVR_CODE + call count + mov r13, rax ; N(avoid dac) + mov byte [blocked + DAC_CODE], 0 + + mov byte [blocked + FFT_CODE], 1 + call clear_memo + mov rdi, SVR_CODE + call count + mov r14, rax ; N(avoid fft) + mov byte [blocked + FFT_CODE], 0 + + mov byte [blocked + DAC_CODE], 1 + mov byte [blocked + FFT_CODE], 1 + call clear_memo + mov rdi, SVR_CODE + call count ; N(avoid both) in rax + mov byte [blocked + DAC_CODE], 0 + mov byte [blocked + FFT_CODE], 0 + + sub r12, r13 + sub r12, r14 + add r12, rax + mov [t2], r12 + + mov rcx, label1 + call print_string + mov rax, [t1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [t2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; clear_memo: reset all memo entries to -1. Clobbers RAX, RCX, RDI. +clear_memo: + mov rax, -1 + lea rdi, [memo] + mov rcx, NCODES + rep stosq + ret + +; encode3: read 3 lowercase letters at [RSI] into a base-26 code, advance RSI. +; Output: RAX = code. Clobbers RAX, RDX. +encode3: + movzx eax, byte [rsi] + sub eax, 'a' + imul eax, eax, 676 + movzx edx, byte [rsi + 1] + sub edx, 'a' + imul edx, edx, 26 + add eax, edx + movzx edx, byte [rsi + 2] + sub edx, 'a' + add eax, edx + add rsi, 3 + ret + +; count: number of paths from node RDI to out. Memoised DFS over the DAG. +; Output: RAX. Clobbers RAX; preserves everything else via the stack. +count: + cmp rdi, OUT_CODE + je .one + cmp byte [blocked + rdi], 0 + jne .zero + mov rax, [memo + rdi*8] + cmp rax, -1 + jne .ret + push r12 + push r13 + push r14 + push r15 + mov r12, rdi + mov r13, [adj_head + r12*8] + mov r14, r13 + add r14, [adj_cnt + r12*8] + xor r15, r15 +.loop: + cmp r13, r14 + jge .done + mov rdi, [child + r13*8] + call count + add r15, rax + inc r13 + jmp .loop +.done: + mov [memo + r12*8], r15 + mov rax, r15 + pop r15 + pop r14 + pop r13 + pop r12 + ret +.one: + mov rax, 1 + ret +.zero: + xor eax, eax +.ret: + 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 diff --git a/aoc-2025/day12.asm b/aoc-2025/day12.asm new file mode 100644 index 0000000..6eb64a9 --- /dev/null +++ b/aoc-2025/day12.asm @@ -0,0 +1,590 @@ +; Advent of Code 2025 - Day 12 + +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 262144 +%define GRID_SIZE 4096 ; regions are at most 50x50 + +section .data + input_path db "input/day12.txt", 0 + + newline db 10 + + label1 db "Part 1: ", 0 + +section .bss + raw resb RAW_SIZE + + base_r resd (6 * 9) ; parsed shape cells + base_c resd (6 * 9) + base_n resq 6 ; cells per shape (also its area cost) + + odr resd (6 * 8 * 9) ; orientation cell offsets from anchor + odc resd (6 * 8 * 9) + oncells resq (6 * 8) + + tr resd 9 ; scratch for orientation building + tc resd 9 + + grid resb GRID_SIZE + remaining resq 6 + counts resq 6 + + raw_len resq 1 + cursor resq 1 + pend resq 1 + cur_shape resq 1 + shape_row resq 1 + orients_done resq 1 + rW resq 1 + rL resq 1 + area resq 1 + left resq 1 + count_feasible 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 + + 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 + + ; parse shapes and regions + lea rsi, [raw] + mov rax, [raw_len] + lea rax, [raw + rax] + mov [pend], rax + mov qword [cur_shape], 0 + mov qword [orients_done], 0 +pline: + cmp rsi, [pend] + jae pdone + mov al, [rsi] + cmp al, 10 + je pskip + cmp al, 13 + je pskip + cmp al, ' ' + je pskip + cmp al, '0' + jl maybe_grid + cmp al, '9' + jg maybe_grid + ; a number begins the line + call parse_num + mov r10, rax + mov al, [rsi] + cmp al, 'x' + je region_line + ; shape header "N:" + inc rsi + mov [cur_shape], r10 + mov qword [base_n + r10*8], 0 + mov qword [shape_row], 0 + jmp eol + +region_line: + cmp qword [orients_done], 0 + jne .have + mov [cursor], rsi + call gen_orients + mov rsi, [cursor] + mov qword [orients_done], 1 +.have: + inc rsi ; skip 'x' + call parse_num + mov r11, rax ; L +.find_colon: + mov al, [rsi] + inc rsi + cmp al, ':' + jne .find_colon + xor rcx, rcx +.rcounts: + cmp rcx, 6 + jge .rcounts_done +.rsp: + mov al, [rsi] + cmp al, ' ' + jne .rsp_done + inc rsi + jmp .rsp +.rsp_done: + call parse_num + mov [counts + rcx*8], rax + inc rcx + jmp .rcounts +.rcounts_done: + mov [cursor], rsi + mov rdi, r10 ; W + mov rsi, r11 ; L + call solve_region + mov rsi, [cursor] + jmp eol + +maybe_grid: + cmp al, '#' + je grid_row + cmp al, '.' + je grid_row + inc rsi + jmp pline +grid_row: + mov r10, [cur_shape] + mov r11, [shape_row] + xor rcx, rcx ; column +.cell: + mov al, [rsi] + cmp al, '#' + je .hash + cmp al, '.' + je .dot + jmp .row_done +.hash: + mov rax, r10 + imul rax, 9 + add rax, [base_n + r10*8] + mov edx, r11d + mov [base_r + rax*4], edx + mov edx, ecx + mov [base_c + rax*4], edx + inc qword [base_n + r10*8] +.dot: + inc rcx + inc rsi + jmp .cell +.row_done: + inc qword [shape_row] + jmp eol + +eol: + cmp rsi, [pend] + jae pdone + mov al, [rsi] + inc rsi + cmp al, 10 + jne eol + jmp pline +pskip: + inc rsi + jmp pline +pdone: + + mov rcx, label1 + call print_string + mov rax, [count_feasible] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; parse_num: read decimal at [RSI], advancing RSI. Clobbers RAX, RDX. +parse_num: + xor rax, rax +.d: + 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 .d +.done: + ret + +; gen_orients: build the 8 dihedral orientations of every shape as offset lists +; anchored at their row-major-first cell. +gen_orients: + xor r12, r12 ; shape +.s_loop: + cmp r12, 6 + jge .done + xor r13, r13 ; transform 0..7 +.t_loop: + cmp r13, 8 + jge .s_next + mov r14, [base_n + r12*8] + xor rcx, rcx +.k_loop: + cmp rcx, r14 + jge .k_done + mov rax, r12 + imul rax, 9 + add rax, rcx + movsxd r8, dword [base_r + rax*4] + movsxd r9, dword [base_c + rax*4] + test r13, 4 + jz .noflip + neg r9 +.noflip: + mov rdx, r13 + and rdx, 3 +.rot: + test rdx, rdx + jz .rot_done + mov r15, r8 + mov r8, r9 ; new r = c + mov r9, r15 + neg r9 ; new c = -r + dec rdx + jmp .rot +.rot_done: + mov [tr + rcx*4], r8d + mov [tc + rcx*4], r9d + inc rcx + jmp .k_loop +.k_done: + ; min row + movsxd r8, dword [tr] + xor rcx, rcx +.minr: + cmp rcx, r14 + jge .minr_done + movsxd rax, dword [tr + rcx*4] + cmp rax, r8 + jge .minr_next + mov r8, rax +.minr_next: + inc rcx + jmp .minr +.minr_done: + ; min col among cells on the min row + mov r9, 0x7fffffff + xor rcx, rcx +.minc: + cmp rcx, r14 + jge .minc_done + movsxd rax, dword [tr + rcx*4] + cmp rax, r8 + jne .minc_next + movsxd rax, dword [tc + rcx*4] + cmp rax, r9 + jge .minc_next + mov r9, rax +.minc_next: + inc rcx + jmp .minc +.minc_done: + mov r11, r12 + shl r11, 3 + add r11, r13 ; orientation index + mov [oncells + r11*8], r14 + xor rcx, rcx +.store: + cmp rcx, r14 + jge .store_done + movsxd rax, dword [tr + rcx*4] + sub rax, r8 ; dr + movsxd rdx, dword [tc + rcx*4] + sub rdx, r9 ; dc + mov rbx, r11 + imul rbx, 9 + add rbx, rcx + mov [odr + rbx*4], eax + mov [odc + rbx*4], edx + inc rcx + jmp .store +.store_done: + inc r13 + jmp .t_loop +.s_next: + inc r12 + jmp .s_loop +.done: + ret + +; solve_region(RDI=W, RSI=L): if the region can fit all presents in `counts`, +; increment count_feasible. +solve_region: + xor r8, r8 ; total cells + xor rcx, rcx +.tot: + cmp rcx, 6 + jge .tot_done + mov rax, [counts + rcx*8] + imul rax, [base_n + rcx*8] + add r8, rax + inc rcx + jmp .tot +.tot_done: + mov rax, rdi + imul rax, rsi + mov [area], rax + mov [rW], rdi + mov [rL], rsi + cmp r8, rax + jg .ret ; more cells than space -> impossible + mov r9, rax + sub r9, r8 ; empty budget + + xor r10, r10 ; piece count + xor rcx, rcx +.setrem: + cmp rcx, 6 + jge .setrem_done + mov rax, [counts + rcx*8] + mov [remaining + rcx*8], rax + add r10, rax + inc rcx + jmp .setrem +.setrem_done: + mov [left], r10 + + mov rcx, [area] + lea rdi, [grid] + xor al, al + rep stosb + + xor rdi, rdi ; pos = 0 + mov rsi, r9 ; empty budget + call rec + test rax, rax + jz .ret + inc qword [count_feasible] +.ret: + ret + +; rec(RDI=pos, RSI=empty_budget) -> RAX 1 if the remaining pieces fit. +; State: R12=pos R13=eb R14=row R15=col RBX=shape RBP=orientation. +rec: + push rbx + push rbp + push r12 + push r13 + push r14 + push r15 + mov r12, rdi + mov r13, rsi + cmp qword [left], 0 + je .true +.adv: + cmp r12, [area] + jae .false + cmp byte [grid + r12], 0 + je .found + inc r12 + jmp .adv +.found: + mov rax, r12 + xor rdx, rdx + div qword [rW] + mov r14, rax ; row + mov r15, rdx ; col + + xor rbx, rbx ; shape +.s_loop: + cmp rbx, 6 + jge .try_empty + cmp qword [remaining + rbx*8], 0 + je .s_next + xor rbp, rbp ; orientation +.t_loop: + cmp rbp, 8 + jge .s_next + mov rax, rbx + shl rax, 3 + add rax, rbp + mov r10, rax ; orientation index + mov r11, [oncells + r10*8] + ; validate placement + xor rcx, rcx +.chk: + cmp rcx, r11 + jge .place + mov rax, r10 + imul rax, 9 + add rax, rcx + movsxd r8, dword [odr + rax*4] + movsxd r9, dword [odc + rax*4] + add r8, r14 ; rr + add r9, r15 ; cc + cmp r8, [rL] + jge .t_next + cmp r9, 0 + jl .t_next + cmp r9, [rW] + jge .t_next + mov rax, r8 + imul rax, [rW] + add rax, r9 + cmp byte [grid + rax], 0 + jne .t_next + inc rcx + jmp .chk +.place: + xor rcx, rcx +.place_k: + cmp rcx, r11 + jge .place_done + mov rax, r10 + imul rax, 9 + add rax, rcx + movsxd r8, dword [odr + rax*4] + movsxd r9, dword [odc + rax*4] + add r8, r14 + add r9, r15 + imul r8, [rW] + add r8, r9 + mov byte [grid + r8], 1 + inc rcx + jmp .place_k +.place_done: + dec qword [remaining + rbx*8] + dec qword [left] + mov rdi, r12 + mov rsi, r13 + call rec + test rax, rax + jnz .true + inc qword [remaining + rbx*8] + inc qword [left] + mov rax, rbx ; child clobbered r10/r11 - rebuild them + shl rax, 3 + add rax, rbp + mov r10, rax + mov r11, [oncells + r10*8] + xor rcx, rcx +.unplace_k: + cmp rcx, r11 + jge .unplace_done + mov rax, r10 + imul rax, 9 + add rax, rcx + movsxd r8, dword [odr + rax*4] + movsxd r9, dword [odc + rax*4] + add r8, r14 + add r9, r15 + imul r8, [rW] + add r8, r9 + mov byte [grid + r8], 0 + inc rcx + jmp .unplace_k +.unplace_done: +.t_next: + inc rbp + jmp .t_loop +.s_next: + inc rbx + jmp .s_loop +.try_empty: + test r13, r13 + jz .false + mov byte [grid + r12], 1 + mov rdi, r12 + mov rsi, r13 + dec rsi + call rec + test rax, rax + jnz .true + mov byte [grid + r12], 0 +.false: + xor eax, eax + jmp .ret +.true: + mov eax, 1 +.ret: + pop r15 + pop r14 + pop r13 + pop r12 + pop rbp + pop rbx + 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 diff --git a/aoc-2025/day9.asm b/aoc-2025/day9.asm new file mode 100644 index 0000000..8b0edcf --- /dev/null +++ b/aoc-2025/day9.asm @@ -0,0 +1,644 @@ +; Advent of Code 2025 - Day 9 + +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 262144 +%define MAXN 512 +%define MAXC 1024 +%define MAXR 1024 +%define MAXP ((MAXC + 1) * (MAXR + 1)) + +section .data + input_path db "input/day9.txt", 0 + + newline db 10 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + vx resq MAXN + vy resq MAXN + xs resq MAXN + ys resq MAXN + xs_to_col resd MAXN + ys_to_row resd MAXN + col_lo resq MAXC + row_lo resq MAXR + thincol resd MAXN + thinrow resd MAXN + + vex resq MAXN ; vertical edges: x, ylo, yhi + veylo resq MAXN + veyhi resq MAXN + hey resq MAXN ; horizontal edges: y, xlo, xhi + hexlo resq MAXN + hexhi resq MAXN + + pref resd MAXP ; 2D prefix sum of unfilled cells + + raw_len resq 1 + n_v resq 1 + xn resq 1 + yn resq 1 + c_cnt resq 1 + r_cnt resq 1 + cp1 resq 1 + ve_cnt resq 1 + he_cnt resq 1 + best1 resq 1 + best2 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 + + 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 + + ; parse "X,Y" vertices in order + lea rsi, [raw] + mov rax, [raw_len] + lea r14, [raw + rax] + xor r12, r12 +parse_line: + cmp rsi, r14 + jae parse_done + mov al, [rsi] + cmp al, 10 + je parse_skipnl + cmp al, 13 + je parse_skipnl + call parse_u64 + mov [vx + r12*8], rax + inc rsi + call parse_u64 + mov [vy + r12*8], rax + inc r12 +parse_eol: + cmp rsi, r14 + jae parse_done + mov al, [rsi] + inc rsi + cmp al, 10 + jne parse_eol + jmp parse_line +parse_skipnl: + inc rsi + jmp parse_line +parse_done: + mov [n_v], r12 + + ; xs = sorted, deduped x coordinates + xor rcx, rcx +copy_xs: + cmp rcx, [n_v] + jge copy_xs_done + mov rax, [vx + rcx*8] + mov [xs + rcx*8], rax + inc rcx + jmp copy_xs +copy_xs_done: + lea rdi, [xs] + mov rsi, [n_v] + call sort_q + lea rdi, [xs] + mov rsi, [n_v] + call dedup_q + mov [xn], rax + + ; ys = sorted, deduped y coordinates + xor rcx, rcx +copy_ys: + cmp rcx, [n_v] + jge copy_ys_done + mov rax, [vy + rcx*8] + mov [ys + rcx*8], rax + inc rcx + jmp copy_ys +copy_ys_done: + lea rdi, [ys] + mov rsi, [n_v] + call sort_q + lea rdi, [ys] + mov rsi, [n_v] + call dedup_q + mov [yn], rax + + ; refined columns: thin at each xs, thick strip between + xor rcx, rcx ; i + xor r12, r12 ; column count +build_cols: + cmp rcx, [xn] + jge build_cols_done + mov [xs_to_col + rcx*4], r12d + mov rax, [xs + rcx*8] + mov [col_lo + r12*8], rax + inc r12 + mov rdx, rcx + inc rdx + cmp rdx, [xn] + jge build_cols_next + mov r8, [xs + rdx*8] + mov rax, [xs + rcx*8] + sub r8, rax + cmp r8, 1 + jle build_cols_next + inc rax + mov [col_lo + r12*8], rax + inc r12 +build_cols_next: + inc rcx + jmp build_cols +build_cols_done: + mov [c_cnt], r12 + inc r12 + mov [cp1], r12 + + ; refined rows: thin at each ys, thick strip between + xor rcx, rcx + xor r12, r12 +build_rows: + cmp rcx, [yn] + jge build_rows_done + mov [ys_to_row + rcx*4], r12d + mov rax, [ys + rcx*8] + mov [row_lo + r12*8], rax + inc r12 + mov rdx, rcx + inc rdx + cmp rdx, [yn] + jge build_rows_next + mov r8, [ys + rdx*8] + mov rax, [ys + rcx*8] + sub r8, rax + cmp r8, 1 + jle build_rows_next + inc rax + mov [row_lo + r12*8], rax + inc r12 +build_rows_next: + inc rcx + jmp build_rows +build_rows_done: + mov [r_cnt], r12 + + ; per-vertex refined thin column / row index + xor r8, r8 +map_v: + cmp r8, [n_v] + jge map_v_done + mov r13, [vx + r8*8] + xor rcx, rcx +map_v_xs: + mov rax, [xs + rcx*8] + cmp rax, r13 + je map_v_xf + inc rcx + jmp map_v_xs +map_v_xf: + mov edx, [xs_to_col + rcx*4] + mov [thincol + r8*4], edx + mov r13, [vy + r8*8] + xor rcx, rcx +map_v_ys: + mov rax, [ys + rcx*8] + cmp rax, r13 + je map_v_yf + inc rcx + jmp map_v_ys +map_v_yf: + mov edx, [ys_to_row + rcx*4] + mov [thinrow + r8*4], edx + inc r8 + jmp map_v +map_v_done: + + ; classify edges into vertical / horizontal + xor r8, r8 + xor r12, r12 ; ve count + xor r13, r13 ; he count +gen_edges: + cmp r8, [n_v] + jge gen_edges_done + mov r9, r8 + inc r9 + cmp r9, [n_v] + jne ge_nowrap + xor r9, r9 +ge_nowrap: + mov r10, [vx + r8*8] + mov r11, [vx + r9*8] + cmp r10, r11 + je ge_vert + mov rax, [vy + r8*8] + mov [hey + r13*8], rax + mov rcx, r10 + mov rdx, r11 + cmp rcx, rdx + jle ge_h_ok + xchg rcx, rdx +ge_h_ok: + mov [hexlo + r13*8], rcx + mov [hexhi + r13*8], rdx + inc r13 + jmp ge_next +ge_vert: + mov [vex + r12*8], r10 + mov rcx, [vy + r8*8] + mov rdx, [vy + r9*8] + cmp rcx, rdx + jle ge_v_ok + xchg rcx, rdx +ge_v_ok: + mov [veylo + r12*8], rcx + mov [veyhi + r12*8], rdx + inc r12 +ge_next: + inc r8 + jmp gen_edges +gen_edges_done: + mov [ve_cnt], r12 + mov [he_cnt], r13 + + ; 2D prefix sum of unfilled cells + xor r15, r15 ; refined row r +pref_r: + cmp r15, [r_cnt] + jge pref_done + mov r13, [row_lo + r15*8] ; py + xor r14, r14 ; refined col c +pref_c: + cmp r14, [c_cnt] + jge pref_c_done + mov rdi, [col_lo + r14*8] + mov rsi, r13 + call filled + mov rbx, 1 + sub rbx, rax ; unfilled indicator + + mov rax, r15 + imul rax, [cp1] ; r*cp1 + mov rcx, rax + add rcx, r14 + add rcx, 1 + mov edx, [pref + rcx*4] ; P[r][c+1] + mov rcx, rax + add rcx, r14 + mov r8d, [pref + rcx*4] ; P[r][c] + mov rcx, rax + add rcx, [cp1] + mov r9, rcx ; (r+1)*cp1 + add rcx, r14 + mov r10d, [pref + rcx*4] ; P[r+1][c] + mov eax, ebx + add eax, edx + add eax, r10d + sub eax, r8d + mov rcx, r9 + add rcx, r14 + add rcx, 1 + mov [pref + rcx*4], eax ; P[r+1][c+1] + inc r14 + jmp pref_c +pref_c_done: + inc r15 + jmp pref_r +pref_done: + + ; all pairs: part 1 = max area, part 2 = max area fully inside + mov qword [best1], 0 + mov qword [best2], 0 + xor r8, r8 +pair_i: + cmp r8, [n_v] + jge pair_done + mov r12d, [thincol + r8*4] + mov r13d, [thinrow + r8*4] + mov r14, [vx + r8*8] + mov r15, [vy + r8*8] + lea r9, [r8 + 1] +pair_j: + cmp r9, [n_v] + jge pair_j_done + + ; area = (|xi-xj| + 1) * (|yi-yj| + 1) + mov rax, r14 + sub rax, [vx + r9*8] + jns .ax + neg rax +.ax: + inc rax + mov rbx, rax + mov rax, r15 + sub rax, [vy + r9*8] + jns .ay + neg rax +.ay: + inc rax + imul rax, rbx + cmp rax, [best1] + jle .no1 + mov [best1], rax +.no1: + push rax ; save area + + ; refined block: c1,c2 then r1,r2 + mov eax, [thincol + r9*4] + mov ecx, r12d + cmp ecx, eax + jle .cc + xchg ecx, eax +.cc: + mov edi, ecx ; c1 + mov esi, eax ; c2 + mov eax, [thinrow + r9*4] + mov ecx, r13d + cmp ecx, eax + jle .rr + xchg ecx, eax +.rr: + mov edx, ecx ; r1 + mov ecx, eax ; r2 + call block_unf + pop rbx ; area + test eax, eax + jnz .no2 ; contains unfilled cells + cmp rbx, [best2] + jle .no2 + mov [best2], rbx +.no2: + inc r9 + jmp pair_j +pair_j_done: + inc r8 + jmp pair_i +pair_done: + +print_results: + mov rcx, label1 + call print_string + mov rax, [best1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [best2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; filled: is tile (RDI=px, RSI=py) red or green (inside or on the loop)? +; Output: RAX = 1 if filled, else 0. Clobbers RAX, RCX, RDX, R10, R11. +filled: + xor ecx, ecx ; on-edge flag + xor r11, r11 ; crossing count + xor r10, r10 ; edge index +.v_loop: + cmp r10, [ve_cnt] + jge .v_done + mov rax, [vex + r10*8] + cmp rax, rdi + jne .v_cross + mov rdx, [veylo + r10*8] + cmp rsi, rdx + jl .v_cross + mov rdx, [veyhi + r10*8] + cmp rsi, rdx + jg .v_cross + mov ecx, 1 ; on a vertical edge +.v_cross: + mov rax, [vex + r10*8] + cmp rax, rdi + jle .v_next + mov rdx, [veylo + r10*8] + cmp rsi, rdx + jl .v_next + mov rdx, [veyhi + r10*8] + cmp rsi, rdx + jge .v_next + inc r11 +.v_next: + inc r10 + jmp .v_loop +.v_done: + test ecx, ecx + jnz .yes + xor r10, r10 +.h_loop: + cmp r10, [he_cnt] + jge .h_done + mov rax, [hey + r10*8] + cmp rax, rsi + jne .h_next + mov rdx, [hexlo + r10*8] + cmp rdi, rdx + jl .h_next + mov rdx, [hexhi + r10*8] + cmp rdi, rdx + jg .h_next + jmp .yes +.h_next: + inc r10 + jmp .h_loop +.h_done: + mov rax, r11 + and rax, 1 + ret +.yes: + mov rax, 1 + ret + +; block_unf: count of unfilled refined cells in [c1,c2] x [r1,r2]. +; In: RDI=c1, RSI=c2, RDX=r1, RCX=r2. Out: EAX. Clobbers RAX, R10, R11. +block_unf: + mov r10, rcx + inc r10 + imul r10, [cp1] ; (r2+1)*cp1 + mov r11, r10 + add r11, rsi + add r11, 1 + mov eax, [pref + r11*4] ; A + mov r11, r10 + add r11, rdi + sub eax, [pref + r11*4] ; - C + mov r10, rdx + imul r10, [cp1] ; r1*cp1 + mov r11, r10 + add r11, rsi + add r11, 1 + sub eax, [pref + r11*4] ; - B + mov r11, r10 + add r11, rdi + add eax, [pref + r11*4] ; + D + ret + +; sort_q: insertion sort of qword array RDI[0..RSI-1] ascending. +; Clobbers RAX, RDX, R8, R9, R10. +sort_q: + mov r8, 1 +.i: + cmp r8, rsi + jge .done + mov r10, [rdi + r8*8] + mov r9, r8 + dec r9 +.j: + cmp r9, 0 + jl .place + mov rax, [rdi + r9*8] + cmp rax, r10 + jle .place + mov rdx, r9 + inc rdx + mov [rdi + rdx*8], rax + dec r9 + jmp .j +.place: + mov rdx, r9 + inc rdx + mov [rdi + rdx*8], r10 + inc r8 + jmp .i +.done: + ret + +; dedup_q: remove consecutive duplicates in sorted RDI[0..RSI-1]. +; Out: RAX = new length. Clobbers RAX, RCX, RDX, R8. +dedup_q: + xor rax, rax + xor rcx, rcx +.loop: + cmp rcx, rsi + jge .done + test rax, rax + jz .keep + mov rdx, [rdi + rcx*8] + mov r8, rax + dec r8 + cmp rdx, [rdi + r8*8] + je .skip +.keep: + mov rdx, [rdi + rcx*8] + mov [rdi + rax*8], rdx + inc rax +.skip: + inc rcx + jmp .loop +.done: + ret + +; parse_u64: read decimal digits at [RSI], advancing RSI. 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 + +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 |