1 /* 2 * KiRouter - a push-and-(sometimes-)shove PCB router 3 * 4 * Copyright (C) 2013-2015 CERN 5 * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors. 6 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch> 7 * 8 * This program is free software: you can redistribute it and/or modify it 9 * under the terms of the GNU General Public License as published by the 10 * Free Software Foundation, either version 3 of the License, or (at your 11 * option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License along 19 * with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 22 23 #ifndef __PNS_DIFF_PAIR_H 24 #define __PNS_DIFF_PAIR_H 25 26 #include <vector> 27 28 #include "pns_line.h" 29 #include "pns_via.h" 30 #include "pns_link_holder.h" 31 32 #include "ranged_num.h" 33 34 namespace PNS { 35 36 class DIFF_PAIR; 37 38 /** 39 * Define a "gateway" for routing a differential pair - e.g. a pair of points (anchors) with 40 * certain orientation, spacing and (optionally) predefined entry paths. The routing algorithm 41 * connects such gateways with parallel lines, thus creating a differential pair. 42 */ 43 class DP_GATEWAY 44 { 45 public: 46 DP_GATEWAY( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN, bool aIsDiagonal, 47 int aAllowedEntryAngles = DIRECTION_45::ANG_OBTUSE, int aPriority = 0 ) : m_anchorP(aAnchorP)48 m_anchorP( aAnchorP ), 49 m_anchorN( aAnchorN ), m_isDiagonal( aIsDiagonal ), 50 m_allowedEntryAngles( aAllowedEntryAngles ), m_priority( aPriority ) 51 { 52 m_hasEntryLines = false; 53 } 54 ~DP_GATEWAY()55 ~DP_GATEWAY() 56 { 57 } 58 59 /** 60 * @return true if the gateway anchors lie on a diagonal line. 61 */ IsDiagonal()62 bool IsDiagonal() const 63 { 64 return m_isDiagonal; 65 } 66 AnchorP()67 const VECTOR2I& AnchorP() const { return m_anchorP; } 68 AnchorN()69 const VECTOR2I& AnchorN() const { return m_anchorN; } 70 71 /** 72 * @return a mask of 45-degree entry directions allowed for the gateway. 73 */ AllowedAngles()74 int AllowedAngles () const { return m_allowedEntryAngles; } 75 76 /** 77 * @return priority/score value for gateway matching. 78 */ Priority()79 int Priority() const 80 { 81 return m_priority; 82 } 83 SetPriority(int aPriority)84 void SetPriority(int aPriority) 85 { 86 m_priority = aPriority; 87 } 88 SetEntryLines(const SHAPE_LINE_CHAIN & aEntryP,const SHAPE_LINE_CHAIN & aEntryN)89 void SetEntryLines( const SHAPE_LINE_CHAIN& aEntryP, const SHAPE_LINE_CHAIN& aEntryN ) 90 { 91 m_entryP = aEntryP; 92 m_entryN = aEntryN; 93 m_hasEntryLines = true; 94 } 95 EntryP()96 const SHAPE_LINE_CHAIN& EntryP() const { return m_entryP; } EntryN()97 const SHAPE_LINE_CHAIN& EntryN() const { return m_entryN; } 98 const DIFF_PAIR Entry() const ; 99 100 void Reverse(); 101 HasEntryLines()102 bool HasEntryLines () const 103 { 104 return m_hasEntryLines; 105 } 106 107 private: 108 SHAPE_LINE_CHAIN m_entryP, m_entryN; 109 bool m_hasEntryLines; 110 VECTOR2I m_anchorP, m_anchorN; 111 bool m_isDiagonal; 112 int m_allowedEntryAngles; 113 int m_priority; 114 }; 115 116 /** 117 * Store starting/ending primitives (pads, vias or segments) for a differential pair. 118 */ 119 class DP_PRIMITIVE_PAIR 120 { 121 public: DP_PRIMITIVE_PAIR()122 DP_PRIMITIVE_PAIR(): 123 m_primP( nullptr ), m_primN( nullptr ) {}; 124 125 DP_PRIMITIVE_PAIR( const DP_PRIMITIVE_PAIR& aOther ); 126 DP_PRIMITIVE_PAIR( ITEM* aPrimP, ITEM* aPrimN ); 127 DP_PRIMITIVE_PAIR( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN ); 128 129 ~DP_PRIMITIVE_PAIR(); 130 131 void SetAnchors( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN ); 132 AnchorP()133 const VECTOR2I& AnchorP() const { return m_anchorP; } AnchorN()134 const VECTOR2I& AnchorN() const { return m_anchorN; } 135 136 DP_PRIMITIVE_PAIR& operator=( const DP_PRIMITIVE_PAIR& aOther ); 137 PrimP()138 ITEM* PrimP() const { return m_primP; } PrimN()139 ITEM* PrimN() const { return m_primN; } 140 141 bool Directional() const; 142 143 DIRECTION_45 DirP() const; 144 DIRECTION_45 DirN() const; 145 146 147 void CursorOrientation( const VECTOR2I& aCursorPos, VECTOR2I& aMidpoint, 148 VECTOR2I& aDirection ) const; 149 dump()150 void dump() 151 { 152 printf( "-- Prim-P %p anchor [%d, %d]\n", m_primP, m_anchorP.x, m_anchorP.y ); 153 printf( "-- Prim-N %p anchor [%d, %d]\n", m_primN, m_anchorN.x, m_anchorN.y ); 154 } 155 156 private: 157 DIRECTION_45 anchorDirection( const ITEM* aItem, const VECTOR2I& aP ) const; 158 159 ITEM* m_primP; 160 ITEM* m_primN; 161 VECTOR2I m_anchorP, m_anchorN; 162 }; 163 164 /** 165 * A set of gateways calculated for the cursor or starting/ending primitive pair. 166 */ 167 class DP_GATEWAYS 168 { 169 public: DP_GATEWAYS(int aGap)170 DP_GATEWAYS( int aGap ): 171 m_gap( aGap ), 172 m_viaGap( aGap ) 173 { 174 // Do not leave uninitialized members, and keep static analyzer quiet: 175 m_viaDiameter = 0; 176 m_fitVias = true; 177 } 178 Clear()179 void Clear() { m_gateways.clear(); } 180 181 void SetFitVias( bool aEnable, int aDiameter = 0, int aViaGap = -1 ) 182 { 183 m_fitVias = aEnable; 184 m_viaDiameter = aDiameter; 185 186 if( aViaGap < 0 ) 187 m_viaGap = m_gap; 188 else 189 m_viaGap = aViaGap; 190 } 191 192 193 void BuildForCursor( const VECTOR2I& aCursorPos ); 194 void BuildOrthoProjections( DP_GATEWAYS& aEntries, const VECTOR2I& aCursorPos, 195 int aOrthoScore ); 196 void BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries = false, 197 bool aViaMode = false ); 198 void BuildFromPrimitivePair( const DP_PRIMITIVE_PAIR& aPair, bool aPreferDiagonal ); 199 200 bool FitGateways( DP_GATEWAYS& aEntry, DP_GATEWAYS& aTarget, bool aPrefDiagonal, 201 DIFF_PAIR& aDp ); 202 Gateways()203 std::vector<DP_GATEWAY>& Gateways() { return m_gateways; } 204 CGateways()205 const std::vector<DP_GATEWAY>& CGateways() const { return m_gateways; } 206 207 void FilterByOrientation( int aAngleMask, DIRECTION_45 aRefOrientation ); 208 209 private: 210 struct DP_CANDIDATE 211 { 212 SHAPE_LINE_CHAIN p, n; 213 VECTOR2I gw_p, gw_n; 214 int score; 215 }; 216 217 bool checkDiagonalAlignment( const VECTOR2I& a, const VECTOR2I& b ) const; 218 void buildDpContinuation( const DP_PRIMITIVE_PAIR& aPair, bool aIsDiagonal ); 219 void buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n ); 220 221 int m_gap; 222 int m_viaGap; 223 int m_viaDiameter; 224 bool m_fitVias; 225 226 std::vector<DP_GATEWAY> m_gateways; 227 }; 228 229 230 /** 231 * Basic class for a differential pair. Stores two PNS_LINEs (for positive and negative nets, 232 * respectively), the gap and coupling constraints. 233 */ 234 class DIFF_PAIR : public LINK_HOLDER 235 { 236 public: 237 struct COUPLED_SEGMENTS 238 { COUPLED_SEGMENTSCOUPLED_SEGMENTS239 COUPLED_SEGMENTS ( const SEG& aCoupledP, const SEG& aParentP, int aIndexP, 240 const SEG& aCoupledN, const SEG& aParentN, int aIndexN ) : 241 coupledP( aCoupledP ), 242 coupledN( aCoupledN ), 243 parentP( aParentP ), 244 parentN( aParentN ), 245 indexP( aIndexP ), 246 indexN( aIndexN ) 247 {} 248 249 SEG coupledP; 250 SEG coupledN; 251 SEG parentP; 252 SEG parentN; 253 int indexP; 254 int indexN; 255 }; 256 257 typedef std::vector<COUPLED_SEGMENTS> COUPLED_SEGMENTS_VEC; 258 DIFF_PAIR()259 DIFF_PAIR() : 260 LINK_HOLDER( ITEM::DIFF_PAIR_T ), 261 m_hasVias( false ) 262 { 263 // Initialize some members, to avoid uninitialized variables. 264 m_net_p = 0; 265 m_net_n = 0;; 266 m_width = 0; 267 m_gap = 0; 268 m_viaGap = 0; 269 m_maxUncoupledLength = 0; 270 m_chamferLimit = 0; 271 } 272 DIFF_PAIR(int aGap)273 DIFF_PAIR( int aGap ) : 274 LINK_HOLDER( ITEM::DIFF_PAIR_T ), 275 m_hasVias( false ) 276 { 277 m_gapConstraint = aGap; 278 279 // Initialize other members, to avoid uninitialized variables. 280 m_net_p = 0; 281 m_net_n = 0;; 282 m_width = 0; 283 m_gap = 0; 284 m_viaGap = 0; 285 m_maxUncoupledLength = 0; 286 m_chamferLimit = 0; 287 } 288 289 DIFF_PAIR( const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN& aN, int aGap = 0 ) : LINK_HOLDER(ITEM::DIFF_PAIR_T)290 LINK_HOLDER( ITEM::DIFF_PAIR_T ), 291 m_n( aN ), 292 m_p( aP ), 293 m_hasVias( false ) 294 { 295 m_gapConstraint = aGap; 296 297 // Initialize other members, to avoid uninitialized variables. 298 m_net_p = 0; 299 m_net_n = 0;; 300 m_width = 0; 301 m_gap = 0; 302 m_viaGap = 0; 303 m_maxUncoupledLength = 0; 304 m_chamferLimit = 0; 305 } 306 307 DIFF_PAIR( const LINE &aLineP, const LINE &aLineN, int aGap = 0 ) : LINK_HOLDER(ITEM::DIFF_PAIR_T)308 LINK_HOLDER( ITEM::DIFF_PAIR_T ), 309 m_line_p( aLineP ), 310 m_line_n( aLineN ), 311 m_hasVias( false ) 312 { 313 m_gapConstraint = aGap; 314 m_net_p = aLineP.Net(); 315 m_net_n = aLineN.Net(); 316 m_p = aLineP.CLine(); 317 m_n = aLineN.CLine(); 318 319 // Do not leave uninitialized members, and keep static analyzer quiet: 320 m_width = 0; 321 m_gap = 0; 322 m_viaGap = 0; 323 m_maxUncoupledLength = 0; 324 m_chamferLimit = 0; 325 } 326 ClassOf(const ITEM * aItem)327 static inline bool ClassOf( const ITEM* aItem ) 328 { 329 return aItem && ITEM::DIFF_PAIR_T == aItem->Kind(); 330 } 331 Clone()332 DIFF_PAIR* Clone() const override 333 { 334 assert( false ); 335 return nullptr; 336 } 337 ClearLinks()338 virtual void ClearLinks() override 339 { 340 m_links.clear(); 341 m_line_p.ClearLinks(); 342 m_line_n.ClearLinks(); 343 } 344 345 static DIFF_PAIR* AssembleDp( LINE *aLine ); 346 347 void SetShape( const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN& aN, bool aSwapLanes = false ) 348 { 349 if( aSwapLanes ) 350 { 351 m_p = aN; 352 m_n = aP; 353 } 354 else 355 { 356 m_p = aP; 357 m_n = aN; 358 } 359 } 360 SetShape(const DIFF_PAIR & aPair)361 void SetShape( const DIFF_PAIR& aPair ) 362 { 363 m_p = aPair.m_p; 364 m_n = aPair.m_n; 365 } 366 SetNets(int aP,int aN)367 void SetNets( int aP, int aN ) 368 { 369 m_net_p = aP; 370 m_net_n = aN; 371 } 372 SetWidth(int aWidth)373 void SetWidth( int aWidth ) 374 { 375 m_width = aWidth; 376 m_n.SetWidth( aWidth ); 377 m_p.SetWidth( aWidth ); 378 } 379 Width()380 int Width() const { return m_width; } 381 SetGap(int aGap)382 void SetGap( int aGap ) 383 { 384 m_gap = aGap; 385 m_gapConstraint = RANGED_NUM<int>( m_gap, 10000, 10000 ); 386 } 387 Gap()388 int Gap() const 389 { 390 return m_gap; 391 } 392 AppendVias(const VIA & aViaP,const VIA & aViaN)393 void AppendVias( const VIA &aViaP, const VIA& aViaN ) 394 { 395 m_hasVias = true; 396 m_via_p = aViaP; 397 m_via_n = aViaN; 398 } 399 RemoveVias()400 void RemoveVias() 401 { 402 m_hasVias = false; 403 } 404 EndsWithVias()405 bool EndsWithVias() const 406 { 407 return m_hasVias; 408 } 409 SetViaDiameter(int aDiameter)410 void SetViaDiameter( int aDiameter ) 411 { 412 m_via_p.SetDiameter( aDiameter ); 413 m_via_n.SetDiameter( aDiameter ); 414 } 415 SetViaDrill(int aDrill)416 void SetViaDrill( int aDrill ) 417 { 418 m_via_p.SetDrill( aDrill ); 419 m_via_n.SetDrill( aDrill ); 420 } 421 NetP()422 int NetP() const 423 { 424 return m_net_p; 425 } 426 NetN()427 int NetN() const 428 { 429 return m_net_n; 430 } 431 PLine()432 LINE& PLine() 433 { 434 if( !m_line_p.IsLinked() ) 435 updateLine( m_line_p, m_p, m_net_p, m_via_p ); 436 437 return m_line_p; 438 } 439 NLine()440 LINE& NLine() 441 { 442 if( !m_line_n.IsLinked() ) 443 updateLine( m_line_n, m_n, m_net_n, m_via_n ); 444 445 return m_line_n; 446 } 447 448 DP_PRIMITIVE_PAIR EndingPrimitives(); 449 450 double CoupledLength() const; 451 double TotalLength() const; 452 double CoupledLengthFactor() const; 453 double Skew() const; 454 455 void CoupledSegmentPairs( COUPLED_SEGMENTS_VEC& aPairs ) const; 456 Clear()457 void Clear() 458 { 459 m_n.Clear(); 460 m_p.Clear(); 461 } 462 Append(const DIFF_PAIR & aOther)463 void Append( const DIFF_PAIR& aOther ) 464 { 465 m_n.Append( aOther.m_n ); 466 m_p.Append( aOther.m_p ); 467 } 468 Empty()469 bool Empty() const 470 { 471 return ( m_n.SegmentCount() == 0 ) || ( m_p.SegmentCount() == 0 ); 472 } 473 CP()474 const SHAPE_LINE_CHAIN& CP() const { return m_p; } CN()475 const SHAPE_LINE_CHAIN& CN() const { return m_n; } 476 477 bool BuildInitial( const DP_GATEWAY& aEntry, const DP_GATEWAY& aTarget, bool aPrefDiagonal ); 478 bool CheckConnectionAngle( const DIFF_PAIR &aOther, int allowedAngles ) const; 479 int CoupledLength( const SEG& aP, const SEG& aN ) const; 480 481 int64_t CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const; 482 GapConstraint()483 const RANGED_NUM<int> GapConstraint() const 484 { 485 return m_gapConstraint; 486 } 487 488 private: updateLine(LINE & aLine,const SHAPE_LINE_CHAIN & aShape,int aNet,const VIA & aVia)489 void updateLine( LINE &aLine, const SHAPE_LINE_CHAIN& aShape, int aNet, const VIA& aVia ) 490 { 491 aLine.SetShape( aShape ); 492 aLine.SetWidth( m_width ); 493 aLine.SetNet( aNet ); 494 aLine.SetLayer( Layers().Start() ); 495 496 if( m_hasVias ) 497 aLine.AppendVia( aVia ); 498 } 499 500 SHAPE_LINE_CHAIN m_n, m_p; 501 LINE m_line_p, m_line_n; 502 VIA m_via_p, m_via_n; 503 504 bool m_hasVias; 505 int m_net_p, m_net_n; 506 int m_width; 507 int m_gap; 508 int m_viaGap; 509 int m_maxUncoupledLength; 510 int m_chamferLimit; 511 RANGED_NUM<int> m_gapConstraint; 512 }; 513 514 } 515 516 #endif 517