From owner-freebsd-hackers@FreeBSD.ORG Sun Jun 7 07:02:33 2015 Return-Path: Delivered-To: freebsd-hackers@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id D04DD279 for ; Sun, 7 Jun 2015 07:02:33 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (heidi.turbocat.net [88.198.202.214]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 90AFE1269 for ; Sun, 7 Jun 2015 07:02:33 +0000 (UTC) (envelope-from hps@selasky.org) Received: from laptop015.home.selasky.org (cm-176.74.213.204.customer.telag.net [176.74.213.204]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id BF0901FE023; Sun, 7 Jun 2015 08:52:31 +0200 (CEST) Message-ID: <5573EA5E.40806@selasky.org> Date: Sun, 07 Jun 2015 08:53:18 +0200 From: Hans Petter Selasky User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: Erich Dollansky , "freebsd-hackers@freebsd.org" Subject: Re: allow ffs & co. a binary search References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> In-Reply-To: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Jun 2015 07:02:33 -0000 On 06/07/15 02:13, Erich Dollansky wrote: > Hi, > > I stumbled these days over the functions to find the first or last bit > set. They are currently written like this: > > /* > * Find First Set bit > */ > int > ffs(int mask) > { > int bit; > > if (mask == 0) > return (0); > for (bit = 1; !(mask & 1); bit++) > mask = (unsigned int)mask >> 1; > return (bit); > } > > With other words, the program loops until it finds what it searches for. > > Why not do it the binary way? > > int res; > > res = 0; > IF (Number != 0) THEN > res = 1; > IF ((Number & 0xFFFFFFFF00000000) != 0) THEN > Number = Number & 0xFFFFFFFF00000000; > res = res + 32; > END; > IF ((Number & 0xFFFF0000FFFF0000) != 0) THEN > Number = Number & 0xFFFF0000FFFF0000; > res = res + 16; > END; > IF ((Number & 0xFF00FF00FF00FF00) != 0) THEN > Number = Number & 0xFF00FF00FF00FF00; > res = res + 8; > END; > IF ((Number & 0xF0F0F0F0F0F0F0F0) != 0) THEN > Number = Number & 0xF0F0F0F0F0F0F0F0; > res = res + 4; > END; > IF ((Number & 0xCCCCCCCCCCCCCCCC) != 0) THEN > Number = Number & 0xCCCCCCCCCCCCCCCC; > res = res + 2; > END; > IF ((Number & 0xAAAAAAAAAAAAAAAA) != 0) THEN > Number = Number & 0xAAAAAAAAAAAAAAAA; > res = res + 1; > END; > END; > return res; > > If you like the binary way I could give you the sources for the > complete family following your style to replace the older functions. > Hi Erich, I think this is not the fastest way to do it. You first find the LSB, then you do a sumbits, which doesn't have any conditionals IF/ELSE and performs better with the CPU pipeline. I think the software ffs() is only used for platforms which doesn't have a hardware version btw: From my libmbin: > uint8_t > mbin_sumbits32(uint32_t val) > { > #if 0 > uint8_t t = 0; > > while (val) { > if (val & 1) > t++; > val >>= 1; > } > return (t); > #else > val = ((val & (1U * 0xAAAAAAAAU)) / 2U) + (val & (1U * 0x55555555U)); > val = ((val & (3U * 0x44444444U)) / 4U) + (val & (3U * 0x11111111U)); > val = ((val & (15U * 0x10101010U)) / 16U) + (val & (15U * 0x01010101U)); > val = ((val & (255U * 0x01000100U)) / 256U) + (val & (255U * 0x00010001U)); > val = ((val & (65535U * 0x00010000U)) / 65536U) + (val & (65535U * 0x00000001U)); > return (val); > #endif > } > uint32_t > mbin_lsb32(uint32_t val) > { > return ((~(val - 1)) & val); > } int ffs(int value) { int retval = mbin_sumbits32(mbin_lsb32(value) - 1); if (retval == 32) retval = 0; else retval++; return (retval); } --HPS