core: Make sure that responses to requests received on a WebSocket are sent on existi...
[sip-router] / bit_count.h
1 /*
2  * $Id$
3  *
4  * Copyright (C) 2010 iptelorg GmbH
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  *
18  * History
19  * -------
20  *  2010-04-26  Initial version (Miklos)
21  */
22
23 /* Implements the bit counting function:
24  *   int bit_count(unsigned int u)
25  *   Returns the number of bits in u.
26  */
27
28 #ifndef _BIT_COUNT_H
29 #define _BIT_COUNT_H
30
31 /* fix __CPU_i386 -> __CPU_x86 */
32 #if defined __CPU_i386 && ! defined __CPU_x86
33 #define __CPU_x86
34 #endif
35  
36 #ifdef CC_GCC_LIKE_ASM
37 #if defined __CPU_x86 || defined __CPU_x86_64
38 #ifdef __SSE4_2__
39 /* popcnt requires SSE4.2 support,
40  * see http://en.wikipedia.org/wiki/SSE4 */
41 #define BIT_COUNT_ASM
42 #endif
43 #endif
44 #endif
45
46 #ifdef BIT_COUNT_ASM
47
48 /* Returns the number of 1 bits in u. */
49 static inline int bit_count(unsigned int u)
50 {
51         int     v;
52
53         asm volatile(" popcnt %1, %0 " : "=r" (v) : "rm" (u));
54         return v;
55 }
56
57 #else /* BIT_COUNT_ASM */
58
59 /* Returns the number of 1 bits in u.
60  * source: http://en.wikipedia.org/wiki/Hamming_weight
61  */
62 #if 0
63 static inline int bit_count(unsigned int u)
64 {
65         int     count;
66
67         /* It is likely to have only few
68          * bits set to 1, so there will be only
69          * few iterations */
70         for (count=0; u; count++)
71                 u &= u-1;
72         return count;
73 }
74 #endif
75
76 static inline int bit_count(unsigned int i)
77 {
78         i = i - ((i >> 1) & 0x55555555);
79         i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
80         return (((i + (i >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
81 }
82
83 #if 0
84 /* number of bits in a byte.
85  * (Only slightly faster then the above version,
86  * It is not worth the extra memory usage.)
87  */
88 extern int      bits_in_char[256];
89
90 static inline int bit_count(unsigned int u)
91 {
92         return bits_in_char [u & 0xffu]
93                 +  bits_in_char [(u >>  8 ) & 0xffu]
94                 +  bits_in_char [(u >> 16) & 0xffu]
95                 +  bits_in_char [(u >> 24) & 0xffu];
96 }
97 #endif
98
99 #endif /* BIT_COUNT_ASM */
100
101 #endif /* _BIT_COUNT_H */