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