L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
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
49L4_INLINE void
50l4util_set_bit(int b, volatile l4_umword_t * dest);
51
59L4_INLINE void
60l4util_clear_bit(int b, volatile l4_umword_t * dest);
61
69L4_INLINE void
70l4util_complement_bit(int b, volatile l4_umword_t * dest);
71
81L4_INLINE int
82l4util_test_bit(int b, const volatile l4_umword_t * dest);
83
95L4_INLINE int
96l4util_bts(int b, volatile l4_umword_t * dest);
97
109L4_INLINE int
110l4util_btr(int b, volatile l4_umword_t * dest);
111
123L4_INLINE int
124l4util_btc(int b, volatile l4_umword_t * dest);
125
137L4_INLINE int
139
151L4_INLINE int
153
165L4_INLINE int
166l4util_find_first_set_bit(const void * dest, l4_size_t size);
167
179L4_INLINE int
180l4util_find_first_zero_bit(const void * dest, l4_size_t size);
181
182
191L4_INLINE int
192l4util_next_power2(unsigned long val);
193
195
196/*****************************************************************************
197 *** Implementation of specific version
198 *****************************************************************************/
199
200#include <l4/util/bitops_arch.h>
201
202/*****************************************************************************
203 *** Generic implementations
204 *****************************************************************************/
205
206#ifndef __L4UTIL_BITOPS_HAVE_ARCH_SET_BIT
207#include <l4/util/atomic.h>
208L4_INLINE void
209l4util_set_bit(int b, volatile l4_umword_t * dest)
210{
211 l4_umword_t oldval, newval;
212
213 dest += b / (sizeof(*dest) * 8); /* advance dest to the proper element */
214 b &= sizeof(*dest) * 8 - 1; /* modulo; cut off all upper bits */
215
216 do
217 {
218 oldval = *dest;
219 newval = oldval | (1UL << b);
220 }
221 while (!l4util_cmpxchg(dest, oldval, newval));
222}
223#endif
224
225#ifndef __L4UTIL_BITOPS_HAVE_ARCH_CLEAR_BIT
226#include <l4/util/atomic.h>
227L4_INLINE void
228l4util_clear_bit(int b, volatile l4_umword_t * dest)
229{
230 l4_umword_t oldval, newval;
231
232 dest += b / (sizeof(*dest) * 8);
233 b &= sizeof(*dest) * 8 - 1;
234
235 do
236 {
237 oldval = *dest;
238 newval = oldval & ~(1UL << b);
239 }
240 while (!l4util_cmpxchg(dest, oldval, newval));
241}
242#endif
243
244#ifndef __L4UTIL_BITOPS_HAVE_ARCH_TEST_BIT
245L4_INLINE int
246l4util_test_bit(int b, const volatile l4_umword_t * dest)
247{
248 dest += b / (sizeof(*dest) * 8);
249 b &= sizeof(*dest) * 8 - 1;
250
251 return (*dest >> b) & 1;
252}
253#endif
254
255#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_SET
256#include <l4/util/atomic.h>
257L4_INLINE int
258l4util_bts(int b, volatile l4_umword_t * dest)
259{
260 l4_umword_t oldval, newval;
261
262 dest += b / (sizeof(*dest) * 8);
263 b &= sizeof(*dest) * 8 - 1;
264
265 do
266 {
267 oldval = *dest;
268 newval = oldval | (1UL << b);
269 }
270 while (!l4util_cmpxchg(dest, oldval, newval));
271
272 /* Return old bit */
273 return (oldval >> b) & 1;
274}
275#endif
276
277#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_RESET
278#include <l4/util/atomic.h>
279L4_INLINE int
280l4util_btr(int b, volatile l4_umword_t * dest)
281{
282 l4_umword_t oldval, newval;
283
284 dest += b / (sizeof(*dest) * 8);
285 b &= sizeof(*dest) * 8 - 1;
286
287 do
288 {
289 oldval = *dest;
290 newval = oldval & ~(1UL << b);
291 }
292 while (!l4util_cmpxchg(dest, oldval, newval));
293
294 /* Return old bit */
295 return (oldval >> b) & 1;
296}
297#endif
298
299#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_SCAN_REVERSE
300L4_INLINE int
302{
303 int i;
304
305 if (!word)
306 return -1;
307
308 for (i = 8 * sizeof(word) - 1; i >= 0; i--)
309 if ((1UL << i) & word)
310 return i;
311
312 __builtin_unreachable();
313}
314#endif
315
316#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_SCAN_FORWARD
317L4_INLINE int
319{
320 unsigned int i;
321
322 if (!word)
323 return -1;
324
325 for (i = 0; i < sizeof(word) * 8; i++)
326 if ((1UL << i) & word)
327 return i;
328
329 __builtin_unreachable();
330}
331#endif
332
333#ifndef __L4UTIL_BITOPS_HAVE_ARCH_FIND_FIRST_ZERO_BIT
334L4_INLINE int
335l4util_find_first_zero_bit(const void * dest, l4_size_t size)
336{
337 l4_size_t i, j;
338 unsigned long *v = (unsigned long*)dest;
339
340 if (!size)
341 return 0;
342
343 size = (size + 31) & ~0x1f; /* Grmbl: adapt to x86 implementation... */
344
345 for (i = j = 0; i < size; i++, j++)
346 {
347 if (j >= sizeof(*v) * 8)
348 {
349 j = 0;
350 v++;
351 }
352 if (!((1UL << j) & *v))
353 return i;
354 }
355 return size + 1;
356}
357#endif
358
359#ifndef __L4UTIL_BITOPS_HAVE_ARCH_COMPLEMENT_BIT
360L4_INLINE void
361l4util_complement_bit(int b, volatile l4_umword_t * dest)
362{
363 dest += b / (sizeof(*dest) * 8);
364 b &= sizeof(*dest) * 8 - 1;
365
366 *dest ^= 1UL << b;
367}
368#endif
369
370/*
371 * Adapted from:
372 * http://en.wikipedia.org/wiki/Power_of_two#Algorithm_to_find_the_next-highest_power_of_two
373 */
374L4_INLINE int
375l4util_next_power2(unsigned long val)
376{
377 unsigned i;
378
379 if (val == 0)
380 return 1;
381
382 val--;
383 for (i=1; i < sizeof(unsigned long)*8; i<<=1)
384 val = val | val >> i;
385
386 return val+1;
387}
388
389
390/* Non-implemented version, catch with a linker warning */
391
392extern int __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(void);
393
394#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_COMPLEMENT
395L4_INLINE int
396l4util_btc(int b, volatile l4_umword_t * dest)
397{ (void)b; (void)dest; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); return 0; }
398#endif
399
400#ifndef __L4UTIL_BITOPS_HAVE_ARCH_FIND_FIRST_SET_BIT
401L4_INLINE int
402l4util_find_first_set_bit(const void * dest, l4_size_t size)
403{ (void)dest; (void)size; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); return 0; }
404#endif
405
406#endif /* ! __L4UTIL__INCLUDE__BITOPS_H__ */
L4 compiler related defines.
unsigned int l4_size_t
Unsigned size type.
Definition l4int.h:35
unsigned long l4_umword_t
Unsigned machine word.
Definition l4int.h:51
#define L4_INLINE
L4 Inline function attribute.
Definition compiler.h:62
#define EXTERN_C_BEGIN
Start section with C types and functions.
Definition compiler.h:192
#define EXTERN_C_END
End section with C types and functions.
Definition compiler.h:193
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:381
void l4util_set_bit(int b, volatile l4_umword_t *dest)
Set bit in memory.
Definition bitops.h:209
int l4util_next_power2(unsigned long val)
Find the next power of 2 for a given number.
Definition bitops.h:375
int l4util_bsf(l4_umword_t word)
Bit scan forward.
Definition bitops.h:318
int l4util_btc(int b, volatile l4_umword_t *dest)
Bit test and complement.
Definition bitops.h:396
int l4util_bsr(l4_umword_t word)
Bit scan reverse.
Definition bitops.h:301
int l4util_btr(int b, volatile l4_umword_t *dest)
Bit test and reset.
Definition bitops.h:280
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:402
int l4util_bts(int b, volatile l4_umword_t *dest)
Bit test and set.
Definition bitops.h:258
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:335
void l4util_clear_bit(int b, volatile l4_umword_t *dest)
Clear bit in memory.
Definition bitops.h:228
int l4util_test_bit(int b, const volatile l4_umword_t *dest)
Test bit (return value of bit)
Definition bitops.h:246
void l4util_complement_bit(int b, volatile l4_umword_t *dest)
Complement bit in memory.
Definition bitops.h:361
atomic operations header and generic implementations