HAL  v4.5.0-283-g3f42a39fa
The Hardware Analyzer - a comprehensive reverse engineering and manipulation framework for gate-level netlists.
clock_tree_layout.cpp
Go to the documentation of this file.
1 // MIT License
2 //
3 // Copyright (c) 2019 Ruhr University Bochum, Chair for Embedded Security. All Rights reserved.
4 // Copyright (c) 2019 Marc Fyrbiak, Sebastian Wallat, Max Hoffmann ("ORIGINAL AUTHORS"). All rights reserved.
5 // Copyright (c) 2021 Max Planck Institute for Security and Privacy. All Rights reserved.
6 // Copyright (c) 2021 Jörn Langheinrich, Julian Speith, Nils Albartus, René Walendy, Simon Klix ("ORIGINAL AUTHORS"). All Rights reserved.
7 // Copyright (c) 2025-2026 Sascha Tommasone. All rights reserved.
8 //
9 // Permission is hereby granted, free of charge, to any person obtaining a copy
10 // of this software and associated documentation files (the "Software"), to deal
11 // in the Software without restriction, including without limitation the rights
12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 // copies of the Software, and to permit persons to whom the Software is
14 // furnished to do so, subject to the following conditions:
15 //
16 // The above copyright notice and this permission notice shall be included in all
17 // copies or substantial portions of the Software.
18 //
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 // SOFTWARE.
26 
28 
31 #include "hal_core/netlist/gate.h"
32 
33 #include <algorithm>
34 #include <cmath>
35 #include <string>
36 #include <unordered_map>
37 
38 namespace hal::ctv
39 {
40  namespace
41  {
42  // The sizes of the drawing follow from the length of a typical connection, because that decides how large a
43  // node can be before it touches its neighbours. The ratios are those of a clock tree with connections of
44  // about 25 um that is drawn with a node radius of 1 um, a line width of 0.5 um, a picture margin of 20 um and
45  // 2 pixels per um.
46  constexpr double REFERENCE_EDGE_LENGTH = 25.0;
47  constexpr double NODE_RADIUS_RATIO = 1.0 / REFERENCE_EDGE_LENGTH;
48  constexpr double EDGE_WIDTH_RATIO = 0.5 / REFERENCE_EDGE_LENGTH;
49  constexpr double PICTURE_MARGIN_RATIO = 20.0 / REFERENCE_EDGE_LENGTH;
50  constexpr double EDGE_PICTURE_PIXELS = 2.0 * REFERENCE_EDGE_LENGTH;
51 
52  // Without a single connection there is no typical one, a tenth of the extent of the gates takes its place.
53  constexpr double EXTENT_RATIO = 0.1;
54 
55  struct Bounds
56  {
57  double min_x;
58  double max_x;
59  double min_y;
60  double max_y;
61  };
62 
63  Bounds bounds_of( const Layout &layout )
64  {
65  const Node &first = layout.nodes.front();
66  Bounds bounds = { first.x, first.x, first.y, first.y };
67 
68  for( const Node &node : layout.nodes )
69  {
70  bounds.min_x = std::min( bounds.min_x, node.x );
71  bounds.max_x = std::max( bounds.max_x, node.x );
72  bounds.min_y = std::min( bounds.min_y, node.y );
73  bounds.max_y = std::max( bounds.max_y, node.y );
74  }
75 
76  return bounds;
77  }
78 
79  double typical_edge_length( const Layout &layout )
80  {
81  std::vector<double> lengths;
82  lengths.reserve( layout.edges.size() );
83 
84  for( const Edge &edge : layout.edges )
85  {
86  const Node &from = layout.nodes[edge.from];
87  const Node &to = layout.nodes[edge.to];
88 
89  if( const double length = std::hypot( to.x - from.x, to.y - from.y ); length > 0.0 )
90  {
91  lengths.push_back( length );
92  }
93  }
94 
95  if( !lengths.empty() )
96  {
97  const auto middle = lengths.begin() + lengths.size() / 2;
98  std::nth_element( lengths.begin(), middle, lengths.end() );
99  return *middle;
100  }
101 
102  const Bounds bounds = bounds_of( layout );
103  const double extent = std::max( bounds.max_x - bounds.min_x, bounds.max_y - bounds.min_y );
104 
105  return extent > 0.0 ? EXTENT_RATIO * extent : 1.0;
106  }
107 
108  bool is_valid( const std::optional<double> &value, const bool allow_zero )
109  {
110  return !value.has_value() || ( std::isfinite( *value ) && ( allow_zero ? *value >= 0.0 : *value > 0.0 ) );
111  }
112  } // namespace
113 
115  const std::optional<std::string> &x_key,
116  const std::optional<std::string> &y_key )
117  {
118  if( x_key.has_value() != y_key.has_value() )
119  {
120  return ERR( "give the parameter names of both coordinates or of none" );
121  }
122 
123  std::vector<const Gate *> gates = tree.get_gates();
124  if( gates.empty() )
125  {
126  return ERR( "the clock tree contains no gates" );
127  }
128 
129  // The clock tree keeps its gates in a hash map, sort them to get the same layout every time.
130  std::sort(
131  gates.begin(), gates.end(), []( const Gate *a, const Gate *b ) { return a->get_id() < b->get_id(); } );
132 
133  Layout layout;
134  std::unordered_map<const Gate *, std::size_t> node_of_gate;
135 
136  for( const Gate *gate : gates )
137  {
138  // Coordinates from gate parameters can be negative, a location in HAL can't.
139  std::optional<double> x;
140  std::optional<double> y;
141  if( x_key.has_value() )
142  {
143  x = cte::read_parameter_coordinate( gate, *x_key );
144  y = cte::read_parameter_coordinate( gate, *y_key );
145  }
146  else if( gate->has_location() )
147  {
148  x = gate->get_location_x();
149  y = gate->get_location_y();
150  }
151 
152  if( !x.has_value() || !y.has_value() )
153  {
154  layout.gates_without_coordinates.push_back( gate->get_id() );
155  continue;
156  }
157 
158  node_of_gate[gate] = layout.nodes.size();
159  layout.nodes.push_back( { gate->get_id(), *x, *y } );
160  }
161 
162  if( layout.nodes.empty() )
163  {
164  const std::string expected = x_key.has_value() ? "the gate parameters '" + *x_key + "' and '" + *y_key + "'"
165  : std::string( "a location in the layout" );
166  return ERR( "none of the " + std::to_string( gates.size() )
167  + " gates of the clock tree has coordinates, expected " + expected );
168  }
169 
170  // Nets are not drawn, so the only connections left are those between gates.
171  for( const Gate *gate : gates )
172  {
173  const auto successors = tree.get_neighbors( gate, IGRAPH_OUT );
174  if( successors.is_error() )
175  {
176  return ERR( "could not read the successors of gate with ID " + std::to_string( gate->get_id() ) + ": "
177  + successors.get_error().get() );
178  }
179 
180  for( const auto &[ptr, type] : successors.get() )
181  {
182  if( type != cte::PtrType::GATE )
183  {
184  continue;
185  }
186 
187  const auto from = node_of_gate.find( gate );
188  const auto to = node_of_gate.find( static_cast<const Gate *>( ptr ) );
189 
190  if( from == node_of_gate.end() || to == node_of_gate.end() )
191  {
192  layout.omitted_edges++;
193  continue;
194  }
195 
196  layout.edges.push_back( { from->second, to->second } );
197  }
198  }
199 
200  return OK( std::move( layout ) );
201  }
202 
203  Result<Style> resolve_style( const Layout &layout, const StyleOverrides &overrides )
204  {
205  if( layout.nodes.empty() )
206  {
207  return ERR( "the layout has no gates to size the drawing after" );
208  }
209  if( !is_valid( overrides.node_radius, false ) )
210  {
211  return ERR( "node_radius must be a positive number" );
212  }
213  if( !is_valid( overrides.edge_width, false ) )
214  {
215  return ERR( "edge_width must be a positive number" );
216  }
217  if( !is_valid( overrides.picture_margin, true ) )
218  {
219  return ERR( "picture_margin must not be negative" );
220  }
221  if( !is_valid( overrides.pixels_per_unit, false ) )
222  {
223  return ERR( "pixels_per_unit must be a positive number" );
224  }
225 
226  const double length = typical_edge_length( layout );
227 
228  Style style;
229  style.node_radius = overrides.node_radius.value_or( NODE_RADIUS_RATIO * length );
230  style.edge_width = overrides.edge_width.value_or( EDGE_WIDTH_RATIO * length );
231  style.picture_margin = overrides.picture_margin.value_or( PICTURE_MARGIN_RATIO * length );
232 
233  // A typical connection gets the same number of pixels in every picture. The scene lowers this for a picture that
234  // would be larger than allowed, which only it can tell.
235  style.pixels_per_unit = overrides.pixels_per_unit.value_or( EDGE_PICTURE_PIXELS / length );
236  style.pixels_per_unit_is_fixed = overrides.pixels_per_unit.has_value();
237 
238  return OK( style );
239  }
240 } // namespace hal::ctv
Definition: gate.h:59
std::vector< const Gate * > get_gates() const
Definition: clock_tree.cpp:679
Result< std::vector< std::pair< const void *, PtrType > > > get_neighbors(const void *ptr, igraph_neimode_t direction) const
Definition: clock_tree.cpp:735
double min_x
double max_y
double min_y
double max_x
#define ERR(message)
Definition: result.h:60
#define OK(...)
Definition: result.h:56
S to(const T &str)
std::optional< double > read_parameter_coordinate(const Gate *gate, const std::string &name)
Definition: utils.cpp:94
Result< Layout > build_layout(const cte::ClockTree &tree, const std::optional< std::string > &x_key=std::nullopt, const std::optional< std::string > &y_key=std::nullopt)
Result< Style > resolve_style(const Layout &layout, const StyleOverrides &overrides)
PinType type
std::vector< u32 > gates_without_coordinates
std::size_t omitted_edges
std::vector< Node > nodes
std::vector< Edge > edges
std::optional< double > edge_width
std::optional< double > pixels_per_unit
std::optional< double > node_radius
std::optional< double > picture_margin