L4Re - L4 Runtime Environment
bitops.h
Go to the documentation of this file.
1 /*****************************************************************************/
9 /*
10  * (c) 2000-2009 Author(s)
11  * economic rights: Technische Universit├Ąt Dresden (Germany)
12  * This file is part of TUD:OS and distributed under the terms of the
13  * GNU Lesser General Public License 2.1.
14  * Please see the COPYING-LGPL-2.1 file for details.
15  */
16 
17 /*****************************************************************************/
18 #ifndef __L4UTIL__INCLUDE__BITOPS_H__
19 #define __L4UTIL__INCLUDE__BITOPS_H__
20 
21 /* L4 includes */
22 #include <l4/sys/l4int.h>
23 #include <l4/sys/compiler.h>
24 
26 #define l4util_test_and_clear_bit(b, dest) l4util_btr(b, dest)
27 #define l4util_test_and_set_bit(b, dest) l4util_bts(b, dest)
28 #define l4util_test_and_change_bit(b, dest) l4util_btc(b, dest)
29 #define l4util_log2(word) l4util_bsr(word)
30 
31 /*****************************************************************************
32  *** Prototypes
33  *****************************************************************************/
34 
36 
49 L4_INLINE void
50 l4util_set_bit(int b, volatile l4_umword_t * dest);
51 
59 L4_INLINE void
60 l4util_clear_bit(int b, volatile l4_umword_t * dest);
61 
69 L4_INLINE void
70 l4util_complement_bit(int b, volatile l4_umword_t * dest);
71 
81 L4_INLINE int
82 l4util_test_bit(int b, const volatile l4_umword_t * dest);
83 
95 L4_INLINE int
96 l4util_bts(int b, volatile l4_umword_t * dest);
97 
109 L4_INLINE int
110 l4util_btr(int b, volatile l4_umword_t * dest);
111 
123 L4_INLINE int
124 l4util_btc(int b, volatile l4_umword_t * dest);
125 
137 L4_INLINE int
138 l4util_bsr(l4_umword_t word);
139 
151 L4_INLINE int
152 l4util_bsf(l4_umword_t word);
153 
164 L4_INLINE int
165 l4util_find_first_set_bit(const void * dest, l4_size_t size);
166 
177 L4_INLINE int
178 l4util_find_first_zero_bit(const void * dest, l4_size_t size);
179 
180 
189 L4_INLINE int
190 l4util_next_power2(const unsigned long val);
191 
193 
194 /*****************************************************************************
195  *** Implementation of specific version
196  *****************************************************************************/
197 
198 #include <l4/util/bitops_arch.h>
199 
200 /*****************************************************************************
201  *** Generic implementations
202  *****************************************************************************/
203 
204 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_SET_BIT
205 #include <l4/util/atomic.h>
206 L4_INLINE void
207 l4util_set_bit(int b, volatile l4_umword_t * dest)
208 {
209  l4_umword_t oldval, newval;
210 
211  dest += b / (sizeof(*dest) * 8); /* advance dest to the proper element */
212  b &= sizeof(*dest) * 8 - 1; /* modulo; cut off all upper bits */
213 
214  do
215  {
216  oldval = *dest;
217  newval = oldval | (1UL << b);
218  }
219  while (!l4util_cmpxchg(dest, oldval, newval));
220 }
221 #endif
222 
223 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_CLEAR_BIT
224 #include <l4/util/atomic.h>
225 L4_INLINE void
226 l4util_clear_bit(int b, volatile l4_umword_t * dest)
227 {
228  l4_umword_t oldval, newval;
229 
230  dest += b / (sizeof(*dest) * 8);
231  b &= sizeof(*dest) * 8 - 1;
232 
233  do
234  {
235  oldval = *dest;
236  newval = oldval & ~(1UL << b);
237  }
238  while (!l4util_cmpxchg(dest, oldval, newval));
239 }
240 #endif
241 
242 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_TEST_BIT
243 L4_INLINE int
244 l4util_test_bit(int b, const volatile l4_umword_t * dest)
245 {
246  dest += b / (sizeof(*dest) * 8);
247  b &= sizeof(*dest) * 8 - 1;
248 
249  return (*dest >> b) & 1;
250 }
251 #endif
252 
253 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_SET
254 #include <l4/util/atomic.h>
255 L4_INLINE int
256 l4util_bts(int b, volatile l4_umword_t * dest)
257 {
258  l4_umword_t oldval, newval;
259 
260  dest += b / (sizeof(*dest) * 8);
261  b &= sizeof(*dest) * 8 - 1;
262 
263  do
264  {
265  oldval = *dest;
266  newval = oldval | (1UL << b);
267  }
268  while (!l4util_cmpxchg(dest, oldval, newval));
269 
270  /* Return old bit */
271  return (oldval >> b) & 1;
272 }
273 #endif
274 
275 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_RESET
276 #include <l4/util/atomic.h>
277 L4_INLINE int
278 l4util_btr(int b, volatile l4_umword_t * dest)
279 {
280  l4_umword_t oldval, newval;
281 
282  dest += b / (sizeof(*dest) * 8);
283  b &= sizeof(*dest) * 8 - 1;
284 
285  do
286  {
287  oldval = *dest;
288  newval = oldval & ~(1UL << b);
289  }
290  while (!l4util_cmpxchg(dest, oldval, newval));
291 
292  /* Return old bit */
293  return (oldval >> b) & 1;
294 }
295 #endif
296 
297 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_SCAN_REVERSE
298 L4_INLINE int
300 {
301  int i;
302 
303  if (!word)
304  return -1;
305 
306  for (i = 8 * sizeof(word) - 1; i >= 0; i--)
307  if ((1UL << i) & word)
308  return i;
309 
310  return -1;
311 }
312 #endif
313 
314 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_SCAN_FORWARD
315 L4_INLINE int
317 {
318  unsigned int i;
319 
320  if (!word)
321  return -1;
322 
323  for (i = 0; i < sizeof(word) * 8; i++)
324  if ((1UL << i) & word)
325  return i;
326 
327  return -1;
328 }
329 #endif
330 
331 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_FIND_FIRST_ZERO_BIT
332 L4_INLINE int
333 l4util_find_first_zero_bit(const void * dest, l4_size_t size)
334 {
335  l4_size_t i, j;
336  unsigned long *v = (unsigned long*)dest;
337 
338  if (!size)
339  return 0;
340 
341  size = (size + 31) & ~0x1f; /* Grmbl: adapt to x86 implementation... */
342 
343  for (i = j = 0; i < size; i++, j++)
344  {
345  if (j >= sizeof(*v) * 8)
346  {
347  j = 0;
348  v++;
349  }
350  if (!((1UL << j) & *v))
351  return i;
352  }
353  return size + 1;
354 }
355 #endif
356 
357 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_COMPLEMENT_BIT
358 L4_INLINE void
359 l4util_complement_bit(int b, volatile l4_umword_t * dest)
360 {
361  dest += b / (sizeof(*dest) * 8);
362  b &= sizeof(*dest) * 8 - 1;
363 
364  *dest ^= 1UL << b;
365 }
366 #endif
367 
368 /*
369  * Adapted from:
370  * http://en.wikipedia.org/wiki/Power_of_two#Algorithm_to_find_the_next-highest_power_of_two
371  */
372 L4_INLINE int
373 l4util_next_power2(unsigned long val)
374 {
375  unsigned i;
376 
377  if (val == 0)
378  return 1;
379 
380  val--;
381  for (i=1; i < sizeof(unsigned long)*8; i<<=1)
382  val = val | val >> i;
383 
384  return val+1;
385 }
386 
387 
388 /* Non-implemented version, catch with a linker warning */
389 
390 extern int __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(void);
391 
392 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_COMPLEMENT
393 L4_INLINE int
394 l4util_btc(int b, volatile l4_umword_t * dest)
395 { (void)b; (void)dest; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); return 0; }
396 #endif
397 
398 #ifndef __L4UTIL_BITOPS_HAVE_ARCH_FIND_FIRST_SET_BIT
399 L4_INLINE int
400 l4util_find_first_set_bit(const void * dest, l4_size_t size)
401 { (void)dest; (void)size; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); return 0; }
402 #endif
403 
404 #endif /* ! __L4UTIL__INCLUDE__BITOPS_H__ */
unsigned int l4_size_t
Unsigned size type.
Definition: l4int.h:35
int l4util_test_bit(int b, const volatile l4_umword_t *dest)
Test bit (return value of bit)
Definition: bitops.h:244
#define EXTERN_C_END
End section with C types and functions.
Definition: compiler.h:187
int l4util_btc(int b, volatile l4_umword_t *dest)
Bit test and complement.
Definition: bitops.h:394
int l4util_cmpxchg(volatile l4_umword_t *dest, l4_umword_t cmp_val, l4_umword_t new_val)
Atomic compare and exchange (machine wide fields)
Definition: atomic.h:335
L4 compiler related defines.
int l4util_next_power2(const unsigned long val)
Find the next power of 2 for a given number.
Definition: bitops.h:373
int l4util_btr(int b, volatile l4_umword_t *dest)
Bit test and reset.
Definition: bitops.h:278
atomic operations header and generic implementations
int l4util_find_first_zero_bit(const void *dest, l4_size_t size)
Find the first zero bit in a memory region.
Definition: bitops.h:333
void l4util_complement_bit(int b, volatile l4_umword_t *dest)
Complement bit in memory.
Definition: bitops.h:359
int l4util_bsf(l4_umword_t word)
Bit scan forward.
Definition: bitops.h:316
void l4util_set_bit(int b, volatile l4_umword_t *dest)
Set bit in memory.
Definition: bitops.h:207
unsigned long l4_umword_t
Unsigned machine word.
Definition: l4int.h:52
#define EXTERN_C_BEGIN
Start section with C types and functions.
Definition: compiler.h:186
int l4util_bts(int b, volatile l4_umword_t *dest)
Bit test and set.
Definition: bitops.h:256
int l4util_find_first_set_bit(const void *dest, l4_size_t size)
Find the first set bit in a memory region.
Definition: bitops.h:400
void l4util_clear_bit(int b, volatile l4_umword_t *dest)
Clear bit in memory.
Definition: bitops.h:226
int l4util_bsr(l4_umword_t word)
Bit scan reverse.
Definition: bitops.h:299