diff options
Diffstat (limited to 'design/mock/graph.py')
| -rw-r--r-- | design/mock/graph.py | 583 |
1 files changed, 583 insertions, 0 deletions
diff --git a/design/mock/graph.py b/design/mock/graph.py new file mode 100644 index 0000000..e9b8f2b --- /dev/null +++ b/design/mock/graph.py @@ -0,0 +1,583 @@ +#!/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 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) + 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>") + 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") |
