fastroute: A Fast, Open-Source PCB Autorouter for KiCad (Porting Freerouting to Rust)

The longest part of designing a printed circuit board (PCB) is often the routing: turning hundreds of connections into copper traces that never come closer to each other than a set distance, changing layers through vias. The open-source tool KiCad users have turned to for years is Freerouting, an autorouter written in Java. fastroute is Freerouting ported to Rust: the same algorithms, the same input and output (Specctra .dsn → .ses), the same command line; but without Java, several times faster and with a fraction of the memory.

In this post I go through the project from start to finish: why and how I ported it, what it means to produce results "byte-identical" to Java, the speed-ups that do not change the result, the bugs that were fixed, and the new features Freerouting does not have (length matching, differential pairs, controlled impedance, a live view). I took the live-view screenshots by running the project on my own machine; everywhere I say which measurements are mine and which come from the project's documents.

Project site: fastroute.baltavista.com · source code: github.com/parisxmas/fastroute. (Beware the similar name: it is not related to the FastRoute global router for IC design used in OpenROAD.)

Why rewrite Freerouting?

Freerouting is a good router; its algorithms have matured over the years and been tried on many real boards. But using it, three things kept coming up:

1. Java. Using the KiCad plugin needs a separate Java runtime: installation, version mismatches, and gigabytes of memory on large boards.
2. Speed. A medium-sized board can take minutes, a large one hours.
3. Bugs. As I read the code I found bugs that directly affect the result and had been sitting there for years. For example, when the autorouter stops itself the optimizer never runs at all, because the stop request stays set and every optimizer candidate fails as "stopped".

Instead of writing a new router from scratch, I chose to port Freerouting faithfully. The biggest advantage is that it is measurable: the question "is the port correct?" has a definite answer. Given the same board with the same settings, if it produces the same output as Java, it is correct. I only put the speed-ups and improvements on top of that solid ground.

Project layout

fastroute is a Cargo workspace: about 70,000 lines of Rust, plus about 2,400 lines of Python for the KiCad plugin:

The port went bottom-up in units: first the Java compatibility layer, data structures, rules and library; then board items and search trees (about 13,000 Java lines), DRC and scoring, optimization and the routing board, the autorouting core (expansion rooms, maze search, path finding) and finally the pipeline. The first commit was on 27 September; 82 commits later, version 0.1.13 came out on 7 October.

What does "byte-identical" mean?

In --parity mode fastroute produces an SES file byte-identical to the one Freerouting's deterministic mode writes (single-threaded optimizer, count-based time limits). Before writing that claim I tried it myself. I routed the interf_u board from the KiCad demos on my Apple M4 with fastroute 0.1.13 in --parity mode and compared the output with the Java reference output kept in the project:

$ fastroute -de interf_u.dsn -do interf.ses --parity
...
   12.563 INFO  routing finished in 12.55 s

$ cmp reference/parity-baseline/interf_u.ses interf.ses && echo IDENTICAL
IDENTICAL
$ shasum -a 256 reference/parity-baseline/interf_u.ses interf.ses
2e174236513ccab65daa…  reference/parity-baseline/interf_u.ses
2e174236513ccab65daa…  interf.ses

Getting there takes much more than porting the algorithms correctly. The router's result depends on the finest behaviours of Java's standard library. For example:

• Random numbers. The optimizer and order shuffles use java.util.Random and Collections.shuffle. Reproducing the same order needs an exact copy of the 48-bit linear congruential generator and of the overflow-based rejection loop in nextInt(bound).
• Non-transitive comparators. In some places Java's TreeMap is used with comparators that are not mathematically transitive. The result then depends on the tree's red-black structure, so TreeMap was rewritten on its own, with the same balancing rules.
• Hash order. Iteration order over a HashMap<Integer, …> affects the result in exactly one place; there, Java's iteration order is emulated.
• Floating point. Operation order is kept and no mul_add (fused multiply-add) is used; scores are computed in f32 with the same casts as in Java; DoubleStream.sum's compensated summation and fdlibm (libm) for trigonometry are used.
• String comparison. String.compareTo works on UTF-16 code units.
• The shape of the search tree. Some geometric queries walk the tree themselves and shrink the query as they go; the visiting order changes the rooms produced. So the Rust MinAreaTree reproduces the exact shape of Java's tree.

Here is a piece of the java.util.Random port in fr-jcompat. Java's rejection condition, which relies on integer overflow, is written out explicitly in Rust with wrapping_sub and wrapping_add:

/// `protected int next(int bits)`, `1 <= bits <= 32`.
#[inline]
pub fn next(&mut self, bits: u32) -> i32 {
    debug_assert!((1..=32).contains(&bits));
    self.seed = self.seed.wrapping_mul(Self::MULTIPLIER).wrapping_add(Self::ADDEND) & Self::MASK;
    // (int) (nextseed >>> (48 - bits))
    ((self.seed as u64) >> (48 - bits)) as i32
}

/// `Random.nextInt(int bound)`. Panics if `bound <= 0` (Java throws `IllegalArgumentException`).
pub fn next_int_bound(&mut self, bound: i32) -> i32 {
    assert!(bound > 0, "bound must be positive");
    let mut r = self.next(31);
    let m = bound - 1;
    if (bound & m) == 0 {
        // power of two
        r = ((bound as i64 * r as i64) >> 31) as i32;
    } else {
        let mut u = r;
        loop {
            r = u % bound;
            // Java relies on int overflow to reject values from the incomplete last range.
            if u.wrapping_sub(r).wrapping_add(m) >= 0 {
                break;
            }
            u = self.next(31);
        }
    }
    r
}

Correctness was checked layer by layer: a canonical dump of the board after loading, bit-exact statistics, per-connection trace markers, per-pass hash and score, and finally the SES diff. The first big milestone was the "unrouted" SES written with routing switched off being identical to Java on all 20 benchmark boards; the DSN reader was also tested against 2,470 sample files. Then came the full pipeline: in --parity mode, 20 of 20 boards are byte-identical to Java.

The one thing deliberately not ported is the bugs in Java's DSN reader. In 12 of the sample files the JFlex scanner drops non-ASCII letters from names, loses sync on some quoted strings, or shifts one character of a pin name onto the next pin. fastroute reads these correctly, so those boards cannot be compared with Java.

The live view

The first thing Freerouting does not have: watching the board being routed in your browser. With --live, fastroute opens a local page that needs no internet. Traces appearing and being ripped up, the remaining connections (airlines), the progress of every pass, a chart of unrouted connections per pass, clearance violations, the score and the log are all there. There is zoom, layer toggles, net highlighting and a "Stop" button that keeps the best result. The results are the same with or without the live view.

The frame above is from pass 4 of the interf_u board. The green traces are the ones placed in that pass, the white lines the connections not yet routed. The board starts with 159 connections and drops below 20 in the first pass, as the chart on the right shows. In the final state in the cover image, all 159 connections are routed with no violations.

As a harder example I ran the 6-layer CM5_MINIMA_3 board (a carrier board for the Raspberry Pi Compute Module 5). This board cannot be routed completely. For the remaining connections fastroute reruns the router in parallel with different orders in its multi-start stage:

The run finished in 41 seconds on my machine, with 7 of 88 connections left. That matches exactly the "CM5: 8 → 7 unrouted" improvement in the project's documents; the one remaining violation is a pre-existing one, between two fixed items in the loaded design.

Speeding up without changing the result

Once the port worked correctly, the speed-ups began. The rule was simple: no step may change the result. After every step, all tests, the full pipeline on 10 boards, and the parallel optimizer giving the same result on 1 and 8 threads were checked. With FASTROUTE_VERIFY_CACHES=1, every memoized or indexed result is also computed the old way and compared. The highlights:

• Memoized contact lists, cached by content "epochs" of the item repository and the search tree. CM5: 22.7 → 13.7 s; the fanout stage alone 18.9 → 1.8 s.
• Layer masks in the search tree. Each leaf carries the bit of its layer, inner nodes the union; queries that do not care about another layer skip whole subtrees. CM5: 13.4 → 10.5 s.
• A secondary spatial index. A hierarchical grid per layer over the leaf ranges; Java's sorted result is kept exactly.
• Copy-free intersection tests in geometry, getting rid of an O(n²) in the shove checks, and the mimalloc allocator.
• Streaming in the parallel optimizer: candidates are handed out to threads in order and results are consumed strictly in candidate order, so the result is independent of the thread count.
• Profile-guided optimization (PGO): a build trained on its own boards, another 13–18 %.

In the project's own measurements (M-series Mac, exact mode, JVM start-up included) the sum of 20 boards goes from 2,102 seconds to 420 seconds, about 5 times. The speed-up per board ranges from 3 to 60 times. My own measurement for interf_u:

The default mode runs the optimizer in parallel. Its results are not identical to Java's, but they are deterministic for any thread count. Memory in parallel mode got attention of its own: a board copy used to be a 37 MB deep copy. Items and tree nodes were split into chunks of 64 copied on write (CowVec), and a copy now costs 1–3 MB. On an 874-part, 6-layer test board, peak memory dropped from 2,593 MB to 1,103 MB.

Bugs fixed

A nice side effect of a faithful port is that the bugs in the Java code become plainly visible. They are fixed by default (--parity keeps Freerouting's behaviour exactly). Some of them:

A better router

Beyond the bugs, routing and optimization were improved too:

• Parallel autorouting passes. Freerouting routes the connections of a pass one after another. fastroute works on up to two connections per thread at a time, each on a copy of the board as it was when the connection started, and commits the results in start order. On the 874-part test board the routing stage went from 1,413 s to 508 s with 8 threads.
• Multi-start (--multi-start). If connections remain, the router is rerun in parallel with shuffled orders and the best result is kept (bm05: 7 → 2, StickHub: 3 → 1 unrouted).
• Undoing bad passes. A pass that ends far worse than the best pass so far is undone; Java kept going from the worse board.
• The optimizer on partly routed boards (Freerouting skips the optimizer if even one connection remains) and greedy passes that apply not just the single best candidate per pass but the other improving ones too.
• Checkpoints and time limits. The session file always holds the best board so far; --max-time, Ctrl+C or SIGTERM stop the run and keep the result.
• Diagnosis. --report writes a JSON summary with every unrouted connection and violation. --diagnose routes each unrouted connection again on its own and classifies the reason: are other traces in the way (congestion), or is it the geometry or the rules (blocked)?

Length matching

Freerouting has no length matching. After routing and optimizing, fastroute can match groups of nets (a memory bus, for example). The target is the longest net of the group or a given length. Serpentine meanders are added to the longest straight segments of the shorter nets. Every meander is tried on a board copy and kept only if a slightly wider probe trace has no clearance violation, so the result stays clean in KiCad's DRC too. As KiCad does, the stackup height a via crosses is added to the length.

Differential pairs

Freerouting routes the two nets of a pair independently, so they rarely run side by side. With --pairs, fastroute routes the pairs first on the empty board and makes one net follow the other at the pair gap. The lead net's traces are chained and offset sideways, the offset path is clearance-checked in 0.2 mm pieces, the free pieces become the follower's traces, and the maze router joins them to the pins. The change is kept only if no connection is lost and the score "coupled length − 0.5 × length difference" improves. Finally the shorter net gets meanders until the two lengths are within tolerance.

On the project's STM32H7 test board (4 layers, USB and two Ethernet pairs) the intra-pair skews went from 1.8 / 2.7 / 14.5 mm to 0.1 / 0.25 / 0.25 mm, with no unrouted connections and no KiCad DRC errors left.

Controlled impedance

Freerouting has one trace width per net class and layer; it knows nothing about impedance. impedance_cli.py in fastroute's KiCad plugin computes trace widths from the board's stackup. Outer layers are computed as microstrip (Hammerstad–Jensen with Wadell's thickness correction), inner layers as stripline (Wheeler); differential pairs get the IPC-2141 coupling term. The widths are written into .kicad_dru rules that KiCad's DRC checks. The router switches off neck-down at pins for those classes, which would otherwise break the width. On the test board, the 30 width errors on the 50 Ω class went to zero.

The KiCad plugin

The plugin exports the board, fills the gaps in KiCad's Specctra export, runs the router and imports the result. That takes far more detail than it seems at first:

• .kicad_dru rules are carried over: class-to-class clearances, per-layer track widths, length and skew rules, differential pair gaps; the minimum track width and copper-to-edge clearance too.
• KiCad exports every zone as a plane and every rule area as a keepout. The plugin corrects these and refills the zones after routing. Because rule areas that forbid nothing were closing whole channels, Freerouting left 160 connections unrouted on the multichannel_mixer demo; with the plugin, zero.
• Copper texts, hole clearance rules and the local clearances of pads without a net become keepouts; zone stitching vias are kept.
• The result is checked with KiCad's own DRC. On the KiCad demos, after re-routing from scratch:

The remaining violations (pads close to the board edge, thermal spokes) exist in the original designs as well.

Boards routed by fastroute

The example boards on the site were all routed by fastroute. The STM32H7 control board (4 layers, 158 nets, SDRAM, Ethernet, USB) was routed in about three minutes, with zero unrouted connections and zero KiCad DRC errors:

Installing

The plugin package for KiCad 7 and newer is on the GitHub releases page. It installs with "Install from File" in KiCad's Plugin and Content Manager; binaries for Windows, macOS (Apple Silicon and Intel) and Linux (x64 and ARM64) are inside the package, and no Java is needed. fastroute also runs on its own from the command line, on any Specctra DSN file:

# route, write the result to board.ses
fastroute -de board.dsn -do board.ses

# stop after 10 minutes, keep the best result
fastroute -de board.dsn -do board.ses --max-time=600

# watch it route in the browser
fastroute -de board.dsn -do board.ses --live

# exactly Freerouting's result
fastroute -de board.dsn -do board.ses --parity

Freerouting's options (-mp, --router.*) work as before. To build from source, cargo build --release -p fastroute is enough; scripts/build-pgo.sh produces a build that is about 15 % faster.

Conclusion

fastroute showed me something again: when porting a large piece of software, the most valuable tool is a definite measure of correctness. The "byte-identical to Java" goal made the work harder; everything from Java's random number generator to the balancing rules of TreeMap had to be emulated. But thanks to that goal I could prove that each speed-up did not break the result, and tell every bug apart as "a porting bug, or Freerouting's own?". What came out is a tool that routes the same boards five times faster, without Java and with far less memory, and adds on top the features real boards need.

fastroute is free software under GPL-3.0-or-later and a derivative work of Freerouting; the credit for the routing algorithms goes to the Freerouting authors. I develop it in my spare time. If it helps you, you can support it through GitHub Sponsors or Open Collective; bug reports with a board that shows the problem are just as welcome (a .dsn file is enough). I would be glad to hear your questions on X or LinkedIn.