Module: sip-router Branch: master Commit: 7ee950eb3e34dc0cdb3e825fa347dd29e7526afc URL: http://git.sip-router.org/cgi-bin/gitweb.cgi/sip-router/?a=commit;h=7ee950e… Author: Miklos Tirpak &lt;miklos(a)iptel.org&gt; Committer: Miklos Tirpak &lt;miklos(a)iptel.org&gt; 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 */