linux-kernel - Re: [0/3] Improve generic fls64 for 64-bit machines

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1207509050.21093.1246359933@webmail.messagingengine.com>
Date:	Sun, 06 Apr 2008 21:10:50 +0200
From:	"Alexander van Heukelum" <heukelum@...tmail.fm>
To:	"Benny Halevy" <bhalevy@...asas.com>,
	"Alexander van Heukelum" <heukelum@...lshack.com>
Cc:	"Andrew Morton" <akpm@...ux-foundation.org>,
	"linux-arch" <linux-arch@...r.kernel.org>,
	"Ingo Molnar" <mingo@...e.hu>, "Andi Kleen" <andi@...stfloor.org>,
	"LKML" <linux-kernel@...r.kernel.org>
Subject: Re: [0/3] Improve generic fls64 for 64-bit machines

On Sun, 06 Apr 2008 18:03:40 +0300, "Benny Halevy" <bhalevy@...asas.com>
said:
> On Apr. 04, 2008, 17:22 +0300, Alexander van Heukelum
> <heukelum@...lshack.com> wrote:
> > On Thu, Apr 03, 2008 at 08:19:59PM +0300, Benny Halevy wrote:
> >> On Mar. 15, 2008, 19:29 +0200, Alexander van Heukelum <heukelum@...lshack.com> wrote:
> >>> This series of patches:
> >>>
> >>> [1/3] adds __fls.h to asm-generic
> >>> [2/3] modifies asm-*/bitops.h for 64-bit archs to implement __fls
> >>> [3/3] modifies asm-generic/fls64.h to make use of __fls
> >> I strongly support this.
> >>
> >> I wish we'd also have a consistent naming convention for all
> >> the bitops functions so it will be clearer what data type the
> >> function is working on and is the result 0 or 1 based.
> >>
> >> It seems like what we currently have is:
> >>
> >> name	type	first bit#
> >> ----	----	----------
> >> ffs	int	1
> >> fls	int	1
> >> __ffs	ulong	0
> >> __fls	ulong	0	# in your proposal
> >> ffz	ulong	0
> >> fls64	__u64	1
> >>
> >> so it seems like
> >> - ffz is misnamed and is rather confusing.
> >>   Apprently is should be renamed to __ffz.
> >>
> >> - (new) ffz(x) can be defined to ffs(~(x))
> >>
> >> - It'd be nice to have ffs64, and maybe ffz64.
> >>
> >> Benny
> > 
> > I think every programmer who thinks in terms of bits realises
> > that ffz(x) == __ffs(~x) and ffz(~x) == __ffs(x) etc... so I
> > would rather get rid of ffz entirely by converting all uses
> > to __ffs. Patch (against current linus) below. After that all
> > implementations of ffz could be removed.
> 
> Yeah, very few architectures have an optimized version of ffz
> that will perform noticeably better than __ffs(~x).
> (e.g. h8300, sh)

Yeah, and these implementations seem to be based on a loop over
all bits in the word. I don't think adding one extra not-operation
to convert ffz to __ffs will hurt much ;).

> > ffs64 would be a good addition to complete the set of functions,
> > but that would be the same as glibc's (and gcc-builtin) ffsll.
> > 
> > Looking into that... the relevant gcc builtins are __builtin_ffs
> > (find first set bit), __builtin_clz (count leading zeroes),
> > __builtin_ctz (count trailing zeroes), __builtin_popcount, maybe
> > __builtin_parity and their -l and -ll variants. Maybe the kernel
> > should be changed to use those names instead of the current
> > ones? ffs would stay as it is. __ffs would become ctz, __fls
> > would become something like 31-clz, and hweight would become
> > popcount.
> 
> Interesting idea.  ctz much better than __ffs with regards to the
> return value's first bit number, but unless you expose clz
> and convert the code how do you get rid of the __fls vs. fls
> confusion?

Exposing clz/ctz on all architectures will be the harder part. Changing
all current uses of ffs/fls (and __fls) will take some time. Mostly
because converting code using fls to use clz instead needs to be
done a bit carefully, because fls(0) has defined behaviour, while
clz(0) is undefined.

> (BTW for __fls, I'd use BITS_PER_LONG - 1, not 31 :)

:)

> I think that adopting libc's convention might make more sense,
> i.e., define ffs, ffsl, ffsll, and fls, flsl, flsll, and have *all*
> be 1-based.

I agree that it makes sense for fls. For clz (and ctz) I would choose
clz(unsigned long), clz32(u32), and clz64(u64).

Greetings,
    Alexander

> Benny
-- 
  Alexander van Heukelum
  heukelum@...tmail.fm

-- 
http://www.fastmail.fm - Choose from over 50 domains or use your own

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/