KiCad PCB EDA Suite
drc_test_provider_diff_pair_coupling.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2004-2020 KiCad Developers.
5  *
6  * This program is free software: you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License as published by the
8  * Free Software Foundation, either version 3 of the License, or (at your
9  * option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License along
17  * with this program. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 
21 #include <common.h>
22 #include <board.h>
23 #include <track.h>
24 
25 #include <drc/drc_engine.h>
26 #include <drc/drc_item.h>
27 #include <drc/drc_rule.h>
28 #include <drc/drc_test_provider.h>
29 #include <drc/drc_length_report.h>
30 #include <drc/drc_rtree.h>
31 
32 #include <geometry/shape_segment.h>
33 
36 
37 
38 /*
39  Differential pair gap/coupling test.
40  Errors generated:
41  - DRCE_DIFF_PAIR_GAP_OUT_OF_RANGE
42  - DRCE_DIFF_PAIR_UNCOUPLED_LENGTH_TOO_LONG
43  - DRCE_TOO_MANY_VIAS
44  Todo:
45  - arc support.
46  - improve recognition of coupled segments (now anything that's parallel is considered
47  coupled, causing DRC errors on meanders)
48 */
49 
50 namespace test {
51 
53 {
54 public:
56  m_board( nullptr )
57  {
58  }
59 
61  {
62  }
63 
64  virtual bool Run() override;
65 
66  virtual const wxString GetName() const override
67  {
68  return "diff_pair_coupling";
69  };
70 
71  virtual const wxString GetDescription() const override
72  {
73  return "Tests differential pair coupling";
74  }
75 
76  virtual int GetNumPhases() const override
77  {
78  return 1;
79  }
80 
81  virtual std::set<DRC_CONSTRAINT_T> GetConstraintTypes() const override;
82 
83 private:
84 
86 };
87 
88 };
89 
90 
91 static bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip )
92 {
93  SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
94 
95  int64_t t_a = 0;
96  int64_t t_b = p.TCoef( p.B );
97 
98  int64_t tproj_a = p.TCoef( n_proj_p.A );
99  int64_t tproj_b = p.TCoef( n_proj_p.B );
100 
101  if( t_b < t_a )
102  std::swap( t_b, t_a );
103 
104  if( tproj_b < tproj_a )
105  std::swap( tproj_b, tproj_a );
106 
107  if( t_b <= tproj_a )
108  return false;
109 
110  if( t_a >= tproj_b )
111  return false;
112 
113  int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
114  std::vector<int64_t> tv( t, t + 4 );
115  std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
116 
117  int64_t pLenSq = p.SquaredLength();
118 
119  VECTOR2I dp = p.B - p.A;
120  pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
121  pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
122 
123  pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
124  pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
125 
126  nClip.A = n.LineProject( pClip.A );
127  nClip.B = n.LineProject( pClip.B );
128 
129  return true;
130 }
131 
132 
134 {
135  bool operator<( const DIFF_PAIR_KEY& b ) const
136  {
137  if( netP < b.netP )
138  {
139  return true;
140  }
141  else if( netP > b.netP )
142  {
143  return false;
144  }
145  else // netP == b.netP
146  {
147  if( netN < b.netN )
148  return true;
149  else if( netN > b.netN )
150  return false;
151  else
152  return parentRule < b.parentRule;
153  }
154  }
155 
156  int netP, netN;
158 };
159 
161 {
169 
171  parentN( nullptr ),
172  parentP( nullptr ),
173  computedGap( 0 ),
175  couplingOK( false )
176  {}
177 };
178 
180 {
181  std::set<BOARD_CONNECTED_ITEM*> itemsP, itemsN;
182  std::vector<DIFF_PAIR_COUPLED_SEGMENTS> coupled;
186 };
187 
189 {
190  for( BOARD_CONNECTED_ITEM* itemP : aDp.itemsP )
191  {
192  TRACK* sp = dyn_cast<TRACK*>( itemP );
194  int bestGap = std::numeric_limits<int>::max();
195 
196  if(!sp)
197  continue;
198 
199  for ( BOARD_CONNECTED_ITEM* itemN : aDp.itemsN )
200  {
201  auto sn = dyn_cast<TRACK*> ( itemN );
202 
203  if(!sn)
204  continue;
205 
206  if( ( sn->GetLayerSet() & sp->GetLayerSet() ).none() )
207  continue;
208 
209  SEG ssp ( sp->GetStart(), sp->GetEnd() );
210  SEG ssn ( sn->GetStart(), sn->GetEnd() );
211 
212  if( ssp.ApproxParallel(ssn) )
213  {
215  bool coupled = commonParallelProjection( ssp, ssn, cpair.coupledP, cpair.coupledN );
216 
217  if( coupled )
218  {
219  cpair.parentP = sp;
220  cpair.parentN = sn;
221  cpair.layer = sp->GetLayer();
222 
223  int gap = (cpair.coupledP.A - cpair.coupledN.A).EuclideanNorm();
224  if( gap < bestGap )
225  {
226  bestGap = gap;
227  bestCoupled = cpair;
228  }
229  }
230 
231  }
232  }
233 
234  if( bestCoupled )
235  {
236  auto excludeSelf =
237  [&] ( BOARD_ITEM *aItem )
238  {
239  if( aItem == bestCoupled->parentN || aItem == bestCoupled->parentP )
240  {
241  return false;
242  }
243 
244  if( aItem->Type() == PCB_TRACE_T || aItem->Type() == PCB_VIA_T )
245  {
246  auto bci = static_cast<BOARD_CONNECTED_ITEM*>( aItem );
247 
248  if( bci->GetNetCode() == bestCoupled->parentN->GetNetCode()
249  || bci->GetNetCode() == bestCoupled->parentP->GetNetCode() )
250  return false;
251  }
252 
253  return true;
254  };
255 
256  SHAPE_SEGMENT checkSegStart( bestCoupled->coupledP.A, bestCoupled->coupledN.A );
257  SHAPE_SEGMENT checkSegEnd( bestCoupled->coupledP.B, bestCoupled->coupledN.B );
258 
259  // check if there's anyting in between the segments suspected to be coupled. If
260  // there's nothing, assume they are really coupled.
261 
262  if( !aTree.CheckColliding( &checkSegStart, sp->GetLayer(), 0, excludeSelf )
263  && !aTree.CheckColliding( &checkSegEnd, sp->GetLayer(), 0, excludeSelf ) )
264  {
265  aDp.coupled.push_back( *bestCoupled );
266  }
267  }
268  }
269 }
270 
271 
272 
274 {
276 
277 
278 
279  std::map<DIFF_PAIR_KEY, DIFF_PAIR_ITEMS> dpRuleMatches;
280 
281  auto evaluateDpConstraints =
282  [&]( BOARD_ITEM *item ) -> bool
283  {
284  DIFF_PAIR_KEY key;
285  BOARD_CONNECTED_ITEM* citem = static_cast<BOARD_CONNECTED_ITEM*>( item );
286  NETINFO_ITEM* refNet = citem->GetNet();
287 
288  if( refNet && DRC_ENGINE::IsNetADiffPair( m_board, refNet, key.netP, key.netN ) )
289  {
290  drc_dbg( 10, "eval dp %p\n", item );
291 
292  const DRC_CONSTRAINT_T constraintsToCheck[] = {
295  };
296 
297  for( int i = 0; i < 2; i++ )
298  {
299  auto constraint = m_drcEngine->EvalRules( constraintsToCheck[ i ], item,
300  nullptr, item->GetLayer() );
301 
302  if( constraint.IsNull() )
303  continue;
304 
305  drc_dbg( 10, "cns %d item %p\n", constraintsToCheck[i], item );
306 
307  key.parentRule = constraint.GetParentRule();
308 
309  if( refNet->GetNetCode() == key.netN )
310  dpRuleMatches[key].itemsN.insert( citem );
311  else
312  dpRuleMatches[key].itemsP.insert( citem );
313  }
314  }
315 
316  return true;
317  };
318 
319  m_board->GetConnectivity()->GetFromToCache()->Rebuild( m_board );
320 
322  LSET::AllCuMask(), evaluateDpConstraints );
323 
324  drc_dbg( 10, "dp rule matches %d\n", (int) dpRuleMatches.size() );
325 
326 
327  DRC_RTREE copperTree;
328 
329  auto addToTree =
330  [&copperTree]( BOARD_ITEM *item ) -> bool
331  {
332  copperTree.Insert( item );
333  return true;
334  };
335 
337  LSET::AllCuMask(), addToTree );
338 
339 
340  reportAux( wxString::Format( _("DPs evaluated:") ) );
341 
342  for( auto& it : dpRuleMatches )
343  {
344  NETINFO_ITEM *niP = m_board->GetNetInfo().GetNetItem( it.first.netP );
345  NETINFO_ITEM *niN = m_board->GetNetInfo().GetNetItem( it.first.netN );
346 
347  assert( niP );
348  assert( niN );
349 
350  wxString nameP = niP->GetNetname();
351  wxString nameN = niN->GetNetname();
352 
353  reportAux( wxString::Format( "Rule '%s', DP: (+) %s - (-) %s",
354  it.first.parentRule->m_Name, nameP, nameN ) );
355 
356  extractDiffPairCoupledItems( it.second, copperTree );
357 
358  it.second.totalCoupled = 0;
359  it.second.totalLengthN = 0;
360  it.second.totalLengthP = 0;
361 
362  drc_dbg(10, " coupled prims : %d\n", (int) it.second.coupled.size() );
363 
364  OPT<DRC_CONSTRAINT> gapConstraint =
365  it.first.parentRule->FindConstraint( DIFF_PAIR_GAP_CONSTRAINT );
366  OPT<DRC_CONSTRAINT> maxUncoupledConstraint =
367  it.first.parentRule->FindConstraint( DIFF_PAIR_MAX_UNCOUPLED_CONSTRAINT );
368 
369  for( auto& item : it.second.itemsN )
370  {
371  // fixme: include vias
372  if( auto track = dyn_cast<TRACK*>( item ) )
373  it.second.totalLengthN += track->GetLength();
374  }
375 
376  for( auto& item : it.second.itemsP )
377  {
378  // fixme: include vias
379  if( auto track = dyn_cast<TRACK*>( item ) )
380  it.second.totalLengthP += track->GetLength();
381  }
382 
383  for( auto& cpair : it.second.coupled )
384  {
385  int length = cpair.coupledN.Length();
386  int gap = cpair.coupledN.Distance( cpair.coupledP );
387 
388  gap -= cpair.parentN->GetWidth() / 2;
389  gap -= cpair.parentP->GetWidth() / 2;
390 
391  cpair.computedGap = gap;
392 
394 
395  if( overlay )
396  {
397  overlay->SetIsFill(false);
398  overlay->SetIsStroke(true);
399  overlay->SetStrokeColor( RED );
400  overlay->SetLineWidth( 100000 );
401  overlay->Line( cpair.coupledP );
402  overlay->SetStrokeColor( BLUE );
403  overlay->Line( cpair.coupledN );
404  }
405 
406  drc_dbg( 10, " len %d gap %d l %d\n", length, gap,
407  cpair.parentP->GetLayer() );
408 
409  if( gapConstraint )
410  {
411  auto val = gapConstraint->GetValue();
412  bool insideRange = true;
413  if ( val.HasMin() && gap < val.Min() )
414  insideRange = false;
415  if ( val.HasMax() && gap > val.Max() )
416  insideRange = false;
417 
418 // if(val.HasMin() && val.HasMax() )
419  // drc_dbg(10, "Vmin %d vmax %d\n", val.Min(), val.Max() );
420 
421  cpair.couplingOK = insideRange;
422 
423  if( insideRange )
424  it.second.totalCoupled += length;
425  }
426  }
427 
428  int totalLen = std::max( it.second.totalLengthN, it.second.totalLengthP );
429  reportAux( wxString::Format( " - coupled length: %s, total length: %s",
430 
431  MessageTextFromValue( userUnits(), it.second.totalCoupled ),
432  MessageTextFromValue( userUnits(), totalLen ) ) );
433 
434  int totalUncoupled = totalLen - it.second.totalCoupled;
435 
436  bool uncoupledViolation = false;
437 
438  if( maxUncoupledConstraint )
439  {
440  auto val = maxUncoupledConstraint->GetValue();
441 
442  if ( val.HasMax() && totalUncoupled > val.Max() )
443  {
445 
446  m_msg = wxString::Format( _( "(%s maximum uncoupled length: %s; actual: %s)" ),
447  maxUncoupledConstraint->GetParentRule()->m_Name,
448  MessageTextFromValue( userUnits(), val.Max() ),
449  MessageTextFromValue( userUnits(), totalUncoupled ) );
450 
451  drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + m_msg );
452 
453  for( BOARD_CONNECTED_ITEM* offendingTrack : it.second.itemsP )
454  drce->AddItem( offendingTrack );
455 
456  for( BOARD_CONNECTED_ITEM* offendingTrack : it.second.itemsN )
457  drce->AddItem( offendingTrack );
458 
459  uncoupledViolation = true;
460 
461  drce->SetViolatingRule( maxUncoupledConstraint->GetParentRule() );
462 
463  reportViolation( drce, ( *it.second.itemsP.begin() )->GetPosition() );
464  }
465  }
466 
467  if ( gapConstraint && ( uncoupledViolation || !maxUncoupledConstraint ) )
468  {
469  for( auto& cpair : it.second.coupled )
470  {
471  if( !cpair.couplingOK )
472  {
473  auto val = gapConstraint->GetValue();
475 
476  m_msg = drcItem->GetErrorText() + " (" +
477  gapConstraint->GetParentRule()->m_Name + " ";
478 
479  if( val.HasMin() )
480  m_msg += wxString::Format( _( "minimum gap: %s; " ),
481  MessageTextFromValue( userUnits(), val.Min() ) );
482 
483  if( val.HasMax() )
484  m_msg += wxString::Format( _( "maximum gap: %s; " ),
485  MessageTextFromValue( userUnits(), val.Max() ) );
486 
487  m_msg += wxString::Format( _( "actual: %s)" ),
488  MessageTextFromValue( userUnits(), cpair.computedGap ) );
489 
490  drcItem->SetErrorMessage( m_msg );
491 
492  drcItem->AddItem( cpair.parentP );
493  drcItem->AddItem( cpair.parentN );
494 
495  drcItem->SetViolatingRule( gapConstraint->GetParentRule() );
496 
497  reportViolation( drcItem, cpair.parentP->GetPosition() );
498  }
499  }
500  }
501  }
502 
504 
505  return true;
506 }
507 
508 
510 {
512 }
513 
514 
515 namespace detail
516 {
518 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Return a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:750
wxString MessageTextFromValue(EDA_UNITS aUnits, int aValue, bool aAddUnitLabel, EDA_DATA_TYPE aType)
Convert a value to a string using double notation.
Definition: base_units.cpp:125
static bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
static std::shared_ptr< DRC_ITEM > Create(int aErrorCode)
Constructs a DRC_ITEM for the given error code.
Definition: drc_item.cpp:245
virtual std::set< DRC_CONSTRAINT_T > GetConstraintTypes() const override
std::shared_ptr< KIGFX::VIEW_OVERLAY > GetDebugOverlay() const
Definition: drc_engine.h:99
std::set< BOARD_CONNECTED_ITEM * > itemsN
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:82
ecoord SquaredLength() const
Definition: seg.h:345
NETINFO_ITEM * GetNet() const
Return #NET_INFO object for a given item.
const wxPoint & GetStart() const
Definition: track.h:116
static bool IsNetADiffPair(BOARD *aBoard, NETINFO_ITEM *aNet, int &aNetP, int &aNetN)
std::set< BOARD_CONNECTED_ITEM * > itemsP
bool operator<(const DIFF_PAIR_KEY &b) const
class ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
Definition: sch_symbol.cpp:69
const NETINFO_LIST & GetNetInfo() const
Definition: board.h:752
class PAD, a pad in a footprint
Definition: typeinfo.h:89
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
virtual void reportRuleStatistics()
void Insert(BOARD_ITEM *aItem, int aWorstClearance=0, int aLayer=UNDEFINED_LAYER)
Function Insert() Inserts an item into the tree.
Definition: drc_rtree.h:86
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
DRC_CONSTRAINT_T
Definition: drc_rule.h:41
PCB_LAYER_ID
A quick note on layer IDs:
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.h:389
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:416
bool CheckColliding(SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
Definition: drc_rtree.h:153
BOARD * GetBoard() const
Definition: drc_engine.h:87
static void extractDiffPairCoupledItems(DIFF_PAIR_ITEMS &aDp, DRC_RTREE &aTree)
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:414
const wxString & GetNetname() const
Definition: netinfo.h:119
class ZONE, a copper pour area
Definition: typeinfo.h:105
EDA_UNITS userUnits() const
std::vector< DIFF_PAIR_COUPLED_SEGMENTS > coupled
DRC_CONSTRAINT EvalRules(DRC_CONSTRAINT_T aConstraintId, const BOARD_ITEM *a, const BOARD_ITEM *b, PCB_LAYER_ID aLayer, REPORTER *aReporter=nullptr)
Definition: drc_engine.cpp:736
Definition: color4d.h:59
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: seg.h:41
virtual void reportViolation(std::shared_ptr< DRC_ITEM > &item, wxPoint aMarkerPos)
int forEachGeometryItem(const std::vector< KICAD_T > &aTypes, LSET aLayers, const std::function< bool(BOARD_ITEM *)> &aFunc)
DRC_TEST_PROVIDER is a base class that represents a DRC "provider" which runs some DRC functions over...
Handle the data for a net.
Definition: netinfo.h:64
Definition: color4d.h:56
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:190
#define _(s)
Definition: 3d_actions.cpp:33
static std::shared_ptr< KIGFX::VIEW_OVERLAY > overlay
DRC_ENGINE * m_drcEngine
VECTOR2I A
Definition: seg.h:49
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
The common library.
const wxPoint & GetEnd() const
Definition: track.h:113
boost::optional< T > OPT
Definition: optional.h:7
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
#define drc_dbg(level, fmt,...)
Definition: drc_engine.h:57
NETINFO_ITEM * GetNetItem(int aNetCode) const
DRC_RTREE - Implements an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:43
virtual bool Run() override
Runs this provider against the given PCB with configured options (if any).
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:173
virtual void reportAux(wxString fmt,...)
Definition: track.h:83
virtual LSET GetLayerSet() const
Return a std::bitset of all layers on which the item physically resides.
Definition: board_item.h:178
int GetNetCode() const
Definition: netinfo.h:113
VECTOR2I B
Definition: seg.h:50