Basic support for IPv6. The system-dependent part doesn't work yet,

but the core routines are there and seem to be working.

   o  lib/ipv6.[ch] written
   o  Lexical analyser recognizes IPv6 addresses and when in IPv6
      mode, treats pure IPv4 addresses as router IDs.
   o  Router ID must be configured manually on IPv6 systems.
   o  Added SCOPE_ORGANIZATION for org-scoped IPv6 multicasts.
   o  Fixed few places where ipa_(hton|ntoh) was called as a function
      returning converted address.

4 files changed, 379 insertions, 21 deletions

diff --git a/lib/Modules b/lib/Modules
index 1597b9af..cf654127 100644
--- a/lib/Modules
+++ b/lib/Modules
@@ -2,7 +2,7 @@ birdlib.h
 bitops.c
 bitops.h
 ip.h
-#ifdef CONFIG_IPV6
+#ifdef IPV6
 ipv6.c
 ipv6.h
 #else
diff --git a/lib/ip.h b/lib/ip.h
index 1bce89f8..9b247d57 100644
--- a/lib/ip.h
+++ b/lib/ip.h
@@ -35,7 +35,8 @@
 #define SCOPE_HOST 0
 #define SCOPE_LINK 1
 #define SCOPE_SITE 2
-#define SCOPE_UNIVERSE 3
+#define SCOPE_ORGANIZATION 3
+#define SCOPE_UNIVERSE 4
 
 /*
  *	Is it a valid network prefix?
diff --git a/lib/ipv6.c b/lib/ipv6.c
index e612af72..c1b07637 100644
--- a/lib/ipv6.c
+++ b/lib/ipv6.c
@@ -1,12 +1,357 @@
 /*
  *	BIRD Library -- IPv6 Address Manipulation Functions
  *
- *	(c) 1998 Martin Mares <mj@ucw.cz>
+ *	(c) 1999 Martin Mares <mj@ucw.cz>
  *
  *	Can be freely distributed and used under the terms of the GNU GPL.
+ *
  */
 
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
 #include "nest/bird.h"
 #include "lib/ip.h"
+#include "lib/bitops.h"
+#include "lib/endian.h"
+
+/*
+ *  See RFC 2373 for explanation of IPv6 addressing issues.
+ */
+
+ip_addr
+ipv6_mkmask(unsigned n)
+{
+  ip_addr a;
+  int i;
+
+  for(i=0; i<4; i++)
+    {
+      if (!n)
+	a.addr[i] = 0;
+      else if (n >= 32)
+	{
+	  a.addr[i] = ~0;
+	  n -= 32;
+	}
+      else
+	{
+	  a.addr[i] = u32_mkmask(n);
+	  n = 0;
+	}
+    }
+  return a;
+}
+
+unsigned
+ipv6_mklen(ip_addr *a)
+{
+  int i, j, n;
+
+  for(i=0, n=0; i<4; i++, n+=32)
+    if (a->addr[i] != ~0U)
+      {
+	j = u32_masklen(a->addr[i]);
+	if (j < 0)
+	  return j;
+	n += j;
+	while (++i < 4)
+	  if (a->addr[i])
+	    return -1;
+	break;
+      }
+  return n;
+}
+
+int
+ipv6_classify(ip_addr *a)
+{
+  u32 x = a->addr[0];
+
+  /* FIXME: Relax these requirements? */
+  if ((x & 0xe0000000) == 0x20000000)		/* Aggregatable Global Unicast Address */
+    return IADDR_HOST | SCOPE_UNIVERSE;
+  if ((x & 0xfc000000) == 0xe8000000)		/* Link-Local Address */
+    return IADDR_HOST | SCOPE_LINK;
+  if ((x & 0xfc000000) == 0xec000000)		/* Site-Local Address */
+    return IADDR_HOST | SCOPE_SITE;
+  if ((x & 0xff000000) == 0xff000000)		/* Multicast Address */
+    {
+      unsigned int scope = (x >> 16) & 0x0f;
+      switch (scope)
+	{
+	case 1:	 return IADDR_MULTICAST | SCOPE_HOST;
+	case 2:  return IADDR_MULTICAST | SCOPE_LINK;
+	case 5:  return IADDR_MULTICAST | SCOPE_SITE;
+	case 8:  return IADDR_MULTICAST | SCOPE_ORGANIZATION;
+	case 14: return IADDR_MULTICAST | SCOPE_UNIVERSE;
+	}
+    }
+  return IADDR_INVALID;
+}
+
+void
+ipv6_hton(ip_addr *a)
+{
+  int i;
+
+  for(i=0; i<4; i++)
+    a->addr[i] = htonl(a->addr[i]);
+}
+
+void
+ipv6_ntoh(ip_addr *a)
+{
+  int i;
+
+  for(i=0; i<4; i++)
+    a->addr[i] = ntohl(a->addr[i]);
+}
+
+int
+ipv6_compare(ip_addr *x, ip_addr *y)
+{
+  int i;
+
+  for(i=0; i<4; i++)
+    if (x->addr[i] > y->addr[i])
+      return 1;
+    else if (x->addr[i] < y->addr[i])
+      return -1;
+  return 0;
+}
+
+/*
+ *  Conversion of IPv6 address to presentation format and vice versa.
+ *  Heavily inspired by routines written by Paul Vixie for the BIND project
+ *  and of course by RFC 2373.
+ */
+
+char *
+ip_ntop(ip_addr a, char *b)
+{
+  u16 words[8];
+  int bestpos, bestlen, curpos, curlen, i;
+  char *c;
+
+  /* First of all, preprocess the address and find the longest run of zeros */
+  bestlen = bestpos = curpos = curlen = 0;
+  for(i=0; i<8; i++)
+    {
+      u32 x = a.addr[i/2];
+      words[i] = ((i%2) ? x : (x >> 16)) & 0xffff;
+      if (words[i])
+	curlen = 0;
+      else
+	{
+	  if (!curlen)
+	    curpos = i;
+	  curlen++;
+	  if (curlen > bestlen)
+	    {
+	      bestpos = curpos;
+	      bestlen = curlen;
+	    }
+	}
+    }
+  if (bestlen < 2)
+    bestpos = -1;
+
+  /* Is it an encapsulated IPv4 address? */
+  if (!bestpos &&
+      (bestlen == 5 && a.addr[2] == 0xffff ||
+       bestlen == 6))
+    {
+      u32 x = a.addr[3];
+      b += sprintf(b, "::%s%d.%d.%d.%d",
+		   a.addr[2] ? "ffff:" : "",
+		   ((x >> 24) & 0xff),
+		   ((x >> 16) & 0xff),
+		   ((x >> 8) & 0xff),
+		   (x & 0xff));
+      return b;
+    }
+
+  /* Normal IPv6 formatting, compress the largest sequence of zeros */
+  for(i=0; i<8; i++)
+    {
+      if (i == bestpos)
+	{
+	  i += bestlen - 1;
+	  *b++ = ':';
+	  if (i == 7)
+	    *b++ = ':';
+	}
+      else
+	{
+	  if (i)
+	    *b++ = ':';
+	  b += sprintf(b, "%x", words[i]);
+	}
+    }
+  *b = 0;
+  return b;
+}
+
+char *
+ip_ntox(ip_addr a, char *b)
+{
+  int i;
+
+  for(i=0; i<4; i++)
+    {
+      if (i)
+	*b++ = '.';
+      b += sprintf(b, "%08x", a.addr[i]);
+    }
+  return b;
+}
+
+int
+ipv4_pton_u32(char *a, u32 *o)
+{
+  int i,j;
+  unsigned long int l;
+  u32 ia = 0;
+
+  i=4;
+  while (i--)
+    {
+      char *d, *c = strchr(a, '.');
+      if (!c != !i)
+	return 0;
+      l = strtoul(a, &d, 10);
+      if (d != c && *d || l > 255)
+	return 0;
+      ia = (ia << 8) | l;
+      if (c)
+	c++;
+      a = c;
+    }
+  *o = ia;
+  return 1;
+}
+
+int
+ip_pton(char *a, ip_addr *o)
+{
+  u16 words[8];
+  int i, j, k, l, hfil;
+  char *start;
+
+  if (a[0] == ':')			/* Leading :: */
+    {
+      if (a[1] != ':')
+	return 0;
+      a++;
+    }
+  hfil = -1;
+  i = 0;
+  while (*a)
+    {
+      if (*a == ':')			/* :: */
+	{
+	  if (hfil >= 0)
+	    return 0;
+	  hfil = i;
+	  a++;
+	  continue;
+	}
+      j = 0;
+      l = 0;
+      start = a;
+      for(;;)
+	{
+	  if (*a >= '0' && *a <= '9')
+	    k = *a++ - '0';
+	  else if (*a >= 'A' && *a <= 'F')
+	    k = *a++ - 'A' + 10;
+	  else if (*a >= 'a' && *a <= 'f')
+	    k = *a++ - 'a' + 10;
+	  else
+	    break;
+	  j = (j << 4) + k;
+	  if (j >= 0x10000 || ++l > 4)
+	    return 0;
+	}
+      if (*a == ':' && a[1])
+	a++;
+      else if (*a == '.' && (i == 6 || i < 6 && hfil >= 0))
+	{				/* Embedded IPv4 address */
+	  u32 x;
+	  if (!ipv4_pton_u32(start, &x))
+	    return 0;
+	  words[i++] = x >> 16;
+	  words[i++] = x;
+	  break;
+	}
+      else if (*a)
+	return 0;
+      if (i >= 8)
+	return 0;
+      words[i++] = j;
+    }
+
+  /* Replace :: with an appropriate number of zeros */
+  if (hfil >= 0)
+    {
+      j = 8 - i;
+      for(i=7; i-j >= hfil; i--)
+	words[i] = words[i-j];
+      for(; i>=hfil; i--)
+	words[i] = 0;
+    }
+
+  /* Convert the address to ip_addr format */
+  for(i=0; i<4; i++)
+    o->addr[i] = (words[2*i] << 16) | words[2*i+1];
+  return 1;
+}
+
+#ifdef TEST
+
+#include "bitops.c"
+
+static void test(char *x)
+{
+  ip_addr a;
+  char c[STD_ADDRESS_P_LENGTH+1];
+
+  printf("%-40s ", x);
+  if (!ip_pton(x, &a))
+    {
+      puts("BAD");
+      return;
+    }
+  ip_ntop(a, c);
+  printf("%-40s %04x\n", c, ipv6_classify(&a));
+}
+
+int main(void)
+{
+  puts("Positive tests:");
+  test("1:2:3:4:5:6:7:8");
+  test("dead:beef:DEAD:BEEF::f00d");
+  test("::");
+  test("::1");
+  test("1::");
+  test("::1.234.5.6");
+  test("::ffff:1.234.5.6");
+  test("::fffe:1.234.5.6");
+  test("1:2:3:4:5:6:7::8");
+  test("2080::8:800:200c:417a");
+  test("ff01::101");
+
+  puts("Negative tests:");
+  test(":::");
+  test("1:2:3:4:5:6:7:8:");
+  test("1::2::3");
+  test("::12345");
+  test("::1.2.3.4:5");
+  test(":1:2:3:4:5:6:7:8");
+  test("g:1:2:3:4:5:6:7");
+  return 0;
+}
 
-#error "Ought to implement these."
+#endif
diff --git a/lib/ipv6.h b/lib/ipv6.h
index 35d8e29d..59005f94 100644
--- a/lib/ipv6.h
+++ b/lib/ipv6.h
@@ -1,7 +1,7 @@
 /*
  *	BIRD -- IP Addresses et Cetera for IPv6
  *
- *	(c) 1998 Martin Mares <mj@ucw.cz>
+ *	(c) 1999 Martin Mares <mj@ucw.cz>
  *
  *	Can be freely distributed and used under the terms of the GNU GPL.
  */
@@ -12,11 +12,11 @@
 #include <netinet/in.h>
 #include <string.h>
 
-typedef struct ipv4_addr {
+typedef struct ipv6_addr {
   u32 addr[4];
 } ip_addr;
 
-#define _MI(a,b,c,d) ((struct ip_addr) { a, b, c, d })
+#define _MI(a,b,c,d) ((struct ipv6_addr) {{ a, b, c, d }})
 #define _I0(a) ((a).addr[0])
 #define _I1(a) ((a).addr[1])
 #define _I2(a) ((a).addr[2])
@@ -28,38 +28,50 @@ typedef struct ipv4_addr {
 #define IPA_NONE _MI(0,0,0,0)
 
 #define ipa_equal(x,y) (!memcmp(&(x),&(y),sizeof(ip_addr)))
-#define ipa_nonzero(x) (_I0(a) || _I1(a) || _I2(a) || _I3(a))
-#define ipa_and(a,b) _MI(_I0(a) & _I0(b), \
-			 _I1(a) & _I1(b), \
-			 _I2(a) & _I2(b), \
-			 _I3(a) & _I3(b))
-#define ipa_or(a,b) _MI(_I0(a) | _I0(b), \
-			_I1(a) | _I1(b), \
-			_I2(a) | _I2(b), \
-			_I3(a) | _I3(b))
-#define ipa_xor(a,b) _MI(_I0(a) ^ _I0(b), \
-			 _I1(a) ^ _I1(b), \
-			 _I2(a) ^ _I2(b), \
-			 _I3(a) ^ _I3(b))
-#define ipa_not(a) _MI(~_I0(a),~_I1(a),~_I2(a),~_I3(a))
+#define ipa_nonzero(x) ({ ip_addr _a=(x); (_I0(_a) || _I1(_a) || _I2(_a) || _I3(_a)); })
+#define ipa_and(x,y) ({ ip_addr _a=(x), _b=(y); \
+		     _MI(_I0(_a) & _I0(_b), \
+			 _I1(_a) & _I1(_b), \
+			 _I2(_a) & _I2(_b), \
+			 _I3(_a) & _I3(_b)); })
+#define ipa_or(x,y)  ({ ip_addr _a=(x), _b=(y); \
+		     _MI(_I0(_a) | _I0(_b), \
+			 _I1(_a) | _I1(_b), \
+			 _I2(_a) | _I2(_b), \
+			 _I3(_a) | _I3(_b)); })
+#define ipa_xor(x,y) ({ ip_addr _a=(x), _b=(y); \
+		     _MI(_I0(_a) ^ _I0(_b), \
+			 _I1(_a) ^ _I1(_b), \
+			 _I2(_a) ^ _I2(_b), \
+			 _I3(_a) ^ _I3(_b)); })
+#define ipa_not(x) ({ ip_addr _a=(x); _MI(~_I0(_a),~_I1(_a),~_I2(_a),~_I3(_a)); })
 #define ipa_mkmask(x) ipv6_mkmask(x)
 #define ipa_mklen(x) ipv6_mklen(&(x))
 #define ipa_hash(x) ipv6_hash(&(x))
 #define ipa_hton(x) ipv6_hton(&(x))
 #define ipa_ntoh(x) ipv6_ntoh(&(x))
 #define ipa_classify(x) ipv6_classify(&(x))
+/* ipa_opposite and ipa_class_mask don't make sense with IPv6 */
+/* 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)
 
 ip_addr ipv6_mkmask(unsigned);
 unsigned ipv6_mklen(ip_addr *);
 int ipv6_classify(ip_addr *);
 void ipv6_hton(ip_addr *);
 void ipv6_ntoh(ip_addr *);
+int ipv6_compare(ip_addr *, ip_addr *);
+int ipv4_pton_u32(char *, u32 *);
 
 /* FIXME: Is this hash function uniformly distributed over standard routing tables? */
 static inline unsigned ipv6_hash(ip_addr *a)
 {
+  /* Returns a 16-bit hash key */
   u32 x = _I0(*a) ^ _I1(*a) ^ _I2(*a) ^ _I3(*a);
   return (x ^ (x >> 16) ^ (x >> 8)) & 0xffff;
 }
 
+#define IP_PREC_INTERNET_CONTROL 0		/* FIXME: What's the right value? */
+
 #endif