\hypertarget{FFS_8ih}{
\section{FFS.ih File Reference}
\label{FFS_8ih}\index{FFS.ih@{FFS.ih}}
}
Find First (Last) Set Bit in a 32-bit word.  


{\tt \#include \char`\"{}PBI/Inline.h\char`\"{}}\par
{\tt \#include \char`\"{}PBI/Attribute.h\char`\"{}}\par
{\tt \#include \char`\"{}PBS/impl/FFS.ih.xx-xxx-xxx\char`\"{}}\par


Include dependency graph for FFS.ih:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=186pt]{FFS_8ih__incl}
\end{center}
\end{figure}


This graph shows which files directly or indirectly include this file:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=81pt]{FFS_8ih__dep__incl}
\end{center}
\end{figure}
\subsection*{Defines}
\begin{CompactItemize}
\item 
\hypertarget{FFS_8ih_a0}{
\#define \hyperlink{FFS_8ih_a0}{FFS\_\-\_\-LCL\_\-PROTO}\ INLINE\_\-USR\_\-LCL\_\-PROTO}
\label{FFS_8ih_a0}

\begin{CompactList}\small\item\em Inline definition for a static/local proto-type declaration. \item\end{CompactList}\item 
\hypertarget{FFS_8ih_a1}{
\#define \hyperlink{FFS_8ih_a1}{FFS\_\-\_\-LCL\_\-FNC}\ INLINE\_\-USR\_\-LCL\_\-FNC}
\label{FFS_8ih_a1}

\begin{CompactList}\small\item\em Inline definition for an static/local function declaration. \item\end{CompactList}\end{CompactItemize}
\subsection*{Functions}
\begin{CompactItemize}
\item 
FFS\_\-\_\-LCL\_\-PROTO int \hyperlink{FFS_8ih_a2}{FFSL} (unsigned int w) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Find first leading set bit in a 32-bit word, MSb = 0. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO int \hyperlink{FFS_8ih_a3}{FFSl} (unsigned int w) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Find first leading set bit in a 32-bit word, LSb = 0. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO int \hyperlink{FFS_8ih_a4}{FFST} (unsigned int w) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Find first trailing set bit in a 32-bit word, MSb = 0. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO int \hyperlink{FFS_8ih_a5}{FFSt} (unsigned int w) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Find first trailing set bit in a 32-bit word, LSb = 0. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO int \hyperlink{FFS_8ih_a6}{CNTLZ} (unsigned int w) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Counts the number of leading 0's in a 32 bit word. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO int \hyperlink{FFS_8ih_a7}{CNTTZ} (unsigned int w) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Counts the number of trailing 0's in a 32 bit word. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO unsigned int \hyperlink{FFS_8ih_a8}{FFSL\_\-eliminate} (unsigned int w, int bit) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Eliminates the {\em bit\/}, counting MSb = 0, in word {\em w\/}. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO unsigned int \hyperlink{FFS_8ih_a9}{FFSl\_\-eliminate} (unsigned int w, int bit) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Eliminates the {\em bit\/}, counting LSb = 0, in word {\em w\/}. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO unsigned int \hyperlink{FFS_8ih_a10}{FFST\_\-eliminate} (unsigned int w, int bit) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Eliminates the {\em bit\/}. \item\end{CompactList}\item 
FFS\_\-\_\-LCL\_\-PROTO unsigned int \hyperlink{FFS_8ih_a11}{FFSt\_\-eliminate} (unsigned int w, int bit) ATTR\_\-UNUSED\_\-OK
\begin{CompactList}\small\item\em Eliminates the {\em bit\/}, counting LSb = 0, in word {\em w\/}. \item\end{CompactList}\end{CompactItemize}


\subsection{Detailed Description}
Find First (Last) Set Bit in a 32-bit word. 

\begin{Desc}
\item[Author:]JJRussell - \href{mailto:russell@slac.stanford.edu}{\tt russell@slac.stanford.edu}\end{Desc}


\footnotesize\begin{verbatim}

    CVS $Id: FFS.ih,v 1.3 2004/03/10 00:52:09 russell Exp $
\end{verbatim}\normalsize


{\bf SYNOPSIS} \par
 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.

\begin{itemize}
\item FFSL (w) - Find First Set Leading MSb = 0\item FFSl (w) - Find First Set leading LSb = 0\item FFST (w) - Find First Set Trailing MSb = 0\item FFSt (w) - Find First Set Trailing LSb = 0\item CNTLZ(w) - Count leading zeros, returns 32 if w = 0\item CNTTZ(w) - Count trailing zeros, returns 32 if w = 0\end{itemize}


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



\footnotesize\begin{verbatim}
                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
   \end{verbatim}\normalsize


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

{\bf IMPLEMENTATION} {\bf NOTE} \par
 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).

{\bf Demonstration} {\bf of} {\bf the} {\bf methodk} \par
 Consider a 32-bit number with the following 8 bits pattern in its least significant bits



\footnotesize\begin{verbatim}        
     x:      10110100
    ~x:      01001011
    -x:      01001100
    x & -x:  00000100  <- Only bit left standing was the lowest order
                          bit with a 1 in it
   \end{verbatim}\normalsize


\subsection{Function Documentation}
\hypertarget{FFS_8ih_a6}{
\index{FFS.ih@{FFS.ih}!CNTLZ@{CNTLZ}}
\index{CNTLZ@{CNTLZ}!FFS.ih@{FFS.ih}}
\subsubsection[CNTLZ]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-PROTO int CNTLZ (unsigned int {\em w})}}
\label{FFS_8ih_a6}


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

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The 32 bit word to be examined. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of leading 0's in a 32 bit word.\end{Desc}
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. 

Here is the call graph for this function:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=87pt]{FFS_8ih_a6_cgraph}
\end{center}
\end{figure}
\hypertarget{FFS_8ih_a7}{
\index{FFS.ih@{FFS.ih}!CNTTZ@{CNTTZ}}
\index{CNTTZ@{CNTTZ}!FFS.ih@{FFS.ih}}
\subsubsection[CNTTZ]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-PROTO int CNTTZ (unsigned int {\em w})}}
\label{FFS_8ih_a7}


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

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The 32 bit word to be examined. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of trailing 0's in a 32 bit word.\end{Desc}
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. 

Here is the call graph for this function:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=85pt]{FFS_8ih_a7_cgraph}
\end{center}
\end{figure}
\hypertarget{FFS_8ih_a3}{
\index{FFS.ih@{FFS.ih}!FFSl@{FFSl}}
\index{FFSl@{FFSl}!FFS.ih@{FFS.ih}}
\subsubsection[FFSl]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-PROTO int FFSl (unsigned int {\em w})}}
\label{FFS_8ih_a3}


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

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The 32 bit word to examined from the MSb to LSb for the first set bit. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of the first set bit in {\em w\/}, where LSb = 0\end{Desc}
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. \hypertarget{FFS_8ih_a2}{
\index{FFS.ih@{FFS.ih}!FFSL@{FFSL}}
\index{FFSL@{FFSL}!FFS.ih@{FFS.ih}}
\subsubsection[FFSL]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-PROTO int FFSL (unsigned int {\em w})}}
\label{FFS_8ih_a2}


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

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The 32 bit word to examined from the MSb to LSb for the first set bit. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of the first set bit in {\em w\/}, where MSb = 0\end{Desc}
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. \hypertarget{FFS_8ih_a9}{
\index{FFS.ih@{FFS.ih}!FFSl_eliminate@{FFSl\_\-eliminate}}
\index{FFSl_eliminate@{FFSl\_\-eliminate}!FFS.ih@{FFS.ih}}
\subsubsection[FFSl\_\-eliminate]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-FNC unsigned int FFSl\_\-eliminate (unsigned int {\em w}, int {\em bit})}}
\label{FFS_8ih_a9}


Eliminates the {\em bit\/}, counting LSb = 0, in word {\em w\/}. 

\begin{Desc}
\item[Returns:]The word with the bit eliminated\end{Desc}
\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The word to eliminate the bit from \item[{\em bit}]The number of the bit (LSb = 0) to eliminate\end{description}
\end{Desc}
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. \hypertarget{FFS_8ih_a8}{
\index{FFS.ih@{FFS.ih}!FFSL_eliminate@{FFSL\_\-eliminate}}
\index{FFSL_eliminate@{FFSL\_\-eliminate}!FFS.ih@{FFS.ih}}
\subsubsection[FFSL\_\-eliminate]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-FNC unsigned int FFSL\_\-eliminate (unsigned int {\em w}, int {\em bit})}}
\label{FFS_8ih_a8}


Eliminates the {\em bit\/}, counting MSb = 0, in word {\em w\/}. 

\begin{Desc}
\item[Returns:]The word with the bit eliminated\end{Desc}
\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The word to eliminate the bit from \item[{\em bit}]The number of the bit (MSb = 0) to eliminate\end{description}
\end{Desc}
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. \hypertarget{FFS_8ih_a5}{
\index{FFS.ih@{FFS.ih}!FFSt@{FFSt}}
\index{FFSt@{FFSt}!FFS.ih@{FFS.ih}}
\subsubsection[FFSt]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-PROTO int FFSt (unsigned int {\em w})}}
\label{FFS_8ih_a5}


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

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The 32 bit word to examined from the LSb to MSb for the first set bit. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of the first set bit in {\em w\/}, where LSb = 0\end{Desc}
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. \hypertarget{FFS_8ih_a4}{
\index{FFS.ih@{FFS.ih}!FFST@{FFST}}
\index{FFST@{FFST}!FFS.ih@{FFS.ih}}
\subsubsection[FFST]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-PROTO int FFST (unsigned int {\em w})}}
\label{FFS_8ih_a4}


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

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The 32 bit word to examined from the LSb to MSb for the first set bit. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]The number of the first set bit in {\em w\/}, where MSb = 0\end{Desc}
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. \hypertarget{FFS_8ih_a11}{
\index{FFS.ih@{FFS.ih}!FFSt_eliminate@{FFSt\_\-eliminate}}
\index{FFSt_eliminate@{FFSt\_\-eliminate}!FFS.ih@{FFS.ih}}
\subsubsection[FFSt\_\-eliminate]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-FNC unsigned int FFSt\_\-eliminate (unsigned int {\em w}, int {\em bit})}}
\label{FFS_8ih_a11}


Eliminates the {\em bit\/}, counting LSb = 0, in word {\em w\/}. 

\begin{Desc}
\item[Returns:]The word with the bit eliminated\end{Desc}
\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The word to eliminate the bit from \item[{\em bit}]The number of the bit (LSb = 0) to eliminate\end{description}
\end{Desc}
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. \hypertarget{FFS_8ih_a10}{
\index{FFS.ih@{FFS.ih}!FFST_eliminate@{FFST\_\-eliminate}}
\index{FFST_eliminate@{FFST\_\-eliminate}!FFS.ih@{FFS.ih}}
\subsubsection[FFST\_\-eliminate]{\setlength{\rightskip}{0pt plus 5cm}FFS\_\-\_\-LCL\_\-FNC unsigned int FFST\_\-eliminate (unsigned int {\em w}, int {\em bit})}}
\label{FFS_8ih_a10}


Eliminates the {\em bit\/}. 

\begin{Desc}
\item[Returns:]The word with the bit eliminated\end{Desc}
\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em w}]The word to eliminate the bit from \item[{\em bit}]The number of the bit (MSb = 0) to eliminate\end{description}
\end{Desc}
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. 