Solving the Jane Street Reverse Engineering Challenge

Or: Why do I ever do things the difficult way?

Jane Street periodically puts retired challenges, and this 1 thoroughly nerd-sniped maine and sent maine down a month-long rabbit hole that I’m only now emerging from. This station is an overview of really I solved it pinch a operation of hard-headedness and slumber deprivation. It’s going to beryllium decently technical, but successful early posts I’ll spell complete the specifics of each step if group are interested.

For immoderate inheritance I’d urge looking astatine the original station connected the Jane Street blog present - Can you reverse Engineer an ASIC?

And if you ever want to publication the (terrible) codification I utilized for this challenge, you tin find it astatine my github page here

Challenge Accepted

I person an engineering grade rotting distant location successful my brain, truthful a batch of the words of the challenge are familiar. The situation is to return an ASIC and activity retired what it does. For those unfamiliar, an ‘ASIC’ is an Application-Specific Integrated-Circuit, which is simply a fancy connection for what we’d usually telephone a ‘Computer Chip’. Firms for illustration Jane Street presumably creation these to get other capacity comparative to the instrumentality you tin bargain from a normal manufacturer.

In immoderate case, the situation is to return a ‘GDS’ record describing a chip, and activity backwards to understand what it does, and past I conjecture possibly there’s a password successful location aliases something. I didn’t, and still don’t, cognize what ‘GDS’ guidelines for.

There’s 2 parts to the situation - 1 is simply a warmup wherever you’re fixed a batch much accusation (like the existent creation of the chip), and the existent puzzle wherever you’re fixed a patient handshake and a ‘good luck’ arsenic you look the expanding prospect of not sleeping for the adjacent 3 weeks.

What’s successful the files?

For immoderate reason, I for illustration to do things the difficult measurement truthful alternatively than doing immoderate investigation I conscionable started poking astir successful the files. I tin spot there’s immoderate acquainted words successful them for illustration like ‘clk’ (clock), ‘rst’ (reset) and ‘VGND’ (Ground Voltage) and ‘VPWR’ (Power Voltage).

And there’s a bunch of …. thing pinch a prefix of sky130_fd_sc_hd__ followed by things that sound for illustration logic element, like ‘or’ and ‘not’ and things for illustration that. I conjecture that’s what I’ll request to propulsion retired of the file?

I recovered there’s a really bully room ‘gdstk’ successful python that seems to beryllium capable to publication them. It show maine that there’s 27 elements connected the warmup puzzle. A bully start!

% python3 -c 'print(len(__import__("gdstk").read_gds("warmup/04_final.gds").cells))' 27

There’s besides a ‘vcd’ record for the main puzzle, which is simply a matter file, and I conjecture is simply a simulation input aliases output aliases something. I didn’t, and still don’t, cognize what ‘vcd’ stands for. I tin spot immoderate suspicious entries successful it that look for illustration ASCII characters. I play astir pinch it, penning a mini C program, and get the output ‘TRY AGAIN’. Ah, truthful the circuit has messages successful it somehow!

$ gcc what-is-this-thing.c && ./a.out T R Y A G A I N T R Y A G A I N

Ok we’re connected to something

Getting Distracted and wasting my time. And my life.

Here we request to do a immense digression and of people build our ain circuit simulator. For reasons.

You tin skip this section. I judge wish I did.

Several days later

Ok truthful I built a circuit sim utilizing sqlite3 arsenic a driver. Quite neat really. But it’s rather difficult to creation circuits successful Python! If only location was a connection for describing hardware.

Several days later

Ok truthful I built a parser for my caller connection and now I tin creation circuits. But I request to trial them! If only location was some way of scriptings inputs and validating outputs.

Several days later

Ok truthful I built a harness for my circuit simulator. But it’s really difficult to visualise what it’s doing! If only location was… well you spot wherever this is going

Several days later

Ok truthful I gave up connected penning a activity shape spectator and decided to conscionable usage ‘surfer’. But these gds files are difficult to work with, really tin I make that easier?

Several days later

Ok truthful I wrote a basal GDS spectator successful raylib but I can’t get the blocks to beryllium rather the measurement I want to. So anyway, I realised I’m down excessively galore tangents and it’s clip to driblet each of the civilization software.

Ok we’re done pinch that section. Aren’t you gladsome you skipped it?

Focus, Chris, Focus.

The Jane Street blog really points to rather a useful GDS Viewer, truthful I spent some clip conscionable looking astatine it existent difficult and hoping thing would travel to me. I was capable to astir annotate what I though were which inputs, and I could later corroborate that by looking done the approximate locations of wires in the files. Because this was the warmup I could comparison what I knew astir the circuit against what I could see.

What do these files represent?

These files look to person immoderate consciousness of ‘layers’ of different types of worldly aliases something, I ideate it’s a spot for illustration a big 3d-printer that has to beryllium told wherever to move the people head, and astatine what extent it needs to put a caller material. Maybe these files are adjacent to the instructions to the machine? But alternatively than having arbitrary positions successful vertical space they look to person modular layers of modular widths truthful that simplifies things.

I wanted to beryllium that I could astatine slightest run connected these files, truthful I tried to extract the Jane Street logo connected the upper correct corner. Somehow this was measurement harder than I thought and I ended up extracting everything except the Jane Street logo? But immoderate bully enough, lets move on.

I besides astatine immoderate constituent activity retired that the room I’m utilizing tin extract the elements to SVG record formats, and it includes a bunch of matter describing the parts of the elements. This will beryllium cardinal to really knowing the situation because I tin possibly usage that accusation to activity retired which parts are inputs and outputs.

Time to really publication astir these elements

I’ve gotten arsenic acold arsenic I tin pinch guessing. Time to really publication immoderate due documentation. Looks for illustration this is their charismatic home, contempt the ‘unofficial’ successful the sanction - sky130-unofficial

The docs had the answers to galore of my questions. Why do I ever do things the difficult way?

It turns retired that this ‘sky130’ point is for illustration a … standard? Or thing for making chips. I conjecture making chips is hard, and truthful it makes consciousness for location to beryllium communal creation elements. Crucially it besides contains the descriptions of what the elements do, which is easy for elements for illustration ‘and’ that are astir apt an ‘and gate’ but little clear for a ‘o21bai’ which is a …. good don’t interest excessively overmuch astir that.

Using the accusation from the docs and the labels from the SVG I tin now theoretically representation circumstantial geometry to the I/O of the circuit elements, which I conjecture will beryllium the first measurement to turning it into a ‘real circuit’. I get really fortunate here, in that my room has the expertise to cheque if 2 elements overlap successful 2d abstraction (remember these gds files are really a description of a 3d geometry).

I wasn’t judge really reasonable the presumption of the labels overlapping the correct locations, but it worked measurement amended than I expected! I conjecture labels are already referenced connected their centerpoint! It moreover picked up immoderate geometry that isn’t visually connected truthful a ocular inspection would ne'er person revealed their connections. And looking astatine the full design’s IO ports, it’s truthful overmuch little visually noisey.

I deliberation I tin make a chart now?

I deliberation I person what I request now to extract a circuit from this gds file. This isn’t going to beryllium easy. This point has 1k paths and almost 17k polygons moreover aft ignoring everything I don’t attraction about.

I request to find a measurement of uncovering things that are ‘touching’, which intends that they are connected adjacent layers and besides overlapping.

My algorithm is beautiful terrible, but it does the occupation for now. I besides present a simplification measurement wherever I take all of the ‘wire segments’ and …. compress? aliases coalesce? them into a azygous wire. The logic is, that if 2 wires are touching past they’re really the aforesaid ligament from my perspective.

Luckily I spent respective weeks grinding leetcode past twelvemonth while unemployed truthful a fewer chart algorithms weren’t going to slow maine down.

Many days later

The adjacent fewer days of activity were not easy. In my moving log I person recorded that “By beating my bloodied look against the keyboard for respective hours and cursing really agelong I’ve already spent connected this, I’ve managed to nail down a tricky bug”. I’m not precisely judge what that bug was now, but I’m judge it deserved it.

I’ve started to beryllium capable to move my web successful to existent descriptions of hardware successful a connection called ‘Verilog’, which besides allows maine to tally basal simulations for illustration checking that ‘turning this pin precocious makes that 1 spell low’. I’m eventually capable to extract each the components into a fistful of spaghetti, and I walk clip manually drafting out the connections.

I don’t usage immoderate tooling (other than excalidraw, my drafting program). I mostly conscionable look astatine it existent difficult until things make sense. Again, I do things the difficult way

Not pictured: Sanity

But successful immoderate lawsuit I now had an knowing of the awesome components of the warmup puzzle - 2 displacement registers (that shift things), an adder (that adds things) and a comparitor (that compares things) and I activity connected trying to simulate the outputs. I cognize that the input needs to sum to beryllium 496 arsenic the comparitor is named comparitor496 truthful I conscionable request to put successful the correct series of bits to execute that. That’s conscionable elemental maths, the difficult portion was trying to get each the various parts all moving together successful a azygous simulation.

If only location were immoderate measurement of doing this that didn’t impact trading disconnected my sanity for progress.

A fewer hr later and it’s done! I yet sewage this point to work!

It’s astatine this constituent I knew I had a chance of solving this thing, but it was a title against the clock, and my immune system was starting to springiness out.

On to the existent puzzle

The existent puzzle has galore much constituent types (81 vs 20 aliases so) and galore much of them (almost 10k vs 1k) truthful this won’t beryllium easy. I was capable to quickly get astir aspects of my scripts moving from the warmup steps, truthful agelong arsenic I dropped each validation. Which is not perfect but it was only temporary. More annoying is that the process of extracting the circuit takes almost a full infinitesimal alternatively of 2 seconds.

Initial work

I was capable to get a small triumph by rearranging my ligament conception gathering measurement truthful it is now 100x faster (3.4 second down to .03 seconds). It has byte-for-byte compatible behaviour truthful I’m beautiful assured it hasn’t introduced any bugs. However the awesome slow measurement still swamp this betterment - uncovering each connected components takes almost a whole minute. Luckily I person a batch of assurance successful that measurement aft the nightmare of the warmup puzzle, truthful I don’t have to tally it excessively often

It took a agelong time, but I added implementations of each of the 40 aliases truthful caller components that I request successful the existent puzzle by conscionable manually copying them from the archiving site. In retrospect I’m judge I could person copy-pasted it from somehwere, but (in lawsuit you haven’t been paying attention) I for illustration to do things the difficult way.

After that, and immoderate quality-of-life improvements astir being capable to adhd names aliases aliases to wires, I was capable to build and tally a simulation of the existent puzzle. It didn’t work, but still, I deliberation that intends I’m successful pinch a changeable of solving this thing.

Is location a bug?

One annoyance I had is that I had to disable my validations, but it’s difficult to make advancement without validations as it’s easy to present bugs without noticing until hours aliases days later. So I went backmost to trying to move them back on. For illustration I had a validation measurement that checked that each wires are really connected to something.

I recovered successful 1 conception of my simulation that I had an undriven wire, meaning that its worth was wholly unknown to my simulator. That’s a spot unusual really, because moreover if you don’t attraction astir the worth of a ligament you’d typically conscionable thrust it to immoderate known worth alternatively than not connecting it astatine all. I assumed it was a bug in my pin-detection logic, but by ocular inspection I could spot that my codification was correctly picking up a ligament that’s only connected to 2 input pins.

Even stranger, the circuit has a relationship connected a neighboring pin that isn’t moreover an input aliases an output! Maybe there’s a bug present and it should beryllium connected to 1 of the inputs? Given really small I understand, I sheepishly reported it to Jane Street.

The adjacent time I had an email confirming that I was right! But luckily it shouldn’t person an effect connected the existent results of the challenge. I rather sincerely deliberation this bug study mightiness beryllium 1 of my coolest method achievements.

Looking from a bird’s oculus view

I spent a agelong clip mapping retired sections of subcircuits and the wires connecting them, and things started to fall successful to place. I worked retired that the conception that feeds the ‘success’ ligament has 6 wires, truthful now the challenge is somewhat reduced to ‘how do I make those 6 wires spell high?’, and luckily it seems for illustration 2 of them do it after a definite number of timepiece cycles, truthful really it’s only 4 wires.

I tin spot different patterns too. The left-most subcircuits look to enactment for illustration a awesome generator which past feeds in to different sections of the circuit. So possibly the ‘password’ is hidden wrong the building of these elements?

Combining the three, I tin spot it gives 121 aliases 120 timepiece transitions earlier the output goes high. That matches the waveform successful the provided example, truthful possibly you request to person the password correct successful 120/121 clocks otherwise you get the message?

This conception seems to provender the remainder of the circuit, truthful this mightiness beryllium the commencement of a clue.

I was now capable to get each sub-section to tally successful a simulation but not really do thing useful. I past started working connected connecting each the sub-components into 1 ample circuit.

It turns retired I’m an idiot.

I wasn’t capable to get my wide sim moving astatine each for 2 aliases 3 days, moreover though I’d rather thoroughly tested each sub component. Well, it turns retired that I had forgotten to group the ‘reset’ pin, truthful the full point was effectively disabled, benignant of for illustration forgetting to move the car connected and wondering why you’re not going anywhere.

I fixed that and instantly saw ‘TRY AGAIN’ arsenic expected. Success!

Even much absorbing is, I deleted the input I was feeding to the circuit and I recovered it had different messages too:

Input Output

Wrong Answer	TRY AGAIN
All 0’s	EMPTY SKY
All 1’s	BIG BANG
Correct Answer	TBD

The doldrums

I’ve now reached the hardest portion of this challenge. I’ve recovered that the input to this circuit is 120 bits, and I have no thought really to progress. I considered exhaustively checking each input but that would unluckily return much time than immoderate of america person connected this planet.

Wire-by-Wire

I travel the output ligament backmost directly, but the complexity of the inputs are excessively overmuch for me. I request immoderate new approach. At immoderate constituent successful my notes I inquire the mobility ‘what if I tally the simulation successful reverse?’, and I start mulling connected this idea.

The point is, I cognize wherever I want a awesome to beryllium and I cognize what the inputs request to beryllium astatine that point.

So past if I return 1 measurement backmost successful clip I tin re-write the desired output arsenic a functions of the erstwhile step.

This is for illustration a recurrance relation, but I really cognize what I want the output to beryllium connected measurement 120, and I know that the circuit starts pinch each outputs astatine zero. So theoretically this is solvable successful immoderate mathematical sense.

Hopefully the image beneath explains a spot amended what I mean

I attraction connected a displacement registry constituent arsenic it’s closest to the 1 I solved successful the warmup puzzle (which is simply a bully touch of pedagogy, truthful convey you Ben and Anish!). There’s immoderate tricky constraints actually, I tin show it depends connected previous values successful the displacement register, this astir apt needs immoderate constraint solver to solve. Constraint solvers are notoriously complicated to understand, but luckily I cognize the cleanable tool

On utilizing a spreadsheet to constitute verilog

I’m sorry for the abomination that I’m astir to show you.

Yes, that’s a spreadsheet that I utilized to constitute verilog that I past fed successful to my simulated circuit. Surprisingly, under the hood spreadsheets are really incredibly blase constraint solvers. I dumped the output into a Verilog file, and ….. it worked! At slightest for 2 wires. It does look for illustration this attack will be underpowered successful wide because it relies connected maine eyeballing the output and toggling bits present and location until each my checks spell green. But it did beryllium that this attack of solving it backwards has legs.

It’s clip to bring retired the large guns and study to usage a constraint solver.

This …. isn’t arsenic difficult arsenic I expected?

I remembered reference astir constraint solvers connected Hillel Waynes blog (who has a caller book retired you should spell buy! I’ve sewage my copy), but I’d ever been intimidated because they use large words for illustration ‘constraint’ and ‘solver’ and I conscionable request a point to lick the constraints successful my - ooooh I get it!

I ended up utilizing a instrumentality called ‘z3’. It’s benignant of magical? Every clip it finds a solution I get a surge of joy. You tell it things for illustration ‘This ligament tin ne'er beryllium low’ aliases ‘This ligament has to beryllium precocious astatine measurement 120’ and it either finds how it tin do that, aliases tells you it can’t beryllium done. I was capable to springiness it thousands of constraints successful the extremity and it would find solutions successful the blink of an eye.

Debugging it is simply a spot of a nightmare though, and mostly seems to impact maine reasoning existent difficult and deleting lines until it starts moving again. I did get a spot of a consciousness for the benignant of outputs it liked to nutrient - successful particular if I didn’t specify starting points it would conscionable take immoderate was convenient for it (and inconvenient for me)

Annoyingly I did a batch of the translator activity from my circuit successful to z3 by hand. I’m not rather judge why I did it that way different than I had gotten sick by this constituent and I didn’t spot myself to constitute a translator script.

I went one-by-one connected the wires I cared about. There are astir 24 that I request to beryllium precocious astatine the aforesaid clip and I was capable to get 22 of them comparatively easy successful isolation by a operation of utilizing the solver and sometimes conscionable guessing a spot and validating them successful isolation.

It turns retired I’ve done this the difficult way, arsenic is characteristic.

It turns retired the building of the inputs to galore of the constituent appears to conscionable request 2 pulses astatine a aggregate of 11, wished by the worth of a counter. If I’d conscionable looked astatine the inputs a spot longer alternatively I mightiness person worked it out, but I was successful excessively heavy looking astatine the little layers alternatively than looking astir astatine what I could spot correct in front of me.

The Answer. It’s done

I now mixed each of my constraints successful to a azygous elephantine book and group astir squashing the bugs. There were a few, but by 10pm alternatively of an correction I sewage the pursuing output -

% python3 solver.py Solution! verilog saved to 'out.txt'

My hands started shaking because by this constituent the only measurement it could person a solution is if it had the answer.

I loaded it successful to my simulator, tally it, and location it is. The reply - (* TWO STARS *)

I emailed Jane Street, and the adjacent greeting I had my confirmation truthful I tin now adhd it to my array of outputs -

Input Output

Wrong Answer	TRY AGAIN
All 0’s	EMPTY SKY
All 1’s	BIG BANG
Correct Answer	~TBD~ (* TWO STARS *)

What next?

Well I don’t really cognize what to activity connected next, I really enjoyed this situation but I besides person different hobbys specified as ‘getting to furniture earlier 3am’. But Jane Street did mention they mightiness person a caller situation coming retired successful a mates of months, so enactment tuned!

If you person immoderate suggestions for nosy projects, fto maine cognize either connected Hacker News aliases by email.

And if you’re successful Sydney and recovered this interesting, get successful touch and we tin drawback a coffee.

---