Porting physdes: C++ → Rust 🦀

---

# 🧱 Porting physdes: C++ → Rust 🦀

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1: Project Overview** 🎯
- What is physdes?
- Architecture & Test Results

**Part 2: Data Structures** 📦
- Doubly-Linked List
- Circular Linked List

**Part 3: Geometric Primitives** 📐
- Point, Interval, Polygon

**Part 4: Polygon Ops** ✂️
- Convex Decomposition
- Convex Hull

]
.pull-right[

**Part 5: DME Algorithm** 🕰️
- Deferred Merge Embedding
- Delay Models
- Arena-Based Tree

**Part 6: Visualization** 🖼️
- Clock Tree Visualizer
- Global Router SVG

**Part 7: Routing** 🌐
- Steiner Tree Routing
- Keepout Avoidance

**Part 8: Testing** ✅
- Area-Based Testing

]

---

## 🎯 Project Overview

---

### What is physdes? 🤔

**physdes** is a polyglot geometry library for VLSI physical design:

-   **physdes-cpp** 💻 — Original C++ implementation (mature)
-   **physdes-rs** 🦀 — Rust port (this session's work)
-   **physdes-py** 🐍 — Python version

Core capabilities:

-   🧩 Points, Vectors, Intervals — basic geometric primitives
-   📐 Polygons, Rectilinear Polygons — area, convexity, monotonicity
-   ✂️ Polygon decomposition — convex/explicit/implicit cut
-   🗺️ DME algorithm — clock tree synthesis
-   🌐 Global Router — Steiner tree routing
-   ✅ Area-based verification — algorithmic correctness

---

### Architecture 🏗️

<pre>
graph TD
    subgraph Core_Geometry["Core Geometry"]
        P[Point] --> V[Vector2]
        P --> I[Interval]
        P --> PL[Polygon]
        P --> RP[RPolygon]
        RP --> RP_CUT[RPolygon Cut]
        RP --> RP_HULL[RPolygon Hull]
    end

subgraph Algorithms["Routing Algorithms"]
        DME[DME Algorithm] --> MA[ManhattanArc]
        GR[Global Router] --> RT[RoutingNode]
        GR --> RTREE[RoutingTree]
    end

subgraph Data_Structures["Data Structures"]
        DL[Dllink] --> RDL[RDllist]
    end

Core_Geometry --> Algorithms
    Data_Structures --> RP_CUT
    Data_Structures --> RP_HULL

style Core_Geometry fill:#4caf50
    style Algorithms fill:#2196f3
    style Data_Structures fill:#ff9800
</pre>

]

---

### Test Results 📊

```
test result: ok. 274 passed; 0 failed; 0 ignored
test result: ok. 62 passed; 0 failed; 0 ignored
```

**336 total tests** ✅ — All passing!

-   🧪 **274 unit tests** — geometry, algorithms, data structures, routing
-   📝 **62 doc-tests** — examples in documentation
-   ⚡ **QuickCheck** — property-based randomized testing
-   📏 **Area preservation** — signed area invariant verification

---

## 🔗 Data Structures

---

### Dllink — Doubly-Linked List Node 📎

**C++**: Self-referential pointers (`next{this}, prev{this}`)

```rust
pub struct Dllink<T> {
    next: *mut Dllink<T>,
    prev: *mut Dllink<T>,
    data: T,
}
```

**Rust adaptation**: Null-sentinel pattern 🔄

-   🚫 `new()` — creates locked node (null pointers)
-   🔒 `lock()` / `is_locked()` — sentinel state
-   ✂️ `detach()` — removes from list, re-links neighbors

> 💡 **Why null sentinel?** Rust moves values, so `self-referential` pointers become invalid. Null sentinel avoids this UB.

---

### RDllist — Circular Linked List ⭕

Contiguous storage in `Vec<Dllink<usize>>` for cache efficiency:

-   `new(n)` — creates `n` nodes linked in a circle
-   `reserve(3n)` — capacity for node insertion during decomposition
-   `from_node(k)` — iterator starting at index `k`
-   `detach` + re-iteration — works correctly after node removal

```rust
pub struct RDllist {
    cycle: Vec<Dllink<usize>>,
}
```

> ✅ Used internally by **rpolygon_cut** and **rpolygon_hull** algorithms

---

## 📐 Core Geometry

---

### Point & Vector2 🎯

Type-safe 2D arithmetic with two generic type parameters:

$$ \text{Point} = (x: T_1,\; y: T_2) \qquad
   \text{Vector2} = (dx: T_1,\; dy: T_2)$$

-   `+`, `-`, `+=`, `-=` with vectors
-   `min_dist_with(other)` — Manhattan distance via $|x_1 - x_2| + |y_1 - y_2|$
-   `rotates()`, `flip_xy()`, `flip_y()` — coordinate transforms
-   `hull_with(other)`, `intersect_with(other)` — set operations

Supports nested types: `Point<Point<i32, i32>, i32>` for 3D routing 🏗️

---

### Interval — Range Arithmetic 📏

$$ \text{Interval} = [lb, ub], \quad lb \le ub $$

Key operations:

| Operation | Math | Purpose |
|-----------|------|---------|
| `overlaps` | $[a,b] \cap [c,d] \ne \emptyset$ | Overlap detection |
| `contains` | $[a,b] \supseteq [c,d]$ | Containment check |
| `intersect_with` | $[\max(a,c), \min(b,d)]$ | Set intersection |
| `hull_with` | $[\min(a,c), \max(b,d)]$ | Convex hull |
| `enlarge_with(α)` | $[a-\alpha, b+\alpha]$ | Margin expansion |

> 🧮 Used by **ManhattanArc** for interval-based merging segments in DME

---

### Polygon & RPolygon 🔷

**Polygon** — arbitrary polygon with origin + displacement vectors

$$ \text{area} = \frac{1}{2} \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) $$

**RPolygon** — rectilinear polygon (all edges axis-aligned)

-   `signed_area()` — $O(n)$ shoelace formula
-   `is_rectilinear()` — checks each edge is horizontal or vertical
-   `to_polygon()` — inserts intermediate axis-aligned points
-   `create_mono_rpolygon()` — builds monotone polygon from point set

```rust
// Area preservation: RPolygon area × 2 = Polygon signed_area_x2
assert_eq!(original_area * 2, poly_area);
```

---

## 🗺️ Polygon Decomposition

---

### RPolygon Cut — Convex Decomposition ✂️

Splits a non-convex rectilinear polygon into convex pieces:

<pre>
graph TD
    subgraph Input["Input Polygon"]
        A[Non-convex RPolygon]
    end
    subgraph Output["Output Pieces"]
        B[Convex Piece 1]
        C[Convex Piece 2]
        D[...]
    end
    A -->|rpolygon_cut_convex| B
    A -->|rpolygon_cut_convex| C
    A -->|rpolygon_cut_convex| D

style Input fill:#ff9800
    style Output fill:#4caf50
</pre>

]

---

Four cut strategies:

| Algorithm | Method |
|-----------|--------|
| `rpolygon_cut_convex` | 🏔️ Finds concave vertices, splits recursively |
| `rpolygon_cut_explicit` | ✂️ Cuts at explicit concave corners |
| `rpolygon_cut_implicit` | 🔍 Cuts at implicit (area-based) concavity |
| `rpolygon_cut_rectangle` | 🟦 Two-pass: implicit → explicit → rectangles |

---

### Area Preservation Invariant 📏

$$ \text{Area(original)} = \sum_{\text{piece } i} \text{Area(piece}_i\text{)} $$

This is the **key correctness property**:

```rust
let original_area = rpoly.signed_area();
let convex_pieces = rpolygon_cut_convex(&points, is_anticw);
let total: i32 = convex_pieces.iter()
    .map(|p| RPolygon::new(p).signed_area())
    .sum();
assert_eq!(original_area, total); // ✅ Must hold!
```

Tested for all 4 cut strategies on:
- ✅ **Square** — already convex, returns self
- ✅ **L-shape** — 6 vertices, area = 4
- ✅ **Complex** — 12-vertex x-monotone polygon, area = 53

---

### Convex Hull — Monotone Chain 📈

**Andrew's algorithm** (monotone chain):

$$ \text{cross}(O, A, B) = (A_x - O_x)(B_y - O_y) - (A_y - O_y)(B_x - O_x) $$

```python
# Lower hull: left-to-right, keep counter-clockwise turns
for p in sorted_points:
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
        lower.pop()
    lower.append(p)
# Upper hull: right-to-left
for p in reversed(sorted_points):
    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
        upper.pop()
    upper.append(p)
```

> 🎯 **Key property**: $|\text{Area(hull)}| \ge |\text{Area(original)}|$

---

## 🕰️ DME Algorithm

---

### Deferred Merge Embedding 🕰️

The DME algorithm constructs **zero-skew clock trees** with Manhattan geometry:

<pre>
graph TD
    S1[s1] --> N1[n0]
    S2[s2] --> N1
    S3[s3] --> N2[n1]
    S4[s4] --> N2
    N1 --> N3[n2]
    N2 --> N3

style S1 fill:#4caf50
    style S2 fill:#4caf50
    style S3 fill:#4caf50
    style S4 fill:#4caf50
    style N3 fill:#f44336
</pre>

]

**Three phases**:

1. **🌲 Topology construction** — balanced bipartitioning by coordinates
2. **⬆️ Bottom-up merging** — compute Manhattan arc merging segments
3. **⬇️ Top-down embedding** — select physical positions

---

### Delay Models ⏱️

Two delay models (strategy pattern 🎯):

**Linear model** 📏

$$ \text{Delay} = \alpha \times \text{length}, \quad
   \text{Capacitance} = \beta \times \text{length} $$

**Elmore model** ⚡

$$ \text{Delay} = R_{wire} \times \left(\frac{C_{wire}}{2} + C_{load}\right) $$

```rust
let linear_calc = LinearDelayCalculator::new(0.5, 0.2);
let elmore_calc = ElmoreDelayCalculator::new(0.1, 0.2);
```

> 📚 Reference: Chao, Hsu, Ho & Kahng, "Zero skew clock routing with minimum wirelength," IEEE TCAS 1992

---

### Manhattan Arc — Merging Segment 🌀

A ManhattanArc represents all possible tapping points for zero skew:

$$ \text{Arc} = \left[\begin{array}{c} x - y \\ x + y \end{array}\right] $$

Key methods:

.font-sm.mb-xs[
| Method | Description |
|--------|-------------|
| `from_point(pt)` | Creates arc from sink location |
| `min_dist_with(other)` | $\max(d_x, d_y)$ between arcs |
| `merge_with(other, α)` | Intersection of enlarged arcs |
| `nearest_point_to(pt)` | Find closest point on arc |
| `enlarge_with(α)` | Expand arc by margin $α$ |
]

---

### Arena-Based Tree — No `Rc<RefCell>` 🚀

-   ✅ **Memory safe** — no `Rc` cycle risk, no `RefCell` borrow panics
-   ✅ **Cache friendly** — contiguous `Vec<TreeNode>` storage
-   ✅ **`get_pair_mut(a, b)`** — safe simultaneous mutable access via `split_at_mut`
-   ✅ **`DelayCalculator` trait** — takes values not `&mut TreeNode` (zero side effects)

```rust
pub struct TreeNode {
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
    parent: Option<Rc<RefCell<TreeNode>>>,
    // ...
}
```
]
.pull-right[
**After**: Arena-allocated with `usize` indices — zero overhead ✅

```rust
pub type NodeIdx = usize;

pub struct Tree {
    nodes: Vec<TreeNode>,
    pub root: Option<NodeIdx>,
}
```
]

---

### Tree Statistics 📊

```rust
pub struct SkewAnalysis {
    max_delay: f64,
    min_delay: f64,
    skew: f64,             // max - min
    sink_delays: Vec<f64>,
    total_wirelength: i32,
    delay_model: String,
}
```

The `skew` metric measures clock signal imbalance:

$$ \text{Skew} = \text{Delay}_{\max} - \text{Delay}_{\min} $$

> ✅ DME algorithm achieves **zero skew** across all tested configurations (diamond, circle, L-shape, random, long, varying caps)

---

## 🎨 SVG Visualizers

---

### DME Clock Tree Visualizer 🖼️

Built matching Python `clk_tree_vis.py`:

.font-sm.mb-xs[
| Feature | Status |
|---------|--------|
| Color-coded nodes (🔴 root, 🔵 internal, 🟢 sink) | ✅ |
| Wire length labels on edges | ✅ |
| Delay (`d:1.2`) & capacitance (`c:1.0`) annotations | ✅ |
| `<g class="clock-tree">` wrapper | ✅ |
| Side-by-side comparison (Linear vs Elmore) | ✅ |
| Analysis panel (max/min delay, skew, WL) | ✅ |
]

```rust
let viz = ClockTreeVisualizer::new();
viz.visualize_tree(dme.get_tree(), root, &sinks,
    "output.svg", 800, 600, Some(&analysis));
```

---

### Global Router SVG Visualizer 🌐

Built into `GlobalRoutingTree`:

```rust
tree.to_svg(Some(&keepouts), 800, 600, 50);
tree.save_svg(Some(&keepouts), "routing.svg", 800, 600);
```

Renders:
-   🔴 **Source**, 🔵 **Steiner nodes**, 🟢 **Terminals** with coordinates
-   🟧 **Keepout rectangles** in orange with black borders
-   ➡️ Arrow markers on connections showing routing topology
-   📊 Statistics panel: node count, wirelength, Steiner count

> 🎨 SVG files are tracked in-repo for CI visualization

---

## 🌐 Global Router

---

### Steiner Tree Routing 🌲

<pre>
graph TD
    SOURCE[Source 🔴] -->|"path"| S1[Steiner 🔵]
    SOURCE --> T2[Terminal 🟢]
    S1 --> T1[Terminal 🟢]
    S1 --> S2[Steiner 🔵]
    S2 --> T3[Terminal 🟢]

style SOURCE fill:#f44336,color:#fff
    style S1 fill:#2196f3,color:#fff
    style S2 fill:#2196f3,color:#fff
</pre>

]
]
.pull-right[

Three routing strategies:

| Strategy | Description |
|----------|-------------|
| `route_simple` | 🔗 Each terminal → nearest existing node |
| `route_with_steiners` | 🧩 Insert Steiner nodes for optimal branching |
| `route_with_constraints` | 🔒 Obey wirelength budgets per path |

]
---

### Routing Tree Structure 🏗️

```rust
pub struct RoutingNode {
    id: String,
    node_type: NodeType,  // SOURCE | STEINER | TERMINAL
    pt: Point<i32, i32>,
    children: Vec<usize>,
    parent: Option<usize>,
    path_length: i32,
}
```

**Index-based tree** (not pointer-based):

-   ✅ Memory safe — no raw pointers
-   ✅ Cache friendly — contiguous `Vec<RoutingNode>`
-   ✅ Easy serialization
-   🔄 `optimize_steiner_points()` — removes redundant Steiner nodes

---

### Keepout Avoidance 🚧

**`blocks()` vs `overlaps()`** — critical geometric distinction:

```python
# Python: blocks checks crossing pattern only
def blocks(self, other):
    return (
        contain(self.xcoord, other.xcoord) and contain(other.ycoord, self.ycoord)
        or contain(self.ycoord, other.ycoord) and contain(other.xcoord, self.xcoord)
    )
```

```rust
// Rust: same semantics — a Manhattan L-shape can go around
// simple overlap check would be too restrictive
pub fn blocks(&self, other: &Self) -> bool { ... }
```

> 🎯 **`blocks()`** allows L-shaped paths that merely touch a keepout corner. **`overlaps()`** would block them — wrong!

---

## ✅ Verification

---

### Area-Based Testing 📏

**Signed area preservation** is the cornerstone of verification:

$$
\begin{aligned}
S &= \frac{1}{2}\sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) \\[4pt]
  &= \sum_{\text{pieces } k} S_k \quad \text{(cut decomposition)} \\[4pt]
  |S_{\text{hull}}| &\ge |S_{\text{original}}| \quad \text{(convex hull)}
\end{aligned}
$$

These invariants hold for **all** cut and hull operations! ✅

---

### Hull Area Invariant 📈

<pre>
graph LR
    subgraph Shapes["Test Shapes"]
        SQ[Square\nArea = 1]
        LS[L-Shape\nArea = 4]
        CP[Complex 12-vertex\nArea = 53]
    end
    subgraph Hull_Areas["Convex Hull Areas"]
        SQ_H[Area = 1\n✅ hull = orig]
        LS_H[Area = 5\n✅ hull > orig]
        CP_H[Area = 135\n✅ hull > orig]
    end

SQ --> SQ_H
    LS --> LS_H
    CP --> CP_H

style Shapes fill:#ff9800
    style Hull_Areas fill:#4caf50
</pre>

]

]
.pull-right[
- **Square** (convex): hull area = original = 1 ✅
- **L-shape**: hull (5) > original (4) ✅
- **Complex polygon**: hull (135) > original (53) ✅
]

---

### Test Coverage Summary 🗺️

.font-sm.mb-xs[
| Module | Tests | What's Verified |
|--------|-------|-----------------|
| `dllink` | 4 🔗 | Lock, detach, pointer safety |
| `rdllist` | 9 ⭕ | Construction, iteration, detach cycle |
| `point` | 50+ 🎯 | Arithmetic, comparison, transforms |
| `vector2` | 30+ ➡️ | Dot, cross, norm, scaling |
| `interval` | 20+ 📏 | Overlap, containment, intersection |
| `polygon` | 20+ 🔷 | Area, convexity, rectilinearity |
| `rpolygon` | 30+ 🔶 | Cut, hull, to_polygon, area preservation |
| `manhattan_arc` | 6 🌀 | Construction, distance, enlargement |
| `vlsi_ops` | 15+ 🏭 | Rectangle overlap, spacing, line sweep |
]

**206 unit tests** + **62 doc-tests** = **268 total** ✅

---

## 🏁 Conclusion

---

### Key Takeaways 🎯

-   🦀 **Rust forces safer design** — null-sentinel instead of self-referential pointers
-   📏 **Area invariance is powerful** — catches algorithmic errors in cut/hull
-   🧩 **Polyglot strategy works** — C++ → Rust port completed with **336 passing tests**
-   ⚡ **Monotone chain hull** — simpler and correct vs. complex linked-list algorithm
-   🎨 **SVG visualizers** for DME clock trees and global routing trees
-   🏗️ **Arena-based trees** — `Rc<RefCell>` replaced with `Vec<TreeNode>` + indices

### What's Next? 🚀

-   🔄 Implement full recursive rpolygon_cut algorithms (currently stubs)
-   🎯 Coverage improvement towards 90%+
-   📦 Publish to crates.io
-   🔗 Cross-language test harness (C++ vs Rust vs Python)

---

# Thank You! 🙏

### 🧱 physdes-rs: C++ → Rust Porting

https://github.com/luk036/physdes-rs

---

## Q&A 🎤