Added main execs

1 files changed, 550 insertions, 0 deletions

diff --git a/pcbnew/autorouter/routing_matrix.cpp b/pcbnew/autorouter/routing_matrix.cpp
new file mode 100644
index 0000000..2c97f0d
--- /dev/null
+++ b/pcbnew/autorouter/routing_matrix.cpp
@@ -0,0 +1,550 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+/**
+ * @file routing_matrix.cpp
+ * @brief Functions to create autorouting maps
+ */
+
+#include <fctsys.h>
+#include <common.h>
+
+#include <pcbnew.h>
+#include <cell.h>
+#include <autorout.h>
+
+#include <class_board.h>
+#include <class_module.h>
+#include <class_track.h>
+#include <class_drawsegment.h>
+#include <class_edge_mod.h>
+#include <class_pcb_text.h>
+
+
+MATRIX_ROUTING_HEAD::MATRIX_ROUTING_HEAD()
+{
+    m_BoardSide[0] = m_BoardSide[1] = NULL;
+    m_DistSide[0] = m_DistSide[1] = NULL;
+    m_DirSide[0] = m_DirSide[1] = NULL;
+    m_opWriteCell        = NULL;
+    m_InitMatrixDone     = false;
+    m_Nrows              = 0;
+    m_Ncols              = 0;
+    m_MemSize            = 0;
+    m_RoutingLayersCount = 1;
+    m_GridRouting        = 0;
+    m_RouteCount         = 0;
+}
+
+
+MATRIX_ROUTING_HEAD::~MATRIX_ROUTING_HEAD()
+{
+}
+
+
+bool MATRIX_ROUTING_HEAD::ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly )
+{
+    aPcb->ComputeBoundingBox( aUseBoardEdgesOnly );
+
+    // The boundary box must have its start point on routing grid:
+    m_BrdBox = aPcb->GetBoundingBox();
+
+    m_BrdBox.SetX( m_BrdBox.GetX() - ( m_BrdBox.GetX() % m_GridRouting ) );
+    m_BrdBox.SetY( m_BrdBox.GetY() - ( m_BrdBox.GetY() % m_GridRouting ) );
+
+    // The boundary box must have its end point on routing grid:
+    wxPoint end = m_BrdBox.GetEnd();
+
+    end.x -= end.x % m_GridRouting;
+    end.x += m_GridRouting;
+
+    end.y -= end.y % m_GridRouting;
+    end.y += m_GridRouting;
+
+    m_BrdBox.SetEnd( end );
+
+    aPcb->SetBoundingBox( m_BrdBox );
+
+    m_Nrows = m_BrdBox.GetHeight() / m_GridRouting;
+    m_Ncols = m_BrdBox.GetWidth() / m_GridRouting;
+
+    // gives a small margin
+    m_Ncols += 1;
+    m_Nrows += 1;
+
+    return true;
+}
+
+
+int MATRIX_ROUTING_HEAD::InitRoutingMatrix()
+{
+    if( m_Nrows <= 0 || m_Ncols <= 0 )
+        return 0;
+
+    m_InitMatrixDone = true;     // we have been called
+
+    // give a small margin for memory allocation:
+    int ii = (RoutingMatrix.m_Nrows + 1) * (RoutingMatrix.m_Ncols + 1);
+
+    int side = BOTTOM;
+    for( int jj = 0; jj < m_RoutingLayersCount; jj++ )  // m_RoutingLayersCount = 1 or 2
+    {
+        m_BoardSide[side] = NULL;
+        m_DistSide[side]  = NULL;
+        m_DirSide[side]   = NULL;
+
+        // allocate matrix & initialize everything to empty
+        m_BoardSide[side] = (MATRIX_CELL*) operator new( ii * sizeof(MATRIX_CELL) );
+        memset( m_BoardSide[side], 0, ii * sizeof(MATRIX_CELL) );
+
+        if( m_BoardSide[side] == NULL )
+            return -1;
+
+        // allocate Distances
+        m_DistSide[side] = (DIST_CELL*) operator new( ii * sizeof(DIST_CELL) );
+        memset( m_DistSide[side], 0, ii * sizeof(DIST_CELL) );
+
+        if( m_DistSide[side] == NULL )
+            return -1;
+
+        // allocate Dir (chars)
+        m_DirSide[side] = (char*) operator new( ii );
+        memset( m_DirSide[side], 0, ii );
+
+        if( m_DirSide[side] == NULL )
+            return -1;
+
+        side = TOP;
+    }
+
+    m_MemSize = m_RouteCount * ii * ( sizeof(MATRIX_CELL)
+                + sizeof(DIST_CELL) + sizeof(char) );
+
+    return m_MemSize;
+}
+
+
+void MATRIX_ROUTING_HEAD::UnInitRoutingMatrix()
+{
+    int ii;
+
+    m_InitMatrixDone = false;
+
+    for( ii = 0; ii < MAX_ROUTING_LAYERS_COUNT; ii++ )
+    {
+        // de-allocate Dir matrix
+        if( m_DirSide[ii] )
+        {
+            delete m_DirSide[ii];
+            m_DirSide[ii] = NULL;
+        }
+
+        // de-allocate Distances matrix
+        if( m_DistSide[ii] )
+        {
+            delete m_DistSide[ii];
+            m_DistSide[ii] = NULL;
+        }
+
+        // de-allocate cells matrix
+        if( m_BoardSide[ii] )
+        {
+            delete m_BoardSide[ii];
+            m_BoardSide[ii] = NULL;
+        }
+    }
+
+    m_Nrows = m_Ncols = 0;
+}
+
+
+/**
+ * Function PlaceCells
+ * Initialize the matrix routing by setting obstacles for each occupied cell
+ * a cell set to HOLE is an obstacle for tracks and vias
+ * a cell set to VIA_IMPOSSIBLE is an obstacle for vias only.
+ * a cell set to CELL_is_EDGE is a frontier.
+ * Tracks and vias having the same net code as net_code are skipped
+ * (htey do not are obstacles)
+ *
+ * For single-sided Routing 1:
+ * BOTTOM side is used, and Route_Layer_BOTTOM = Route_Layer_TOP
+ *
+ * If flag == FORCE_PADS: all pads will be put in matrix as obstacles.
+ */
+void PlaceCells( BOARD* aPcb, int net_code, int flag )
+{
+    int     ux0 = 0, uy0 = 0, ux1, uy1, dx, dy;
+    int     marge, via_marge;
+    LSET    layerMask;
+
+    // use the default NETCLASS?
+    NETCLASSPTR nc = aPcb->GetDesignSettings().GetDefault();
+
+    int     trackWidth = nc->GetTrackWidth();
+    int     clearance  = nc->GetClearance();
+    int     viaSize    = nc->GetViaDiameter();
+
+    marge     = clearance + (trackWidth / 2);
+    via_marge = clearance + (viaSize / 2);
+
+    // Place PADS on matrix routing:
+    for( unsigned i = 0; i < aPcb->GetPadCount(); ++i )
+    {
+        D_PAD* pad = aPcb->GetPad( i );
+
+        if( net_code != pad->GetNetCode() || (flag & FORCE_PADS) )
+        {
+            ::PlacePad( pad, HOLE, marge, WRITE_CELL );
+        }
+
+        ::PlacePad( pad, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+    }
+
+    // Place outlines of modules on matrix routing, if they are on a copper layer
+    // or on the edge layer
+
+    for( MODULE* module = aPcb->m_Modules; module; module = module->Next() )
+    {
+        for( BOARD_ITEM* item = module->GraphicalItems(); item; item = item->Next() )
+        {
+            switch( item->Type() )
+            {
+            case PCB_MODULE_EDGE_T:
+            {
+                EDGE_MODULE* edge = (EDGE_MODULE*) item;
+                EDGE_MODULE tmpEdge( *edge );
+
+                if( tmpEdge.GetLayer() == Edge_Cuts )
+                    tmpEdge.SetLayer( UNDEFINED_LAYER );
+
+                TraceSegmentPcb( &tmpEdge, HOLE, marge, WRITE_CELL );
+                TraceSegmentPcb( &tmpEdge, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+            }
+            break;
+
+            default:
+                break;
+            }
+        }
+    }
+
+    // Place board outlines and texts on copper layers:
+    for( BOARD_ITEM* item = aPcb->m_Drawings; item; item = item->Next() )
+    {
+        switch( item->Type() )
+        {
+        case PCB_LINE_T:
+            {
+                DRAWSEGMENT* DrawSegm;
+
+                int          type_cell = HOLE;
+                DrawSegm = (DRAWSEGMENT*) item;
+                DRAWSEGMENT tmpSegm( DrawSegm );
+
+                if( DrawSegm->GetLayer() == Edge_Cuts )
+                {
+                    tmpSegm.SetLayer( UNDEFINED_LAYER );
+                    type_cell |= CELL_is_EDGE;
+                }
+
+                TraceSegmentPcb( &tmpSegm, type_cell, marge, WRITE_CELL );
+            }
+            break;
+
+        case PCB_TEXT_T:
+            {
+                TEXTE_PCB* PtText = (TEXTE_PCB*) item;
+
+                if( PtText->GetText().Length() == 0 )
+                    break;
+
+                EDA_RECT textbox = PtText->GetTextBox( -1 );
+                ux0 = textbox.GetX();
+                uy0 = textbox.GetY();
+                dx  = textbox.GetWidth();
+                dy  = textbox.GetHeight();
+
+                // Put bounding box (rectangle) on matrix
+                dx /= 2;
+                dy /= 2;
+
+                ux1 = ux0 + dx;
+                uy1 = uy0 + dy;
+
+                ux0 -= dx;
+                uy0 -= dy;
+
+                layerMask = LSET( PtText->GetLayer() );
+
+                TraceFilledRectangle( ux0 - marge, uy0 - marge, ux1 + marge,
+                                      uy1 + marge, PtText->GetOrientation(),
+                                      layerMask, HOLE, WRITE_CELL );
+
+                TraceFilledRectangle( ux0 - via_marge, uy0 - via_marge,
+                                      ux1 + via_marge, uy1 + via_marge,
+                                      PtText->GetOrientation(),
+                                      layerMask, VIA_IMPOSSIBLE, WRITE_OR_CELL );
+            }
+            break;
+
+        default:
+            break;
+        }
+    }
+
+    // Put tracks and vias on matrix
+    for( TRACK* track = aPcb->m_Track; track; track = track->Next() )
+    {
+        if( net_code == track->GetNetCode() )
+            continue;
+
+        TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
+        TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
+    }
+}
+
+
+int Build_Work( BOARD* Pcb )
+{
+    RATSNEST_ITEM*  pt_rats;
+    D_PAD*          pt_pad;
+    int             r1, r2, c1, c2, current_net_code;
+    RATSNEST_ITEM*  pt_ch;
+    int             demi_pas = RoutingMatrix.m_GridRouting / 2;
+    wxString        msg;
+
+    InitWork(); // clear work list
+    int cellCount = 0;
+
+    for( unsigned ii = 0; ii < Pcb->GetRatsnestsCount(); ii++ )
+    {
+        pt_rats = &Pcb->m_FullRatsnest[ii];
+
+        /* We consider here only ratsnest that are active ( obviously not yet routed)
+         * and routables (that are not yet attempt to be routed and fail
+         */
+        if( (pt_rats->m_Status & CH_ACTIF) == 0 )
+            continue;
+
+        if( pt_rats->m_Status & CH_UNROUTABLE )
+            continue;
+
+        if( (pt_rats->m_Status & CH_ROUTE_REQ) == 0 )
+            continue;
+
+        pt_pad = pt_rats->m_PadStart;
+
+        current_net_code = pt_pad->GetNetCode();
+        pt_ch = pt_rats;
+
+        r1 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY() + demi_pas )
+            / RoutingMatrix.m_GridRouting;
+
+        if( r1 < 0 || r1 >= RoutingMatrix.m_Nrows )
+        {
+            msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r1,
+                        pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        c1 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas ) / RoutingMatrix.m_GridRouting;
+
+        if( c1 < 0 || c1 >= RoutingMatrix.m_Ncols )
+        {
+            msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c1,
+                        pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        pt_pad = pt_rats->m_PadEnd;
+
+        r2 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY()
+               + demi_pas ) / RoutingMatrix.m_GridRouting;
+
+        if( r2 < 0 || r2 >= RoutingMatrix.m_Nrows )
+        {
+            msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r2,
+                        pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        c2 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas )
+             / RoutingMatrix.m_GridRouting;
+
+        if( c2 < 0 || c2 >= RoutingMatrix.m_Ncols )
+        {
+            msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c2,
+                        pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() );
+            wxMessageBox( msg );
+            return 0;
+        }
+
+        SetWork( r1, c1, current_net_code, r2, c2, pt_ch, 0 );
+        cellCount++;
+    }
+
+    SortWork();
+    return cellCount;
+}
+
+// Initialize m_opWriteCell member to make the aLogicOp
+void MATRIX_ROUTING_HEAD::SetCellOperation( int aLogicOp )
+{
+    switch( aLogicOp )
+    {
+    default:
+    case WRITE_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::SetCell;
+        break;
+
+    case WRITE_OR_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::OrCell;
+        break;
+
+    case WRITE_XOR_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::XorCell;
+        break;
+
+    case WRITE_AND_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::AndCell;
+        break;
+
+    case WRITE_ADD_CELL:
+        m_opWriteCell = &MATRIX_ROUTING_HEAD::AddCell;
+        break;
+    }
+}
+
+
+/* return the value stored in a cell
+ */
+MATRIX_CELL MATRIX_ROUTING_HEAD::GetCell( int aRow, int aCol, int aSide )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    return p[aRow * m_Ncols + aCol];
+}
+
+
+/* basic cell operation : WRITE operation
+ */
+void MATRIX_ROUTING_HEAD::SetCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] = x;
+}
+
+
+/* basic cell operation : OR operation
+ */
+void MATRIX_ROUTING_HEAD::OrCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] |= x;
+}
+
+
+/* basic cell operation : XOR operation
+ */
+void MATRIX_ROUTING_HEAD::XorCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] ^= x;
+}
+
+
+/* basic cell operation : AND operation
+ */
+void MATRIX_ROUTING_HEAD::AndCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] &= x;
+}
+
+
+/* basic cell operation : ADD operation
+ */
+void MATRIX_ROUTING_HEAD::AddCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
+{
+    MATRIX_CELL* p;
+
+    p = RoutingMatrix.m_BoardSide[aSide];
+    p[aRow * m_Ncols + aCol] += x;
+}
+
+
+// fetch distance cell
+DIST_CELL MATRIX_ROUTING_HEAD::GetDist( int aRow, int aCol, int aSide ) // fetch distance cell
+{
+    DIST_CELL* p;
+
+    p = RoutingMatrix.m_DistSide[aSide];
+    return p[aRow * m_Ncols + aCol];
+}
+
+
+// store distance cell
+void MATRIX_ROUTING_HEAD::SetDist( int aRow, int aCol, int aSide, DIST_CELL x )
+{
+    DIST_CELL* p;
+
+    p = RoutingMatrix.m_DistSide[aSide];
+    p[aRow * m_Ncols + aCol] = x;
+}
+
+
+// fetch direction cell
+int MATRIX_ROUTING_HEAD::GetDir( int aRow, int aCol, int aSide )
+{
+    DIR_CELL* p;
+
+    p = RoutingMatrix.m_DirSide[aSide];
+    return (int) (p[aRow * m_Ncols + aCol]);
+}
+
+
+// store direction cell
+void MATRIX_ROUTING_HEAD::SetDir( int aRow, int aCol, int aSide, int x )
+{
+    DIR_CELL* p;
+
+    p = RoutingMatrix.m_DirSide[aSide];
+    p[aRow * m_Ncols + aCol] = (char) x;
+}