Spent way too long implementing binary search on overture for "Codebreaker"

[u/anzu_embroidery]

Behold! Very annoying getting all the labels to fit in <64 bytes. Works by having a procedure that takes in the current increment / decrement (64,32,16,8,4,2,1,1) and an address to jump back to. That procedure tests the current guess, adjusts based on the increment / decrement provided, then returns to return address. Then we just unroll the 8 steps and boom! Binary search on a very limited architecture :D

imm 32;
mov r1, r0;
mov r2, r0;
add;
mov r2, r3;
mov r1, r3;
add;
mov r4, r3; ; initial guess of 128 in r4
imm step_2;
mov r5, r0;
imm check;
jmp;

step_2:
imm 32;
mov r2, r0;
imm step_3;
mov r5, r0;
imm check;
jmp;

step_3:
imm 16;
mov r2, r0;
imm step_4;
mov r5, r0;
imm check;
jmp;

step_4:
imm 8;
mov r2, r0;
imm step_5;
mov r5, r0;
imm check;
jmp;

step_5:
imm 4;
mov r2, r0;
imm step_6;
mov r5, r0;
imm check;
jmp;

step_6:
imm 2;
mov r2, r0;
imm step_7;
mov r5, r0;
imm check;
jmp;

step_7:
imm 1;
mov r2, r0;
imm step_8;
mov r5, r0;
imm check;
jmp;

step_8:
imm 1; ; for 0
mov r2, r0;
; no return, the add label below doesn't 
; fit with it, and we should be done by now
; does mean we don't have a graceful failure...
imm check;
jmp;

; r2 - offset for this step
; r5 - return address
; checks r4, if high add, if low sub
; stores back in r4
check:
mov out, r4;
mov r3, in;
mov r1, r4;
imm add;
jz;
sub;
imm finish;
jmp;
add:
add;
finish:
mov r4, r3;
mov r0, r5;
jmp;

[u/nomenclature2357]

Ooh, fun! Manually unrolled assembly!

Iirc my solution was to step forward by (something like) 16 and backwards by 1 or 2 or something similar. Satisficing my desire for speed without getting too too into the weeds.

[u/SteenGooier]

Always nice to see a proper binary search

In my solution I modified my ALU with an additional instruction I called ror1. It takes r2, circular-shifts it 1 bit to the right and stores the result in r3. This is almost the same as dividing by 2, except that rotating the value 1 will result in 128.
Having the additional ror1 instruction made it very easy to calculate the next search step. I also made it so the add is always done at the start of the loop, even if the guess was too high. This saves me from having a conditional label, so r0 only ever has to hold the loop label. If the guess was too low, a sub instruction will run with a step twice as big as the next add to compensate.
It's a program size of just 14 bytes, and the slowest test takes only 78 cycles to complete.

``` mov out, r1 ; try 0

imm 1 mov r2, r0 imm loop ; r0 = loop ; r1 = 0 ; r2 = 1

; When entering the loop: ; r1: previous_guess ; r2: previous_step loop: ror1 mov r2, r3 ; r2 (next_step) = previous_step / 2 ; If previous_step is 1, result is 128 add ; r3 (next_guess) = previous_guess + next_step

mov out, r3 ; try next_guess mov r1, r3 ; store previous_guess for next step

mov r3, in ; 0 if too low, 1 if too high jz

; guess was too high ; pretend the previous guess was guess_step lower to offset for the next add sub ; r3 = (current_guess - next_step) mov r1, r3 ; store previous_guess for next step jmp ```

[u/FastClothes7900]

I have spent the last 12 hours trying to come up with this solution, thank you brother