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)
38extern "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. */
45static __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. */
144static __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. */
192static __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. */
209SPAN_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. */
214SPAN_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. */
219SPAN_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. */
225SPAN_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. */
232SPAN_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. */
237SPAN_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. */
242SPAN_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. */
247SPAN_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. */
253static __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. */
263static __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. */
277static __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. */
287static __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. */
298static __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 ------------------------------------------------------------*/
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