Add binary search to getBelPinWire() and getBelPinType()

Signed-off-by: Clifford Wolf <clifford@clifford.at>

3 files changed, 43 insertions, 16 deletions

diff --git a/ice40/arch.cc b/ice40/arch.cc
index 8162098c..fd68e972 100644
--- a/ice40/arch.cc
+++ b/ice40/arch.cc
@@ -311,9 +311,23 @@ PortType Arch::getBelPinType(BelId bel, PortPin pin) const
     int num_bel_wires = chip_info->bel_data[bel.index].num_bel_wires;
     const BelWirePOD *bel_wires = chip_info->bel_data[bel.index].bel_wires.get();
 
-    for (int i = 0; i < num_bel_wires; i++)
-        if (bel_wires[i].port == pin)
-            return PortType(bel_wires[i].type);
+    if (num_bel_wires < 7) {
+        for (int i = 0; i < num_bel_wires; i++) {
+            if (bel_wires[i].port == pin)
+                return PortType(bel_wires[i].type);
+        }
+    } else {
+        int b = 0, e = num_bel_wires-1;
+        while (b <= e) {
+            int i = (b+e) / 2;
+            if (bel_wires[i].port == pin)
+                return PortType(bel_wires[i].type);
+            if (bel_wires[i].port > pin)
+                e = i-1;
+            else
+                b = i+1;
+        }
+    }
 
     return PORT_INOUT;
 }
@@ -327,10 +341,25 @@ WireId Arch::getBelPinWire(BelId bel, PortPin pin) const
     int num_bel_wires = chip_info->bel_data[bel.index].num_bel_wires;
     const BelWirePOD *bel_wires = chip_info->bel_data[bel.index].bel_wires.get();
 
-    for (int i = 0; i < num_bel_wires; i++) {
-        if (bel_wires[i].port == pin) {
-            ret.index = bel_wires[i].wire_index;
-            break;
+    if (num_bel_wires < 7) {
+        for (int i = 0; i < num_bel_wires; i++) {
+            if (bel_wires[i].port == pin) {
+                ret.index = bel_wires[i].wire_index;
+                break;
+            }
+        }
+    } else {
+        int b = 0, e = num_bel_wires-1;
+        while (b <= e) {
+            int i = (b+e) / 2;
+            if (bel_wires[i].port == pin) {
+                ret.index = bel_wires[i].wire_index;
+                break;
+            }
+            if (bel_wires[i].port > pin)
+                e = i-1;
+            else
+                b = i+1;
         }
     }
 
diff --git a/ice40/arch.h b/ice40/arch.h
index 8c6a3d93..1d68ec4a 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -44,9 +44,9 @@ template <typename T> struct RelPtr
 };
 
 NPNR_PACKED_STRUCT(struct BelWirePOD {
-    int32_t wire_index;
     PortPin port;
     int32_t type;
+    int32_t wire_index;
 });
 
 NPNR_PACKED_STRUCT(struct BelInfoPOD {
diff --git a/ice40/chipdb.py b/ice40/chipdb.py
index 3ef58185..32d3485f 100644
--- a/ice40/chipdb.py
+++ b/ice40/chipdb.py
@@ -492,13 +492,13 @@ def add_bel_input(bel, wire, port):
     if wire not in wire_belports:
         wire_belports[wire] = set()
     wire_belports[wire].add((bel, port))
-    bel_wires[bel].append((wire, port, 0))
+    bel_wires[bel].append((portpins[port], 0, wire))
 
 def add_bel_output(bel, wire, port):
     if wire not in wire_belports:
         wire_belports[wire] = set()
     wire_belports[wire].add((bel, port))
-    bel_wires[bel].append((wire, port, 1))
+    bel_wires[bel].append((portpins[port], 1, wire))
 
 def add_bel_lc(x, y, z):
     bel = len(bel_name)
@@ -759,14 +759,12 @@ bba.post('NEXTPNR_NAMESPACE_END')
 bba.push("chipdb_blob_%s" % dev_name)
 bba.r("chip_info_%s" % dev_name, "chip_info")
 
-index = 0
 for bel in range(len(bel_name)):
     bba.l("bel_wires_%d" % bel, "BelWirePOD")
-    for i in range(len(bel_wires[bel])):
-        bba.u32(bel_wires[bel][i][0], "wire_index")
-        bba.u32(portpins[bel_wires[bel][i][1]], "port")
-        bba.u32(bel_wires[bel][i][2], "type")
-        index += 1
+    for data in sorted(bel_wires[bel]):
+        bba.u32(data[0], "port")
+        bba.u32(data[1], "type")
+        bba.u32(data[2], "wire_index")
 
 bba.l("bel_data_%s" % dev_name, "BelInfoPOD")
 for bel in range(len(bel_name)):