dovecot-2.2: liblib: Added "number packing" API.

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-2.2/rev/b45d968adff8
changeset: 14861:b45d968adff8
user:      Timo Sirainen <tss at iki.fi>
date:      Sat Aug 11 07:46:42 2012 +0300
description:
liblib: Added "number packing" API.

diffstat:

 src/lib/Makefile.am    |   3 +++
 src/lib/numpack.c      |  45 +++++++++++++++++++++++++++++++++++++++++++++
 src/lib/numpack.h      |  10 ++++++++++
 src/lib/test-lib.c     |   1 +
 src/lib/test-lib.h     |   1 +
 src/lib/test-numpack.c |  44 ++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 104 insertions(+), 0 deletions(-)

diffs (160 lines):

diff -r f0feae227c60 -r b45d968adff8 src/lib/Makefile.am
--- a/src/lib/Makefile.am	Sat Aug 11 05:47:03 2012 +0300
+++ b/src/lib/Makefile.am	Sat Aug 11 07:46:42 2012 +0300
@@ -95,6 +95,7 @@
 	mountpoint.c \
 	network.c \
 	nfs-workarounds.c \
+	numpack.c \
 	ostream.c \
 	ostream-file.c \
 	ostream-buffer.c \
@@ -207,6 +208,7 @@
 	mountpoint.h \
 	network.h \
 	nfs-workarounds.h \
+	numpack.h \
 	ostream.h \
 	ostream-private.h \
 	ostream-rawlog.h \
@@ -273,6 +275,7 @@
 	test-llist.c \
 	test-mempool-alloconly.c \
 	test-network.c \
+	test-numpack.c \
 	test-ostream-file.c \
 	test-primes.c \
 	test-priorityq.c \
diff -r f0feae227c60 -r b45d968adff8 src/lib/numpack.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/numpack.c	Sat Aug 11 07:46:42 2012 +0300
@@ -0,0 +1,45 @@
+/* Copyright (c) 2012 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "buffer.h"
+#include "numpack.h"
+
+void numpack_encode(buffer_t *buf, uint64_t num)
+{
+	/* number continues as long as the highest bit is set */
+	while (num >= 0x80) {
+		buffer_append_c(buf, (num & 0x7f) | 0x80);
+		num >>= 7;
+	}
+
+	buffer_append_c(buf, num);
+}
+
+int numpack_decode(const uint8_t **p, const uint8_t *end, uint64_t *num_r)
+{
+	const uint8_t *c = *p;
+	uint64_t value = 0;
+	unsigned int bits = 0;
+
+	for (;;) {
+		if (c == end)
+			return -1;
+
+		value |= (uint64_t)(*c & 0x7f) << bits;
+		if (*c < 0x80)
+			break;
+
+		bits += 7;
+		c++;
+	}
+
+	if (bits >= 64) {
+		/* overflow */
+		*p = end;
+		return -1;
+	}
+
+	*p = c + 1;
+	*num_r = value;
+	return 0;
+}
diff -r f0feae227c60 -r b45d968adff8 src/lib/numpack.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/numpack.h	Sat Aug 11 07:46:42 2012 +0300
@@ -0,0 +1,10 @@
+#ifndef NUMPACK_H
+#define NUMPACK_H
+
+/* Numbers are stored by 7 bits at a time. The highest bit specifies if the
+   number continues to next byte. */
+
+void numpack_encode(buffer_t *buf, uint64_t num);
+int numpack_decode(const uint8_t **p, const uint8_t *end, uint64_t *num_r);
+
+#endif
diff -r f0feae227c60 -r b45d968adff8 src/lib/test-lib.c
--- a/src/lib/test-lib.c	Sat Aug 11 05:47:03 2012 +0300
+++ b/src/lib/test-lib.c	Sat Aug 11 07:46:42 2012 +0300
@@ -23,6 +23,7 @@
 		test_llist,
 		test_mempool_alloconly,
 		test_network,
+		test_numpack,
 		test_ostream_file,
 		test_primes,
 		test_priorityq,
diff -r f0feae227c60 -r b45d968adff8 src/lib/test-lib.h
--- a/src/lib/test-lib.h	Sat Aug 11 05:47:03 2012 +0300
+++ b/src/lib/test-lib.h	Sat Aug 11 07:46:42 2012 +0300
@@ -22,6 +22,7 @@
 void test_llist(void);
 void test_mempool_alloconly(void);
 void test_network(void);
+void test_numpack(void);
 void test_ostream_file(void);
 void test_primes(void);
 void test_priorityq(void);
diff -r f0feae227c60 -r b45d968adff8 src/lib/test-numpack.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/test-numpack.c	Sat Aug 11 07:46:42 2012 +0300
@@ -0,0 +1,44 @@
+/* Copyright (c) 2012 Dovecot authors, see the included COPYING file */
+
+#include "test-lib.h"
+#include "buffer.h"
+#include "numpack.h"
+
+#include <stdlib.h>
+
+static struct test {
+	uint64_t input;
+	uint8_t output[10];
+	unsigned int output_size;
+} tests[] = {
+	{ 0xffffffff, { 0xff, 0xff, 0xff, 0xff, 0xf }, 5 },
+	{ 0, { 0 }, 1 },
+	{ 0x7f, { 0x7f }, 1 },
+	{ 0x80, { 0x80, 1 }, 2 },
+	{ 0x81, { 0x81, 1 }, 2 },
+	{ 0xdeadbeefcafe, { 0xfe, 0x95, 0xbf, 0xf7, 0xdb, 0xd5, 0x37 }, 7 },
+	{ 0xffffffffffffffff, { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 1 }, 10 },
+	{ 0xfffffffe, { 0xfe, 0xff, 0xff, 0xff, 0xf }, 5 },
+};
+
+void test_numpack(void)
+{
+	buffer_t *buf = buffer_create_dynamic(pool_datastack_create(), 32);
+	unsigned int i;
+	const uint8_t *p, *end;
+	uint64_t num;
+
+	test_begin("numpack");
+	for (i = 0; i < N_ELEMENTS(tests); i++) {
+		buffer_set_used_size(buf, 0);
+		numpack_encode(buf, tests[i].input);
+		test_assert(buf->used == tests[i].output_size &&
+			    memcmp(buf->data, tests[i].output,
+				   tests[i].output_size) == 0);
+
+		p = buf->data; end = p + buf->used;
+		test_assert(numpack_decode(&p, end, &num) == 0);
+		test_assert(num == tests[i].input);
+	}
+	test_end();
+}