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 libkern/fl