Welcome back to another round of Simple Sudoku Solvers! If you\nare unfamiliar with the series, I suggest you start with the\nfirst post or by perusing the backlog. Last time, in Agda,\nthe solver wasn’t allowed to hand us a board without a correctness\nproof. Today we go in the opposite direction: assembly, where nothing is\nchecked at all, and the machine stares at us directly.
\nTo be quite specific, today we’ll write AArch64 assembly for macOS,\nbecause that’s the machine I’m sitting at1.\nSurprisingly, the solver is just a little over 200 lines, and as always,\nthe code is on\nGitHub.
\nSeason three is about solvers, specifications, and constraints, and\nassembly might seem like the odd duck. But I think it fits!
\nAfter a proof assistant that checks everything, it’s worth looking at\nwhat’s left when nothing is checked, and nothing is proven.
\nNothing is hidden. There is no allocator, no
garbage collector, no runtime, and no compiler making choices for us.\nThe board gets copied because we wrote exactly the instructions that\ncopy it.
The machine already knows our tricks! We’ve been
doing bit-twiddling with candidate masks since the\nCommon Lisp episode, and in Forth\nwe had to roll our own popcount and lowest-bit search. The CPU has\ninstructions for most of that, and today we get to use them directly.\nSo, in many ways, we gain some abstractions!
The stack is, uh, the stack. In Forth we built our
own stack of boards for backtracking. Here, the machine stack is right\nthere, so we might as well use it.
Since there are no types, everything is a number, and the only thing\nstanding between us and a wrong answer is our own diligence. Fun!
\nIf you’ve never read ARM assembly before, here is what you need for\nthis post.
\nAArch64 has 31 general-purpose registers, x0 to\nx30, each 64 bits wide. Writing w0 instead of\nx0 means “the lower 32 bits of register 0”, and since all\nof our numbers are small, we’ll use w registers most of the\ntime. sp is the stack pointer.
Instructions read like op destination, source, source,\nso add w0, w1, w2 means w0 = w1 + w2. Memory\nis only touched by loads and stores:\nldrb w9, [x19, w21, uxtw] loads the byte at address\nx19 + w21 into w9, and strb\nstores one. [x7], #1 means “load from x7, then\nadd 1 to x7”, which is handy for walking through\nmemory.
We call functions with bl, which jumps and stores the\nreturn address in x30, and we return with ret,\nwhich jumps back to x30. Arguments go in x0\nand up, and the result comes back in x0. A function may\nfreely overwrite x0 to x17 (x18\nis reserved), but has to restore x19 to x28\nbefore it returns, so those are where we keep anything we need to\nsurvive a call.
Labels like 1: are local, and b.ne 1b means\n“branch to the closest label 1 going\nb**ackwards, if the last comparison was\n*not e*qual”. 1f looks\n**forwards. Comments start with //.
That should be enough to get through it. Everything else I’ll explain\nas we go. I recommend keeping your favorite drawing tool (pen and paper\nwork well) handy to simulate the stack and register movement in your\nhead. I’ve always had trouble with the mnemonics, so I read assembly\ndifferently than most other programming languages, modelling stack and\nregister state as I go. Maybe that works for you as well!
\nThe board is the same flat array of 81 bytes that we’ve been using\nfor most of the series, with 0 for an empty cell. We put it\nin the data section (which means it’s baked into the executable quite\nliterally), with the puzzle already filled in:
.data\n .p2align 4\nboard: .byte 8,0,0,0,0,0,0,0,0\n .byte 0,0,3,6,0,0,0,0,0\n .byte 0,7,0,0,9,0,2,0,0\n .byte 0,5,0,0,0,7,0,0,0\n .byte 0,0,0,0,4,5,7,0,0\n .byte 0,0,0,1,0,0,0,3,0\n .byte 0,0,1,0,0,0,0,6,8\n .byte 0,0,8,5,0,0,0,1,0\n .byte 0,9,0,0,0,0,4,0,0This is the same puzzle we used in the Agda episode, and it’s one of\nthe harder ones I use for checking. .p2align 4 aligns the\nboard to 16 bytes. Strictly speaking we don’t need that, but we’re about\nto copy it around in 16-byte chunks, and it doesn’t cost us anything, so\nwe might as well do it.
There is one global board, and the solver mutates it in place.\nWhatever is in board when solve returns is our\nanswer.
As always, we’ll go outside-in. This is solve in its\nentirety, and it is the longest function in the file, so we’ll take it\nin pieces.
solve:\n stp x29, x30, [sp, #-64]!\n mov x29, sp\n stp x19, x20, [sp, #16]\n stp x21, x22, [sp, #32]\n str x23, [sp, #48]\n bl propagate\n cbz w0, failThe first five lines are the prologue, which is the ceremony every\nfunction that calls other functions usually goes through (it’s also the\nmain thing that distinguishes functions and labels inside the block). We\nreserve 64 bytes on the stack, save our return address\n(x30) and the frame pointer (x29), and save\nthe callee-saved registers we’re about to use. stp stores a\npair of registers in one go, and the ! means “update\nsp first”.
The rest is familiar. We propagate, and if propagation hits a dead\nend, we fail. cbz is “compare and branch if zero”, which\ncomes up a lot, because it’s basically an if statement.
Next up is finding the cell with the fewest candidates:
\n adrp x19, board@PAGE\n add x19, x19, board@PAGEOFF\n mov w20, #-1 // best cell\n mov w21, #10 // its candidate count\n mov w22, #0 // cell\nmrv:\n ldrb w9, [x19, w22, uxtw]\n cbnz w9, 1f\n mov w0, w22\n bl cands\n fmov s0, w0\n cnt v0.8b, v0.8b\n addv b0, v0.8b\n fmov w9, s0\n cmp w9, w21\n b.hs 1f\n mov w21, w9\n mov w20, w22\n mov w23, w0 // its candidates\n1: add w22, w22, #1\n cmp w22, #81\n b.lo mrv\n tbnz w20, #31, done // no empty cell leftThe first two lines load the address of the board. On AArch64, an\ninstruction is always 32 bits wide, so you can’t fit a full address into\none. Instead, adrp gets the address of the 4KB page the\nboard is on, and add adds the offset within that page.\nYou’ll see this pair a lot. It’s a weird little ceremony if you ask me,\nbut nobody did.
Then we loop over all 81 cells. Filled cells are skipped. For empty\ncells, we get the candidate mask from cands and count its\nbits, and if the count beats the best one so far, we remember the cell,\nthe count, and the mask.
Counting bits is the first weird, delightful bit. Base AArch64 has no\ninstruction for counting the bits in a general-purpose\nregister2. It does have one for its vector\nregisters, though. cnt counts the bits in each of eight\nbytes, and addv adds those eight counts up. So we move our\nmask over to the vector unit with fmov, count there, and\nmove the result back. It’s four instructions instead of the\nnine-iteration loop we wrote in Forth where we implemented bit-counting\nby hand.
w20 starts out as -1 (all ones in binary).\nIf it’s unchanged after the loop, there are no empty cells left, and\nwe’re done. tbnz tests a single bit and branches if it is\nset, and bit 31 is the sign bit, so this is a cheap “is it negative?”\ncheck, and another one of those idioms you just kind of have to\nknow.
Note that we never check if the best cell has zero candidates.\nPropagation already returns a dead end for that, so by the time we\nselect one, every cell has at least one candidate.
\nNow for the backtracking:
\n sub sp, sp, #96\n copy81 sp, x19\ntry:\n rbit w9, w23\n clz w9, w9\n strb w9, [x19, w20, uxtw]\n bl solve\n cbnz w0, found\n copy81 x19, sp\n sub w9, w23, #1\n and w23, w23, w9 // drop the digit we tried\n cbnz w23, try\n add sp, sp, #96Before we try anything, we make room on the stack and copy the board\nthere. The board is 81 bytes, but the stack pointer has to stay aligned\nto 16 bytes, so we take 96, more ceremony.
\nThis is basically what we did in Forth with the board stack, except\nthat it lives on the “real” stack, grows by itself with recursion, and\ngets popped when we return. We don’t have to pick a maximum depth this\ntime, though the depth is bounded anyway, since every level fills at\nleast one cell.
\nThen we try each candidate. rbit reverses the bits of\nthe mask and clz counts the leading zeros, which together\ngive us the position of the lowest set bit. That’s the trailing zero\ncount we also used before, in Rust,\nand as we’ll see in a minute, the position of the bit maps to the digit.\nFinally, we write the digit into the cell and recurse!
If the recursive call succeeds, we’re done. Otherwise we copy the\nsaved board back and drop the digit we just tried from the mask.\nx & (x - 1) clears the lowest set bit of x\n(still one of my favorite little tricks from the series), and when the\nmask is empty, we’ve run out of options.
The rest is bookkeeping:
\nfail:\n mov w0, #0\n b 1f\nfound:\n add sp, sp, #96\ndone:\n mov w0, #1\n1: ldr x23, [sp, #48]\n ldp x21, x22, [sp, #32]\n ldp x19, x20, [sp, #16]\n ldp x29, x30, [sp], #64\n retWe set the return value and undo the prologue, in reverse. The only\nsubtle part is the order of the labels. found has to give\nthe 96 bytes of board back before falling through into\ndone. fail and done can be\nreached without them, so they have to navigate around\nfound.
You won’t notice right away if you mess any of this up (ask me how I\nknow). If you’re lucky it’ll just crash, if you’re not, it’ll return\nsomewhere random. There are no types to catch you, and nothing checks\nthat you restore what you saved. Functions by hand.
\ncopy81 is a macro. The assembler has a simple macro\nsystem, which we use to avoid writing the same eight lines twice (you\nknow that I’m a macro fiend):
.macro copy81 dst, src\n ldp q0, q1, [\\src]\n stp q0, q1, [\\dst]\n ldp q0, q1, [\\src, #32]\n stp q0, q1, [\\dst, #32]\n ldr q0, [\\src, #64]\n str q0, [\\dst, #64]\n ldrb w9, [\\src, #80]\n strb w9, [\\dst, #80]\n.endmq0 and q1 are 128-bit vector registers, so\none ldp moves 32 bytes. Two pairs and a single give us 80\nbytes, and one more byte gets us to 81.
It’s basically memcpy, specialized to our board!
Propagation is the loop we’ve written way too often at this point. We\nfill every cell that has a single candidate, and keep going until\nnothing changes.
\npropagate:\n stp x29, x30, [sp, #-48]!\n mov x29, sp\n stp x19, x20, [sp, #16]\n str x21, [sp, #32]\n adrp x19, board@PAGE\n add x19, x19, board@PAGEOFF\nagain:\n mov w20, #0 // changed?\n mov w21, #0 // cell\ncell:\n ldrb w9, [x19, w21, uxtw]\n cbnz w9, next\n mov w0, w21\n bl cands\n cbz w0, dead\n sub w9, w0, #1\n tst w0, w9\n b.ne next // more than one candidate\n rbit w9, w0\n clz w9, w9\n strb w9, [x19, w21, uxtw]\n mov w20, #1\nnext:\n add w21, w21, #1\n cmp w21, #81\n b.lo cell\n cbnz w20, again\n mov w0, #1\n b 1f\ndead:\n mov w0, #0\n1: ldr x21, [sp, #32]\n ldp x19, x20, [sp, #16]\n ldp x29, x30, [sp], #48\n retThere are two small departures from earlier versions.
\nFirst, we don’t need popcount here. We only care whether a mask has\nexactly one bit set, and our x & (x - 1) trick can\nanswer that. It’s zero exactly when there was at most one bit.\ntst computes the and without storing it, so we\ndon’t even need an extra register.
Second, the contradiction check is folded in. In Forth, we had a\nseparate contradiction? pass after propagation. Here, if\nany empty cell has no candidates, we nope out on the spot with\ncbz w0, dead. It means that an invalid input puzzle can\npass, but surely no one would hand us the wrong input?
This is where the bit tricks pay their dues. We need the set of\ndigits that don’t appear in a cell’s row, column, or box. As in every\nother bitmask solver so far, we collect the digits we’ve seen in a mask\nand invert it at the end.
\nThere is one change from before, though. Usually digit d\nlives in bit d-1, so we have to skip empty cells, because\nthere is no bit -1.
Here, digit d lives in bit d. Empty cells\nare 0, so they set bit 0, and we throw that bit away at the end. That\nmeans we never have to check whether a cell is empty, and no branching\nis needed.
It also means that the position of a bit is the digit, which is what\nsaved us the + 1 in solve and\npropagate.
Since we do this for 27 cells, it too gets its own macro:
\n.macro mark used, at\n ldrb w10, \\at\n lsl w10, w6, w10\n orr \\used, \\used, w10\n.endmw6 holds 1, so this loads a cell, shifts 1 left by its\nvalue, and ors it into the mask. With that, the candidate\nfunction becomes three loops:
cands:\n adrp x9, board@PAGE\n add x9, x9, board@PAGEOFF\n mov w2, #9\n udiv w3, w0, w2 // row\n msub w4, w3, w2, w0 // col\n mov w5, #0 // used digits\n mov w6, #1\n\n mul w7, w3, w2\n add x7, x9, w7, uxtw // first cell of the row\n mov w8, #9\n1: mark w5, "[x7], #1"\n subs w8, w8, #1\n b.ne 1b\n\n add x7, x9, w4, uxtw // first cell of the column\n mov w8, #9\n2: mark w5, "[x7], #9"\n subs w8, w8, #1\n b.ne 2b\n\n mov w2, #3\n udiv w3, w3, w2\n mov w8, #27\n mul w3, w3, w8 // box row offset\n udiv w4, w4, w2\n mul w4, w4, w2 // box column offset\n add w3, w3, w4\n add x7, x9, w3, uxtw // first cell of the box\n mov w8, #3\n3: mark w5, "[x7]"\n mark w5, "[x7, #1]"\n mark w5, "[x7, #2]"\n add x7, x7, #9\n subs w8, w8, #1\n b.ne 3b\n\n mvn w0, w5\n and w0, w0, #0x3fe\n retThere is no modulo instruction, so to get the column we divide\n(udiv) and then compute cell - row * 9 with\nmsub, which multiplies and subtracts in one go. This seems\nlike a clever trick at first, but again, this is one of those tricks\nyou’ll just find online and then try to remember every time until it’s\nhard-wired in your brain.
The row loop walks nine consecutive bytes, and the column loop walks\nwith a stride of nine. The box loop unrolls the three cells of each box\nrow and then skips ahead by nine. The box offset is the same arithmetic\nwe did in Forth, 27 for every block of rows, and 3 for every block of\ncolumns. cands doesn’t call anything, so it only uses\nregisters it may clobber, and we can skip the prologue entirely. This\nmight not be a good idea in big programs written by multiple people, but\nit’s fine between lazy friends.
At the end, mvn inverts the mask and the\nand keeps bits 1 to 9. That throws away bit 0, where the\nempty cells went, and all the bits above 9, which the inversion set (but\nwhich we don’t care about).
And that’s about it!
\nOn my machine, the whole program takes about 4 milliseconds, and\nroughly 1.7 of those are the operating system starting a process. The\nPython reference takes about 70 milliseconds for the same puzzle, and\nAgda took 2.7 seconds. I didn’t do anything clever to make it fast,\neither. It recomputes candidates from scratch every time, just like the\nForth solver did. There just isn’t anything to slow us down except our\nown laziness.
\nWe wrote a Sudoku solver in about 200 lines of assembly, and we used\nnative bit instructions to do what we’ve been emulating before. We kept\nour backtracking boards on the “real” stack, and we learned some cool\nnew tricks like x & (x - 1).
This episode remains the surprise guest this season, but I did enjoy\nwriting it. If the Agda episode was about trusting nothing but our spec,\nthis was about trusting nothing, period. Nothing verified that we\nrestored our registers or that our stack stayed aligned.
\nPersonally, I prefer the proof, but it was fun to find out how to do\nit with just our CPU.
\nIn the next episode, we go even lower: Verilog, where there are no\ninstructions anymore, only wires and blinkenlights. See you there!
\nIf you’re on Linux on an ARM machine, two
things change, according to untested claims by a language genie. System\ncalls take their number in x8 and use svc #0,\nand write is number 64 there. Addresses are written as\nadrp x9, board and\nadd x9, x9, :lo12:board.
By the way, Apple doesn’t promise that system call numbers stay\nstable, and officially you should go through the C library. For a blog\npost, I think we can live with that. Just harden your production version\na bit.
\nNewer revisions of the architecture added one,
but I didn’t want to depend on that, and I also wanted to show what\nyou’ll see in a lot of other places.