From patchwork Tue May 15 16:22:26 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: William Breathitt Gray X-Patchwork-Id: 913816 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=linux-gpio-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="WWqNbXJL"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 40ljbZ5jwjz9s01 for ; Wed, 16 May 2018 02:25:30 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753432AbeEOQWf (ORCPT ); Tue, 15 May 2018 12:22:35 -0400 Received: from mail-yb0-f193.google.com ([209.85.213.193]:33988 "EHLO mail-yb0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753169AbeEOQWd (ORCPT ); Tue, 15 May 2018 12:22:33 -0400 Received: by mail-yb0-f193.google.com with SMTP id i1-v6so260214ybe.1; Tue, 15 May 2018 09:22:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=zXWx52J09B2XRIIWL2fJqPQYDuMBxPhU30oY293qaME=; b=WWqNbXJLI9rq4GUn54LE/T+RMmUb5qKQ8QKBWfyrS/jgA9BpNwU3jxvv9pGwFHjEuv rwsWwUWFPpVD0/cVETOfz0S/AYB4siQVHr/0HbihrR407NUqigc3ONZIKaIzpTLDpF+8 u/V36P3Y25zwe2XHyvmLbDDLfWkNUd/oYEzbU/ifQD6p/8fLJ96qQ4jcrx3TKwxNoBLe LZcD9QKCZ0yc4Fc6BoipKhUvQ1ApuleJcJxVhFRso4d6kaYcuxGxPmY51/4/qAPMu4dO 7cNpSIzWu/OmhGC8jN95MjoNU9tfJ0PxEqU/mbQ1uokaXj2OnxlBBDMxuARvyJlGTB3s pmiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=zXWx52J09B2XRIIWL2fJqPQYDuMBxPhU30oY293qaME=; b=qV7AbcU9FTr1IbJ7KngCZ67MTKycdDpm5HodBmgMm0/7vgWywkbbC0aLQKULC+va0b mJiJjKEH1n1oeDTlkRnNGEZafHxFlnchvix+BiD5ahc9BpDvUuMWhkyfEIo02b1Zx0am ARbAv77TIexp0b8jaS9AP/T2F510dGDGH/xzglWCAPUc2gBQ55A7GVf73GvwTup1Lm89 lI9+KeL4+83xmKbzbsjvUy2jlHv6i2EXq49SoBWygqs301MyJ/CyVXzmctNAapXI1rSJ 5oknVpsIO98CNjz+7+NlW48gT+nNXhDT8fS0lSVseYGPr6V86VaZmHKc4MzD7pr+2x9e 1h0A== X-Gm-Message-State: ALKqPwcJtSxKVcydersloRDU+5Q8l1oq4Gtem3TAdd5nxCfA0Y3q/8Y8 31jLNl4olPL9Nj31yYkdheI= X-Google-Smtp-Source: AB8JxZrDxMqEaurRHShiLPHJ3mbH8/o18rHwaWpq0shnDyKzrcER43JKbjppA60vfn9dfsmD1Tkr2w== X-Received: by 2002:a25:51c9:: with SMTP id f192-v6mr8828470ybb.288.1526401352353; Tue, 15 May 2018 09:22:32 -0700 (PDT) Received: from localhost ([72.188.97.40]) by smtp.gmail.com with ESMTPSA id r81-v6sm156289ywb.13.2018.05.15.09.22.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 15 May 2018 09:22:31 -0700 (PDT) From: William Breathitt Gray To: linus.walleij@linaro.org Cc: linux-gpio@vger.kernel.org, linux-arch@vger.kernel.org, linux-kernel@vger.kernel.org, William Breathitt Gray , Arnd Bergmann Subject: [PATCH v4 1/8] bitops: Introduce the for_each_set_clump macro Date: Tue, 15 May 2018 12:22:26 -0400 Message-Id: <87c7edee3bd6789345bd1cc6fd0cb91c2d508eda.1526400945.git.vilhelm.gray@gmail.com> X-Mailer: git-send-email 2.17.0 In-Reply-To: References: Sender: linux-gpio-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-gpio@vger.kernel.org This macro iterates for each group of bits (clump) with set bits, within a bitmap memory region. For each iteration, "clump" is set to the found clump index, "index" is set to the word index of the bitmap containing the found clump, and "offset" is set to the bit offset of the found clump within the respective bitmap word. Suggested-by: Andy Shevchenko Cc: Arnd Bergmann Signed-off-by: William Breathitt Gray --- include/asm-generic/bitops/find.h | 9 +++++++ include/linux/bitops.h | 7 ++++++ lib/find_bit.c | 40 +++++++++++++++++++++++++++++++ 3 files changed, 56 insertions(+) diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h index 8a1ee10014de..3d3b2fc34908 100644 --- a/include/asm-generic/bitops/find.h +++ b/include/asm-generic/bitops/find.h @@ -2,6 +2,8 @@ #ifndef _ASM_GENERIC_BITOPS_FIND_H_ #define _ASM_GENERIC_BITOPS_FIND_H_ +#include + #ifndef find_next_bit /** * find_next_bit - find the next set bit in a memory region @@ -80,4 +82,11 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr, #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ +size_t find_next_clump(size_t *const index, unsigned int *const offset, + const unsigned long *const bits, const size_t size, + const size_t clump_index, const unsigned int clump_size); + +#define find_first_clump(index, offset, bits, size, clump_size) \ + find_next_clump((index), (offset), (bits), (size), 0, (clump_size)) + #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 4cac4e1a72ff..cfaff6a14406 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -59,6 +59,13 @@ extern unsigned long __sw_hweight64(__u64 w); (bit) < (size); \ (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) +#define for_each_set_clump(clump, index, offset, bits, size, clump_size) \ + for ((clump) = find_first_clump(&(index), &(offset), (bits), (size), \ + (clump_size)); \ + (clump) < (size); \ + (clump) = find_next_clump(&(index), &(offset), (bits), (size), \ + (clump) + 1, (clump_size))) + static inline int get_bitmask_order(unsigned int count) { int order; diff --git a/lib/find_bit.c b/lib/find_bit.c index ee3df93ba69a..1d547fe9304f 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -218,3 +218,43 @@ EXPORT_SYMBOL(find_next_bit_le); #endif #endif /* __BIG_ENDIAN */ + +/** + * find_next_clump - find next clump with set bits in a memory region + * @index: location to store bitmap word index of found clump + * @offset: bits offset of the found clump within the respective bitmap word + * @bits: address to base the search on + * @size: bitmap size in number of clumps + * @clump_index: clump index at which to start searching + * @clump_size: clump size in bits + * + * Returns the clump index for the next clump with set bits; the respective + * bitmap word index is stored at the location pointed by @index, and the bits + * offset of the found clump within the respective bitmap word is stored at the + * location pointed by @offset. If no bits are set, returns @size. + */ +size_t find_next_clump(size_t *const index, unsigned int *const offset, + const unsigned long *const bits, const size_t size, + const size_t clump_index, const unsigned int clump_size) +{ + size_t i; + unsigned int bits_offset; + unsigned long word_mask; + const unsigned long clump_mask = GENMASK(clump_size - 1, 0); + + for (i = clump_index; i < size; i++) { + bits_offset = i * clump_size; + + *index = BIT_WORD(bits_offset); + *offset = bits_offset % BITS_PER_LONG; + + word_mask = bits[*index] & (clump_mask << *offset); + if (!word_mask) + continue; + + return i; + } + + return size; +} +EXPORT_SYMBOL(find_next_clump);