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