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)
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(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. */
151static __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. */
199static __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. */
216SPAN_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. */
221SPAN_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. */
226SPAN_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. */
232SPAN_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. */
239SPAN_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. */
244SPAN_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. */
249SPAN_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. */
254SPAN_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. */
260static __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. */
270static __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. */
284static __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. */
294static __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. */
305static __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:163
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:174
int one_bits32(uint32_t x)
Find the number of set bits in a 32 bit word.
Definition bit_operations.c:143
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