#!/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) 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. """ import re from collections import Counter import gen import dense as D import context as C from context import (PAGE, RAISED, RULE, VELLUM, BRIGHT, DIM, FAINT, GOLD, KW, CODE, HEAP, STACK, DATA, A, S, ROW, TAG, PAD, MONO, BOLD, b, ph, mix, Svg) HERE = __file__.rsplit("/", 1)[0] NORETURN = {"__stack_chk_fail", "__syscall_do_cancel"} TRAIL = gen.TRAIL def read_dis(name, lines=True): """(address, line, mnemonic, operands, target) from objdump -d[l] -M intel.""" out, line = [], None for l in open(f"{HERE}/{name}"): m = re.search(r"\.c:(\d+)", l) if m and not re.match(r"^\s+[0-9a-f]+:", l): line = int(m.group(1)) continue m = re.match(r"^\s+([0-9a-f]+):\s+(\S+)\s*(.*)$", l) if not m: continue mnem, ops = m.group(2), m.group(3) if mnem in ("addr32", "bnd", "notrack") and ops: # a prefix: the instruction is what follows it mnem, _, ops = ops.partition(" ") ops = ops.strip() tgt = re.match(r"([0-9a-f]+) <([^>]+)>", ops) callee = tgt.group(2) if tgt else None ops = re.sub(r"\s*<[^>]+>", "", re.sub(r"\s+#.*", "", ops)).strip() mn, ops = D.conv(mnem, ops) out.append((int(m.group(1), 16), line if lines else None, mn, ops, int(tgt.group(1), 16) if tgt else None, callee)) return out class Block: def __init__(self, name, rows): self.name, self.rows = name, rows self.a = rows[0][0] self.out = [] # (target name, kind): taken, fall, jmp self.ret = rows[-1][2] == "ret" def blocks(insns, base): """Basic blocks: a leader at the entry, at every jump's target and after every jump, ret or call that does not return. Padding (nops after a jump) is left out. Names are offsets: +5f.""" lo, hi = insns[0][0], insns[-1][0] lead = {lo} for i, (a, ln, mn, ops, t, callee) in enumerate(insns): ends = mn.startswith("j") or mn == "ret" or (mn == "call" and callee in NORETURN) if ends and i + 1 < len(insns): lead.add(insns[i + 1][0]) if mn.startswith("j") and t and lo <= t <= hi: lead.add(t) out, cur = {}, [] for r in insns: if r[0] in lead and cur: out[cur[0][0]] = cur cur = [] cur.append(r) out[cur[0][0]] = cur bl = {} for a, rows in out.items(): if all(r[2] in ("nop", "xchg") for r in rows): continue # padding between functions' paths: not a block bl[a] = Block("+%x" % (a - base), rows) order = sorted(bl) for i, a in enumerate(order): last = bl[a].rows[-1] nxt = bl[a].rows[-1][0] + 1 nxt = next((x for x in order if x > a), None) mn, t, callee = last[2], last[4], last[5] if mn == "jmp": bl[a].out = [(t, "jmp")] elif mn.startswith("j"): bl[a].out = [(t, "taken"), (nxt, "fall")] elif mn == "ret" or (mn == "call" and callee in NORETURN): bl[a].out = [] else: bl[a].out = [(nxt, "fall")] bl[a].out = [(x, k) for x, k in bl[a].out if x in bl] return bl def layers(bl, entry): """Back edges by a depth-first walk from the entry; layers by the longest path over the rest; a block that returns in the last layer.""" back, state = set(), {} def walk(a): state[a] = 1 for t, k in bl[a].out: if state.get(t) == 1: back.add((a, t)) elif t not in state: walk(t) state[a] = 2 walk(entry) lay = {a: 0 for a in bl} for _ in bl: for a in bl: for t, k in bl[a].out: if (a, t) not in back: lay[t] = max(lay[t], lay[a] + 1) last = max(lay.values()) for a in bl: if bl[a].ret: lay[a] = last + (0 if all(lay[x] < last or bl[x].ret for x in bl) else 1) 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): return max(300, X_OPS + max(len(r[3]) for r in blk.rows) * 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) 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 = [] for p in pts: if q and abs(p[0] - q[-1][0]) < 0.5 and abs(p[1] - q[-1][1]) < 0.5: continue if len(q) >= 2 and (abs(q[-2][0] - q[-1][0]) < 0.5 and abs(q[-1][0] - p[0]) < 0.5 or abs(q[-2][1] - q[-1][1]) < 0.5 and abs(q[-1][1] - p[1]) < 0.5): q[-1] = p continue q.append(p) gen.arrow(g, q, *a, **k) def place(bl, lay, cols, widths, heights, x0, y0, pitch, gap): """Each block at its column (a scene's layout, by the rule in the catalogue) and its layer.""" nl = max(lay.values()) + 1 lh = [max([heights[a] for a in bl if lay[a] == k] or [0]) for k in range(nl)] ly = [y0] for k in range(1, nl): ly.append(ly[-1] + lh[k - 1] + gap) pos = {a: (x0 + cols[a] * pitch, ly[lay[a]]) for a in bl} return pos, lh, ly def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x, small=False): """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.""" sw0 = 2 trail = st.get("edge_trail", []) counts = st.get("edge_counts", {}) backs = sorted([(a, t) for a, t in back], key=lambda e: -(lay[e[0]] - lay[e[1]])) lane = {e: lane_x0 + i * (10 if small else 16) for i, e in enumerate(backs)} inc = {} for a in bl: for t, k in bl[a].out: if (a, t) not in back: inc.setdefault(t, []).append(a) track = {} for a in sorted(bl, key=lambda a: (lay[a], pos[a][0])): x, y = pos[a] w, h = widths[a], heights[a] outs = bl[a].out for t, kind in outs: e = (a, t) n = counts.get(e, 0) ink = TRAIL[trail.index(e)] if e in trail else DIM if n else RULE sw = 3 if trail and e == trail[0] else sw0 tx, ty = pos[t] tw_ = widths[t] if e in back: lx = lane[e] k = track.get(lay[a], 0) track[lay[a]] = k + 1 by = ly[lay[a]] + lh[lay[a]] + (8 if small else 14) + k * 8 sx = x + (16 if small else 40) 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) 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) g.t(lx + 5, hy + 22, "×%d" % n, 18, BRIGHT, "sansb") else: g.t(lx + 5, hy + 22, "×%d" % n, 18, FAINT, "sans") continue # the side the target lies on picks the port srcs = sorted(inc.get(t, []), key=lambda s_: pos[s_][0]) slot = srcs.index(a) tx_ = tx + tw_ / 2 + (slot - (len(srcs) - 1) / 2) * (16 if small else 48) crosses = any(lay[a] < lay[o] < lay[t] and pos[o][0] - 8 < tx_ < pos[o][0] + widths[o] + 8 for o in bl) side = 1 if crosses else (tx + tw_ / 2) - (x + w / 2) # the channel is on the right sx = x + w / 2 if abs(side) < w / 2 - 40 and not crosses else ( x + w - (16 if small else 40) if side > 0 else x + (16 if small else 40)) gy = ly[lay[a]] + lh[lay[a]] + gap / 2 + track.get(("f", lay[a]), 0) * 6 track[("f", lay[a])] = track.get(("f", lay[a]), 0) + 1 between = [o for o in bl if lay[a] < lay[o] < lay[t] and pos[o][0] - 8 < tx_ < pos[o][0] + widths[o] + 8] if between: # it would cross a block: the right channel gy2 = ly[lay[t]] - gap / 2 pts = [(sx, y + h), (sx, gy), (channel_x, gy), (channel_x, gy2), (tx_, gy2), (tx_, ty)] 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) 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] cnt = Counter(p) ec = Counter(zip(p, p[1:])) trail = list(reversed(list(zip(p, p[1:]))[-3:])) 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} 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} # 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)]} 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 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.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", 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) 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 three boxes. The pc is at the `syscall` (mock 16's moment 4).""" gen.W, gen.H = 2000, 2000 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) 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"][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 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.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, 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 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), ] for k, (num, title, sub, upto, cur, notes, moving) in enumerate(inst): dx = 64 + k * 940 g.o.append(f'') 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) 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.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.""" 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) 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) 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 s_.get("count"): g.t(bx + widths[a] - 8, b(by), "×%d" % s_["count"], S, DIM, MONO, "end") return pos 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 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.",)]]) 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 frame_sort_map("22-graph-sort") frame_open_map("23-graph-open") frame_strip("24-graph-strip") frame_lens("25-blocks-lens")