Fixed 146-instruction reverse breadth-first-search Word-RAM program
DefinitionDirKECC1549_Main_ReverseSearchCodeThis defines a concrete multiplication Word-RAM algorithm with 146 instructions and polynomial capacity
The code implements reverse breadth-first search on the published graph layout. With B=n+2m+3, it uses the designated parent cells 6B+v, visited flags at 8B+64+v, and a queue at 10B+64+i. It initializes every parent to the vertex itself and every visited flag to zero, marks and enqueues the root, and scans each dequeued vertex's incoming-adjacency interval. A first discovery marks the predecessor, records its parent, and enqueues it.
Because the machine has no separate register file, the code first saves original cells 1 through 16 at 16B+64 through 16B+79. It reconstructs and saves original cell 0 at 16B+80. While using those cells as registers, graph reads at addresses 1 through 16 read their saved copies. The epilogue restores all cells 0 through 16 before halting.
The instruction list and its numeric jump targets are explicit. This definition contains no correctness, termination, or running-time assumption. Those properties are separate theorem obligations.
import Definitions.Def_WordRAM_Complexity_Programs
set_option autoImplicit false
namespace DirKECC1549.Main
/-- Fixed reverse breadth-first search. Registers 0–16 are spilled and restored.
The search uses parent cells 6B+v, visited cells 8B+64+v, queue cells 10B+64+i,
and a spill area starting at 16B+64, where B = n+2m+3.
Registers: 1=n, 2=spill base, 3=m, 4=B, 5=root, 6=parent base, 7=visited base,
8=queue base, 9=head, 10=tail, 11=current vertex, 12=scan index, 13=scan end,
14=edge/predecessor, 15=visited flag. Register 0 is the indirect-address pointer.
Graph reads at addresses 1–16 use saved words while the registers are live. -/
def reverseSearchAlgorithm : WordRAM.Complexity.Algorithm .multiplication where
capacityCoefficient := 64
capacityDegree := 1
code := [
-- entry:
-- Begin the spill prologue; input cells 0 and 1 contain n and m.
.binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 1)), -- 0
.binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 1)), -- 1
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 3), -- 2
.binary .shl (.direct 0) (.memory (.direct 0)) (.immediate 4), -- 3
-- Register 0 now points to spill base S = 16B+64.
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 64), -- 4
-- Save original cell 1 at S+0.
.copy (.indirect 0) (.memory (.direct 1)), -- 5
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 6
-- Save original cell 2 at S+1.
.copy (.indirect 0) (.memory (.direct 2)), -- 7
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 8
-- Save original cell 3 at S+2.
.copy (.indirect 0) (.memory (.direct 3)), -- 9
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 10
-- Save original cell 4 at S+3.
.copy (.indirect 0) (.memory (.direct 4)), -- 11
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 12
-- Save original cell 5 at S+4.
.copy (.indirect 0) (.memory (.direct 5)), -- 13
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 14
-- Save original cell 6 at S+5.
.copy (.indirect 0) (.memory (.direct 6)), -- 15
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 16
-- Save original cell 7 at S+6.
.copy (.indirect 0) (.memory (.direct 7)), -- 17
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 18
-- Save original cell 8 at S+7.
.copy (.indirect 0) (.memory (.direct 8)), -- 19
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 20
-- Save original cell 9 at S+8.
.copy (.indirect 0) (.memory (.direct 9)), -- 21
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 22
-- Save original cell 10 at S+9.
.copy (.indirect 0) (.memory (.direct 10)), -- 23
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 24
-- Save original cell 11 at S+10.
.copy (.indirect 0) (.memory (.direct 11)), -- 25
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 26
-- Save original cell 12 at S+11.
.copy (.indirect 0) (.memory (.direct 12)), -- 27
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 28
-- Save original cell 13 at S+12.
.copy (.indirect 0) (.memory (.direct 13)), -- 29
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 30
-- Save original cell 14 at S+13.
.copy (.indirect 0) (.memory (.direct 14)), -- 31
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 32
-- Save original cell 15 at S+14.
.copy (.indirect 0) (.memory (.direct 15)), -- 33
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 34
-- Save original cell 16 at S+15.
.copy (.indirect 0) (.memory (.direct 16)), -- 35
.copy (.direct 2) (.memory (.direct 0)), -- 36
-- Register 2 holds S throughout the search.
.binary .sub (.direct 2) (.memory (.direct 2)) (.immediate 15), -- 37
-- Recover m from its saved word.
.copy (.direct 3) (.memory (.indirect 2)), -- 38
.copy (.direct 4) (.memory (.direct 0)), -- 39
.binary .sub (.direct 4) (.memory (.direct 4)) (.immediate 79), -- 40
-- Recover B from S+15 = 16B+79.
.binary .shr (.direct 4) (.memory (.direct 4)) (.immediate 4), -- 41
.copy (.direct 1) (.memory (.direct 4)), -- 42
.binary .sub (.direct 1) (.memory (.direct 1)) (.memory (.direct 3)), -- 43
.binary .sub (.direct 1) (.memory (.direct 1)) (.memory (.direct 3)), -- 44
-- Recover n from B-2m-3.
.binary .sub (.direct 1) (.memory (.direct 1)) (.immediate 3), -- 45
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 46
-- Save original cell 0 at S+16 for the epilogue.
.copy (.indirect 0) (.memory (.direct 1)), -- 47
.binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 5), -- 48
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 2), -- 49
-- Read root r from parameter cell 5B+2, which is above register 16.
.copy (.direct 5) (.memory (.indirect 0)), -- 50
-- Parent-array base 6B.
.binary (.mul rfl) (.direct 6) (.memory (.direct 4)) (.immediate 6), -- 51
.binary (.mul rfl) (.direct 7) (.memory (.direct 4)) (.immediate 8), -- 52
-- Visited-array base 8B+64.
.binary .add (.direct 7) (.memory (.direct 7)) (.immediate 64), -- 53
.binary (.mul rfl) (.direct 8) (.memory (.direct 4)) (.immediate 10), -- 54
-- Queue base 10B+64.
.binary .add (.direct 8) (.memory (.direct 8)) (.immediate 64), -- 55
.copy (.direct 11) (.immediate 0), -- 56
-- initialize:
-- Initialize every parent and every visited flag.
.branch .le (.memory (.direct 1)) (.memory (.direct 11)) 64, -- 57
.binary .add (.direct 0) (.memory (.direct 6)) (.memory (.direct 11)), -- 58
.copy (.indirect 0) (.memory (.direct 11)), -- 59
.binary .add (.direct 0) (.memory (.direct 7)) (.memory (.direct 11)), -- 60
.copy (.indirect 0) (.immediate 0), -- 61
.binary .add (.direct 11) (.memory (.direct 11)) (.immediate 1), -- 62
.jump 57, -- 63
-- root:
.binary .add (.direct 0) (.memory (.direct 7)) (.memory (.direct 5)), -- 64
-- Mark the root before enqueueing it.
.copy (.indirect 0) (.immediate 1), -- 65
.copy (.direct 0) (.memory (.direct 8)), -- 66
.copy (.indirect 0) (.memory (.direct 5)), -- 67
-- Queue head.
.copy (.direct 9) (.immediate 0), -- 68
-- Queue tail.
.copy (.direct 10) (.immediate 1), -- 69
-- dequeue:
-- Stop when the queue is empty.
.branch .le (.memory (.direct 10)) (.memory (.direct 9)) 111, -- 70
.binary .add (.direct 0) (.memory (.direct 8)) (.memory (.direct 9)), -- 71
-- Current vertex u.
.copy (.direct 11) (.memory (.indirect 0)), -- 72
.binary .add (.direct 9) (.memory (.direct 9)) (.immediate 1), -- 73
.binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 3), -- 74
.binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 11)), -- 75
-- Read the spill copy for graph addresses 1 through 16.
.branch .lt (.immediate 16) (.memory (.direct 0)) 79, -- 76
.binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 77
.binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 78
-- begin_load:
.copy (.direct 12) (.memory (.indirect 0)), -- 79
.binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 3), -- 80
.binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 11)), -- 81
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 82
-- Read the spill copy for graph addresses 1 through 16.
.branch .lt (.immediate 16) (.memory (.direct 0)) 86, -- 83
.binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 84
.binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 85
-- end_load:
.copy (.direct 13) (.memory (.indirect 0)), -- 86
-- scan:
-- Scan the incoming-adjacency interval of u.
.branch .le (.memory (.direct 13)) (.memory (.direct 12)) 70, -- 87
.binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 4), -- 88
.binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 12)), -- 89
-- Read the spill copy for graph addresses 1 through 16.
.branch .lt (.immediate 16) (.memory (.direct 0)) 93, -- 90
.binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 91
.binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 92
-- edge_load:
.copy (.direct 14) (.memory (.indirect 0)), -- 93
.binary .add (.direct 12) (.memory (.direct 12)) (.immediate 1), -- 94
.binary (.mul rfl) (.direct 0) (.memory (.direct 14)) (.immediate 2), -- 95
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 2), -- 96
-- Read the spill copy for graph addresses 1 through 16.
.branch .lt (.immediate 16) (.memory (.direct 0)) 100, -- 97
.binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 98
.binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 99
-- tail_load:
.copy (.direct 14) (.memory (.indirect 0)), -- 100
.binary .add (.direct 0) (.memory (.direct 7)) (.memory (.direct 14)), -- 101
.copy (.direct 15) (.memory (.indirect 0)), -- 102
-- Skip an already discovered predecessor.
.branch .eq (.memory (.direct 15)) (.immediate 1) 87, -- 103
-- Mark new predecessor v.
.copy (.indirect 0) (.immediate 1), -- 104
.binary .add (.direct 0) (.memory (.direct 6)) (.memory (.direct 14)), -- 105
-- Set par(v) = u.
.copy (.indirect 0) (.memory (.direct 11)), -- 106
.binary .add (.direct 0) (.memory (.direct 8)) (.memory (.direct 10)), -- 107
-- Enqueue v exactly once.
.copy (.indirect 0) (.memory (.direct 14)), -- 108
.binary .add (.direct 10) (.memory (.direct 10)) (.immediate 1), -- 109
.jump 87, -- 110
-- restore:
-- Restore original cells 1 through 16, using only pointer register 0.
.copy (.direct 0) (.memory (.direct 2)), -- 111
.copy (.direct 1) (.memory (.indirect 0)), -- 112
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 113
.copy (.direct 2) (.memory (.indirect 0)), -- 114
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 115
.copy (.direct 3) (.memory (.indirect 0)), -- 116
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 117
.copy (.direct 4) (.memory (.indirect 0)), -- 118
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 119
.copy (.direct 5) (.memory (.indirect 0)), -- 120
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 121
.copy (.direct 6) (.memory (.indirect 0)), -- 122
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 123
.copy (.direct 7) (.memory (.indirect 0)), -- 124
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 125
.copy (.direct 8) (.memory (.indirect 0)), -- 126
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 127
.copy (.direct 9) (.memory (.indirect 0)), -- 128
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 129
.copy (.direct 10) (.memory (.indirect 0)), -- 130
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 131
.copy (.direct 11) (.memory (.indirect 0)), -- 132
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 133
.copy (.direct 12) (.memory (.indirect 0)), -- 134
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 135
.copy (.direct 13) (.memory (.indirect 0)), -- 136
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 137
.copy (.direct 14) (.memory (.indirect 0)), -- 138
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 139
.copy (.direct 15) (.memory (.indirect 0)), -- 140
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 141
.copy (.direct 16) (.memory (.indirect 0)), -- 142
.binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 143
-- Restore original n in cell 0 from S+16.
.copy (.direct 0) (.memory (.indirect 0)), -- 144
.halt -- 145
]
end DirKECC1549.Main