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 coupled, causing
47  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_TYPE_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  return true;
139  else if( netP > b.netP )
140  return false;
141  else // netP == b.netP
142  {
143  if( netN < b.netN )
144  return true;
145  else if( netN > b.netN )
146  return false;
147  else
148  return parentRule < b.parentRule;
149  }
150  }
151 
152  int netP, netN;
154  };
155 
157  {
163  };
164 
166  {
167  std::set<BOARD_CONNECTED_ITEM*> itemsP, itemsN;
168  std::vector<DIFF_PAIR_COUPLED_SEGMENTS> coupled;
172  };
173 
175 {
176  for( BOARD_CONNECTED_ITEM* itemP : aDp.itemsP )
177  {
178  TRACK* sp = dyn_cast<TRACK*>( itemP );
180  int bestGap = std::numeric_limits<int>::max();
181 
182  if(!sp)
183  continue;
184 
185  for ( BOARD_CONNECTED_ITEM* itemN : aDp.itemsN )
186  {
187  auto sn = dyn_cast<TRACK*> ( itemN );
188 
189  if(!sn)
190  continue;
191 
192  if( ( sn->GetLayerSet() & sp->GetLayerSet() ).none() )
193  continue;
194 
195  SEG ssp ( sp->GetStart(), sp->GetEnd() );
196  SEG ssn ( sn->GetStart(), sn->GetEnd() );
197 
198  if( ssp.ApproxParallel(ssn) )
199  {
201  bool coupled = commonParallelProjection( ssp, ssn, cpair.coupledP, cpair.coupledN );
202 
203  if( coupled )
204  {
205  cpair.parentP = sp;
206  cpair.parentN = sn;
207  cpair.layer = sp->GetLayer();
208 
209  int gap = (cpair.coupledP.A - cpair.coupledN.A).EuclideanNorm();
210  if( gap < bestGap )
211  {
212  bestGap = gap;
213  bestCoupled = cpair;
214  }
215  }
216 
217  }
218  }
219 
220  if( bestCoupled )
221  {
222  printf("Best-gap %d\n", bestGap );
223  auto excludeSelf =
224  [&] ( BOARD_ITEM *aItem )
225  {
226  if( aItem == bestCoupled->parentN || aItem == bestCoupled->parentP )
227  {
228  return false;
229  }
230 
231  if( aItem->Type() == PCB_TRACE_T || aItem->Type() == PCB_VIA_T )
232  {
233  auto bci = static_cast<BOARD_CONNECTED_ITEM*>( aItem );
234 
235  if( bci->GetNetCode() == bestCoupled->parentN->GetNetCode()
236  || bci->GetNetCode() == bestCoupled->parentP->GetNetCode() )
237  return false;
238  }
239 
240  return true;
241  };
242 
243  SHAPE_SEGMENT checkSegStart( bestCoupled->coupledP.A, bestCoupled->coupledN.A );
244  SHAPE_SEGMENT checkSegEnd( bestCoupled->coupledP.B, bestCoupled->coupledN.B );
245 
246  // check if there's anyting in between the segments suspected to be coupled. If
247  // there's nothing, assume they are really coupled.
248 
249  if( !aTree.CheckColliding( &checkSegStart, sp->GetLayer(), 0, excludeSelf )
250  && !aTree.CheckColliding( &checkSegEnd, sp->GetLayer(), 0, excludeSelf ) )
251  {
252  aDp.coupled.push_back( *bestCoupled );
253  }
254  }
255  }
256 }
257 
258 
259 
261 {
263 
264 
265 
266  std::map<DIFF_PAIR_KEY, DIFF_PAIR_ITEMS> dpRuleMatches;
267 
268  auto evaluateDpConstraints =
269  [&]( BOARD_ITEM *item ) -> bool
270  {
271  DIFF_PAIR_KEY key;
272  BOARD_CONNECTED_ITEM* citem = static_cast<BOARD_CONNECTED_ITEM*>( item );
273  NETINFO_ITEM* refNet = citem->GetNet();
274 
275  if( refNet && DRC_ENGINE::IsNetADiffPair( m_board, refNet, key.netP, key.netN ) )
276  {
277  drc_dbg( 10, "eval dp %p\n", item );
278 
279  const DRC_CONSTRAINT_TYPE_T constraintsToCheck[] = {
282  };
283 
284  for( int i = 0; i < 2; i++ )
285  {
286  auto constraint = m_drcEngine->EvalRulesForItems( constraintsToCheck[i],
287  item, nullptr,
288  item->GetLayer() );
289 
290  if( constraint.IsNull() )
291  continue;
292 
293  drc_dbg( 10, "cns %d item %p\n", constraintsToCheck[i], item );
294 
295  key.parentRule = constraint.GetParentRule();
296 
297  if( refNet->GetNet() == key.netN )
298  dpRuleMatches[key].itemsN.insert( citem );
299  else
300  dpRuleMatches[key].itemsP.insert( citem );
301  }
302  }
303 
304  return true;
305  };
306 
307  m_board->GetConnectivity()->GetFromToCache()->Rebuild( m_board );
308 
310  LSET::AllCuMask(), evaluateDpConstraints );
311 
312  drc_dbg( 10, "dp rule matches %d\n", (int) dpRuleMatches.size() );
313 
314 
315  DRC_RTREE copperTree;
316 
317  auto addToTree =
318  [&copperTree]( BOARD_ITEM *item ) -> bool
319  {
320  copperTree.Insert( item );
321  return true;
322  };
323 
325  LSET::AllCuMask(), addToTree );
326 
327 
328  reportAux( wxString::Format( _("DPs evaluated:") ) );
329 
330  for( auto& it : dpRuleMatches )
331  {
332  NETINFO_ITEM *niP = m_board->GetNetInfo().GetNetItem( it.first.netP );
333  NETINFO_ITEM *niN = m_board->GetNetInfo().GetNetItem( it.first.netN );
334 
335  assert( niP );
336  assert( niN );
337 
338  wxString nameP = niP->GetNetname();
339  wxString nameN = niN->GetNetname();
340 
341  reportAux( wxString::Format( "Rule '%s', DP: (+) %s - (-) %s", it.first.parentRule->m_Name, nameP, nameN ) );
342 
343  extractDiffPairCoupledItems( it.second, copperTree );
344 
345  it.second.totalCoupled = 0;
346  it.second.totalLengthN = 0;
347  it.second.totalLengthP = 0;
348 
349  drc_dbg(10, " coupled prims : %d\n", (int) it.second.coupled.size() );
350 
351  OPT<DRC_CONSTRAINT> gapConstraint = it.first.parentRule->FindConstraint( DIFF_PAIR_GAP_CONSTRAINT );
352  OPT<DRC_CONSTRAINT> maxUncoupledConstraint = it.first.parentRule->FindConstraint( DIFF_PAIR_MAX_UNCOUPLED_CONSTRAINT );
353 
354  for( auto& item : it.second.itemsN )
355  {
356  // fixme: include vias
357  if( auto track = dyn_cast<TRACK*>( item ) )
358  it.second.totalLengthN += track->GetLength();
359  }
360 
361  for( auto& item : it.second.itemsP )
362  {
363  // fixme: include vias
364  if( auto track = dyn_cast<TRACK*>( item ) )
365  it.second.totalLengthP += track->GetLength();
366  }
367 
368  for( auto& cpair : it.second.coupled )
369  {
370  int length = cpair.coupledN.Length();
371  int gap = cpair.coupledN.Distance( cpair.coupledP );
372 
373  gap -= cpair.parentN->GetWidth() / 2;
374  gap -= cpair.parentP->GetWidth() / 2;
375 
376  cpair.computedGap = gap;
377 
378  auto overlay = m_drcEngine->GetDebugOverlay();
379 
380  printf("Overlay %p\n", overlay.get () );
381 
382  if( overlay )
383  {
384  overlay->SetIsFill(false);
385  overlay->SetIsStroke(true);
386  overlay->SetStrokeColor( RED );
387  overlay->SetLineWidth( 100000 );
388  overlay->Line( cpair.coupledP );
389  overlay->SetStrokeColor( BLUE );
390  overlay->Line( cpair.coupledN );
391  }
392 
393  drc_dbg(10, " len %d gap %d l %d\n", length, gap, cpair.parentP->GetLayer() );
394 
395  if( gapConstraint )
396  {
397  auto val = gapConstraint->GetValue();
398  bool insideRange = true;
399  if ( val.HasMin() && gap < val.Min() )
400  insideRange = false;
401  if ( val.HasMax() && gap > val.Max() )
402  insideRange = false;
403 
404 
405 // if(val.HasMin() && val.HasMax() )
406  // drc_dbg(10, "Vmin %d vmax %d\n", val.Min(), val.Max() );
407 
408  cpair.couplingOK = insideRange;
409 
410  if( insideRange )
411  it.second.totalCoupled += length;
412  }
413  }
414 
415  int totalLen = std::max( it.second.totalLengthN, it.second.totalLengthP );
416  reportAux( wxString::Format( " - coupled length: %s, total length: %s",
417 
418  MessageTextFromValue( userUnits(), it.second.totalCoupled ),
419  MessageTextFromValue( userUnits(), totalLen ) ) );
420 
421  int totalUncoupled = totalLen - it.second.totalCoupled;
422 
423  bool uncoupledViolation = false;
424 
425  if( maxUncoupledConstraint )
426  {
427  auto val = maxUncoupledConstraint->GetValue();
428 
429  if ( val.HasMax() && totalUncoupled > val.Max() )
430  {
432 
433  m_msg = wxString::Format( _( "(%s maximum uncoupled length: %s; actual: %s)" ),
434  maxUncoupledConstraint->GetParentRule()->m_Name,
435  MessageTextFromValue( userUnits(), val.Max() ),
436  MessageTextFromValue( userUnits(), totalUncoupled ) );
437 
438  drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + m_msg );
439 
440  for( BOARD_CONNECTED_ITEM* offendingTrack : it.second.itemsP )
441  drce->AddItem( offendingTrack );
442 
443  for( BOARD_CONNECTED_ITEM* offendingTrack : it.second.itemsN )
444  drce->AddItem( offendingTrack );
445 
446  uncoupledViolation = true;
447 
448  drce->SetViolatingRule( maxUncoupledConstraint->GetParentRule() );
449 
450  reportViolation( drce, ( *it.second.itemsP.begin() )->GetPosition() );
451  }
452  }
453 
454  if ( gapConstraint && ( uncoupledViolation || !maxUncoupledConstraint ) )
455  {
456  for( auto& cpair : it.second.coupled )
457  {
458  if( !cpair.couplingOK )
459  {
460  auto val = gapConstraint->GetValue();
462 
463  m_msg = drcItem->GetErrorText() + " (" + gapConstraint->GetParentRule()->m_Name + " ";
464 
465  if( val.HasMin() )
466  m_msg += wxString::Format( _( "minimum gap: %s; " ),
467  MessageTextFromValue( userUnits(), val.Min() ) );
468 
469  if( val.HasMax() )
470  m_msg += wxString::Format( _( "maximum gap: %s; " ),
471  MessageTextFromValue( userUnits(), val.Max() ) );
472 
473 
474  m_msg += wxString::Format( _( "actual: %s)" ),
475  MessageTextFromValue( userUnits(), cpair.computedGap ) );
476 
477  drcItem->SetErrorMessage( m_msg );
478 
479  drcItem->AddItem( cpair.parentP );
480  drcItem->AddItem( cpair.parentN );
481 
482  drcItem->SetViolatingRule( gapConstraint->GetParentRule() );
483 
484  reportViolation( drcItem, cpair.parentP->GetPosition() );
485  }
486  }
487  }
488  }
489 
491 
492  return true;
493 }
494 
495 
497 {
499 }
500 
501 
502 namespace detail
503 {
505 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
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)
Definition: base_units.cpp:123
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:239
std::shared_ptr< KIGFX::VIEW_OVERLAY > GetDebugOverlay() const
Definition: drc_engine.h:97
std::set< BOARD_CONNECTED_ITEM * > itemsN
BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class,...
Definition: board_item.h:86
ecoord SquaredLength() const
Definition: seg.h:324
NETINFO_ITEM * GetNet() const
Function GetNet Returns NET_INFO object for a given item.
const wxPoint & GetStart() const
Definition: track.h:116
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:98
static int IsNetADiffPair(BOARD *aBoard, NETINFO_ITEM *aNet, int &aNetP, int &aNetN)
const NETINFO_LIST & GetNetInfo() const
Definition: board.h:719
class PAD, a pad in a footprint
Definition: typeinfo.h:90
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
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:96
PCB_LAYER_ID
A quick note on layer IDs:
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:362
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:389
bool CheckColliding(SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
Definition: drc_rtree.h:142
BOARD * GetBoard() const
Definition: drc_engine.h:85
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:382
const wxString & GetNetname() const
Function GetNetname.
Definition: netinfo.h:231
class ZONE, a copper pour area
Definition: typeinfo.h:106
EDA_UNITS userUnits() const
std::vector< DIFF_PAIR_COUPLED_SEGMENTS > coupled
Definition: color4d.h:60
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Function Format outputs a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: seg.h:39
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...
NETINFO_ITEM handles the data for a net.
Definition: netinfo.h:65
Definition: color4d.h:57
virtual std::set< DRC_CONSTRAINT_TYPE_T > GetConstraintTypes() const override
DRC_CONSTRAINT_TYPE_T
Definition: drc_rule.h:41
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
int GetNet() const
Function GetNet.
Definition: netinfo.h:223
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:186
#define _(s)
Definition: 3d_actions.cpp:33
DRC_ENGINE * m_drcEngine
VECTOR2I A
Definition: seg.h:47
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:97
DRC_CONSTRAINT EvalRulesForItems(DRC_CONSTRAINT_TYPE_T ruleID, const BOARD_ITEM *a, const BOARD_ITEM *b=nullptr, PCB_LAYER_ID aLayer=UNDEFINED_LAYER, REPORTER *aReporter=nullptr)
Definition: drc_engine.cpp:707
#define drc_dbg(level, fmt,...)
Definition: drc_engine.h:55
NETINFO_ITEM * GetNetItem(int aNetCode) const
Function GetItem.
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
Function GetLayer returns the primary layer this item is on.
Definition: board_item.h:185
virtual void reportAux(wxString fmt,...)
Definition: track.h:83
virtual LSET GetLayerSet() const
Function GetLayerSet returns a std::bitset of all layers on which the item physically resides.
Definition: board_item.h:191
VECTOR2I B
Definition: seg.h:48