---

GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> EDS / V2-10-2 > ebfio / mv2304

---

         

---

FFS.h File Reference

Provides the interface and implementation of the Find First Set routines. More...

#include "EDS/impl/FFS.xx-xxx-xxx.h"

Functions
static __inline int	FFS (unsigned int word)
	Finds the first set bit (MSB = bit 0) in a 32-bit word.
static __inline unsigned int	FFS_eliminate (unsigned int word, int bit)
	Eliminates the specified bit, bit from word.
static __inline unsigned int	FFS_mask (int bit)
	Converts the bit to a bit mask.
static __inline unsigned int	FFS_insert (unsigned int word, int bit)
	Inserts the specified bit, bit into word.

---

Detailed Description

Provides the interface and implementation of the Find First Set routines.

Author:

JJRussell - russell@slac.stanford.edu

  CVS $Id: FFS.h,v 1.3 2005/10/13 22:00:55 russell Exp $

ABSTRACt

This facility provides the interface and implementation of the Find First Set routines. These routines provide a machine independent interface to a machine dependent implementation to find the first set bit in a 32 bit word. On most machines, this consists of a single machine instruction

USAGE

Two routines are provided, FFS() and FFS_eliminate(). These routines find and then eliminate the first set bit in a 32 bit word.

Example

As example, consider counting the number of set bits in a 32-bit word.

     int count_bits (unsigned int word)
     {
        int cnt = 0;
        while (word)
        {
            int bit;
            bit  = FFS (word);
            cnt += 1;
            word = FFS_eliminate (word, bit);
        }
        return cnt;
     }

---

Function Documentation

int FFS

(

unsigned int

word

)

[static]

Finds the first set bit (MSB = bit 0) in a 32-bit word.

Returns:

Returns the bit number of the first set bit

Overview

This routine scans a 32 bit longword from left (MSB) to right (LSB) looking for the first bit set. If it finds a bit it returns a value in the range 0-31. The routine is not protected against 0 as an input and the result is undefined.

PPC Implementation

On the PowerPCs, this is a direct map to the PPC instruction 'cntlz', count leading zeros.

X86 Implementation

The Intel implementation is an 'bsr' instruction with the bit numbers reversed to match a big endian machine.

Generic

The generic implementation is a straighforward piece of C code, that scans MSB to LSB for the first set bit.

static __inline unsigned int FFS_eliminate	(	unsigned int	word,
		int	bit
	)			[static]

Eliminates the specified bit, bit from word.

Returns:

The value of the input word with the specified bit eliminated.

Parameters:

	word	The word to eliminate the bit from
	bit	The bit (MSB = 0) to eliminate

This is merely a convenience routine. Nothing fancy is going on here, just a straightforward elimination of the specified bit using a mask operation. It is provided to eliminate the inevitable mistake of misspecifying the mask word (0x80000000 >> bit), for instance by omitting one of the trailing 0's. That kind of mistake is almost impossible to spot.

int FFS_insert	(	unsigned int	word,
		int	bit
	)			[static]

Inserts the specified bit, bit into word.

Returns:

The value of the input word with the specified bit inserted

Parameters:

	word	The word to insert the bit into
	bit	The bit (MSB = 0) to add

This is merely a convenience routine. Nothing fancy is going on here, just a straightforward insertion of the specified bit using an OR operation. It is provided to eliminate the inevitable mistake of misspecifying the mask word (0x80000000 >> bit), for instance by omitting one of the trailing 0's. That kind of mistake is almost impossible to spot.

static __inline unsigned int FFS_mask

(

int

bit

)

[static]

Converts the bit to a bit mask.

Returns:

A 32 bit value with the specified bit set (MSB = bit 0)

Parameters:

bit

The bit (MSB = 0) to set.

Nothing fancy, this routine exists for consistency across the FFS routines.

---