Reimplementation of prefix sets.

Prefix sets were broken beyond any repair and have to be reimplemented.
They are reimplemented using a trie with bitmasks in nodes.
There is also change in the interpretation of minus prefix pattern,
but the old interpretation was already inconsistent with
the documentation and broken.

There is also some bugfixes in filter code related to set variables.

4 files changed, 53 insertions, 0 deletions

diff --git a/lib/bitops.c b/lib/bitops.c
index 6ca0505..88cef78 100644
--- a/lib/bitops.c
+++ b/lib/bitops.c
@@ -45,3 +45,24 @@ u32_masklen(u32 x)
   if (x & 0xaaaaaaaa) l++;
   return l;
 }
+
+/**
+ * u32_log2 - compute a binary logarithm.
+ * @v: number
+ *
+ * This function computes a integral part of binary logarithm of given
+ * integer @v and returns it. The computed value is also an index of the
+ * first non-zero bit position.
+ */
+
+u32
+u32_log2(u32 v)
+{
+  u32 r, shift;
+  r =     (v > 0xFFFF) << 4; v >>= r;
+  shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
+  shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
+  shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
+  r |= (v >> 1);
+  return r;
+}
diff --git a/lib/bitops.h b/lib/bitops.h
index 1b6dc68..bebd830 100644
--- a/lib/bitops.h
+++ b/lib/bitops.h
@@ -17,3 +17,5 @@
 
 u32 u32_mkmask(unsigned n);
 int u32_masklen(u32 x);
+
+u32 u32_log2(u32 v);
diff --git a/lib/ipv4.h b/lib/ipv4.h
index 4c4fab9..b64d9b2 100644
--- a/lib/ipv4.h
+++ b/lib/ipv4.h
@@ -35,6 +35,7 @@ typedef u32 ip_addr;
 
 #endif
 
+#define MAX_PREFIX_LENGTH 32
 #define BITS_PER_IP_ADDRESS 32
 #define STD_ADDRESS_P_LENGTH 15
 #define SIZE_OF_IP_HEADER 24
@@ -58,6 +59,9 @@ typedef u32 ip_addr;
 #define ipa_from_u32(x) _MI(x)
 #define ipa_to_u32(x) _I(x)
 #define ipa_compare(x,y) ipv4_compare(_I(x),_I(y))
+/* ipa_pxlen() requires that x != y */
+#define ipa_pxlen(x, y) ipv4_pxlen(_I(x), _I(y))
+#define ipa_getbit(x, y) (_I(x) & (0x80000000 >> (y)))
 
 #define ip_skip_header(x, y) ipv4_skip_header(x, y)
 
@@ -78,6 +82,12 @@ static inline int ipv4_compare(u32 x, u32 y)
   return (x > y) - (x < y);
 }
 
+static inline u32 ipv4_pxlen(u32 a, u32 b)
+{
+  return 31 - u32_log2(a ^ b);
+}
+
+
 #define IP_PREC_INTERNET_CONTROL 0xc0
 
 #endif
diff --git a/lib/ipv6.h b/lib/ipv6.h
index 191c1c7..9193c4f 100644
--- a/lib/ipv6.h
+++ b/lib/ipv6.h
@@ -12,6 +12,7 @@
 #include <sys/types.h>
 #include <netinet/in.h>
 #include "lib/string.h"
+#include "lib/bitops.h"
 
 typedef struct ipv6_addr {
   u32 addr[4];
@@ -23,6 +24,7 @@ typedef struct ipv6_addr {
 #define _I2(a) ((a).addr[2])
 #define _I3(a) ((a).addr[3])
 
+#define MAX_PREFIX_LENGTH 128
 #define BITS_PER_IP_ADDRESS 128
 #define STD_ADDRESS_P_LENGTH 39
 #define SIZE_OF_IP_HEADER 40
@@ -57,6 +59,9 @@ typedef struct ipv6_addr {
 /* ipa_from_u32 and ipa_to_u32 replaced by ipa_build */
 #define ipa_build(a,b,c,d) _MI(a,b,c,d)
 #define ipa_compare(x,y) ipv6_compare(x,y)
+/* ipa_pxlen() requires that x != y */
+#define ipa_pxlen(x, y) ipv6_pxlen(x, y)
+#define ipa_getbit(x, y) ipv6_getbit(x, y)
 #define ipa_absolutize(x,y) ipv6_absolutize(x,y)
 
 ip_addr ipv6_mkmask(unsigned);
@@ -81,6 +86,21 @@ static inline unsigned ipv6_hash(ip_addr *a)
   return (x ^ (x >> 16) ^ (x >> 8)) & 0xffff;
 }
 
+static inline u32 ipv6_getbit(ip_addr a, u32 y)
+{
+  return a.addr[y / 32] & (0x80000000 >> (y % 32));
+}
+
+static inline u32 ipv6_pxlen(ip_addr a, ip_addr b)
+{
+  int i = 0;
+  i+= (a.addr[i] == b.addr[i]);
+  i+= (a.addr[i] == b.addr[i]);
+  i+= (a.addr[i] == b.addr[i]);
+  i+= (a.addr[i] == b.addr[i]);
+  return 32 * i + 31 - u32_log2(a.addr[i] ^ b.addr[i]);
+}
+
 /*
  *  RFC 1883 defines packet precendece, but RFC 2460 replaces it
  *  by generic Traffic Class ID with no defined semantics. Better