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 <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 "diff_pair_coupling";
70  };
71 
72  virtual const wxString GetDescription() const override
73  {
74  return "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 are approximately parallel with everything and their
214  // parallel projection is < 1 IU, leading to bad distance calculations
215  if( ssp.SquaredLength() > 1 && ssn.SquaredLength() > 1 && 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, "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, "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, "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( "Rule '%s', DP: (+) %s - (-) %s",
362  it.first.parentRule->m_Name, nameP, nameN ) );
363 
364  extractDiffPairCoupledItems( it.second, copperTree );
365 
366  it.second.totalCoupled = 0;
367  it.second.totalLengthN = 0;
368  it.second.totalLengthP = 0;
369 
370  drc_dbg(10, " coupled prims : %d\n", (int) it.second.coupled.size() );
371 
372  OPT<DRC_CONSTRAINT> gapConstraint =
373  it.first.parentRule->FindConstraint( DIFF_PAIR_GAP_CONSTRAINT );
374  OPT<DRC_CONSTRAINT> maxUncoupledConstraint =
375  it.first.parentRule->FindConstraint( DIFF_PAIR_MAX_UNCOUPLED_CONSTRAINT );
376 
377  for( BOARD_CONNECTED_ITEM* item : it.second.itemsN )
378  {
379  // fixme: include vias
380  if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
381  it.second.totalLengthN += track->GetLength();
382  }
383 
384  for( BOARD_CONNECTED_ITEM* item : it.second.itemsP )
385  {
386  // fixme: include vias
387  if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
388  it.second.totalLengthP += track->GetLength();
389  }
390 
391  for( auto& cpair : it.second.coupled )
392  {
393  int length = cpair.coupledN.Length();
394  int gap = cpair.coupledN.Distance( cpair.coupledP );
395 
396  gap -= cpair.parentN->GetWidth() / 2;
397  gap -= cpair.parentP->GetWidth() / 2;
398 
399  cpair.computedGap = gap;
400 
401  auto overlay = m_drcEngine->GetDebugOverlay();
402 
403  if( overlay )
404  {
405  overlay->SetIsFill(false);
406  overlay->SetIsStroke(true);
407  overlay->SetStrokeColor( RED );
408  overlay->SetLineWidth( 100000 );
409  overlay->Line( cpair.coupledP );
410  overlay->SetStrokeColor( BLUE );
411  overlay->Line( cpair.coupledN );
412  }
413 
414  drc_dbg( 10, " len %d gap %d l %d\n", length, gap,
415  cpair.parentP->GetLayer() );
416 
417  if( gapConstraint )
418  {
419  auto val = gapConstraint->GetValue();
420  bool insideRange = true;
421 
422  if( val.HasMin() && gap < val.Min() )
423  insideRange = false;
424 
425  if( val.HasMax() && gap > val.Max() )
426  insideRange = false;
427 
428 // if(val.HasMin() && val.HasMax() )
429  // drc_dbg(10, "Vmin %d vmax %d\n", val.Min(), val.Max() );
430 
431  cpair.couplingOK = insideRange;
432  }
433  else
434  {
435  cpair.couplingOK = true;
436  }
437 
438  if( cpair.couplingOK )
439  it.second.totalCoupled += length;
440  }
441 
442  int totalLen = std::max( it.second.totalLengthN, it.second.totalLengthP );
443  reportAux( wxString::Format( " - coupled length: %s, total length: %s",
444 
445  MessageTextFromValue( userUnits(), it.second.totalCoupled ),
446  MessageTextFromValue( userUnits(), totalLen ) ) );
447 
448  int totalUncoupled = totalLen - it.second.totalCoupled;
449 
450  bool uncoupledViolation = false;
451 
452  if( maxUncoupledConstraint )
453  {
454  auto val = maxUncoupledConstraint->GetValue();
455 
456  if ( val.HasMax() && totalUncoupled > val.Max() )
457  {
459 
460  m_msg = wxString::Format( _( "(%s maximum uncoupled length: %s; actual: %s)" ),
461  maxUncoupledConstraint->GetParentRule()->m_Name,
462  MessageTextFromValue( userUnits(), val.Max() ),
463  MessageTextFromValue( userUnits(), totalUncoupled ) );
464 
465  drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + m_msg );
466 
467  for( BOARD_CONNECTED_ITEM* offendingTrack : it.second.itemsP )
468  drce->AddItem( offendingTrack );
469 
470  for( BOARD_CONNECTED_ITEM* offendingTrack : it.second.itemsN )
471  drce->AddItem( offendingTrack );
472 
473  uncoupledViolation = true;
474 
475  drce->SetViolatingRule( maxUncoupledConstraint->GetParentRule() );
476 
477  reportViolation( drce, ( *it.second.itemsP.begin() )->GetPosition() );
478  }
479  }
480 
481  if ( gapConstraint && ( uncoupledViolation || !maxUncoupledConstraint ) )
482  {
483  for( auto& cpair : it.second.coupled )
484  {
485  if( !cpair.couplingOK )
486  {
487  auto val = gapConstraint->GetValue();
489 
490  m_msg = drcItem->GetErrorText() + " (" +
491  gapConstraint->GetParentRule()->m_Name + " ";
492 
493  if( val.HasMin() )
494  m_msg += wxString::Format( _( "minimum gap: %s; " ),
495  MessageTextFromValue( userUnits(), val.Min() ) );
496 
497  if( val.HasMax() )
498  m_msg += wxString::Format( _( "maximum gap: %s; " ),
499  MessageTextFromValue( userUnits(), val.Max() ) );
500 
501  m_msg += wxString::Format( _( "actual: %s)" ),
502  MessageTextFromValue( userUnits(), cpair.computedGap ) );
503 
504  drcItem->SetErrorMessage( m_msg );
505 
506  drcItem->AddItem( cpair.parentP );
507  drcItem->AddItem( cpair.parentN );
508 
509  drcItem->SetViolatingRule( gapConstraint->GetParentRule() );
510 
511  reportViolation( drcItem, cpair.parentP->GetPosition() );
512  }
513  }
514  }
515  }
516 
518 
519  return true;
520 }
521 
522 
524 {
526 }
527 
528 
529 namespace detail
530 {
532 }
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: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:253
virtual std::set< DRC_CONSTRAINT_T > GetConstraintTypes() const override
std::shared_ptr< KIGFX::VIEW_OVERLAY > GetDebugOverlay() const
Definition: drc_engine.h:99
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:80
ecoord SquaredLength() const
Definition: seg.h:355
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:684
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:71
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.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:128
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:344
const wxString & GetNetname() const
Definition: netinfo.h:119
#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 aConstraintId, const BOARD_ITEM *a, const BOARD_ITEM *b, PCB_LAYER_ID aLayer, REPORTER *aReporter=nullptr)
Definition: drc_engine.cpp:768
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:40
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
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:86
boost::optional< T > OPT
Definition: optional.h:7
bool IsCopperLayer(LAYER_NUM aLayerId)
Tests whether a layer is a copper layer.
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:44
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:171
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:176
int GetNetCode() const
Definition: netinfo.h:113
VECTOR2I B
Definition: seg.h:49