From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 58359 invoked by alias); 27 Jul 2017 21:03:15 -0000 Mailing-List: contact newlib-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: newlib-owner@sourceware.org Received: (qmail 58333 invoked by uid 89); 27 Jul 2017 21:03:14 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.4 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 spammy=delight, warren, ctz, ebook X-HELO: smtp-out-so.shaw.ca Received: from smtp-out-so.shaw.ca (HELO smtp-out-so.shaw.ca) (64.59.136.139) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 27 Jul 2017 21:03:12 +0000 Received: from [192.168.1.100] ([24.64.240.204]) by shaw.ca with SMTP id apw5d531xDJTWapw6dMaTl; Thu, 27 Jul 2017 15:03:10 -0600 X-Authority-Analysis: v=2.2 cv=B4DJ6KlM c=1 sm=1 tr=0 a=MVEHjbUiAHxQW0jfcDq5EA==:117 a=MVEHjbUiAHxQW0jfcDq5EA==:17 a=IkcTkHD0fZMA:10 a=NEAV23lmAAAA:8 a=WJzlD7WXAAAA:8 a=8pif782wAAAA:8 a=bBmCkCVWAAAA:8 a=CLYR60w1pytT-rjTB8MA:9 a=QEXdDO2ut3YA:10 a=XPhSJoF3BniwEGB9uug3:22 a=2Hm06ypIHy5svNcjg0qB:22 Reply-To: Brian.Inglis@SystematicSw.ab.ca Subject: Re: [PATCH] Workaround for ffs() on LP64 targets To: newlib@sourceware.org References: <20170727080624.24818-1-sebastian.huber@embedded-brains.de> <26467603-cd3e-63af-04f3-d0c78e14e348@redhat.com> <42255ff2-66cf-e021-788b-250d45693374@embedded-brains.de> From: Brian Inglis Message-ID: <52ed828d-dd7b-0327-79ae-051b8187b095@SystematicSw.ab.ca> Date: Thu, 27 Jul 2017 21:03:00 -0000 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 In-Reply-To: <42255ff2-66cf-e021-788b-250d45693374@embedded-brains.de> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-CMAE-Envelope: MS4wfMKcYykr1QIRPMs4xQebBPEDlb+D3jkVOuzBHvTyN0IGmiyMFytle4ZMQ1YioS7On+tKiaVH4yXcdYjj4HBT7wzHVFW3yPRdn5wNEahDfsZ7mmL8sXFP yd7a3x/v6mzZb/Tj0tD7oMeiLluv/lZTFvk1gfk76vJa4lZM8N1dNvTP8FZ+HWaQLrNHDhSr4bhNtQ== X-IsSubscribed: yes X-SW-Source: 2017/txt/msg00681.txt.bz2 On 2017-07-27 05:24, Sebastian Huber wrote: > On 27/07/17 13:13, Eric Blake wrote: >> On 07/27/2017 03:06 AM, Sebastian Huber wrote: >>> Signed-off-by: Sebastian Huber >>> --- >>> newlib/libc/misc/ffs.c | 11 +++++++++++ >>> 1 file changed, 11 insertions(+) >>> >>> diff --git a/newlib/libc/misc/ffs.c b/newlib/libc/misc/ffs.c >>> index ba5700920..a09cbd3bb 100644 >>> --- a/newlib/libc/misc/ffs.c >>> +++ b/newlib/libc/misc/ffs.c >>> @@ -31,6 +31,17 @@ No supporting OS subroutines are required. */ >>> int >>> ffs(int i) >>> { >>> +#ifdef __LP64__ >>> + /* GCC would expand the __builtin_ffs() to ffs() in this case */ >>> + int bit; >>> + >>> + if (i == 0) >>> + return (0); >>> + for (bit = 1; !(i & 1); bit++) >>> + i = (unsigned int)i >> 1; >>> + return (bit); >> If we're going to open-code it to work around the compiler creating an >> infloop recursion to ffs(), at least code a straight-line version >> without branches, rather than the painfully slow bit-by-bit loop. >> There's plenty of examples on the web of writing ffs() by using >> bit-twiddling without branching. Definitive twiddling reference is now Hacker's Delight 2nd ed, Henry S. Warren, Jr., 2013, Pearson/InformIT/AW; available in ebook formats: https://github.com/jyfc/ebook/blob/master/02_algorithm/Hacker's%20Delight%202nd%20Edition.pdf https://www.safaribooksonline.com/library/view/hackers-delight-second/9780133084993/ https://en.wikipedia.org/wiki/Hacker%27s_Delight http://www.hackersdelight.org/ > This is roughly the same implementation we had before. I do not intend to > optimize this. Programmers using these functions expect the usage cost to be trivial and fairly constant ~ O(log2(bits)) not O(bits); if not, they may implement their own! Try this one, seems decently short; adjust for different word sizes; with gcc -O3 on x86-64 compiles to 32 instructions branch free: YMMV int ffsll( long long in ) { /* find first set == 1 + count trailing zeros */ int index = 64; if (!in) return 0; in &= -in; /* clear all but lsb set */ /* * for ctz remove above test and add next line * if (in) --index; */ if (in & 0x00000000FFFFFFFF) index -= 32; if (in & 0x0000FFFF0000FFFF) index -= 16; if (in & 0x00FF00FF00FF00FF) index -= 8; if (in & 0x0F0F0F0F0F0F0F0F) index -= 4; if (in & 0x3333333333333333) index -= 2; if (in & 0x5555555555555555) index -= 1; return index; } -- Take care. Thanks, Brian Inglis, Calgary, Alberta, Canada