From a72831d5c322078260314c305ddd940e4967947d Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Wed, 11 Nov 2026 14:17:51 -0300 Subject: design: rings; nothing from after the moment shown From the user. A loop is a ring its blocks sit on, upright, an inner loop a smaller ring touching its parent, a way out leaving along the tangent; layers stay for functions that are trees of branches; the track is withdrawn. A graph shows only what the run has done by the moment shown: counts so far, a block or edge not reached yet drawn quiet, a fold of what is not reached yet that opens when the run arrives (reach, unfold); the rule stands in Forbidden for every block. A pane unrolls from its strip into its whole column and rolls back, so the whole function or the whole stack can be shown for a beat and a far jump is travelled. Co-Authored-By: Claude Fable 5.2 Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa --- design/mock/22-graph-sort.png | Bin 241323 -> 327316 bytes design/mock/22-graph-sort.svg | 1099 +++++++++++++++------------ design/mock/23-graph-open.png | Bin 152825 -> 0 bytes design/mock/23-graph-open.svg | 229 ------ design/mock/24-graph-strip.png | Bin 64854 -> 76321 bytes design/mock/24-graph-strip.svg | 222 +++--- design/mock/25-blocks-lens-480.png | Bin 36257 -> 40418 bytes design/mock/25-blocks-lens.png | Bin 216534 -> 240101 bytes design/mock/25-blocks-lens.svg | 1469 +++++++++++++++++++----------------- design/mock/42-frame-layouts.png | Bin 360073 -> 362630 bytes design/mock/43-graph-forms.png | Bin 220933 -> 202259 bytes design/mock/43-graph-forms.svg | 467 +++++------- design/mock/frame.py | 60 +- design/mock/graph.py | 1043 ++++++++++--------------- 14 files changed, 2141 insertions(+), 2448 deletions(-) delete mode 100644 design/mock/23-graph-open.png delete mode 100644 design/mock/23-graph-open.svg (limited to 'design/mock') diff --git a/design/mock/22-graph-sort.png b/design/mock/22-graph-sort.png index d536ca4..30ba6e0 100644 Binary files a/design/mock/22-graph-sort.png and b/design/mock/22-graph-sort.png differ diff --git a/design/mock/22-graph-sort.svg b/design/mock/22-graph-sort.svg index b30ffe4..0c2d5e4 100644 --- a/design/mock/22-graph-sort.svg +++ b/design/mock/22-graph-sort.svg @@ -1,486 +1,621 @@ - + - + +the map: sort's rings over the source, the disassembly linear beside them, at the 11th compare - - -sort.c -lines 1 to 22 of 22 -1 -int -a -[ -8 -] -= -{ -4 -, -9 -, -17 -, -31 -, -12 -, -26 -, -5 -, -20 -} -; -2 -3 -void -swap -( -int -* -x -, -int -* -y -) -{ -4 -int -t -= -* -x -; -5 -* -x -= -* -y -; -6 -* -y -= -t -; -7 -} -8 -9 -void -sort -( -int -n -) -{ -10 -for -( -int -i -= -1 -; -i -< -n -; -i -+ -+ -) -{ -11 -int -j -= -i -; - - -12 -while -( -j -> -0 -& -& -a -[ -j -- -1 -] -> -a -[ -j -] -) -{ - -13 -swap -( -& -a -[ -j -- -1 -] -, -& -a -[ -j -] -) -; - -14 -j -- -- -; -15 -} -16 -} -17 -} -18 -19 -int -main -( -void -) -{ -20 -sort -( -8 -) -; -21 -return -0 -; -22 -} -the map: sort's disassembly as its track, in the second column (1024 to 1904), at the 11th compare + + +the blocks of sort +its blocks · the visits so far · the path · the loops' turns + + + + + + + + + + + + + + + + + + + + + + + + + + +5 + turns +5 + turns + ++12 +×6 + ++1e +×6 + ++24 +×11 + ++5d +×5 + ++97 +×5 + ++99 +×5 + ++2f +×11 + ++56 +×11 + ++5f +swap +×5 + ++0 +×1 + ++a7 + + + +sort.c +lines 1 to 22 of 22 +1 +int +a +[ +8 +] += +{ +4 +, +9 +, +17 +, +31 +, +12 +, +26 +, +5 +, +20 +} +; +2 +3 +void +swap +( +int +* +x +, +int +* +y +) +{ +4 +int +t += +* +x +; +5 +* +x += +* +y +; +6 +* +y += +t +; +7 +} +8 +9 +void +sort +( +int +n +) +{ +10 +for +( +int +i += +1 +; +i +< +n +; +i ++ ++ +) +{ +11 +int +j += +i +; + + +12 +while +( +j +> +0 +& +& +a +[ +j +- +1 +] +> +a +[ +j +] +) +{ + +13 +swap +( +& +a +[ +j +- +1 +] +, +& +a +[ +j +] +) +; + +14 +j +- +- +; +15 +} +16 +} +17 +} +18 +19 +int +main +( +void +) +{ +20 +sort +( +8 +) +; +21 +return +0 +; +22 +} - - -disassembly · sort -its blocks · visits · the edges taken · the loops' turns - - - - - - - - - - - - - - - - - - - - - - - - - - -×5 -×5 - - - -401150 -lines 9 to 10 -×1 -+0 -9 -push -rbp -+1 -mov -rbp, rsp -+4 -sub -rsp, 0x10 -+8 -mov -[rbp - 4], edi -+b -10 -mov -[rbp - 8] - - - - -, 1 - - - -401162 -line 10 -×6 -+12 -10 -mov -eax, [rbp - 8] -+15 -cmp -eax, [rbp - 4] -+18 -jge -4011f7 -taken 0 · not 6 - - - -40116e -line 11 -×6 -+1e -11 -mov -eax, [rbp - 8] -+21 -mov -[rbp - 0xc], eax - - - -401174 -line 12 -×11 -+24 -12 -xor -eax, eax -+26 -cmp -[rbp - 0xc] - - - - -, 0 -+2a -mov -[rbp - 0xd], al -+2d -jle -4011a6 -taken 0 · not 11 - - - -40117f -line 12 -×11 -+2f -12 -mov -eax, [rbp - 0xc] -+32 -sub -eax, 1 -+35 -movsxd -rcx, eax -+38 -lea -rax, [rip + 0x2e81] -+3f -mov -eax, [rax + rcx*4] -+42 -movsxd -rdx, [rbp - 0xc] - - - - - -+46 -lea -rcx, [rip + 0x2e73] -+4d -cmp -eax, [rcx + rdx*4] -+50 -setg -al -+53 -mov -[rbp - 0xd], al - - - -4011a6 -line 12 -×11 - -+56 -12 -mov -al, [rbp - 0xd] -7fffffffecd3 -◂ -1 - -+59 -test -al, 1 -1 - : -1 - -zf - - - -+5b -jne -4011af -taken - · reads zf - - - -4011af -lines 12 to 14 -×5 -+5f -13 -mov -eax, [rbp - 0xc] -+62 -sub -eax, 1 -+65 -cdqe - -+67 -lea -rdi, [rip + 0x2e52] -+6e -shl -rax, 2 -+72 -add -rdi, rax -+75 -movsxd -rax, [rbp - 0xc] - - - - - -+79 -lea -rsi, [rip + 0x2e40] -+80 -shl -rax, 2 -+84 -add -rsi, rax -+87 -call -401120 - - -swap -+8c -14 -mov -eax, [rbp - 0xc] -+8f -add -eax, 0xffffffff -+92 -mov -[rbp - 0xc], eax -+95 -12 -jmp -401174 - - - -4011ad -line 12 -×5 -+5d -12 -jmp -4011e7 - - - -4011e7 -line 16 -×5 -+97 -16 -jmp -4011e9 - - - -4011e9 -line 10 -×5 -+99 -10 -mov -eax, [rbp - 8] -+9c -add -eax, 1 -+9f -mov -[rbp - 8], eax -+a2 -jmp -401162 - - - -4011f7 -line 17 -+a7 -17 -add -rsp, 0x10 -+ab -pop -rbp -+ac -ret - - - - -the map's stage ends at 1784 + + +disassembly +sort + +401 +13b +mov +rax, [rbp - 8] +swap +401 +13f +mov +[rax], ecx +401 +141 +mov +ecx, [rbp - 0x14] +401 +144 +mov +rax, [rbp - 0x10] +401 +148 +mov +[rax], ecx +401 +14a +pop +rbp +401 +14b +ret + +401 +14c +nop +[rax] +401 +150 +9 +push +rbp +401 +151 +mov +rbp, rsp +401 +154 +sub +rsp, 0x10 +401 +158 +mov +[rbp - 4], edi +401 +15b +10 +mov +[rbp - 8] + + + + +, 1 +401 +162 +mov +eax, [rbp - 8] +401 +165 +cmp +eax, [rbp - 4] +401 +168 +jge +4011f7 +401 +16e +11 +mov +eax, [rbp - 8] +401 +171 +mov +[rbp - 0xc], eax +401 +174 +12 +xor +eax, eax +401 +176 +cmp +[rbp - 0xc] + + + + +, 0 +401 +17a +mov +[rbp - 0xd], al +401 +17d +jle +4011a6 +401 +17f +mov +eax, [rbp - 0xc] +401 +182 +sub +eax, 1 +401 +185 +movsxd +rcx, eax +401 +188 +lea +rax, [rip + 0x2e81] +401 +18f +mov +eax, [rax + rcx*4] +401 +192 +movsxd +rdx, [rbp - 0xc] + + + + + +401 +196 +lea +rcx, [rip + 0x2e73] +401 +19d +cmp +eax, [rcx + rdx*4] +401 +1a0 +setg +al + +401 +1a3 +mov +[rbp - 0xd], al +7fffffffecd3 +◂ +1 + +401 +1a6 +mov +al, [rbp - 0xd] +7fffffffecd3 +◂ +1 + +401 +1a9 +test +al, 1 +1 + : +1 + +zf + + + +401 +1ab +jne +4011af +taken + · reads zf +401 +1ad +jmp +4011e7 +401 +1af +13 +mov +eax, [rbp - 0xc] +401 +1b2 +sub +eax, 1 +401 +1b5 +cdqe + +401 +1b7 +lea +rdi, [rip + 0x2e52] +401 +1be +shl +rax, 2 +401 +1c2 +add +rdi, rax +401 +1c5 +movsxd +rax, [rbp - 0xc] + + + + + +401 +1c9 +lea +rsi, [rip + 0x2e40] +401 +1d0 +shl +rax, 2 +401 +1d4 +add +rsi, rax +401 +1d7 +call +401120 +swap +401 +1dc +14 +mov +eax, [rbp - 0xc] +401 +1df +add +eax, 0xffffffff +401 +1e2 +mov +[rbp - 0xc], eax +401 +1e5 +12 +jmp +401174 +401 +1e7 +16 +jmp +4011e9 +401 +1e9 +10 +mov +eax, [rbp - 8] +401 +1ec +add +eax, 1 +401 +1ef +mov +[rbp - 8], eax +401 +1f2 +jmp +401162 +401 +1f7 +17 +add +rsp, 0x10 +401 +1fb +pop +rbp +401 +1fc +ret + +401 +1fd +nop +[rax] + +401 +200 +push +rbp +main +401 +201 +mov +rbp, rsp +401 +204 +sub +rsp, 0x10 +401 +208 +mov +[rbp - 4] + + + + +, 0 +401 +20f +mov +edi, 8 +401 +214 +call +401150 +sort +401 +219 +xor +eax, eax +401 +21b +add +rsp, 0x10 +401 +21f +pop +rbp + +×1 + +×6 + +×6 + +×11 + +×11 + +×11 + +×5 + +×5 + +×5 + +×5 + + + + + + + + + + + + + + +the map's stage ends at 1784; the other columns (memory, the registers whole, the stack) as in 19 diff --git a/design/mock/23-graph-open.png b/design/mock/23-graph-open.png deleted file mode 100644 index 1c3e8df..0000000 Binary files a/design/mock/23-graph-open.png and /dev/null differ diff --git a/design/mock/23-graph-open.svg b/design/mock/23-graph-open.svg deleted file mode 100644 index 0d7e9aa..0000000 --- a/design/mock/23-graph-open.svg +++ /dev/null @@ -1,229 +0,0 @@ - - - -the map: libc's open as its track · 19 blocks, the run reached 8; the 11 never reached folded - - - -disassembly · open · libc.so.6 -no source · 19 blocks · folded: 11 never reached - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -7ffff7d10ec0 -×1 -+0 -endbr64 - -+4 -push -rbp -+5 -mov -rbp, rsp -+8 -sub -rsp, 0x70 -+c -mov -[rbp - 0x30], rdx -+10 -mov -rax, fs:0x28 -+19 -mov -[rbp - 0x48], rax -+1d -xor -eax, eax -+1f -test -sil, 0x40 -+23 -jne -7ffff7d10f90 -taken 0 · not 1 - - - -7ffff7d10ee9 -×1 -+29 -mov -eax, esi -+2b -xor -r10d, r10d -+2e -not -eax -+30 -test -eax, 0x410000 -+35 -je -7ffff7d10f90 -taken 0 · not 1 - - -+d0 to +eb -never reached -the O_CREAT path: the mode from the varargs - - - -7ffff7d10efb -×1 -+3b -mov -r11, fs:0x10 -+44 -movsxd -rdx, esi -+47 -mov -eax, [r11 + 0x308] -+4e -cmp -[rip + 0x11018b] - -, 0 -+55 -jne -7ffff7d10fb0 -taken 1 · not 0 - - -+5b to +b3 -4 blocks never reached -multi-threaded: a cancellable call - - - -7ffff7d10fb0 -×1 -+f0 -mov -rsi, rdi -+f3 -xor -r9d, r9d - -+f6 -xor -r8d, r8d - -+f9 -mov -rdi, 0xffffffffffffff9c - -+100 -mov -eax, 0x101 - - - -+105 -syscall - -openat - nr 257 -+107 -mov -rdx, rax - - -+136 to +149 -2 blocks never reached -cancelled - - - -7ffff7d10fca -+10a -cmp -rax, 0xfffffffffffff000 -+110 -ja -7ffff7d10fe8 - - - -7ffff7d10fd2 -+112 -mov -eax, edx - - -+128 to +cd -3 blocks never reached -an error: errno set, -1 returned - - - -7ffff7d10fd4 -+114 -mov -rdx, [rbp - 0x48] -+118 -sub -rdx, fs:0x28 -+121 -jne -7ffff7d10fec - - -+12c to +130 -2 blocks never reached -the canary broken - - - -7ffff7d10fe3 -+123 -leave - -+124 -ret - - - - diff --git a/design/mock/24-graph-strip.png b/design/mock/24-graph-strip.png index 2c1bf80..ab615cd 100644 Binary files a/design/mock/24-graph-strip.png and b/design/mock/24-graph-strip.png differ diff --git a/design/mock/24-graph-strip.svg b/design/mock/24-graph-strip.svg index fda1525..4e9da35 100644 --- a/design/mock/24-graph-strip.svg +++ b/design/mock/24-graph-strip.svg @@ -1,122 +1,126 @@ - + - + 1 the condition the pc on jne in the test's block, the second time; its two ways out - + the blocks of reverse -its blocks · the visits · the path · the loops' turns - - - - - - - - -×1 - -+0 -×1 - -+41 -×2 - -+19 -×1 - -+48 +its blocks · the visits so far · the path · the loops' turns + + + + + + + + +1 + turn + ++41 +×2 + ++19 +×1 + ++0 +×1 + ++48 2 the edge taken -taken: along the line to the body, the mark on the edge, landing +taken: round the top of the ring to the body, the mark on it - + the blocks of reverse -its blocks · the visits · the path · the loops' turns - - - - - - - - -×1 - -+0 -×1 - -+41 -×2 - -+19 -×1 - -+48 - - -3 -the loop's turn -back over the arch to the test, the mark coming round; the count struck as it lands - - - -the blocks of reverse -its blocks · the visits · the path · the loops' turns - - - - - - - - - -×2 - -+0 -×1 - -+41 -×2 - -+19 -×2 - -+48 - - -4 -the way out -not taken, the fourth time: under the body to the exit, landed - - - -the blocks of reverse -its blocks · the visits · the path · the loops' turns - - - - - - - - -×3 - -+0 -×1 - -+41 -×4 - -+19 -×3 - -+48 -×1 +its blocks · the visits so far · the path · the loops' turns + + + + + + + + +1 + turn + ++41 +×2 + ++19 +×1 + ++0 +×1 + ++48 + + +3 +the loop's turn +back round the foot of the ring to the test; the count at its centre struck as it lands + + + +the blocks of reverse +its blocks · the visits so far · the path · the loops' turns + + + + + + + + + +2 + turns + ++41 +×2 + ++19 +×2 + ++0 +×1 + ++48 + + +4 +the way out +not taken, the fourth time: down the tangent, out of the ring, landed + + + +the blocks of reverse +its blocks · the visits so far · the path · the loops' turns + + + + + + + + +3 + turns + ++41 +×4 + ++19 +×3 + ++0 +×1 + ++48 +×1 diff --git a/design/mock/25-blocks-lens-480.png b/design/mock/25-blocks-lens-480.png index af3d2b6..afb981d 100644 Binary files a/design/mock/25-blocks-lens-480.png and b/design/mock/25-blocks-lens-480.png differ diff --git a/design/mock/25-blocks-lens.png b/design/mock/25-blocks-lens.png index 468aee9..c7bea19 100644 Binary files a/design/mock/25-blocks-lens.png and b/design/mock/25-blocks-lens.png differ diff --git a/design/mock/25-blocks-lens.svg b/design/mock/25-blocks-lens.svg index 5041b62..b1f7031 100644 --- a/design/mock/25-blocks-lens.svg +++ b/design/mock/25-blocks-lens.svg @@ -1,744 +1,874 @@ - - + + the blocks of sort -its blocks · the visits · the path · the loops' turns - - - - - - - - - - - - - - - - - - - - - - - - - - -×5 -×5 - -+0 -×1 - -+12 -×6 - -+1e -×6 - -+24 -×11 - -+2f -×11 - -+56 -×11 - -+5f -×5 - -swap - -+5d -×5 - -+97 -×5 - -+99 -×5 - -+a7 - - - -sort.c -lines 8 to 15 of 22 -8 -9 -void -sort -( -int -n -) -{ -10 -for -( -int -i -= -1 -; -i -< -n -; -i -+ -+ -) -{ -11 -int -j -= -i -; - - -12 -while -( -j -> -0 -& -& -a -[ -j -- -1 -] -> -a -[ -j -] -) -{ - -13 -swap -( -& -a -[ -j -- -1 -] -, -& -a -[ -j -] -) -; - -14 -j -- -- -; -15 -} - - - -disassembly -sort -4011 -92 -12 -movsxd -rdx, [rbp - 0xc] - - - - - -4011 -96 -lea -rcx, [rip + 0x2e73] -4011 -9d -cmp -eax, [rcx + rdx*4] -4011 -a0 -setg -al - +its blocks · the visits so far · the path · the loops' turns + + + + + + + + + + + + + + + + + + + + + + + + + + +5 + turns +5 + turns + ++12 +×6 + ++1e +×6 + ++24 +×11 + ++5d +×5 + ++97 +×5 + ++99 +×5 + ++2f +×11 + ++56 +×11 + ++5f +swap +×5 + ++0 +×1 + ++a7 + + + +sort.c +lines 9 to 14 of 22 +9 +void +sort +( +int +n +) +{ +10 +for +( +int +i += +1 +; +i +< +n +; +i ++ ++ +) +{ +11 +int +j += +i +; + + +12 +while +( +j +> +0 +& +& +a +[ +j +- +1 +] +> +a +[ +j +] +) +{ + +13 +swap +( +& +a +[ +j +- +1 +] +, +& +a +[ +j +] +) +; + +14 +j +- +- +; + + + +disassembly +sort 4011 -a3 -mov -[rbp - 0xd], al -7fffffffecd3 -◂ -1 - +9d +12 +cmp +eax, [rcx + rdx*4] 4011 -a6 -mov -al, [rbp - 0xd] -7fffffffecd3 -◂ -1 - +a0 +setg +al + 4011 -a9 -test -al, 1 -1 - : -1 - -zf - - - +a3 +mov +[rbp - 0xd], al +7fffffffecd3 +◂ +1 + 4011 -ab -jne -4011af -taken - · reads zf +a6 +mov +al, [rbp - 0xd] +7fffffffecd3 +◂ +1 + 4011 -ad -jmp -4011e7 +a9 +test +al, 1 +1 + : +1 + +zf + + + 4011 -af -13 -mov -eax, [rbp - 0xc] +ab +jne +4011af +taken + · reads zf 4011 -b2 -sub -eax, 1 +ad +jmp +4011e7 4011 -b5 -cdqe - +af +13 +mov +eax, [rbp - 0xc] 4011 -b7 -lea -rdi, [rip + 0x2e52] +b2 +sub +eax, 1 4011 -be -shl -rax, 2 +b5 +cdqe + 4011 -c2 -add -rdi, rax - -×11 - -×5 - -×5 - - - -registers -stack -heap -code -data -rwx - -read-only - -rbx -0 -r8 -7ffff7e19680 -r9 -7ffff7e1afa0 -r10 -7fffffffea60 - - - - - -r11 -7ffff7ffca90 - - - - - -r12 -7fffffffee38 - - - - - -r13 -1 -r14 -7ffff7ffd000 - - - - - -r15 -403e10 - - - - - -rax -1 -rcx -404010 - - -0x900000004 -rdx -4 -rsi -404024 - - -0x1f0000001a -rdi -404020 - - -0x1a00000005 -rbp -7fffffffece0 - - -7fffffffed00 - - -7fffffffedb0 - - -7fffffffee10 - - -0 -rsp -7fffffffecd0 - - -0x401000000 - - -rip -4011ab -sort+91 -cf - -pf - -af -zf -sf - -IF -df -of - - - -stack -twelve words from rsp · the frames they belong to -rsp - -+0 -j, high half +b7 +lea +rdi, [rip + 0x2e52] + +×11 + +×5 + +×5 + + + +registers +stack +heap +code +data +rwx + +read-only + +rbx +0 +r8 +7ffff7e19680 +r9 +7ffff7e1afa0 +r10 +7fffffffea60 + + + + + +r11 +7ffff7ffca90 + + + + + +r12 +7fffffffee38 + + + + + +r13 +1 +r14 +7ffff7ffd000 + + + + + +r15 +403e10 + + + + + +rax +1 +rcx +404010 + + +0x900000004 +rdx +4 +rsi +404024 + + +0x1f0000001a +rdi +404020 + + +0x1a00000005 +rbp +7fffffffece0 + + +7fffffffed00 + + +7fffffffedb0 + + +7fffffffee10 + + +0 +rsp +7fffffffecd0 + + +0x401000000 + + +rip +4011ab +sort+91 +cf + +pf + +af +zf +sf + +IF +df +of + + + +stack +twenty words from rsp · the frames they belong to +rsp + ++0 +j, high half +7fffffffe +cd0 + + +0x401000000 ++8 +i, n +7fffffffe +cd8 + + +0x800000006 +rbp + ++10 +saved rbp +7fffffffe +ce0 + + +7fffffffed00 + + + + + ++18 +7fffffffe +ce8 + + +401219 +main+25 ++20 +7fffffffe +cf0 + + +0 ++28 +7fffffffe +cf8 + + +0 ++30 +saved rbp +7fffffffe +d00 + + +7fffffffedb0 + + + + + ++38 +7fffffffe +d08 + + +7ffff7c27781 +libc+27781 ++40 7fffffffe -cd0 - - -0x401000000 -+8 -i, n +d10 + + +7ffff7fe0c60 +ld.so+22c60 ++48 7fffffffe -cd8 - - -0x800000006 -rbp - -+10 -saved rbp +d18 + + +7fffffffee38 + + + + + ++50 7fffffffe -ce0 - - -7fffffffed00 - - - - - -+18 +d20 + + +0x1f7fbe000 ++58 7fffffffe -ce8 +d28 -401219 -main+25 -+20 +401200 +main+0 ++60 7fffffffe -cf0 - - -0 -+28 +d30 + + +7fffffffed70 + + + + + ++68 7fffffffe -cf8 - - -0 -+30 -saved rbp +d38 + + + + + ++70 7fffffffe -d00 - - -7fffffffedb0 - - - - - -+38 +d40 + + +0 ++78 7fffffffe -d08 - - -7ffff7c27781 -libc+27781 -+40 +d48 + + +0x455b402647827406 ++80 7fffffffe -d10 +d50 -7ffff7fe0c60 -ld.so+22c60 -+48 +7fffffffee38 + + + + + ++88 7fffffffe -d18 - - -7fffffffee38 - - - - - -+50 +d58 + + +1 ++90 7fffffffe -d20 - - -0x1f7fbe000 -+58 +d60 + + +7ffff7ffd000 ++98 7fffffffe -d28 +d68 -401200 -main+0 - - - -sort - - - -main - - -libc.so.6+27781 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +403e10 + + + +sort + + + +main + + +libc.so.6+27781 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - + + - + - + - - + + - + - + - - + + - - + + + - - + - - + + - - + - - + - + - + - - + + - + + - + + - - + + - + - + + - + - - + + - + - + - - + + - - + - - + - - + + - + + - - - + + - + + - + + - + + - - + + - - + + - + - + - + - - + + - + - + - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - + - + - + - + @@ -746,135 +876,128 @@ - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - - - - - - - - - + + moment 434 of 1905 diff --git a/design/mock/42-frame-layouts.png b/design/mock/42-frame-layouts.png index ab9cece..56ba531 100644 Binary files a/design/mock/42-frame-layouts.png and b/design/mock/42-frame-layouts.png differ diff --git a/design/mock/43-graph-forms.png b/design/mock/43-graph-forms.png index 1775fd6..e5ff83c 100644 Binary files a/design/mock/43-graph-forms.png and b/design/mock/43-graph-forms.png differ diff --git a/design/mock/43-graph-forms.svg b/design/mock/43-graph-forms.svg index 6ec334b..0b857bc 100644 --- a/design/mock/43-graph-forms.svg +++ b/design/mock/43-graph-forms.svg @@ -1,311 +1,210 @@ - + - -sort's graph, four ways -The same moment in each (the 11th compare: 17 > 5, jne about to take the swap); the lens's scale, mono 20. Veiled: what falls outside the box the frame gives the lens. -1 -present: layers, boxes, square lanes -ten layers, 400 high: past the lens's 296 (veiled), so it pans; a third of its width + +the graph's two forms +At the lens's scale, mono 20; each in the pane the `blocks` split gives it, 880 by 344. Every number is the run's by the moment shown; veiled: what a pane must pan to. +1 +rings: sort at the 11th compare +each loop a ring, the inner touching the outer at its header; ways out down the tangent; whole in 880 by 344 - + the blocks of sort -its blocks · the visits · the path - - - - - - - - - - - - - - - - - - - - - - -×5 - - - - -×5 - - -+0 -×1 - - -+12 -×6 - - -+1e -×6 - - -+24 -×11 - - -+2f -×11 - - -+56 -×11 - - -+5d -×5 - - -+5f -×5 - - -+97 -×5 - - -+99 -×5 - - -+a7 - +its blocks · the visits so far · the path · the loops' turns + + + + + + + + + + + + + + + + + + + + + + + + + + +5 + turns +5 + turns + ++12 +×6 + ++1e +×6 + ++24 +×11 + ++5d +×5 + ++97 +×5 + ++99 +×5 + ++2f +×11 + ++56 +×11 + ++5f +swap +×5 + ++0 +×1 + ++a7 2 -the same layers, rounded -pills and round corners: smoother, and just as tall +layers: the same moment +the loops as lanes; 400 high, so it pans in 344 (veiled): for loops, rings the blocks of sort -its blocks · the visits · the path - - - - - - - - - - - - - - - - - - - - +its blocks · the visits so far · the path + + + + + + + + + + + + + + + + + + + + ×5 - - + + ×5 - + +0 -×1 - +×1 + +12 -×6 - +×6 + +1e -×6 - +×6 + +24 -×11 - +×11 + +2f -×11 - +×11 + +56 -×11 - +×11 + +5d -×5 - +×5 + +5f -×5 - +swap +×5 + +97 -×5 - +×5 + +99 -×5 - +×5 + +a7 - -3 -rings -each loop a circle its blocks sit on, the inner inside the outer: 420 high, past the band's 200 (veiled) - - - -the blocks of sort -its blocks · the visits · the path · the loops' turns - - - - - - - - - - - - - - - - - - - - - - - - - - -×5 -×5 - -+0 -×1 - -+12 -×6 - -+1e -×6 - -+24 -×11 - -+2f -×11 - -+56 -×11 - -+5d -×5 - -+5f -×5 - -+97 -×5 - -+99 -×5 - -+a7 - -swap - -What each costs -1 The tools' picture. Tall by nature: a layer a block, - so it pans in a short pane, and leaves the width. -2 Rounding the corners does not change the shape. -3 The most circular, and a loop is a ring; but rings - want a square pane, a loop's way out is a chord - across them, and pills on its sides sit across it. -4 The track. A line of blocks as they run, each loop - an arch over its own blocks: a closed shape, its - turns at its centre; a jump past blocks a dip - under them. Wide and short: 11 blocks in 1622 - by 150, whole. Its order is the disassembly's, - which is under the source; run down, it is the - map's column with its rows. -4 -the track: recommended -the band across the frame, 1792 by 200: the whole graph, no pan - - - -the blocks of sort -its blocks · the visits · the path · the loops' turns - - - - - - - - - - - - - - - - - - - - - - - - - - -×5 -×5 - -+0 -×1 - -+12 -×6 - -+1e -×6 - -+24 -×11 - -+2f -×11 - -+56 -×11 - -+5f -×5 - -swap - -+5d -×5 - -+97 -×5 - -+99 -×5 - -+a7 -Ink in 3 and 4: never taken in the whole run, dashed rule (j > 0 failing); not yet, rule (the way out); taken, dim; the last three, the trail's golds. 1 and 2 keep the layers' ink: never taken, rule. + +2 +layers: libc's open at its syscall +a tree of branches and no loop (rings has none to draw, and is this); what is not reached yet folded, dashed + + + +the blocks of open · libc.so.6 +its blocks · the visits so far · the path + + + + + + + + + + + + + + + + + + + + + ++0 +×1 + ++29 +×1 + ++3b +×1 + ++d0 + ++f0 +×1 + ++5b … +· 7 + ++be … +· 8 +Which, and why +1 Rings, the first form. A loop is a ring and the mark going + round it is the picture of iteration; its turns at its + centre. Nested loops: rings touching at the header. +2 Layers, the second, for a function of branches: the path + reads down, and a fork is two columns. Rings with no + loop is this. For loops it is tall and pans. + The track is withdrawn: a ring says a loop, a layer a + branch; a line of blocks said neither, and its arches + were rings flattened to fit a band. +Nothing from after the moment: counts so far; an edge or +a block not reached yet is quiet (rule, page, no count); +open's folds are what it has not reached yet, and open +as the run gets there. +Ink: not reached so far, rule; taken so far, dim; the last three, the trail's golds, the newest 3. A fold, dashed. No count before a block's first visit. diff --git a/design/mock/frame.py b/design/mock/frame.py index 15b3933..209116f 100644 --- a/design/mock/frame.py +++ b/design/mock/frame.py @@ -1,11 +1,11 @@ #!/usr/bin/env python3 """The working frame reworked: the disassembly under the source in every split, the registers a scene does not -move folded three to a row, the stack given what that frees, and the `blocks` lens's drawing across the band. +move folded three to a row, the stack given what that frees, and the `blocks` lens's rings over the program column. python3 -B frame.py # 40-frame-beside, 41-frame-subject, 25-blocks-lens (.svg), 42-frame-layouts.png 40 and 41 are mocks 9 and 11 in the reworked frame (the same recording of targets/list, the same moments, each -pane's minimap from the map as map.py draws it); 25 is sort with the `blocks` lens (graph.py's track, the stop in +pane's minimap from the map as map.py draws it); 25 is sort with the `blocks` lens (graph.py's rings, the stop in sort-dbg.txt); 42 sets the three layouts weighed this round side by side, each as the list's `subject` and sort's `blocks`, at a third of their size: A (recommended) folds the quiet registers, B keeps all seventeen and gives the source's rows to the disassembly, C sets the registers in two columns. @@ -26,15 +26,17 @@ from context import (PAGE, RAISED, RULE, VELLUM, BRIGHT, DIM, FAINT, GOLD, HEAP, HERE = G.HERE TOP, FOOT = 48, 888 -WORDS = {6: "six", 8: "eight", 10: "ten", 11: "eleven", 12: "twelve", 13: "thirteen", 14: "fourteen", 15: "fifteen"} +WORDS = {6: "six", 8: "eight", 10: "ten", 11: "eleven", 12: "twelve", 13: "thirteen", 14: "fourteen", 15: "fifteen", + 20: "twenty", 22: "twenty-two"} # ---- the splits ------------------------------------------------------------------------------------------------- # What a scene gives its lens, and the program column's rows under it: (drawing, view, source, disassembly). The -# `blocks` lens has no view: its drawing is the band across both columns. -SPLITS = {"none": (0, 0, 14, 17), "beside": (152, 152, 8, 17), "subject": (296, 200, 8, 11), "blocks": (200, 0, 8, 15)} +# `blocks` lens has no view: its drawing (rings, 880 by 344) is over the program column, and the state column is +# the registers' and the stack's from the top. +SPLITS = {"none": (0, 0, 14, 17), "beside": (152, 152, 8, 17), "subject": (296, 200, 8, 11), "blocks": (344, 0, 6, 11)} LAYOUTS = { "A": dict(regs="fold", src=None, dis=None), # the splits above - "B": dict(regs="all", src=6, dis=lambda d: d + 2), # all seventeen rows; the source gives two rows + "B": dict(regs="all", src=6, dis=lambda d, s: d + s - 6), # all seventeen rows; the source gives to six "C": dict(regs="two", src=None, dis=None), # the registers in two columns of eight, rip across } @@ -44,22 +46,23 @@ def boxes(split, layout, quiet): band, view, src, dis = SPLITS[split] L = LAYOUTS[layout] if L["src"] is not None and split != "none": - src, dis = L["src"], L["dis"](dis) + src, dis = L["src"], L["dis"](dis, src) regs = {"fold": C.reg_rows(quiet), "all": 17, "two": 9}[L["regs"]] out = {} y = TOP + (band + 12 if band else 0) out["source"] = (64, y, ph(src)) out["disasm"] = (64, y + ph(src) + 12, ph(dis)) assert out["disasm"][1] + out["disasm"][2] == FOOT or split == "none", (split, layout, out) - ys = TOP + (view + 12 if view else band + 12 if split == "blocks" else 0) + ys = TOP + (view + 12 if view else 0) out["registers"] = (976, ys, ph(regs)) yk = ys + ph(regs) + 12 - out["stack"] = (976, yk, FOOT - yk) + words = (FOOT - yk - TAG - 8) // ROW + out["stack"] = (976, FOOT - ph(words), ph(words)) # a panel is 32 + 24n: what is left over is above it if band: out["drawing"] = (64, TOP, band) if view: out["view"] = (976, TOP, view) - return out, regs, (FOOT - yk - TAG - 8) // ROW + return out, regs, words # ---- the registers in two columns (layout C) ------------------------------------------------------------------ @@ -256,33 +259,7 @@ SORT_REGS = [("rax", [], ("int", 1)), ("rbx", [], ("int", 0)), ("rcx", [(0x40401 SORT_FLAGS = [("CF", 0, 0), ("PF", 0, 1), ("AF", 0, 1), ("ZF", 0, 0), ("SF", 0, 0), ("IF", 1, 0), ("DF", 0, 0), ("OF", 0, 0)] SORT_QUIET = ("rbx", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15") # sort moves the other eight SORT_SRC = open(HERE + "/../../anim/tools/sort.c").read().split("\n") -TEXT = G.read_dis("sort-clang.dis") # the program's text: swap, sort, main -FUNC = lambda a: "swap" if a < 0x401150 else "sort" if a < 0x401200 else "main" - - -def sort_disasm(g, y, n): - """n rows round the pc; each block's first row under a rule, its visits ranged right in the annotation's room - (the pill's count, in its digits); the trail's three rows and the pc's with what they did.""" - i = [r[0] for r in TEXT].index(G.PC) - lo = max(0, min(i - n // 2, len(TEXT) - n)) - st = G.sort_state(G.UPTO, G.PC, G.TRAIL_ROWS) - notes = dict(G.NOTES) - notes[0x4011a3] = [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)] - rows = [] - for a, ln, mn, ops, t, callee in TEXT[lo:lo + n]: - state = "cur" if a == G.PC else {0x4011a9: "trail0", 0x4011a6: "trail1", 0x4011a3: "trail2"}.get(a) - note = ("runs", notes[a]) if a in notes else ("text", callee, VELLUM) if mn == "call" else None - rows.append((a, ln, mn, [(t, CODE)] if t and (mn.startswith("j") or mn == "call") else [(ops, VELLUM)], - state, note)) - at = C.disasm(g, y, rows, "sort", 12) - for a in at: - if a in G.SORT_BL and a != "note": # a block's first row: the rule over it, its pill's digits - yy = at[a] - g.rect(C.LX + 2, yy, C.CW - 4, 2, RULE) - n_ = st["blocks"][a]["count"] - g.t(C.LX + C.CW - 12, b(yy), "×%d" % n_, S, FAINT, MONO, "end") - line12 = [at[r[0]] for r in rows if r[1] == 12 and r[0] < 0x4011af] - return at, (min(line12), max(line12) + ROW), lo +TEXT, FUNC = G.TEXT, G.FUNC def sort_strips(g, bx, lo, n, words): @@ -313,19 +290,20 @@ def sort_frame(g, layout="A", strips=True): """Mock 25 in a layout: the `blocks` lens across the band, the source and the disassembly under it.""" bx, nregs, words = boxes("blocks", layout, SORT_QUIET) st = G.sort_state(G.UPTO, G.PC, G.TRAIL_ROWS, G.NOTES) - G.track_lens(g, 64, TOP, 1792, 200, G.SORT_BL, G.SB[0], G.SORT_BASE, st, "the blocks of sort") + G.rings(g, 64, TOP, 880, 344, G.SORT_BL, G.SORT_BASE, st, G.SORT_RINGS, "the blocks of sort") src, dis = (bx["source"][2] - 32) // ROW, (bx["disasm"][2] - 32) // ROW C.LX, C.RX = 64, 976 M.strip(strips) first = max(1, 12 - src // 2) ys = C.source(g, bx["source"][1], src, SORT_SRC, first, 12, [14, 13], "sort.c", 22) - at, run, lo = sort_disasm(g, bx["disasm"][1], dis) + at, run, lo = G.sort_disasm(g, bx["disasm"][1], dis) M.strip(False) draw_registers(g, layout, bx["registers"][1], SORT_REGS, SORT_FLAGS, {}, SORT_QUIET) M.strip(strips) C.RX = 976 roles = {0: ("j, high half", VELLUM), 1: ("i, n", VELLUM), 2: ("saved rbp", DIM), 6: ("saved rbp", DIM)} - C.stack(g, bx["stack"][1], sort_slots(words), [("sort", 0, 3), ("main", 4, 7), ("libc.so.6+27781", 8, 29)], + C.stack(g, bx["stack"][1], sort_slots(words), [("sort", 0, 3), ("main", 4, 7), ("libc.so.6+27781", 8, 29), + ("__libc_start_main+137", 30, 41)], rsp=RSP_S, roles={k: v for k, v in roles.items() if k < words}, note="%s words from rsp" % WORDS[words]) M.strip(False) C.thread(g, ys, [run]) @@ -392,7 +370,7 @@ def sheet(out): "list, subject" if kind == "subject" else "sort, blocks", src, dis, regs, words) d.text((x, y + 352), lab, font=body, fill="#eee6d2") if kind == "blocks": - d.text((x, y + 378), "the graph across the band: 1792 by 200, whole", font=body, fill="#9aa6d9") + d.text((x, y + 378), "rings over the program column, 880 by 344: whole", font=body, fill="#9aa6d9") else: d.text((x, y + 378), "the drawing 296 and its view of 7 over the state column", font=body, fill="#9aa6d9") s.save(HERE + "/" + out) diff --git a/design/mock/graph.py b/design/mock/graph.py index 6062fa9..083842e 100644 --- a/design/mock/graph.py +++ b/design/mock/graph.py @@ -1,19 +1,20 @@ #!/usr/bin/env python3 -"""The disassembly's other form: a function as a graph of its basic blocks, with what the run did on it. +"""The disassembly's other form: a function as a graph of its basic blocks, with what the run has done on it by +the moment shown, and nothing after. - python3 -B graph.py # 22-graph-sort, 23-graph-open, 24-graph-strip, 43-graph-forms (.svg) + python3 -B graph.py # 22-graph-sort, 24-graph-strip, 43-graph-forms (.svg) # (25, the `blocks` lens in the working frame, is frame.py's) -The form is the track: the blocks in a line in the order they run, each loop closing over the line as an arch -whose blocks sit on its floor, a forward jump that skips blocks dipping under them. Across in the lens's band, -down on the map, where the blocks are cards that carry their rows. The layered form it replaced (`silhouette`, -with `place` and `edges`) is kept for the comparison sheet, 43. +Two forms. `rings`, the first: each loop a ring its blocks sit on, clockwise from its header at the ring's left, +an inner loop a smaller ring touching its parent at its header, a loop's way out leaving along the ring's tangent; +what is outside every loop laid in layers. `layers`, the second, for a function that is a tree of branches: the +blocks in layers, pills and round corners. A block a pill either way (its offset, its visits so far). Data: sort as the scene builds it (clang -O0, anim/build.zig, less the instrumentation's calls): sort-clang.dis (objdump -dl), its path from `ztrace record --by insn --from sort` (the block leaders it hit), its stop in sort-dbg.txt. reverse from anim/tools/list.c (cc -O0), reverse-O0.dis, its path from `ztrace dbg` stepped by -instruction. libc's `open` from objdump of -/usr/lib/libc.so.6 (libc-open.dis), its path the one mock 16's run took. +instruction. libc's `open` from objdump of /usr/lib/libc.so.6 (libc-open.dis), its path the one mock 16's run +took. Every count is the path's up to the moment shown. """ import math import re @@ -129,102 +130,6 @@ def layers(bl, entry): return lay, back -# ---- a block, at the map's size: a head and insn rows -------------------------------------------------------- -X_OFF, X_LINE, X_MN, X_OPS = 72, 116, 128, 212 - - -def block_w(blk, base, note_w=0): - """As wide as its widest row as drawn (the size words gone, a width's cells in their place), 300 at least.""" - ops = [len(re.sub(r"\b\w+ ptr ", "", r[3])) + (3 if " ptr " in r[3] else 0) for r in blk.rows] - return max(300, X_OPS + max(ops) * A + 24 + note_w) - - -def fold_rows(rows, keep): - """A block longer than 16 rows: its first four and last four, the middle one `more` row.""" - if len(rows) <= 16 or keep: - return rows - return rows[:4] + [None] + rows[-4:] - - -def draw_block(g, x, y, w, blk, base, st): - """st: count (visits), cur (the pc's address in it), trail (ran rows), notes {address: note}, cur_line.""" - if hasattr(blk, "folded"): # blocks the whole recording never reached: one dashed box, no rows - h = TAG + ROW + PAD - g.rect(x, y, w, h, PAGE) - g.frame(x, y, w, h, RULE, 2, "12 8") - g.t(x + 12, b(y), "+%x to +%x" % (blk.rows[0][0] - base, blk.rows[-1][0] - base), S, FAINT, MONO) - g.t(x + w - 12, b(y), "%d blocks never reached" % len(blk.folded) if len(blk.folded) > 1 else "never reached", - 18, FAINT, "sans", "end") - g.t(x + 12, b(y + TAG), blk.name, 18, DIM, "sans") - return h, {} - rows = fold_rows(blk.rows, st.get("cur")) - h = TAG + len(rows) * ROW + PAD - reached = st.get("count", 0) > 0 - g.rect(x, y, w, h, PAGE) - g.rect(x, y, w, TAG, RAISED if reached else PAGE) - g.frame(x, y, w, h, GOLD if st.get("cur") else RULE, 2) # not reached yet: plain, no count - ink = CODE - C.addr(g, x + 12, y, blk.a, ink) - lines = sorted({r[1] for r in blk.rows if r[1]}) - if lines: - g.t(x + 12 + len("%x" % blk.a) * A + 16, b(y), "line %d" % lines[0] if len(lines) == 1 else - "lines %d to %d" % (lines[0], lines[-1]), 18, FAINT, "sans") - if reached: - g.t(x + w - 12, b(y), "×%d" % st["count"], S, VELLUM, MONO, "end") - yy, last_line, at = y + TAG, None, {} - for r in rows: - if r is None: - C.more(g, x + X_OFF - 36, yy) - g.t(x + X_MN, b(yy), "%d rows" % (len(blk.rows) - 8), S, FAINT, MONO) - yy += ROW - continue - a, ln, mn, ops, t, callee = r - at[a] = yy - dim_ = False - if a == st.get("cur"): - g.path(f"M{x + 20},{yy + 12} l-10,-6 v12 Z", fill=C.current_row(g, x + 2, yy, w - 4, 24)) - elif a in st.get("trail", []): - g.rect(x + 2, yy + 1, 4, ROW - 2, TRAIL[st["trail"].index(a)]) - g.t(x + X_OFF, b(yy), "+%x" % (a - base), S, FAINT if not dim_ else mix(FAINT, PAGE, 0.4), MONO, "end") - if ln and ln != last_line: - on = ln == st.get("cur_line") and st.get("cur") - g.t(x + X_LINE, b(yy), str(ln), S, GOLD if on else FAINT, BOLD if on else MONO, "end") - last_line = ln - fade = (lambda c: mix(c, PAGE, 0.55)) if dim_ else (lambda c: c) - g.t(x + X_MN, b(yy), mn, S, fade(FAINT if mn in ("nop", "endbr64") else KW), - MONO if mn in ("nop", "endbr64") else BOLD) - if t and (mn.startswith("j") or mn == "call"): - ex = C.addr(g, x + X_OPS, yy, t, fade(CODE)) - else: - ex = C.operands(g, x + X_OPS, yy, mn, ops, fade(VELLUM)) - note = st.get("notes", {}).get(a) - if note: - nx = max(ex + 2 * A, x + X_OPS + 20 * A) - for s_, ink_ in note: - if ink_ == "chip": - g.rect(nx, yy + 2, 32, 20, RAISED) - g.t(nx + 16, b(yy), s_, S, BRIGHT, BOLD, "middle") - nx += 38 - else: - g.t(nx, b(yy), s_, S, ink_, MONO) - nx += len(s_) * A - if mn == "call" and callee: # a call that comes back: out of the block's side and in again a row down - hx = x + w - g.path(f"M{hx},{yy + 12} h14 q6,0 6,6 v12 q0,6 -6,6 h-8", fade(DIM) if reached else RULE, 2) - g.path(f"M{hx},{yy + 36} l8,-4 v8 Z", fill=fade(DIM) if reached else RULE) - g.t(hx + 28, b(yy) + 12, callee, S, fade(VELLUM), MONO) - if st.get("split") and r is rows[-1] and not st.get("cur"): # a conditional's two ways, counted, in words - tk, nt = st["split"] - g.t(max(ex + 2 * A, x + X_OPS + 10 * A), b(yy), "taken %d · not %d" % (tk, nt), S, FAINT, MONO) - yy += ROW - if blk.ret: # the way out: a stub and a bar under the block - cx = x + w / 2 - g.rect(cx - 1, y + h, 2, 14, DIM if reached else RULE) - g.rect(cx - 14, y + h + 14, 28, 3, DIM if reached else RULE) - return h, at - - -# ---- the graph: placement and edges ----------------------------------------------------------------------- def arrow(g, pts, *a, **k): """gen.arrow, its repeated and straight-through points dropped.""" q = [] @@ -253,7 +158,7 @@ def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0 """Every edge: forward ones down from the bottom by the side their target lies on, along the gap's middle, down into the target's top; one that would cross a block runs in the right channel; a back edge leaves the bottom, goes out to its loop's lane on the left, climbs it and enters its header's head from the side: the one thing - that climbs. Ink: never taken `rule`; taken in the run `dim`; the last three taken the trail's golds.""" + that climbs. Ink by the moment shown: not taken yet `rule`; taken `dim`; the last three the trail's golds.""" sw0 = 2 trail = st.get("edge_trail", []) counts = st.get("edge_counts", {}) @@ -324,243 +229,6 @@ def run_state(bl, path, upto, base): return cnt, ec, trail -# ---- the data: sort as the scene builds it ------------------------------------------------------------------ -SORTC = [r for r in read_dis("sort-clang.dis") if 0x401150 <= r[0] < 0x401200] -SORT_BASE = 0x401150 -SORT_BL = blocks(SORTC, SORT_BASE) -SB = sorted(SORT_BL) -# the block leaders the run hit, from sort's entry to its return: ztrace record --by insn --from sort, clang -O0 -SORT_PATH = [SORT_BASE + int(o, 16) for o in ( - "0 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f " - "56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 " - "5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5d 97 99 12 a7").split()] -O = lambda off: SORT_BASE + off -NEVER = {(a, t) for a in SORT_BL for t, _ in SORT_BL[a].out} - set(zip(SORT_PATH, SORT_PATH[1:])) - - -def sort_state(upto, cur, trail_rows, notes=None, cur_line=12): - cnt, ec, trail = run_state(SORT_BL, SORT_PATH, upto, SORT_BASE) - blk = {a: {"count": cnt.get(a, 0)} for a in SORT_BL} - if cur: - ca = max(a for a in SORT_BL if a <= cur) - blk[ca].update(cur=cur, trail=trail_rows, notes=notes or {}, cur_line=cur_line) - return {"blocks": blk, "edge_counts": ec, "edge_trail": trail, "never": NEVER} - - -# the 11th time through the compare: i = 6, j = 4, a[3] = 17 against a[4] = 5; the stop is the jne after it -# (sort-dbg.txt). Five swaps so far, five turns of each loop. -UPTO = [i for i, a in enumerate(SORT_PATH) if a == O(0x56)][10] + 1 -PC = 0x4011ab -TRAIL_ROWS = [0x4011a9, 0x4011a6, 0x4011a3] -NOTES = {0x4011a6: [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)], - 0x4011a9: [("1", VELLUM), (" : ", FAINT), ("1", VELLUM), (" ", FAINT), ("zf", DIM)], - 0x4011ab: [("taken", VELLUM), (" · reads zf", FAINT)]} - - -def frame_sort_map(name): - """Mock 22: on the map, the disassembly column as sort's track, one column wide (1024 to 1904), beside the - source whole: the cards on their spine, the loops' lanes on the left, the jumps past cards on the right.""" - gen.W, gen.H = 1980, 1860 - g = Svg() - src = open(HERE + "/../../anim/tools/sort.c").read().split("\n") - C.LX = 112 - C.source(g, 96, 22, src, 1, 12, [14, 13], "sort.c", 22) - C.LX = 64 - g.t(112, 60, "the map: sort's disassembly as its track, in the second column (1024 to 1904), at the 11th compare", - 22, DIM, "sans") - st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES) - hgt, ats, _ = track_map(g, 1024, 96, 880, SORT_BL, SB[0], SORT_BASE, st, "disassembly · sort", - "its blocks · visits · the edges taken · the loops' turns", notes_w=17 * A) - print("22: the track on the map is %d high; the map's stage holds %d" % (hgt, 1688)) - g.rect(112, 1784, 1792, 2, RULE) - g.t(112, 1808, "the map's stage ends at 1784", 18, FAINT, "sans") - g.save(name) - - -# ---- libc's open: unreached blocks folded ----------------------------------------------------------------- -OPEN = read_dis("libc-open.dis", lines=False) -OPEN_BASE = 0x110ec0 -L = 0x7ffff7c00000 - - -def rebase(rows): - return [(a + L, ln, mn, ops, (t + L) if t else None, callee) for a, ln, mn, ops, t, callee in rows] - - -OPEN_BL = blocks(rebase(OPEN), OPEN_BASE + L) -OPEN_PATH = [a + L for a in (0x110ec0, 0x110ee9, 0x110efb, 0x110fb0, 0x110fca, 0x110fd2, 0x110fd4, 0x110fe3)] - - -def fold_unreached(bl, path, groups): - """Blocks the run never reached, a connected run of them one box: `5 blocks not reached`.""" - out = {a: bl[a] for a in bl if a in path} - for name, members in groups: - rows = [r for m in members for r in bl[m].rows] - fb = Block(name, rows) - fb.folded = members - out[members[0]] = fb - rep = {m: ms[0] for _, ms in groups for m in ms} - for a, blk in list(out.items()): - seen = [] - for t, k in (blk.out if not hasattr(blk, "folded") else [o for m in blk.folded for o in bl[m].out]): - t2 = rep.get(t, t) - if t2 != a and t2 in out and (t2, k) not in seen and t2 not in [s_ for s_, _ in seen]: - seen.append((t2, k)) - blk.out = seen - blk.ret = blk.ret if not hasattr(blk, "folded") else False - return out - - -def frame_open_map(name): - """Mock 23: libc's open, 19 blocks, of which the run reached 8; the 11 it did not are folded into five cards by - what they are. The pc is at the `syscall` (mock 16's moment 4): the blocks after it are reached later.""" - gen.W, gen.H = 1008, 1640 - g = Svg() - o = lambda x: x + L - groups = [("the O_CREAT path: the mode from the varargs", [o(0x110f90)]), - ("multi-threaded: a cancellable call", [o(0x110f1b), o(0x110f23), o(0x110f2b), o(0x110f6d)]), - ("an error: errno set, -1 returned", [o(0x110fe8), o(0x110f79), o(0x110f7e)]), - ("cancelled", [o(0x110ff6), o(0x111009)]), - ("the canary broken", [o(0x110fec), o(0x110ff0)])] - groups = [(n, [m for m in ms if m in OPEN_BL]) for n, ms in groups] - bl = fold_unreached(OPEN_BL, OPEN_PATH, groups) - st = {"blocks": {a: {"count": 1} for a in OPEN_PATH}} - st["blocks"][o(0x110fb0)].update(cur=o(0x110fc5), trail=[o(0x110fc0), o(0x110fb9), o(0x110fb6)], - notes={o(0x110fc5): [("openat", BRIGHT), (" nr 257", FAINT)]}) - st["edge_counts"] = Counter(zip(OPEN_PATH[:4], OPEN_PATH[1:4])) - st["edge_trail"] = list(reversed(list(zip(OPEN_PATH[:4], OPEN_PATH[1:4])))) - for a in OPEN_PATH[4:]: - st["blocks"][a]["count"] = 0 # not yet: the run is at the syscall - for _, ms in groups: - st["blocks"][ms[0]] = {"count": 0} - g.t(64, 60, "the map: libc's open as its track · 19 blocks, the run reached 8; the 11 never reached folded", 22, - DIM, "sans") - hgt, _, _ = track_map(g, 64, 96, 880, bl, OPEN_PATH[0], OPEN_BASE + L, st, "disassembly · open · libc.so.6", - "no source · 19 blocks · folded: 11 never reached", notes_w=18 * A) - print("23: %d high" % hgt) - g.save(name) - - -# ---- reverse: a loop's turn, as a strip ------------------------------------------------------------------- -REV = read_dis("reverse-O0.dis") -REV_BASE = 0x401188 -REV_BL = blocks(REV, REV_BASE) -RB = sorted(REV_BL) -R0, R1, R2, R3 = RB -REV_PATH = [R0, R2, R1, R2, R1, R2, R1, R2, R3] - - -def frame_strip(name): - """Mock 24: reverse's loop in the lens, four instants: the condition about to be decided; the edge taken, the - mark on it; the turn, the mark on the arch over the loop's blocks, its count struck; the way out, under.""" - gen.W, gen.H = 1920, 600 - g = Svg() - inst = [ - ("1", "the condition", "the pc on jne in the test's block, the second time; its two ways out", 4, 0x4011ce, None), - ("2", "the edge taken", "taken: along the line to the body, the mark on the edge, landing", 4, None, - ((R2, R1), 0.55)), - ("3", "the loop's turn", "back over the arch to the test, the mark coming round; the count struck as it lands", 5, - None, ((R1, R2), 0.6)), - ("4", "the way out", "not taken, the fourth time: under the body to the exit, landed", 9, 0x4011d0, None), - ] - for k, (num, title, sub, upto, cur, moving) in enumerate(inst): - x, y = 64 + (k % 2) * 912, 40 + (k // 2) * 280 - g.t(x, y + 24, num, 28, GOLD, "sansb") - g.t(x + 28, y + 24, title, 28, VELLUM, "sansm") - g.t(x, y + 52, sub, 18, FAINT, "sans") - path = REV_PATH[:upto] + ([moving[0][1]] if moving else []) - cnt, ec, trail = run_state(REV_BL, path, len(path), REV_BASE) - if moving: # the mark is on its edge: the target not yet entered, the edge lit - cnt[moving[0][1]] -= 1 - st = {"blocks": {a: {"count": cnt.get(a, 0)} for a in REV_BL}, "edge_counts": ec, "edge_trail": trail} - if cur: - ca = max(a for a in REV_BL if a <= cur) - st["blocks"][ca].update(cur=cur) - track_lens(g, x, y + 72, 880, 200, REV_BL, R0, REV_BASE, st, "the blocks of reverse", moving=moving, - struck=moving[0] if moving and moving[0] == (R1, R2) else None) - g.save(name) - - -# ---- the layered form, as the lens drew it before the track (the comparison sheet) ------------------------- -def silhouette(g, x, y, w, h, bl, entry, base, cols, st, title, rounded=False, pitch=300): - """The layered form without its text (the lens before the track): a block a box 24 high, as wide as its rows - (10 a row, 132 at least), its offset and visits; the pc's gold; edges and lanes as on the map, small. - rounded: the same layers with pills and round corners (the comparison sheet's second form).""" - lay, back = layers(bl, entry) - widths = {a: max(132, 60 + len(bl[a].rows) * 10) for a in bl} - heights = {a: 24 for a in bl} - nb = len(back) - x0 = x + 24 + nb * 10 + 16 - pos, lh, ly = place(bl, lay, cols, widths, heights, x0 + 60, y + TAG + 14, pitch, 12) - C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits · the path") - edges(g, bl, lay, back, pos, widths, heights, lh, ly, 12, st, base, x + 24, max(pos[a][0] + widths[a] for a in bl) + 20, - small=True, radius=12 if rounded else None) - for a in bl: - s_ = st["blocks"].get(a, {}) - bx, by = pos[a] - cur = s_.get("cur") - if rounded: - pill(g, bx, by, widths[a], RAISED if s_.get("count") else PAGE, GOLD if cur else RULE, 3 if cur else 2) - else: - g.rect(bx, by, widths[a], 24, RAISED if s_.get("count") else PAGE) - g.frame(bx, by, widths[a], 24, GOLD if cur else RULE, 2 if not cur else 3) - g.t(bx + (12 if rounded else 8), b(by), "+%x" % (a - base), S, VELLUM if s_.get("count") else FAINT, MONO) - if s_.get("count"): - g.t(bx + widths[a] - (12 if rounded else 8), b(by), "×%d" % s_["count"], S, DIM, MONO, "end") - return pos, max(by for _, by in pos.values()) + 24 - y - - -# ---- the track ---------------------------------------------------------------------------------------------- -def loops_of(bl, entry): - """Layers and back edges as `layers` finds them, and each loop's blocks: a back edge's natural loop (its - header, and every block that reaches its latch without passing the header), loops of one header merged.""" - lay, back = layers(bl, entry) - preds = {a: [] for a in bl} - for a in bl: - for t, _ in bl[a].out: - preds[t].append(a) - loops = {} - for a, h in back: - body, todo = {h, a}, [a] - while todo: - n = todo.pop() - if n == h: - continue - for p in preds[n]: - if p not in body: - body.add(p) - todo.append(p) - loops.setdefault(h, set()).update(body) - return lay, back, loops - - -def track_order(bl, lay, loops): - """The line's order: as they run (by layer, then address), each loop's blocks together from its header, so - that a block outside a loop never sits on its floor; the blocks that return last.""" - def emit(nodes, header=None): - out, done = [], set() - for a in sorted(nodes, key=lambda a: (lay[a], a)): - if a in done: - continue - if a in loops and a != header and loops[a] <= nodes: - inner = emit(loops[a], a) - out += inner - done |= set(inner) - else: - out.append(a) - done.add(a) - return out - return emit(set(bl)) - - -def spans_levels(spans): - """Arches (or dips) by nesting: one that holds another is a level higher, so that none crosses another.""" - lv = {} - for s in sorted(spans, key=lambda s: s[1] - s[0]): - inner = [lv[o[2]] for o in spans if o[2] in lv and s[0] <= o[0] and o[1] <= s[1] and o[2] != s[2]] - lv[s[2]] = 1 + max(inner, default=0) - return lv - class Path: """An edge as drawn: straight runs and quarter circles, one family. Kept as points too, to measure it and to @@ -619,13 +287,6 @@ def draw_path(g, p, ink, sw, dash=None, hl=8, hw=8): gen.head_tri(g, x2, y2, ux, uy, ink, hl, hw) -def pill(g, x, y, w, fill, stroke, sw=2, dash=None): - """A block in the lens: a pill 24 high, its ends half circles.""" - a = (f'") - - def mark(g, p, f, ink=GOLD): """The current mark travelling an edge: the gold plaque, its point the way it goes.""" (mx, my), (ux, uy) = p.at(f) @@ -634,260 +295,183 @@ def mark(g, p, f, ink=GOLD): def edge_ink(e, st): - """Never taken in the whole recording: rule, dashed. Not yet: rule. Taken: dim. The last three: the trail's - golds, the newest 3 units.""" + """By the moment shown: not taken yet, `rule`; taken, `dim`; the last three taken, the trail's golds, the newest + 3 units. Nothing that needs the rest of the run.""" trail = st.get("edge_trail", []) if e in trail: return TRAIL[trail.index(e)], 3 if trail.index(e) == 0 else 2, None if st.get("edge_counts", {}).get(e, 0): return DIM, 2, None - return RULE, 2, "12 8" if e in st.get("never", ()) else None - - -TRACK = dict(gap=40, arch=52, arch_step=36, dip=44, dip_step=16, stub=10, port=16) - - -def track_lens(g, x, y, w, h, bl, entry, base, st, title, note="its blocks · the visits · the path · the loops' turns", - tag=True, moving=None, struck=None): - """The `blocks` lens: the function as a track across the band. A block a pill 24 high (its offset, its - visits; as long as its rows at 10 a row, the text's length at least) on one line, in the order they run; - an edge to the next block a straight run along the line; a loop's back edge an arch over its blocks, out of - its latch's top and down into its header's (the loop is the closed shape the arch and its floor make, its - turns at its centre); a forward jump past blocks a dip under them. Arches nest by level, 32 apart; dips 16. - moving: (edge, fraction): the mark on that edge. struck: an arch whose count is being struck. - Returns the edges' paths, and the line's y.""" - lay, back, loops = loops_of(bl, entry) - order = track_order(bl, lay, loops) - idx = {a: i for i, a in enumerate(order)} - - def text_of(a): - n = st["blocks"].get(a, {}).get("count", 0) - return "+%x" % (a - base), ("×%d" % n) if n else "" - pw = {a: max(24 + (len(text_of(a)[0]) + len(text_of(a)[1]) + 1) * A + 8, 10 * len(bl[a].rows) + 24) for a in order} - gap = TRACK["gap"] - total = sum(pw.values()) + gap * (len(order) - 1) - xs, xx = {}, x + (w - total) / 2 - for a in order: - xs[a] = xx - xx += pw[a] + gap - arches = [(idx[t], idx[a], (a, t)) for a, t in back] - dips = [(idx[a], idx[t], (a, t)) for a in order for t, _ in bl[a].out - if (a, t) not in back and idx[t] > idx[a] + 1] - al, dl = spans_levels(arches), spans_levels(dips) - H = lambda k: TRACK["arch"] + TRACK["arch_step"] * (k - 1) - D = lambda k: TRACK["dip"] + TRACK["dip_step"] * (k - 1) - top, foot = H(max(al.values(), default=1)), D(max(dl.values(), default=1)) - y0 = y + TAG + (h - TAG - top - foot) / 2 + top + return RULE, 2, None + + +def pill(g, x, y, w, fill, stroke, sw=2, dash=None): + """A block: a pill 24 high, its ends half circles.""" + a = (f'") + + +def calls_of(blk): + """The functions a block calls and that come back: named in its pill, after its offset.""" + if hasattr(blk, "folded"): + return "" + names = [r[5] for r in blk.rows if r[2] == "call" and r[5] and r[5] not in NORETURN] + return " ".join(names[:2]) + (" …" if len(names) > 2 else "") + + +def pill_text(bl, a, base, st): + """A block's words: its offset, the functions it calls, and its visits so far (none before its first).""" + if hasattr(bl[a], "folded"): + return "+%x …" % (bl[a].folded[0] - base), "· %d" % len(bl[a].folded) + n = st["blocks"].get(a, {}).get("count", 0) + return "+%x" % (a - base), ("×%d" % n) if n else "" + + +def pill_w(bl, a, base, st): + off, cnt = pill_text(bl, a, base, st) + c = calls_of(bl[a]) + return 24 + (len(off) + len(cnt) + 1 + (len(c) + 1 if c else 0)) * A + 8 + + +def draw_pill(g, x, y, bl, a, base, st, w=None): + """Reached so far: on `raised`, its offset primary, its visits. Not yet: on the page, its offset faint, no count. + A fold of blocks not reached yet: dashed, its span and how many. The pc's: framed gold, 3.""" + w = w or pill_w(bl, a, base, st) + s0 = st["blocks"].get(a, {}) + n, cur, fold = s0.get("count", 0), s0.get("cur"), hasattr(bl[a], "folded") + pill(g, x, y, w, RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2, "12 8" if fold else None) + off, cnt = pill_text(bl, a, base, st) + g.t(x + 12, b(y), off, S, VELLUM if n else FAINT, MONO) + c = calls_of(bl[a]) + if c: # a call is not an edge: the callee named in the pill, faint + g.t(x + 12 + (len(off) + 1) * A, b(y), c, S, FAINT, MONO) + if cnt: + g.t(x + w - 12, b(y), cnt, S, DIM if n else FAINT, MONO, "end") + return w + + +# ---- the second form: layers ------------------------------------------------------------------------------------ +def layered(g, x, y, w, h, bl, entry, base, cols, st, title, pitch=300, tag=True): + """`layers`: the blocks in layers by the longest path from the entry (from the code, not from the run), each + under its fall-through predecessor and a taken target to its right; a block a pill; edges down from the foot, + a back edge up its lane on the left; every corner round (12). Returns the pills' places and the height used.""" + lay, back = layers(bl, entry) + widths = {a: pill_w(bl, a, base, st) for a in bl} + heights = {a: 24 for a in bl} + x0 = x + 24 + len(back) * 10 + 16 + pos, lh, ly = place(bl, lay, cols, widths, heights, x0 + 60, y + TAG + 14, pitch, 12) if tag: - C.tag(g, x, y, w, h, title, focus=True, note=note) - paths = {} - s_, P = TRACK["stub"], TRACK["port"] - for a in order: - for t, kind in bl[a].out: - e = (a, t) - if e in back: # out of the latch's top, over, down into the header's - k, r = H(al[e]), H(al[e]) - 12 - s_ - xa, xt = xs[a] + pw[a] - P, xs[t] + P - p = (Path(xa, y0 - 12).to(xa, y0 - 12 - s_).arc(xa - r, y0 - k, r, False).to(xt + r, y0 - k) - .arc(xt, y0 - 12 - s_, r, False).to(xt, y0 - 12)) - elif idx[t] == idx[a] + 1: # to the next block: along the line - p = Path(xs[a] + pw[a], y0).to(xs[t], y0) - else: # past blocks: under them - k, r = D(dl[e]), D(dl[e]) - 12 - s_ - xa, xt = xs[a] + pw[a] - P, xs[t] + P - p = (Path(xa, y0 + 12).to(xa, y0 + 12 + s_).arc(xa + r, y0 + k, r, False).to(xt - r, y0 + k) - .arc(xt, y0 + 12 + s_, r, False).to(xt, y0 + 12)) - paths[e] = p - for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())): # the trail on top - ink, sw, dash = edge_ink(e, st) - draw_path(g, p, ink, sw, dash) - for a, t in back: # each loop's turns, at its centre: under its arch, over what it holds - e = (a, t) - n = st.get("edge_counts", {}).get(e, 0) - inner = max([H(al[o]) for o in al if al[o] < al[e]] + [12]) - cx, cy = (xs[t] + xs[a] + pw[a]) / 2, y0 - inner - (H(al[e]) - inner) * 0.4 # clear of the mark on the arch - s = "×%d" % n - if struck == e: - g.rect(cx - len(s) * A / 2 - 5, cy - 11, len(s) * A + 10, 22, C.SOFT) - g.t(cx, cy + 7, s, S, BRIGHT, BOLD, "middle") - elif n: - g.t(cx, cy + 7, s, S, DIM, MONO, "middle") - for a in order: - s0 = st["blocks"].get(a, {}) - n, cur = s0.get("count", 0), s0.get("cur") and not moving - pill(g, xs[a], y0 - 12, pw[a], RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2) - off, cnt = text_of(a) - g.t(xs[a] + 12, b(y0 - 12), off, S, VELLUM if n else FAINT, MONO) - if cnt: - g.t(xs[a] + pw[a] - 12, b(y0 - 12), cnt, S, DIM, MONO, "end") - for i, r_ in enumerate(bl[a].rows): # a call that comes back: a hook under the pill, out and in again - if r_[2] == "call" and r_[5] and r_[5] not in NORETURN: - cx = xs[a] + 16 + (pw[a] - 48) * i / max(len(bl[a].rows) - 1, 1) - g.path(f"M{cx:.1f},{y0 + 12:.1f} v6 a5,5 0 0 0 10,0 v-6", DIM if n else RULE, 2) - g.t(cx + 16, y0 + 34, r_[5], S, VELLUM if n else FAINT, MONO) - if moving: - mark(g, paths[moving[0]], moving[1]) - return paths, y0, xs, pw - - -def track_map(g, x, y, w, bl, entry, base, st, title, note, notes_w=0): - """The map's graph: the same track run down, a block a card that carries its rows (`draw_block`), the cards - in the line's order on one spine 40 in from their left; a back edge leaves its latch's left side and climbs - a lane on the left, 48 apart, into its header's head; a forward jump past cards leaves the source's right - side and goes down a channel on the right into its target's head. Every bend a quarter circle of 16; cards 10 - apart. The turns in the lobe between a lane and what it holds; a conditional's two ways counted in words in - its jump's row (`taken 5 · not 6`), where the pc's block has the jump's own annotation. - Returns the panel's height and each card's rows' y.""" - lay, back, loops = loops_of(bl, entry) - order = track_order(bl, lay, loops) - idx = {a: i for i, a in enumerate(order)} - fold = lambda a: hasattr(bl[a], "folded") - split_w = lambda a: (X_OPS + max(len("%x" % (bl[a].rows[-1][4] or 0)) + 2, 10) * A + 17 * A - if len(bl[a].out) == 2 and st["blocks"].get(a, {}).get("count") - and not st["blocks"].get(a, {}).get("cur") else 0) - widths = {a: 520 if fold(a) else max(block_w(bl[a], base, notes_w if st["blocks"].get(a, {}).get("notes") else 0), - split_w(a)) for a in order} - heights = {a: TAG + (ROW if fold(a) else len(fold_rows(bl[a].rows, st["blocks"].get(a, {}).get("cur"))) * ROW) + PAD - for a in order} - arches = [(idx[t], idx[a], (a, t)) for a, t in back] - dips = [(idx[a], idx[t], (a, t)) for a in order for t, _ in bl[a].out - if (a, t) not in back and idx[t] > idx[a] + 1] - al, dl = spans_levels(arches), spans_levels(dips) - cx0 = x + 24 + 48 * max(al.values(), default=0) + 12 - ys, yy = {}, y + TAG + 8 - for a in order: - ys[a] = yy - yy += heights[a] + 10 - yy += 10 # room under the last card for the way out's bar - hook = lambda a: max([28 + len(r[5]) * A for r in bl[a].rows if r[2] == "call" and r[5]] + [0]) if not fold(a) else 0 - chan = max(cx0 + widths[a] + hook(a) for a in order) + 24 - hgt = yy - y - C.tag(g, x, y, w, hgt, title, focus=True, note=note) - R, spine = 16, cx0 + 40 - paths = {} - for a in order: - for t, kind in bl[a].out: - e = (a, t) - ya, yt = ys[a] + heights[a] - 14, ys[t] + 12 - if e in back: - L = cx0 - 48 * al[e] - p = (Path(cx0, ya).to(L + R, ya).arc(L, ya - R, R, True).to(L, yt + R).arc(L + R, yt, R, True) - .to(cx0, yt)) - elif idx[t] == idx[a] + 1: - p = Path(spine, ys[a] + heights[a]).to(spine, ys[t]) - else: - Cx = chan + 32 * (dl[e] - 1) - p = (Path(cx0 + widths[a], ya).to(Cx - R, ya).arc(Cx, ya + R, R, True).to(Cx, yt - R) - .arc(Cx - R, yt, R, True).to(cx0 + widths[t], yt)) - paths[e] = p - for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())): - ink, sw, dash = edge_ink(e, st) - draw_path(g, p, ink, sw, dash, hl=10, hw=10) - counts = st.get("edge_counts", {}) - for a, t in back: # the turns, in the lobe - e = (a, t) - n = counts.get(e, 0) - if n: - L = cx0 - 48 * al[e] - g.t(L + 24, (ys[t] + ys[a] + heights[a]) / 2 + 7, "×%d" % n, S, DIM, MONO, "middle") - ats = {} - for a in order: - s0 = dict(st["blocks"].get(a, {})) - if len(bl[a].out) == 2 and not fold(a) and s0.get("count"): # a conditional reached: its two ways counted - (t1, k1), (t2, k2) = bl[a].out - tk, nt = (t1, t2) if k1 == "taken" else (t2, t1) - s0["split"] = (counts.get((a, tk), 0), counts.get((a, nt), 0)) - _, at = draw_block(g, cx0, ys[a], widths[a], bl[a], base, s0) - ats.update(at) - return hgt, ats, paths - - -# ---- rings: the comparison sheet's third form, each loop a circle its blocks sit on ---------------------------- -RING_AT = {0x12: ("o", 180), 0x1e: ("o", 235), 0x24: ("o", 300), 0x5d: ("o", 25), 0x97: ("o", 80), 0x99: ("o", 130), - 0x2f: ("i", 15), 0x56: ("i", 95), 0x5f: ("i", 185)} - - -def rings(g, x, y, w, h, st, title): - """sort as rings: the outer loop a circle of 170, its blocks round it clockwise; the inner loop a circle of 92 - inside it, touching it at its header; the way in and the way out as short tracks at the left; a loop's exit a - chord between the rings. Every edge an arc of its ring or a straight chord.""" - C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits · the path · the loops' turns") - R, r = 170, 92 - ox, oy = x + w / 2 + 120, y + TAG + 24 + R - t0 = math.radians(300) - ix, iy = ox + (R - r) * math.cos(t0), oy + (R - r) * math.sin(t0) - ring = {"o": (ox, oy, R), "i": (ix, iy, r)} + C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits so far · the path") + edges(g, bl, lay, back, pos, widths, heights, lh, ly, 12, st, base, x + 24, + max(pos[a][0] + widths[a] for a in bl) + 20, small=True, radius=12) + for a in bl: + draw_pill(g, *pos[a], bl, a, base, st, widths[a]) + return pos, max(by for _, by in pos.values()) + 24 - y + + +def fold_not_yet(bl, reached, groups): + """The blocks the run has not reached by the moment shown, folded: each group (the code beyond one way the run + has not taken yet, as far as it leads, cut so that no fold leads back into another) one dashed pill in the + place of its first block; an edge into or out of a member is the fold's.""" + out = {a: bl[a] for a in bl if a in reached or not any(a in ms for ms in groups)} + rep = {} + for ms in groups: + fb = Block("+%x" % ms[0], [r for m in ms for r in bl[m].rows]) + fb.folded = ms + out[ms[0]] = fb + rep.update({m: ms[0] for m in ms}) + for a, blk in list(out.items()): + seen = [] + for t, k in (blk.out if not hasattr(blk, "folded") else [o for m in blk.folded for o in bl[m].out]): + t2 = rep.get(t, t) + if t2 != a and t2 in out and t2 not in [s_ for s_, _ in seen]: + seen.append((t2, k)) + blk.out = seen + if hasattr(blk, "folded"): + blk.ret = False + return out + + +# ---- the first form: rings ---------------------------------------------------------------------------------- +def rings(g, x, y, w, h, bl, base, st, spec, title, moving=None, struck=None, tag=True): + """`rings`: each loop a circle its blocks sit on, upright, clockwise from its header at the ring's left (9 + o'clock), where the way in arrives; an inner loop a smaller ring outside its parent, touching it at its header, + which is the parent's block at 3 o'clock. An edge from a block to the next on its ring, and a loop's back edge, + are arcs of the ring; an edge inside a loop that passes blocks of it is an arc 30 inside the ring; a way out + leaves along the ring's tangent, out of the pill's foot, and every bend after is a quarter circle of 16. + Outside every loop the blocks lie as `layers` lays them. The loop's turns so far at its centre. + spec: rings {name: (dx, dy, r)} from the origin; at {offset: (ring, degrees)}; free {offset: (dx, dy)}; + the origin (dx, dy) from the panel's corner; edges {(from, to): kind}, kind "line", ("arc", ring), + ("skip", ring) or a function of the places giving a Path; hook {offset: (dx, side)}.""" + if tag: + C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits so far · the path · the loops' turns") + ox, oy = x + spec["origin"][0], y + spec["origin"][1] + ring = {k: (ox + dx, oy + dy, r) for k, (dx, dy, r) in spec["rings"].items()} pos = {} - for off, (k, deg) in RING_AT.items(): - cx, cy, rr = ring[k] - pos[O(off)] = (cx + rr * math.cos(math.radians(deg)), cy + rr * math.sin(math.radians(deg))) - pos[O(0x0)] = (ox - R - 170, oy) - pos[O(0xa7)] = (ox - R - 170, oy + 96) - texts = {a: ("+%x" % (a - SORT_BASE), "×%d" % st["blocks"][a]["count"] if st["blocks"][a]["count"] else "") - for a in SORT_BL} - pw = {a: 24 + (len(texts[a][0]) + len(texts[a][1]) + 1) * A + 8 for a in SORT_BL} + for off, (k, deg) in spec["at"].items(): + cx, cy, r = ring[k] + pos[base + off] = (cx + r * math.cos(math.radians(deg)), cy + r * math.sin(math.radians(deg))) + for off, (dx, dy) in spec["free"].items(): + pos[base + off] = (ox + dx, oy + dy) + pw = {a: pill_w(bl, a, base, st) for a in pos} inside = lambda a, px, py: abs(px - pos[a][0]) < pw[a] / 2 + 4 and abs(py - pos[a][1]) < 16 - def on_ring(a, t, k): - """The arc of ring k from a's pill to t's, clockwise, cut where each pill ends.""" - cx, cy, rr = ring[k] + def arc(a, t, k, inset=0): + cx, cy, r = ring[k] + r -= inset a0 = math.atan2(pos[a][1] - cy, pos[a][0] - cx) a1 = math.atan2(pos[t][1] - cy, pos[t][0] - cx) while a1 <= a0: a1 += 2 * math.pi - pt = lambda th: (cx + rr * math.cos(th), cy + rr * math.sin(th)) + pt = lambda th: (cx + r * math.cos(th), cy + r * math.sin(th)) s, e = a0, a1 while inside(a, *pt(s)): - s += 0.005 + s += 0.004 while inside(t, *pt(e)): - e -= 0.005 + e -= 0.004 p = Path(*pt(s)) - p.arc(*pt(e), rr, True) + steps = max(1, int((e - s) / (math.pi / 2)) + 1) # an arc a quarter or less at a time + for k_ in range(1, steps + 1): + p.arc(*pt(s + (e - s) * k_ / steps), r, True) return p paths = {} - for a in SORT_BL: - for t, kind in SORT_BL[a].out: - ka, kt = RING_AT.get(a - SORT_BASE, (None,))[0], RING_AT.get(t - SORT_BASE, (None,))[0] - if (a, t) == (O(0x0), O(0x12)): - p = Path(pos[a][0] + pw[a] / 2, oy).to(pos[t][0] - pw[t] / 2, oy) - elif (a, t) == (O(0x12), O(0xa7)): - sx = pos[a][0] - 20 - p = (Path(sx, oy + 12).to(sx, oy + 40).arc(sx - 56, oy + 96, 56, True) - .to(pos[t][0] + pw[t] / 2, oy + 96)) - elif ka and kt and ka == kt or (a - SORT_BASE, t - SORT_BASE) in ((0x24, 0x2f), (0x5f, 0x24)): - p = on_ring(a, t, "i" if (a - SORT_BASE, t - SORT_BASE) in ((0x24, 0x2f), (0x5f, 0x24)) else ka) - else: # between the rings, or across one: a chord - (ax, ay), (tx, ty) = pos[a], pos[t] - d = math.hypot(tx - ax, ty - ay) - ux, uy = (tx - ax) / d, (ty - ay) / d - s, e = 0, d - while inside(a, ax + ux * s, ay + uy * s): - s += 1 - while inside(t, ax + ux * e, ay + uy * e): - e -= 1 - p = Path(ax + ux * s, ay + uy * s).to(ax + ux * e, ay + uy * e) - paths[(a, t)] = p + for (fo, to), kind in spec["edges"].items(): + a, t = base + fo, base + to + if callable(kind): + p = kind(pos, pw, base) + elif kind == "line": + p = Path(pos[a][0] + pw[a] / 2, pos[a][1]).to(pos[t][0] - pw[t] / 2, pos[t][1]) + elif kind[0] == "arc": + p = arc(a, t, kind[1]) + else: + p = arc(a, t, kind[1], 30) + paths[(a, t)] = p for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())): ink, sw, dash = edge_ink(e, st) - if len(p.pts) > 2: # an arc: its head on the tangent at its end - draw_arc_head(g, p, ink, sw, dash) - else: - draw_path(g, p, ink, sw, dash) - for (cx, cy, rr), e in ((ring["o"], (O(0x99), O(0x12))), (ring["i"], (O(0x5f), O(0x24)))): - n = st["edge_counts"].get(e, 0) - tx, ty = (cx, cy) if rr < R else (cx - 80, cy + 60) - g.t(tx, ty + 7, "×%d" % n, S, DIM, MONO, "middle") - for a in SORT_BL: - s0 = st["blocks"][a] - n, cur = s0.get("count", 0), s0.get("cur") - px, py = pos[a][0] - pw[a] / 2, pos[a][1] - 12 - pill(g, px, py, pw[a], RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2) - g.t(px + 12, b(py), texts[a][0], S, VELLUM if n else FAINT, MONO) - if texts[a][1]: - g.t(px + pw[a] - 12, b(py), texts[a][1], S, DIM, MONO, "end") - sx, sy = pos[O(0x5f)][0] + 26, pos[O(0x5f)][1] - 12 - g.path(f"M{sx:.1f},{sy:.1f} v-6 a5,5 0 0 1 10,0 v6", DIM, 2) - g.t(sx + 16, sy - 6, "swap", S, VELLUM, MONO) + (draw_arc_head if len(p.pts) > 2 and abs(p.pts[-1][0] - p.pts[-2][0]) > 0.5 and + abs(p.pts[-1][1] - p.pts[-2][1]) > 0.5 else draw_path)(g, p, ink, sw, dash) + for k, e in spec["turns"].items(): # each loop's turns so far, at its centre, under the line its pills are on + cx, cy, _ = ring[k] + cy += spec.get("turns_dy", 30) + e = (base + e[0], base + e[1]) + n = st.get("edge_counts", {}).get(e, 0) + if not n: + continue + s, word = str(n), " turn" if n == 1 else " turns" + x0 = cx - (len(s) * A + gen.tw(word, 18, "sans")) / 2 + if struck == e: + g.rect(x0 - 5, cy - 11, len(s) * A + 10, 22, C.SOFT) + g.t(x0, cy + 7, s, S, BRIGHT if struck == e else VELLUM, BOLD if struck == e else MONO) + g.t(x0 + len(s) * A, cy + 6, word, 18, DIM, "sans") + for a in pos: + s0 = dict(st["blocks"].get(a, {})) + if moving: + s0.pop("cur", None) + draw_pill(g, pos[a][0] - pw[a] / 2, pos[a][1] - 12, bl, a, base, {"blocks": {a: s0}}, pw[a]) + if moving: + mark(g, paths[moving[0]], moving[1]) + return paths, pos def draw_arc_head(g, p, ink, sw, dash): @@ -904,72 +488,271 @@ def draw_arc_head(g, p, ink, sw, dash): gen.head_tri(g, x2, y2, (x2 - x1) / l_, (y2 - y1) / l_, ink, 8, 8) -def frame_forms(name): - """Mock 43: sort's graph four ways, at the same moment and at the lens's scale: the present form, its layers - rounded, rings, and the track (recommended), each in the box it is given and at the size it needs.""" - gen.W, gen.H = 1920, 1600 +# ---- the data: sort as the scene builds it ------------------------------------------------------------------ +SORTC = [r for r in read_dis("sort-clang.dis") if 0x401150 <= r[0] < 0x401200] +SORT_BASE = 0x401150 +SORT_BL = blocks(SORTC, SORT_BASE) +SB = sorted(SORT_BL) +# the block leaders the run hit, from sort's entry to its return: ztrace record --by insn --from sort, clang -O0 +SORT_PATH = [SORT_BASE + int(o, 16) for o in ( + "0 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f " + "56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 " + "5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5d 97 99 12 a7").split()] +O = lambda off: SORT_BASE + off + + +def sort_state(upto, cur, trail_rows, notes=None, cur_line=12): + """The run's facts by the moment shown: the path's first `upto` blocks, and nothing after.""" + cnt, ec, trail = run_state(SORT_BL, SORT_PATH, upto, SORT_BASE) + blk = {a: {"count": cnt.get(a, 0)} for a in SORT_BL} + if cur: + ca = max(a for a in SORT_BL if a <= cur) + blk[ca].update(cur=cur, trail=trail_rows, notes=notes or {}, cur_line=cur_line) + return {"blocks": blk, "edge_counts": ec, "edge_trail": trail} + + +# the 11th time through the compare: i = 6, j = 4, a[3] = 17 against a[4] = 5; the stop is the jne after it +# (sort-dbg.txt). Five swaps so far, five turns of each loop; the function's way out not taken yet. +UPTO = [i for i, a in enumerate(SORT_PATH) if a == O(0x56)][10] + 1 +PC = 0x4011ab +TRAIL_ROWS = [0x4011a9, 0x4011a6, 0x4011a3] +NOTES = {0x4011a6: [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)], + 0x4011a9: [("1", VELLUM), (" : ", FAINT), ("1", VELLUM), (" ", FAINT), ("zf", DIM)], + 0x4011ab: [("taken", VELLUM), (" · reads zf", FAINT)]} + + +def down_round(sx, sy, ty, tx, ey, r=16): + """A way out: straight down from (sx, sy) to ty, round a quarter, across to tx, round a quarter, and straight + to (tx, ey), up or down.""" + left = tx < sx + p = Path(sx, sy).to(sx, ty - r) + p.arc(sx + (-r if left else r), ty, r, left) + up = ey < ty + p.to(tx + (r if left else -r), ty) + p.arc(tx, ty + (-r if up else r), r, left if up else not left) + return p.to(tx, ey) + + +SORT_RINGS = { + "origin": (434, TAG + 14 + 144), + "rings": {"o": (0, 0, 140), "i": (224, 0, 84)}, + "at": {0x12: ("o", 180), 0x1e: ("o", 225), 0x24: ("o", 0), 0x5d: ("o", 60), 0x97: ("o", 110), 0x99: ("o", 145), + 0x2f: ("i", 270), 0x56: ("i", 0), 0x5f: ("i", 75)}, + "free": {0x0: (-320, 0), 0xa7: (-180, 124)}, + "edges": {(0x0, 0x12): "line", (0x12, 0x1e): ("arc", "o"), (0x1e, 0x24): ("arc", "o"), (0x24, 0x2f): ("arc", "i"), + (0x2f, 0x56): ("arc", "i"), (0x56, 0x5f): ("arc", "i"), (0x5f, 0x24): ("arc", "i"), + (0x24, 0x56): ("skip", "i"), (0x5d, 0x97): ("arc", "o"), (0x97, 0x99): ("arc", "o"), + (0x99, 0x12): ("arc", "o"), + # the inner loop's way out: down out of +56's foot, along its ring's tangent, under +5f, into +5d's end + (0x56, 0x5d): lambda pos, pw, base: (Path(pos[base + 0x56][0] + 30, pos[base + 0x56][1] + 12) + .to(pos[base + 0x56][0] + 30, pos[base + 0x5d][1] - 16) + .arc(pos[base + 0x56][0] + 14, pos[base + 0x5d][1], 16, True) + .to(pos[base + 0x5d][0] + pw[base + 0x5d] / 2, pos[base + 0x5d][1])), + # the function's way out: down out of +12's foot, outside the ring, into +a7 + (0x12, 0xa7): lambda pos, pw, base: Path(pos[base + 0x12][0] - 40, pos[base + 0x12][1] + 12) + .to(pos[base + 0xa7][0], pos[base + 0xa7][1] - 12)}, + "turns": {"o": (0x99, 0x12), "i": (0x5f, 0x24)}, +} + + +# ---- libc's open, at its syscall: a tree of branches, what is not reached yet folded -------------------------- +OPEN = read_dis("libc-open.dis", lines=False) +OPEN_BASE = 0x110ec0 +L = 0x7ffff7c00000 + + +def rebase(rows): + return [(a + L, ln, mn, ops, (t + L) if t else None, callee) for a, ln, mn, ops, t, callee in rows] + + +OPEN_BL = blocks(rebase(OPEN), OPEN_BASE + L) +OPEN_PATH = [a + L for a in (0x110ec0, 0x110ee9, 0x110efb, 0x110fb0)] # by the syscall (mock 16's moment 4) + + +# ---- reverse: a loop's turn ------------------------------------------------------------------------------------ +REV = read_dis("reverse-O0.dis") +REV_BASE = 0x401188 +REV_BL = blocks(REV, REV_BASE) +RB = sorted(REV_BL) +R0, R1, R2, R3 = RB +REV_PATH = [R0, R2, R1, R2, R1, R2, R1, R2, R3] +REV_RINGS = { + "origin": (441, TAG + 14 + 82), + "rings": {"o": (0, 0, 70)}, + "at": {R2 - REV_BASE: ("o", 180), R1 - REV_BASE: ("o", 0)}, + "free": {R0 - REV_BASE: (-230, 0), R3 - REV_BASE: (-100, 100)}, + "edges": {(R0 - REV_BASE, R2 - REV_BASE): "line", (R2 - REV_BASE, R1 - REV_BASE): ("arc", "o"), + (R1 - REV_BASE, R2 - REV_BASE): ("arc", "o"), + (R2 - REV_BASE, R3 - REV_BASE): lambda pos, pw, base: Path(pos[R2][0] - 30, pos[R2][1] + 12) + .to(pos[R3][0], pos[R3][1] - 12)}, + "turns": {"o": (R1 - REV_BASE, R2 - REV_BASE)}, +} + + +# ---- the disassembly beside the graph, linear, its blocks ruled --------------------------------------------------- +TEXT = read_dis("sort-clang.dis") # the program's text: swap, sort, main +FUNC = lambda a: "swap" if a < 0x401150 else "sort" if a < 0x401200 else "main" + + +def sort_disasm(g, y, n, line=12): + """n rows round the pc; each block's first row under a rule, its visits so far ranged right in the annotation's + room; the trail's three rows and the pc's with what they did; another function's rows `outside`.""" + i = [r[0] for r in TEXT].index(PC) + lo = max(0, min(i - n // 2, len(TEXT) - n)) + st = sort_state(UPTO, PC, TRAIL_ROWS) + notes = dict(NOTES) + notes[0x4011a3] = [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)] + rows, last = [], None + for a, ln, mn, ops, t, callee in TEXT[lo:lo + n]: + f = FUNC(a) + state = "cur" if a == PC else {0x4011a9: "trail0", 0x4011a6: "trail1", 0x4011a3: "trail2"}.get(a) + note = ("runs", notes[a]) if a in notes else ("text", callee, VELLUM) if mn == "call" else None + if f != "sort": + state = "other_first" if f != last else "other" + note = ("text", f, DIM) if f != last else note + rows.append((a, ln if f == "sort" else None, mn, + [(t, CODE)] if t and (mn.startswith("j") or mn == "call") else [(ops, VELLUM)], state, note)) + last = f + at = C.disasm(g, y, rows, "sort", line) + for a in at: + if a in SORT_BL: # a block's first row: the rule over it, its pill's count in digits + yy = at[a] + g.rect(C.LX + 2, yy, C.CW - 4, 2, RULE) + n_ = st["blocks"][a]["count"] + if n_: + g.t(C.LX + C.CW - 12, b(yy), "×%d" % n_, S, FAINT, MONO, "end") + line12 = [at[r[0]] for r in rows if r[1] == 12 and r[0] < 0x4011af] + return at, (min(line12), max(line12) + ROW), lo + + +# ---- the mocks ------------------------------------------------------------------------------------------------ +def frame_sort_map(name): + """Mock 22: the map's first two columns at the 11th compare: the drawing (rings, at its size in the frame) over + the source whole, and the disassembly column linear, 69 rows round the pc, each block ruled with its visits so + far; the thread across the gutter; the working frame's windows outlined.""" + gen.W, gen.H = 2000, 1860 g = Svg() st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES) - g.t(64, 56, "sort's graph, four ways", 36, BRIGHT, "sansm") - g.t(64, 90, "The same moment in each (the 11th compare: 17 > 5, jne about to take the swap); the lens's scale, " - "mono 20. Veiled: what falls outside the box the frame gives the lens.", 20, DIM, "sans") + g.t(112, 60, "the map: sort's rings over the source, the disassembly linear beside them, at the 11th compare", 22, + DIM, "sans") + rings(g, 112, 96, 880, 344, SORT_BL, SORT_BASE, st, SORT_RINGS, "the blocks of sort") + src = open(HERE + "/../../anim/tools/sort.c").read().split("\n") + C.LX = 112 + ys = C.source(g, 452, 22, src, 1, 12, [14, 13], "sort.c", 22) + C.LX = 1024 + at, run, lo = sort_disasm(g, 96, 69) + C.LX = 64 + D.thread_across(g, ys, [run]) + g.frame(112 - 4, 96 - 4, 888, 352, DIM, 2) # the frame's windows (25): the drawing whole + for bx, by, bw, bh in ((112, 452 + TAG + PAD + 8 * ROW, 880, 6 * ROW), (1024, at[0x4011ab] - 5 * ROW, 880, 11 * ROW)): + g.frame(bx - 1, by - 1, bw + 2, bh + 2, DIM, 2) # on the rows' edges, never through a line's letters + g.rect(112, 1798, 1792, 2, RULE) + g.t(112, 1824, "the map's stage ends at 1784; the other columns (memory, the registers whole, the stack) as in 19", + 18, FAINT, "sans") + g.save(name) + + +def frame_strip(name): + """Mock 24: reverse's loop as a ring, four instants: the condition; the edge taken, the mark on the ring's top; + the turn, the mark coming round under it, the count at the centre struck; the way out, down the tangent.""" + gen.W, gen.H = 1920, 712 + g = Svg() + inst = [ + ("1", "the condition", "the pc on jne in the test's block, the second time; its two ways out", 4, 0x4011ce, None), + ("2", "the edge taken", "taken: round the top of the ring to the body, the mark on it", 4, None, + ((R2, R1), 0.5)), + ("3", "the loop's turn", "back round the foot of the ring to the test; the count at its centre struck as it lands", + 5, None, ((R1, R2), 0.5)), + ("4", "the way out", "not taken, the fourth time: down the tangent, out of the ring, landed", 9, 0x4011d0, None), + ] + for k, (num, title, sub, upto, cur, moving) in enumerate(inst): + x, y = 64 + (k % 2) * 912, 40 + (k // 2) * 320 + g.t(x, y + 24, num, 28, GOLD, "sansb") + g.t(x + 28, y + 24, title, 28, VELLUM, "sansm") + g.t(x, y + 52, sub, 18, FAINT, "sans") + path = REV_PATH[:upto] + ([moving[0][1]] if moving else []) + cnt, ec, trail = run_state(REV_BL, path, len(path), REV_BASE) + if moving: # the mark is on its edge: the target not yet entered, the edge lit + cnt[moving[0][1]] -= 1 + st = {"blocks": {a: {"count": cnt.get(a, 0)} for a in REV_BL}, "edge_counts": ec, "edge_trail": trail} + if cur: + ca = max(a for a in REV_BL if a <= cur) + st["blocks"][ca].update(cur=cur) + rings(g, x, y + 72, 880, 248, REV_BL, REV_BASE, st, REV_RINGS, "the blocks of reverse", moving=moving, + struck=moving[0] if moving and moving[0] == (R1, R2) else None) + g.save(name) - def veil(x, y, w, h): - g.o.append(f'') + +def frame_forms(name): + """Mock 43: the graph's two forms at the lens's scale, every count as of the moment shown: rings (the first), on + sort in the pane the frame gives it; layers (the second), on sort, and on libc's open at its syscall, a tree of + branches, what the run has not reached yet folded.""" + gen.W, gen.H = 1920, 1260 + g = Svg() + st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES) + g.t(64, 56, "the graph's two forms", 36, BRIGHT, "sansm") + g.t(64, 90, "At the lens's scale, mono 20; each in the pane the `blocks` split gives it, 880 by 344. Every number is " + "the run's by the moment shown; veiled: what a pane must pan to.", 20, DIM, "sans") def label(x, y, key, title, sub): - g.t(x, y, key, 28, GOLD if key == "4" else BRIGHT, "sansb") + g.t(x, y, key, 28, GOLD if key == "1" else BRIGHT, "sansb") g.t(x + 30, y, title, 28, VELLUM, "sansm") g.t(x, y + 28, sub, 18, FAINT, "sans") + + def veil(x, y, w, h): + g.o.append(f'') + label(64, 152, "1", "rings: sort at the 11th compare", "each loop a ring, the inner touching the outer at its " + "header; ways out down the tangent; whole in 880 by 344") + rings(g, 64, 212, 880, 344, SORT_BL, SORT_BASE, st, SORT_RINGS, "the blocks of sort") cols = {a: 0 for a in SORT_BL} cols[O(0xa7)] = 1 cols[O(0x5f)] = 1 - for k, (key, title, sub, rounded) in enumerate(( - ("1", "present: layers, boxes, square lanes", "ten layers, 400 high: past the lens's 296 (veiled), so it " - "pans; a third of its width", False), - ("2", "the same layers, rounded", "pills and round corners: smoother, and just as tall", True))): - x = 64 + k * 912 - label(x, 152, key, title, sub) - _, hh = silhouette(Svg(), x, 212, 880, 999, SORT_BL, SB[0], SORT_BASE, cols, st, "", rounded, pitch=330) - silhouette(g, x, 212, 880, hh + 16, SORT_BL, SB[0], SORT_BASE, cols, st, "the blocks of sort", rounded, pitch=330) - veil(x - 2, 212 + 296, 884, hh + 16 - 296 + 2) - label(64, 704, "3", "rings", "each loop a circle its blocks sit on, the inner inside the outer: 420 high, " - "past the band's 200 (veiled)") - rings(g, 64, 764, 880, 420, st, "the blocks of sort") - veil(62, 764 + 200, 884, 222) + label(976, 152, "2", "layers: the same moment", "the loops as lanes; 400 high, so it pans in 344 (veiled): " + "for loops, rings") + _, hh = layered(Svg(), 976, 212, 880, 999, SORT_BL, SB[0], SORT_BASE, cols, st, "", pitch=330) + layered(g, 976, 212, 880, hh + 16, SORT_BL, SB[0], SORT_BASE, cols, st, "the blocks of sort", pitch=330) + veil(974, 212 + 344, 884, hh + 16 - 344 + 2) + # libc's open at its syscall: the branches it has taken, and a fold for each run of what it has not reached yet + o = lambda off: OPEN_BASE + L + off + bl = fold_not_yet(OPEN_BL, set(OPEN_PATH), [[o(x) for x in (0x5b, 0x63, 0x6b, 0xad, 0xb9, 0x136, 0x149)], + [o(x) for x in (0xbe, 0x10a, 0x112, 0x114, 0x123, 0x128, 0x12c, 0x130)]]) + ost = {"blocks": {a: {"count": 1 if a in OPEN_PATH else 0} for a in bl}, + "edge_counts": Counter(zip(OPEN_PATH, OPEN_PATH[1:])), + "edge_trail": list(reversed(list(zip(OPEN_PATH, OPEN_PATH[1:]))))} + ost["blocks"][OPEN_PATH[-1]]["cur"] = True + ocols = {a: (0 if a in OPEN_PATH else 1) for a in bl} + label(64, 670, "2", "layers: libc's open at its syscall", "a tree of branches and no loop (rings has none to " + "draw, and is this); what is not reached yet folded, dashed") + layered(g, 64, 730, 880, 344, bl, OPEN_PATH[0], OPEN_BASE + L, ocols, ost, "the blocks of open · libc.so.6", + pitch=380) nx = 976 for i, (s, ink) in enumerate(( - ("What each costs", VELLUM), - ("1 The tools' picture. Tall by nature: a layer a block,", DIM), - (" so it pans in a short pane, and leaves the width.", DIM), - ("2 Rounding the corners does not change the shape.", DIM), - ("3 The most circular, and a loop is a ring; but rings", DIM), - (" want a square pane, a loop's way out is a chord", DIM), - (" across them, and pills on its sides sit across it.", DIM), - ("4 The track. A line of blocks as they run, each loop", VELLUM), - (" an arch over its own blocks: a closed shape, its", VELLUM), - (" turns at its centre; a jump past blocks a dip", VELLUM), - (" under them. Wide and short: 11 blocks in 1622", VELLUM), - (" by 150, whole. Its order is the disassembly's,", VELLUM), - (" which is under the source; run down, it is the", VELLUM), - (" map's column with its rows.", VELLUM))): - g.t(nx, 730 + i * 30, s, 22 if i == 0 else 20, ink, "sansm" if i == 0 else "sans") - label(64, 1220, "4", "the track: recommended", "the band across the frame, 1792 by 200: the whole graph, no pan") - paths, y0, xs, pw = track_lens(g, 64, 1280, 1792, 200, SORT_BL, SB[0], SORT_BASE, st, "the blocks of sort") - print("43: the track is %d wide" % (max(xs[a] + pw[a] for a in xs) - min(xs.values()))) - g.t(64, 1530, "Ink in 3 and 4: never taken in the whole run, dashed rule (j > 0 failing); not yet, rule (the " - "way out); taken, dim; the last three, the trail's golds. 1 and 2 keep the layers' ink: never taken, rule.", - 18, DIM, "sans") + ("Which, and why", VELLUM), + ("1 Rings, the first form. A loop is a ring and the mark going", VELLUM), + (" round it is the picture of iteration; its turns at its", VELLUM), + (" centre. Nested loops: rings touching at the header.", VELLUM), + ("2 Layers, the second, for a function of branches: the path", DIM), + (" reads down, and a fork is two columns. Rings with no", DIM), + (" loop is this. For loops it is tall and pans.", DIM), + (" The track is withdrawn: a ring says a loop, a layer a", DIM), + (" branch; a line of blocks said neither, and its arches", DIM), + (" were rings flattened to fit a band.", DIM), + ("Nothing from after the moment: counts so far; an edge or", VELLUM), + ("a block not reached yet is quiet (rule, page, no count);", VELLUM), + ("open's folds are what it has not reached yet, and open", VELLUM), + ("as the run gets there.", VELLUM))): + g.t(nx, 690 + i * 30, s, 22 if i == 0 else 20, ink, "sansm" if i == 0 else "sans") + g.t(64, 1120, "Ink: not reached so far, rule; taken so far, dim; the last three, the trail's golds, the newest 3. " + "A fold, dashed. No count before a block's first visit.", 18, DIM, "sans") g.save(name) if __name__ == "__main__": assert len(SORT_BL) == 11 and len(REV_BL) == 4, (len(SORT_BL), len(REV_BL)) assert Counter(SORT_PATH)[O(0x56)] == 17 and Counter(SORT_PATH)[O(0x5f)] == 10 - lay_, back_, loops_ = loops_of(SORT_BL, SB[0]) - assert [a - SORT_BASE for a in track_order(SORT_BL, lay_, loops_)] == \ - [0x0, 0x12, 0x1e, 0x24, 0x2f, 0x56, 0x5f, 0x5d, 0x97, 0x99, 0xa7] + st_ = sort_state(UPTO, PC, TRAIL_ROWS) # nothing from after the moment: the way out not taken yet + assert st_["blocks"][O(0xa7)]["count"] == 0 and st_["edge_counts"][(O(0x12), O(0xa7))] == 0 + assert st_["blocks"][O(0x5f)]["count"] == 5 and st_["edge_counts"][(O(0x99), O(0x12))] == 5 frame_sort_map("22-graph-sort") - frame_open_map("23-graph-open") frame_strip("24-graph-strip") frame_forms("43-graph-forms") -- cgit v1.3