KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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-2023 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 <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>
29#include <drc/drc_rtree.h>
30
32
35
36#include <view/view_overlay.h>
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
50namespace test {
51
53{
54public:
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 wxT( "diff_pair_coupling" );
69 };
70
71 virtual const wxString GetDescription() const override
72 {
73 return wxT( "Tests differential pair coupling" );
74 }
75
76private:
78};
79
80};
81
82
83static bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip )
84{
85 SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
86
87 int64_t t_a = 0;
88 int64_t t_b = p.TCoef( p.B );
89
90 int64_t tproj_a = p.TCoef( n_proj_p.A );
91 int64_t tproj_b = p.TCoef( n_proj_p.B );
92
93 if( t_b < t_a )
94 std::swap( t_b, t_a );
95
96 if( tproj_b < tproj_a )
97 std::swap( tproj_b, tproj_a );
98
99 if( t_b <= tproj_a )
100 return false;
101
102 if( t_a >= tproj_b )
103 return false;
104
105 int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
106 std::vector<int64_t> tv( t, t + 4 );
107 std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
108
109 int64_t pLenSq = p.SquaredLength();
110
111 VECTOR2I dp = p.B - p.A;
112 pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
113 pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
114
115 pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
116 pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
117
118 nClip.A = n.LineProject( pClip.A );
119 nClip.B = n.LineProject( pClip.B );
120
121 return true;
122}
123
124
126{
127 bool operator<( const DIFF_PAIR_KEY& b ) const
128 {
129 if( netP < b.netP )
130 {
131 return true;
132 }
133 else if( netP > b.netP )
134 {
135 return false;
136 }
137 else // netP == b.netP
138 {
139 if( netN < b.netN )
140 return true;
141 else if( netN > b.netN )
142 return false;
143 else if( gapRuleName.IsEmpty() )
144 return gapRuleName < b.gapRuleName;
145 else
147 }
148 }
149
150 int netP, netN;
151 wxString gapRuleName;
153 std::optional<MINOPTMAX<int>> gapConstraint;
155 std::optional<MINOPTMAX<int>> uncoupledConstraint;
157};
158
160{
169
171 parentN( nullptr ),
172 parentP( nullptr ),
173 computedGap( 0 ),
175 couplingFailMin( false ),
176 couplingFailMax( false )
177 {}
178};
179
180
182{
183 std::set<BOARD_CONNECTED_ITEM*> itemsP, itemsN;
184 std::vector<DIFF_PAIR_COUPLED_SEGMENTS> coupled;
188};
189
190
192{
193 for( BOARD_CONNECTED_ITEM* itemP : aDp.itemsP )
194 {
195 PCB_TRACK* sp = dyn_cast<PCB_TRACK*>( itemP );
196 std::optional<DIFF_PAIR_COUPLED_SEGMENTS> bestCoupled;
197 int bestGap = std::numeric_limits<int>::max();
198
199 if( !sp )
200 continue;
201
202 for ( BOARD_CONNECTED_ITEM* itemN : aDp.itemsN )
203 {
204 PCB_TRACK* sn = dyn_cast<PCB_TRACK*> ( itemN );
205
206 if( !sn )
207 continue;
208
209 if( ( sn->GetLayerSet() & sp->GetLayerSet() ).none() )
210 continue;
211
212 SEG ssp ( sp->GetStart(), sp->GetEnd() );
213 SEG ssn ( sn->GetStart(), sn->GetEnd() );
214
215 // Segments that are ~ 1 IU in length per side are approximately parallel (tolerance is 1 IU)
216 // with everything and their parallel projection is < 1 IU, leading to bad distance calculations
217 if( ssp.SquaredLength() > 2 && ssn.SquaredLength() > 2 && ssp.ApproxParallel(ssn) )
218 {
220 bool coupled = commonParallelProjection( ssp, ssn, cpair.coupledP, cpair.coupledN );
221
222 if( coupled )
223 {
224 cpair.parentP = sp;
225 cpair.parentN = sn;
226 cpair.layer = sp->GetLayer();
227
228 int gap = (cpair.coupledP.A - cpair.coupledN.A).EuclideanNorm();
229 if( gap < bestGap )
230 {
231 bestGap = gap;
232 bestCoupled = cpair;
233 }
234 }
235
236 }
237 }
238
239 if( bestCoupled )
240 {
241 auto excludeSelf =
242 [&] ( BOARD_ITEM *aItem )
243 {
244 if( aItem == bestCoupled->parentN || aItem == bestCoupled->parentP )
245 {
246 return false;
247 }
248
249 if( aItem->Type() == PCB_TRACE_T || aItem->Type() == PCB_VIA_T )
250 {
251 auto bci = static_cast<BOARD_CONNECTED_ITEM*>( aItem );
252
253 if( bci->GetNetCode() == bestCoupled->parentN->GetNetCode()
254 || bci->GetNetCode() == bestCoupled->parentP->GetNetCode() )
255 return false;
256 }
257
258 return true;
259 };
260
261 SHAPE_SEGMENT checkSegStart( bestCoupled->coupledP.A, bestCoupled->coupledN.A );
262 SHAPE_SEGMENT checkSegEnd( bestCoupled->coupledP.B, bestCoupled->coupledN.B );
263 DRC_RTREE* tree = bestCoupled->parentP->GetBoard()->m_CopperItemRTreeCache.get();
264
265 // check if there's anything in between the segments suspected to be coupled. If
266 // there's nothing, assume they are really coupled.
267
268 if( !tree->CheckColliding( &checkSegStart, sp->GetLayer(), 0, excludeSelf )
269 && !tree->CheckColliding( &checkSegEnd, sp->GetLayer(), 0, excludeSelf ) )
270 {
271 aDp.coupled.push_back( *bestCoupled );
272 }
273 }
274 }
275}
276
277
278
280{
282
284
285 std::map<DIFF_PAIR_KEY, DIFF_PAIR_ITEMS> dpRuleMatches;
286
287 auto evaluateDpConstraints =
288 [&]( BOARD_ITEM *item ) -> bool
289 {
290 DIFF_PAIR_KEY key;
291 BOARD_CONNECTED_ITEM* citem = static_cast<BOARD_CONNECTED_ITEM*>( item );
292 NETINFO_ITEM* refNet = citem->GetNet();
293
294 if( refNet && DRC_ENGINE::IsNetADiffPair( m_board, refNet, key.netP, key.netN ) )
295 {
296 drc_dbg( 10, wxT( "eval dp %p\n" ), item );
297
298 const DRC_CONSTRAINT_T constraintsToCheck[] = {
301 };
302
303 for( int i = 0; i < 2; i++ )
304 {
305 DRC_CONSTRAINT constraint = m_drcEngine->EvalRules( constraintsToCheck[ i ],
306 item, nullptr,
307 item->GetLayer() );
308
309 if( constraint.IsNull() || constraint.GetSeverity() == RPT_SEVERITY_IGNORE )
310 continue;
311
312 drc_dbg( 10, wxT( "cns %d item %p\n" ), constraintsToCheck[i], item );
313
314 DRC_RULE* parentRule = constraint.GetParentRule();
315 wxString ruleName = parentRule ? parentRule->m_Name : constraint.GetName();
316
317 switch( constraintsToCheck[i] )
318 {
320 key.gapConstraint = constraint.GetValue();
321 key.gapRule = parentRule;
322 key.gapRuleName = ruleName;
323 break;
324
326 key.uncoupledConstraint = constraint.GetValue();
327 key.uncoupledRule = parentRule;
328 key.uncoupledRuleName = ruleName;
329 break;
330
331 default:
332 break;
333 }
334
335 if( refNet->GetNetCode() == key.netN )
336 dpRuleMatches[key].itemsN.insert( citem );
337 else
338 dpRuleMatches[key].itemsP.insert( citem );
339 }
340 }
341
342 return true;
343 };
344
345 m_board->GetConnectivity()->GetFromToCache()->Rebuild( m_board );
346
348 evaluateDpConstraints );
349
350 drc_dbg( 10, wxT( "dp rule matches %d\n" ), (int) dpRuleMatches.size() );
351
352 reportAux( wxT( "DPs evaluated:" ) );
353
354 for( auto& [ key, itemSet ] : dpRuleMatches )
355 {
356 NETINFO_ITEM *niP = m_board->GetNetInfo().GetNetItem( key.netP );
357 NETINFO_ITEM *niN = m_board->GetNetInfo().GetNetItem( key.netN );
358
359 assert( niP );
360 assert( niN );
361
362 wxString nameP = niP->GetNetname();
363 wxString nameN = niN->GetNetname();
364
365 reportAux( wxString::Format( wxT( "Rule '%s', DP: (+) %s - (-) %s" ),
366 key.gapRuleName, nameP, nameN ) );
367
369
370 itemSet.totalCoupled = 0;
371 itemSet.totalLengthN = 0;
372 itemSet.totalLengthP = 0;
373
374 drc_dbg(10, wxT( " coupled prims : %d\n" ), (int) itemSet.coupled.size() );
375
376 for( BOARD_CONNECTED_ITEM* item : itemSet.itemsN )
377 {
378 // fixme: include vias
379 if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
380 itemSet.totalLengthN += track->GetLength();
381 }
382
383 for( BOARD_CONNECTED_ITEM* item : itemSet.itemsP )
384 {
385 // fixme: include vias
386 if( PCB_TRACK* track = dyn_cast<PCB_TRACK*>( item ) )
387 itemSet.totalLengthP += track->GetLength();
388 }
389
390 for( DIFF_PAIR_COUPLED_SEGMENTS& dp : itemSet.coupled )
391 {
392 int length = dp.coupledN.Length();
393 int gap = dp.coupledN.Distance( dp.coupledP );
394
395 wxCHECK2( dp.parentN && dp.parentP, continue );
396
397 gap -= dp.parentN->GetWidth() / 2;
398 gap -= dp.parentP->GetWidth() / 2;
399
400 dp.computedGap = gap;
401
402 std::shared_ptr<KIGFX::VIEW_OVERLAY> overlay = m_drcEngine->GetDebugOverlay();
403
404 if( overlay )
405 {
406 overlay->SetIsFill(false);
407 overlay->SetIsStroke(true);
408 overlay->SetStrokeColor( RED );
409 overlay->SetLineWidth( 100000 );
410 overlay->Line( dp.coupledP );
411 overlay->SetStrokeColor( BLUE );
412 overlay->Line( dp.coupledN );
413 }
414
415 drc_dbg( 10, wxT( " len %d gap %d l %d\n" ),
416 length,
417 gap,
418 dp.parentP->GetLayer() );
419
420 if( key.gapConstraint )
421 {
422 if( key.gapConstraint->HasMin()
423 && key.gapConstraint->Min() >= 0
424 && ( gap < key.gapConstraint->Min() - epsilon ) )
425 {
426 dp.couplingFailMin = true;
427 }
428
429 if( key.gapConstraint->HasMax()
430 && key.gapConstraint->Max() >= 0
431 && ( gap > key.gapConstraint->Max() + epsilon ) )
432 {
433 dp.couplingFailMax = true;
434 }
435 }
436
437 if( !dp.couplingFailMin && !dp.couplingFailMax )
438 itemSet.totalCoupled += length;
439 }
440
441 int totalLen = std::max( itemSet.totalLengthN, itemSet.totalLengthP );
442 reportAux( wxString::Format( wxT( " - coupled length: %s, total length: %s" ),
443 MessageTextFromValue( itemSet.totalCoupled ),
444 MessageTextFromValue( totalLen ) ) );
445
446 int totalUncoupled = totalLen - itemSet.totalCoupled;
447
448 bool uncoupledViolation = false;
449
450 if( key.uncoupledConstraint && ( !itemSet.itemsP.empty() || !itemSet.itemsN.empty() ) )
451 {
452 const MINOPTMAX<int>& val = *key.uncoupledConstraint;
453
454 if( val.HasMax() && val.Max() >= 0 && totalUncoupled > val.Max() )
455 {
457 wxString msg = formatMsg( _( "(%s maximum uncoupled length %s; actual %s)" ),
458 key.uncoupledRuleName,
459 val.Max(),
460 totalUncoupled );
461
462 drce->SetErrorMessage( drce->GetErrorText() + wxS( " " ) + msg );
463
464 BOARD_CONNECTED_ITEM* item = nullptr;
465 auto p_it = itemSet.itemsP.begin();
466 auto n_it = itemSet.itemsN.begin();
467
468 if( p_it != itemSet.itemsP.end() )
469 {
470 item = *p_it;
471 drce->AddItem( *p_it );
472 p_it++;
473 }
474
475 if( n_it != itemSet.itemsN.end() )
476 {
477 item = *n_it;
478 drce->AddItem( *n_it );
479 n_it++;
480 }
481
482 while( p_it != itemSet.itemsP.end() )
483 drce->AddItem( *p_it++ );
484
485 while( n_it != itemSet.itemsN.end() )
486 drce->AddItem( *n_it++ );
487
488 uncoupledViolation = true;
489
490 drce->SetViolatingRule( key.uncoupledRule );
491
492 reportViolation( drce, item->GetPosition(), item->GetLayer() );
493 }
494 }
495
496 if( key.gapConstraint && ( uncoupledViolation || !key.uncoupledConstraint ) )
497 {
498 for( DIFF_PAIR_COUPLED_SEGMENTS& dp : itemSet.coupled )
499 {
500 wxCHECK2( dp.parentP && dp.parentN, continue );
501
502 if( ( dp.couplingFailMin || dp.couplingFailMax ) )
503 {
504 // We have a candidate violation, now we need to re-query for a constraint
505 // given the actual items, because there may be a location-based rule in play.
507 dp.parentP, dp.parentN,
508 dp.parentP->GetLayer() );
509 MINOPTMAX<int> val = constraint.GetValue();
510
511 if( !val.HasMin() || val.Min() < 0 || dp.computedGap >= val.Min() )
512 dp.couplingFailMin = false;
513
514 if( !val.HasMax() || val.Max() < 0 || dp.computedGap <= val.Max() )
515 dp.couplingFailMax = false;
516
517 if( !dp.couplingFailMin && !dp.couplingFailMax )
518 continue;
519
521 wxString msg;
522
523 if( dp.couplingFailMin )
524 {
525 msg = formatMsg( _( "(%s minimum gap %s; actual %s)" ),
526 key.gapRuleName,
527 val.Min(),
528 dp.computedGap );
529 }
530 else if( dp.couplingFailMax )
531 {
532 msg = formatMsg( _( "(%s maximum gap %s; actual %s)" ),
533 key.gapRuleName,
534 val.Max(),
535 dp.computedGap );
536 }
537
538 drcItem->SetErrorMessage( drcItem->GetErrorText() + wxS( " " ) + msg );
539
540 BOARD_CONNECTED_ITEM* item = nullptr;
541
542 if( dp.parentP )
543 {
544 item = dp.parentP;
545 drcItem->AddItem( dp.parentP );
546 }
547
548 if( dp.parentN )
549 {
550 item = dp.parentN;
551 drcItem->AddItem( dp.parentN );
552 }
553
554 drcItem->SetViolatingRule( key.gapRule );
555
556 reportViolation( drcItem, item->GetPosition(), item->GetLayer() );
557 }
558 }
559 }
560 }
561
563
564 return true;
565}
566
567
568namespace detail
569{
571}
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:77
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:226
virtual LSET GetLayerSet() const
Return a std::bitset of all layers on which the item physically resides.
Definition: board_item.h:231
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:276
const NETINFO_LIST & GetNetInfo() const
Definition: board.h:832
BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Definition: board.cpp:775
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:441
wxString GetName() const
Definition: drc_rule.h:149
SEVERITY GetSeverity() const
Definition: drc_rule.h:162
const MINOPTMAX< int > & GetValue() const
Definition: drc_rule.h:141
DRC_RULE * GetParentRule() const
Definition: drc_rule.h:145
bool IsNull() const
Definition: drc_rule.h:136
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:675
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:331
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:177
wxString m_Name
Definition: drc_rule.h:112
Represent a DRC "provider" which runs some DRC functions over a BOARD and spits out DRC_ITEM and posi...
wxString formatMsg(const wxString &aFormatString, const wxString &aSource, double aConstraint, double aActual)
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)
DRC_ENGINE * m_drcEngine
void reportAux(const wxString &aMsg)
virtual void reportRuleStatistics()
virtual VECTOR2I GetPosition() const
Definition: eda_item.h:239
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Return a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:863
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:56
const wxString & GetNetname() const
Definition: netinfo.h:114
int GetNetCode() const
Definition: netinfo.h:108
NETINFO_ITEM * GetNetItem(int aNetCode) const
int GetWidth() const
Definition: pcb_track.h:107
const VECTOR2I & GetStart() const
Definition: pcb_track.h:113
const VECTOR2I & GetEnd() const
Definition: pcb_track.h:110
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:326
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:402
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:388
ecoord SquaredLength() const
Definition: seg.h:331
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:329
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:312
wxString MessageTextFromValue(double aValue, bool aAddUnitLabel=true, EDA_DATA_TYPE aType=EDA_DATA_TYPE::DISTANCE) const
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
#define drc_dbg(level, fmt,...)
Definition: drc_engine.h:58
@ DRCE_DIFF_PAIR_GAP_OUT_OF_RANGE
Definition: drc_item.h:99
@ DRCE_DIFF_PAIR_UNCOUPLED_LENGTH_TOO_LONG
Definition: drc_item.h:100
DRC_CONSTRAINT_T
Definition: drc_rule.h:45
@ DIFF_PAIR_GAP_CONSTRAINT
Definition: drc_rule.h:66
@ MAX_UNCOUPLED_CONSTRAINT
Definition: drc_rule.h:67
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:60
@ UNDEFINED_LAYER
Definition: layer_ids.h:61
std::shared_ptr< PNS_LOG_VIEWER_OVERLAY > overlay
Definition: playground.cpp:36
@ RPT_SEVERITY_IGNORE
const double epsilon
std::vector< FAB_LAYER_COLOR > dummy
std::set< BOARD_CONNECTED_ITEM * > itemsN
std::vector< DIFF_PAIR_COUPLED_SEGMENTS > coupled
std::set< BOARD_CONNECTED_ITEM * > itemsP
std::optional< MINOPTMAX< int > > uncoupledConstraint
std::optional< MINOPTMAX< int > > gapConstraint
bool operator<(const DIFF_PAIR_KEY &b) const
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:128
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:97
@ PCB_ARC_T
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:98
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:96
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:129