]>
Commit | Line | Data |
---|---|---|
10602db8 DR |
1 | /* |
2 | * SpanDSP - a series of DSP components for telephony | |
3 | * | |
4 | * bit_operations.h - Various bit level operations, such as bit reversal | |
5 | * | |
6 | * Written by Steve Underwood <steveu@coppice.org> | |
7 | * | |
8 | * Copyright (C) 2006 Steve Underwood | |
9 | * | |
10 | * All rights reserved. | |
11 | * | |
12 | * This program is free software; you can redistribute it and/or modify | |
13 | * it under the terms of the GNU General Public License version 2, as | |
14 | * published by the Free Software Foundation. | |
15 | * | |
16 | * This program is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | * GNU General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU General Public License | |
22 | * along with this program; if not, write to the Free Software | |
23 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
10602db8 DR |
24 | */ |
25 | ||
26 | /*! \file */ | |
27 | ||
28 | #if !defined(_BIT_OPERATIONS_H_) | |
29 | #define _BIT_OPERATIONS_H_ | |
30 | ||
10602db8 DR |
31 | #if defined(__i386__) || defined(__x86_64__) |
32 | /*! \brief Find the bit position of the highest set bit in a word | |
33 | \param bits The word to be searched | |
34 | \return The bit number of the highest set bit, or -1 if the word is zero. */ | |
dc57a3ea | 35 | static inline int top_bit(unsigned int bits) |
10602db8 | 36 | { |
4460a860 M |
37 | int res; |
38 | ||
39 | __asm__(" xorl %[res],%[res];\n" | |
40 | " decl %[res];\n" | |
41 | " bsrl %[bits],%[res]\n" | |
42 | :[res] "=&r" (res) | |
43 | :[bits] "rm"(bits) | |
44 | ); | |
45 | return res; | |
10602db8 | 46 | } |
10602db8 DR |
47 | |
48 | /*! \brief Find the bit position of the lowest set bit in a word | |
49 | \param bits The word to be searched | |
50 | \return The bit number of the lowest set bit, or -1 if the word is zero. */ | |
dc57a3ea | 51 | static inline int bottom_bit(unsigned int bits) |
10602db8 | 52 | { |
4460a860 M |
53 | int res; |
54 | ||
55 | __asm__(" xorl %[res],%[res];\n" | |
56 | " decl %[res];\n" | |
57 | " bsfl %[bits],%[res]\n" | |
58 | :[res] "=&r" (res) | |
59 | :[bits] "rm"(bits) | |
60 | ); | |
61 | return res; | |
10602db8 | 62 | } |
10602db8 | 63 | #else |
dc57a3ea | 64 | static inline int top_bit(unsigned int bits) |
10602db8 | 65 | { |
4460a860 M |
66 | int i; |
67 | ||
68 | if (bits == 0) | |
69 | return -1; | |
70 | i = 0; | |
71 | if (bits & 0xFFFF0000) { | |
72 | bits &= 0xFFFF0000; | |
73 | i += 16; | |
74 | } | |
75 | if (bits & 0xFF00FF00) { | |
76 | bits &= 0xFF00FF00; | |
77 | i += 8; | |
78 | } | |
79 | if (bits & 0xF0F0F0F0) { | |
80 | bits &= 0xF0F0F0F0; | |
81 | i += 4; | |
82 | } | |
83 | if (bits & 0xCCCCCCCC) { | |
84 | bits &= 0xCCCCCCCC; | |
85 | i += 2; | |
86 | } | |
87 | if (bits & 0xAAAAAAAA) { | |
88 | bits &= 0xAAAAAAAA; | |
89 | i += 1; | |
90 | } | |
91 | return i; | |
10602db8 | 92 | } |
10602db8 | 93 | |
dc57a3ea | 94 | static inline int bottom_bit(unsigned int bits) |
10602db8 | 95 | { |
4460a860 M |
96 | int i; |
97 | ||
98 | if (bits == 0) | |
99 | return -1; | |
100 | i = 32; | |
101 | if (bits & 0x0000FFFF) { | |
102 | bits &= 0x0000FFFF; | |
103 | i -= 16; | |
104 | } | |
105 | if (bits & 0x00FF00FF) { | |
106 | bits &= 0x00FF00FF; | |
107 | i -= 8; | |
108 | } | |
109 | if (bits & 0x0F0F0F0F) { | |
110 | bits &= 0x0F0F0F0F; | |
111 | i -= 4; | |
112 | } | |
113 | if (bits & 0x33333333) { | |
114 | bits &= 0x33333333; | |
115 | i -= 2; | |
116 | } | |
117 | if (bits & 0x55555555) { | |
118 | bits &= 0x55555555; | |
119 | i -= 1; | |
120 | } | |
121 | return i; | |
10602db8 | 122 | } |
10602db8 DR |
123 | #endif |
124 | ||
125 | /*! \brief Bit reverse a byte. | |
126 | \param data The byte to be reversed. | |
127 | \return The bit reversed version of data. */ | |
dc57a3ea | 128 | static inline uint8_t bit_reverse8(uint8_t x) |
10602db8 DR |
129 | { |
130 | #if defined(__i386__) || defined(__x86_64__) | |
4460a860 M |
131 | /* If multiply is fast */ |
132 | return ((x * 0x0802U & 0x22110U) | (x * 0x8020U & 0x88440U)) * | |
133 | 0x10101U >> 16; | |
10602db8 | 134 | #else |
4460a860 M |
135 | /* If multiply is slow, but we have a barrel shifter */ |
136 | x = (x >> 4) | (x << 4); | |
137 | x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); | |
138 | return ((x & 0xAA) >> 1) | ((x & 0x55) << 1); | |
10602db8 DR |
139 | #endif |
140 | } | |
10602db8 DR |
141 | |
142 | /*! \brief Bit reverse a 16 bit word. | |
143 | \param data The word to be reversed. | |
144 | \return The bit reversed version of data. */ | |
145 | uint16_t bit_reverse16(uint16_t data); | |
146 | ||
147 | /*! \brief Bit reverse a 32 bit word. | |
148 | \param data The word to be reversed. | |
149 | \return The bit reversed version of data. */ | |
150 | uint32_t bit_reverse32(uint32_t data); | |
151 | ||
152 | /*! \brief Bit reverse each of the four bytes in a 32 bit word. | |
153 | \param data The word to be reversed. | |
154 | \return The bit reversed version of data. */ | |
155 | uint32_t bit_reverse_4bytes(uint32_t data); | |
156 | ||
157 | /*! \brief Find the number of set bits in a 32 bit word. | |
158 | \param x The word to be searched. | |
159 | \return The number of set bits. */ | |
160 | int one_bits32(uint32_t x); | |
161 | ||
162 | /*! \brief Create a mask as wide as the number in a 32 bit word. | |
163 | \param x The word to be searched. | |
164 | \return The mask. */ | |
165 | uint32_t make_mask32(uint32_t x); | |
166 | ||
167 | /*! \brief Create a mask as wide as the number in a 16 bit word. | |
168 | \param x The word to be searched. | |
169 | \return The mask. */ | |
170 | uint16_t make_mask16(uint16_t x); | |
171 | ||
172 | /*! \brief Find the least significant one in a word, and return a word | |
dc57a3ea | 173 | with just that bit set. |
10602db8 DR |
174 | \param x The word to be searched. |
175 | \return The word with the single set bit. */ | |
dc57a3ea | 176 | static inline uint32_t least_significant_one32(uint32_t x) |
10602db8 | 177 | { |
dc57a3ea | 178 | return x & (-(int32_t) x); |
10602db8 | 179 | } |
10602db8 DR |
180 | |
181 | /*! \brief Find the most significant one in a word, and return a word | |
dc57a3ea | 182 | with just that bit set. |
10602db8 DR |
183 | \param x The word to be searched. |
184 | \return The word with the single set bit. */ | |
dc57a3ea | 185 | static inline uint32_t most_significant_one32(uint32_t x) |
10602db8 DR |
186 | { |
187 | #if defined(__i386__) || defined(__x86_64__) | |
4460a860 | 188 | return 1 << top_bit(x); |
10602db8 | 189 | #else |
4460a860 | 190 | x = make_mask32(x); |
dc57a3ea | 191 | return x ^ (x >> 1); |
10602db8 DR |
192 | #endif |
193 | } | |
10602db8 DR |
194 | |
195 | /*! \brief Find the parity of a byte. | |
196 | \param x The byte to be checked. | |
197 | \return 1 for odd, or 0 for even. */ | |
dc57a3ea | 198 | static inline int parity8(uint8_t x) |
10602db8 | 199 | { |
4460a860 M |
200 | x = (x ^ (x >> 4)) & 0x0F; |
201 | return (0x6996 >> x) & 1; | |
10602db8 | 202 | } |
10602db8 DR |
203 | |
204 | /*! \brief Find the parity of a 16 bit word. | |
205 | \param x The word to be checked. | |
206 | \return 1 for odd, or 0 for even. */ | |
dc57a3ea | 207 | static inline int parity16(uint16_t x) |
10602db8 | 208 | { |
4460a860 M |
209 | x ^= (x >> 8); |
210 | x = (x ^ (x >> 4)) & 0x0F; | |
211 | return (0x6996 >> x) & 1; | |
10602db8 | 212 | } |
10602db8 DR |
213 | |
214 | /*! \brief Find the parity of a 32 bit word. | |
215 | \param x The word to be checked. | |
216 | \return 1 for odd, or 0 for even. */ | |
dc57a3ea | 217 | static inline int parity32(uint32_t x) |
10602db8 | 218 | { |
4460a860 M |
219 | x ^= (x >> 16); |
220 | x ^= (x >> 8); | |
221 | x = (x ^ (x >> 4)) & 0x0F; | |
222 | return (0x6996 >> x) & 1; | |
10602db8 | 223 | } |
10602db8 | 224 | |
10602db8 DR |
225 | #endif |
226 | /*- End of file ------------------------------------------------------------*/ |