diff options
Diffstat (limited to 'design/mock/graph.py')
| -rw-r--r-- | design/mock/graph.py | 1023 |
1 files changed, 403 insertions, 620 deletions
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'<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 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 + return RULE, 2, None -TRACK = dict(gap=40, arch=52, arch_step=36, dip=44, dip_step=16, stub=10, port=16) +def pill(g, x, y, w, fill, stroke, sw=2, dash=None): + """A block: 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 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 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 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 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 -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 +# ---- 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="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 -# ---- 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 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 -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)} + +# ---- 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 veil(x, y, w, h): - g.o.append(f'<rect x="{x}" y="{y}" width="{w}" height="{h}" fill="{PAGE}" opacity="0.6"/>') + +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 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'<rect x="{x}" y="{y}" width="{w}" height="{h}" fill="{PAGE}" opacity="0.6"/>') + 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") |
