Introduction
All computers deal in bits, and this ASIC is no different. The ASIC incrementally takes in 121 input bits and applies a deterministic procedure to them. We wish to find an input that turns on the success signal. This sounds like a Boolean satisfiability problem.
Directly solving the supplied ASIC is a daunting task, so instead we set out to solve the warm-up GDS, using its published behavior to test our process. Once our process is established, we repeat it with the ASIC.
The warm-up as a running example
The warm-up describes two 8-bit registers, a 9-bit adder, and a comparison with 496. On every rising clock edge for which en=1, 1 bit from A and 1 from B enter the two registers. After 8 edges, the register values are summed in the adder and the result is compared to 496, turning on iff equal. This is succinctly described as
where brackets mean a Boolean truth value. Figure 1 shows this circuit.
The sample tests shift bits in order from most significant to least significant. They first check a positive example, , then a negative example, . We shall use these values to test our recovered circuit.
always @(posedge clk or negedge rst_n)
if (!rst_n) parallel_out <= 8'b0;
else if (en) parallel_out <= {parallel_out[6:0], serial_in};
assign sum = a + b;
assign eq = (val == 9'd496);
comparator496 cmp0 (.val(sum), .eq(S));
We can inspect the conducting polygons and contacts either separately or as a stack. The contacts join conductors on adjacent layers; these vertical connections are as important as intersections within a layer.
From GDS geometry to wires
What the file describes
GDS stores polygons tagged with a layer/datatype pair, text labels, reusable cell definitions, and references that place copies of those definitions. This design uses the SkyWater SKY130 process and its high-density standard-cell library. In this process, layers 67–72 are local interconnect (LI1) through metal 5, datatype 20 denotes conductor drawing geometry, datatype 16 denotes pin geometry, and datatype 44 denotes a via cut. Identifying this geometry lets us recover the wires.
A close-up separates the routing layers from the cells beneath them. We retain this geometry when recovering connectivity, rather than treating intersections in a top-down projection as electrical connections.
What the DSU represents logically
Our extractor gives an integer ID to each conductor polygon. A disjoint-set union (DSU) maintains groups of IDs. At first, every polygon is alone. We do union(a,b) if 1) polygons and intersect on the same conducting layer, or 2) a via cut intersects and . After all unions are completed, returns the same ID as iff and are connected through such contacts.
We treat each equivalence class as one ideal electrical node, called a net. Note that the DSU records only connectivity; it does not record logical operations, time, direction, or a signal's value.
# Same mask layer: exact polygon contact is electrical contact.
for i, polygon in enumerate(layer.polygons):
for j in layer.tree.query(polygon, predicate="intersects"):
dsu.union(layer.offset + i, layer.offset + int(j))
# A via cut joins every conductor it touches below to every one above.
for cut in via_cuts:
for i in conductors_below_touching(cut):
for j in conductors_above_touching(cut):
dsu.union(below.offset + i, above.offset + j)
In the worked example below, the DSU groups 13 conductor drawing polygons on 3 layers through 8 same-layer contacts and 4 via cuts, and attaches 2 cell endpoints. Four overlapping pin shapes bring the extractor's count to 17; they add no new conducting area. The 3 layers are drawn separately in Figure 5 to make the contacts visible.
n237.The recovered nets can also be inspected in the original geometry. The conductor view includes pin shapes as well as drawing polygons; the full stack supplies their physical context.
Attaching names to components
Standard-cell definitions contain pin labels on LI1. A placed reference carries a transform: a location, a rotation, and possibly a reflection. We apply that transform to the label coordinate and extract which DSU component lies under that point. For example,
means that the transformed coordinate of pin label X lies on a conductor polygon whose DSU root was compactly renamed n237. The compact IDs are arbitrary; the endpoint grouping is what matters.
Repeating this for every pin label in the design gives the netlist: a list of placed cells together with the net attached to each of their pins.
Net IDs are assigned during extraction and can differ between executions. The wire from sr_a/_11_.X to sr_a/_19_.D is labeled n237 in the write-up; its endpoints identify the same wire in the notebook.
From named cells to Boolean equations
Connectivity tells us which pins share a wire, but cell semantics tell us what those pins compute.
Standard cells, masters, and instances
This design does not lay out transistors gate by gate. It assembles circuits from small, pre-designed components such as AND gates, multiplexers, and flip-flops, each stored once in the GDS as a definition and then placed wherever it is needed. Those definitions have names beginning sky130_fd_sc_hd__.
For example, one embedded definition is named
The mux2 identifies a 2-input multiplexer, and the 1 identifies its drive-strength variant. Drive strength does not affect the Boolean rule, so we will ignore it. We call a reusable GDS definition a master; an instance is one such placed copy of it. In the warm-up, sr_a/_11_ is an instance of the mux2_1 master.
The master defines 4 signal pins:
| Pin | Direction | Meaning |
|---|---|---|
A0 | input | value selected when S=0 |
A1 | input | value selected when S=1 |
S | input | selection bit |
X | output | selected value |
Consequently, sr_a/_11_.X means “pin X on this particular placed mux.”
Substituting nets into a documented cell rule
Our geometric reconstruction attaches the 4 pins of this instance to the following nets:
Each net carries a Boolean value. The 3 input pins read the values on , , and ; the output pin drives the result onto . A mux operates under the following rule:
Equivalently,
where means “if , then , otherwise .”
In this example, is connected to the top-level input en. When en=1, the mux passes , the output of the preceding shift-register stage, toward the next flip-flop. When en=0, it passes back, which is that flip-flop's own output, so the flip-flop retains its current value at the next clock edge.
Translating the remaining cells
We repeat the same substitution for every placed component. For example, a 2-input AND cell obeys
If one particular instance has A,
B, and X, that instance contributes
An inverter contributes a negation. More complicated cells contribute larger
expressions. For example, the documented function of an a21o cell is
This process produces Boolean equations for all combinational cells: components whose outputs depend only on their current inputs. Flip-flops require one additional idea because their outputs depend on an earlier clock edge.
Adding memory and the clock
A combinational equation relates values at a specific point in time. A flip-flop introduces state. Specifically, an output Q after a rising edge equals D just before that edge. We therefore index state by clock step. If n28 is the Q output of sr_a/_19_, then
Substituting the mux equation yields
Figure 7 illustrates this rule, both as a circuit and over time.
The mux output n237 changes whenever its inputs change. The flip-flop copies n237 into n28 only at a rising clock edge, then holds it. Thus the clock marks when the transition equation applies. Pulling reset low overrides the clock and forces n28 to 0.
We can now replay the sample tests on the recovered warm-up circuit. The flip-flop states change at the clock edges, while the combinational wires follow the current inputs and stored state.
Turning a clocked circuit into one finite formula
We give the state vector a separate name at each modeled clock edge and connect adjacent states using the next-state function. We call this unrolling the circuit. This leaves one finite combinational formula.
For the warm-up, applying the transition rule 8 times creates states . Reset fixes ; the serial input bits at each step are known values; and we evaluate the final expression for S. Because nothing here is unknown, the warm-up is a check rather than a search: comes out 1 for and 0 for , exactly as the published sample tests require.
The warm-up also ships its routed DEF, which states the true connectivity, so we can compare that against our recovered nets. All 84 signal nets and all 291 endpoints agree: no net is missing an endpoint, none has gained one, none is split into two, and no two are merged into one. Since the recovered circuit agrees with both the sample tests and the DEF, we use the same method on the ASIC.
The ASIC uses exactly this construction, with 1 change: the serial inputs are unknown Boolean variables rather than known bits. Let be the vector of all 92 flip-flop outputs immediately after edge , and let be the bit presented at the next edge. The transition function evaluates every recovered combinational equation using , , and enable, then collects the resulting flip-flop outputs. Thus
In the supplied waveform, example_inputs.vcd, there are 121 transitions with enable=1, followed by 1 with enable=0. Therefore, there are states through , with the goal being . Figure 9 shows the resulting chain.
The extra disabled transition is necessary because success is stored only after input capture ends.
A Boolean satisfiability (SAT) solver takes a set of constraints over Boolean variables and either returns an assignment that satisfies all of them at once, called a model, or reports unsat, meaning it has proved that no such assignment exists. That is exactly the problem promised in the introduction, so we hand our equations to Z3.
The exported instance contains variables: unknown inputs and state variables. It contains top-level assertions: 88 reset facts, transition equalities, and 1 final success requirement. The other 4 flip-flops have no reset pin. Under the recovered transition relation, a backward fan-in audit shows that none lies in the transitive fan-in of success, so their unconstrained initial values do not affect the result.
To prove uniqueness, after the first model is found, we add the following clause:
It is false for exactly the assignment just found and true for every other 121-bit string, so solving again searches for a different input. Z3 returns unsat, which proves that no other 121-bit input satisfies the recovered circuit.
Result
The unique 121-bit input is
0000000101010000100000000000010101010000000000001010000001000001000000100000101000010000000100000010000010010001010000000
On the next rising edge, success becomes true, and the output circuit emits
(* TWO STARS *)
Arranged in the serial stream's row-major order on an grid, the input has exactly two 1-bits in every row and column, and no two 1-bits touch horizontally, vertically, or diagonally (Figure 11). This is oddly reminiscent of Star Battle, leading us to ponder what the mystery regions are.
Recovering the regions
Closer inspection of the 92 flip-flops reveals that 44 lie in 2 regular banks of 22. Tracing their next-state equations pairs each bank into eleven 2-bit counters. One bank is selected by column; the other is selected by an irregular position-dependent signal. Because the 121 bits arrive serially in row-major order, the same 11-column selection schedule is reused for every row.
For a concrete example, one pair has low bit n717 and high bit n509. Simplifying the gates that drive their D pins gives the following behavior, with meaning the current input is 1, capture is enabled, and this particular counter is selected:
| old HL | new HL | meaning | |
|---|---|---|---|
| 0 | any | unchanged | this cell does not add to the counter |
| 1 | 00 | 01 | first selected star |
| 1 | 01 | 10 | second selected star |
| 1 | 10 or 11 | 11 | third or later star, saturated at 3 |
Thus the remaining problem is to learn which counter is selected at each of the 121 positions. We reset the circuit and feed 0 for every position before . The position machinery still advances, so the selection signals are correct for position , but no star has been counted anywhere and every counter therefore sits at 00. From 00, a selected counter must move to 01 when it sees a star, while an unselected one cannot move at all. So we copy that pre-edge state and evaluate the next state twice, once with and once with . For these 2 counter banks, exactly 1 low flip-flop per bank differs between the 2 evaluations, and it is the low bit of the counter selected at position .
For cell , the differing low bits are n313 in one bank and n717 in the other. The n313 choice recurs at cells , identifying column 1. At the column bit changes to n304, while the region bit is still n717, so and must share the same region. At the pair is n671 and n495: column 6 and a new region. Repeating this comparison for all 121 stream positions yields the complete partition.
The extracted schedule must pass 4 checks: 11 column selectors repeat every row; 11 region selectors cover all 121 cells exactly once; each resulting region is orthogonally connected; and the winning replay leaves every column and region counter at binary 10. All 4 hold, and the resulting reconstruction is Figure 13.
The ASIC is therefore fully accounted for. Touching polygons gave us wires, wires plus the cell library gave us Boolean equations, the clock turned those equations into one unrolled formula, and that formula had exactly one solution: the unique Star Battle board above, which the ASIC confirms by printing (* TWO STARS *).
Easter eggs
- The two attempts in
example_inputs.vcdencode The night sky awaits: split each into eleven 11-bit records, reverse each record's first 7 bits, and read only those 7-bit character codes (ignoring 4 zero padding bits; the last 2 codes are spaces). - Below the die, 36 inert tiny-cell references spell out
PER ARENAM AD ASTRAin Morse code, “through the arena to the stars,” a spin on per aspera ad astra. - The output circuit has 4 reachable responses:
EMPTY SKYfor all 0s,BIG BANGfor all 1s,TRY AGAINfor an ordinary incorrect input, and, naturally following OCaml comment syntax,(* TWO STARS *)for the answer.