dovecot-2.2: lib: bit twiddles

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-2.2/rev/f7af15d654c3
changeset: 17447:f7af15d654c3
user:      Phil Carmody <phil at dovecot.fi>
date:      Mon Jun 09 23:02:52 2014 +0300
description:
lib: bit twiddles
bits_requiredXX() gives the number of bits required to store an unsigned
integer. Here, XX is 8, 16, 32, 64, reperesenting the size of the operand.
It belongs in the same file as nearest_power(), which makes most sense
in a separate bit twiddles file. Universal enough to stay in lib.h by
inclusion.

Signed-off-by: Phil Carmody <phil at dovecot.fi>

diffstat:

 src/lib/Makefile.am |   2 ++
 src/lib/bits.c      |  22 ++++++++++++++++++++++
 src/lib/bits.h      |  38 ++++++++++++++++++++++++++++++++++++++
 src/lib/lib.c       |  10 ----------
 src/lib/lib.h       |   2 +-
 5 files changed, 63 insertions(+), 11 deletions(-)

diffs (123 lines):

diff -r f9349a3c2604 -r f7af15d654c3 src/lib/Makefile.am
--- a/src/lib/Makefile.am	Mon Jun 09 22:59:59 2014 +0300
+++ b/src/lib/Makefile.am	Mon Jun 09 23:02:52 2014 +0300
@@ -17,6 +17,7 @@
 	askpass.c \
 	backtrace-string.c \
 	base64.c \
+	bits.c \
 	bsearch-insert-pos.c \
 	buffer.c \
 	child-wait.c \
@@ -146,6 +147,7 @@
 	askpass.h \
 	backtrace-string.h \
 	base64.h \
+	bits.h \
 	bsearch-insert-pos.h \
 	buffer.h \
 	child-wait.h \
diff -r f9349a3c2604 -r f7af15d654c3 src/lib/bits.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/bits.c	Mon Jun 09 23:02:52 2014 +0300
@@ -0,0 +1,22 @@
+/* Copyright (c) 2001-2014 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+
+size_t nearest_power(size_t num)
+{
+	size_t n = 1;
+
+	i_assert(num <= ((size_t)1 << (CHAR_BIT*sizeof(size_t) - 1)));
+
+	while (n < num) n <<= 1;
+	return n;
+}
+
+unsigned int bits_required8(uint8_t num)
+{
+	int ret = 0;
+	if (num > 0xf) { ret += 4; num >>= 4; }
+	if (num > 0x3) { ret += 2; num >>= 2; }
+	num &= ~(num>>1); /* 3->2, else unchanged */
+	return ret + num;
+}
diff -r f9349a3c2604 -r f7af15d654c3 src/lib/bits.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/bits.h	Mon Jun 09 23:02:52 2014 +0300
@@ -0,0 +1,38 @@
+#ifndef BITS_H
+#define BITS_H
+
+/* default lib includes */
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif
+
+#include "macros.h"
+
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
+
+size_t nearest_power(size_t num) ATTR_CONST;
+
+unsigned int bits_required8(uint8_t num) ATTR_CONST;
+
+static inline
+unsigned int bits_required16(uint16_t num)
+{
+	return (num <= 0xff) ? bits_required8(num)
+		: 8 + bits_required16(num >> 8);
+}
+static inline
+unsigned int bits_required32(uint32_t num)
+{
+	return (num <= 0xffff) ? bits_required16(num)
+		: 16 + bits_required16(num >> 16);
+}
+static inline
+unsigned int bits_required64(uint64_t num)
+{
+	return (num <= 0xffffffff) ? bits_required32(num)
+		: 32 + bits_required32(num >> 32);
+}
+
+#endif
diff -r f9349a3c2604 -r f7af15d654c3 src/lib/lib.c
--- a/src/lib/lib.c	Mon Jun 09 22:59:59 2014 +0300
+++ b/src/lib/lib.c	Mon Jun 09 23:02:52 2014 +0300
@@ -13,16 +13,6 @@
 
 static ARRAY(lib_atexit_callback_t *) atexit_callbacks = ARRAY_INIT;
 
-size_t nearest_power(size_t num)
-{
-	size_t n = 1;
-
-	i_assert(num <= ((size_t)1 << (CHAR_BIT*sizeof(size_t) - 1)));
-
-	while (n < num) n <<= 1;
-	return n;
-}
-
 int close_keep_errno(int *fd)
 {
 	int ret, old_errno = errno;
diff -r f9349a3c2604 -r f7af15d654c3 src/lib/lib.h
--- a/src/lib/lib.h	Mon Jun 09 22:59:59 2014 +0300
+++ b/src/lib/lib.h	Mon Jun 09 23:02:52 2014 +0300
@@ -38,11 +38,11 @@
 typedef void lib_atexit_callback_t(void);
 
 #include "array-decl.h" /* ARRAY*()s may exist in any header */
+#include "bits.h"
 #include "hash-decl.h" /* HASH_TABLE*()s may exist in any header */
 #include "strfuncs.h"
 #include "strnum.h"
 
-size_t nearest_power(size_t num) ATTR_CONST;
 int close_keep_errno(int *fd);
 
 /* Call the given callback at the beginning of lib_deinit(). The main