Hardware accelerated flag checker 1

Challenge

We are given a single file, netlist.v: a synthesized (Yosys-style, gate-level) Verilog module flag_checker(clk, reset_n, character, found_flag).

• character is a 7-bit input (one ASCII byte fed per clock).
• s is a 5-bit state register.
• found_flag is asserted when s == 5’b11111 (31), derived from: 228 = ~(s[4] & 227) found_flag = ~228 => found_flag = s[4] & ~( ~(s0&s1) | ~(s2&s3) ) => found_flag = s0 & s1 & s2 & s3 & s4
• The reset logic: 000 = ~(reset_n & 228) forces s back to 0 either when reset_n is deasserted, or automatically the cycle after found_flag becomes 1 (self-resetting checker).
• Everything else is ~200 lines of raw NAND/NOR/INV gates (_289_[4:0]) that compute the next-state function of (s, character) — this is what Yosys produces when it synthesizes something like:

always @(posedge clk)
  if (!reset_n || found_flag) s <= 0;
  else if (character == flag[s]) s <= s + 1;
  else s <= fail_state(s, character);   // KMP-style failure transition

Approach

Rather than trying to read ~200 lines of anonymous gates by hand, wrote a small generic gate-level simulator in Python (sim.py):

1. Parsed every assign LHS = ~(A op B); / assign LHS = ~A; line with a regex into a (lhs, rhs) list, preserving file order (Yosys always emits gates in a topologically-sorted order, so a single top-to-bottom pass with a resolve() lookup into a growing env dict is enough to evaluate the whole netlist — no fixed-point iteration needed).
2. evalnet(s_bits, char_bits) seeds env with the 5 bits of s, 7 bits of character, and reset_n = 1, then executes every assign in order, interpreting ~(A|B) as NOR, ~(A&B) as NAND, ~A as NOT.
3. Returns the computed _289_[4:0] (next-state) and found_flag.
4. Brute forced the FSM: starting at state 0, try every byte 0..127 as character and see which one(s) produce a non-zero next state. At most states there were two such candidates: one character that advances state -> state+1 (the “correct” next flag byte), and one that is a KMP failure-function edge (e.g. feeding ‘N’ again from deep inside the string always folds back toward state 1, since ‘N’ is also the first byte of the flag). Always preferring the next_state == state + 1 candidate over any other resolves the ambiguity and walks straight through the automaton.
5. Iterating this from state 0 up to state 31 (where found_flag would assert) recovers the flag one byte per state transition.

This produced, byte by byte: N N S { q u 1 c k _ a n d _ 3 f f 1 c i 3 n 7 _ c h e c k 5 }

i.e. NNS{qu1ck_and_3ff1ci3n7_check5} — 31 characters, matching the 31 non-zero states of the 5-bit register (2^5 - 1).

Flag

NNS{qu1ck_and_3ff1ci3n7_check5}