From 25844ee408f73893175a8dc999391df0a3ed377a Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sat, 22 Dec 2018 01:00:42 +0100 Subject: Day 21 --- 2018/21_notes.txt | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+) create mode 100644 2018/21_notes.txt (limited to '2018/21_notes.txt') diff --git a/2018/21_notes.txt b/2018/21_notes.txt new file mode 100644 index 0000000..905f861 --- /dev/null +++ b/2018/21_notes.txt @@ -0,0 +1,100 @@ +L0: // r4 <- 123 + // r4 <- 72 + // r4 <- 1 + jmp L1 + // jmp L0 +L1: r4 <- 0 +L2: r3 <- r4 | 65536 + r4 <- 3730679 +L3: // r5 <- r3 & 255 + // r4 <- r4 + (r3 & 255) + // r4 <- (r4 + (r3 & 255)) & 16777215 + // r4 <- ((r4 + (r3 & 255)) & 16777215) * 65899 + r4 <- (((r4 + (r3 & 255)) & 16777215) * 65899) & 16777215 + // r5 <- 256 > r3 + if (r3 >= 256) + then jmp L4 + else jmp L8 +L4: r5 <- 0 +L5: r2 <- r5 + 1 + r2 <- r2 * 256 + // r2 <- r2 > r3 + if (r2 <= r3) + then jmp L6 + else jmp L7 +L6: r5 <- r5 + 1 + jmp L5 +L7: r3 <- r5 + jmp L3 +L8: // r5 <- r4 == r0 + if (r4 != r0) + then jmp L2 + [else exit] + + + ↓‾‾‾‾‾‾‾‾‾‾‾| +0 → 1 → 2 → 3 → 4 → 5 → 7 + ↑ ↓ ↕ + └── 8 6 + ↓ + * + +L5: +loop { + r2 = (r5 + 1) * 256; + if r2 > r3 { jmp L7; } + r5 += 1; +} + +L5: +Let x = ceil((r3 + 1) / 256). +Set r5 = x - 1; r2 = x * 256. +Jump to L7. +This takes (x+1)*5+2*x = 7*x+5 instructions. + + +// -------------------------- + + +L0: jmp L1 [4 instrs] +L1: r4 <- 0 +L2: r3 <- r4 | 65536 + r4 <- 3730679 +L3: r4 <- (((r4 + (r3 & 0xff)) & 0xffffff) * 65899) & 0xffffff [6 instrs] + if (r3 >= 256) + then jmp L4 + else jmp L8 +L4: Set r3 = ceil((r3 + 1) / 256) - 1. [7*ceil((r3+1)/256)+6 instrs] + jmp L3 +L8: // r5 <- r4 == r0 + if (r4 != r0) + then jmp L2 + [else exit] + + + ↓‾‾‾| +0 → 1 → 2 → 3 → 4 + ↑ ↓ + └── 8 + ↓ + * + + +// -------------------------- + + +Earliest exit is if r0 is equal to the value in r4 on the first arrival at L8. + + +L3: +loop { + r4 = (((r4 + (r3 & 0xff)) & 0xffffff) * 65899) & 0xffffff [6 instrs] + if r3 < 256 { jmp L8 } + r3 = ceil((r3 + 1) / 256) - 1 [7*ceil((r3+1)/256)+6 instrs] +} + +exit at 8 +-> r4 == r0 at end of 3, jmp to 8 +-> r4 == r0 and r3 < 256 at end of 3 +-> r3 < 256 and r0 == (((r4 + (r3 & 255)) & 16777215) * 65899) & 16777215 at start of 3 +-> r3 < 256 and r0 == (r4 + r3) * 65899 (mod 2^24) at start of 3 -- cgit v1.2.3-70-g09d2