Re: svn commit: r289765 - in head/sys: conf libkern sys
On Thu, 22 Oct 2015, Conrad E. Meyer wrote:
Log:
Add libkern ffsll() for parity with flsll()
Sponsored by: EMC / Isilon Storage Division
This fills a much needed gap, like the one filled by flsll().
It uses the long long abomination.
uintmax_t has been Standard since 1999, but is still not supported
by the ffs() family.
It further expands the design error in ffs().
(ffs() only supports ints. Its behaviour on negative values is
undocumented, but needs documentation more than for non-negative
values because even in the 2's complement case, the sign bit can
be anywhere). The bad BSD documented is for ffs() is duplicated
in POSIX in at least old versions. I think this requires ffs()
to operate on values, so it cannot work in the 1's complement
case. The -0 has all bits 1 but value 0. ffs(-0) by value must
be -1, and ABIs are probably allowed to pass -0 as +0 so ffs(-0)
is probably -1 even if ffs() is by bits.)
Due to this design error, it is not obvious that even u_char is
directly supported by the ffs() family. It is supported because
POSIX requires 8-bit chars so chars get promoted to non-negative
ints when passed to ffs(). This doesn't happen for u_int, but
you can promote u_int manually to long long to get correct and
pessimal code. This doesn't work for u_foo that is already
of larger rank than long long.
Added: head/sys/libkern/ffsll.c
==
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/libkern/ffsll.cThu Oct 22 20:28:37 2015(r289765)
+ ...
+/*
+ * Find First Set bit
+ */
+int
+ffsll(long long mask)
+{
+ int bit;
+
+ if (mask == 0)
+ return (0);
+ for (bit = 1; !(mask & 1); bit++)
+ mask = (unsigned long long)mask >> 1;
+ return (bit);
+}
This has the usual implementation for negative values. They are cast
to the correct unsigned type to get defined behaviour for the shift.
The cast itself gives implementation-defined behaviour. Even when the
compiler was gcc so that it was documented in man pages and info pages,
the documentation for this was hard to find. Whatever it is, it gives
the undocumented behaviour of the function.
This implementation is pessimal unless the compiler can convert it to
special instructions. On i386, 2 32-bit ffs()'s are more portable and
much faster, since each one uses a special instruction and it is not
possible to do much better. (But fls64() can be done better in userland
using the FPU or perhaps SSE.)
clang optimizes similar simple loops for popcount() but doesn't optimize
the ones used in libc for the ffs() family. If it did optimize these
loops, 2 32-bit ffs()'s with asms inside them wouldn't be so good, but
for bswap64() we arranged for compilers to good combining for even more
complicated variations. (For bswap*, clang converts the complicated C
expression giving the rearrangement to minimal bswap instruction(s),
but we hard-code these instructions in asm because gcc can't do this
in the old versions in FreeBSD, and then arrange so that clang can
combine the asms efficiently on i386.)
Efficiency of the ffs() family is rarely important. bitset.h uses ffsl()
but bitstring.h uses a simple loop.
Bruce
___
svn-src-all@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
svn commit: r289765 - in head/sys: conf libkern sys
Author: cem Date: Thu Oct 22 20:28:37 2015 New Revision: 289765 URL: https://svnweb.freebsd.org/changeset/base/289765 Log: Add libkern ffsll() for parity with flsll() Sponsored by: EMC / Isilon Storage Division Differential Revision:https://reviews.freebsd.org/D3962 Added: head/sys/libkern/ffsll.c (contents, props changed) Modified: head/sys/conf/files.arm head/sys/conf/files.arm64 head/sys/conf/files.i386 head/sys/conf/files.mips head/sys/conf/files.pc98 head/sys/conf/files.powerpc head/sys/conf/files.sparc64 head/sys/sys/libkern.h Modified: head/sys/conf/files.arm == --- head/sys/conf/files.arm Thu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.arm Thu Oct 22 20:28:37 2015(r289765) @@ -120,6 +120,7 @@ libkern/ashldi3.c standard libkern/ashrdi3.c standard libkern/divdi3.c standard libkern/ffsl.c standard +libkern/ffsll.cstandard libkern/fls.c standard libkern/flsl.c standard libkern/flsll.cstandard Modified: head/sys/conf/files.arm64 == --- head/sys/conf/files.arm64 Thu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.arm64 Thu Oct 22 20:28:37 2015(r289765) @@ -82,6 +82,7 @@ kern/subr_dummy_vdso_tc.c standard libkern/bcmp.c standard libkern/ffs.c standard libkern/ffsl.c standard +libkern/ffsll.cstandard libkern/fls.c standard libkern/flsl.c standard libkern/flsll.cstandard Modified: head/sys/conf/files.i386 == --- head/sys/conf/files.i386Thu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.i386Thu Oct 22 20:28:37 2015(r289765) @@ -530,6 +530,7 @@ kern/imgact_aout.c optional compat_aout kern/imgact_gzip.c optional gzip kern/subr_sfbuf.c standard libkern/divdi3.c standard +libkern/ffsll.cstandard libkern/flsll.cstandard libkern/memmove.c standard libkern/memset.c standard Modified: head/sys/conf/files.mips == --- head/sys/conf/files.mipsThu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.mipsThu Oct 22 20:28:37 2015(r289765) @@ -56,6 +56,7 @@ kern/subr_sfbuf.c optionalmips | mips # gcc/clang runtime libkern/ffsl.c standard +libkern/ffsll.cstandard libkern/fls.c standard libkern/flsl.c standard libkern/flsll.cstandard Modified: head/sys/conf/files.pc98 == --- head/sys/conf/files.pc98Thu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.pc98Thu Oct 22 20:28:37 2015(r289765) @@ -222,6 +222,7 @@ kern/imgact_aout.c optional compat_aout kern/imgact_gzip.c optional gzip kern/subr_sfbuf.c standard libkern/divdi3.c standard +libkern/ffsll.cstandard libkern/flsll.cstandard libkern/memmove.c standard libkern/memset.c standard Modified: head/sys/conf/files.powerpc == --- head/sys/conf/files.powerpc Thu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.powerpc Thu Oct 22 20:28:37 2015(r289765) @@ -87,6 +87,7 @@ libkern/cmpdi2.c optionalpowerpc libkern/divdi3.c optionalpowerpc libkern/ffs.c standard libkern/ffsl.c standard +libkern/ffsll.cstandard libkern/fls.c standard libkern/flsl.c standard libkern/flsll.cstandard Modified: head/sys/conf/files.sparc64 == --- head/sys/conf/files.sparc64 Thu Oct 22 19:42:57 2015(r289764) +++ head/sys/conf/files.sparc64 Thu Oct 22 20:28:37 2015(r289765) @@ -67,6 +67,7 @@ kern/syscalls.c optionalktr kern/subr_sfbuf.c standard libkern/ffs.c standard libkern/ffsl.c standard +libkern/ffsll.cstandard libkern/fls.c standard libkern/flsl.c standard
