pipapo: Initial importHEADmaster

Signed-off-by: Stefano Brivio <sbrivio@redhat.com>

18 files changed, 3856 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..76025f6
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,78 @@
+CFLAGS += -Wall -Wextra -pedantic -march=native -mtune=native -MMD
+
+all: pipapo pipapo.debug pipapo.show pipapo.mem pipapo.noavx2 pipapo.nosimd pipapo.check
+
+SRCS := $(shell find . ! -type l -name "*.c")
+OBJS := $(SRCS:.c=.o)
+OBJS_DEBUG := $(SRCS:.c=.debug.o)
+OBJS_SHOW := $(SRCS:.c=.show.o)
+OBJS_MEM := $(SRCS:.c=.mem.o)
+OBJS_NOAVX2 := $(SRCS:.c=.noavx2.o)
+OBJS_NOSIMD := $(SRCS:.c=.nosimd.o)
+OBJS_CHECK := $(SRCS:.c=.check.o)
+DEPS := $(OBJS:.o=.d) $(OBJS_DEBUG:.o=.d) $(OBJS_SHOW:.o=.d) $(OBJS_MEM:.o=.d) $(OBJS_NOAVX2:.o=.d) $(OBJS_NOSIMD:.o=.d) $(OBJS_CHECK:.o=.d)
+
+$(OBJS): CFLAGS += -Ofast -funroll-loops -D__MATCH_AVX2 -D__MATCH_CTZL
+$(OBJS_DEBUG): CFLAGS += -O0 -g -D__MATCH_AVX2 -D__MATCH_CTZL
+$(OBJS_SHOW): CFLAGS += -DVERBOSE
+$(OBJS_MEM): CFLAGS += -DVERBOSE -D__MATCH_AVX2 -D__MATCH_CTZL
+$(OBJS_NOAVX2): CFLAGS += -Ofast -funroll-loops -DMATCH_UNROLLED -D__MATCH_CTZL
+$(OBJS_NOSIMD): CFLAGS += -Ofast -funroll-loops -DMATCH_UNROLLED
+$(OBJS_CHECK): CFLAGS += -DVERBOSE -Ofast -funroll-loops -DMATCH_UNROLLED
+
+pipapo: $(OBJS)
+	$(CC) $(CFLAGS) $(OBJS) -o pipapo
+
+pipapo.debug: $(OBJS_DEBUG)
+	$(CC) $(CFLAGS) $(OBJS_DEBUG) -o pipapo.debug
+
+pipapo.show: $(OBJS_SHOW)
+	$(CC) $(CFLAGS) $(OBJS_SHOW) -o pipapo.show
+
+pipapo.mem: $(OBJS_MEM)
+	$(CC) $(CFLAGS) $(OBJS_MEM) -o pipapo.mem
+
+pipapo.noavx2: $(OBJS_NOAVX2)
+	$(CC) $(CFLAGS) $(OBJS_NOAVX2) -o pipapo.noavx2
+
+pipapo.nosimd: $(OBJS_NOSIMD)
+	$(CC) $(CFLAGS) $(OBJS_NOSIMD) -o pipapo.nosimd
+
+pipapo.check: $(OBJS_CHECK)
+	$(CC) $(CFLAGS) $(OBJS_CHECK) -o pipapo.check
+
+%.debug.c: %.c
+	ln -s $< $@
+
+%.show.c: %.c
+	ln -s $< $@
+
+%.mem.c: %.c
+	ln -s $< $@
+
+%.noavx2.c: %.c
+	ln -s $< $@
+
+%.nosimd.c: %.c
+	ln -s $< $@
+
+%.check.c: %.c
+	ln -s $< $@
+
+%.o: %.c Makefile
+	$(CC) $(CFLAGS) -MMD -c -o $@ $<
+
+LINKS := $(shell find . -type l -name "*.c")
+
+.SECONDARY:
+
+.PHONY: clean tests
+clean:
+	-${RM} pipapo pipapo.debug pipapo.show pipapo.mem pipapo.noavx2 pipapo.nosimd $(OBJS) $(OBJS_DEBUG) $(OBJS_SHOW) $(OBJS_MEM) $(OBJS_NOAVX2) $(OBJS_NOSIMD) $(OBJS_CHECK) $(DEPS) $(LINKS)
+	-${RM} -r tests/plots
+
+tests: all
+	cd tests; ./run.sh
+	display tests/plots/*.png
+
+-include $(DEPS)
diff --git a/README b/README
new file mode 100644
index 0000000..3a6a81d
--- /dev/null
+++ b/README
@@ -0,0 +1,16 @@
+Build with:
+
+	make
+
+Run tests and display performance plots with:
+
+	make tests
+
+Run the 'show' target to show all the steps with an example ruleset and
+packet list, e.g.:
+
+	./pipapo.show tests/net_port_ranged.tiny tests/net_port_ranged.tiny.packets
+
+Run the main target for a quick performance test against a ruleset, e.g.:
+
+	./pipapo tests/net_port.static tests/net_port.static.packets
diff --git a/avx2.h b/avx2.h
new file mode 100644
index 0000000..fca4c60
--- /dev/null
+++ b/avx2.h
@@ -0,0 +1,355 @@
+/* PIPAPO - PIle PAcket POlicies
+ *
+ * avx2.h - Lookup routines based on AVX2 intrinsics
+ *
+ * Author: Stefano Brivio <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <immintrin.h>
+#include <stdint.h>
+
+#define AVX_LOAD(lt, g, v, bsize)					\
+	_mm256_stream_load_si256((__m256i *)(lt + (g * BUCKETS + (v)) * bsize));
+
+/**
+ * avx2_lookup4() - AVX2-based lookup for packet fields of 4 four-bit groups
+ * @map:	Previous matching bitmap that will be updated
+ * @lt:		Lookup table for this field
+ * @pkt:	Packet bytes to be matched
+ * @bsize:	Bucket size for this lookup table, in bytes
+ * @first:	If this is the first field in a set, start with all-ones bitmap
+ * @last:	Last field: stop on the first match and return position
+ *
+ * Load buckets from lookup table corresponding to the values of each 4-bit
+ * group of packet bytes, and perform a bitwise intersection between them. If
+ * this is the first field in the set, simply AND the buckets together
+ * (equivalent to using an all-ones starting bitmap), use the provided starting
+ * bitmap otherwise. Then store the resulting match bitmap in @map.
+ *
+ * This implements steps 4.1 to 4.3 of the algorithm description, and is used
+ * for 16-bit fields (i.e. ports).
+ *
+ * Return: 32-byte rounded position of match, if last field, otherwise 0 on
+ * match and -1 on no match.
+ */
+__always_inline int avx2_lookup4(uint8_t *map, uint8_t *lt, uint8_t *pkt,
+				 int bsize, int first, int last)
+{
+	__m256i r0, r1, r2, r3, r4;
+	int i, ret = -1;
+
+	for (i = 0; i < bsize; i += 32) {
+		r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize);
+		r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize);
+		r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize);
+		r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize);
+
+		if (first) {
+			r4 = _mm256_and_si256(r1, r0);
+		} else {
+			r4 = _mm256_stream_load_si256((__m256i *)(map + i));
+
+			r4 = _mm256_and_si256(r0, r4);
+			r4 = _mm256_and_si256(r1, r4);
+		}
+		r4 = _mm256_and_si256(r2, r4);
+		r4 = _mm256_and_si256(r3, r4);
+
+		if (!_mm256_testz_si256(r4, r4)) {
+			if (last) {
+				_mm256_store_si256((__m256i *)(map + i), r4);
+				return i;
+			}
+			ret = 0;
+		}
+		_mm256_store_si256((__m256i *)(map + i), r4);
+	}
+
+	return ret;
+}
+
+/**
+ * avx2_lookup8() - AVX2-based lookup for packet fields of 8 four-bit groups
+ * @map:	Previous matching bitmap that will be updated
+ * @lt:		Lookup table for this field
+ * @pkt:	Packet bytes to be matched
+ * @bsize:	Bucket size for this lookup table, in bytes
+ * @first:	If this is the first field in a set, start with all-ones bitmap
+ * @last:	Last field: stop on the first match and return position
+ *
+ * Load buckets from lookup table corresponding to the values of each 4-bit
+ * group of packet bytes, and perform a bitwise intersection between them. If
+ * this is the first field in the set, simply AND the buckets together
+ * (equivalent to using an all-ones starting bitmap), use the provided starting
+ * bitmap otherwise. Then store the resulting match bitmap in @map.
+ *
+ * This implements steps 4.1 to 4.3 of the algorithm description, and is used
+ * for 32-bit fields (i.e. IPv4 addresses).
+ *
+ * Return: 32-byte rounded position of match, if last field, otherwise 0 on
+ * match and -1 on no match.
+ */
+__always_inline int avx2_lookup8(uint8_t *map, uint8_t *lt, uint8_t *pkt,
+				 int bsize, int first, int last)
+{
+	__m256i r0, r1, r2, r3, r4, r5, r6, r7, r8;
+	int i, ret = -1;
+
+	for (i = 0; i < bsize; i += 32) {
+		r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize);
+		r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize);
+		r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize);
+		r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize);
+		r4 = AVX_LOAD(lt + i, 4, pkt[2] >> 4, bsize);
+		r5 = AVX_LOAD(lt + i, 5, pkt[2] & 0x0f, bsize);
+		r6 = AVX_LOAD(lt + i, 6, pkt[3] >> 4, bsize);
+		r7 = AVX_LOAD(lt + i, 7, pkt[3] & 0x0f, bsize);
+
+		if (first) {
+			r8 = _mm256_and_si256(r1, r0);
+		} else {
+			r8 = _mm256_stream_load_si256((__m256i *)(map + i));
+			r8 = _mm256_and_si256(r0, r8);
+			r8 = _mm256_and_si256(r1, r8);
+		}
+		r8 = _mm256_and_si256(r2, r8);
+		r8 = _mm256_and_si256(r3, r8);
+		r8 = _mm256_and_si256(r4, r8);
+		r8 = _mm256_and_si256(r5, r8);
+		r8 = _mm256_and_si256(r6, r8);
+		r8 = _mm256_and_si256(r7, r8);
+
+		if (!_mm256_testz_si256(r8, r8)) {
+			if (last) {
+				_mm256_store_si256((__m256i *)(map + i), r8);
+				return i;
+			}
+			ret = 0;
+		}
+		_mm256_store_si256((__m256i *)(map + i), r8);
+	}
+
+	return ret;
+}
+
+/**
+ * avx2_lookup12() - AVX2-based lookup for packet fields of 12 four-bit groups
+ * @map:	Previous matching bitmap that will be updated
+ * @lt:		Lookup table for this field
+ * @pkt:	Packet bytes to be matched
+ * @bsize:	Bucket size for this lookup table, in bytes
+ * @first:	If this is the first field in a set, start with all-ones bitmap
+ * @last:	Last field: stop on the first match and return position
+ *
+ * Load buckets from lookup table corresponding to the values of each 4-bit
+ * group of packet bytes, and perform a bitwise intersection between them. If
+ * this is the first field in the set, simply AND the buckets together
+ * (equivalent to using an all-ones starting bitmap), use the provided starting
+ * bitmap otherwise. Then store the resulting match bitmap in @map.
+ *
+ * This implements steps 4.1 to 4.3 of the algorithm description, and is used
+ * for 48-bit fields (i.e. MAC addresses).
+ *
+ * Return: 32-byte rounded position of match, if last field, otherwise 0 on
+ * match and -1 on no match.
+ */
+__always_inline int avx2_lookup12(uint8_t *map, uint8_t *lt, uint8_t *pkt,
+				  int bsize, int first, int last)
+{
+	__m256i r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12;
+	int i, ret = -1;
+
+	for (i = 0; i < bsize; i += 32) {
+		r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize);
+		r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize);
+		r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize);
+		r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize);
+		r4 = AVX_LOAD(lt + i, 4, pkt[2] >> 4, bsize);
+		r5 = AVX_LOAD(lt + i, 5, pkt[2] & 0x0f, bsize);
+		r6 = AVX_LOAD(lt + i, 6, pkt[3] >> 4, bsize);
+		r7 = AVX_LOAD(lt + i, 7, pkt[3] & 0x0f, bsize);
+		r8 = AVX_LOAD(lt + i, 8, pkt[4] >> 4, bsize);
+		r9 = AVX_LOAD(lt + i, 9, pkt[4] & 0x0f, bsize);
+		r10 = AVX_LOAD(lt + i, 10, pkt[5] >> 4, bsize);
+		r11 = AVX_LOAD(lt + i, 11, pkt[5] & 0x0f, bsize);
+
+		if (first) {
+			r12 = _mm256_and_si256(r0, r1);
+		} else {
+			r12 = _mm256_stream_load_si256((__m256i *)(map + i));
+			r12 = _mm256_and_si256(r0, r12);
+			r12 = _mm256_and_si256(r1, r12);
+		}
+
+		r12 = _mm256_and_si256(r0, r12);
+		r12 = _mm256_and_si256(r1, r12);
+		r12 = _mm256_and_si256(r2, r12);
+		r12 = _mm256_and_si256(r3, r12);
+		r12 = _mm256_and_si256(r4, r12);
+		r12 = _mm256_and_si256(r5, r12);
+		r12 = _mm256_and_si256(r6, r12);
+		r12 = _mm256_and_si256(r7, r12);
+		r12 = _mm256_and_si256(r8, r12);
+		r12 = _mm256_and_si256(r9, r12);
+		r12 = _mm256_and_si256(r10, r12);
+		r12 = _mm256_and_si256(r11, r12);
+
+		if (!_mm256_testz_si256(r12, r12)) {
+			if (last) {
+				_mm256_store_si256((__m256i *)(map + i), r12);
+				return i;
+			}
+			ret = 0;
+		}
+		_mm256_store_si256((__m256i *)(map + i), r12);
+	}
+
+	return ret;
+}
+
+/**
+ * avx2_lookup32() - AVX2-based lookup for packet fields of 32 four-bit groups
+ * @map:	Previous matching bitmap that will be updated
+ * @lt:		Lookup table for this field
+ * @pkt:	Packet bytes to be matched
+ * @bsize:	Bucket size for this lookup table, in bytes
+ * @first:	If this is the first field in a set, start with all-ones bitmap
+ * @last:	Last field: stop on the first match and return position
+ *
+ * Load buckets from lookup table corresponding to the values of each 4-bit
+ * group of packet bytes, and perform a bitwise intersection between them. If
+ * this is the first field in the set, simply AND the buckets together
+ * (equivalent to using an all-ones starting bitmap), use the provided starting
+ * bitmap otherwise. Then store the resulting match bitmap in @map.
+ *
+ * This implements steps 4.1 to 4.3 of the algorithm description, and is used
+ * for 128-bit fields (i.e. IPv6 addresses).
+ *
+ * Return: 32-byte rounded position of match, if last field, otherwise 0 on
+ * match and -1 on no match.
+ */
+__always_inline int avx2_lookup32(uint8_t *map, uint8_t *lt, uint8_t *pkt,
+				  int bsize, int first, int last)
+{
+	__m256i r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r15;
+	int i, ret = -1;
+
+	for (i = 0; i < bsize; i += 32) {
+		r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize);
+		r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize);
+		r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize);
+		r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize);
+		r4 = AVX_LOAD(lt + i, 4, pkt[2] >> 4, bsize);
+		r5 = AVX_LOAD(lt + i, 5, pkt[2] & 0x0f, bsize);
+		r6 = AVX_LOAD(lt + i, 6, pkt[3] >> 4, bsize);
+		r7 = AVX_LOAD(lt + i, 7, pkt[3] & 0x0f, bsize);
+		r8 = AVX_LOAD(lt + i, 8, pkt[4] >> 4, bsize);
+		r9 = AVX_LOAD(lt + i, 9, pkt[4] & 0x0f, bsize);
+		r10 = AVX_LOAD(lt + i, 10, pkt[5] >> 4, bsize);
+		r11 = AVX_LOAD(lt + i, 11, pkt[5] & 0x0f, bsize);
+		r12 = AVX_LOAD(lt + i, 12, pkt[6] >> 4, bsize);
+		r13 = AVX_LOAD(lt + i, 13, pkt[6] & 0x0f, bsize);
+
+		if (first) {
+			r15 = _mm256_and_si256(r0, r1);
+		} else {
+			r15 = _mm256_stream_load_si256((__m256i *)(map + i));
+			r15 = _mm256_and_si256(r0, r15);
+			r15 = _mm256_and_si256(r1, r15);
+		}
+
+		r15 = _mm256_and_si256(r2, r15);
+		r15 = _mm256_and_si256(r3, r15);
+		r15 = _mm256_and_si256(r4, r15);
+		r15 = _mm256_and_si256(r5, r15);
+		r15 = _mm256_and_si256(r6, r15);
+		r15 = _mm256_and_si256(r7, r15);
+		r15 = _mm256_and_si256(r8, r15);
+		r15 = _mm256_and_si256(r9, r15);
+		r15 = _mm256_and_si256(r10, r15);
+		r15 = _mm256_and_si256(r11, r15);
+		r15 = _mm256_and_si256(r12, r15);
+		r15 = _mm256_and_si256(r13, r15);
+
+		r0 = AVX_LOAD(lt + i, 14, pkt[7] >> 4, bsize);
+		r1 = AVX_LOAD(lt + i, 15, pkt[7] & 0x0f, bsize);
+		r2 = AVX_LOAD(lt + i, 16, pkt[8] >> 4, bsize);
+		r3 = AVX_LOAD(lt + i, 17, pkt[8] & 0x0f, bsize);
+		r4 = AVX_LOAD(lt + i, 18, pkt[9] >> 4, bsize);
+		r5 = AVX_LOAD(lt + i, 19, pkt[9] & 0x0f, bsize);
+		r6 = AVX_LOAD(lt + i, 20, pkt[10] >> 4, bsize);
+		r7 = AVX_LOAD(lt + i, 21, pkt[10] & 0x0f, bsize);
+		r8 = AVX_LOAD(lt + i, 22, pkt[11] >> 4, bsize);
+		r9 = AVX_LOAD(lt + i, 23, pkt[11] & 0x0f, bsize);
+		r10 = AVX_LOAD(lt + i, 24, pkt[12] >> 4, bsize);
+		r11 = AVX_LOAD(lt + i, 25, pkt[12] & 0x0f, bsize);
+		r12 = AVX_LOAD(lt + i, 26, pkt[13] >> 4, bsize);
+		r13 = AVX_LOAD(lt + i, 27, pkt[13] & 0x0f, bsize);
+
+		r15 = _mm256_and_si256(r0, r15);
+		r15 = _mm256_and_si256(r1, r15);
+		r15 = _mm256_and_si256(r2, r15);
+		r15 = _mm256_and_si256(r3, r15);
+		r15 = _mm256_and_si256(r4, r15);
+		r15 = _mm256_and_si256(r5, r15);
+		r15 = _mm256_and_si256(r6, r15);
+		r15 = _mm256_and_si256(r7, r15);
+		r15 = _mm256_and_si256(r8, r15);
+		r15 = _mm256_and_si256(r9, r15);
+		r15 = _mm256_and_si256(r10, r15);
+		r15 = _mm256_and_si256(r11, r15);
+		r15 = _mm256_and_si256(r12, r15);
+		r15 = _mm256_and_si256(r13, r15);
+
+		r0 = AVX_LOAD(lt + i, 28, pkt[14] >> 4, bsize);
+		r1 = AVX_LOAD(lt + i, 29, pkt[14] & 0x0f, bsize);
+		r2 = AVX_LOAD(lt + i, 30, pkt[15] >> 4, bsize);
+		r3 = AVX_LOAD(lt + i, 31, pkt[15] & 0x0f, bsize);
+
+		r15 = _mm256_and_si256(r0, r15);
+		r15 = _mm256_and_si256(r1, r15);
+		r15 = _mm256_and_si256(r2, r15);
+		r15 = _mm256_and_si256(r3, r15);
+
+		if (!_mm256_testz_si256(r15, r15)) {
+			if (last) {
+				_mm256_store_si256((__m256i *)(map + i), r15);
+				return i;
+			}
+			ret = 0;
+		}
+		_mm256_store_si256((__m256i *)(map + i), r15);
+	}
+
+	return ret;
+}
+
+/**
+ * avx2_lookup() - AVX2-based lookup for packet fields
+ * @map:	Previous matching bitmap that will be updated
+ * @lt:		Lookup table for this field
+ * @pkt:	Packet bytes to be matched
+ * @bsize:	Bucket size for this lookup table, in bytes
+ * @first:	If this is the first field in a set, start with all-ones bitmap
+ * @last:	If this is the last field in a set, stop on the first match
+ *
+ * This implements steps 4.1 to 4.3 of the algorithm description.
+ *
+ * Return: 32-byte rounded position of match, if last field, otherwise 0 on
+ * match and -1 on no match.
+ */
+__always_inline int avx2_lookup(uint8_t *map, uint8_t *lt, uint8_t *pkt,
+				int groups, int bsize, int first, int last)
+{
+	if (groups == 4)
+		return avx2_lookup4(map, lt, pkt, bsize, first, last);
+	if (groups == 8)
+		return avx2_lookup8(map, lt, pkt, bsize, first, last);
+	if (groups == 12)
+		return avx2_lookup12(map, lt, pkt, bsize, first, last);
+	if (groups == 32)
+		return avx2_lookup32(map, lt, pkt, bsize, first, last);
+
+	return 0;
+}
diff --git a/match.c b/match.c
new file mode 100644
index 0000000..31bdb5f
--- /dev/null
+++ b/match.c
@@ -0,0 +1,284 @@
+/* PIPAPO - PIle PAcket POlicies
+ *
+ * match.c - Equivalent match implementation for kernel
+ *
+ * Author: Stefano Brivio <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "pipapo.h"
+#include "util.h"
+#include "set.h"
+#include "match.h"
+
+#ifdef MATCH_AVX2
+#include "avx2.h"
+#endif
+
+/**
+ * match_init() - Initialise equivalent of matching data representation
+ * @s:		Set data
+ * @layout:	Set layout
+ *
+ * This conceptually corresponds to the creation of in-kernel matching data.
+ *
+ * Return: 0 on success, NULL on failure
+ */
+struct kernel_set *kernel_init(struct set *s, struct desc_spec **layout)
+{
+	struct kernel_set *ks;
+	struct field *f;
+	int i;
+
+	ks = calloc(sizeof(*ks), 1);
+	if (!ks)
+		return NULL;
+
+	for_each_field(f, s, layout) {
+		ks->offset[i] = f->offset;
+		ks->groups[i] = f->groups;
+		ks->bsize[i] = f->bsize;
+#ifdef MATCH_AVX2
+		ks->lt[i] = aligned_alloc(32, f->groups * f->bsize * BUCKETS);
+#else
+		ks->lt[i] = malloc(f->groups * f->bsize * BUCKETS);
+#endif
+		memcpy(ks->lt[i], f->lt, f->groups * f->bsize * BUCKETS);
+
+#ifdef MATCH_CTZL
+		ks->mt[i] = aligned_alloc(8, f->rules * sizeof(*ks->mt[i]));
+#else
+		ks->mt[i] = malloc(f->rules * sizeof(*ks->mt[i]));
+#endif
+		memcpy(ks->mt[i], f->mt, f->rules * sizeof(*ks->mt[i]));
+
+		if (f->bsize > ks->max_bsize)
+			ks->max_bsize = f->bsize;
+	}
+	ks->groups[i] = 0;
+
+#ifdef MATCH_AVX2
+	ks->map[0] = aligned_alloc(32, round_up(ks->max_bsize, 32));
+	ks->map[1] = aligned_alloc(32, round_up(ks->max_bsize, 32));
+	memset(ks->map[0], 0, ks->max_bsize);
+	memset(ks->map[1], 0, ks->max_bsize);
+#else
+	ks->map[0] = calloc(ks->max_bsize, 1);
+	ks->map[1] = calloc(ks->max_bsize, 1);
+#endif
+
+	return ks;
+}
+
+#if defined(VERBOSE) && !defined(MATCH_UNROLLED) && !defined(MATCH_AVX2)
+/**
+ * show_match() - Show bucket and bitmap result for a single matching step
+ * @res:	Resulting bitmap to be displayed
+ * @group_lt:	Pointer to lookup table row for current bit group
+ * @v:		Value of packet bytes for current group
+ * @bsize:	Lookup bucket size, in bytes
+ *
+ * For documentation purposes only: this shows algorithm step 4.3 in detail.
+ */
+static void show_match(uint8_t *res, uint8_t *group_lt, int v, int bsize)
+{
+	uint8_t *bucket = group_lt + v * bsize;
+	int i;
+
+	fprintf(stdout, "  bucket: ");
+	for (i = 0; i < bsize; i++)
+		fprintf(stdout, "%02x ", bucket[i]);
+	fprintf(stdout, "(value: %i)\n", v);
+
+	fprintf(stdout, "  result: ");
+	for (i = 0; i < bsize; i++)
+		fprintf(stdout, "%02x ", res[i]);
+	fprintf(stdout, "\n\n");
+}
+#else
+#define show_match(...) do { } while (0)
+#endif
+
+#ifdef VERBOSE
+/**
+ * show_field() - Show field packet bytes and initial bitmap for given field
+ * @f:		Index of current field in set
+ * @pkt:	Packet bytes for this field
+ * @init:	Initial bitmap
+ * @bsize:	Lookup bucket size, in bytes
+ *
+ * For documentation purposes only: this shows algorithm steps 4.1 and 4.2.
+ */
+static void show_field(int f, uint8_t *pkt, int len, uint8_t *init, int bsize)
+{
+	int i;
+
+	fprintf(stdout, "\nField %i, packet bytes:", f);
+	for (i = 0; i < len; i++)
+		fprintf(stdout, " %02x", pkt[i]);
+
+	fprintf(stdout, ", initial bitmap:");
+	for (i = 0; i < bsize; i++)
+		fprintf(stdout, " %02x", init[i]);
+	fprintf(stdout, "\n\n");
+}
+#else
+#define show_field(...) do { } while (0)
+#endif
+
+/* Provide explicitly unrolled versions for lookup steps: the compiler doesn't
+ * know that only some group sizes make sense. This speeds up non-AVX2 matching.
+ */
+#define MATCH_REPEAT_4(x)						       \
+	andmem(map[idx], lt + (x +  0 + (*pkt_p >> 4)) * ks->bsize[f],	       \
+	       ks->bsize[f]);						       \
+	andmem(map[idx], lt + (x + 16 + (*pkt_p & 0x0f)) * ks->bsize[f],       \
+	       ks->bsize[f]);						       \
+	pkt_p++;							       \
+	andmem(map[idx], lt + (x + 32 + (*pkt_p >> 4)) * ks->bsize[f],	       \
+	       ks->bsize[f]);						       \
+	andmem(map[idx], lt + (x + 48 + (*pkt_p & 0x0f)) * ks->bsize[f],       \
+	       ks->bsize[f]);						       \
+	pkt_p++;
+
+#define MATCH_REPEAT_8(x)						\
+	MATCH_REPEAT_4(x)						\
+	MATCH_REPEAT_4(x + 64)
+
+#define MATCH_REPEAT_12							\
+	MATCH_REPEAT_8(0)						\
+	MATCH_REPEAT_4(128)
+
+#define MATCH_REPEAT_32							\
+	MATCH_REPEAT_8(0)						\
+	MATCH_REPEAT_8(128)						\
+	MATCH_REPEAT_8(256)						\
+	MATCH_REPEAT_8(384)
+
+/**
+ * match() - Equivalent of in-kernel matching implementation
+ * @ks:		Kernel representation of set data
+ * @packet:	Packet bytes
+ *
+ * This conceptually corresponds to the in-kernel matching function, and it
+ * implements algorithm steps 4.1 to 4.5.
+ *
+ * Return: matched key if any, 0 otherwise
+ */
+uint32_t match(struct kernel_set *ks, uint8_t *packet)
+{
+	int f, g, b, match = 0, offset, idx = ks->map_idx;
+	uint8_t *pkt_p, *lt, v, **map = ks->map;
+
+	(void)g;
+	(void)v;
+	(void)offset;
+	(void)match;
+
+#ifndef MATCH_AVX2
+	/* AVX2 implementation loads all matching buckets first, so an explicit
+	 * initial all-ones bitmap isn't needed.
+	 */
+	memset(map[idx], 0xff, ks->max_bsize);
+#endif
+
+	/* Go through each set field */
+	for (f = 0; ks->groups[f]; f++) {
+		lt = ks->lt[f];
+		pkt_p = packet + ks->offset[f];
+
+		show_field(f, pkt_p, ks->groups[f] / 2, map[idx], ks->bsize[f]);
+
+		/* For each 4-bit group, select lookup table bucket depending on
+		 * packet bytes value, AND bucket values (steps 4.1 - 4.3).
+		 */
+#ifdef MATCH_UNROLLED
+		if (ks->groups[f] == 4) {
+			MATCH_REPEAT_4(0);
+		} else if (ks->groups[f] == 8) {
+			MATCH_REPEAT_8(0);
+		} else if (ks->groups[f] == 12) {
+			MATCH_REPEAT_12;
+		} else if (ks->groups[f] == 32) {
+			MATCH_REPEAT_32;
+		}
+#elif defined(MATCH_AVX2)
+		match = avx2_lookup(map[idx], lt, pkt_p, ks->groups[f],
+				    ks->bsize[f], f == 0, !ks->groups[f + 1]);
+		if (match < 0) {
+			ks->map_idx = idx;
+			return 0;
+		}
+#else /* !MATCH_UNROLLED && !MATCH_AVX2 */
+		for (g = 0; g < ks->groups[f]; g++) {
+			if (g % 2) {
+				v = *pkt_p & 0x0f;
+				pkt_p++;
+			} else {
+				v = *pkt_p >> 4;
+			}
+			andmem(map[idx], lt + v * ks->bsize[f], ks->bsize[f]);
+			show_match(map[idx], lt, v, ks->bsize[f]);
+			lt += ks->bsize[f] * BUCKETS;
+		}
+#endif
+
+		/* Now populate the bitmap for the next field, unless this is
+		 * the last field, in which case return the matched key if any
+		 * (steps 4.4 - 4.5). Now map[idx] contains the matching bitmap,
+		 * and map[!idx] is the bitmap for the next field.
+		 *
+		 * If we used the AVX2-based lookup, and this is the last field,
+		 * we can already give ffs_and_fill() a hint about the position
+		 * of the first bit set: that won't be before a 'match' offset.
+		 */
+#ifdef MATCH_CTZL
+		b = ffs_and_fill(map[idx], match, ks->bsize[f] / 8, map[!idx],
+				 ks->mt[f], !ks->groups[f + 1]);
+		if (b < 0) {
+			ks->map_idx = idx;
+			return 0;
+		}
+		if (!ks->groups[f + 1]) {
+			/* Last field: we're just returning the key without
+			 * filling the next bitmap, so _map[!idx]_ is clear and
+			 * can be reused as *next* bitmap (not initial) for the
+			 * next packet.
+			 */
+			ks->map_idx = idx;
+			return ks->mt[f][b].key;
+		}
+#else
+		offset = match = 0;
+		while ((b = ffs_clear(map[idx], ks->bsize[f], offset)) >= 0) {
+			if (!ks->groups[f + 1]) {
+				ks->map_idx = !idx;
+				return ks->mt[f][b].key;
+			}
+
+			offset = b / (sizeof(int) * 8);
+			match = 1;
+			verbose("  map bit %i: fill %i bit%s from %i\n", b,
+				ks->mt[f][b].n, ks->mt[f][b].n == 1 ? "" : "s",
+				ks->mt[f][b].to);
+			fill(map[!idx], ks->mt[f][b].to, ks->mt[f][b].n);
+		}
+
+		if (!match) {
+			ks->map_idx = !idx;
+			return 0;
+		}
+#endif
+		/* Swap bitmap indices: map[!idx] will be the initial bitmap,
+		 * and map[idx] is guaranteed to be all-zeroes at this point.
+		 */
+		idx = !idx;
+	}
+
+	return 0;
+}
diff --git a/match.h b/match.h
new file mode 100644
index 0000000..c3821a7
--- /dev/null
+++ b/match.h
@@ -0,0 +1,24 @@
+/**
+ * struct kernel_set - Representation of in-kernel set data
+ * @groups:	Number of 4-bit groups for each field (algorithm step 3.1)
+ * @offset:	Offset of field within packet data, in bytes
+ * @bsize:	Lookup table bucket size for field, in bytes
+ * @lt:		Lookup table for field (algorithm steps 3.2 - 3.4)
+ * @mt:		Mapping table for field (algorithm steps 3.5 - 3.6)
+ * @map:	Result bitmap, two copies: swap indices instead of copying
+ * @map_idx:	Index of current matching bitmap
+ * @max_bsize:	Maximum lookup table bucket size for all fields in the set
+ */
+struct kernel_set {
+	int groups[MAX_FIELDS];
+	int offset[MAX_FIELDS];
+	int bsize[MAX_FIELDS];
+	uint8_t *lt[MAX_FIELDS];
+	union map_bucket *mt[MAX_FIELDS];
+	uint8_t *map[2];
+	int map_idx;
+	int max_bsize;
+};
+
+struct kernel_set *kernel_init(struct set *s, struct desc_spec **layout);
+uint32_t match(struct kernel_set *ks, uint8_t *packet);
diff --git a/pipapo.c b/pipapo.c
new file mode 100644
index 0000000..d44cb72
--- /dev/null
+++ b/pipapo.c
@@ -0,0 +1,1093 @@
+/* PIPAPO - PIle PAcket POlicies
+ *
+ * pipapo.c - Stand-alone algorithm implementation
+ *
+ * Author: Stefano Brivio <sbrivio@redhat.com>
+ * License: GPLv2
+ *
+ *
+ * == 1. Problem
+ *
+ * Match packets against n generic entries with m (ipset-like) fields in a set,
+ * mapping them to n keys, for example:
+ *
+ *             --- fields --->
+ *   |     [net],[port],[net]... => [key]
+ * entries [net],[port],[net]... => [key]
+ *   |     [net],[port],[net]... => [key]
+ *   V     ...
+ *
+ * where [net] fields can be IP ranges or netmasks, and [port] fields are port
+ * ranges. Arbitrary packet fields (source and destination IPv4, IPv6, MAC
+ * addresses and ports) can be matched.
+ *
+ *
+ * == 2. Introduction
+ *
+ * This algorithm is loosely inspired by [Ligatti 2010], and fundamentally
+ * relies on the consideration that every contiguous range in a space of b bits
+ * can be converted into b netmasks, from Theorem 3 in [Rottenstreich 2010].
+ * Despite the fact that we don't implement a boolean classifier here, some
+ * relevant optimisation ideas were inspired by [Kogan 2014], especially related
+ * to the notion of order-independent regions of a classifier.
+ *
+ * Classification against a number of entries, that require matching given bits
+ * of a packet field, is performed by grouping those bits in sets of arbitrary
+ * size, and classifying packet bits one group at a time.
+ *
+ *   Example: to match the source port (16 bits) of a packet, we can divide
+ *   those 16 bits in 4 groups of 4 bits each. Given the entry:
+ *      0000 0001 0101 1001
+ *   and a packet with source port:
+ *      0000 0001 1010 1001
+ *   first and second groups match, but the third doesn't. We conclude that the
+ *   packet doesn't match the given entry.
+ *
+ * Translate the set to a sequence of lookup tables, one per field. Each table
+ * has two dimensions: bit groups to be matched for a single packet field, and
+ * all the possible values of said groups. Each group in the table maps to the
+ * next group through a set of rules, which are generated from entries during
+ * the pre-computation phase. The last group in a table maps to the next table,
+ * and the set of matched rules after the last table in the set is mapped to a
+ * single verdict key.
+ *
+ * To match, we perform table lookups using the values of relevant packet bits,
+ * divided according to the groups, and use a sequence of bitwise operations to
+ * progressively evaluate rule matching.
+ *
+ * In the description below, the basic idea is described first, and
+ * optimisations are illustrated later. Steps with O(n) computational complexity
+ * are then all reduced to O(log(n)) problems.
+ *
+ *
+ * == 3. Precomputation
+ *
+ * - For each packet field:
+ *
+ *   (3.1) divide the b packet bits we want to classify into groups of size t,
+ *   obtaining ceil(b / t) groups
+ *
+ *      Example: match on destination IP address, with t = 4: 32 bits, 8 groups
+ *      of 4 bits each
+ *
+ *   (3.2) allocate a lookup table with one column ("bucket") for each possible
+ *   value of a group, and with one row for each group
+ *
+ *      Example: 8 groups, 2^4 buckets:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0
+ *        1
+ *        2
+ *        3
+ *        4
+ *        5
+ *        6
+ *        7
+ *
+ *   (3.3) map the bits we want to classify for the current field, for a given
+ *   entry, to a single rule for non-ranged and netmask set items, and to one or
+ *   multiple rules for ranges. Ranges are expanded to composing netmasks:
+ *
+ *      Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048
+ *      - rule #0: 10.0.0.5
+ *      - rule #1: 192.168.1.0/24
+ *      - rule #2: 192.168.2.0/31
+ *
+ *   (3.4) insert references to the rules in the lookup table, selecting buckets
+ *   according to bit values of a rule in the given group
+ *
+ *      Example: given:
+ *      - rule #0: 10.0.0.5 mapping to buckets
+ *        < 0 10  0 0   0 0  0 5 >
+ *      - rule #1: 192.168.1.0/24 mapping to buckets
+ *        < 12 0  10 8  0 1  < 0..15 > < 0..15 > >
+ *      - rule #2: 192.168.2.0/31 mapping to buckets
+ *        < 12 0  10 8  0 2  0 < 0..1 > >
+ *
+ *      these bits are set in the lookup table:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0    0                                              1,2
+ *        1   1,2                                      0
+ *        2    0                                      1,2
+ *        3    0                              1,2
+ *        4  0,1,2
+ *        5    0   1   2
+ *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
+ *
+ *   (3.5) if this is not the last field in the set, build a mapping table that
+ *   maps rules from the lookup table to rules belonging to the same entry in
+ *   the next lookup table
+ *
+ *      Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048
+ *
+ *      given lookup table #0 (see example above):
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0    0                                              1,2
+ *        1   1,2                                      0
+ *        2    0                                      1,2
+ *        3    0                              1,2
+ *        4  0,1,2
+ *        5    0   1   2
+ *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
+ *
+ *      and lookup table #1 with:
+ *      - rule #0: 1024 mapping to buckets
+ *        < 0  0  4  0 >
+ *      - rule #1: 2048 mapping to buckets
+ *        < 0  0  5  0 >
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0   0,1
+ *        1   0,1
+ *        2                    0   1
+ *        3   0,1
+ *
+ *      we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024
+ *      in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1
+ *      (rules #1, #2) to 2048 in lookup table #2 (rule #1):
+ *
+ *                 rules
+ *               0   1   2
+ *      map to:  0   1   1
+ *
+ *   (3.6) if this is the last field in the set, build a mapping table that maps
+ *   rules from the last lookup table to verdict keys
+ *
+ *      Example: 10.0.0.5:1024 gives 66 as verdict and
+ *      192.168.1.0-192.168.2.1:2048 gives 42. From the rules of lookup table #2
+ *      as mapped above:
+ *
+ *                 rules
+ *               0   1
+ *      map to: 66  42
+ *
+ *
+ * == 4. Matching
+ *
+ * (4.1) We use a result bitmap, with the size of a single lookup table bucket,
+ * to represent the matching state that applies at every algorithm step.
+ *
+ * - For each packet field:
+ *
+ *   (4.2) start with an all-ones result bitmap
+ *
+ *   (4.3) perform a lookup into the table corresponding to the current field,
+ *   for each group, and at every group, AND the current result bitmap with the
+ *   value from the lookup table bucket
+ *
+ *      Example: 192.168.1.5 < 12 0  10 8  0 1  0 5 >, with lookup table from
+ *      pre-computation example.
+ *      Lookup table buckets are at least 3 bits wide, we'll arbitrarily assume
+ *      they are 8 bits for convenience. Initial result bitmap is 0xff, the
+ *      steps below show the value of the result bitmap after each group is
+ *      processed:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0    0                                              1,2
+ *
+ *        result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6
+ *
+ *        1   1,2                                      0
+ *
+ *        result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6
+ *
+ *        2    0                                      1,2
+ *
+ *        result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6
+ *
+ *        3    0                              1,2
+ *
+ *        result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6
+ *
+ *        4  0,1,2
+ *
+ *        result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6
+ *
+ *        5    0   1   2
+ *
+ *        result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2
+ *
+ *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *
+ *        result bitmap is now: 0x2 & 0x7 [bucket 0] = 0x2
+ *
+ *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
+ *
+ *        final result bitmap for this field is: 0x2 & 0x3 [bucket 5] = 0x2
+ *
+ *   (4.4) at the next field, start with a new, all-zeroes result bitmap. For
+ *   each bit set in the previous result bitmap, OR the new result bitmap with
+ *   the corresponding value from the mapping table for this field
+ *
+ *      Example: with mapping table from pre-computation example, current result
+ *      bitmap 0x02:
+ *
+ *                 rules
+ *               0   1   2
+ *      map to:  0   1   1
+ *
+ *      new result bitmap is 0x00 | 0x02 [bit/rule 1 was set] = 0x02
+ *
+ *      we can now extend this example to cover the second iteration of the step
+ *      above (lookup and AND bitmap): assuming the port field is
+ *      2048 < 0  0  5  0 >, with starting result bitmap 0x2, and lookup table
+ *      for "port" field from pre-computation example:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0   0,1
+ *        1   0,1
+ *        2                    0   1
+ *        3   0,1
+ *
+ *       operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
+ *       & 0x3 [bucket 0], resulting bitmap is 0x2.
+ *
+ *   (4.5) if this is the last field in the set, look up the value from the
+ *   verdict table corresponding to the final result bitmap
+ *
+ *      Example: 0x2 resulting bitmap from 192.168.1.5:2048, verdict table from
+ *      pre-computation example:
+ *
+ *                 rules
+ *               0   1
+ *      map to: 66  42
+ *
+ *      the verdict is 42.
+ *
+ *
+ * == 5. Ideas for Future Optimisations
+ *
+ * (5.1) Reduction of number of rules by allowing inverted netmasks
+ *
+ * CAVEAT: This needs some complicated tracking for inverted entries, which
+ * aren't implemented here at all. In order to further halve the number of
+ * rules as described below, we also need to use sets of netmasks, instead of a
+ * single netmask for each entry, and intersect between them and their
+ * inversions. This also introduces further complexity.
+ * 
+ * Theorem 3 in [Rottenstreich 2010] shows that every range of b bits can be
+ * converted into b bitmaps, with inversions, as also illustrated by section 9
+ * in [Kogan 2014].
+ *
+ * Further, if we allow partial subtractions between netmasks, for each range R
+ * of b bits, that can be converted into a b0 number of bitmaps, there exists a
+ * complementary range, R1, that can be converted into a b1 number of bitmaps,
+ * such that b1 + b0 = b.
+ *
+ * [TODO: Formal proof. This consideration is intuitively true and was validated
+ * by bruteforcing over the IPv4 address space, so we can safely use it in the
+ * implementation for the moment.]
+ *
+ * By construction, this allows us to express any range of b bits as ceil(b / 2)
+ * entries, either as reversed or direct entries. By allowing reversed entries,
+ * we need to also provide a reverse mapping possibility, which is achieved by
+ * modifying the mapping table from pre-computation step 4.5, and the step
+ * itself, as follows:
+ * - every bit corresponding to a reverse rule is set in the initial result
+ *   bitmap, which is not necessarily an all-zeroes bitmap anymore
+ * - the transformation step becomes a XOR operation: the XOR step with the
+ *   modified initial bitmap reverses the result, if we guarantee that one
+ *   single XOR step is performed. This comes, in turn, from optimisation 5.2
+ *
+ *   Example: match on 0.0.0.1-127.255.255.255:1024 and on 192.168.1.1:1024.
+ *   A direct mapping means we need 31 rules for the first address range, using
+ *   reversed rules we only need 2 rules instead (rule #0: 0.0.0.0/32,
+ *   rule #1: 128.0.0.0/1). Rule #2: 192.168.1.1/32.
+ *   First lookup table:
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0    0                               1   1   1   1  1,2  1   1   1
+ *        1  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        2   0,1  1   1   1   1   1   1   1   1   1  1,2  1   1   1   1   1
+ *        3   0,1  1   1   1   1   1   1   1  1,2  1   1   1   1   1   1   1
+ *        4  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        5   0,1 1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        7   0,1 1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *
+ *   Second lookup table: rule #0: 1024 for first entry, rule #1: 1024 for
+ *                        second entry
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0   0,1
+ *        1                   0,1
+ *        2   0,1
+ *        3   0,1
+ *
+ *    mapping table: initial bitmap is 0x1 (entry with rule #0 in second table
+ *                   is reversed in first table: set bit #0)
+ *                 rules
+ *                  0   1   2
+ *      XOR with: 0x1 0x1 0x2
+ *
+ * - expansion to reverse rules is selected if the number of reversed rules is
+ *   strictly less than the number of needed direct rules.
+ *
+ * (5.2) Single step for match and fill from result bitmap
+ *
+ * CAVEAT: This significantly affects complexity of listing and deletion,
+ * because once rules are replaced, further steps are needed to rebuild the
+ * originating entries.
+ * 
+ * Step 4.4 loops over all bits set in the current result bitmap: this is
+ * needed as set entries might overlap, for one or more fields. The
+ * computational complexity of mapping steps is O(m * log(n)), with m > 1
+ * overlapping factor, because we have no tight bounds on the number of
+ * overlapping entries. However, we can apply a reduction step on lookup tables,
+ * and ensure a single bit is set in the result bitmap after each lookup table
+ * is considered, with three observations:
+ *
+ * (5.2.1) In case two entries overlap entirely in a given lookup table, and
+ * their rules are present in the previous mapping table (or if it's the first
+ * lookup table), the entries can map to the same set of rules without loss of
+ * generality.
+ *
+ *   Example: given entries 192.168.1.0/24:1024 and 192.168.1.0/24:2048, first
+ *            lookup table initially has rules:
+ *              #0: 192.168.1.0/24
+ *              #1: 192.168.1.0/24
+ *            and second lookup table has rules:
+ *              #0: 1024
+ *              #1: 2048
+ *            with mapping table #0 -> #0 | #1 -> #1.
+ *            After this reduction step, the first lookup table has a single
+ *            rule (#0: 192.168.1.0/24), mapping to both rule #0 and #1.
+ *
+ *   Example: given entries 192.168.1.0/24:1024:10.0.0.1 and
+ *            192.168.2.0/24:1024:10.0.0.1, we don't apply any reduction step.
+ *            First lookup table has rules:
+ *              #0: 192.168.1.0/24
+ *              #1: 192.168.2.0/24
+ *            and second lookup table has rules:
+ *              #0: 1024
+ *              #1: 1024
+ *            with first mapping table #0 -> #0 | #1 -> #1. As there are no
+ *            images in the first lookup table with both rules #0 and #1 set,
+ *            these two rules will be preserved. Third lookup table has two
+ *            rules:
+ *              #0: 10.0.0.1/32
+ *              #1: 10.0.0.1/32
+ *            and second mapping table is: #0 -> #0 | #1 -> #1.
+ *
+ * (5.2.2) In case two entries overlap partially in a given lookup table, due to
+ * the way we expand ranges to netmasks, one set of rules is always a proper
+ * subset of the other overlapping one. That is, we can hit this situation:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0       x,y
+ *        1   x,y x,y  y   y
+ *
+ * but not:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0       x,y
+ *        1    x  x,y  y   y
+ *
+ * so in case entries corresponding to x map to a proper subset of the y rules,
+ * x rules never occur without y rules. We can then replace the x,y pairs by
+ * x, and merge their mapping tables.
+ *
+ *   Example: entries: 192.168.1.1-192.168.1.2:1
+ *              expands to: 192.168.1.1/32:1 (#0:#0), 192.168.1.2/32:1 (#1:#0)
+ *                     192.168.1.0-192.168.1.1:2
+ *              expands to: 192.168.1.0/31:2 (#2:#1)
+ *                     192.168.1.0-192.168.1.2:3
+ *              expands to: 192.168.1.0/31:3 (#3:#2), 192.168.1.2/32:3 (#4:#2)
+ *
+ *   First lookup table (only last group shown):
+ *                     bucket
+ *      group  0    1    2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *       ...
+ *        7   2,3 0,2,3 1,4
+ *
+ *   Second lookup table (only last group shown):
+ *                     bucket
+ *      group  0    1    2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *       ...
+ *        3         0    1   2
+ *
+ *   Initial mapping table: #0 -> #0 | #1 -> #0 | #2 -> #1 | #3 -> #2 | #4 -> #2
+ *
+ *   Apply reduction step from 5.2.1 twice to first lookup table: rule #1
+ *   entirely overlaps with #4, #2 entirely overlaps with #3. New lookup table:
+ *
+ *                     bucket
+ *      group  0    1    2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *       ...
+ *        7    2   0,2   1
+ *
+ *   New mapping table: #0 -> #0 | #1 -> #0, #2 | #2 -> #1, #2
+ *
+ *   Apply reduction step from 5.2.2: 0 never occurs without 2:
+ *
+ *                     bucket
+ *      group  0    1    2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *       ...
+ *        7    2    0    1
+ *
+ *   New mapping table: #0 -> #0, #1, #2 | #1 -> #0, #2 | #2 -> #1, #2
+ *
+ * (5.2.3) There are no other ways entries can overlap (directly from set
+ * theory)
+ * [TODO: Formal proof or reference.]
+ *
+ * (5.3) Single step for invert, match and bitmap fill operations (comes almost
+ * for free with 5.2 and 5.1).
+ *
+ * We can now replace the loop from 4.4 with a single XOR operation
+ * depending on the single bit set in the result bitmask after a lookup table is
+ * evaluated. Computational complexity of that step becomes, in theory, O(1):
+ * a single bit is set, hence lookup of the corresponding bitmap can be done in
+ * constant time. For all practical implementations, this is O(log(n)): the
+ * number of words in the mapping table grows linearly with the number of
+ * entries, but number of rules grows sublinearly and we can find the set bit
+ * with very efficient operations, too (e.g. x86's TZCNT, AVX-512 VPLZCNTQ,
+ * PPC's CNTLZ, etc.)]
+ *
+ * (5.4) [TODO: Evaluate if this provides an actual advantage even with an
+ * implementation of step 4.3 optionally based on AVX2 VPAND instrinsics.]
+ * As an alternative to finding the first bit set in the result bitmap for the
+ * mapping table lookup, we can terminate step 4.3 early, once we reach the last
+ * group of a table and a set bit is found in the result, and use the position
+ * of this bit directly for the mapping table lookup.
+ *
+ * (5.5) [TODO: Evaluate how bad this is on architectures where branching is
+ * expensive, e.g. PPC, find out if it makes sense to implement this optionally
+ * depending on architecture.]
+ * - We can terminate the algorithm early if the initial result bitmap, as we
+ *   start processing the next lookup table, is empty: that means that the
+ *   packet won't match any entry
+ * - We can terminate step 4.3 early if the result bitmap happens to be empty
+ *   after a group is entirely evaluated: this means the result bitmap will be
+ *   also empty at the beginning of step 4.4. We can't terminate the whole
+ *   algorithm in this case, though, as entries might be represented with an
+ *   inverted set of rules.
+ *
+ * (5.6) The mapping table described in step (3.5) grows in size linearly with
+ * the product of rules for the current field and rules for the next field. For
+ * entries with non-overlapping rules in a given field, this size would grow
+ * with the number of rules for this field, independently of the fact that these
+ * rules might map to the same set of rules in the next field.
+ *
+ *      Example: one entry, 192.168.1.0-192.168.2.1:2048
+ *
+ *      given lookup table #0 (see example above):
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0    0                                              1,2
+ *        1   1,2                                      0
+ *        2    0                                      1,2
+ *        3    0                              1,2
+ *        4  0,1,2
+ *        5    0   1   2
+ *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
+ *
+ *      and lookup table #1 with:
+ *      - rule #0: 1024 mapping to buckets
+ *        < 0  0  4  0 >
+ *      - rule #1: 2048 mapping to buckets
+ *        < 0  0  5  0 >
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0   0,1
+ *        1   0,1
+ *        2                    0   1
+ *        3   0,1
+ *
+ *      we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024
+ *      in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1
+ *      (rules #1, #2) to 2048 in lookup table #2 (rule #1):
+ *
+ *                 rules
+ *               0   1   2
+ *      map to:  0   1   1
+ *
+ *
+ * == 6. References
+ *
+ * [Ligatti 2010]
+ *	A Packet-classification Algorithm for Arbitrary Bitmask Rules, with
+ *	Automatic Time-space Tradeoffs
+ *	Jay Ligatti, Josh Kuhn, and Chris Gage.
+ *	Proceedings of the IEEE International Conference on Computer
+ *	Communication Networks (ICCCN), August 2010.
+ *	http://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf
+ *
+ * [Rottenstreich 2010]
+ *	Worst-Case TCAM Rule Expansion
+ *	Ori Rottenstreich and Isaac Keslassy.
+ *	2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010.
+ *	http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.4592&rep=rep1&type=pdf
+ *
+ * [Kogan 2014]
+ *	SAX-PAC (Scalable And eXpressive PAcket Classification)
+ *	Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane,
+ *	and Patrick Eugster.
+ *	Proceedings of the 2014 ACM conference on SIGCOMM, August 2014.
+ *	http://www.sigcomm.org/sites/default/files/ccr/papers/2014/August/2619239-2626294.pdf
+ */
+
+#ifndef VERBOSE
+#define PERF_TEST_BLOCK		100
+#endif
+
+#include <stdio.h>
+#include <arpa/inet.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <time.h>
+
+#include "pipapo.h"
+#include "set.h"
+#include "match.h"
+#include "util.h"
+
+/* Specifiers for set description: label, type, length, and offset in packet */
+struct desc_spec desc_specs[] = {
+	{ "key",	KEY,	0,		0 },
+	{ "dmac",	MAC,	MAC_LEN,	0 },
+	{ "smac",	MAC,	MAC_LEN,	6 },
+	{ "saddr",	ADDR,	ADDR_LEN,	26 },
+	{ "daddr",	ADDR,	ADDR_LEN,	30 },
+	{ "sport",	PORT,	PORT_LEN,	34 },
+	{ "dport",	PORT,	PORT_LEN,	36 },
+	{ "saddr6",	ADDR6,	ADDR6_LEN,	22 },
+	{ "daddr6",	ADDR6,	ADDR6_LEN,	38 },
+	{ "sport6",	PORT,	PORT_LEN,	54 },
+	{ "dport6",	PORT,	PORT_LEN,	56 },
+	{ NULL,		0,	0,		0 },
+};
+
+/**
+ * desc_parse_spec() - Parse set layout from tokens on first line of set file
+ * @d:		Pre-allocated set description to fill in
+ * @n:		Number of field tokens
+ * @tokens:	Labels of fields in desired set layout
+ *
+ * Return: 0 on success, negative error code on failure
+ */
+int desc_parse_spec(struct desc *d, int n, char (*tokens)[BUFSIZ])
+{
+	struct desc_spec *spec;
+	int i;
+
+	d->row_size = sizeof(enum set_ops);
+
+	for (i = 0; i < n; i++) {
+		for (spec = desc_specs; spec->label; spec++) {
+			if (!strncmp(tokens[i], spec->label, BUFSIZ))
+				break;
+		}
+
+		if (!spec->label) {
+			fprintf(stderr, "Invalid set specifier token %s\n",
+				tokens[i]);
+			return -EINVAL;
+		}
+
+		d->layout[i] = spec;
+
+		if (spec->type == KEY) {
+			d->row_size += sizeof(uint32_t);
+			continue;
+		}
+
+		d->fields++;
+		if (spec->type == ADDR)
+			d->row_size += sizeof(struct addr);
+		else if (spec->type == ADDR6)
+			d->row_size += sizeof(struct addr6);
+		else if (spec->type == PORT)
+			d->row_size += sizeof(struct port);
+		else if (spec->type == MAC)
+			d->row_size += sizeof(struct mac);
+	}
+
+	return 0;
+}
+
+/**
+ * desc_parse_entry() - Parse set entries from set file
+ * @d:		Pre-allocated set description, d->data to be filled
+ * @at:		Starting position in d->data to be filled with next set entry
+ * @n:		Number of fields
+ * @tokens:	Set items: addresses, ports, ranges thereof
+ *
+ * Return: 0 on success, negative error code on failure
+ */
+int desc_parse_entry(struct desc *d, int at, int n, char (*tokens)[BUFSIZ])
+{
+	int i, base = at * d->row_size, offset, b;
+	struct addr6 a6;
+	struct addr a;
+	struct port p;
+	char *c, *end;
+	struct mac m;
+	uint32_t key;
+	uint8_t v[6];
+
+	if (!strncmp(tokens[0], "list", strlen(tokens[0]))) {
+		*(enum set_ops *)(d->data + base) = LIST;
+		return 0;
+	}
+
+	if (!strncmp(tokens[0], "add", strlen(tokens[0])))
+		*(enum set_ops *)(d->data + base) = ADD;
+	else if (!strncmp(tokens[0], "delete", strlen(tokens[0])))
+		*(enum set_ops *)(d->data + base) = DEL;
+	else
+		return -EINVAL;
+	offset = sizeof(enum set_ops);
+	tokens++;
+	n--;
+
+	for (i = 0; i < n; i++) {
+		switch (d->layout[i]->type) {
+		case KEY:
+			key = strtoul(tokens[i], &end, 10);
+			if (*end)
+				return -EINVAL;
+
+			memcpy(d->data + base + offset, &key, sizeof(key));
+			offset += sizeof(key);
+			break;
+		case ADDR:
+			/* IPv4... */
+			if ((c = strchr(tokens[i], '-'))) {
+				/* range */
+				if (!inet_aton(c + 1, (struct in_addr *)&a.end))
+					return -EINVAL;
+				a.cidr = 0;
+				*c = 0;
+			} else if ((c = strchr(tokens[i], '/'))) {
+				/* netmask */
+				*c = 0;
+				a.cidr = strtoul(c + 1, &end, 10);
+				if (*end)
+					return -EINVAL;
+			} else {
+				/* address */
+				a.cidr = 32;
+			}
+
+			if (!inet_aton(tokens[i], (struct in_addr *)&a.start))
+				return -EINVAL;
+
+			memcpy(d->data + base + offset, &a, sizeof(a));
+			offset += sizeof(a);
+			break;
+		case ADDR6:
+			/* IPv6... */
+			if ((c = strchr(tokens[i], '-'))) {
+				/* range */
+				if (!inet_pton(AF_INET6, c + 1, &a6.end))
+					return -EINVAL;
+				a6.cidr = 0;
+				*c = 0;
+			} else if ((c = strchr(tokens[i], '/'))) {
+				/* netmask */
+				*c = 0;
+				a6.cidr = strtoul(c + 1, &end, 10);
+				if (*end)
+					return -EINVAL;
+			} else {
+				/* address */
+				a6.cidr = 128;
+			}
+
+			if (!inet_pton(AF_INET6, tokens[i], &a6.start))
+				return -EINVAL;
+
+			memcpy(d->data + base + offset, &a6, sizeof(a6));
+			offset += sizeof(a6);
+			break;
+		case PORT:
+			if ((c = strchr(tokens[i], '-'))) {
+				*c = 0;
+				p.end = htons(strtoul(c + 1, &end, 10));
+				if (*end)
+					return -EINVAL;
+			} else {
+				p.end = 0;
+			}
+
+			p.start = htons(strtoul(tokens[i], &end, 10));
+			if (*end)
+				return -EINVAL;
+
+			memcpy(d->data + base + offset, &p, sizeof(p));
+			offset += sizeof(p);
+			break;
+		case MAC:
+			if ((c = strchr(tokens[i], '-')))
+				*c = 0;
+
+			b = sscanf(tokens[i],
+				   "%hhx:%hhx:%hhx:%hhx:%hhx:%hhx%*c",
+				   v + 0, v + 1, v + 2, v + 3, v + 4, v + 5);
+			if (b != 6)
+				return -EINVAL;
+			memcpy(&m.start, v, 6);
+
+			if (c) {
+				b = sscanf(c + 1,
+					   "%hhx:%hhx:%hhx:%hhx:%hhx:%hhx%*c",
+					   v + 0, v + 1, v + 2,
+					   v + 3, v + 4, v + 5);
+				if (b != 6)
+					return -EINVAL;
+				memcpy(&m.end, v, 6);
+			} else {
+				memset(&m.end, 0, 6);
+			}
+
+			memcpy(d->data + base + offset, &m, sizeof(m));
+			offset += sizeof(m);
+			break;
+		}
+	}
+
+	return 0;
+}
+
+/**
+ * usage() - Display usage and exit
+ * @argv0:	Executable name
+ */
+void usage(const char *argv0)
+{
+	fprintf(stderr, "%s <ruleset> <packets>\n", argv0);
+	exit(1);
+}
+
+/**
+ * packet_parse() - Parse packets and expected key from path into binary format
+ * @path:	Path to packet file
+ * @ret:	Pointer to packet buffer, incremented by this function
+ *
+ * Return: 0 on success, negative error code on failure
+ */
+static int packet_parse(const char *path, uint8_t **ret)
+{
+	int alloc, n, byte_count, packet_count = 0, err;
+	uint8_t *packets, *pos, *tmp;
+	char buf[BUFSIZ], *end;
+	char *p;
+	FILE *f;
+
+	alloc = BUFSIZ;
+	pos = packets = malloc(alloc * (sizeof(uint32_t) + PACKET_SIZE));
+	if (!packets)
+		return -ENOMEM;
+
+	f = fopen(path, "r");
+	if (!f) {
+		err = -errno;
+		goto fail;
+	}
+
+	while (fgets(buf, BUFSIZ, f)) {
+		if (!*buf || *buf == '#' || *buf == ' ' || *buf == '\n')
+			continue;
+
+		if (++packet_count > alloc) {
+			alloc += BUFSIZ;
+			tmp = realloc(packets,
+				      alloc * (sizeof(uint32_t) + PACKET_SIZE));
+			if (!tmp) {
+				err = -ENOMEM;
+				goto fail_close;
+			}
+			packets = tmp;
+			pos = packets;
+			pos += (packet_count - 1) *
+			       (sizeof(uint32_t) + PACKET_SIZE);
+		}
+
+		/* Key */
+		p = strtok(buf, " \t");
+		n = strtoul(p, &end, 0);
+		if (*end) {
+			err = -EINVAL;
+			goto fail_close;
+		}
+		*(uint32_t *)pos = n;
+		pos += sizeof(uint32_t);
+
+		/* Packet bytes */
+		byte_count = 0;
+		while ((p = strtok(NULL, " \t\n"))) {
+			n = strtoul(p, &end, 0);
+			if (*end) {
+				err = -EINVAL;
+				goto fail_close;
+			}
+			*pos = n;
+			pos++;
+			if (++byte_count >= PACKET_SIZE)
+				break;
+		}
+		if (byte_count < PACKET_SIZE) {
+			memset(pos, 0, PACKET_SIZE - byte_count);
+			pos += PACKET_SIZE - byte_count;
+		}
+	}
+	fclose(f);
+
+	*ret = packets;
+	verbose("Read %i packets from %s\n", packet_count, path);
+
+	return packet_count;
+
+fail_close:
+	fclose(f);
+fail:
+	free(packets);
+	return err;
+}
+
+/**
+ * desc_parse() - Parse set file from path
+ * @path:	Path to set file
+ * @d:		Pre-allocated set, with description and data parts
+ *
+ * Return: 0 on success, negative error code on failure
+ */
+int desc_parse(const char *path, struct desc *d)
+{
+	int first = 1, err = 0, alloc = 0, n;
+	char t[9][BUFSIZ];
+	char buf[BUFSIZ];
+	uint8_t *tmp;
+	FILE *f;
+
+	f = fopen(path, "r");
+	if (!f)
+		return -errno;
+
+	while (fgets(buf, BUFSIZ, f)) {
+		n = sscanf(buf, "%s %s %s %s %s %s %s %s %s", t[0],
+			   t[1], t[2], t[3], t[4], t[5], t[6], t[7], t[8]);
+		if (!n || *t[0] == '#')
+			continue;
+
+		if (first) {
+			/* First line is the set type specifier */
+			err = desc_parse_spec(d, n, t);
+			if (err)
+				goto out;
+
+			first = 0;
+			continue;
+		}
+
+		if (d->entries == alloc) {
+			alloc += BUFSIZ;
+			tmp = realloc(d->data, alloc * d->row_size);
+			if (!tmp) {
+				err = -ENOMEM;
+				goto out;
+			}
+			d->data = tmp;
+		}
+
+		err = desc_parse_entry(d, d->entries++, n, t);
+	}
+
+out:
+	fclose(f);
+	return err;
+}
+
+/**
+ * main() - Entry point: parse set and packets, pre-compute, match
+ * @argc:	Argument count
+ * @argv:	Path to set description and packet files
+ *
+ * Return: 0 on success, 1 on matching failure, negative error code otherwise
+ */
+int main(int argc, char **argv)
+{
+	int packet_count, offset = 0, i, err;
+	uint8_t *packets, *ptr;
+	struct desc d = { 0 };
+	struct kernel_set *ks;
+	struct set s = { 0 };
+	uint32_t key;
+#ifdef VERBOSE
+	char *total_mem_suffix = "B";
+	int total_mem = 0;
+	struct field *f;
+#else
+	struct timespec tp_start, tp_end;
+	int repeat = 0, b = 0;
+	double time = 0;
+#endif
+	(void)key;
+
+	if (argc != 3)
+		usage(argv[0]);
+
+	verbose("=== Parsing\n");
+
+	if ((packet_count = packet_parse(argv[2], &packets)) < 0) {
+		fprintf(stderr, "Parsing failed, %s\n", strerror(packet_count));
+		exit(packet_count);
+	}
+
+	if ((err = desc_parse(argv[1], &d))) {
+		fprintf(stderr, "Parsing failed, %s\n", strerror(err));
+		return err;
+	}
+	verbose("\n");
+
+	verbose("=== Pre-computation\n");
+
+	if ((err = init(&s, d.layout))) {
+		fprintf(stderr, "Set init failed, %s\n", strerror(err));
+		return err;
+	}
+
+	for (i = 0; i < d.entries; i++) {
+		if (*(enum set_ops *)(d.data + offset) == ADD)
+			err = add(&s, d.layout,
+				  d.data + offset + sizeof(enum set_ops));
+		else if (*(enum set_ops *)(d.data + offset) == LIST)
+			list_or_del(&s, d.layout, NULL);
+		else if (*(enum set_ops *)(d.data + offset) == DEL)
+			err = list_or_del(&s, d.layout,
+					  d.data + offset +
+					  sizeof(enum set_ops));
+
+		if (err)
+			return err;
+		offset += d.row_size;
+	}
+
+	for (i = 0; d.layout[i]->type != KEY; i++) {
+		verbose("\n");
+		verbose("Lookup table for %s:\n", d.layout[i]->label);
+		show_lookup(&s.fields[i]);
+		verbose("Mapping table for %s:\n", d.layout[i]->label);
+		show_mapping(&s.fields[i], d.layout[i + 1]->type == KEY);
+	}
+	verbose("\n");
+
+	verbose("=== Match\n");
+
+	ks = kernel_init(&s, d.layout);
+
+#ifndef VERBOSE
+repeat_block:
+	repeat = PERF_TEST_BLOCK;
+	b++;
+	clock_gettime(CLOCK_MONOTONIC, &tp_start);
+	do {
+#endif
+		ptr = packets;
+		for (i = 0; i < packet_count; i++) {
+			key = match(ks, ptr + sizeof(uint32_t));
+#ifdef VERBOSE
+			verbose("Packet #%i => key: %u\n\n", i, key);
+			if (key != *(uint32_t *)ptr) {
+				verbose("FAIL: expected key: %u\n",
+					*(uint32_t *)ptr);
+				return 1;
+			}
+#endif
+			ptr += PACKET_SIZE + sizeof(uint32_t);
+		}
+#ifndef VERBOSE
+	} while (repeat--);
+	clock_gettime(CLOCK_MONOTONIC, &tp_end);
+	time += (tp_end.tv_sec - tp_start.tv_sec) +
+	        (tp_end.tv_nsec - tp_start.tv_nsec) / 1E9;
+	if (time < 5) {
+		goto repeat_block;
+	}
+
+	fprintf(stdout, "Matched %lfM packets in %lfs (%lf Mpps)\n",
+		PERF_TEST_BLOCK * b * packet_count / 1000.0 / 1000,
+		time,
+		PERF_TEST_BLOCK * b * packet_count / 1000.0 / 1000 / time);
+#endif
+
+#ifdef VERBOSE
+	verbose("\n");
+
+	verbose("\n=== Memory Usage\n");
+	for_each_field(f, &s, d.layout) {
+		char *lt_suffix = "B", *mt_suffix = "B", *field_suffix = "B";
+		int lt_size = f->groups * BUCKETS * f->bsize;
+		int mt_size = f->rules * sizeof(*f->mt);
+		int field_size;
+
+		total_mem += field_size = lt_size + mt_size + sizeof(*f);
+
+		if (lt_size > 20 * 1024) {
+			lt_size /= 1024;
+			lt_suffix = "KiB";
+		}
+
+		if (mt_size > 20 * 1024) {
+			mt_size /= 1024;
+			mt_suffix = "KiB";
+		}
+
+		if (field_size > 20 * 1024) {
+			field_size /= 1024;
+			field_suffix = "KiB";
+		}
+
+		verbose("Field %i, %s, %i rules:\n", i, d.layout[i]->label,
+			f->rules);
+		verbose("  lookup table: %i%s\n", lt_size, lt_suffix);
+		free(f->lt);
+		verbose("  mapping table: %i%s\n", mt_size, mt_suffix);
+		free(f->mt);
+		verbose("  total: %i%s\n", field_size, field_suffix);
+		verbose("\n");
+	}
+
+	if (total_mem > 50 * 1024 * 1024) {
+		total_mem /= 1024 * 1024;
+		total_mem_suffix = "MiB";
+	} else if (total_mem > 20 * 1024) {
+		total_mem /= 1024;
+		total_mem_suffix = "KiB";
+	}
+	verbose("Total: %i%s\n", total_mem, total_mem_suffix);
+#endif
+
+	/* Rest of allocated data is volatile */
+	free(s.fields);
+	free(d.data);
+	free(packets);
+	free(ks->map[0]);
+	free(ks->map[1]);
+	for (i = 0; i < 8; i++) {
+		free(ks->lt[i]);
+		free(ks->mt[i]);
+	}
+	free(ks);
+
+	return 0;
+}
diff --git a/pipapo.h b/pipapo.h
new file mode 100644
index 0000000..4d10ca8
--- /dev/null
+++ b/pipapo.h
@@ -0,0 +1,141 @@
+#define PACKET_SIZE	64
+#define GROUP_BITS	4
+#define BUCKETS		(1 << GROUP_BITS)
+#define MAX_FIELDS	8	/* E.g. mac,mac,addr,addr,port,port */
+
+#define ADDR_LEN	4
+#define ADDR6_LEN	16
+#define PORT_LEN	2
+#define MAC_LEN		6
+
+#ifdef __MATCH_AVX2
+#ifdef __AVX2__
+#define MATCH_AVX2
+#else
+#warning "AVX2 not supported, disabling"
+#endif
+#endif
+
+#ifdef __MATCH_CTZL
+#ifdef __GNUC__
+#define MATCH_CTZL
+#else
+#warning "__builtin_ctzl() not supported, disabling"
+#endif
+#endif
+
+/**
+ * enum desc_type - Types used in set description entries
+ * @KEY:	Verdict key for packets matching entry
+ * @ADDR:	IPv4 address
+ * @PORT:	Generic 16-bit port
+ * @ADDR6:	IPv6 address
+ * @MAC:	MAC address
+ */
+enum desc_type {
+	KEY,
+	ADDR,
+	PORT,
+	ADDR6,
+	MAC,
+};
+
+/**
+ * enum set_ops - Operations used in set files
+ * @ADD:	Add entry to set
+ * @LIST:	List current set entries
+ * @DEL:	Delete entry from set
+ */
+enum set_ops {
+	ADD,
+	LIST,
+	DEL,
+};
+
+/**
+ * struct desc_spec - Description of a single set specifier
+ * @label:	Field name
+ * @type:	Type of set field
+ * @len:	Length of packet field to be matched, in bytes
+ * @offset:	Field offset in packet, bytes
+ */
+struct desc_spec {
+	char *label;
+	enum desc_type type;
+	int len;
+	int offset;
+};
+
+/**
+ * struct desc - Description of a set
+ * @layout:	Layout as array of field specifiers
+ * @fields:	Number of fields
+ * @row_size:	Size of binary data for one entry (input to pre-computation)
+ * @entries:	Total number of set operations
+ * @data:	Binary data for pre-computation, concatenation of structs below
+ */
+struct desc {
+	struct desc_spec *layout[MAX_FIELDS];
+	int fields;
+	int row_size;
+	int entries;
+	uint8_t *data;
+};
+
+/**
+ * struct addr - Represent an IPv4 address, range or mask (in set description)
+ * @start:	Start of range, or address
+ * @end:	End of range, zero for single addresses or masks
+ * @cidr:	Mask length, 0 for ranges, 32 for single addresses
+ */
+struct addr {
+	uint32_t start;
+	uint32_t end;
+	uint8_t cidr;
+};
+
+/**
+ * struct addr6 - Represent an IPv6 address, range or mask (in set description)
+ * @start:	Start of range, or address
+ * @end:	End of range, zero for single addresses or masks
+ * @cidr:	Mask length, 0 for ranges, 128 for single addresses
+ */
+struct addr6 {
+	uint32_t start[4];
+	uint32_t end[4];
+	uint8_t cidr;
+};
+
+/**
+ * struct port - Represent a port or port range (in set description)
+ * @start:	Start of range, or single port number
+ * @end:	End of range, zero for single port
+ */
+struct port {
+	uint16_t start;
+	uint16_t end;
+};
+
+/**
+ * struct mac - Represent a MAC address or range (in set description)
+ * @start:	Start of range, or single MAC address
+ * @end:	End of range, zero for single MAC address
+ */
+struct mac {
+	uint8_t start[6];
+	uint8_t end[6];
+};
+
+/**
+ * union map_bucket - Bucket in mapping table (algorithm steps 3.5, 3.6)
+ * @to:		First rule number (in next field) this rule maps to
+ * @n:		Number of rules (in next field) this rule maps to
+ * @key:	If there's no next field, key this rule maps to
+ */
+union map_bucket {
+	struct {
+		uint32_t to:24;
+		uint32_t n:8;
+	};
+	uint32_t key;
+};
diff --git a/set.c b/set.c
new file mode 100644
index 0000000..6943b36
--- /dev/null
+++ b/set.c
@@ -0,0 +1,902 @@
+/* PIPAPO - PIle PAcket POlicies
+ *
+ * set.c - Insertion, listing, deletion
+ *
+ * Author: Stefano Brivio <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <arpa/inet.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "pipapo.h"
+#include "set.h"
+#include "util.h"
+
+/**
+ * struct rule_map - Internal convenience only: first number and amount of rules
+ * @x:		Number of first rule
+ * @n:		Rule count
+ */
+struct rule_map {
+	int x, n;
+};
+
+/**
+ * base_step_diff() - Check if setting 'step' bit in mask changes it
+ * @base:	Mask we are expanding
+ * @step:	Step bit for given expansion step
+ * @len:	Total length of mask space (set and unset bits), bytes
+ *
+ * Convenience function for mask expansion.
+ *
+ * Return: non-zero if given step bit changes mask base, 0 otherwise.
+ */
+static int base_step_diff(uint8_t *base, int step, int len)
+{
+	uint8_t tmp[16];
+
+	memcpy(tmp, base, len);
+	set_bit(tmp + len - 1 - step / 8, step % 8, len);
+
+	return memcmp(tmp, base, len);
+}
+
+/**
+ * base_step_after_end() - Check if mask reaches after range end with given step
+ * @base:	Mask we are expanding
+ * @end:	End of range
+ * @step:	Step bit for given expansion step
+ * @len:	Total length of mask space (set and unset bits), bytes
+ *
+ * Convenience function for mask expansion.
+ *
+ * Return: non-zero if mask exceeds range with step bit, 0 otherwise.
+ */
+static int base_step_after_end(uint8_t *base, uint8_t *end, int step, int len)
+{
+	uint8_t tmp[16];
+	int i;
+
+	memcpy(tmp, base, len);
+
+	for (i = 0; i <= step; i++)
+		set_bit(tmp + len - 1 - i / 8, i % 8, len);
+
+	return memcmp(tmp, end, len) > 0;
+}
+
+/**
+ * resize() - Resize lookup and mapping tables according to new number of rules
+ * @f:		Field containing lookup and mapping tables
+ * @old_rules:	Previous amount of rules in field
+ * @rules:	New amount of rules
+ *
+ * Increase, decrease or maintain tables size depending on new amount of rules,
+ * and copy data over. In case the new size is smaller, throw away data for
+ * highest-numbered rules.
+ *
+ * Return: 0 on success, -ENOMEM on allocation failure.
+ */
+static int resize(struct field *f, int old_rules, int rules)
+{
+	uint8_t *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
+	union map_bucket *new_mt, *old_mt = f->mt;
+	ssize_t new_bucket_size, copy;
+	int group, bucket;
+
+	new_bucket_size = DIV_ROUND_UP(rules, 8);
+#if defined(MATCH_AVX2) || defined(MATCH_CTZL)
+	new_bucket_size = round_up(new_bucket_size, 32);
+#endif
+
+	if (new_bucket_size == f->bsize)
+		goto mt;
+
+	if (new_bucket_size > f->bsize)
+		copy = f->bsize;
+	else
+		copy = new_bucket_size;
+
+	new_p = new_lt = calloc(new_bucket_size, f->groups * BUCKETS);
+	if (!new_lt)
+		return -ENOMEM;
+
+	old_p = old_lt;
+	for (group = 0; group < f->groups; group++) {
+		for (bucket = 0; bucket < BUCKETS; bucket++) {
+			memcpy(new_p, old_p, copy);
+			new_p += copy;
+			old_p += copy;
+
+			if (new_bucket_size > f->bsize)
+				new_p += new_bucket_size - f->bsize;
+			else
+				old_p += f->bsize - new_bucket_size;
+		}
+	}
+mt:
+	new_mt = calloc(rules, sizeof(*new_mt));
+	if (!new_mt) {
+		free(new_lt);
+		return -ENOMEM;
+	}
+
+	if (f->mt)
+		memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
+
+	f->bsize = new_bucket_size;
+
+	if (new_lt) {
+		f->lt = new_lt;
+		free(old_lt);
+	}
+
+	f->mt = new_mt;
+	free(old_mt);
+
+	return 0;
+}
+
+/**
+ * bucket_set_bit() - Set rule bit in lookup bucket according to group value
+ * @f:		Field containing lookup table
+ * @rule:	Rule bit number to be set
+ * @group:	Bit group in field
+ * @v:		Value of 4-bit group
+ */
+static void bucket_set_bit(struct field *f, int rule, int group, int v)
+{
+	uint8_t *pos;
+
+	pos = f->lt + f->bsize * BUCKETS * group;
+	pos += f->bsize * v;
+
+	set_bit(pos, rule, f->bsize);
+}
+
+/**
+ * insert() - Insert new rule in field given binary data and mask length
+ * @f:		Field containing lookup table
+ * @data:	Base value of classifying entry
+ * @mask_len:	Length of mask, matches field length for non-ranged entry
+ *
+ * Insert a new rule reference in lookup buckets corresponding to data and
+ * mask_len. This implements algorithm step 3.4.
+ *
+ * Return: 1 on success, negative error code on failure.
+ */
+static int insert(struct field *f, uint8_t *data, int mask_len)
+{
+	int rule = f->rules++, group, ret, i, v;
+	uint8_t mask;
+
+	ret = resize(f, f->rules - 1, f->rules);
+	if (ret)
+		return ret;
+
+	for (group = 0; group < f->groups; group++) {
+		if (group % 2)
+			v = data[group / 2] & 0x0f;
+		else
+			v = (data[group / 2] & 0xf0) >> 4;
+
+		if (mask_len >= (group + 1) * 4) {
+			/* Not masked */
+			bucket_set_bit(f, rule, group, v);
+		} else if (mask_len <= group * 4) {
+			/* Completely masked */
+			for (i = 0; i < (4 << 2); i++)
+				bucket_set_bit(f, rule, group, i);
+		} else {
+			/* The mask limit falls on this group */
+			mask = 0x0f >> (mask_len - group * 4);
+			for (i = 0; i < (4 << 2); i++) {
+				if ((i & ~mask) == (v & ~mask))
+					bucket_set_bit(f, rule, group, i);
+			}
+		}
+	}
+
+	return 1;
+}
+
+/**
+ * expand() - Expand range to composing netmasks and insert into lookup table
+ * @f:		Field containing lookup table
+ * @start:	Start of range
+ * @end:	End of range
+ * @mask_len:	Length of mask, matches field length for non-ranged entry TODO
+ *
+ * Expand range to composing netmasks and insert corresponding rule references
+ * in lookup buckets. This implements algorithm steps 3.3 - 3.4.
+ *
+ * Return: number of inserted rules on success, negative error code on failure.
+ */
+static int expand(struct field *f, uint8_t *start, uint8_t *end, int len)
+{
+	int step, masks = 0, err;
+	uint8_t base[16];
+
+	memcpy(base, start, len);
+	while (memcmp(base, end, len) <= 0) {
+		step = 0;
+		while (base_step_diff(base, step, len)) {
+			if (base_step_after_end(base, end, step, len))
+				break;
+			step++;
+
+			if (step >= len * 8)
+				goto out;
+		}
+
+		err = insert(f, base, len * 8 - step);
+		if (err < 0)
+			return err;
+
+		masks++;
+		bit_sum(base, step, len);
+	}
+
+out:
+	return masks;
+}
+
+/**
+ * map() - Insert references in mapping tables, mapping rules between fields
+ * @s:		Set data
+ * @layout:	Set layout
+ * @rmap:	Table of rule maps, arrays of first rule and amount of rules
+ *		in next field a given rule maps to, for each field
+ * @key:	Verdict key the inserted rules finally map to, in last field
+ *
+ * This implements algorithm steps 3.5 - 3.6.
+ */
+static void map(struct set *s, struct desc_spec **layout,
+		struct rule_map rmap[16], uint32_t key)
+{
+	struct field *f;
+	int i, j;
+
+	for (i = 0, f = s->fields; layout[i + 1]->type != KEY; i++, f++) {
+		for (j = 0; j < rmap[i].n; j++) {
+			f->mt[rmap[i].x + j].to = rmap[i + 1].x;
+			f->mt[rmap[i].x + j].n = rmap[i + 1].n;
+		}
+	}
+
+	for (j = 0; j < rmap[i].n; j++)
+		f->mt[rmap[i].x + j].key = key;
+}
+
+/**
+ * add() - Insert one entry in set data
+ * @s:		Set data
+ * @layout:	Set layout
+ * @data:	Concatenation of structs with parsed values for each field item
+ *
+ * This is the entry point for all algorithm steps in section 3.
+ */
+int add(struct set *s, struct desc_spec **layout, uint8_t *data)
+{
+	uint8_t zero_mac[MAC_LEN] = { 0 };
+	struct rule_map rmap[16] = { 0 };
+	char buf[BUFSIZ], buf2[BUFSIZ];
+	struct field *f;
+	struct addr6 *a6;
+	struct addr *a;
+	struct port *p;
+	struct mac *m;
+	int i, ret = 0;
+
+	(void)buf;
+	(void)buf2;
+
+	for_each_field(f, s, layout) {
+		/* See union map_bucket */
+		if (f->rules >= (1 << (24 - 1)) - 256)
+			return -ENOSPC;
+	}
+
+	verbose("Adding entry:\n");
+
+	for_each_field(f, s, layout) {
+		rmap[i].x = f->rules;
+
+		verbose("  inserting %s, ", layout[i]->label);
+
+		switch (layout[i]->type) {
+		case ADDR:
+			a = (struct addr *)data;
+
+			if (a->cidr == 0) {
+				verbose("start: %s, end: %s, ",
+					inet_ntop(AF_INET, &a->start, buf,
+						  BUFSIZ),
+					inet_ntop(AF_INET, &a->end, buf2,
+						  BUFSIZ));
+			} else if (a->cidr == 32) {
+				verbose("address: %s, ",
+					inet_ntop(AF_INET, &a->start, buf,
+						  BUFSIZ));
+			} else {
+				verbose("address: %s/%i, ",
+					inet_ntop(AF_INET, &a->start, buf,
+						  BUFSIZ),
+					a->cidr);
+			}
+
+			if (a->cidr)
+				ret = insert(f, (uint8_t *)&a->start, a->cidr);
+			else
+				ret = expand(f, (uint8_t *)&a->start,
+					     (uint8_t *)&a->end, ADDR_LEN);
+			if (ret < 0)
+				return ret;
+
+			data += sizeof(*a);
+			break;
+		case ADDR6:
+			a6 = (struct addr6 *)data;
+
+			if (a6->cidr == 0) {
+				verbose("start: %s, end: %s, ",
+					inet_ntop(AF_INET6, &a6->start, buf,
+						  BUFSIZ),
+					inet_ntop(AF_INET6, &a6->end, buf2,
+						  BUFSIZ));
+			} else if (a6->cidr == 128) {
+				verbose("address: %s, ",
+					inet_ntop(AF_INET6, &a6->start, buf,
+						  BUFSIZ));
+			} else {
+				verbose("address: %s/%i, ",
+					inet_ntop(AF_INET6, &a6->start, buf,
+						  BUFSIZ),
+					a6->cidr);
+			}
+
+			if (a6->cidr)
+				ret = insert(f, (uint8_t *)&a6->start,
+					     a6->cidr);
+			else
+				ret = expand(f, (uint8_t *)&a6->start,
+					     (uint8_t *)&a6->end, ADDR6_LEN);
+			if (ret < 0)
+				return ret;
+
+			data += sizeof(*a6);
+			break;
+		case PORT:
+			p = (struct port *)data;
+
+			if (p->end)
+				verbose("start: %i, end: %i, ",
+						ntohs(p->start), ntohs(p->end));
+			else
+				verbose("port: %i, ", ntohs(p->start));
+
+			if (p->end)
+				ret = expand(f, (uint8_t *)&p->start,
+					     (uint8_t *)&p->end, PORT_LEN);
+			else
+				ret = insert(f, (uint8_t *)&p->start,
+					     ADDR6_LEN * 8);
+			if (ret < 0)
+				return ret;
+
+			data += sizeof(*p);
+			break;
+		case MAC:
+			m = (struct mac *)data;
+
+			if (memcmp(&m->end, zero_mac, MAC_LEN))
+				verbose("start: %02x:%02x:%02x:%02x:%02x:%02x, "
+					"end: %02x:%02x:%02x:%02x:%02x:%02x, ",
+					m->start[0], m->start[1], m->start[2],
+					m->start[3], m->start[4], m->start[5],
+					m->end[0], m->end[1], m->end[2],
+					m->end[3], m->end[4], m->end[5]);
+			else
+				verbose("mac: %02x:%02x:%02x:%02x:%02x:%02x, ",
+					m->start[0], m->start[1], m->start[2],
+					m->start[3], m->start[4], m->start[5]);
+
+			if (memcmp(&m->end, zero_mac, MAC_LEN))
+				ret = expand(f, m->start, m->end, MAC_LEN);
+			else
+				ret = insert(f, m->start, MAC_LEN * 8);
+			if (ret < 0)
+				return ret;
+
+			data += sizeof(*m);
+			break;
+		case KEY:
+			break;
+		}
+
+		if (ret > 1)
+			verbose("rules %i-%i\n", rmap[i].x,
+				rmap[i].x + ret - 1);
+		else
+			verbose("rule %i\n", rmap[i].x);
+		rmap[i].n = ret;
+	}
+
+	map(s, layout, rmap, *(uint32_t *)data);
+
+	return 0;
+}
+
+/**
+ * rules_same_key() - Find amount of rules mapping to the same rules/key
+ * @f:		Field containing mapping table
+ * @start:	First rule to be checked against subsequent ones
+ *
+ * This is used to find out how many rules were created as part of the same set
+ * entry, for listing and deletion.
+ *
+ * Return: amount of rules mapping to the same rules or key given starting one
+ */
+static int rules_same_key(struct field *f, int start)
+{
+	uint32_t key;
+	int r;
+
+	for (r = start; r < f->rules; r++) {
+		if (r != start && key != f->mt[r].key)
+			return r - start;
+
+		key = f->mt[r].key;
+	}
+
+	if (r != start)
+		return r - start;
+
+	return 0;
+}
+
+/**
+ * aggregate() - Aggregate rules back to originating entries, print or match
+ * @f:		Field containing lookup and mapping tables
+ * @type:	Field type
+ * @start:	First rule for entry
+ * @len:	Amount of rules originated from same entry
+ * @match:	Optional (used for deletion), struct with field value
+ *
+ * This is used in listing, to print originating entries for rules found in
+ * lookup tables, and in deletion, to check a group of rules against the values
+ * we want to delete from a given set field.
+ *
+ * Return: 0 on match or if no match is requested, non-zero otherwise.
+ */
+static int aggregate(struct field *f, enum desc_type type, int start, int len,
+		     uint8_t *match)
+{
+	uint8_t left[16] = { 0 }, *l = left, right[16] = { 0 }, *r = right;
+	uint8_t zero_mac[MAC_LEN] = { 0 };
+	char buf_l[BUFSIZ], buf_r[BUFSIZ];
+	int g, b, x0, x1, mask_len = 0;
+	struct addr6 *a6;
+	struct addr *a;
+	struct port *p;
+	struct mac *m;
+
+	for (g = 0; g < f->groups; g++) {
+		x0 = x1 = -1;
+		for (b = 0; b < BUCKETS; b++) {
+			if (test_bit(f->lt + (g * BUCKETS + b) * f->bsize,
+				     start))
+				if (x0 == -1)
+					x0 = b;
+			if (test_bit(f->lt + (g * BUCKETS + b) * f->bsize,
+				     start + len - 1))
+				x1 = b;
+		}
+
+		if (g % 2) {
+			*(l++) |= x0 & 0x0f;
+			*(r++) |= x1 & 0x0f;
+		} else {
+			*l |= x0 << 4;
+			*r |= x1 << 4;
+		}
+
+		if (x1 - x0 == 0)
+			mask_len += 4;
+		else if (x1 - x0 == 1)
+			mask_len += 3;
+		else if (x1 - x0 == 3)
+			mask_len += 2;
+		else if (x1 - x0 == 7)
+			mask_len += 1;
+	}
+
+	l = left;
+	r = right;
+
+	switch (type) {
+	case ADDR:
+		if (match) {
+			a = (struct addr *)match;
+			if (!a->cidr)
+				return !memcmp(&a->start, l, ADDR_LEN) &&
+				       !memcmp(&a->end, r, ADDR_LEN);
+			return !memcmp(&a->start, l, ADDR_LEN) &&
+			       (a->cidr == mask_len);
+		}
+
+		inet_ntop(AF_INET, l, buf_l, BUFSIZ);
+		inet_ntop(AF_INET, r, buf_r, BUFSIZ);
+		if (mask_len == 32)
+			fprintf(stdout, "%s ", buf_l);
+		else if (len == 1)
+			fprintf(stdout, "%s/%i ", buf_l, mask_len);
+		else
+			fprintf(stdout, "%s-%s ", buf_l, buf_r);
+		break;
+	case ADDR6:
+		if (match) {
+			a6 = (struct addr6 *)match;
+			if (!a6->cidr)
+				return !memcmp(&a6->start, l, ADDR6_LEN) &&
+				       !memcmp(&a6->end, r, ADDR6_LEN);
+			return !memcmp(&a6->start, l, ADDR_LEN) &&
+			       (a6->cidr == mask_len);
+		}
+
+		inet_ntop(AF_INET6, l, buf_l, BUFSIZ);
+		inet_ntop(AF_INET6, r, buf_r, BUFSIZ);
+		if (mask_len == 128)
+			fprintf(stdout, "%s ", buf_l);
+		else if (len == 1)
+			fprintf(stdout, "%s/%i ", buf_l, mask_len);
+		else
+			fprintf(stdout, "%s-%s ", buf_l, buf_r);
+		break;
+	case PORT:
+		if (match) {
+			p = (struct port *)match;
+			return p->start == *(uint16_t *)l &&
+			       (!p->end || p->end == *(uint16_t *)r);
+		}
+
+		if (mask_len == 16 && len == 1)
+			fprintf(stdout, "%u ", ntohs(*(uint16_t *)l));
+		else
+			fprintf(stdout, "%u-%u ", ntohs(*(uint16_t *)l),
+				ntohs(*(uint16_t *)r));
+		break;
+	case MAC:
+		if (match) {
+			m = (struct mac *)match;
+			return !memcmp(&m->start, l, MAC_LEN) &&
+			       (memcmp(zero_mac, &m->end, MAC_LEN) ||
+			        !memcmp(&m->end, r, MAC_LEN));
+		}
+
+		if (mask_len == 48 && len == 1)
+			fprintf(stdout, "%02x:%02x:%02x:%02x:%02x:%02x ",
+				l[0], l[1], l[2], l[3], l[4], l[5]);
+		else
+			fprintf(stdout, "%02x:%02x:%02x:%02x:%02x:%02x-"
+				"%02x:%02x:%02x:%02x:%02x:%02x ",
+				l[0], l[1], l[2], l[3], l[4], l[5],
+				r[0], r[1], r[2], r[3], r[4], r[5]);
+		break;
+	default:
+		break;
+	}
+
+	return 0;
+}
+
+/**
+ * unmap() - Delete group of rules from mapping table, renumber remaining ones
+ * @mt:		Mapping table
+ * @rules:	Original amount of rules in mapping table
+ * @start:	First rule to be deleted
+ * @n:		Amount of rules originated from same entry
+ * @to_offset:	First rule index in next field this group of rules maps to
+ * @is_key:	If this is the last field, delete key from mapping table
+ *
+ * This is used to unmap rules from the mapping table for a single field,
+ * maintaining consistency and compactness for the existing ones. In pictures:
+ * let's assume that we want to delete rules 2 and 3 from the following mapping
+ * table:
+ *
+ *                 rules
+ *               0      1      2      3      4
+ *      map to:  4-10   4-10   11-15  11-15  16-18
+ *
+ * the result will be:
+ *
+ *                 rules
+ *               0      1      2
+ *      map to:  4-10   4-10   11-13
+ *
+ * for fields before the last one. In case this is the mapping table for the
+ * last field in a set, and its rules map to verdict keys:
+ *
+ *                 rules
+ *               0      1      2      3      4
+ *         key:  42     42     33     33     44
+ *
+ * the result will be:
+ *
+ *                 rules
+ *               0      1      2
+ *         key:  42     42     44
+ */
+void unmap(union map_bucket *mt, int rules, int start, int n, int to_offset,
+	   int is_key)
+{
+	int i;
+
+	memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
+	memset(mt + rules - n, 0, n * sizeof(*mt));
+
+	if (is_key)
+		return;
+
+	for (i = start; i < rules - n; i++)
+		mt[i].to -= to_offset;
+}
+
+/**
+ * drop() - Delete entry from lookup and mapping tables, given rule mapping
+ * @s:		Set data
+ * @layout:	Set layout
+ * @rmap:	Table of rule maps, arrays of first rule and amount of rules
+ *		in next field a given entry maps to, for each field
+ *
+ * For each rule in lookup table buckets mapping to this set of rules, drop
+ * all bits set in lookup table mapping. In pictures, assuming we want to drop
+ * rules 0 and 1 from this lookup table:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0    0                                              1,2
+ *        1   1,2                                      0
+ *        2    0                                      1,2
+ *        3    0                              1,2
+ *        4  0,1,2
+ *        5    0   1   2
+ *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
+ *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
+ *
+ * rule 2 becomes rule 0, and the result will be:
+ *
+ *                     bucket
+ *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+ *        0                                                    0
+ *        1    0
+ *        2                                            0
+ *        3                                    0
+ *        4    0
+ *        5            0
+ *        6    0
+ *        7    0   0
+ *
+ * once this is done, call unmap() to drop all the corresponding rule references
+ * from mapping tables.
+ */
+static void drop(struct set *s, struct desc_spec **layout,
+		 struct rule_map rmap[16])
+{
+	struct field *f;
+	int i, g, b;
+
+	for_each_field(f, s, layout) {
+		for (g = 0; g < f->groups; g++) {
+			for (b = 0; b < BUCKETS; b++)
+				fold_bits(f->lt + (g * BUCKETS + b) * f->bsize,
+					  rmap[i].x, rmap[i].n, f->bsize);
+		}
+		unmap(f->mt, f->rules, rmap[i].x, rmap[i].n, rmap[i + 1].n,
+		      layout[i + 1]->type == KEY);
+
+		resize(f, f->rules, f->rules - rmap[i].n);
+		f->rules -= rmap[i].n;
+	}
+}
+
+/**
+ * list_or_del() - List set entries, or delete entry if del_match is passed
+ * @s:		Set data
+ * @layout:	Set layout
+ * @del_match:	Optional, delete matching entry (concatenation of values)
+ *
+ * Return: 0 on listing and successful deletion, -ENOENT on match failure.
+ */
+int list_or_del(struct set *s, struct desc_spec **layout, uint8_t *del_match)
+{
+	int f0_rules, fx_rules, start, first_rule = 0, i, l, found;
+	struct rule_map rmap[16] = { 0 };
+	uint8_t *p = del_match;
+	struct field *f;
+
+	if (!del_match) {
+		fprintf(stdout, "List:");
+		for (l = 0; layout[l]->type != KEY; l++)
+			fprintf(stdout, " %s", layout[l]->label);
+		fprintf(stdout, "\n");
+	}
+
+	while ((f0_rules = rules_same_key(s->fields + 0, first_rule))) {
+		start = first_rule;
+		fx_rules = f0_rules;
+
+		p = del_match;
+		for (i = 0, f = s->fields; layout[i]->type != KEY; i++, f++) {
+			found = aggregate(f, layout[i]->type, start, fx_rules,
+					  p);
+
+			rmap[i].x = start;
+			rmap[i].n = fx_rules;
+
+			if (del_match) {
+				if (!found)
+					break;
+				if (layout[i]->type == ADDR)
+					p += sizeof(struct addr);
+				else if (layout[i]->type == ADDR6)
+					p += sizeof(struct addr6);
+				else if (layout[i]->type == PORT)
+					p += sizeof(struct port);
+				else if (layout[i]->type == MAC)
+					p += sizeof(struct mac);
+
+				if (layout[i + 1]->type == KEY &&
+				    *(uint32_t *)p == f->mt[start].key) {
+					drop(s, layout, rmap);
+					return 0;
+				}
+			}
+
+			if (layout[i + 1]->type == KEY) {
+				fprintf(stdout, "%u\n", f->mt[start].key);
+			} else {
+				fx_rules = f->mt[start].n;
+				start = f->mt[start].to;
+			}
+		}
+
+		first_rule += f0_rules;
+	}
+
+	if (del_match)
+		return -ENOENT;
+
+	return 0;
+}
+
+/**
+ * init() - Initialise set data
+ * @set:	Empty set, array of fields
+ * @layout:	Parsed set layout
+ *
+ * Return: 0 on success, -ENOMEM on allocation failure.
+ */
+int init(struct set *s, struct desc_spec **layout)
+{
+	struct field *f;
+	int i;
+
+	for (i = 0; layout[i]->type != KEY; i++);
+
+	s->fields = malloc(sizeof(struct field) * i);
+	if (!s->fields)
+		return -ENOMEM;
+
+	s->fields[i - 1].groups = 0;
+
+	for_each_field(f, s, layout) {
+		f->groups = layout[i]->len * 2;	/* 4-bit groups */
+		f->offset = layout[i]->offset;
+		f->bsize = 0;
+		f->rules = 0;
+		f->lt = NULL;
+		f->mt = NULL;
+	}
+
+	return 0;
+}
+
+#ifdef VERBOSE
+/**
+ * show_lookup() - Print lookup table for given field
+ * @field:	Field containing lookup table
+ *
+ * For documentation purposes only.
+ */
+void show_lookup(struct field *f)
+{
+	int bucket, group, in_group = 0, v;
+	uint8_t *copy, *p;
+
+	copy = malloc(f->groups * BUCKETS * f->bsize);
+	memcpy(copy, f->lt, f->groups * BUCKETS * f->bsize);
+
+	fprintf(stdout, "%20s\n", "bucket");
+	fprintf(stdout, "group    ");
+	for (bucket = 0; bucket < BUCKETS; bucket++)
+		fprintf(stdout, "%5i", bucket);
+	fprintf(stdout, "\n");
+
+	p = copy;
+	for (group = 0; group < f->groups; group++) {
+		if (in_group)
+			fprintf(stdout, "         ");
+		else
+			fprintf(stdout, "%3i      ", group);
+
+		in_group = 0;
+		for (bucket = 0; bucket < BUCKETS; bucket++) {
+			v = ffs_clear(p, f->bsize, 0);
+			if (v >= 0) {
+				in_group = 1;
+				fprintf(stdout, "%5i", v);
+			} else {
+				fprintf(stdout, "     ");
+			}
+			p += f->bsize;
+		}
+
+		if (in_group) {
+			p -= BUCKETS * f->bsize;
+			group--;
+		}
+		fprintf(stdout, "\n");
+	}
+
+	free(copy);
+}
+
+/**
+ * show_lookup() - Print mapping table for given field
+ * @field:	Field containing mapping table
+ * @to_key:	Last field: print verdict keys instead of mapping to next field
+ *
+ * For documentation purposes only.
+ */
+void show_mapping(struct field *f, int to_key)
+{
+	uint32_t prev_key;
+	int r, prev_r;
+
+	prev_key = f->mt[0].key;
+	prev_r = 0;
+	for (r = 1; r < f->rules + 1; r++) {
+		if (r < f->rules && f->mt[r].key == prev_key)
+			continue;
+
+		if (prev_r != r - 1)
+			fprintf(stdout, "( %i-%i => ", prev_r, r - 1);
+		else
+			fprintf(stdout, "( %i => ", r - 1);
+
+		if (to_key) {
+			fprintf(stdout, "%u ) ", prev_key);
+		} else {
+			if (f->mt[r - 1].n > 1) {
+				fprintf(stdout, "%i-%i ) ", f->mt[r - 1].to,
+					f->mt[r - 1].to + f->mt[r - 1].n - 1);
+			} else {
+				fprintf(stdout, "%i ) ", f->mt[r - 1].to);
+			}
+		}
+
+		if (r < f->rules) {
+			prev_key = f->mt[r].key;
+			prev_r = r;
+		}
+	}
+
+	fprintf(stdout, "\n");
+}
+#endif
diff --git a/set.h b/set.h
new file mode 100644
index 0000000..37845d3
--- /dev/null
+++ b/set.h
@@ -0,0 +1,43 @@
+/**
+ * struct field - Pre-computed field data
+ * @offset:	Offset in packet header, bytes
+ * @groups:	Number of 4-bit groups
+ * @rules:	Number of inserted rules
+ * @bsize:	Lookup table bucket size, bytes
+ * @lt:		Lookup table
+ * @mt:		Mapping table (n:m rules in next field)
+ */
+struct field {
+	int offset;
+	int groups;
+	int rules;
+
+	int bsize;
+	uint8_t *lt;
+	union map_bucket *mt;
+};
+
+/**
+ * struct set - Array of sets
+ * @fields:	Composing fields
+ */
+struct set {
+	struct field *fields;
+};
+
+#define for_each_field(f, s, layout)					\
+	for ((i) = 0, (f) = (s)->fields;				\
+	     (layout)[(i)]->type != KEY;				\
+	     i++, f++)
+
+int init(struct set *s, struct desc_spec **layout);
+int add(struct set *s, struct desc_spec **layout, uint8_t *data);
+int list_or_del(struct set *s, struct desc_spec **layout, uint8_t *match);
+
+#ifdef VERBOSE
+void show_lookup(struct field *f);
+void show_mapping(struct field *f, int to_key);
+#else
+#define show_lookup(...) do { } while (0)
+#define show_mapping(...) do { } while (0)
+#endif
diff --git a/tests/gen.sh b/tests/gen.sh
new file mode 100755
index 0000000..05b3b51
--- /dev/null
+++ b/tests/gen.sh
@@ -0,0 +1,214 @@
+#!/bin/sh -e
+#
+# PIPAPO - PIle PAcket POlicies
+#
+# tests/gen.sh - Generate test sets and packets
+#
+# Author: Stefano Brivio <sbrivio@redhat.com>
+# License: GPLv2
+
+rand() {
+	shuf -i ${1}-${2} -n 1
+}
+
+port() {
+	if [ "${size}" = "single" ]; then
+		p1=$(rand 0 65535)
+		p2=$((p1 / 2 + 1))
+
+		printf "dport key\na ${p1} 1\n" > port.single
+		printf "1  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0     0   0   0   0     0  0   %i %i\n" $((p1 / 256)) $((p1 % 256)) > port.single.packets
+		printf "0  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0     0   0   0   0     0  0   %i %i\n" $((p2 / 256)) $((p2 % 256)) >> port.single.packets
+		return
+	fi
+
+	case ${size} in
+	tiny)	n=100 ;;
+	small)	n=1000 ;;
+	mid)	n=10000 ;;
+	big)	n=100000 ;;
+	huge)	n=200000 ;;
+	esac
+
+	:> port.${size}.packets
+	printf "dport key\n" > port.${size}
+	p=$(rand 0 10)
+	mul=$(rand 1 2)
+	inc=$(rand 1 50)
+	nopkt=0
+	for i in $(seq 1 ${n}); do
+		p=$((p * mul + inc))
+		if [ ${p} -ge 65536 ]; then
+			nopkt=1
+			p=$((p % 65536))
+		fi
+		if [ ${nopkt} -eq 0 ]; then
+			printf "%i  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0     0   0   0   0     0  0   %i %i\n" ${i} $((p / 256)) $((p % 256)) >> port.${size}.packets
+		fi
+		printf "a %i %i\n" ${p} ${i} >> port.${size}
+	done
+}
+
+net_port() {
+	if [ "${size}" = "single" ]; then
+		p1=$(rand 0 65535)
+		p2=$((p1 / 2 + 1))
+
+		printf "daddr dport key\na 10.$((p1 / 256)).$((p1 % 256)).5 ${p1} 1\n" > net_port.single
+		printf "1  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0    10  %i  %i   5   0  0   %i %i\n" $((p1 / 256)) $((p1 % 256)) $((p1 / 256)) $((p1 % 256)) > net_port.single.packets
+		printf "0  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0     0   0   0   0   0  0   %i %i\n" $((p2 / 256)) $((p2 % 256)) >> net_port.single.packets
+		return
+	fi
+
+	case ${size} in
+	tiny)	n=10 ;;
+	small)	n=100 ;;
+	mid)	n=316 ;;
+	big)	n=1000 ;;
+	huge)	n=10000 ;;
+	esac
+
+	:> net_port.${size}.packets
+	printf "daddr dport key\n" > net_port.${size}
+	a=$(rand 0 10)
+	p=$(rand 0 10)
+	inc=$(rand 1 50)
+	nopkt=0
+	for i in $(seq 1 ${n}); do
+		mul=$(rand 1 5)
+		a=$((a + inc * mul))
+		if [ ${a} -lt 4294967296 ]; then
+			a=$((a % 4294967296))
+		else
+			nopkt=1
+		fi
+
+		a1=$((a / 16777216))
+		a2=$(((a / 65536) % 256))
+		a3=$(((a / 256) % 256))
+		a4=$((a % 256))
+
+		p=$(((p * mul + inc) % 65536))
+		p1=$((p / 256))
+		p2=$((p % 256))
+
+		if [ ${nopkt} -eq 0 ]; then
+			printf "%i  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0    %i  %i  %i  %i     0  0   %i %i\n" ${i} ${a1} ${a2} ${a3} ${a4} ${p1} ${p2} >> net_port.${size}.packets
+		fi
+		printf "a %i.%i.%i.%i %i %i\n" ${a1} ${a2} ${a3} ${a4} ${p} ${i} >> net_port.${size}
+	done
+}
+
+net_port_ranged() {
+	if [ "${size}" = "single" ]; then
+		p1=$(rand 0 65535)
+		p2=$((p1 / 2 + 1))
+
+		printf "daddr dport key\na 10.$((p1 / 256)).0.$((p1 % 256))-10.$((p1 / 256)).$((p1 / 256)).$((p1 / 256)) ${p1} 1\n" > net_port_ranged.single
+		printf "1  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0    10  %i   0  %i   0  0   %i %i\n" $((p1 / 256)) $((p1 % 256)) $((p1 / 256)) $((p1 % 256)) > net_port_ranged.single.packets
+		printf "0  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0     0   0   0   0   0  0   %i %i\n" $((p2 / 256)) $((p2 % 256)) >> net_port_ranged.single.packets
+		return
+	fi
+
+	case ${size} in
+	tiny)	n=10 ;;
+	small)	n=100 ;;
+	mid)	n=316 ;;
+	big)	n=1000 ;;
+	huge)	n=10000 ;;
+	esac
+
+	:> net_port_ranged.${size}.packets
+	printf "daddr dport key\n" > net_port_ranged.${size}
+	a=$(rand 0 10)
+	p=$(rand 0 10)
+	inc=$(rand 1 50)
+	nopkt=0
+	for i in $(seq 1 ${n}); do
+		mul=$(rand 2 5)
+		a=$((a + inc * mul))
+		if [ ${a} -lt 4094967296 ]; then
+			a=$((a % 4094967296))
+		else
+			nopkt=1
+		fi
+
+		end=$((a + inc))
+
+		s1=$((a / 16777216))
+		s2=$(((a / 65536) % 256))
+		s3=$(((a / 256) % 256))
+		s4=$((a % 256))
+
+		e1=$((end / 16777216))
+		e2=$(((end / 65536) % 256))
+		e3=$(((end / 256) % 256))
+		e4=$((end % 256))
+
+		p=$(((p * mul + inc) % 60536))
+		p1=$((p / 256))
+		p2=$((p % 256))
+
+		if [ ${nopkt} -eq 0 ] && [ ${s4} -ne ${e4} ]; then
+			printf "%i  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0    %i  %i  %i  %i     0  0   %i %i\n" ${i} ${s1} ${s2} ${s3} ${s4} ${p1} ${p2} >> net_port_ranged.${size}.packets
+			printf "%i  0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0  64  0 1 2 3  0 0  1  0 0     0   0   0   0    %i  %i  %i  %i     0  0   %i %i\n" ${i} ${e1} ${e2} ${e3} ${e4} ${p1} ${p2} >> net_port_ranged.${size}.packets
+		fi
+		printf "a %i.%i.%i.%i-%i.%i.%i.%i %i-%i %i\n" ${s1} ${s2} ${s3} ${s4} ${e1} ${e2} ${e3} ${e4} ${p} $((p + inc)) ${i} >> net_port_ranged.${size}
+	done
+}
+
+mac_net6_ranged() {
+	case ${size} in
+	single)	n=1 ;;
+	tiny)	n=3 ;;
+	small)	n=10 ;;
+	mid)	n=31 ;;
+	big)	n=100 ;;
+	huge)	n=316 ;;
+	esac
+
+	:> mac_net6_ranged.${size}.packets
+	printf "dmac saddr6 key\n" > mac_net6_ranged.${size}
+	m=$(rand 0 10)
+	a=$(rand 0 10)
+	inc=$(rand 1 50)
+	nopkt=0
+	for i in $(seq 1 ${n}); do
+		mul=$(rand 2 5)
+
+		a=$((a + inc * mul))
+		end=$((a + inc))
+
+		sh=$((a / 65535))
+		sl=$((a % 65535))
+
+		eh=$((end / 65535))
+		el=$((end % 65535))
+
+		s1=$((sh / 256))
+		s2=$((sh % 256))
+		s3=$((sl / 256))
+		s4=$((sl % 256))
+
+		e1=$((eh / 256))
+		e2=$((eh % 256))
+		e3=$((el / 256))
+		e4=$((el % 256))
+
+		m=$(((m * mul + inc) % 60536))
+		m1=$((m / 256))
+		m2=$((m % 256))
+
+		printf "%i  0 0 0 0 %i %i  0 0 0 0 0 0  0x86 0xdd  0x60  0x00 0x00   0x00 0x00 0x00 0x00 0x00  0x20 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00  0x%02x 0x%02x 0x%02x 0x%02x\n" ${i} ${m1} ${m2} ${s1} ${s2} ${s3} ${s4} >> mac_net6_ranged.${size}.packets
+		printf "%i  0 0 0 0 %i %i  0 0 0 0 0 0  0x86 0xdd  0x60  0x00 0x00   0x00 0x00 0x00 0x00 0x00  0x20 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00  0x%02x 0x%02x 0x%02x 0x%02x\n" ${i} ${m1} ${m2} ${e1} ${e2} ${e3} ${e4} >> mac_net6_ranged.${size}.packets
+		printf "a 00:00:00:00:%02x:%02x-00:00:00:%02x:00:00 2001::%04x:%04x-2001::%04x:%04x %i\n" ${m1} ${m2} $((m1 + 1)) ${sh} ${sl} ${eh} ${el} ${i} >> mac_net6_ranged.${size}
+	done
+}
+
+for type in port net_port net_port_ranged mac_net6_ranged; do
+	for size in single tiny small mid big huge; do
+		printf "Generating ${type}.${size} test set..."
+		${type} ${size}
+		printf " done\n"
+	done
+done
diff --git a/tests/mac_mac_addr_addr_port_port.static b/tests/mac_mac_addr_addr_port_port.static
new file mode 100644
index 0000000..f578a1d
--- /dev/null
+++ b/tests/mac_mac_addr_addr_port_port.static
@@ -0,0 +1,204 @@
+# Equivalent of mac,mac,net,net,port,port
+dmac smac saddr daddr sport dport key
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 10.0.0.1-10.255.255.253 1.0.0.3-254.254.254.251 10-1000 1-60000 42
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-5000 22 43
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4000 22 4000
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4001 22 4001
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4002 22 4002
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4003 22 4003
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4004 22 4004
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4005 22 4005
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4006 22 4006
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4007 22 4007
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4008 22 4008
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4009 22 4009
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4010 22 4010
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4011 22 4011
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4012 22 4012
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4013 22 4013
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4014 22 4014
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4015 22 4015
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4016 22 4016
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4017 22 4017
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4018 22 4018
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4019 22 4019
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4020 22 4020
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4021 22 4021
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4022 22 4022
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4023 22 4023
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4024 22 4024
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4025 22 4025
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4026 22 4026
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4027 22 4027
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4028 22 4028
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4029 22 4029
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4030 22 4030
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4031 22 4031
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4032 22 4032
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4033 22 4033
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4034 22 4034
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4035 22 4035
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4036 22 4036
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4037 22 4037
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4038 22 4038
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4039 22 4039
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4040 22 4040
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4041 22 4041
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4042 22 4042
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4043 22 4043
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4044 22 4044
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4045 22 4045
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4046 22 4046
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4047 22 4047
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4048 22 4048
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4049 22 4049
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4050 22 4050
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4051 22 4051
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4052 22 4052
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4053 22 4053
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4054 22 4054
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4055 22 4055
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4056 22 4056
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4057 22 4057
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4058 22 4058
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4059 22 4059
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4060 22 4060
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4061 22 4061
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4062 22 4062
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4063 22 4063
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4064 22 4064
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4065 22 4065
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4066 22 4066
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4067 22 4067
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4068 22 4068
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4069 22 4069
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4070 22 4070
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4071 22 4071
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4072 22 4072
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4073 22 4073
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4074 22 4074
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4075 22 4075
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4076 22 4076
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4077 22 4077
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4078 22 4078
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4079 22 4079
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4080 22 4080
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4081 22 4081
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4082 22 4082
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4083 22 4083
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4084 22 4084
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4085 22 4085
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4086 22 4086
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4087 22 4087
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4088 22 4088
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4089 22 4089
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4090 22 4090
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4091 22 4091
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4092 22 4092
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4093 22 4093
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4094 22 4094
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4095 22 4095
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4096 22 4096
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4097 22 4097
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4098 22 4098
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4099 22 4099
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4100 22 4100
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4101 22 4101
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4102 22 4102
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4103 22 4103
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4104 22 4104
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4105 22 4105
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4106 22 4106
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4107 22 4107
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4108 22 4108
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4109 22 4109
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4110 22 4110
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4111 22 4111
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4112 22 4112
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4113 22 4113
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4114 22 4114
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4115 22 4115
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4116 22 4116
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4117 22 4117
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4118 22 4118
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4119 22 4119
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4120 22 4120
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4121 22 4121
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4122 22 4122
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4123 22 4123
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4124 22 4124
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4125 22 4125
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4126 22 4126
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4127 22 4127
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4128 22 4128
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4129 22 4129
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4130 22 4130
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4131 22 4131
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4132 22 4132
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4133 22 4133
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4134 22 4134
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4135 22 4135
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4136 22 4136
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4137 22 4137
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4138 22 4138
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4139 22 4139
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4140 22 4140
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4141 22 4141
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4142 22 4142
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4143 22 4143
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4144 22 4144
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4145 22 4145
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4146 22 4146
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4147 22 4147
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4148 22 4148
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4149 22 4149
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4150 22 4150
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4151 22 4151
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4152 22 4152
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4153 22 4153
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4154 22 4154
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4155 22 4155
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4156 22 4156
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4157 22 4157
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4158 22 4158
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4159 22 4159
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4160 22 4160
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4161 22 4161
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4162 22 4162
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4163 22 4163
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4164 22 4164
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4165 22 4165
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4166 22 4166
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4167 22 4167
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4168 22 4168
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4169 22 4169
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4170 22 4170
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4171 22 4171
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4172 22 4172
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4173 22 4173
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4174 22 4174
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4175 22 4175
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4176 22 4176
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4177 22 4177
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4178 22 4178
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4179 22 4179
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4180 22 4180
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4181 22 4181
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4182 22 4182
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4183 22 4183
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4184 22 4184
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4185 22 4185
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4186 22 4186
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4187 22 4187
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4188 22 4188
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4189 22 4189
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4190 22 4190
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4191 22 4191
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4192 22 4192
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4193 22 4193
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4194 22 4194
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4195 22 4195
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4196 22 4196
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4197 22 4197
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4198 22 4198
+a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4199 22 4199
diff --git a/tests/mac_mac_addr_addr_port_port.static.packets b/tests/mac_mac_addr_addr_port_port.static.packets
new file mode 100644
index 0000000..fac1061
--- /dev/null
+++ b/tests/mac_mac_addr_addr_port_port.static.packets
@@ -0,0 +1,7 @@
+# KEY BYTES, PACKET_SIZE bytes as decimal or hex will be read, the rest
+  discarded, packets are zero-padded if less than PACKET_SIZE. KEY is the
+  expected matching key from the ruleset, 0 if no match is expected
+# Key	MAC                                                            IPv4            DSCP  Length  ID       Flags  TTL  Checksum  Source            Destination          sport   dport
+42	0x00 0xb0 0xcc 0xac 0xc1 0x00  0x00 0xde 0xad 0xc0 0xff 0xfe   0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10    0 128 255     10   0   0   3     0 10    0  22
+0	0x00 0xb0 0xcc 0xac 0xc1 0x00  0x00 0xde 0xad 0xc0 0xff 0xfe   0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168   1   1     10   0   0   3     0 10    0  22
+43	0x00 0xb0 0xcc 0xac 0xc1 0x00  0x00 0xde 0xad 0xc0 0xff 0xfe   0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168   1   1    192 168   1   2     0 10    0  22
diff --git a/tests/net_port.static b/tests/net_port.static
new file mode 100644
index 0000000..9ab492c
--- /dev/null
+++ b/tests/net_port.static
@@ -0,0 +1,15 @@
+# Equivalent of net,port
+saddr dport key
+a 10.0.0.0-10.255.255.251 22 42
+a 192.168.1.1 1024 666
+a 10.0.0.0-10.0.0.10 80-82 8
+a 192.168.1.0/24 5000-6000 10
+a 8.8.8.0/24 222 66
+d 192.168.1.0/24 5000-6000 10
+a 192.168.1.0/24 5000-6000 10
+l
+d 8.8.8.0/24 222 66
+d 192.168.1.0/24 5000-6000 10
+a 192.168.1.0/24 5000-6000 10
+l
+
diff --git a/tests/net_port.static.packets b/tests/net_port.static.packets
new file mode 100644
index 0000000..bb983dd
--- /dev/null
+++ b/tests/net_port.static.packets
@@ -0,0 +1,15 @@
+# KEY BYTES, PACKET_SIZE bytes as decimal or hex will be read, the rest
+  discarded, packets are zero-padded if less than PACKET_SIZE. KEY is the
+  expected matching key from the ruleset, 0 if no match is expected
+# Key	MAC                       IPv4            DSCP  Length  ID       Flags  TTL  Checksum  Source             Destination       sport  dport
+42	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10  0   128 255    10  0   0   1     1 0    0  22
+42	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10  255 255 251    10  0   0   1     1 0    0  22
+42	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10  0   0   0      10  0   0   1     1 0    0  22
+0	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10  255 255 252    10  0   0   1     1 0    0  22
+0	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10  255 255 251    10  0   0   1     1 0    0  23
+666	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168 1   1      10  0   0   1     1 0    4  0
+0	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168 1   1      10  0   0   1     1 0    4  1
+8	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       10  0   0   5      10  0   0   1     1 0    0  81
+10	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168 1   2      10  0   0   1     1 0    19 136
+0	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168 2   2      10  0   0   1     1 0    19 136
+0	0 0 0 0 0 0  0 0 0 0 0 0  0x08 0x00 0x45  0     64      0 1 2 3  0 0    1    0 0       192 168 1   2      10  0   0   1     1 0    23 113
diff --git a/tests/plot.sh b/tests/plot.sh
new file mode 100755
index 0000000..7c4904e
--- /dev/null
+++ b/tests/plot.sh
@@ -0,0 +1,19 @@
+#!/bin/sh
+
+xmax=200000
+avx=plots/rate_port.data
+noavx=plots/rate_noavx2_port.data
+nosimd=plots/rate_nosimd_port.data
+out=plots/port.png
+
+gnuplot <<EOF
+	set terminal pngcairo size 600,400 enhanced font 'Lucida Sans,10' rounded
+	set logscale x
+	set xlabel "Entries for each field"
+	set ylabel "Mpps"
+	set title 'Single port'
+	set grid
+	set key right top
+	set output '${out}'
+	plot '${avx}' w l ls 1 t 'AVX2', '${noavx}' w l ls 2 t 'No AVX2', '${nosimd}' w l ls 3 t 'No SIMD'
+EOF
diff --git a/tests/run.sh b/tests/run.sh
new file mode 100755
index 0000000..2b32f2a
--- /dev/null
+++ b/tests/run.sh
@@ -0,0 +1,119 @@
+#!/bin/sh -e
+#
+# PIPAPO - PIle PAcket POlicies
+#
+# tests/run.sh - Run functional and performance tests, plot matching rates
+#
+# Author: Stefano Brivio <sbrivio@redhat.com>
+# License: GPLv2
+
+check() {
+	if ! ../pipapo.check ${type}.${size} ${type}.${size}.packets >/dev/null; then
+		echo "  functional test: FAIL at ${type}.${size} ${type}.${size}.packets"
+		exit 1
+	fi
+	echo "    functional test: PASS"
+}
+
+pps() {
+	s="$(wc -l ${type}.${size})"
+	s=${s% *}
+	if [ ${s} -gt 10 ]; then
+		s=$((s / 10))
+		s=$((s * 10))
+	fi
+
+	pps="$(../pipapo ${type}.${size} ${type}.${size}.packets | sed -nr 's/.* \((.*) Mpps\)$/\1/p')"
+	printf "%i %f\n" "${s}" "${pps}" >> plots/rate_${type}.data
+	echo "    matching rate (AVX2): ${pps} Mpps"
+
+	pps="$(../pipapo.noavx2 ${type}.${size} ${type}.${size}.packets | sed -nr 's/.* \((.*) Mpps\)$/\1/p')"
+	printf "%i %f\n" "${s}" "${pps}" >> plots/rate_noavx2_${type}.data
+	echo "    matching rate (no AVX2): ${pps} Mpps"
+
+	pps="$(../pipapo.nosimd ${type}.${size} ${type}.${size}.packets | sed -nr 's/.* \((.*) Mpps\)$/\1/p')"
+	printf "%i %f\n" "${s}" "${pps}" >> plots/rate_nosimd_${type}.data 
+	echo "    matching rate (no SIMD): ${pps} Mpps"
+}
+
+mem() {
+	s="$(wc -l ${type}.${size})"
+	s=${s% *}
+	if [ ${s} -gt 10 ]; then
+		s=$((s / 10))
+		s=$((s * 10))
+	fi
+
+	out="$(../pipapo.mem ${type}.${size} ${type}.${size}.packets | sed -nr 's/^Total: ([0-9].*)((KiB$|MiB$|B$))$/\1 \2/p')"
+	case ${out} in
+	*" KiB")
+		_out=$((${out%% *} * 1024))
+		;;
+	*" MiB")
+		_out=$((${out%% *} * 1024 * 1024))
+		;;
+	*" B")
+		_out=${out%% *}
+		;;
+	esac
+
+	printf "%i %i\n" "${s}" "${_out}" >> plots/memory_${type}.data
+
+	echo "    memory used: $(echo ${out} | tr -d ' ')"
+}
+
+[ -d plots ] || { ./gen.sh && mkdir -p plots; }
+
+plot() {
+	title="$(echo ${title} | tr '_' ', ')"
+	gnuplot <<EOF
+		set terminal pngcairo size 600,400 enhanced font 'Lucida Sans,10' rounded
+		set logscale x
+		set xlabel "Entries for each field"
+		set ylabel "Mpps"
+		set title '${title}'
+		set grid
+		set key right top
+		set output 'plots/${type}.png'
+		plot 'plots/rate_${type}.data' w l ls 1 t 'AVX2', 'plots/rate_noavx2_${type}.data' w l ls 2 t 'No AVX2', 'plots/rate_nosimd_${type}.data' w l ls 3 t 'No SIMD'
+EOF
+}
+
+for type in port net_port net_port_ranged mac_net6_ranged; do
+	echo "=== TEST: ${type}"
+	for size in single tiny small mid big huge; do
+		:> plots/rate_${type}.data
+		:> plots/rate_noavx2_${type}.data
+		:> plots/rate_nosimd_${type}.data
+		:> plots/memory_${type}.data
+	done
+
+	for size in single tiny small mid big huge; do
+		echo "  - size: ${size}"
+		check
+		pps
+		mem
+	done
+
+	plot
+
+	echo
+done
+
+for test in *.static; do
+	echo "=== TEST: ${test}"
+	type="${test%*.static}"
+	:> plots/rate_${type}.data
+	:> plots/rate_noavx2_${type}.data
+	:> plots/rate_nosimd_${type}.data
+	:> plots/memory_${type}.data
+	size="static"
+
+	check
+	pps
+	mem
+
+	echo
+done
+
+exit 0
diff --git a/util.c b/util.c
new file mode 100644
index 0000000..f1d4538
--- /dev/null
+++ b/util.c
@@ -0,0 +1,217 @@
+/* PIPAPO - PIle PAcket POlicies
+ *
+ * util.c - Convenience routines
+ *
+ * Author: Stefano Brivio <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <stdint.h>
+#include <string.h>
+#include <strings.h>
+
+#include "pipapo.h"
+
+/**
+ * set_bit() - Set single bit in arbitrary-sized word
+ * @data:	Word
+ * @n:		Bit number
+ *
+ * Equivalent to set_bit() in kernel.
+ */
+void set_bit(uint8_t *data, int n)
+{
+	data[n / 8] |= 1 << (n % 8);
+}
+
+/**
+ * bit_sum() - Sum bit to arbitrary-sized word with carry
+ * @v:		Word
+ * @n:		Bit number
+ * @len:	Word length
+ */
+void bit_sum(uint8_t *v, int n, int len)
+{
+	int carry = 0, i;
+
+	for (i = len - 1 - n / 8; i >= 0; i--) {
+		if (carry)
+			v[i]++;
+		else
+			v[i] += 1 << (n % 8);
+
+		if (v[i])
+			break;
+		carry = 1;
+	}
+}
+
+/**
+ * bit_sub() - Subtract bit from arbitrary-sized word with carry
+ * @v:		Word
+ * @n:		Bit number
+ * @len:	Word length
+ */
+void bit_sub(uint8_t *v, int n, int len)
+{
+	int carry = 0, i;
+
+	for (i = len - 1 - n / 8; i >= 0; i--) {
+		if (carry)
+			v[i]--;
+		else
+			v[i] -= 1 << (n % 8);
+
+		if (v[i] != 0xff)
+			break;
+		carry = 1;
+	}
+}
+
+/**
+ * andmem() - AND two memory regions
+ * @dst:	First operand and destination
+ * @src:	Second operand
+ * @len:	Length of memory region
+ *
+ * Equivalent to bitmap_and() in kernel.
+ */
+void andmem(uint8_t *dst, uint8_t *src, unsigned len)
+{
+	while (len >= sizeof(long)) {
+		*(unsigned long *)dst &= *(unsigned long *)src;
+		dst += sizeof(long);
+		src += sizeof(long);
+		len -= sizeof(long);
+	}
+
+	while (len >= sizeof(int)) {
+		*(unsigned int *)dst &= *(unsigned int *)src;
+		dst += sizeof(int);
+		src += sizeof(int);
+		len -= sizeof(int);
+	}
+
+	while (len--) {
+		*dst &= *src;
+		dst++;
+		src++;
+	}
+}
+
+/**
+ * ffs_clear() - Find first bit set in memory region and clear it
+ * @data:	Start of memory region
+ * @len:	Length of memory region
+ * @offset:	Starting offset in byte
+ *
+ * Similar purpose as for_each_set_bit_from() in kernel.
+ *
+ * Return: position of first set bit, if any, -1 otherwise
+ */
+int ffs_clear(uint8_t *data, unsigned int len, int byte_offset)
+{
+	int tmp = 0, n, c = byte_offset;
+
+	data += byte_offset;
+	len -= byte_offset;
+
+	while (len) {
+		if (len >= sizeof(long)) {
+			n = ffsl(*(unsigned long *)data);
+			if (n--) {
+				*((unsigned long *)data) &= ~(1UL << n);
+				return n + c * 8;
+			}
+			len -= sizeof(long);
+			data += sizeof(long);
+			c += sizeof(long);
+		} else if (len >= sizeof(int)) {
+			n = ffs(*(unsigned int *)data);
+			if (n--) {
+				*((unsigned int *)data) &= ~(1U << n);
+				return n + c * 8;
+			}
+			len -= sizeof(int);
+			data += sizeof(int);
+			c += sizeof(int);
+		} else {
+			memcpy(&tmp, data, len);
+			n = ffs(tmp);
+			if (n--) {
+				data[n / 8] &= ~(1U << (n % 8));
+				return n + c * 8;
+			}
+			return -1;
+		}
+	}
+
+	return -1;
+}
+
+/**
+ * test_bit - Test bit in memory region
+ * @data:	Memory region
+ * @n:		Bit to be tested
+ *
+ * Equivalent to test_bit() in kernel.
+ *
+ * Return: 1 if bit set, 0 if bit unset.
+ */
+int test_bit(uint8_t *data, int n)
+{
+	return !!(data[n / 8] & (1 << (n % 8)));
+}
+
+/**
+ * fold_bits() - Shift a bitmap region, removing a given amount of bits
+ * @data:	Memory region
+ * @first:	First bit to be removed
+ * @n:		Amount of bits to be removed
+ * @len:	Size of memory region
+ *
+ * Similar to bitmap_shift_left() in kernel, *not* equivalent to bitmap_fold().
+ * For example, with this bitmap, if start is 7 and n is 4:
+ *
+ * 1000 0110   1100 0001
+ * |       |   |       |
+ * 7       0  15       8
+ *
+ * we are removing these four bits:
+ * 
+ * x000 0110   1100 0xxx
+ * |       |   |       |
+ * 7       0  15       8
+ *
+ * resulting in:
+ *
+ * 0000 0110   0000 1100
+ * |       |   |       |
+ * 7       0  15       8
+ */
+void fold_bits(uint8_t *data, int first, int n, int len)
+{
+	uint8_t keep, carry;
+	int i;
+
+	if (first % 8)
+		keep = data[first / 8] & (0xff >> (8 - first % 8));
+	else
+		keep = 0;
+
+	while (n) {
+		for (i = first / 8; i < len; i++) {
+			if (i < len - 1)
+				carry = data[i + 1] & 0x01;
+			else
+				carry = 0;
+
+			data[i] >>= 1;
+			data[i] |= carry << 7;
+		}
+		n--;
+	}
+
+	data[first / 8] &= 0xff << (first % 8);
+	data[first / 8] |= keep;
+}
diff --git a/util.h b/util.h
new file mode 100644
index 0000000..94fc0f2
--- /dev/null
+++ b/util.h
@@ -0,0 +1,110 @@
+#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
+#define __round_mask(x, y) ((__typeof__(x))((y)-1))
+#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
+
+#define min(x, y) (((x) < (y)) ? (x) : (y))
+
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+#ifdef VERBOSE
+#define verbose(...) fprintf(stdout, __VA_ARGS__)
+#else
+#define verbose(...) do { } while (0)
+#endif
+
+void set_bit(uint8_t *data, int n, int len);
+void bit_sum(uint8_t *v, int n, int len);
+void bit_sub(uint8_t *v, int n, int len);
+void andmem(uint8_t *dst, uint8_t *src, int len);
+void ormem(uint8_t *dst, uint8_t *src, int len);
+int ffs_clear(uint8_t *data, int len, int byte_offset);
+int test_bit(uint8_t *data, int n);
+void fold_bits(uint8_t *data, int bit, int n, int len);
+
+/**
+ * fill() - Fill bits in given region
+ * @data:	Memory region
+ * @start:	First bit to set
+ * @len:	Number of bits to set
+ *
+ * Equivalent to bitmap_set() in kernel.
+ */
+__always_inline void fill(uint8_t *data, int start, int len)
+{
+	uint8_t mask;
+
+	data += start / 8;
+	if (likely(start % 8 || len < 8)) {
+		if (len + start % 8 < 8) {
+			mask = 0xff >> (8 - len);
+			*data |= mask << (start % 8);
+			return;
+		}
+
+		*data |= 0xff << (start % 8);
+		len -= 8 - start % 8;
+		data++;
+
+		if (len < 8) {
+			mask = 0xff >> (8 - len);
+			*data |= mask;
+			return;
+		}
+	}
+	memset(data, 0xff, len / 8);
+	data += len / 8;
+
+	if (len %= 8)
+		*data |= 0xff >> (8 - len);
+}
+
+/**
+ * ffs_and_fill() - For each set bit, set bits from selected mapping table item
+ * @map:	Bitmap to be scanned for set bits
+ * @offset:	Optional, initial offset, bytes
+ * @len:	Length of bitmap in 64-bit words
+ * @dst:	Destination bitmap
+ * @mt:		Mapping table containing bit set specifiers
+ * @one:	Find a single bit and return, don't fill
+ *
+ * Original implementation by Daniel Lemire, public domain.
+ *
+ * For each bit set in map, select the bucket from mapping table with index
+ * corresponding to the position of the bit set. Use start bit and amount of
+ * bits specified in bucket to fill region in dst.
+ *
+ * If __builtin_ctzl() is available, this is vastly more efficient compared to
+ * looking for bits using ffs64() as we can directly iterate without having to 
+ * return the bit position and clearing it or caching it for each set bit.
+ *
+ * If __builtin_ctzl() is not available, ffs_clear() will be used instead.
+ *
+ * Return: 0 on match, bit position if 'one' is passed, -1 otherwise.
+ */
+__always_inline int ffs_and_fill(uint8_t *map, int offset, int len,
+				 uint8_t *dst, union map_bucket *mt, int one)
+{
+	uint64_t bitset;
+	int k, ret = -1;
+
+	for (k = offset / 8; k < len; k++) {
+		bitset = ((uint64_t *)map)[k];
+		while (bitset) {
+			uint64_t t = bitset & -bitset;
+			int r = __builtin_ctzl(bitset);
+
+			if (unlikely(one))
+				return(k * 64 + r);
+
+			ret = 0;
+
+			fill(dst, mt[k * 64 + r].to, mt[k * 64 + r].n);
+
+			bitset ^= t;
+		}
+		map[k] = 0;
+	}
+
+	return ret;
+}