diff options
Diffstat (limited to 'design/mock/graph.py')
| -rw-r--r-- | design/mock/graph.py | 722 |
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") |
