Filter: Faster prefix sets

Use 16-way (4bit) branching in prefix trie instead of basic binary
branching. The change makes IPv4 prefix sets almost 3x faster, but
with more memory consumption and much more complicated algorithm.

Together with a previous filter change, it makes IPv4 prefix sets
about ~4.3x faster and slightly smaller (on my test data).

2 files changed, 18 insertions, 2 deletions

diff --git a/lib/birdlib.h b/lib/birdlib.h
index 431b7c0d..81d4908a 100644
--- a/lib/birdlib.h
+++ b/lib/birdlib.h
@@ -32,6 +32,9 @@ struct align_probe { char x; long int y; };
 #define MAX(a,b) MAX_(a,b)
 #endif
 
+#define ROUND_DOWN_POW2(a,b)  ((a) & ~((b)-1))
+#define ROUND_UP_POW2(a,b)  (((a)+((b)-1)) & ~((b)-1))
+
 #define U64(c) UINT64_C(c)
 #define ABS(a)   ((a)>=0 ? (a) : -(a))
 #define DELTA(a,b) (((a)>=(b))?(a)-(b):(b)-(a))
diff --git a/lib/ip.h b/lib/ip.h
index 5b179acb..cc36ce64 100644
--- a/lib/ip.h
+++ b/lib/ip.h
@@ -280,10 +280,16 @@ static inline uint ip6_pxlen(ip6_addr a, ip6_addr b)
 }
 
 static inline u32 ip4_getbit(ip4_addr a, uint pos)
-{ return _I(a) & (0x80000000 >> pos); }
+{ return (_I(a) >> (31 - pos)) & 1; }
+
+static inline u32 ip4_getbits(ip4_addr a, uint pos, uint n)
+{ return (_I(a) >> ((32 - n) - pos)) & ((1u << n) - 1); }
 
 static inline u32 ip6_getbit(ip6_addr a, uint pos)
-{ return a.addr[pos / 32] & (0x80000000 >> (pos % 32)); }
+{ return (a.addr[pos / 32] >> (31 - (pos % 32))) & 0x1; }
+
+static inline u32 ip6_getbits(ip6_addr a, uint pos, uint n)
+{ return (a.addr[pos / 32] >> ((32 - n) - (pos % 32))) & ((1u << n) - 1); }
 
 static inline u32 ip4_setbit(ip4_addr *a, uint pos)
 { return _I(*a) |= (0x80000000 >> pos); }
@@ -297,6 +303,13 @@ static inline u32 ip4_clrbit(ip4_addr *a, uint pos)
 static inline u32 ip6_clrbit(ip6_addr *a, uint pos)
 { return a->addr[pos / 32] &= ~(0x80000000 >> (pos % 32)); }
 
+static inline ip4_addr ip4_setbits(ip4_addr a, uint pos, uint val)
+{ _I(a) |= val << (31 - pos); return a; }
+
+static inline ip6_addr ip6_setbits(ip6_addr a, uint pos, uint val)
+{ a.addr[pos / 32] |= val << (31 - pos % 32); return a; }
+
+
 static inline ip4_addr ip4_opposite_m1(ip4_addr a)
 { return _MI4(_I(a) ^ 1); }