From patchwork Fri Feb 1 22:03:16 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 217603 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id DC6082C029F for ; Sat, 2 Feb 2013 09:14:28 +1100 (EST) Received: from localhost ([::1]:54701 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1U1OsL-00013s-My for incoming@patchwork.ozlabs.org; Fri, 01 Feb 2013 17:14:25 -0500 Received: from eggs.gnu.org ([208.118.235.92]:54688) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1U1Olk-0008LK-9l for qemu-devel@nongnu.org; Fri, 01 Feb 2013 17:11:14 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1U1Ohs-0007FF-CQ for qemu-devel@nongnu.org; Fri, 01 Feb 2013 17:07:36 -0500 Received: from mail-wg0-f43.google.com ([74.125.82.43]:43217) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1U1Ohs-0007De-1a for qemu-devel@nongnu.org; Fri, 01 Feb 2013 17:03:36 -0500 Received: by mail-wg0-f43.google.com with SMTP id e12so3316773wge.22 for ; Fri, 01 Feb 2013 14:03:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:sender:from:to:cc:subject:date:message-id:x-mailer; bh=RT3yHmuVg1lS0iHNdijgxarE97hqZ5CYMXpFgqaxP6g=; b=DIsv65Rt8EPBjn9ID92qlSlHefrbICPHOCIxTQSxnYakO8oJNRtkcxmH9Ju7gE47nQ GjqXDdnIW9Hmzu+98tAxlHAwH32GS4p6x2nxZ2bb0w7ipVSFC7bKT2DHJ07hDr6fkYYT jOecP95thtPad3E3822fniJtJCFrLns5PHSckXDzz8oH+x52PZ5Zs/C5SVBkHZ41T7Cm fH19IlNe3Jse4/cnn1kSTPoTo4MZK4AmMXmbFS8+AnJrk7ftJwXMHCQLXZHKe7VhuB7L YHD67e0h35rRcb97vObWr+Sr74KQBAKrSOsci64nXE5NSb+Nm0LnZZhN4r8oFDYmCG0Z m4vg== X-Received: by 10.180.101.99 with SMTP id ff3mr256442wib.21.1359756215267; Fri, 01 Feb 2013 14:03:35 -0800 (PST) Received: from yakj.usersys.redhat.com.org ([62.4.152.208]) by mx.google.com with ESMTPS id gz3sm5946883wib.2.2013.02.01.14.03.32 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Fri, 01 Feb 2013 14:03:34 -0800 (PST) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Fri, 1 Feb 2013 23:03:16 +0100 Message-Id: <1359756196-5588-1-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.1 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 74.125.82.43 Cc: blauwirbel@gmail.com, peter.maydell@linaro.org, sw@weilnetz.de Subject: [Qemu-devel] [PATCH v3] bitops: unify bitops_ffsl with the one in host-utils.h, call it bitops_ctzl X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org We had two copies of a ffs function for longs with subtly different semantics and, for the one in bitops.h, a confusing name: the result was off-by-one compared to the library function ffsl. Unify the functions into one, and solve the name problem by calling the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. This also fixes the build on platforms with ffsl, including Mac OS X and Windows. Signed-off-by: Paolo Bonzini Reviewed-by: Eric Blake Tested-by: Andreas Färber Tested-by: Peter Maydell --- include/qemu/bitops.h | 55 +++++++++++++++++++---------------------------- include/qemu/hbitmap.h | 2 +- include/qemu/host-utils.h | 26 ---------------------- memory.c | 4 ++-- util/bitops.c | 4 ++-- util/hbitmap.c | 2 +- 6 files changed, 28 insertions(+), 65 deletions(-) diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h index 74e14e5..8b88791 100644 --- a/include/qemu/bitops.h +++ b/include/qemu/bitops.h @@ -13,6 +13,7 @@ #define BITOPS_H #include "qemu-common.h" +#include "host-utils.h" #define BITS_PER_BYTE CHAR_BIT #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) @@ -23,41 +24,29 @@ #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) /** - * bitops_ffs - find first bit in word. + * bitops_ctzl - count trailing zeroes in word. * @word: The word to search * - * Undefined if no bit exists, so code should check against 0 first. + * Returns -1 if no bit exists. Note that compared to the C library + * routine ffsl, this one returns one less. */ -static unsigned long bitops_ffsl(unsigned long word) +static unsigned long bitops_ctzl(unsigned long word) { - int num = 0; +#if QEMU_GNUC_PREREQ(3, 4) + return __builtin_ffsl(word) - 1; +#else + if (!word) { + return -1; + } -#if LONG_MAX > 0x7FFFFFFF - if ((word & 0xffffffff) == 0) { - num += 32; - word >>= 32; - } + if (sizeof(long) == 4) { + return ctz32(word); + } else if (sizeof(long) == 8) { + return ctz64(word); + } else { + abort(); + } #endif - if ((word & 0xffff) == 0) { - num += 16; - word >>= 16; - } - if ((word & 0xff) == 0) { - num += 8; - word >>= 8; - } - if ((word & 0xf) == 0) { - num += 4; - word >>= 4; - } - if ((word & 0x3) == 0) { - num += 2; - word >>= 2; - } - if ((word & 0x1) == 0) { - num += 1; - } - return num; } /** @@ -99,14 +88,14 @@ static inline unsigned long bitops_flsl(unsigned long word) } /** - * ffz - find first zero in word. + * cto - count trailing ones in word. * @word: The word to search * - * Undefined if no zero exists, so code should check against ~0UL first. + * Returns -1 if all bit are set. */ -static inline unsigned long ffz(unsigned long word) +static inline unsigned long bitops_ctol(unsigned long word) { - return bitops_ffsl(~word); + return bitops_ctzl(~word); } /** diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 73f5d1d..250de03 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -170,7 +170,7 @@ static inline int64_t hbitmap_iter_next(HBitmapIter *hbi) /* The next call will resume work from the next bit. */ hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); - item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ffsl(cur) - 1; + item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + bitops_ctzl(cur); return item << hbi->granularity; } diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h index 2a32be4..81c9a75 100644 --- a/include/qemu/host-utils.h +++ b/include/qemu/host-utils.h @@ -26,7 +26,6 @@ #define HOST_UTILS_H 1 #include "qemu/compiler.h" /* QEMU_GNUC_PREREQ */ -#include /* ffsl */ #if defined(__x86_64__) #define __HAVE_FAST_MULU64__ @@ -238,29 +237,4 @@ static inline int ctpop64(uint64_t val) #endif } -/* glibc does not provide an inline version of ffsl, so always define - * ours. We need to give it a different name, however. - */ -#ifdef __GLIBC__ -#define ffsl qemu_ffsl -#endif -static inline int ffsl(long val) -{ - if (!val) { - return 0; - } - -#if QEMU_GNUC_PREREQ(3, 4) - return __builtin_ctzl(val) + 1; -#else - if (sizeof(long) == 4) { - return ctz32(val) + 1; - } else if (sizeof(long) == 8) { - return ctz64(val) + 1; - } else { - abort(); - } -#endif -} - #endif diff --git a/memory.c b/memory.c index 410c5f8..cd7d5e0 100644 --- a/memory.c +++ b/memory.c @@ -855,7 +855,7 @@ static uint64_t memory_region_dispatch_read1(MemoryRegion *mr, } if (!mr->ops->read) { - return mr->ops->old_mmio.read[bitops_ffsl(size)](mr->opaque, addr); + return mr->ops->old_mmio.read[bitops_ctzl(size)](mr->opaque, addr); } /* FIXME: support unaligned access */ @@ -908,7 +908,7 @@ static void memory_region_dispatch_write(MemoryRegion *mr, adjust_endianness(mr, &data, size); if (!mr->ops->write) { - mr->ops->old_mmio.write[bitops_ffsl(size)](mr->opaque, addr, data); + mr->ops->old_mmio.write[bitops_ctzl(size)](mr->opaque, addr, data); return; } diff --git a/util/bitops.c b/util/bitops.c index 4c3a836..7b853cf 100644 --- a/util/bitops.c +++ b/util/bitops.c @@ -60,7 +60,7 @@ found_first: return result + size; /* Nope. */ } found_middle: - return result + bitops_ffsl(tmp); + return result + bitops_ctzl(tmp); } /* @@ -109,7 +109,7 @@ found_first: return result + size; /* Nope. */ } found_middle: - return result + ffz(tmp); + return result + bitops_ctol(tmp); } unsigned long find_last_bit(const unsigned long *addr, unsigned long size) diff --git a/util/hbitmap.c b/util/hbitmap.c index 2aa487d..a0df5d3 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -126,7 +126,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) * The index of this word's least significant set bit provides * the low-order bits. */ - pos = (pos << BITS_PER_LEVEL) + ffsl(cur) - 1; + pos = (pos << BITS_PER_LEVEL) + bitops_ctzl(cur); hbi->cur[i] = cur & (cur - 1); /* Set up next level for iteration. */