ffs function

[jacob navia]

The Find First Set function (ffs) finds the lowest bit set in an
integer.

I wanted to add this to the library in lcc-win but before doing it I
would like your opinion as to *where* should I declare them?

First, this function is POSIX and the include file is called

"strings.h"

I do not know why. There you will find bzero() and other functions
that have absolutely nothing to do with any strings. The only
string functions there are strcasecmp (that is equivalent to
stricmp in lcc-win) and strncasecmp (equivalent to strnicmp).

Question:

Should I add a "utils.h" header?
Or follow POSIX?

I have a founction for counting bits in an integer and I
have added it in bitstring.h but that is a header concerned
with the bit string implementation... Not really the subject
of those functions.

Since I am revising this, I added the function

fls (Find Last Set) that will find the higher order
bit in an integer. Strange, this function is NOT in POSIX. Maybe
anyone here knows why?

Below is the documentation for both functions
--------------------------------------------------------------------
Function: _ffs _fls

Synopsis

#include <utils.h> // ???????????????????
int _stdcall _ffs(int n);
int _stdcall _fls(int n);

Description
The fsf() function returns the index of the first bit different from
zero in the given integer argument. The first bit (the least
significant) is numbered 1.

The fls() function returns the index of the first most significant bit
set.. Bit indexes start at 1.

Returns
The value of the index or zero if and only if all bits are zero


;

 

[Chris Torek]

The Find First Set function (ffs) finds the lowest bit set in an
integer.

First, this function is POSIX and the include file is called
"strings.h"
I do not know why.

Historical accident.

ffs() is an "XSI" function in POSIX, i.e., it was not originally
in POSIX but rather was added later when they imported a bunch of
bad ideas. (Like C, POSIX standards come in different versions
and dates.)

fls (Find Last Set) that will find the higher order
bit in an integer. Strange, this function is NOT in POSIX. Maybe
anyone here knows why?

It was not in the Historical Accident imported into Issue 4, Version
2 of POSIX. (Specifically, the VAX had an instruction spelled
"ffs" but nothing spelled "fls", and no instruction to "find highest
order set bit".)

 

[Randy Howard]

The Find First Set function (ffs) finds the lowest bit set in an
integer.

I wanted to add this to the library in lcc-win but before doing it I
would like your opinion as to *where* should I declare them?

First, this function is POSIX and the include file is called

"strings.h"

I do not know why.

From the man page on my system:

"The ffs() function appeared in 4.3BSD. Its prototype existed
previously in <string.h> before it was moved to <strings.h> for
IEEE Std 1003.1-2001 (``POSIX.1'') compliance."

 

[Terminal Crazy]

Synopsis

#include <utils.h> // ???????????????????
int _stdcall _ffs(int n);
int _stdcall _fls(int n);

Description
The fsf() function returns the index of the first bit different from
zero in the given integer argument. The first bit (the least
significant) is numbered 1.

The fls() function returns the index of the first most significant bit
set.. Bit indexes start at 1.

Returns
The value of the index or zero if and only if all bits are zero

Out of interest,
why do the indexes start at 1? I would have expected it to be 0 being C or
is that from the POSIX spec ?

 

[Thad Smith]

The Find First Set function (ffs) finds the lowest bit set in an
integer.

I wanted to add this to the library in lcc-win but before doing it I
would like your opinion as to *where* should I declare them?

First, this function is POSIX and the include file is called

"strings.h"

I do not know why. There you will find bzero() and other functions
that have absolutely nothing to do with any strings. The only
string functions there are strcasecmp (that is equivalent to
stricmp in lcc-win) and strncasecmp (equivalent to strnicmp).

Question:

Should I add a "utils.h" header?
Or follow POSIX?

If you implement all the functions in that Posix header, I suggest using
the Posix header name.

Starting from scratch, neither "strings.h" nor "utils.h" is suggestive of
the functionality, but "utils.h" is closer.

I have a founction for counting bits in an integer and I
have added it in bitstring.h but that is a header concerned
with the bit string implementation... Not really the subject
of those functions.

Hmmm, that seems to be a closer fit than the earlier headers.

...
Below is the documentation for both functions
--------------------------------------------------------------------
Function: _ffs _fls

Synopsis

#include <utils.h> // ???????????????????
int _stdcall _ffs(int n);
int _stdcall _fls(int n);

Description
The fsf() function returns the index of the first bit different from
zero in the given integer argument. The first bit (the least
significant) is numbered 1.

The fls() function returns the index of the first most significant bit
set.. Bit indexes start at 1.

Returns
The value of the index or zero if and only if all bits are zero

Why have leading underscores? If the user doesn't include the chosen
non-standard header file, ffs will not be defined and would not conflict
with a user identifier. Your version would then be in a library, only
linked if the user did not define and link their own ffs.

For description I suggest:
Function ffs() returns the index of the least significant one bit of the
binary value of n. The least significant bit of the argument has index 1.
The sign bit has index 32.

Function fls() returns the index of the most significant one bit of the
binary value of n. The least significant bit of the argument has index 1.
The sign bit has index 32.

Both functions return zero for n = 0.

Examples:
ffs(10) returns 2
fls(10) returns 4
fls(-4) returns 32

 

[Keith Thompson]

The Find First Set function (ffs) finds the lowest bit set in an
integer.

I wanted to add this to the library in lcc-win but before doing it I
would like your opinion as to *where* should I declare them?

First, this function is POSIX and the include file is called

"strings.h"

I do not know why. There you will find bzero() and other functions
that have absolutely nothing to do with any strings. The only
string functions there are strcasecmp (that is equivalent to
stricmp in lcc-win) and strncasecmp (equivalent to strnicmp).

Question:

Should I add a "utils.h" header?
Or follow POSIX?

If you intend to support the full POSIX <strings.h> header (or all of
POSIX), then obviously the declaration of ffs() should be there. If
not, I'd put it somewhere else, perhaps in a "utils.h" header (which
could also be a good place for your MIN() and MAX() macros). If you
decide later to support all of <strings.h>, you can always add it
there too.

[...]

Below is the documentation for both functions
--------------------------------------------------------------------
Function: _ffs _fls

Synopsis

#include <utils.h> // ???????????????????
int _stdcall _ffs(int n);
int _stdcall _fls(int n);

Description
The fsf() function returns the index of the first bit different from

Typo: "fsf()" should be "ffs".

zero in the given integer argument. The first bit (the least
significant) is numbered 1.

The fls() function returns the index of the first most significant bit
set.. Bit indexes start at 1.

Returns
The value of the index or zero if and only if all bits are zero

[...]

I'm confused; is the function called "_ffs" or "ffs"?

 

[jacob navia]

Out of interest,
why do the indexes start at 1? I would have expected it to be 0 being C or
is that from the POSIX spec ?

It is in the POSIX spec. Besides, if you return zero for the
least significant bit set, what do you return for ZERO ???

 

[jacob navia]

Keith Thompson wrote:
[snip]
Thanks. I will correct those typos!

 

[jacob navia]

Historical accident.

ffs() is an "XSI" function in POSIX, i.e., it was not originally
in POSIX but rather was added later when they imported a bunch of
bad ideas. (Like C, POSIX standards come in different versions
and dates.)

Since the x86 has an instruction bsf (bit search forward) that is
essentially this instruction it is maybe not such a bad idea.

It was not in the Historical Accident imported into Issue 4, Version
2 of POSIX. (Specifically, the VAX had an instruction spelled
"ffs" but nothing spelled "fls", and no instruction to "find highest
order set bit".)

But it should be for completeness.

Thanks for your answer

 

[CBFalconer]

The Find First Set function (ffs) finds the lowest bit set in an
integer.

I wanted to add this to the library in lcc-win but before doing
it I would like your opinion as to *where* should I declare them?

First, this function is POSIX and the include file is called

"strings.h"

I do not know why. There you will find bzero() and other functions
that have absolutely nothing to do with any strings. The only
string functions there are strcasecmp (that is equivalent to
stricmp in lcc-win) and strncasecmp (equivalent to strnicmp).

Question:

Should I add a "utils.h" header?
Or follow POSIX?

I have a founction for counting bits in an integer and I
have added it in bitstring.h but that is a header concerned
with the bit string implementation... Not really the subject
of those functions.

You should add something that is guarded and obviously belongs to
lcc. I.e something like "lccaddons01.h". If the code is in the
main library, it should be protected by double leading underscores,
and the header file can create a suitable define, such as:

#define __function function

That way everything is in your namespace until the file in
included.

 

[user923005]

It is in the POSIX spec. Besides, if you return zero for the
least significant bit set, what do you return for ZERO ???

-1
Because no bits are set.