\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`\"{}IPBS/impl/FFS.ih.xx-xxx-xxx\char`\"{}}\par Include dependency graph for FFS.ih:\begin{figure}[H] \begin{center} \leavevmode \includegraphics[width=141pt]{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=141pt]{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.1.1.1 2006/02/10 21:45:35 saxton 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}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.\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}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.\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}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}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}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}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.