summaryrefslogtreecommitdiff
path: root/design/mock/graph.py
diff options
context:
space:
mode:
Diffstat (limited to 'design/mock/graph.py')
-rw-r--r--design/mock/graph.py722
1 files changed, 557 insertions, 165 deletions
diff --git a/design/mock/graph.py b/design/mock/graph.py
index e9b8f2b..6062fa9 100644
--- a/design/mock/graph.py
+++ b/design/mock/graph.py
@@ -1,12 +1,21 @@
#!/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.
- python3 -B graph.py # 22-graph-sort, 23-graph-open, 24-graph-strip, 25-blocks-lens (.svg)
+ python3 -B graph.py # 22-graph-sort, 23-graph-open, 24-graph-strip, 43-graph-forms (.svg)
+ # (25, the `blocks` lens in the working frame, is frame.py's)
-Data: sort and reverse from anim/tools/sort.c and list.c (cc -O0 -g -no-pie), their disassembly in
-sort-O0.dis and reverse-O0.dis (objdump -dl), the paths their runs took 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.
+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.
+
+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.
"""
+import math
import re
from collections import Counter
@@ -125,7 +134,9 @@ X_OFF, X_LINE, X_MN, X_OPS = 72, 116, 128, 212
def block_w(blk, base, note_w=0):
- return max(300, X_OPS + max(len(r[3]) for r in blk.rows) * A + 24 + note_w)
+ """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):
@@ -202,6 +213,9 @@ def draw_block(g, x, y, w, blk, base, st):
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
@@ -235,7 +249,7 @@ def place(bl, lay, cols, widths, heights, x0, y0, pitch, gap):
return pos, lh, ly
-def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x, small=False):
+def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x, small=False, radius=None):
"""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
@@ -271,7 +285,7 @@ def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0
hy = ty + (12 if not small else 12)
pts = [(sx, y + h), (sx, by), (lx, by), (lx, hy), (tx - 1, hy)]
st.setdefault("paths", {})[e] = pts
- arrow(g, pts, ink, sw, r=4 if small else 8, hl=7 if small else 10, hw=8 if small else 10)
+ arrow(g, pts, ink, sw, r=radius or (4 if small else 8), hl=7 if small else 10, hw=8 if small else 10)
if n: # the loop's turns, on the lane under its turn into the header
if st.get("struck_count") == e: # the count is a value: written, it is struck
g.rect(lx + 1, hy + 8, 10 + len(str(n)) * 11, 20, C.SOFT)
@@ -296,35 +310,11 @@ def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0
else:
pts = [(sx, y + h), (sx, gy), (tx_, gy), (tx_, ty)]
st.setdefault("paths", {})[e] = pts
- arrow(g, pts, ink, sw, r=4 if small else 8, hl=7 if small else 10, hw=8 if small else 10)
+ arrow(g, pts, ink, sw, r=radius or (4 if small else 8), hl=7 if small else 10, hw=8 if small else 10)
if n and kind != "jmp" and not small and len(outs) > 1:
g.t(sx + 8, y + h + 20, str(n), S, FAINT, MONO)
-def graph(g, x, y, w, title, note, bl, entry, base, cols, st, pitch=None, gap=48, notes_w=0):
- """The panel: its tag, the blocks at the map's size, the edges. Returns the blocks' row positions."""
- lay, back = layers(bl, entry)
- widths = {a: 520 if hasattr(bl[a], "folded") else block_w(bl[a], base, notes_w if st["blocks"].get(a, {}).get("notes")
- else 0) for a in bl}
- heights = {a: TAG + (ROW if hasattr(bl[a], "folded") else
- len(fold_rows(bl[a].rows, st["blocks"].get(a, {}).get("cur"))) * ROW) + PAD for a in bl}
- nb = len([e for e in back])
- lane_x0 = x + 24
- x0 = x + 24 + nb * 16 + 24
- pitch = pitch or max(widths.values()) + 56
- pos, lh, ly = place(bl, lay, cols, widths, heights, x0, y + TAG + 36, pitch, gap)
- channel_x = max(pos[a][0] + widths[a] for a in bl) + 32
- hgt = max(pos[a][1] + heights[a] for a in bl) - y + 48
- C.tag(g, x, y, w, hgt, title, focus=True, note=note)
- edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x)
- ats = {}
- for a in bl:
- s_ = st["blocks"].get(a, {})
- _, at = draw_block(g, pos[a][0], pos[a][1], widths[a], bl[a], base, s_)
- ats.update(at)
- return pos, ats, hgt
-
-
def run_state(bl, path, upto, base):
"""Visits and edge counts over the path's first `upto` blocks; the last three edges taken."""
p = path[:upto]
@@ -334,49 +324,56 @@ def run_state(bl, path, upto, base):
return cnt, ec, trail
-# ---- the data ---------------------------------------------------------------------------------------------
-SORT = read_dis("sort-O0.dis")
-SORT_BASE = 0x401143
-SORT_BL = blocks(SORT, SORT_BASE)
-SB = sorted(SORT_BL) # B0 .. B7 by address
-NAMES = dict(zip("B0 B1 B2 B3 B4 B5 B6 B7".split(), SB))
-SORT_PATH = [NAMES[n] for n in ("B0 B6 B1 B3 B4 B5 B6 B1 B3 B4 B5 B6 B1 B3 B4 B5 B6 B1 B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B1 "
- "B3 B4 B2 B3 B4 B5 B6 B1 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B1 "
- "B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B7").split()]
-SORT_COLS = {NAMES["B0"]: 0, NAMES["B6"]: 0, NAMES["B1"]: 0, NAMES["B3"]: 0, NAMES["B4"]: 0, NAMES["B2"]: 0,
- NAMES["B5"]: 1, NAMES["B7"]: 1}
+# ---- 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}
- 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}
+ 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 (moment 370 of the stepped run)
-UPTO = [i for i, a in enumerate(SORT_PATH) if a == NAMES["B4"]][10] + 1
-NOTES_370 = {0x4011bf: [("404030 ", HEAP), ("◂ ", FAINT), ("17", VELLUM)],
- 0x4011d6: [("404034 ", HEAP), ("◂ ", FAINT), ("5", VELLUM)],
- 0x4011d9: [("17", VELLUM), (" : ", FAINT), ("5", VELLUM), (" ", FAINT), ("zf", DIM), (" sf", DIM), (" of", DIM)],
- 0x4011db: [("taken", VELLUM), (" · reads zf sf of", FAINT)]}
+# 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 graph, two columns wide, beside the source whole."""
- gen.W, gen.H = 2900, 1800
+ """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()
- D.put(112)
src = open(HERE + "/../../anim/tools/sort.c").read().split("\n")
C.LX = 112
- C.source(g, 96, 22, src, 1, 12, [13, 14], "sort.c", 22)
+ 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 graph, two columns wide (1024 to 2816), at moment 370 of 465 in sort",
+ 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, 0x4011db, [0x4011d9, 0x4011d6, 0x4011cf], NOTES_370)
- graph(g, 1024, 96, 1792, "disassembly · sort", "its blocks · visits so far · the edges the run took",
- SORT_BL, SB[0], SORT_BASE, SORT_COLS, st, pitch=560, notes_w=30 * A)
+ 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)
@@ -415,9 +412,9 @@ def fold_unreached(bl, path, groups):
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 three boxes.
- The pc is at the `syscall` (mock 16's moment 4)."""
- gen.W, gen.H = 2000, 2000
+ """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)]),
@@ -427,11 +424,7 @@ def frame_open_map(name):
("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)
- cols = {a: 0 for a in bl}
- for n, ms in groups:
- cols[ms[0]] = 1
- st = {"blocks": {a: {"count": 1} for a in OPEN_PATH}, "edge_counts": Counter(zip(OPEN_PATH, OPEN_PATH[1:])),
- "edge_trail": list(reversed(list(zip(OPEN_PATH, OPEN_PATH[1:]))[1:4]))}
+ 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]))
@@ -440,10 +433,11 @@ def frame_open_map(name):
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 graph · 19 blocks, the run reached 8 so far; the 11 it never reached are "
- "folded into five boxes", 22, DIM, "sans")
- graph(g, 64, 96, 1872, "disassembly · open · libc.so.6", "no source · 19 blocks · folded: 11 never reached",
- bl, OPEN_PATH[0], OPEN_BASE + L, cols, st, pitch=880, gap=40, notes_w=18 * A)
+ 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)
@@ -457,127 +451,525 @@ REV_PATH = [R0, R2, R1, R2, R1, R2, R1, R2, R3]
def frame_strip(name):
- """Mock 24: reverse's loop, four instants: the condition about to be decided; its edge taken, the mark
- travelling it; the back edge's turn, the count going up; the way out."""
- gen.W, gen.H = 3840, 1120
+ """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()
- cols = {R0: 0, R1: 0, R2: 0, R3: 0}
inst = [
- ("1", "the condition", "cur at jne, the compare's chips framed; the second turn", 4, 0x4011ce,
- {0x4011c9: [("1004070", HEAP), (" : ", FAINT), ("0", VELLUM), (" ", FAINT), ("zf", DIM)],
- 0x4011ce: [("taken", VELLUM), (" · reads zf", FAINT)]}, None),
- ("2", "the edge taken", "the edge lit gold, the mark on it, halfway", 5, None, {}, (R2, R1)),
- ("3", "the loop's turn", "the back edge climbs, the mark on it; its count struck: the second turn", 6, None, {}, (R1, R2)),
- ("4", "the way out", "not taken: down to the exit, landed", 9, 0x4011d0, {}, None),
+ ("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, notes, moving) in enumerate(inst):
- dx = 64 + k * 940
- g.o.append(f'<g transform="translate({dx - 64},0)">')
- g.t(64, 40, num, 28, GOLD, "sansb")
- g.t(92, 40, title, 28, VELLUM, "sansm")
- g.t(64, 70, sub, 20, FAINT, "sans")
- cnt, ec, trail = run_state(REV_BL, REV_PATH, upto, REV_BASE)
+ 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, notes=notes, cur_line=20 if ca == R2 else 21 if ca == R1 else 26)
- if moving == (R1, R2):
- st["struck_count"] = moving
- pos, ats, hgt = graph(g, 64, 96, 900, "disassembly · reverse", "", REV_BL, R0, REV_BASE, cols, st, pitch=470,
- gap=48, notes_w=18 * A)
- if moving: # the mark between blocks: the gold plaque halfway along the edge it takes
- pts = st["paths"][moving]
- seg = [(p, q, abs(q[0] - p[0]) + abs(q[1] - p[1])) for p, q in zip(pts, pts[1:])]
- half, run = sum(l for _, _, l in seg) / 2, 0
- for p, q, l in seg:
- if run + l >= half:
- f = (half - run) / l
- mx, my = p[0] + (q[0] - p[0]) * f, p[1] + (q[1] - p[1]) * f
- break
- run += l
- g.rect(mx - 12, my - 12, 24, 24, GOLD)
- up = q[1] < p[1]
- g.path(f"M{mx},{my + (-6 if up else 6)} l-6,{8 if up else -8} h12 Z", fill=gen.INK)
- g.o.append("</g>")
+ 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 working frame: a `blocks` lens, the graph as shapes, its view the disassembly -----------------------
-def silhouette(g, x, y, w, h, bl, entry, base, cols, st, title):
- """The graph without its text: a block a box 24 high, as wide as its rows (8 a row, 72 at least), its offset
- and visits; the pc's gold; edges and lanes as on the map, small."""
+# ---- 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, 300, 12)
+ 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)
+ 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")
- 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 + 8, b(by), "+%x" % (a - base), S, VELLUM if s_.get("count") else FAINT, MONO)
+ 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] - 8, b(by), "×%d" % s_["count"], S, DIM, MONO, "end")
- return pos
+ 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
+ put the travelling mark on it."""
+ def __init__(self, x, y):
+ self.d, self.pts = f"M{x:.1f},{y:.1f}", [(x, y)]
+
+ def to(self, x, y):
+ self.d += f" L{x:.1f},{y:.1f}"
+ self.pts.append((x, y))
+ return self
+
+ def arc(self, x, y, r, cw):
+ """A circular arc of radius r to (x, y), clockwise on the screen when cw."""
+ x0, y0 = self.pts[-1]
+ self.d += f" A{r:.1f},{r:.1f} 0 0 {1 if cw else 0} {x:.1f},{y:.1f}"
+ cl = math.hypot(x - x0, y - y0)
+ ux, uy = (x - x0) / cl, (y - y0) / cl
+ hh = math.sqrt(max(r * r - cl * cl / 4, 0))
+ nx, ny = (-uy, ux) if cw else (uy, -ux)
+ cx, cy = (x0 + x) / 2 + nx * hh, (y0 + y) / 2 + ny * hh
+ a0, a1 = math.atan2(y0 - cy, x0 - cx), math.atan2(y - cy, x - cx)
+ if cw and a1 < a0:
+ a1 += 2 * math.pi
+ if not cw and a1 > a0:
+ a1 -= 2 * math.pi
+ for k in range(1, 17):
+ a = a0 + (a1 - a0) * k / 16
+ self.pts.append((cx + r * math.cos(a), cy + r * math.sin(a)))
+ return self
+
+ def length(self):
+ return sum(math.hypot(q[0] - p[0], q[1] - p[1]) for p, q in zip(self.pts, self.pts[1:]))
+
+ def at(self, f):
+ """The point a fraction f along, and the unit direction there."""
+ goal, run = self.length() * f, 0
+ for p, q in zip(self.pts, self.pts[1:]):
+ l_ = math.hypot(q[0] - p[0], q[1] - p[1])
+ if l_ and run + l_ >= goal:
+ k = (goal - run) / l_
+ return (p[0] + (q[0] - p[0]) * k, p[1] + (q[1] - p[1]) * k), ((q[0] - p[0]) / l_, (q[1] - p[1]) / l_)
+ run += l_
+ p, q = self.pts[-2], self.pts[-1]
+ l_ = math.hypot(q[0] - p[0], q[1] - p[1])
+ return q, ((q[0] - p[0]) / l_, (q[1] - p[1]) / l_)
+
+
+def draw_path(g, p, ink, sw, dash=None, hl=8, hw=8):
+ """The edge and its head on its last point; the stroke stops at the head's base (its last leg is straight)."""
+ (x1, y1), (x2, y2) = p.pts[-2], p.pts[-1]
+ l_ = math.hypot(x2 - x1, y2 - y1)
+ ux, uy = (x2 - x1) / l_, (y2 - y1) / l_
+ d = p.d[:p.d.rfind(" L")] + f" L{x2 - ux * (hl - 1):.1f},{y2 - uy * (hl - 1):.1f}"
+ g.path(d, ink, sw, dash=dash, join="round", cap="butt")
+ 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'<rect x="{x + sw / 2:.1f}" y="{y + sw / 2:.1f}" width="{w - sw:.1f}" height="{24 - sw:.1f}" '
+ f'rx="{12 - sw / 2:.1f}" fill="{fill}" stroke="{stroke}" stroke-width="{sw}"')
+ g.o.append(a + (f' stroke-dasharray="{dash}"' if dash else "") + "/>")
-def frame_lens(name):
- """Mock 25: sort at moment 370 in the working frame with the `blocks` lens: its drawing the graph as shapes,
- its view the disassembly round the pc (moved from the program column, which is the source's alone)."""
- gen.W, gen.H = 1920, 1080
+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)
+ g.rect(mx - 11, my - 11, 22, 22, ink)
+ gen.head_tri(g, mx + ux * 6, my + uy * 6, ux, uy, gen.INK, 12, 10)
+
+
+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."""
+ 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
+ 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)}
+ 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}
+ 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]
+ 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))
+ s, e = a0, a1
+ while inside(a, *pt(s)):
+ s += 0.005
+ while inside(t, *pt(e)):
+ e -= 0.005
+ p = Path(*pt(s))
+ p.arc(*pt(e), rr, 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 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)
+
+
+def draw_arc_head(g, p, ink, sw, dash):
+ """An arc, its stroke ending where its head begins, the head on the arc's tangent."""
+ pts, run, cut = p.pts, 0, 7
+ k = len(pts) - 1
+ while k > 0 and run < cut:
+ run += math.hypot(pts[k][0] - pts[k - 1][0], pts[k][1] - pts[k - 1][1])
+ k -= 1
+ d = "M%.1f,%.1f " % pts[0] + " ".join("L%.1f,%.1f" % q for q in pts[1:k + 1])
+ g.path(d, ink, sw, dash=dash, join="round")
+ (x1, y1), (x2, y2) = pts[-2], pts[-1]
+ l_ = math.hypot(x2 - x1, y2 - y1)
+ 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
g = Svg()
- st = sort_state(UPTO, 0x4011db, [0x4011d9, 0x4011d6, 0x4011cf], NOTES_370)
- pos = silhouette(g, 64, 48, 880, 296, SORT_BL, SB[0], SORT_BASE, {a: c for a, c in SORT_COLS.items()}, st,
- "the blocks of sort")
- # its view: the disassembly, seven rows round the pc, the block's rows bracketed as the drawing's gold box
- C.LX, C.CW = 976, 880
- rows = [(a, ln, mn, [(t, CODE)] if t and mn.startswith("j") else [(ops, VELLUM)],
- "cur" if a == 0x4011db else {0x4011d9: "trail0", 0x4011d6: "trail1", 0x4011cf: "trail2"}.get(a),
- ("runs", NOTES_370[a]) if a in NOTES_370 else None)
- for a, ln, mn, ops, t, callee in SORT if 0x4011c7 <= a <= 0x4011e1] # seven rows: the view's
- C.disasm(g, 48, rows, "sort · +84 to +a1", 12)
- C.LX, C.CW = 64, 880
- # the program column: the source alone
- src = open(HERE + "/../../anim/tools/sort.c").read().split("\n")
- C.source(g, 356, 21, src, 1, 12, [14, 13], "sort.c", 22)
- # registers and the stack, moment 370
- S_, H_ = STACK, HEAP
- E = [(0x7fffffffed00, S_), (0x7fffffffedb0, S_), (0x7fffffffee10, S_)]
- regs = [("rax", [], ("int", 5)), ("rbx", [], ("int", 0)), ("rcx", [], ("int", 0x10)), ("rdx", [], ("int", 0x11)),
- ("rsi", [(0x404034, DATA)], ("int", 0x1f0000001a)), ("rdi", [(0x404030, DATA)], ("int", 0x1a00000005)),
- ("rbp", [(0x7fffffffecf0, S_)] + E, ("int", 0)), ("rsp", [(0x7fffffffecd8, S_)], ("int", 0x800000000)),
- ("r8", [(0x7ffff7e19680, DATA)], None), ("r9", [(0x7ffff7e1afa0, DATA)], None),
- ("r10", [(0x7fffffffea60, S_)], ("int", 0)), ("r11", [(0x7ffff7ffca90, DATA)], ("int", 0x786843bb9f54c5c1)),
- ("r12", [(0x7fffffffee38, S_), (0x7fffffffefea, S_)], ("str", "./sort")), ("r13", [], ("int", 1)),
- ("r14", [(0x7ffff7ffd000, DATA), (0x7ffff7ffe3c0, DATA)], ("int", 0)),
- ("r15", [(0x403e10, DATA), (0x4010e0, CODE, "__do_global_dtors_aux")], None),
- ("rip", [(0x4011db, CODE, "sort+152")], None)]
- flags = [("CF", 0, 0), ("PF", 1, 0), ("AF", 1, 0), ("ZF", 0, 0), ("SF", 0, 0), ("IF", 1, 0), ("DF", 0, 0), ("OF", 0, 0)]
- C.RX = 976
- C.registers(g, 260, regs, flags, {"rax": {0: "tick"}, "rdx": {0: "tick"}})
- C.stack(g, 712, [(0x7fffffffecd8, ["rsp"], [], ("int", 0x800000000)), (0x7fffffffece0, [], [], ("int", 0)),
- (0x7fffffffece8, [], [], ("int", 0x400000006)), (0x7fffffffecf0, ["rbp"], E, ("int", 0)),
- (0x7fffffffecf8, [], [(0x4011ff, CODE, "main+14")], None),
- (0x7fffffffed00, [], E[1:], ("int", 0))],
- [("sort(8)", 0, 4)], rsp=0x7fffffffecd8,
- roles={2: ("i, j", VELLUM), 3: ("saved rbp", DIM)})
- C.clock(g, 370, 465)
- gen.caption(g, [[("The sixth pass, its third compare: ",), ("17 : 5", "mono"), (", so ",), ("jg", "mono"),
- (" goes back to the swap.",)],
- [("The swap has run 5 times so far; the outer loop has turned 5.",)]])
+ 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")
+
+ def veil(x, y, w, h):
+ g.o.append(f'<rect x="{x}" y="{y}" width="{w}" height="{h}" fill="{PAGE}" opacity="0.6"/>')
+
+ def label(x, y, key, title, sub):
+ g.t(x, y, key, 28, GOLD if key == "4" else BRIGHT, "sansb")
+ g.t(x + 30, y, title, 28, VELLUM, "sansm")
+ g.t(x, y + 28, sub, 18, FAINT, "sans")
+ 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)
+ 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")
g.save(name)
if __name__ == "__main__":
- assert len(SORT_BL) == 8 and len(REV_BL) == 4, (len(SORT_BL), len(REV_BL))
- assert Counter(SORT_PATH)[NAMES["B4"]] == 17 and Counter(SORT_PATH)[NAMES["B2"]] == 10
+ 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]
frame_sort_map("22-graph-sort")
frame_open_map("23-graph-open")
frame_strip("24-graph-strip")
- frame_lens("25-blocks-lens")
+ frame_forms("43-graph-forms")