Mercurial > hg > audiostuff

comparison spandsp-0.0.6pre17/src/spandsp/bit_operations.h @ 4:26cd8f1ef0b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import spandsp-0.0.6pre17
author Peter Meerwald <pmeerw@cosy.sbg.ac.at>
date Fri, 25 Jun 2010 15:50:58 +0200
parents
children
comparison
equal deleted inserted replaced
3:c6c5a16ce2f2 4:26cd8f1ef0b1
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 Lesser General Public License version 2.1,
14 * as 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 Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with this program; if not, write to the Free Software
23 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 *
25 * $Id: bit_operations.h,v 1.27 2009/07/10 13:15:56 steveu Exp $
26 */
27
28 /*! \file */
29
30 #if !defined(_SPANDSP_BIT_OPERATIONS_H_)
31 #define _SPANDSP_BIT_OPERATIONS_H_
32
33 #if defined(__i386__) || defined(__x86_64__)
34 #if !defined(__SUNPRO_C) || (__SUNPRO_C >= 0x0590)
35 #define SPANDSP_USE_86_ASM
36 #endif
37 #endif
38
39 #if defined(__cplusplus)
40 extern "C"
41 {
42 #endif
43
44 /*! \brief Find the bit position of the highest set bit in a word
45 \param bits The word to be searched
46 \return The bit number of the highest set bit, or -1 if the word is zero. */
47 static __inline__ int top_bit(unsigned int bits)
48 {
49 #if defined(SPANDSP_USE_86_ASM)
50 int res;
51
52 __asm__ (" xorl %[res],%[res];\n"
53 " decl %[res];\n"
54 " bsrl %[bits],%[res]\n"
55 : [res] "=&r" (res)
56 : [bits] "rm" (bits));
57 return res;
58 #elif defined(__ppc__) || defined(__powerpc__)
59 int res;
60
61 __asm__ ("cntlzw %[res],%[bits];\n"
62 : [res] "=&r" (res)
63 : [bits] "r" (bits));
64 return 31 - res;
65 #elif defined(_M_IX86)
66 /* Visual Studio i386 */
67 __asm
68 {
69 xor eax, eax
70 dec eax
71 bsr eax, bits
72 }
73 #elif defined(_M_X64)
74 /* Visual Studio x86_64 */
75 /* TODO: Need the appropriate x86_64 code */
76 int res;
77
78 if (bits == 0)
79 return -1;
80 res = 0;
81 if (bits & 0xFFFF0000)
82 {
83 bits &= 0xFFFF0000;
84 res += 16;
85 }
86 if (bits & 0xFF00FF00)
87 {
88 bits &= 0xFF00FF00;
89 res += 8;
90 }
91 if (bits & 0xF0F0F0F0)
92 {
93 bits &= 0xF0F0F0F0;
94 res += 4;
95 }
96 if (bits & 0xCCCCCCCC)
97 {
98 bits &= 0xCCCCCCCC;
99 res += 2;
100 }
101 if (bits & 0xAAAAAAAA)
102 {
103 bits &= 0xAAAAAAAA;
104 res += 1;
105 }
106 return res;
107 #else
108 int res;
109
110 if (bits == 0)
111 return -1;
112 res = 0;
113 if (bits & 0xFFFF0000)
114 {
115 bits &= 0xFFFF0000;
116 res += 16;
117 }
118 if (bits & 0xFF00FF00)
119 {
120 bits &= 0xFF00FF00;
121 res += 8;
122 }
123 if (bits & 0xF0F0F0F0)
124 {
125 bits &= 0xF0F0F0F0;
126 res += 4;
127 }
128 if (bits & 0xCCCCCCCC)
129 {
130 bits &= 0xCCCCCCCC;
131 res += 2;
132 }
133 if (bits & 0xAAAAAAAA)
134 {
135 bits &= 0xAAAAAAAA;
136 res += 1;
137 }
138 return res;
139 #endif
140 }
141 /*- End of function --------------------------------------------------------*/
142
143 /*! \brief Find the bit position of the lowest set bit in a word
144 \param bits The word to be searched
145 \return The bit number of the lowest set bit, or -1 if the word is zero. */
146 static __inline__ int bottom_bit(unsigned int bits)
147 {
148 int res;
149
150 #if defined(SPANDSP_USE_86_ASM)
151 __asm__ (" xorl %[res],%[res];\n"
152 " decl %[res];\n"
153 " bsfl %[bits],%[res]\n"
154 : [res] "=&r" (res)
155 : [bits] "rm" (bits));
156 return res;
157 #else
158 if (bits == 0)
159 return -1;
160 res = 31;
161 if (bits & 0x0000FFFF)
162 {
163 bits &= 0x0000FFFF;
164 res -= 16;
165 }
166 if (bits & 0x00FF00FF)
167 {
168 bits &= 0x00FF00FF;
169 res -= 8;
170 }
171 if (bits & 0x0F0F0F0F)
172 {
173 bits &= 0x0F0F0F0F;
174 res -= 4;
175 }
176 if (bits & 0x33333333)
177 {
178 bits &= 0x33333333;
179 res -= 2;
180 }
181 if (bits & 0x55555555)
182 {
183 bits &= 0x55555555;
184 res -= 1;
185 }
186 return res;
187 #endif
188 }
189 /*- End of function --------------------------------------------------------*/
190
191 /*! \brief Bit reverse a byte.
192 \param data The byte to be reversed.
193 \return The bit reversed version of data. */
194 static __inline__ uint8_t bit_reverse8(uint8_t x)
195 {
196 #if defined(__i386__) || defined(__x86_64__) || defined(__ppc__) || defined(__powerpc__)
197 /* If multiply is fast */
198 return ((x*0x0802U & 0x22110U) | (x*0x8020U & 0x88440U))*0x10101U >> 16;
199 #else
200 /* If multiply is slow, but we have a barrel shifter */
201 x = (x >> 4) | (x << 4);
202 x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
203 return ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
204 #endif
205 }
206 /*- End of function --------------------------------------------------------*/
207
208 /*! \brief Bit reverse a 16 bit word.
209 \param data The word to be reversed.
210 \return The bit reversed version of data. */
211 SPAN_DECLARE(uint16_t) bit_reverse16(uint16_t data);
212
213 /*! \brief Bit reverse a 32 bit word.
214 \param data The word to be reversed.
215 \return The bit reversed version of data. */
216 SPAN_DECLARE(uint32_t) bit_reverse32(uint32_t data);
217
218 /*! \brief Bit reverse each of the four bytes in a 32 bit word.
219 \param data The word to be reversed.
220 \return The bit reversed version of data. */
221 SPAN_DECLARE(uint32_t) bit_reverse_4bytes(uint32_t data);
222
223 #if defined(__x86_64__)
224 /*! \brief Bit reverse each of the eight bytes in a 64 bit word.
225 \param data The word to be reversed.
226 \return The bit reversed version of data. */
227 SPAN_DECLARE(uint64_t) bit_reverse_8bytes(uint64_t data);
228 #endif
229
230 /*! \brief Bit reverse each bytes in a buffer.
231 \param to The buffer to place the reversed data in.
232 \param from The buffer containing the data to be reversed.
233 \param len The length of the data in the buffer. */
234 SPAN_DECLARE(void) bit_reverse(uint8_t to[], const uint8_t from[], int len);
235
236 /*! \brief Find the number of set bits in a 32 bit word.
237 \param x The word to be searched.
238 \return The number of set bits. */
239 SPAN_DECLARE(int) one_bits32(uint32_t x);
240
241 /*! \brief Create a mask as wide as the number in a 32 bit word.
242 \param x The word to be searched.
243 \return The mask. */
244 SPAN_DECLARE(uint32_t) make_mask32(uint32_t x);
245
246 /*! \brief Create a mask as wide as the number in a 16 bit word.
247 \param x The word to be searched.
248 \return The mask. */
249 SPAN_DECLARE(uint16_t) make_mask16(uint16_t x);
250
251 /*! \brief Find the least significant one in a word, and return a word
252 with just that bit set.
253 \param x The word to be searched.
254 \return The word with the single set bit. */
255 static __inline__ uint32_t least_significant_one32(uint32_t x)
256 {
257 return (x & (-(int32_t) x));
258 }
259 /*- End of function --------------------------------------------------------*/
260
261 /*! \brief Find the most significant one in a word, and return a word
262 with just that bit set.
263 \param x The word to be searched.
264 \return The word with the single set bit. */
265 static __inline__ uint32_t most_significant_one32(uint32_t x)
266 {
267 #if defined(__i386__) || defined(__x86_64__) || defined(__ppc__) || defined(__powerpc__)
268 return 1 << top_bit(x);
269 #else
270 x = make_mask32(x);
271 return (x ^ (x >> 1));
272 #endif
273 }
274 /*- End of function --------------------------------------------------------*/
275
276 /*! \brief Find the parity of a byte.
277 \param x The byte to be checked.
278 \return 1 for odd, or 0 for even. */
279 static __inline__ int parity8(uint8_t x)
280 {
281 x = (x ^ (x >> 4)) & 0x0F;
282 return (0x6996 >> x) & 1;
283 }
284 /*- End of function --------------------------------------------------------*/
285
286 /*! \brief Find the parity of a 16 bit word.
287 \param x The word to be checked.
288 \return 1 for odd, or 0 for even. */
289 static __inline__ int parity16(uint16_t x)
290 {
291 x ^= (x >> 8);
292 x = (x ^ (x >> 4)) & 0x0F;
293 return (0x6996 >> x) & 1;
294 }
295 /*- End of function --------------------------------------------------------*/
296
297 /*! \brief Find the parity of a 32 bit word.
298 \param x The word to be checked.
299 \return 1 for odd, or 0 for even. */
300 static __inline__ int parity32(uint32_t x)
301 {
302 x ^= (x >> 16);
303 x ^= (x >> 8);
304 x = (x ^ (x >> 4)) & 0x0F;
305 return (0x6996 >> x) & 1;
306 }
307 /*- End of function --------------------------------------------------------*/
308
309 #if defined(__cplusplus)
310 }
311 #endif
312
313 #endif
314 /*- End of file ------------------------------------------------------------*/

Repositories maintained by Peter Meerwald, pmeerw@pmeerw.net.