RTEMS 4.6.1 On-Line Library

Priority Bitmap Manipulation Find First Bit Routine

RTEMS Porting Guide

8.3: Find First Bit Routine

The _CPU_Bitfield_Find_first_bit routine sets _output to the bit number of the first bit set in _value. _value is of CPU dependent type Priority_Bit_map_control. A stub version of this routine is as follows:

#define _CPU_Bitfield_Find_first_bit( _value, _output ) \
  { \
    (_output) = 0;   /* do something to prevent warnings */ \
  }

There are a number of variables in using a "find first bit" type instruction.

What happens when run on a value of zero?
Bits may be numbered from MSB to LSB or vice-versa.
The numbering may be zero or one based.
The "find first bit" instruction may search from MSB or LSB.

RTEMS guarantees that (1) will never happen so it is not a concern. Cases (2),(3), (4) are handled by the macros _CPU_Priority_mask() and _CPU_Priority_bits_index(). These three form a set of routines which must logically operate together. Bits in the _value are set and cleared based on masks built by CPU_Priority_mask(). The basic major and minor values calculated by _Priority_Major() and _Priority_Minor() are "massaged" by _CPU_Priority_bits_index() to properly range between the values returned by the "find first bit" instruction. This makes it possible for _Priority_Get_highest() to calculate the major and directly index into the minor table. This mapping is necessary to ensure that 0 (a high priority major/minor) is the first bit found.

This entire "find first bit" and mapping process depends heavily on the manner in which a priority is broken into a major and minor components with the major being the 4 MSB of a priority and minor the 4 LSB. Thus (0 << 4) + 0 corresponds to priority 0 -- the highest priority. And (15 << 4) + 14 corresponds to priority 254 -- the next to the lowest priority.

If your CPU does not have a "find first bit" instruction, then there are ways to make do without it. Here are a handful of ways to implement this in software:

a series of 16 bit test instructions
a "binary search using if's"

the following algorithm based upon a 16 entry lookup table. In this pseudo-code, bit_set_table[16] has values which indicate the first bit set:

_number = 0 if _value > 0x00ff
     _value >>=8
     _number = 8;
 if _value > 0x0000f
     _value >=8
     _number += 4

_number += bit_set_table[ _value ]

The following illustrates how the CPU_USE_GENERIC_BITFIELD_CODE macro may be so the port can use the generic implementation of this bitfield code. This can be used temporarily during the porting process to avoid writing these routines until the end. This results in a functional although lower performance port. This is perfectly acceptable during development and testing phases.

#define CPU_USE_GENERIC_BITFIELD_CODE TRUE
#define CPU_USE_GENERIC_BITFIELD_DATA TRUE

Eventually, CPU specific implementations of these routines are usually written since they dramatically impact the performance of blocking operations. However they may take advantage of instructions which are not available on all models in the CPU family. In this case, one might find something like this stub example did:

#if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE)
#define _CPU_Bitfield_Find_first_bit( _value, _output ) \
  { \
    (_output) = 0;   /* do something to prevent warnings */ \
  }
#endif

RTEMS Porting Guide