283 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/* bit search implementation3 *4 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.5 * Written by David Howells (dhowells@redhat.com)6 *7 * Copyright (C) 2008 IBM Corporation8 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>9 * (Inspired by David Howell's find_next_bit implementation)10 *11 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease12 * size and improve performance, 2015.13 */14 15#include <linux/bitops.h>16#include <linux/bitmap.h>17#include <linux/export.h>18#include <linux/math.h>19#include <linux/minmax.h>20#include <linux/swab.h>21 22/*23 * Common helper for find_bit() function family24 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)25 * @MUNGE: The expression that post-processes a word containing found bit (may be empty)26 * @size: The bitmap size in bits27 */28#define FIND_FIRST_BIT(FETCH, MUNGE, size) \29({ \30 unsigned long idx, val, sz = (size); \31 \32 for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \33 val = (FETCH); \34 if (val) { \35 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \36 break; \37 } \38 } \39 \40 sz; \41})42 43/*44 * Common helper for find_next_bit() function family45 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)46 * @MUNGE: The expression that post-processes a word containing found bit (may be empty)47 * @size: The bitmap size in bits48 * @start: The bitnumber to start searching at49 */50#define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \51({ \52 unsigned long mask, idx, tmp, sz = (size), __start = (start); \53 \54 if (unlikely(__start >= sz)) \55 goto out; \56 \57 mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \58 idx = __start / BITS_PER_LONG; \59 \60 for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \61 if ((idx + 1) * BITS_PER_LONG >= sz) \62 goto out; \63 idx++; \64 } \65 \66 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \67out: \68 sz; \69})70 71#define FIND_NTH_BIT(FETCH, size, num) \72({ \73 unsigned long sz = (size), nr = (num), idx, w, tmp; \74 \75 for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \76 if (idx * BITS_PER_LONG + nr >= sz) \77 goto out; \78 \79 tmp = (FETCH); \80 w = hweight_long(tmp); \81 if (w > nr) \82 goto found; \83 \84 nr -= w; \85 } \86 \87 if (sz % BITS_PER_LONG) \88 tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \89found: \90 sz = idx * BITS_PER_LONG + fns(tmp, nr); \91out: \92 sz; \93})94 95#ifndef find_first_bit96/*97 * Find the first set bit in a memory region.98 */99unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)100{101 return FIND_FIRST_BIT(addr[idx], /* nop */, size);102}103EXPORT_SYMBOL(_find_first_bit);104#endif105 106#ifndef find_first_and_bit107/*108 * Find the first set bit in two memory regions.109 */110unsigned long _find_first_and_bit(const unsigned long *addr1,111 const unsigned long *addr2,112 unsigned long size)113{114 return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size);115}116EXPORT_SYMBOL(_find_first_and_bit);117#endif118 119/*120 * Find the first set bit in three memory regions.121 */122unsigned long _find_first_and_and_bit(const unsigned long *addr1,123 const unsigned long *addr2,124 const unsigned long *addr3,125 unsigned long size)126{127 return FIND_FIRST_BIT(addr1[idx] & addr2[idx] & addr3[idx], /* nop */, size);128}129EXPORT_SYMBOL(_find_first_and_and_bit);130 131#ifndef find_first_zero_bit132/*133 * Find the first cleared bit in a memory region.134 */135unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)136{137 return FIND_FIRST_BIT(~addr[idx], /* nop */, size);138}139EXPORT_SYMBOL(_find_first_zero_bit);140#endif141 142#ifndef find_next_bit143unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)144{145 return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);146}147EXPORT_SYMBOL(_find_next_bit);148#endif149 150unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)151{152 return FIND_NTH_BIT(addr[idx], size, n);153}154EXPORT_SYMBOL(__find_nth_bit);155 156unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,157 unsigned long size, unsigned long n)158{159 return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n);160}161EXPORT_SYMBOL(__find_nth_and_bit);162 163unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,164 unsigned long size, unsigned long n)165{166 return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);167}168EXPORT_SYMBOL(__find_nth_andnot_bit);169 170unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,171 const unsigned long *addr2,172 const unsigned long *addr3,173 unsigned long size, unsigned long n)174{175 return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);176}177EXPORT_SYMBOL(__find_nth_and_andnot_bit);178 179#ifndef find_next_and_bit180unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,181 unsigned long nbits, unsigned long start)182{183 return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);184}185EXPORT_SYMBOL(_find_next_and_bit);186#endif187 188#ifndef find_next_andnot_bit189unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,190 unsigned long nbits, unsigned long start)191{192 return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);193}194EXPORT_SYMBOL(_find_next_andnot_bit);195#endif196 197#ifndef find_next_or_bit198unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,199 unsigned long nbits, unsigned long start)200{201 return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);202}203EXPORT_SYMBOL(_find_next_or_bit);204#endif205 206#ifndef find_next_zero_bit207unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,208 unsigned long start)209{210 return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);211}212EXPORT_SYMBOL(_find_next_zero_bit);213#endif214 215#ifndef find_last_bit216unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)217{218 if (size) {219 unsigned long val = BITMAP_LAST_WORD_MASK(size);220 unsigned long idx = (size-1) / BITS_PER_LONG;221 222 do {223 val &= addr[idx];224 if (val)225 return idx * BITS_PER_LONG + __fls(val);226 227 val = ~0ul;228 } while (idx--);229 }230 return size;231}232EXPORT_SYMBOL(_find_last_bit);233#endif234 235unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,236 unsigned long size, unsigned long offset)237{238 offset = find_next_bit(addr, size, offset);239 if (offset == size)240 return size;241 242 offset = round_down(offset, 8);243 *clump = bitmap_get_value8(addr, offset);244 245 return offset;246}247EXPORT_SYMBOL(find_next_clump8);248 249#ifdef __BIG_ENDIAN250 251#ifndef find_first_zero_bit_le252/*253 * Find the first cleared bit in an LE memory region.254 */255unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)256{257 return FIND_FIRST_BIT(~addr[idx], swab, size);258}259EXPORT_SYMBOL(_find_first_zero_bit_le);260 261#endif262 263#ifndef find_next_zero_bit_le264unsigned long _find_next_zero_bit_le(const unsigned long *addr,265 unsigned long size, unsigned long offset)266{267 return FIND_NEXT_BIT(~addr[idx], swab, size, offset);268}269EXPORT_SYMBOL(_find_next_zero_bit_le);270#endif271 272#ifndef find_next_bit_le273unsigned long _find_next_bit_le(const unsigned long *addr,274 unsigned long size, unsigned long offset)275{276 return FIND_NEXT_BIT(addr[idx], swab, size, offset);277}278EXPORT_SYMBOL(_find_next_bit_le);279 280#endif281 282#endif /* __BIG_ENDIAN */283