git:master: core: bit conting and testing functions - sr-dev

19 May 2010

Module: sip-router
Branch: master
Commit: 7ee950eb3e34dc0cdb3e825fa347dd29e7526afc
URL:    http://git.sip-router.org/cgi-bin/gitweb.cgi/sip-router/?a=commit;h=7ee950eb...
Author: Miklos Tirpak miklos@iptel.org
Committer: Miklos Tirpak miklos@iptel.org
Date:   Wed May 19 11:53:19 2010 +0200
core: bit conting and testing functions
new functions for bit operations:
- bit_count()
- bit_test()
- bit_test_and_set()
---
bit_count.c |   44 +++++++++++++++++++++
 bit_count.h |  101 +++++++++++++++++++++++++++++++++++++++++++++++++
 bit_test.h  |  121 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 266 insertions(+), 0 deletions(-)

diff --git a/bit_count.c b/bit_count.c
new file mode 100644
index 0000000..faef43c
--- /dev/null
+++ b/bit_count.c
@@ -0,0 +1,44 @@
+/*
+ * $Id$
+ *
+ * Copyright (C) 2010 iptelorg GmbH
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * History
+ * -------
+ *  2010-04-26	Initial version (Miklos)
+ */
+
+#include "bit_count.h"
+
+#if 0
+/* number of bits in a byte */
+int	bits_in_char[256] = {
+			0 ,1 ,1 ,2 ,1 ,2 ,2 ,3 ,1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,
+			1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,
+			1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,
+			2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,
+			1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,
+			2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,
+			2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,
+			3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 ,
+			1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,
+			2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,
+			2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,
+			3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 ,
+			2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,
+			3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 ,
+			3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 ,
+			4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 ,5 ,6 ,6 ,7 ,6 ,7 ,7 ,8 };
+#endif
diff --git a/bit_count.h b/bit_count.h
new file mode 100644
index 0000000..6e7f62c
--- /dev/null
+++ b/bit_count.h
@@ -0,0 +1,101 @@
+/*
+ * $Id$
+ *
+ * Copyright (C) 2010 iptelorg GmbH
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * History
+ * -------
+ *  2010-04-26	Initial version (Miklos)
+ */
+
+/* Implements the bit counting function:
+ *   int bit_count(unsigned int u)
+ *   Returns the number of bits in u.
+ */
+
+#ifndef _BIT_COUNT_H
+#define _BIT_COUNT_H
+
+/* fix __CPU_i386 -> __CPU_x86 */
+#if defined __CPU_i386 && ! defined __CPU_x86
+#define __CPU_x86
+#endif
+ 
+#ifdef CC_GCC_LIKE_ASM
+#if defined __CPU_x86 || defined __CPU_x86_64
+#ifdef __SSE4_2__
+/* popcnt requires SSE4.2 support,
+ * see http://en.wikipedia.org/wiki/SSE4 */
+#define BIT_COUNT_ASM
+#endif
+#endif
+#endif
+
+#ifdef BIT_COUNT_ASM
+
+/* Returns the number of 1 bits in u. */
+static inline int bit_count(unsigned int u)
+{
+	int	v;
+
+	asm volatile(" popcnt %1, %0 " : "=r" (v) : "rm" (u));
+	return v;
+}
+
+#else /* BIT_COUNT_ASM */
+
+/* Returns the number of 1 bits in u.
+ * source: http://en.wikipedia.org/wiki/Hamming_weight
+ */
+#if 0
+static inline int bit_count(unsigned int u)
+{
+	int	count;
+
+	/* It is likely to have only few
+	 * bits set to 1, so there will be only
+	 * few iterations */
+	for (count=0; u; count++)
+		u &= u-1;
+	return count;
+}
+#endif
+
+static inline int bit_count(unsigned int i)
+{
+	i = i - ((i >> 1) & 0x55555555);
+	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
+	return (((i + (i >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
+}
+
+#if 0
+/* number of bits in a byte.
+ * (Only slightly faster then the above version,
+ * It is not worth the extra memory usage.)
+ */
+extern int	bits_in_char[256];
+
+static inline int bit_count(unsigned int u)
+{
+	return bits_in_char [u & 0xffu]
+		+  bits_in_char [(u >>  8 ) & 0xffu]
+		+  bits_in_char [(u >> 16) & 0xffu]
+		+  bits_in_char [(u >> 24) & 0xffu];
+}
+#endif
+
+#endif /* BIT_COUNT_ASM */
+
+#endif /* _BIT_COUNT_H */
diff --git a/bit_test.h b/bit_test.h
new file mode 100644
index 0000000..534e502
--- /dev/null
+++ b/bit_test.h
@@ -0,0 +1,121 @@
+/*
+ * $Id$
+ *
+ * Copyright (C) 2010 iptelorg GmbH
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * History
+ * -------
+ *  2010-04-26	Initial version (Miklos)
+ */
+
+/* Bit test functions:
+ *  - int bit_test(int offset, unsigned int *addr)
+ *      Returns the bit found at offset position 
+ *      in a bitstring pointed by addr.
+ *
+ *  - int bit_test_and_set(int offset, unsigned int *addr)
+ *      Returns the bit found at offset position 
+ *      in a bitstring pointed by addr, and sets
+ *      the bit at the given offset.
+ *
+ * Note that 0 <= offset <= 128, Make sure that addr points to
+ * a large enough memory area.
+ */
+
+#ifndef _BIT_TEST_H
+#define _BIT_TEST_H
+
+/* fix __CPU_i386 -> __CPU_x86 */
+#if defined __CPU_i386 && ! defined __CPU_x86
+#define __CPU_x86
+#endif
+ 
+#ifdef CC_GCC_LIKE_ASM
+#if defined __CPU_x86 || defined __CPU_x86_64
+#define BIT_TEST_ASM
+#endif
+#endif
+
+#ifdef BIT_TEST_ASM
+
+/* Returns the bit found at offset position in the bitstring
+ * pointed by addr.
+ * Note that the CPU can access 4 bytes starting from addr,
+ * hence 0 <= offset < 128 holds. Make sure that addr points
+ * to a memory area that is large enough.
+ */
+static inline int bit_test(int offset, unsigned int *addr)
+{
+	unsigned char	v;
+
+	asm volatile(
+		" bt %2, %1 \n\t"
+		" setc %0 \n\t"
+		: "=qm" (v) : "m" (*addr), "r" (offset)
+	);
+	return (int)v;
+}
+
+/* Returns the bit found at offset position in the bitstring
+ * pointed by addr and sets it to 1.
+ * Note that the CPU can access 4 bytes starting from addr,
+ * hence 0 <= offset < 128 holds. Make sure that addr points
+ * to a memory area that is large enough.
+ */
+static inline int bit_test_and_set(int offset, unsigned int *addr)
+{
+	unsigned char	v;
+
+	asm volatile(
+		" bts %2, %1 \n\t"
+		" setc %0 \n\t"
+		: "=qm" (v) : "m" (*addr), "r" (offset)
+	);
+	return (int)v;
+}
+
+#else /* BIT_TEST_ASM */
+
+/* Returns the bit found at offset position in the bitstring
+ * pointed by addr.
+ * Note that offset can be grater than 32, make sure that addr points
+ * to a memory area that is large enough.
+ */
+static inline int bit_test(int offset, unsigned int *addr)
+{
+	return ((*(addr + offset/32)) & (1U << (offset % 32))) ? 1 : 0;
+}
+
+/* Returns the bit found at offset position in the bitstring
+ * pointed by addr and sets it to 1.
+ * Note that offset can be grater than 32, make sure that addr points
+ * to a memory area that is large enough.
+ */
+static inline int bit_test_and_set(int offset, unsigned int *addr)
+{
+	unsigned int	*i;
+	int	mask, res;
+
+	i = addr + offset/32;
+	mask = 1U << (offset % 32);
+	res = ((*i) & mask) ? 1 : 0;
+	(*i) |= mask;
+
+	return res;
+}
+
+#endif /* BIT_TEST_ASM */
+
+#endif /* #ifndef _BIT_TEST_H */

    