446 lines
10 KiB
C
446 lines
10 KiB
C
/*****************************************************************************/
|
|
/**
|
|
* \file
|
|
* \brief bit manipulation functions
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \date 07/03/2001
|
|
* \author Lars Reuther <reuther@os.inf.tu-dresden.de> */
|
|
/*
|
|
* (c) 2000-2009 Author(s)
|
|
* economic rights: Technische Universität Dresden (Germany)
|
|
* This file is part of TUD:OS and distributed under the terms of the
|
|
* GNU Lesser General Public License 2.1.
|
|
* Please see the COPYING-LGPL-2.1 file for details.
|
|
*/
|
|
|
|
/*****************************************************************************/
|
|
#ifndef __L4UTIL__INCLUDE__BITOPS_H__
|
|
#define __L4UTIL__INCLUDE__BITOPS_H__
|
|
|
|
/* L4 includes */
|
|
#include <l4/sys/l4int.h>
|
|
#include <l4/sys/compiler.h>
|
|
|
|
/** define some more usual names */
|
|
#define l4util_test_and_clear_bit(b, dest) l4util_btr(b, dest)
|
|
#define l4util_test_and_set_bit(b, dest) l4util_bts(b, dest)
|
|
#define l4util_test_and_change_bit(b, dest) l4util_btc(b, dest)
|
|
#define l4util_log2(word) l4util_bsr(word)
|
|
|
|
/*****************************************************************************
|
|
*** Prototypes
|
|
*****************************************************************************/
|
|
|
|
EXTERN_C_BEGIN
|
|
|
|
/**
|
|
* \defgroup l4util_bitops Bit Manipulation
|
|
* \ingroup l4util_api
|
|
*/
|
|
|
|
/**
|
|
* \brief Set bit in memory
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*/
|
|
L4_INLINE void
|
|
l4util_set_bit(int b, volatile l4_umword_t * dest);
|
|
|
|
L4_INLINE void
|
|
l4util_set_bit32(int b, volatile l4_uint32_t * dest);
|
|
|
|
#if L4_MWORD_BITS >= 64
|
|
L4_INLINE void
|
|
l4util_set_bit64(int b, volatile l4_uint64_t * dest);
|
|
#endif
|
|
|
|
/**
|
|
* \brief Clear bit in memory
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*/
|
|
L4_INLINE void
|
|
l4util_clear_bit(int b, volatile l4_umword_t * dest);
|
|
|
|
L4_INLINE void
|
|
l4util_clear_bit32(int b, volatile l4_uint32_t * dest);
|
|
|
|
#if L4_MWORD_BITS >= 64
|
|
L4_INLINE void
|
|
l4util_clear_bit64(int b, volatile l4_uint64_t * dest);
|
|
#endif
|
|
|
|
/**
|
|
* \brief Complement bit in memory
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*/
|
|
L4_INLINE void
|
|
l4util_complement_bit(int b, volatile l4_umword_t * dest);
|
|
|
|
/**
|
|
* \brief Test bit (return value of bit)
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*
|
|
* \return Value of bit \em b.
|
|
*/
|
|
L4_INLINE int
|
|
l4util_test_bit(int b, const volatile l4_umword_t * dest);
|
|
|
|
L4_INLINE int
|
|
l4util_test_bit32(int b, const volatile l4_uint32_t * dest);
|
|
|
|
#if L4_MWORD_BITS >= 64
|
|
L4_INLINE int
|
|
l4util_test_bit64(int b, const volatile l4_uint64_t * dest);
|
|
#endif
|
|
|
|
/**
|
|
* \brief Bit test and set
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*
|
|
* \return Old value of bit \em b.
|
|
*
|
|
* Set the \em b bit of \em dest to 1 and return the old value.
|
|
*/
|
|
L4_INLINE int
|
|
l4util_bts(int b, volatile l4_umword_t * dest);
|
|
|
|
/**
|
|
* \brief Bit test and reset
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*
|
|
* \return Old value of bit \em b.
|
|
*
|
|
* Reset bit \em b and return old value.
|
|
*/
|
|
L4_INLINE int
|
|
l4util_btr(int b, volatile l4_umword_t * dest);
|
|
|
|
/**
|
|
* \brief Bit test and complement
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param b bit position
|
|
* \param dest destination operand
|
|
*
|
|
* \return Old value of bit \em b.
|
|
*
|
|
* Complement bit \em b and return old value.
|
|
*/
|
|
L4_INLINE int
|
|
l4util_btc(int b, volatile l4_umword_t * dest);
|
|
|
|
/**
|
|
* \brief Bit scan reverse
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param word value (machine size)
|
|
*
|
|
* \return index of most significant set bit in word,
|
|
* -1 if no bit is set (word == 0)
|
|
*
|
|
* "bit scan reverse", find most significant set bit in word (-> LOG2(word))
|
|
*/
|
|
L4_INLINE int
|
|
l4util_bsr(l4_umword_t word);
|
|
|
|
/**
|
|
* \brief Bit scan forward
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param word value (machine size)
|
|
*
|
|
* \return index of least significant bit set in word,
|
|
* -1 if no bit is set (word == 0)
|
|
*
|
|
* "bit scan forward", find least significant bit set in word.
|
|
*/
|
|
L4_INLINE int
|
|
l4util_bsf(l4_umword_t word);
|
|
|
|
/**
|
|
* \brief Find the first set bit in a memory region
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param dest bit string
|
|
* \param size size of string in bits (must be a multiple of 32!)
|
|
*
|
|
* \return number of the first set bit,
|
|
* >= size if no bit is set
|
|
*/
|
|
L4_INLINE int
|
|
l4util_find_first_set_bit(const void * dest, l4_size_t size);
|
|
|
|
/**
|
|
* \brief Find the first zero bit in a memory region
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param dest bit string
|
|
* \param size size of string in bits (must be a multiple of 32!)
|
|
*
|
|
* \return number of the first zero bit,
|
|
* >= size if no bit is set
|
|
*/
|
|
L4_INLINE int
|
|
l4util_find_first_zero_bit(const void * dest, l4_size_t size);
|
|
|
|
|
|
/**
|
|
* \brief Find the next power of 2 for a given number.
|
|
* \ingroup l4util_bitops
|
|
*
|
|
* \param val initial value
|
|
*
|
|
* \return next-highest power of 2
|
|
*/
|
|
L4_INLINE int
|
|
l4util_next_power2(const unsigned long val);
|
|
|
|
EXTERN_C_END
|
|
|
|
/*****************************************************************************
|
|
*** Implementation of specific version
|
|
*****************************************************************************/
|
|
|
|
#include <l4/util/bitops_arch.h>
|
|
|
|
/*****************************************************************************
|
|
*** Generic implementations
|
|
*****************************************************************************/
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_SET_BIT
|
|
#include <l4/util/atomic.h>
|
|
L4_INLINE void
|
|
l4util_set_bit(int b, volatile l4_umword_t * dest)
|
|
{
|
|
l4_umword_t oldval, newval;
|
|
|
|
dest += b / (sizeof(*dest) * 8); /* advance dest to the proper element */
|
|
b &= sizeof(*dest) * 8 - 1; /* modulo; cut off all upper bits */
|
|
|
|
do
|
|
{
|
|
oldval = *dest;
|
|
newval = oldval | (1 << b);
|
|
}
|
|
while (!l4util_cmpxchg(dest, oldval, newval));
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_CLEAR_BIT
|
|
#include <l4/util/atomic.h>
|
|
L4_INLINE void
|
|
l4util_clear_bit(int b, volatile l4_umword_t * dest)
|
|
{
|
|
l4_umword_t oldval, newval;
|
|
|
|
dest += b / (sizeof(*dest) * 8);
|
|
b &= sizeof(*dest) * 8 - 1;
|
|
|
|
do
|
|
{
|
|
oldval = *dest;
|
|
newval = oldval & ~(1 << b);
|
|
}
|
|
while (!l4util_cmpxchg(dest, oldval, newval));
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_TEST_BIT
|
|
L4_INLINE int
|
|
l4util_test_bit(int b, const volatile l4_umword_t * dest)
|
|
{
|
|
dest += b / (sizeof(*dest) * 8);
|
|
b &= sizeof(*dest) * 8 - 1;
|
|
|
|
return (*dest >> b) & 1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_TEST_BIT32
|
|
L4_INLINE int
|
|
l4util_test_bit32(int b, const volatile l4_uint32_t * dest)
|
|
{
|
|
dest += b / (sizeof(*dest) * 8);
|
|
b &= sizeof(*dest) * 8 - 1;
|
|
|
|
return (*dest >> b) & 1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_SET
|
|
#include <l4/util/atomic.h>
|
|
L4_INLINE int
|
|
l4util_bts(int b, volatile l4_umword_t * dest)
|
|
{
|
|
l4_umword_t oldval, newval;
|
|
|
|
dest += b / (sizeof(*dest) * 8);
|
|
b &= sizeof(*dest) * 8 - 1;
|
|
|
|
do
|
|
{
|
|
oldval = *dest;
|
|
newval = oldval | (1 << b);
|
|
}
|
|
while (!l4util_cmpxchg(dest, oldval, newval));
|
|
|
|
/* Return old bit */
|
|
return (oldval >> b) & 1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_RESET
|
|
#include <l4/util/atomic.h>
|
|
L4_INLINE int
|
|
l4util_btr(int b, volatile l4_umword_t * dest)
|
|
{
|
|
l4_umword_t oldval, newval;
|
|
|
|
dest += b / (sizeof(*dest) * 8);
|
|
b &= sizeof(*dest) * 8 - 1;
|
|
|
|
do
|
|
{
|
|
oldval = *dest;
|
|
newval = oldval & ~(1 << b);
|
|
}
|
|
while (!l4util_cmpxchg(dest, oldval, newval));
|
|
|
|
/* Return old bit */
|
|
return (oldval >> b) & 1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_SCAN_REVERSE
|
|
L4_INLINE int
|
|
l4util_bsr(l4_umword_t word)
|
|
{
|
|
int i;
|
|
|
|
if (!word)
|
|
return -1;
|
|
|
|
for (i = 8 * sizeof(word) - 1; i >= 0; i--)
|
|
if ((1 << i) & word)
|
|
return i;
|
|
|
|
return -1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_SCAN_FORWARD
|
|
L4_INLINE int
|
|
l4util_bsf(l4_umword_t word)
|
|
{
|
|
unsigned int i;
|
|
|
|
if (!word)
|
|
return -1;
|
|
|
|
for (i = 0; i < sizeof(word) * 8; i++)
|
|
if ((1 << i) & word)
|
|
return i;
|
|
|
|
return -1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_FIND_FIRST_ZERO_BIT
|
|
L4_INLINE int
|
|
l4util_find_first_zero_bit(const void * dest, l4_size_t size)
|
|
{
|
|
l4_size_t i, j;
|
|
unsigned long *v = (unsigned long*)dest;
|
|
|
|
if (!size)
|
|
return 0;
|
|
|
|
size = (size + 31) & ~0x1f; /* Grmbl: adapt to x86 implementation... */
|
|
|
|
for (i = j = 0; i < size; i++, j++)
|
|
{
|
|
if (j >= sizeof(*v) * 8)
|
|
{
|
|
j = 0;
|
|
v++;
|
|
}
|
|
if (!((1 << j) & *v))
|
|
return i;
|
|
}
|
|
return size + 1;
|
|
}
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_COMPLEMENT_BIT
|
|
L4_INLINE void
|
|
l4util_complement_bit(int b, volatile l4_umword_t * dest)
|
|
{
|
|
dest += b / (sizeof(*dest) * 8);
|
|
b &= sizeof(*dest) * 8 - 1;
|
|
|
|
*dest ^= 1UL << b;
|
|
}
|
|
#endif
|
|
|
|
/*
|
|
* Adapted from:
|
|
* http://en.wikipedia.org/wiki/Power_of_two#Algorithm_to_find_the_next-highest_power_of_two
|
|
*/
|
|
L4_INLINE int
|
|
l4util_next_power2(unsigned long val)
|
|
{
|
|
unsigned i;
|
|
|
|
if (val == 0)
|
|
return 1;
|
|
|
|
val--;
|
|
for (i=1; i < sizeof(unsigned long)*8; i<<=1)
|
|
val = val | val >> i;
|
|
|
|
return val+1;
|
|
}
|
|
|
|
|
|
/* Non-implemented version, catch with a linker warning */
|
|
|
|
extern int __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(void);
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_CLEAR_BIT32
|
|
L4_INLINE void
|
|
l4util_clear_bit32(int b, volatile l4_uint32_t * dest)
|
|
{ (void)b; (void)dest; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); }
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_BIT_TEST_AND_COMPLEMENT
|
|
L4_INLINE int
|
|
l4util_btc(int b, volatile l4_umword_t * dest)
|
|
{ (void)b; (void)dest; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); return 0; }
|
|
#endif
|
|
|
|
#ifndef __L4UTIL_BITOPS_HAVE_ARCH_FIND_FIRST_SET_BIT
|
|
L4_INLINE int
|
|
l4util_find_first_set_bit(const void * dest, l4_size_t size)
|
|
{ (void)dest; (void)size; __this_l4util_bitops_function_is_not_implemented_for_this_arch__sorry(); return 0; }
|
|
#endif
|
|
|
|
#endif /* ! __L4UTIL__INCLUDE__BITOPS_H__ */
|