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-2022 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 <pcb_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 #include <view/view_overlay.h>
38 
39 /*
40  Differential pair gap/coupling test.
41  Errors generated:
42  - DRCE_DIFF_PAIR_GAP_OUT_OF_RANGE
43  - DRCE_DIFF_PAIR_UNCOUPLED_LENGTH_TOO_LONG
44  - DRCE_TOO_MANY_VIAS
45  Todo:
46  - arc support.
47  - improve recognition of coupled segments (now anything that's parallel is considered
48  coupled, causing DRC errors on meanders)
49 */
50 
51 namespace test {
52 
54 {
55 public:
57  m_board( nullptr )
58  {
59  }
60 
62  {
63  }
64 
65  virtual bool Run() override;
66 
67  virtual const wxString GetName() const override
68  {
69  return wxT( "diff_pair_coupling" );
70  };
71 
72  virtual const wxString GetDescription() const override
73  {
74  return wxT( "Tests differential pair coupling" );
75  }
76 
77  virtual int GetNumPhases() const override
78  {
79  return 1;
80  }
81 
82  virtual std::set<DRC_CONSTRAINT_T> GetConstraintTypes() const override;
83 
84 private:
85 
87 };
88 
89 };
90 
91 
92 static bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip )
93 {
94  SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
95 
96  int64_t t_a = 0;
97  int64_t t_b = p.TCoef( p.B );
98 
99  int64_t tproj_a = p.TCoef( n_proj_p.A );
100  int64_t tproj_b = p.TCoef( n_proj_p.B );
101 
102  if( t_b < t_a )
103  std::swap( t_b, t_a );
104 
105  if( tproj_b < tproj_a )
106  std::swap( tproj_b, tproj_a );
107 
108  if( t_b <= tproj_a )
109  return false;
110 
111  if( t_a >= tproj_b )
112  return false;
113 
114  int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
115  std::vector<int64_t> tv( t, t + 4 );
116  std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
117 
118  int64_t pLenSq = p.SquaredLength();
119 
120  VECTOR2I dp = p.B - p.A;
121  pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
122  pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
123 
124  pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
125  pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
126 
127  nClip.A = n.LineProject( pClip.A );
128  nClip.B = n.LineProject( pClip.B );
129 
130  return true;
131 }
132 
133 
135 {
136  bool operator<( const DIFF_PAIR_KEY& b ) const
137  {
138  if( netP < b.netP )
139  {
140  return true;
141  }
142  else if( netP > b.netP )
143  {
144  return false;
145  }
146  else // netP == b.netP
147  {
148  if( netN < b.netN )
149  return true;
150  else if( netN > b.netN )
151  return false;
152  else
153  return parentRule < b.parentRule;
154  }
155  }
156 
157  int netP, netN;
159 };
160 
162 {
170 
172  parentN( nullptr ),
173  parentP( nullptr ),
174  computedGap( 0 ),
176  couplingOK( false )
177  {}
178 };
179 
181 {
182  std::set<BOARD_CONNECTED_ITEM*> itemsP, itemsN;
183  std::vector<DIFF_PAIR_COUPLED_SEGMENTS> coupled;
187 };
188 
190 {
191  for( BOARD_CONNECTED_ITEM* itemP : aDp.itemsP )
192  {
193  PCB_TRACK* sp = dyn_cast<PCB_TRACK*>( itemP );
195  int bestGap = std::numeric_limits<int>::max();
196 
197  if( !sp )
198  continue;
199 
200  for ( BOARD_CONNECTED_ITEM* itemN : aDp.itemsN )
201  {
202  PCB_TRACK* sn = dyn_cast<PCB_TRACK*> ( itemN );
203 
204  if( !sn )
205  continue;
206 
207  if( ( sn->GetLayerSet() & sp->GetLayerSet() ).none() )
208  continue;
209 
210  SEG ssp ( sp->GetStart(), sp->GetEnd() );
211  SEG ssn ( sn->GetStart(), sn->GetEnd() );
212 
213  // Segments that are ~ 1 IU in length per side are approximately parallel (tolerance is 1 IU)
214  // with everything and their parallel projection is < 1 IU, leading to bad distance calculations
215  if( ssp.SquaredLength() > 2 && ssn.SquaredLength() > 2 && ssp.ApproxParallel(ssn) )
216  {
218  bool coupled = commonParallelProjection( ssp, ssn, cpair.coupledP, cpair.coupledN );
219 
220  if( coupled )
221  {
222  cpair.parentP = sp;
223  cpair.parentN = sn;
224  cpair.layer = sp->GetLayer();
225 
226  int gap = (cpair.coupledP.A - cpair.coupledN.A).EuclideanNorm();
227  if( gap < bestGap )
228  {
229  bestGap = gap;
230  bestCoupled = cpair;
231  }
232  }
233 
234  }
235  }
236 
237  if( bestCoupled )
238  {
239  auto excludeSelf =
240  [&] ( BOARD_ITEM *aItem )
241  {
242  if( aItem == bestCoupled->parentN || aItem == bestCoupled->parentP )
243  {
244  return false;
245  }
246 
247  if( aItem->Type() == PCB_TRACE_T || aItem->Type() == PCB_VIA_T )
248  {
249  auto bci = static_cast<BOARD_CONNECTED_ITEM*>( aItem );
250 
251  if( bci->GetNetCode() == bestCoupled->parentN->GetNetCode()
252  || bci->GetNetCode() == bestCoupled->parentP->GetNetCode() )
253  return false;
254  }
255 
256  return true;
257  };
258 
259  SHAPE_SEGMENT checkSegStart( bestCoupled->coupledP.A, bestCoupled->coupledN.A );
260  SHAPE_SEGMENT checkSegEnd( bestCoupled->coupledP.B, bestCoupled->coupledN.B );
261 
262  // check if there's anything in between the segments suspected to be coupled. If
263  // there's nothing, assume they are really coupled.
264 
265  if( !aTree.CheckColliding( &checkSegStart, sp->GetLayer(), 0, excludeSelf )
266  && !aTree.CheckColliding( &checkSegEnd, sp->GetLayer(), 0, excludeSelf ) )
267  {
268  aDp.coupled.push_back( *bestCoupled );
269  }
270  }
271  }
272 }
273 
274 
275 
277 {
279 
280 
281 
282  std::map<DIFF_PAIR_KEY, DIFF_PAIR_ITEMS> dpRuleMatches;
283 
284  auto evaluateDpConstraints =
285  [&]( BOARD_ITEM *item ) -> bool
286  {
287  DIFF_PAIR_KEY key;
288  BOARD_CONNECTED_ITEM* citem = static_cast<BOARD_CONNECTED_ITEM*>( item );
289  NETINFO_ITEM* refNet = citem->GetNet();
290 
291  if( refNet && DRC_ENGINE::IsNetADiffPair( m_board, refNet, key.netP, key.netN ) )
292  {
293  drc_dbg( 10, wxT( "eval dp %p\n" ), item );
294 
295  const DRC_CONSTRAINT_T constraintsToCheck[] = {
298  };
299 
300  for( int i = 0; i < 2; i++ )
301  {
302  auto constraint = m_drcEngine->EvalRules( constraintsToCheck[ i ], item,
303  nullptr, item->GetLayer() );
304 
305  if( constraint.IsNull() )
306  continue;
307 
308  drc_dbg( 10, wxT( "cns %d item %p\n" ), constraintsToCheck[i], item );
309 
310  key.parentRule = constraint.GetParentRule();
311 
312  if( refNet->GetNetCode() == key.netN )
313  dpRuleMatches[key].itemsN.insert( citem );
314  else
315  dpRuleMatches[key].itemsP.insert( citem );
316  }
317  }
318 
319  return true;
320  };
321 
322  m_board->GetConnectivity()->GetFromToCache()->Rebuild( m_board );
323 
325  LSET::AllCuMask(), evaluateDpConstraints );
326 
327  drc_dbg( 10, wxT( "dp rule matches %d\n" ), (int) dpRuleMatches.size() );
328 
329 
330  DRC_RTREE copperTree;
331 
332  auto addToTree =
333  [&copperTree]( BOARD_ITEM *item ) -> bool
334  {
335  for( PCB_LAYER_ID layer : item->GetLayerSet().Seq() )
336  {
337  if( IsCopperLayer( layer ) )
338  copperTree.Insert( item, layer );
339  }
340 
341  return true;
342  };
343 
345  LSET::AllCuMask(), addToTree );
346 
347 
348  reportAux( wxString::Format( _("DPs evaluated:") ) );
349 
350  for( auto& it : dpRuleMatches )
351  {
352  NETINFO_ITEM *niP = m_board->GetNetInfo().GetNetItem( it.first.netP );
353  NETINFO_ITEM *niN = m_board->GetNetInfo().GetNetItem( it.first.netN );
354 
355  assert( niP );
356  assert( niN );
357 
358  wxString nameP = niP->GetNetname();
359  wxString nameN = niN->GetNetname();
360 
361  reportAux( wxString::Format( wxT( "Rule '%s', DP: (+) %s - (-) %s" ),
362  it.first.parentRule->m_Name,
363  nameP,
364  nameN ) );
365 
366  extractDiffPairCoupledItems( it.second, copperTree );
367 
368  it.second.totalCoupled = 0;
369  it.second.totalLengthN = 0;
370  it.second.totalLengthP = 0;
371 
372  drc_dbg(10, wxT( " coupled prims : %d\n" ), (int) it.second.coupled.size() );
373 
374  OPT<DRC_CONSTRAINT> gapConstraint =
375  it.first.parentRule->FindConstraint( DIFF_PAIR_GAP_CONSTRAINT );
376  OPT<DRC_CONSTRAINT> maxUncoupledConstraint =
377  it.first.parentRule->FindConstraint( DIFF_PAIR_MAX_UNCOUPLED_CONSTRAINT );
378 
379  for( BOARD_CONNECTED_ITEM* item : it.second.itemsN )
380  {
381  // fixme: include vias
382  if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
383  it.second.totalLengthN += track->GetLength();
384  }
385 
386  for( BOARD_CONNECTED_ITEM* item : it.second.itemsP )
387  {
388  // fixme: include vias
389  if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
390  it.second.totalLengthP += track->GetLength();
391  }
392 
393  for( auto& cpair : it.second.coupled )
394  {
395  int length = cpair.coupledN.Length();
396  int gap = cpair.coupledN.Distance( cpair.coupledP );
397 
398  gap -= cpair.parentN->GetWidth() / 2;
399  gap -= cpair.parentP->GetWidth() / 2;
400 
401  cpair.computedGap = gap;
402 
404 
405  if( overlay )
406  {
407  overlay->SetIsFill(false);
408  overlay->SetIsStroke(true);
409  overlay->SetStrokeColor( RED );
410  overlay->SetLineWidth( 100000 );
411  overlay->Line( cpair.coupledP );
412  overlay->SetStrokeColor( BLUE );
413  overlay->Line( cpair.coupledN );
414  }
415 
416  drc_dbg( 10, wxT( " len %d gap %d l %d\n" ),
417  length,
418  gap,
419  cpair.parentP->GetLayer() );
420 
421  if( gapConstraint )
422  {
423  auto val = gapConstraint->GetValue();
424  bool insideRange = true;
425 
426  if( val.HasMin() && gap < val.Min() )
427  insideRange = false;
428 
429  if( val.HasMax() && gap > val.Max() )
430  insideRange = false;
431 
432 // if(val.HasMin() && val.HasMax() )
433  // drc_dbg(10, "Vmin %d vmax %d\n", val.Min(), val.Max() );
434 
435  cpair.couplingOK = insideRange;
436  }
437  else
438  {
439  cpair.couplingOK = true;
440  }
441 
442  if( cpair.couplingOK )
443  it.second.totalCoupled += length;
444  }
445 
446  int totalLen = std::max( it.second.totalLengthN, it.second.totalLengthP );
447  reportAux( wxString::Format( wxT( " - coupled length: %s, total length: %s" ),
448  MessageTextFromValue( userUnits(), it.second.totalCoupled ),
449  MessageTextFromValue( userUnits(), totalLen ) ) );
450 
451  int totalUncoupled = totalLen - it.second.totalCoupled;
452 
453  bool uncoupledViolation = false;
454 
455  if( maxUncoupledConstraint )
456  {
457  auto val = maxUncoupledConstraint->GetValue();
458 
459  if ( val.HasMax() && totalUncoupled > val.Max() )
460  {
462 
463  m_msg = wxString::Format( _( "(%s maximum uncoupled length: %s; actual: %s)" ),
464  maxUncoupledConstraint->GetParentRule()->m_Name,
465  MessageTextFromValue( userUnits(), val.Max() ),
466  MessageTextFromValue( userUnits(), totalUncoupled ) );
467 
468  drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + m_msg );
469 
470  auto pit = it.second.itemsP.begin();
471  auto nit = it.second.itemsN.begin();
472 
473  drce->AddItem( *pit );
474  drce->AddItem( *nit );
475 
476  for( pit++; pit != it.second.itemsP.end(); pit++ )
477  drce->AddItem( *pit );
478 
479  for( nit++; nit != it.second.itemsN.end(); nit++ )
480  drce->AddItem( *nit );
481 
482  uncoupledViolation = true;
483 
484  drce->SetViolatingRule( maxUncoupledConstraint->GetParentRule() );
485 
486  reportViolation( drce, ( *it.second.itemsP.begin() )->GetPosition() );
487  }
488  }
489 
490  if ( gapConstraint && ( uncoupledViolation || !maxUncoupledConstraint ) )
491  {
492  for( auto& cpair : it.second.coupled )
493  {
494  if( !cpair.couplingOK )
495  {
496  auto val = gapConstraint->GetValue();
498 
499  m_msg = drcItem->GetErrorText() + wxT( " (" ) +
500  gapConstraint->GetParentRule()->m_Name + wxS( " " );
501 
502  if( val.HasMin() )
503  m_msg += wxString::Format( _( "minimum gap: %s; " ),
504  MessageTextFromValue( userUnits(), val.Min() ) );
505 
506  if( val.HasMax() )
507  m_msg += wxString::Format( _( "maximum gap: %s; " ),
508  MessageTextFromValue( userUnits(), val.Max() ) );
509 
510  m_msg += wxString::Format( _( "actual: %s)" ),
511  MessageTextFromValue( userUnits(), cpair.computedGap ) );
512 
513  drcItem->SetErrorMessage( m_msg );
514 
515  drcItem->AddItem( cpair.parentP );
516  drcItem->AddItem( cpair.parentN );
517 
518  drcItem->SetViolatingRule( gapConstraint->GetParentRule() );
519 
520  reportViolation( drcItem, cpair.parentP->GetPosition() );
521  }
522  }
523  }
524  }
525 
527 
528  return true;
529 }
530 
531 
533 {
535 }
536 
537 
538 namespace detail
539 {
541 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Return a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:759
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:104
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:266
virtual std::set< DRC_CONSTRAINT_T > GetConstraintTypes() const override
std::shared_ptr< PNS_LOG_VIEWER_OVERLAY > overlay
Definition: playground.cpp:36
std::shared_ptr< KIGFX::VIEW_OVERLAY > GetDebugOverlay() const
Definition: drc_engine.h:104
const wxPoint & GetEnd() const
Definition: pcb_track.h:105
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:49
ecoord SquaredLength() const
Definition: seg.h:355
virtual void reportViolation(std::shared_ptr< DRC_ITEM > &item, const wxPoint &aMarkerPos)
NETINFO_ITEM * GetNet() const
Return #NET_INFO object for a given item.
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 PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
const NETINFO_LIST & GetNetInfo() const
Definition: board.h:680
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()
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:72
DRC_CONSTRAINT_T
Definition: drc_rule.h:41
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:268
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:402
bool CheckColliding(SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
Definition: drc_rtree.h:146
BOARD * GetBoard() const
Definition: drc_engine.h:88
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:345
const wxString & GetNetname() const
Definition: netinfo.h:126
#define _(s)
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 aConstraintType, const BOARD_ITEM *a, const BOARD_ITEM *b, PCB_LAYER_ID aLayer, REPORTER *aReporter=nullptr)
Definition: drc_engine.cpp:759
Definition: color4d.h:59
bool IsCopperLayer(LAYER_NUM aLayerId)
Tests whether a layer is a copper layer.
Definition: layer_ids.h:808
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:40
int forEachGeometryItem(const std::vector< KICAD_T > &aTypes, LSET aLayers, const std::function< bool(BOARD_ITEM *)> &aFunc)
Represent a DRC "provider" which runs some DRC functions over a BOARD and spits out #DRC_ITEMs and po...
Handle the data for a net.
Definition: netinfo.h:66
Definition: color4d.h:56
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:191
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
DRC_ENGINE * m_drcEngine
VECTOR2I A
Definition: seg.h:48
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
The common library.
void Insert(BOARD_ITEM *aItem, PCB_LAYER_ID aLayer, int aWorstClearance=0)
Insert an item into the tree on a particular layer with an optional worst clearance.
Definition: drc_rtree.h:93
boost::optional< T > OPT
Definition: optional.h:7
class PCB_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
Implement an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:46
virtual bool Run() override
Run 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:143
virtual void reportAux(wxString fmt,...)
const wxPoint & GetStart() const
Definition: pcb_track.h:108
virtual LSET GetLayerSet() const
Return a std::bitset of all layers on which the item physically resides.
Definition: board_item.h:148
int GetNetCode() const
Definition: netinfo.h:120
VECTOR2I B
Definition: seg.h:49