/
level_builder.go
84 lines (76 loc) · 2.75 KB
/
level_builder.go
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
package constraint
// The main idea here is to find a naive clustering of independent constraints that can be solved in parallel.
//
// We know that at each constraint, we will have at most one unsolved wire.
// (a constraint may have no unsolved wire in which case it is a plain check that the constraint hold,
// or it may additionally have some wires that will be solved by solver hints)
//
// We build a graph of dependency; we say that a wire is solved at a level l
// --> l = max(level_of_dependencies(wire)) + 1
func (system *System) updateLevel(cID int, c Iterable) {
system.lbOutputs = system.lbOutputs[:0]
system.lbHints = map[*Hint]struct{}{}
level := -1
wireIterator := c.WireIterator()
for wID := wireIterator(); wID != -1; wID = wireIterator() {
// iterate over all wires of the R1C
system.processWire(uint32(wID), &level)
}
// level = max(dependencies) + 1
level++
// mark output wire with level
for _, wireID := range system.lbOutputs {
for int(wireID) >= len(system.lbWireLevel) {
// we didn't encounter this wire yet, we need to grow b.wireLevels
system.lbWireLevel = append(system.lbWireLevel, -1)
}
system.lbWireLevel[wireID] = level
}
// we can't skip levels, so appending is fine.
if level >= len(system.Levels) {
system.Levels = append(system.Levels, []int{cID})
} else {
system.Levels[level] = append(system.Levels[level], cID)
}
}
func (system *System) processWire(wireID uint32, maxLevel *int) {
if wireID < uint32(system.GetNbPublicVariables()+system.GetNbSecretVariables()) {
return // ignore inputs
}
for int(wireID) >= len(system.lbWireLevel) {
// we didn't encounter this wire yet, we need to grow b.wireLevels
system.lbWireLevel = append(system.lbWireLevel, -1)
}
if system.lbWireLevel[wireID] != -1 {
// we know how to solve this wire, it's a dependency
if system.lbWireLevel[wireID] > *maxLevel {
*maxLevel = system.lbWireLevel[wireID]
}
return
}
// we don't know how to solve this wire; it's either THE wire we have to solve or a hint.
if h, ok := system.MHints[int(wireID)]; ok {
// check that we didn't process that hint already; performance wise, if many wires in a
// constraint are the output of the same hint, and input to parent hint are themselves
// computed with a hint, we can suffer.
// (nominal case: not too many different hints involved for a single constraint)
if _, ok := system.lbHints[h]; ok {
// skip
return
}
system.lbHints[h] = struct{}{}
for _, hwid := range h.Wires {
system.lbOutputs = append(system.lbOutputs, uint32(hwid))
}
for _, in := range h.Inputs {
for _, t := range in {
if !t.IsConstant() {
system.processWire(t.VID, maxLevel)
}
}
}
return
}
// it's the missing wire
system.lbOutputs = append(system.lbOutputs, wireID)
}