1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
|
#!/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, 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.
Data: sort as the scene builds it (clang -O0, anim/build.zig, less the instrumentation's calls): sort-clang.dis
(objdump -dl), its path from `ztrace record --by insn --from sort` (the block leaders it hit), its stop in
sort-dbg.txt. reverse from anim/tools/list.c (cc -O0), reverse-O0.dis, its path from `ztrace dbg` stepped by
instruction. libc's `open` from objdump of
/usr/lib/libc.so.6 (libc-open.dis), its path the one mock 16's run took.
"""
import math
import re
from collections import Counter
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):
"""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 = []
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, radius=None):
"""Every edge: forward ones down from the bottom by the side their target lies on, along the gap's middle, down
into the target's top; one that would cross a block runs in the right channel; a back edge leaves the bottom,
goes out to its loop's lane on the left, climbs it and enters its header's head from the side: the one thing
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=radius or (4 if small else 8), hl=7 if small else 10, hw=8 if small else 10)
if n: # the loop's turns, on the lane under its turn into the header
if st.get("struck_count") == e: # the count is a value: written, it is struck
g.rect(lx + 1, hy + 8, 10 + len(str(n)) * 11, 20, C.SOFT)
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=radius or (4 if small else 8), hl=7 if small else 10, hw=8 if small else 10)
if n and kind != "jmp" and not small and len(outs) > 1:
g.t(sx + 8, y + h + 20, str(n), S, FAINT, MONO)
def 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 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
put the travelling mark on it."""
def __init__(self, x, y):
self.d, self.pts = f"M{x:.1f},{y:.1f}", [(x, y)]
def to(self, x, y):
self.d += f" L{x:.1f},{y:.1f}"
self.pts.append((x, y))
return self
def arc(self, x, y, r, cw):
"""A circular arc of radius r to (x, y), clockwise on the screen when cw."""
x0, y0 = self.pts[-1]
self.d += f" A{r:.1f},{r:.1f} 0 0 {1 if cw else 0} {x:.1f},{y:.1f}"
cl = math.hypot(x - x0, y - y0)
ux, uy = (x - x0) / cl, (y - y0) / cl
hh = math.sqrt(max(r * r - cl * cl / 4, 0))
nx, ny = (-uy, ux) if cw else (uy, -ux)
cx, cy = (x0 + x) / 2 + nx * hh, (y0 + y) / 2 + ny * hh
a0, a1 = math.atan2(y0 - cy, x0 - cx), math.atan2(y - cy, x - cx)
if cw and a1 < a0:
a1 += 2 * math.pi
if not cw and a1 > a0:
a1 -= 2 * math.pi
for k in range(1, 17):
a = a0 + (a1 - a0) * k / 16
self.pts.append((cx + r * math.cos(a), cy + r * math.sin(a)))
return self
def length(self):
return sum(math.hypot(q[0] - p[0], q[1] - p[1]) for p, q in zip(self.pts, self.pts[1:]))
def at(self, f):
"""The point a fraction f along, and the unit direction there."""
goal, run = self.length() * f, 0
for p, q in zip(self.pts, self.pts[1:]):
l_ = math.hypot(q[0] - p[0], q[1] - p[1])
if l_ and run + l_ >= goal:
k = (goal - run) / l_
return (p[0] + (q[0] - p[0]) * k, p[1] + (q[1] - p[1]) * k), ((q[0] - p[0]) / l_, (q[1] - p[1]) / l_)
run += l_
p, q = self.pts[-2], self.pts[-1]
l_ = math.hypot(q[0] - p[0], q[1] - p[1])
return q, ((q[0] - p[0]) / l_, (q[1] - p[1]) / l_)
def draw_path(g, p, ink, sw, dash=None, hl=8, hw=8):
"""The edge and its head on its last point; the stroke stops at the head's base (its last leg is straight)."""
(x1, y1), (x2, y2) = p.pts[-2], p.pts[-1]
l_ = math.hypot(x2 - x1, y2 - y1)
ux, uy = (x2 - x1) / l_, (y2 - y1) / l_
d = p.d[:p.d.rfind(" L")] + f" L{x2 - ux * (hl - 1):.1f},{y2 - uy * (hl - 1):.1f}"
g.path(d, ink, sw, dash=dash, join="round", cap="butt")
gen.head_tri(g, x2, y2, ux, uy, ink, hl, hw)
def pill(g, x, y, w, fill, stroke, sw=2, dash=None):
"""A block in the lens: a pill 24 high, its ends half circles."""
a = (f'<rect x="{x + sw / 2:.1f}" y="{y + sw / 2:.1f}" width="{w - sw:.1f}" height="{24 - sw:.1f}" '
f'rx="{12 - sw / 2:.1f}" fill="{fill}" stroke="{stroke}" stroke-width="{sw}"')
g.o.append(a + (f' stroke-dasharray="{dash}"' if dash else "") + "/>")
def mark(g, p, f, ink=GOLD):
"""The current mark travelling an edge: the gold plaque, its point the way it goes."""
(mx, my), (ux, uy) = p.at(f)
g.rect(mx - 11, my - 11, 22, 22, ink)
gen.head_tri(g, mx + ux * 6, my + uy * 6, ux, uy, gen.INK, 12, 10)
def edge_ink(e, st):
"""Never taken in the whole recording: rule, dashed. Not yet: rule. Taken: dim. The last three: the trail's
golds, the newest 3 units."""
trail = st.get("edge_trail", [])
if e in trail:
return TRAIL[trail.index(e)], 3 if trail.index(e) == 0 else 2, None
if st.get("edge_counts", {}).get(e, 0):
return DIM, 2, None
return RULE, 2, "12 8" if e in st.get("never", ()) else None
TRACK = dict(gap=40, arch=52, arch_step=36, dip=44, dip_step=16, stub=10, port=16)
def track_lens(g, x, y, w, h, bl, entry, base, st, title, note="its blocks · the visits · the path · the loops' turns",
tag=True, moving=None, struck=None):
"""The `blocks` lens: the function as a track across the band. A block a pill 24 high (its offset, its
visits; as long as its rows at 10 a row, the text's length at least) on one line, in the order they run;
an edge to the next block a straight run along the line; a loop's back edge an arch over its blocks, out of
its latch's top and down into its header's (the loop is the closed shape the arch and its floor make, its
turns at its centre); a forward jump past blocks a dip under them. Arches nest by level, 32 apart; dips 16.
moving: (edge, fraction): the mark on that edge. struck: an arch whose count is being struck.
Returns the edges' paths, and the line's y."""
lay, back, loops = loops_of(bl, entry)
order = track_order(bl, lay, loops)
idx = {a: i for i, a in enumerate(order)}
def text_of(a):
n = st["blocks"].get(a, {}).get("count", 0)
return "+%x" % (a - base), ("×%d" % n) if n else ""
pw = {a: max(24 + (len(text_of(a)[0]) + len(text_of(a)[1]) + 1) * A + 8, 10 * len(bl[a].rows) + 24) for a in order}
gap = TRACK["gap"]
total = sum(pw.values()) + gap * (len(order) - 1)
xs, xx = {}, x + (w - total) / 2
for a in order:
xs[a] = xx
xx += pw[a] + gap
arches = [(idx[t], idx[a], (a, t)) for a, t in back]
dips = [(idx[a], idx[t], (a, t)) for a in order for t, _ in bl[a].out
if (a, t) not in back and idx[t] > idx[a] + 1]
al, dl = spans_levels(arches), spans_levels(dips)
H = lambda k: TRACK["arch"] + TRACK["arch_step"] * (k - 1)
D = lambda k: TRACK["dip"] + TRACK["dip_step"] * (k - 1)
top, foot = H(max(al.values(), default=1)), D(max(dl.values(), default=1))
y0 = y + TAG + (h - TAG - top - foot) / 2 + top
if tag:
C.tag(g, x, y, w, h, title, focus=True, note=note)
paths = {}
s_, P = TRACK["stub"], TRACK["port"]
for a in order:
for t, kind in bl[a].out:
e = (a, t)
if e in back: # out of the latch's top, over, down into the header's
k, r = H(al[e]), H(al[e]) - 12 - s_
xa, xt = xs[a] + pw[a] - P, xs[t] + P
p = (Path(xa, y0 - 12).to(xa, y0 - 12 - s_).arc(xa - r, y0 - k, r, False).to(xt + r, y0 - k)
.arc(xt, y0 - 12 - s_, r, False).to(xt, y0 - 12))
elif idx[t] == idx[a] + 1: # to the next block: along the line
p = Path(xs[a] + pw[a], y0).to(xs[t], y0)
else: # past blocks: under them
k, r = D(dl[e]), D(dl[e]) - 12 - s_
xa, xt = xs[a] + pw[a] - P, xs[t] + P
p = (Path(xa, y0 + 12).to(xa, y0 + 12 + s_).arc(xa + r, y0 + k, r, False).to(xt - r, y0 + k)
.arc(xt, y0 + 12 + s_, r, False).to(xt, y0 + 12))
paths[e] = p
for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())): # the trail on top
ink, sw, dash = edge_ink(e, st)
draw_path(g, p, ink, sw, dash)
for a, t in back: # each loop's turns, at its centre: under its arch, over what it holds
e = (a, t)
n = st.get("edge_counts", {}).get(e, 0)
inner = max([H(al[o]) for o in al if al[o] < al[e]] + [12])
cx, cy = (xs[t] + xs[a] + pw[a]) / 2, y0 - inner - (H(al[e]) - inner) * 0.4 # clear of the mark on the arch
s = "×%d" % n
if struck == e:
g.rect(cx - len(s) * A / 2 - 5, cy - 11, len(s) * A + 10, 22, C.SOFT)
g.t(cx, cy + 7, s, S, BRIGHT, BOLD, "middle")
elif n:
g.t(cx, cy + 7, s, S, DIM, MONO, "middle")
for a in order:
s0 = st["blocks"].get(a, {})
n, cur = s0.get("count", 0), s0.get("cur") and not moving
pill(g, xs[a], y0 - 12, pw[a], RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2)
off, cnt = text_of(a)
g.t(xs[a] + 12, b(y0 - 12), off, S, VELLUM if n else FAINT, MONO)
if cnt:
g.t(xs[a] + pw[a] - 12, b(y0 - 12), cnt, S, DIM, MONO, "end")
for i, r_ in enumerate(bl[a].rows): # a call that comes back: a hook under the pill, out and in again
if r_[2] == "call" and r_[5] and r_[5] not in NORETURN:
cx = xs[a] + 16 + (pw[a] - 48) * i / max(len(bl[a].rows) - 1, 1)
g.path(f"M{cx:.1f},{y0 + 12:.1f} v6 a5,5 0 0 0 10,0 v-6", DIM if n else RULE, 2)
g.t(cx + 16, y0 + 34, r_[5], S, VELLUM if n else FAINT, MONO)
if moving:
mark(g, paths[moving[0]], moving[1])
return paths, y0, xs, pw
def track_map(g, x, y, w, bl, entry, base, st, title, note, notes_w=0):
"""The map's graph: the same track run down, a block a card that carries its rows (`draw_block`), the cards
in the line's order on one spine 40 in from their left; a back edge leaves its latch's left side and climbs
a lane on the left, 48 apart, into its header's head; a forward jump past cards leaves the source's right
side and goes down a channel on the right into its target's head. Every bend a quarter circle of 16; cards 10
apart. The turns in the lobe between a lane and what it holds; a conditional's two ways counted in words in
its jump's row (`taken 5 · not 6`), where the pc's block has the jump's own annotation.
Returns the panel's height and each card's rows' y."""
lay, back, loops = loops_of(bl, entry)
order = track_order(bl, lay, loops)
idx = {a: i for i, a in enumerate(order)}
fold = lambda a: hasattr(bl[a], "folded")
split_w = lambda a: (X_OPS + max(len("%x" % (bl[a].rows[-1][4] or 0)) + 2, 10) * A + 17 * A
if len(bl[a].out) == 2 and st["blocks"].get(a, {}).get("count")
and not st["blocks"].get(a, {}).get("cur") else 0)
widths = {a: 520 if fold(a) else max(block_w(bl[a], base, notes_w if st["blocks"].get(a, {}).get("notes") else 0),
split_w(a)) for a in order}
heights = {a: TAG + (ROW if fold(a) else len(fold_rows(bl[a].rows, st["blocks"].get(a, {}).get("cur"))) * ROW) + PAD
for a in order}
arches = [(idx[t], idx[a], (a, t)) for a, t in back]
dips = [(idx[a], idx[t], (a, t)) for a in order for t, _ in bl[a].out
if (a, t) not in back and idx[t] > idx[a] + 1]
al, dl = spans_levels(arches), spans_levels(dips)
cx0 = x + 24 + 48 * max(al.values(), default=0) + 12
ys, yy = {}, y + TAG + 8
for a in order:
ys[a] = yy
yy += heights[a] + 10
yy += 10 # room under the last card for the way out's bar
hook = lambda a: max([28 + len(r[5]) * A for r in bl[a].rows if r[2] == "call" and r[5]] + [0]) if not fold(a) else 0
chan = max(cx0 + widths[a] + hook(a) for a in order) + 24
hgt = yy - y
C.tag(g, x, y, w, hgt, title, focus=True, note=note)
R, spine = 16, cx0 + 40
paths = {}
for a in order:
for t, kind in bl[a].out:
e = (a, t)
ya, yt = ys[a] + heights[a] - 14, ys[t] + 12
if e in back:
L = cx0 - 48 * al[e]
p = (Path(cx0, ya).to(L + R, ya).arc(L, ya - R, R, True).to(L, yt + R).arc(L + R, yt, R, True)
.to(cx0, yt))
elif idx[t] == idx[a] + 1:
p = Path(spine, ys[a] + heights[a]).to(spine, ys[t])
else:
Cx = chan + 32 * (dl[e] - 1)
p = (Path(cx0 + widths[a], ya).to(Cx - R, ya).arc(Cx, ya + R, R, True).to(Cx, yt - R)
.arc(Cx - R, yt, R, True).to(cx0 + widths[t], yt))
paths[e] = p
for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())):
ink, sw, dash = edge_ink(e, st)
draw_path(g, p, ink, sw, dash, hl=10, hw=10)
counts = st.get("edge_counts", {})
for a, t in back: # the turns, in the lobe
e = (a, t)
n = counts.get(e, 0)
if n:
L = cx0 - 48 * al[e]
g.t(L + 24, (ys[t] + ys[a] + heights[a]) / 2 + 7, "×%d" % n, S, DIM, MONO, "middle")
ats = {}
for a in order:
s0 = dict(st["blocks"].get(a, {}))
if len(bl[a].out) == 2 and not fold(a) and s0.get("count"): # a conditional reached: its two ways counted
(t1, k1), (t2, k2) = bl[a].out
tk, nt = (t1, t2) if k1 == "taken" else (t2, t1)
s0["split"] = (counts.get((a, tk), 0), counts.get((a, nt), 0))
_, at = draw_block(g, cx0, ys[a], widths[a], bl[a], base, s0)
ats.update(at)
return hgt, ats, paths
# ---- rings: the comparison sheet's third form, each loop a circle its blocks sit on ----------------------------
RING_AT = {0x12: ("o", 180), 0x1e: ("o", 235), 0x24: ("o", 300), 0x5d: ("o", 25), 0x97: ("o", 80), 0x99: ("o", 130),
0x2f: ("i", 15), 0x56: ("i", 95), 0x5f: ("i", 185)}
def rings(g, x, y, w, h, st, title):
"""sort as rings: the outer loop a circle of 170, its blocks round it clockwise; the inner loop a circle of 92
inside it, touching it at its header; the way in and the way out as short tracks at the left; a loop's exit a
chord between the rings. Every edge an arc of its ring or a straight chord."""
C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits · the path · the loops' turns")
R, r = 170, 92
ox, oy = x + w / 2 + 120, y + TAG + 24 + R
t0 = math.radians(300)
ix, iy = ox + (R - r) * math.cos(t0), oy + (R - r) * math.sin(t0)
ring = {"o": (ox, oy, R), "i": (ix, iy, r)}
pos = {}
for off, (k, deg) in RING_AT.items():
cx, cy, rr = ring[k]
pos[O(off)] = (cx + rr * math.cos(math.radians(deg)), cy + rr * math.sin(math.radians(deg)))
pos[O(0x0)] = (ox - R - 170, oy)
pos[O(0xa7)] = (ox - R - 170, oy + 96)
texts = {a: ("+%x" % (a - SORT_BASE), "×%d" % st["blocks"][a]["count"] if st["blocks"][a]["count"] else "")
for a in SORT_BL}
pw = {a: 24 + (len(texts[a][0]) + len(texts[a][1]) + 1) * A + 8 for a in SORT_BL}
inside = lambda a, px, py: abs(px - pos[a][0]) < pw[a] / 2 + 4 and abs(py - pos[a][1]) < 16
def on_ring(a, t, k):
"""The arc of ring k from a's pill to t's, clockwise, cut where each pill ends."""
cx, cy, rr = ring[k]
a0 = math.atan2(pos[a][1] - cy, pos[a][0] - cx)
a1 = math.atan2(pos[t][1] - cy, pos[t][0] - cx)
while a1 <= a0:
a1 += 2 * math.pi
pt = lambda th: (cx + rr * math.cos(th), cy + rr * math.sin(th))
s, e = a0, a1
while inside(a, *pt(s)):
s += 0.005
while inside(t, *pt(e)):
e -= 0.005
p = Path(*pt(s))
p.arc(*pt(e), rr, True)
return p
paths = {}
for a in SORT_BL:
for t, kind in SORT_BL[a].out:
ka, kt = RING_AT.get(a - SORT_BASE, (None,))[0], RING_AT.get(t - SORT_BASE, (None,))[0]
if (a, t) == (O(0x0), O(0x12)):
p = Path(pos[a][0] + pw[a] / 2, oy).to(pos[t][0] - pw[t] / 2, oy)
elif (a, t) == (O(0x12), O(0xa7)):
sx = pos[a][0] - 20
p = (Path(sx, oy + 12).to(sx, oy + 40).arc(sx - 56, oy + 96, 56, True)
.to(pos[t][0] + pw[t] / 2, oy + 96))
elif ka and kt and ka == kt or (a - SORT_BASE, t - SORT_BASE) in ((0x24, 0x2f), (0x5f, 0x24)):
p = on_ring(a, t, "i" if (a - SORT_BASE, t - SORT_BASE) in ((0x24, 0x2f), (0x5f, 0x24)) else ka)
else: # between the rings, or across one: a chord
(ax, ay), (tx, ty) = pos[a], pos[t]
d = math.hypot(tx - ax, ty - ay)
ux, uy = (tx - ax) / d, (ty - ay) / d
s, e = 0, d
while inside(a, ax + ux * s, ay + uy * s):
s += 1
while inside(t, ax + ux * e, ay + uy * e):
e -= 1
p = Path(ax + ux * s, ay + uy * s).to(ax + ux * e, ay + uy * e)
paths[(a, t)] = p
for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())):
ink, sw, dash = edge_ink(e, st)
if len(p.pts) > 2: # an arc: its head on the tangent at its end
draw_arc_head(g, p, ink, sw, dash)
else:
draw_path(g, p, ink, sw, dash)
for (cx, cy, rr), e in ((ring["o"], (O(0x99), O(0x12))), (ring["i"], (O(0x5f), O(0x24)))):
n = st["edge_counts"].get(e, 0)
tx, ty = (cx, cy) if rr < R else (cx - 80, cy + 60)
g.t(tx, ty + 7, "×%d" % n, S, DIM, MONO, "middle")
for a in SORT_BL:
s0 = st["blocks"][a]
n, cur = s0.get("count", 0), s0.get("cur")
px, py = pos[a][0] - pw[a] / 2, pos[a][1] - 12
pill(g, px, py, pw[a], RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2)
g.t(px + 12, b(py), texts[a][0], S, VELLUM if n else FAINT, MONO)
if texts[a][1]:
g.t(px + pw[a] - 12, b(py), texts[a][1], S, DIM, MONO, "end")
sx, sy = pos[O(0x5f)][0] + 26, pos[O(0x5f)][1] - 12
g.path(f"M{sx:.1f},{sy:.1f} v-6 a5,5 0 0 1 10,0 v6", DIM, 2)
g.t(sx + 16, sy - 6, "swap", S, VELLUM, MONO)
def draw_arc_head(g, p, ink, sw, dash):
"""An arc, its stroke ending where its head begins, the head on the arc's tangent."""
pts, run, cut = p.pts, 0, 7
k = len(pts) - 1
while k > 0 and run < cut:
run += math.hypot(pts[k][0] - pts[k - 1][0], pts[k][1] - pts[k - 1][1])
k -= 1
d = "M%.1f,%.1f " % pts[0] + " ".join("L%.1f,%.1f" % q for q in pts[1:k + 1])
g.path(d, ink, sw, dash=dash, join="round")
(x1, y1), (x2, y2) = pts[-2], pts[-1]
l_ = math.hypot(x2 - x1, y2 - y1)
gen.head_tri(g, x2, y2, (x2 - x1) / l_, (y2 - y1) / l_, ink, 8, 8)
def frame_forms(name):
"""Mock 43: sort's graph four ways, at the same moment and at the lens's scale: the present form, its layers
rounded, rings, and the track (recommended), each in the box it is given and at the size it needs."""
gen.W, gen.H = 1920, 1600
g = Svg()
st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES)
g.t(64, 56, "sort's graph, four ways", 36, BRIGHT, "sansm")
g.t(64, 90, "The same moment in each (the 11th compare: 17 > 5, jne about to take the swap); the lens's scale, "
"mono 20. Veiled: what falls outside the box the frame gives the lens.", 20, DIM, "sans")
def veil(x, y, w, h):
g.o.append(f'<rect x="{x}" y="{y}" width="{w}" height="{h}" fill="{PAGE}" opacity="0.6"/>')
def label(x, y, key, title, sub):
g.t(x, y, key, 28, GOLD if key == "4" else BRIGHT, "sansb")
g.t(x + 30, y, title, 28, VELLUM, "sansm")
g.t(x, y + 28, sub, 18, FAINT, "sans")
cols = {a: 0 for a in SORT_BL}
cols[O(0xa7)] = 1
cols[O(0x5f)] = 1
for k, (key, title, sub, rounded) in enumerate((
("1", "present: layers, boxes, square lanes", "ten layers, 400 high: past the lens's 296 (veiled), so it "
"pans; a third of its width", False),
("2", "the same layers, rounded", "pills and round corners: smoother, and just as tall", True))):
x = 64 + k * 912
label(x, 152, key, title, sub)
_, hh = silhouette(Svg(), x, 212, 880, 999, SORT_BL, SB[0], SORT_BASE, cols, st, "", rounded, pitch=330)
silhouette(g, x, 212, 880, hh + 16, SORT_BL, SB[0], SORT_BASE, cols, st, "the blocks of sort", rounded, pitch=330)
veil(x - 2, 212 + 296, 884, hh + 16 - 296 + 2)
label(64, 704, "3", "rings", "each loop a circle its blocks sit on, the inner inside the outer: 420 high, "
"past the band's 200 (veiled)")
rings(g, 64, 764, 880, 420, st, "the blocks of sort")
veil(62, 764 + 200, 884, 222)
nx = 976
for i, (s, ink) in enumerate((
("What each costs", VELLUM),
("1 The tools' picture. Tall by nature: a layer a block,", DIM),
(" so it pans in a short pane, and leaves the width.", DIM),
("2 Rounding the corners does not change the shape.", DIM),
("3 The most circular, and a loop is a ring; but rings", DIM),
(" want a square pane, a loop's way out is a chord", DIM),
(" across them, and pills on its sides sit across it.", DIM),
("4 The track. A line of blocks as they run, each loop", VELLUM),
(" an arch over its own blocks: a closed shape, its", VELLUM),
(" turns at its centre; a jump past blocks a dip", VELLUM),
(" under them. Wide and short: 11 blocks in 1622", VELLUM),
(" by 150, whole. Its order is the disassembly's,", VELLUM),
(" which is under the source; run down, it is the", VELLUM),
(" map's column with its rows.", VELLUM))):
g.t(nx, 730 + i * 30, s, 22 if i == 0 else 20, ink, "sansm" if i == 0 else "sans")
label(64, 1220, "4", "the track: recommended", "the band across the frame, 1792 by 200: the whole graph, no pan")
paths, y0, xs, pw = track_lens(g, 64, 1280, 1792, 200, SORT_BL, SB[0], SORT_BASE, st, "the blocks of sort")
print("43: the track is %d wide" % (max(xs[a] + pw[a] for a in xs) - min(xs.values())))
g.t(64, 1530, "Ink in 3 and 4: never taken in the whole run, dashed rule (j > 0 failing); not yet, rule (the "
"way out); taken, dim; the last three, the trail's golds. 1 and 2 keep the layers' ink: never taken, rule.",
18, DIM, "sans")
g.save(name)
if __name__ == "__main__":
assert len(SORT_BL) == 11 and len(REV_BL) == 4, (len(SORT_BL), len(REV_BL))
assert Counter(SORT_PATH)[O(0x56)] == 17 and Counter(SORT_PATH)[O(0x5f)] == 10
lay_, back_, loops_ = loops_of(SORT_BL, SB[0])
assert [a - SORT_BASE for a in track_order(SORT_BL, lay_, loops_)] == \
[0x0, 0x12, 0x1e, 0x24, 0x2f, 0x56, 0x5f, 0x5d, 0x97, 0x99, 0xa7]
frame_sort_map("22-graph-sort")
frame_open_map("23-graph-open")
frame_strip("24-graph-strip")
frame_forms("43-graph-forms")
|