GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> IPBS / V0-0-2 > pbs / i845e

Interface   Data Structures   File List   Data Fields   Globals  
g » glast » flight » FES » source » IPBS » V0-0-2 » IPBS

FFS.ih File Reference

Find First (Last) Set Bit in a 32-bit word. More...

#include <PBI/Inline.h>
#include <PBI/Attribute.h>
#include <IPBS/impl/FFS.ih.xx-xxx-xxx>

Defines

#define FFS__LCL_PROTO   INLINE_USR_LCL_PROTO
 Inline definition for a static/local proto-type declaration.
#define FFS__LCL_FNC   INLINE_USR_LCL_FNC
 Inline definition for an static/local function declaration.

Functions

FFS__LCL_PROTO int FFSL (unsigned int w) ATTR_UNUSED_OK
 Find first leading set bit in a 32-bit word, MSb = 0.
FFS__LCL_PROTO int FFSl (unsigned int w) ATTR_UNUSED_OK
 Find first leading set bit in a 32-bit word, LSb = 0.
FFS__LCL_PROTO int FFST (unsigned int w) ATTR_UNUSED_OK
 Find first trailing set bit in a 32-bit word, MSb = 0.
FFS__LCL_PROTO int FFSt (unsigned int w) ATTR_UNUSED_OK
 Find first trailing set bit in a 32-bit word, LSb = 0.
FFS__LCL_PROTO int CNTLZ (unsigned int w) ATTR_UNUSED_OK
 Counts the number of leading 0's in a 32 bit word.
FFS__LCL_PROTO int CNTTZ (unsigned int w) ATTR_UNUSED_OK
 Counts the number of trailing 0's in a 32 bit word.
FFS__LCL_PROTO unsigned int FFSL_eliminate (unsigned int w, int bit) ATTR_UNUSED_OK
 Eliminates the bit, counting MSb = 0, in word w.
FFS__LCL_PROTO unsigned int FFSl_eliminate (unsigned int w, int bit) ATTR_UNUSED_OK
 Eliminates the bit, counting LSb = 0, in word w.
FFS__LCL_PROTO unsigned int FFST_eliminate (unsigned int w, int bit) ATTR_UNUSED_OK
 Eliminates the bit.
FFS__LCL_PROTO unsigned int FFSt_eliminate (unsigned int w, int bit) ATTR_UNUSED_OK
 Eliminates the bit, counting LSb = 0, in word w.

Detailed Description

Find First (Last) Set Bit in a 32-bit word.

Author:
JJRussell - russell@slac.stanford.edu

    CVS $Id: FFS.ih,v 1.2 2011/03/25 21:15:00 saxton Exp $

SYNOPSIS
This routine provides an efficient implementation to find the first leading or trailing bit set in a 32-bit word. There are six routines defined.

The convention is that the final letter designates whether the notional scan is a leading or trailing scan and whether the MSb or the LSb is designated as 0.

The interface is generic, but the implementation is machine and compiler dependent. The following table indicates on which platforms the routine maps into a single machine instruction

                PowerPC          Intel     All Others
       FFSL     cntlz         bsr ^ 31     C scan routine
       FFSl     FFSL ^ 31          bsr     C scan routine
       FFST     FFSL(x & -x)  bsf ^ 31     C scan routine
       FFSt     FFST ^ 31          bsf     C scan routine

The FFSL routine effectively counts the leading zeros, while the FFSt routine effectively counts the trailing zeros.

IMPLEMENTATION NOTE
Some implementation use the trick of preconditioning the input value (x => x & -x) to implement the trailing scan. This trick is courtesy of the fine 'gcc' folks. It takes a minute to understand how this works.

Consider an arbitrary word and first focus on the trailing bits. One a twos-complement machine, negation consists of first complementing the bits, then adding one. So, again thinking of the low order bits, the complement turns all the 0's to 1's and all the 1's to 0's. Imagine a string of 0's in the low order bits. These bits all turn to 1's under the complement. Adding 1's generates a 0 and a carry into the next bit until a 0 (which in the original un-complemented word was the first 1) is encountered. The bits above the first 1 are now the complement of the original pattern, so the 'and' operation eliminates these, leaving only one bit standing, the bit with the first one. One now just uses the FFSL to find this bit. It is a trivial manner to turn the result of FFSL to the correct result of FFSt (it is already the right answer for FFST).

Demonstration of the methodk
Consider a 32-bit number with the following 8 bits pattern in its least significant bits

     x:      10110100
    ~x:      01001011
    -x:      01001100
    x & -x:  00000100  <- Only bit left standing was the lowest order
                          bit with a 1 in it

Function Documentation

int CNTLZ ( unsigned int  w  ) 

Counts the number of leading 0's in a 32 bit word.

Parameters:
w The 32 bit word to be examined.
Returns:
The number of leading 0's in a 32 bit word.
This routine examines a 32 bit longword, returning the count of leading 0s (left (MSb) to right (LSb)) If it finds a bit it returns a value in the range 0-31. This routine is almost a synomyn for FFSL, but it is protected against 0, returning 32 if the word is 0.

References FFSL().

int CNTTZ ( unsigned int  w  ) 

Counts the number of trailing 0's in a 32 bit word.

Parameters:
w The 32 bit word to be examined.
Returns:
The number of trailing 0's in a 32 bit word.
This routine examines a 32 bit longword, returning the count of trailing 0s (left (MSb) to right (LSb)) If it finds a bit it returns a value in the range 0-31. This routine is almost a synomyn for FFSt, but it is protected against 0, returning 32 if the word is 0.

References FFSt().

int FFSl ( unsigned int  w  ) 

Find first leading set bit in a 32-bit word, LSb = 0.

Parameters:
w The 32 bit word to examined from the MSb to LSb for the first set bit.
Returns:
The number of the first set bit in w, where LSb = 0
This routine examines 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.

int FFSL ( unsigned int  w  ) 

Find first leading set bit in a 32-bit word, MSb = 0.

Parameters:
w The 32 bit word to examined from the MSb to LSb for the first set bit.
Returns:
The number of the first set bit in w, where MSb = 0
This routine examines 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.

Referenced by CNTLZ(), lsu__scale(), and lsu_calc().

FFS__LCL_FNC unsigned int FFSl_eliminate ( unsigned int  w,
int  bit 
)

Eliminates the bit, counting LSb = 0, in word w.

Returns:
The word with the bit eliminated
Parameters:
w The word to eliminate the bit from
bit The number of the bit (LSb = 0) to eliminate
This function is used in conjugation with FFSl. This is the same function as FFSt, but the code looks more consistent if the names match.

FFS__LCL_FNC unsigned int FFSL_eliminate ( unsigned int  w,
int  bit 
)

Eliminates the bit, counting MSb = 0, in word w.

Returns:
The word with the bit eliminated
Parameters:
w The word to eliminate the bit from
bit The number of the bit (MSb = 0) to eliminate
This function is used in conjugation with FFSL. This is the same function as FFST, but the code looks more consistent if the names match.

int FFSt ( unsigned int  w  ) 

Find first trailing set bit in a 32-bit word, LSb = 0.

Parameters:
w The 32 bit word to examined from the LSb to MSb for the first set bit.
Returns:
The number of the first set bit in w, where LSb = 0
This routine examines a 32 bit longword from right (MSb) to left (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.

Referenced by CNTTZ().

int FFST ( unsigned int  w  ) 

Find first trailing set bit in a 32-bit word, MSb = 0.

Parameters:
w The 32 bit word to examined from the LSb to MSb for the first set bit.
Returns:
The number of the first set bit in w, where MSb = 0
This routine examines a 32 bit longword from right (MSb) to left (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.

FFS__LCL_FNC unsigned int FFSt_eliminate ( unsigned int  w,
int  bit 
)

Eliminates the bit, counting LSb = 0, in word w.

Returns:
The word with the bit eliminated
Parameters:
w The word to eliminate the bit from
bit The number of the bit (LSb = 0) to eliminate
This function is used in conjugation with FFSt. This is the same function as FFSl, but the code looks more consistent if the names match.

FFS__LCL_FNC unsigned int FFST_eliminate ( unsigned int  w,
int  bit 
)

Eliminates the bit.

Returns:
The word with the bit eliminated
Parameters:
w The word to eliminate the bit from
bit The number of the bit (MSb = 0) to eliminate
This function is used in conjugation with FFST. This is the same function as FFSL, but the code looks more consistent if the names match.

Generated on Wed Nov 21 21:23:51 2012 by  doxygen 1.5.8