Merge branch 'quagga' into google-bgp-multipath

Conflicts:
	bgpd/bgp_route.c

1 files changed, 233 insertions, 81 deletions

diff --git a/lib/prefix.c b/lib/prefix.c
index 61a278ca..a3b1adf8 100644
--- a/lib/prefix.c
+++ b/lib/prefix.c
@@ -32,6 +32,139 @@
 static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
 			         0xf8, 0xfc, 0xfe, 0xff};
 
+static const struct in6_addr maskbytes6[] =
+{
+  /* /0   */ { { { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /1   */ { { { 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /2   */ { { { 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /3   */ { { { 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /4   */ { { { 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /5   */ { { { 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /6   */ { { { 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /7   */ { { { 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /8   */ { { { 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /9   */ { { { 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /10  */ { { { 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /11  */ { { { 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /12  */ { { { 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /13  */ { { { 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /14  */ { { { 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /15  */ { { { 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /16  */ { { { 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /17  */ { { { 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /18  */ { { { 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /19  */ { { { 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /20  */ { { { 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /21  */ { { { 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /22  */ { { { 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /23  */ { { { 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /24  */ { { { 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /25  */ { { { 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /26  */ { { { 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /27  */ { { { 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /28  */ { { { 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /29  */ { { { 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /30  */ { { { 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /31  */ { { { 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /32  */ { { { 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /33  */ { { { 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /34  */ { { { 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /35  */ { { { 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /36  */ { { { 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /37  */ { { { 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /38  */ { { { 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /39  */ { { { 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /40  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /41  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /42  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /43  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /44  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /45  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /46  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /47  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /48  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /49  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /50  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /51  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /52  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /53  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /54  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /55  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /56  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /57  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /58  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /59  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /60  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /61  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /62  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /63  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /64  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /65  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /66  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /67  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /68  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /69  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /70  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /71  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /72  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /73  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /74  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /75  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /76  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /77  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /78  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /79  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /80  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /81  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /82  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /83  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /84  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /85  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /86  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /87  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /88  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /89  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /90  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /91  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /92  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /93  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /94  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /95  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /96  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00 } } },
+  /* /97  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00 } } },
+  /* /98  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00 } } },
+  /* /99  */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00 } } },
+  /* /100 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00 } } },
+  /* /101 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00 } } },
+  /* /102 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00 } } },
+  /* /103 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00 } } },
+  /* /104 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00 } } },
+  /* /105 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00 } } },
+  /* /106 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00 } } },
+  /* /107 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00 } } },
+  /* /108 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00 } } },
+  /* /109 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00 } } },
+  /* /110 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00 } } },
+  /* /111 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00 } } },
+  /* /112 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00 } } },
+  /* /113 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00 } } },
+  /* /114 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00 } } },
+  /* /115 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00 } } },
+  /* /116 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00 } } },
+  /* /117 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00 } } },
+  /* /118 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00 } } },
+  /* /119 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00 } } },
+  /* /120 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00 } } },
+  /* /121 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80 } } },
+  /* /122 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0 } } },
+  /* /123 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0 } } },
+  /* /124 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0 } } },
+  /* /125 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8 } } },
+  /* /126 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc } } },
+  /* /127 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe } } },
+  /* /128 */ { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } } }
+};
+
 /* Number of bits in prefix type. */
 #ifndef PNBBY
 #define PNBBY 8
@@ -39,6 +172,21 @@ static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
 
 #define MASKBIT(offset)  ((0xff << (PNBBY - (offset))) & 0xff)
 
+unsigned int
+prefix_bit (const u_char *prefix, const u_char prefixlen)
+{
+  unsigned int offset = prefixlen / 8;
+  unsigned int shift  = 7 - (prefixlen % 8);
+  
+  return (prefix[offset] >> shift) & 1;
+}
+
+unsigned int
+prefix6_bit (const struct in6_addr *prefix, const u_char prefixlen)
+{
+  return prefix_bit((const u_char *) &prefix->s6_addr, prefixlen);
+}
+
 /* Address Famiy Identifier to Address Family converter. */
 int
 afi2family (afi_t afi)
@@ -133,11 +281,11 @@ prefix_same (const struct prefix *p1, const struct prefix *p2)
   if (p1->family == p2->family && p1->prefixlen == p2->prefixlen)
     {
       if (p1->family == AF_INET)
-	if (IPV4_ADDR_SAME (&p1->u.prefix, &p2->u.prefix))
+	if (IPV4_ADDR_SAME (&p1->u.prefix4.s_addr, &p2->u.prefix4.s_addr))
 	  return 1;
 #ifdef HAVE_IPV6
       if (p1->family == AF_INET6 )
-	if (IPV6_ADDR_SAME (&p1->u.prefix, &p2->u.prefix))
+	if (IPV6_ADDR_SAME (&p1->u.prefix6.s6_addr, &p2->u.prefix6.s6_addr))
 	  return 1;
 #endif /* HAVE_IPV6 */
     }
@@ -167,8 +315,8 @@ prefix_cmp (const struct prefix *p1, const struct prefix *p2)
   if (p1->family != p2->family || p1->prefixlen != p2->prefixlen)
     return 1;
 
-  offset = p1->prefixlen / 8;
-  shift = p1->prefixlen % 8;
+  offset = p1->prefixlen / PNBBY;
+  shift = p1->prefixlen % PNBBY;
 
   if (shift)
     if (maskbit[shift] & (pp1[offset] ^ pp2[offset]))
@@ -181,6 +329,46 @@ prefix_cmp (const struct prefix *p1, const struct prefix *p2)
   return 0;
 }
 
+/*
+ * Count the number of common bits in 2 prefixes. The prefix length is
+ * ignored for this function; the whole prefix is compared. If the prefix
+ * address families don't match, return -1; otherwise the return value is
+ * in range 0 ... maximum prefix length for the address family.
+ */
+int
+prefix_common_bits (const struct prefix *p1, const struct prefix *p2)
+{
+  int pos, bit;
+  int length = 0;
+  u_char xor;
+
+  /* Set both prefix's head pointer. */
+  const u_char *pp1 = (const u_char *)&p1->u.prefix;
+  const u_char *pp2 = (const u_char *)&p2->u.prefix;
+
+  if (p1->family == AF_INET)
+    length = IPV4_MAX_BYTELEN;
+#ifdef HAVE_IPV6
+  if (p1->family == AF_INET6)
+    length = IPV6_MAX_BYTELEN;
+#endif
+  if (p1->family != p2->family || !length)
+    return -1;
+
+  for (pos = 0; pos < length; pos++)
+    if (pp1[pos] != pp2[pos])
+      break;
+  if (pos == length)
+    return pos * 8;
+
+  xor = pp1[pos] ^ pp2[pos];
+  for (bit = 0; bit < 8; bit++)
+    if (xor & (1 << (7 - bit)))
+      break;
+
+  return pos * 8 + bit;
+}
+
 /* Return prefix family type string. */
 const char *
 prefix_family_str (const struct prefix *p)
@@ -261,25 +449,20 @@ str2prefix_ipv4 (const char *str, struct prefix_ipv4 *p)
   return ret;
 }
 
-/* Convert masklen into IP address's netmask. */
+/* Convert masklen into IP address's netmask (network byte order). */
 void
-masklen2ip (int masklen, struct in_addr *netmask)
+masklen2ip (const int masklen, struct in_addr *netmask)
 {
-  u_char *pnt;
-  int bit;
-  int offset;
+  assert (masklen >= 0 && masklen <= IPV4_MAX_BITLEN);
 
-  memset (netmask, 0, sizeof (struct in_addr));
-  pnt = (unsigned char *) netmask;
+  /* left shift is only defined for less than the size of the type.
+   * we unconditionally use long long in case the target platform
+   * has defined behaviour for << 32 (or has a 64-bit left shift) */
 
-  offset = masklen / 8;
-  bit = masklen % 8;
-  
-  while (offset--)
-    *pnt++ = 0xff;
-
-  if (bit)
-    *pnt = maskbit[bit];
+  if (sizeof(unsigned long long) > 4)
+    netmask->s_addr = htonl(0xffffffffULL << (32 - masklen));
+  else
+    netmask->s_addr = htonl(masklen ? 0xffffffffU << (32 - masklen) : 0);
 }
 
 /* Convert IP address's netmask into integer. We assume netmask is
@@ -287,54 +470,22 @@ masklen2ip (int masklen, struct in_addr *netmask)
 u_char
 ip_masklen (struct in_addr netmask)
 {
-  u_char len;
-  u_char *pnt;
-  u_char *end;
-  u_char val;
-
-  len = 0;
-  pnt = (u_char *) &netmask;
-  end = pnt + 4;
-
-  while ((pnt < end) && (*pnt == 0xff))
-    {
-      len+= 8;
-      pnt++;
-    } 
-
-  if (pnt < end)
-    {
-      val = *pnt;
-      while (val)
-	{
-	  len++;
-	  val <<= 1;
-	}
-    }
-  return len;
+  uint32_t tmp = ~ntohl(netmask.s_addr);
+  if (tmp)
+    /* clz: count leading zeroes. sadly, the behaviour of this builtin
+     * is undefined for a 0 argument, even though most CPUs give 32 */
+    return __builtin_clz(tmp);
+  else
+    return 32;
 }
 
-/* Apply mask to IPv4 prefix. */
+/* Apply mask to IPv4 prefix (network byte order). */
 void
 apply_mask_ipv4 (struct prefix_ipv4 *p)
 {
-  u_char *pnt;
-  int index;
-  int offset;
-
-  index = p->prefixlen / 8;
-
-  if (index < 4)
-    {
-      pnt = (u_char *) &p->prefix;
-      offset = p->prefixlen % 8;
-
-      pnt[index] &= maskbit[offset];
-      index++;
-
-      while (index < 4)
-	pnt[index++] = 0;
-    }
+  struct in_addr mask;
+  masklen2ip(p->prefixlen, &mask);
+  p->prefix.s_addr &= mask.s_addr;
 }
 
 /* If prefix is 0.0.0.0/0 then return 1 else return 0. */
@@ -396,7 +547,7 @@ str2prefix_ipv6 (const char *str, struct prefix_ipv6 *p)
       if (ret == 0)
 	return 0;
       plen = (u_char) atoi (++pnt);
-      if (plen > 128)
+      if (plen > IPV6_MAX_BITLEN)
 	return 0;
       p->prefixlen = plen;
     }
@@ -416,13 +567,13 @@ ip6_masklen (struct in6_addr netmask)
   
   pnt = (unsigned char *) & netmask;
 
-  while ((*pnt == 0xff) && len < 128) 
+  while ((*pnt == 0xff) && len < IPV6_MAX_BITLEN)
     {
       len += 8;
       pnt++;
     } 
   
-  if (len < 128) 
+  if (len < IPV6_MAX_BITLEN)
     {
       val = *pnt;
       while (val) 
@@ -435,23 +586,10 @@ ip6_masklen (struct in6_addr netmask)
 }
 
 void
-masklen2ip6 (int masklen, struct in6_addr *netmask)
+masklen2ip6 (const int masklen, struct in6_addr *netmask)
 {
-  unsigned char *pnt;
-  int bit;
-  int offset;
-
-  memset (netmask, 0, sizeof (struct in6_addr));
-  pnt = (unsigned char *) netmask;
-
-  offset = masklen / 8;
-  bit = masklen % 8;
-
-  while (offset--)
-    *pnt++ = 0xff;
-
-  if (bit)
-    *pnt = maskbit[bit];
+  assert (masklen >= 0 && masklen <= IPV6_MAX_BITLEN);
+  memcpy (netmask, maskbytes6 + masklen, sizeof (struct in6_addr));
 }
 
 void
@@ -570,6 +708,20 @@ sockunion2hostprefix (const union sockunion *su)
   return NULL;
 }
 
+void
+prefix2sockunion (const struct prefix *p, union sockunion *su)
+{
+  memset (su, 0, sizeof (*su));
+
+  su->sa.sa_family = p->family;
+  if (p->family == AF_INET)
+    su->sin.sin_addr = p->u.prefix4;
+#ifdef HAVE_IPV6
+  if (p->family == AF_INET6)
+    memcpy (&su->sin6.sin6_addr, &p->u.prefix6, sizeof (struct in6_addr));
+#endif /* HAVE_IPV6 */
+}
+
 int
 prefix_blen (const struct prefix *p)
 {