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>
30#include <drc/drc_rtree.h>
31
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
51namespace test {
52
54{
55public:
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
77private:
79};
80
81};
82
83
84static bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip )
85{
86 SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
87
88 int64_t t_a = 0;
89 int64_t t_b = p.TCoef( p.B );
90
91 int64_t tproj_a = p.TCoef( n_proj_p.A );
92 int64_t tproj_b = p.TCoef( n_proj_p.B );
93
94 if( t_b < t_a )
95 std::swap( t_b, t_a );
96
97 if( tproj_b < tproj_a )
98 std::swap( tproj_b, tproj_a );
99
100 if( t_b <= tproj_a )
101 return false;
102
103 if( t_a >= tproj_b )
104 return false;
105
106 int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
107 std::vector<int64_t> tv( t, t + 4 );
108 std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
109
110 int64_t pLenSq = p.SquaredLength();
111
112 VECTOR2I dp = p.B - p.A;
113 pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
114 pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
115
116 pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
117 pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
118
119 nClip.A = n.LineProject( pClip.A );
120 nClip.B = n.LineProject( pClip.B );
121
122 return true;
123}
124
125
127{
128 bool operator<( const DIFF_PAIR_KEY& b ) const
129 {
130 if( netP < b.netP )
131 {
132 return true;
133 }
134 else if( netP > b.netP )
135 {
136 return false;
137 }
138 else // netP == b.netP
139 {
140 if( netN < b.netN )
141 return true;
142 else if( netN > b.netN )
143 return false;
144 else
145 return parentRule < b.parentRule;
146 }
147 }
148
149 int netP, netN;
151};
152
154{
162
164 parentN( nullptr ),
165 parentP( nullptr ),
166 computedGap( 0 ),
168 couplingOK( false )
169 {}
170};
171
172
174{
175 std::set<BOARD_CONNECTED_ITEM*> itemsP, itemsN;
176 std::vector<DIFF_PAIR_COUPLED_SEGMENTS> coupled;
180};
181
182
184{
185 for( BOARD_CONNECTED_ITEM* itemP : aDp.itemsP )
186 {
187 PCB_TRACK* sp = dyn_cast<PCB_TRACK*>( itemP );
188 std::optional<DIFF_PAIR_COUPLED_SEGMENTS> bestCoupled;
189 int bestGap = std::numeric_limits<int>::max();
190
191 if( !sp )
192 continue;
193
194 for ( BOARD_CONNECTED_ITEM* itemN : aDp.itemsN )
195 {
196 PCB_TRACK* sn = dyn_cast<PCB_TRACK*> ( itemN );
197
198 if( !sn )
199 continue;
200
201 if( ( sn->GetLayerSet() & sp->GetLayerSet() ).none() )
202 continue;
203
204 SEG ssp ( sp->GetStart(), sp->GetEnd() );
205 SEG ssn ( sn->GetStart(), sn->GetEnd() );
206
207 // Segments that are ~ 1 IU in length per side are approximately parallel (tolerance is 1 IU)
208 // with everything and their parallel projection is < 1 IU, leading to bad distance calculations
209 if( ssp.SquaredLength() > 2 && ssn.SquaredLength() > 2 && ssp.ApproxParallel(ssn) )
210 {
212 bool coupled = commonParallelProjection( ssp, ssn, cpair.coupledP, cpair.coupledN );
213
214 if( coupled )
215 {
216 cpair.parentP = sp;
217 cpair.parentN = sn;
218 cpair.layer = sp->GetLayer();
219
220 int gap = (cpair.coupledP.A - cpair.coupledN.A).EuclideanNorm();
221 if( gap < bestGap )
222 {
223 bestGap = gap;
224 bestCoupled = cpair;
225 }
226 }
227
228 }
229 }
230
231 if( bestCoupled )
232 {
233 auto excludeSelf =
234 [&] ( BOARD_ITEM *aItem )
235 {
236 if( aItem == bestCoupled->parentN || aItem == bestCoupled->parentP )
237 {
238 return false;
239 }
240
241 if( aItem->Type() == PCB_TRACE_T || aItem->Type() == PCB_VIA_T )
242 {
243 auto bci = static_cast<BOARD_CONNECTED_ITEM*>( aItem );
244
245 if( bci->GetNetCode() == bestCoupled->parentN->GetNetCode()
246 || bci->GetNetCode() == bestCoupled->parentP->GetNetCode() )
247 return false;
248 }
249
250 return true;
251 };
252
253 SHAPE_SEGMENT checkSegStart( bestCoupled->coupledP.A, bestCoupled->coupledN.A );
254 SHAPE_SEGMENT checkSegEnd( bestCoupled->coupledP.B, bestCoupled->coupledN.B );
255 DRC_RTREE* tree = bestCoupled->parentP->GetBoard()->m_CopperItemRTreeCache.get();
256
257 // check if there's anything in between the segments suspected to be coupled. If
258 // there's nothing, assume they are really coupled.
259
260 if( !tree->CheckColliding( &checkSegStart, sp->GetLayer(), 0, excludeSelf )
261 && !tree->CheckColliding( &checkSegEnd, sp->GetLayer(), 0, excludeSelf ) )
262 {
263 aDp.coupled.push_back( *bestCoupled );
264 }
265 }
266 }
267}
268
269
270
272{
274
275
276
277 std::map<DIFF_PAIR_KEY, DIFF_PAIR_ITEMS> dpRuleMatches;
278
279 auto evaluateDpConstraints =
280 [&]( BOARD_ITEM *item ) -> bool
281 {
282 DIFF_PAIR_KEY key;
283 BOARD_CONNECTED_ITEM* citem = static_cast<BOARD_CONNECTED_ITEM*>( item );
284 NETINFO_ITEM* refNet = citem->GetNet();
285
286 if( refNet && DRC_ENGINE::IsNetADiffPair( m_board, refNet, key.netP, key.netN ) )
287 {
288 drc_dbg( 10, wxT( "eval dp %p\n" ), item );
289
290 const DRC_CONSTRAINT_T constraintsToCheck[] = {
293 };
294
295 for( int i = 0; i < 2; i++ )
296 {
297 auto constraint = m_drcEngine->EvalRules( constraintsToCheck[ i ], item,
298 nullptr, item->GetLayer() );
299
300 if( constraint.IsNull() || constraint.GetSeverity() == RPT_SEVERITY_IGNORE )
301 continue;
302
303 drc_dbg( 10, wxT( "cns %d item %p\n" ), constraintsToCheck[i], item );
304
305 key.parentRule = constraint.GetParentRule();
306
307 if( refNet->GetNetCode() == key.netN )
308 dpRuleMatches[key].itemsN.insert( citem );
309 else
310 dpRuleMatches[key].itemsP.insert( citem );
311 }
312 }
313
314 return true;
315 };
316
317 m_board->GetConnectivity()->GetFromToCache()->Rebuild( m_board );
318
320 evaluateDpConstraints );
321
322 drc_dbg( 10, wxT( "dp rule matches %d\n" ), (int) dpRuleMatches.size() );
323
324
325 reportAux( wxT( "DPs evaluated:" ) );
326
327 for( auto& [ key, itemSet ] : dpRuleMatches )
328 {
329 NETINFO_ITEM *niP = m_board->GetNetInfo().GetNetItem( key.netP );
330 NETINFO_ITEM *niN = m_board->GetNetInfo().GetNetItem( key.netN );
331
332 assert( niP );
333 assert( niN );
334
335 wxString nameP = niP->GetNetname();
336 wxString nameN = niN->GetNetname();
337
338 reportAux( wxString::Format( wxT( "Rule '%s', DP: (+) %s - (-) %s" ),
339 key.parentRule->m_Name,
340 nameP,
341 nameN ) );
342
344
345 itemSet.totalCoupled = 0;
346 itemSet.totalLengthN = 0;
347 itemSet.totalLengthP = 0;
348
349 drc_dbg(10, wxT( " coupled prims : %d\n" ), (int) itemSet.coupled.size() );
350
351 std::optional<DRC_CONSTRAINT> gapConstraint
352 = key.parentRule->FindConstraint( DIFF_PAIR_GAP_CONSTRAINT );
353
354 std::optional<DRC_CONSTRAINT> maxUncoupledConstraint
355 = key.parentRule->FindConstraint( DIFF_PAIR_MAX_UNCOUPLED_CONSTRAINT );
356
357 for( BOARD_CONNECTED_ITEM* item : itemSet.itemsN )
358 {
359 // fixme: include vias
360 if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
361 itemSet.totalLengthN += track->GetLength();
362 }
363
364 for( BOARD_CONNECTED_ITEM* item : itemSet.itemsP )
365 {
366 // fixme: include vias
367 if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
368 itemSet.totalLengthP += track->GetLength();
369 }
370
371 for( DIFF_PAIR_COUPLED_SEGMENTS& dp : itemSet.coupled )
372 {
373 int length = dp.coupledN.Length();
374 int gap = dp.coupledN.Distance( dp.coupledP );
375
376 gap -= dp.parentN->GetWidth() / 2;
377 gap -= dp.parentP->GetWidth() / 2;
378
379 dp.computedGap = gap;
380
382
383 if( overlay )
384 {
385 overlay->SetIsFill(false);
386 overlay->SetIsStroke(true);
387 overlay->SetStrokeColor( RED );
388 overlay->SetLineWidth( 100000 );
389 overlay->Line( dp.coupledP );
390 overlay->SetStrokeColor( BLUE );
391 overlay->Line( dp.coupledN );
392 }
393
394 drc_dbg( 10, wxT( " len %d gap %d l %d\n" ),
395 length,
396 gap,
397 dp.parentP->GetLayer() );
398
399 if( gapConstraint )
400 {
401 auto val = gapConstraint->GetValue();
402 bool insideRange = true;
403
404 if( val.HasMin() && gap < val.Min() )
405 insideRange = false;
406
407 if( val.HasMax() && gap > val.Max() )
408 insideRange = false;
409
410 dp.couplingOK = insideRange;
411 }
412 else
413 {
414 dp.couplingOK = true;
415 }
416
417 if( dp.couplingOK )
418 itemSet.totalCoupled += length;
419 }
420
421 int totalLen = std::max( itemSet.totalLengthN, itemSet.totalLengthP );
422 reportAux( wxString::Format( wxT( " - coupled length: %s, total length: %s" ),
423 MessageTextFromValue( itemSet.totalCoupled ),
424 MessageTextFromValue( totalLen ) ) );
425
426 int totalUncoupled = totalLen - itemSet.totalCoupled;
427
428 bool uncoupledViolation = false;
429
430 if( maxUncoupledConstraint && ( !itemSet.itemsP.empty() || ! itemSet.itemsN.empty() ) )
431 {
432 const MINOPTMAX<int>& val = maxUncoupledConstraint->GetValue();
433
434 if ( val.HasMax() && totalUncoupled > val.Max() )
435 {
437 wxString msg;
438
439 msg = wxString::Format( _( "(%s maximum uncoupled length: %s; actual: %s)" ),
440 maxUncoupledConstraint->GetParentRule()->m_Name,
441 MessageTextFromValue( val.Max() ),
442 MessageTextFromValue( totalUncoupled ) );
443
444 drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + msg );
445
446 BOARD_CONNECTED_ITEM* item = nullptr;
447 auto p_it = itemSet.itemsP.begin();
448 auto n_it = itemSet.itemsN.begin();
449
450 if( p_it != itemSet.itemsP.end() )
451 {
452 item = *p_it;
453 drce->AddItem( *p_it );
454 p_it++;
455 }
456
457 if( n_it != itemSet.itemsN.end() )
458 {
459 item = *n_it;
460 drce->AddItem( *n_it );
461 n_it++;
462 }
463
464 while( p_it != itemSet.itemsP.end() )
465 drce->AddItem( *p_it++ );
466
467 while( n_it != itemSet.itemsN.end() )
468 drce->AddItem( *n_it++ );
469
470 uncoupledViolation = true;
471
472 drce->SetViolatingRule( maxUncoupledConstraint->GetParentRule() );
473
474 reportViolation( drce, item->GetPosition(), item->GetLayer() );
475 }
476 }
477
478 if ( gapConstraint && ( uncoupledViolation || !maxUncoupledConstraint ) )
479 {
480 for( DIFF_PAIR_COUPLED_SEGMENTS& dp : itemSet.coupled )
481 {
482 if( !dp.couplingOK && ( dp.parentP || dp.parentN ) )
483 {
484 MINOPTMAX<int> val = gapConstraint->GetValue();
486 wxString msg;
487
488 msg = drcItem->GetErrorText() + wxT( " (" ) +
489 gapConstraint->GetParentRule()->m_Name + wxS( " " );
490
491 if( val.HasMin() )
492 msg += wxString::Format( _( "minimum gap: %s; " ),
493 MessageTextFromValue( val.Min() ) );
494
495 if( val.HasMax() )
496 msg += wxString::Format( _( "maximum gap: %s; " ),
497 MessageTextFromValue( val.Max() ) );
498
499 msg += wxString::Format( _( "actual: %s)" ),
501
502 drcItem->SetErrorMessage( msg );
503
504 BOARD_CONNECTED_ITEM* item = nullptr;
505
506 if( dp.parentP )
507 {
508 item = dp.parentP;
509 drcItem->AddItem( dp.parentP );
510 }
511
512 if( dp.parentN )
513 {
514 item = dp.parentN;
515 drcItem->AddItem( dp.parentN );
516 }
517
518 drcItem->SetViolatingRule( gapConstraint->GetParentRule() );
519
520 reportViolation( drcItem, item->GetPosition(), item->GetLayer() );
521 }
522 }
523 }
524 }
525
527
528 return true;
529}
530
531
532namespace detail
533{
535}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
NETINFO_ITEM * GetNet() const
Return #NET_INFO object for a given item.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:50
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:167
virtual LSET GetLayerSet() const
Return a std::bitset of all layers on which the item physically resides.
Definition: board_item.h:172
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:265
const NETINFO_LIST & GetNetInfo() const
Definition: board.h:763
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:424
BOARD * GetBoard() const
Definition: drc_engine.h:89
std::shared_ptr< KIGFX::VIEW_OVERLAY > GetDebugOverlay() const
Definition: drc_engine.h:105
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:671
static bool IsNetADiffPair(BOARD *aBoard, NETINFO_ITEM *aNet, int &aNetP, int &aNetN)
static std::shared_ptr< DRC_ITEM > Create(int aErrorCode)
Constructs a DRC_ITEM for the given error code.
Definition: drc_item.cpp:325
Implement an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:48
bool CheckColliding(SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
Definition: drc_rtree.h:174
Represent a DRC "provider" which runs some DRC functions over a BOARD and spits out #DRC_ITEMs and po...
int forEachGeometryItem(const std::vector< KICAD_T > &aTypes, LSET aLayers, const std::function< bool(BOARD_ITEM *)> &aFunc)
virtual void reportViolation(std::shared_ptr< DRC_ITEM > &item, const VECTOR2I &aMarkerPos, int aMarkerLayer)
virtual void reportAux(wxString fmt,...)
DRC_ENGINE * m_drcEngine
virtual void reportRuleStatistics()
virtual VECTOR2I GetPosition() const
Definition: eda_item.h:249
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Return a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:773
T Min() const
Definition: minoptmax.h:33
bool HasMax() const
Definition: minoptmax.h:38
bool HasMin() const
Definition: minoptmax.h:37
T Max() const
Definition: minoptmax.h:34
Handle the data for a net.
Definition: netinfo.h:66
const wxString & GetNetname() const
Definition: netinfo.h:119
int GetNetCode() const
Definition: netinfo.h:113
NETINFO_ITEM * GetNetItem(int aNetCode) const
int GetWidth() const
Definition: pcb_track.h:105
const VECTOR2I & GetStart() const
Definition: pcb_track.h:111
const VECTOR2I & GetEnd() const
Definition: pcb_track.h:108
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
int Length() const
Return the length (this).
Definition: seg.h:351
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.h:291
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:403
ecoord SquaredLength() const
Definition: seg.h:356
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:319
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:302
wxString MessageTextFromValue(double aValue, bool aAddUnitLabel=true, EDA_DATA_TYPE aType=EDA_DATA_TYPE::DISTANCE)
A lower-precision version of StringFromValue().
virtual bool Run() override
Run this provider against the given PCB with configured options (if any).
@ BLUE
Definition: color4d.h:56
@ RED
Definition: color4d.h:59
The common library.
#define drc_dbg(level, fmt,...)
Definition: drc_engine.h:58
@ DRCE_DIFF_PAIR_GAP_OUT_OF_RANGE
Definition: drc_item.h:98
@ DRCE_DIFF_PAIR_UNCOUPLED_LENGTH_TOO_LONG
Definition: drc_item.h:99
DRC_CONSTRAINT_T
Definition: drc_rule.h:44
@ DIFF_PAIR_MAX_UNCOUPLED_CONSTRAINT
Definition: drc_rule.h:66
@ DIFF_PAIR_GAP_CONSTRAINT
Definition: drc_rule.h:65
static bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
static void extractDiffPairCoupledItems(DIFF_PAIR_ITEMS &aDp)
#define _(s)
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59
@ UNDEFINED_LAYER
Definition: layer_ids.h:60
std::shared_ptr< PNS_LOG_VIEWER_OVERLAY > overlay
Definition: playground.cpp:36
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
@ RPT_SEVERITY_IGNORE
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:74
std::set< BOARD_CONNECTED_ITEM * > itemsN
std::vector< DIFF_PAIR_COUPLED_SEGMENTS > coupled
std::set< BOARD_CONNECTED_ITEM * > itemsP
bool operator<(const DIFF_PAIR_KEY &b) const
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:102
@ PCB_ARC_T
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:103
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:101
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:105