1// SPDX-License-Identifier: GPL-2.0-or-later 2/* bit search implementation 3 * 4 * Copied from lib/find_bit.c to tools/lib/find_bit.c 5 * 6 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 7 * Written by David Howells (dhowells@redhat.com) 8 * 9 * Copyright (C) 2008 IBM Corporation 10 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> 11 * (Inspired by David Howell's find_next_bit implementation) 12 * 13 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease 14 * size and improve performance, 2015. 15 */ 16 17#include <linux/bitops.h> 18#include <linux/bitmap.h> 19#include <linux/kernel.h> 20 21/* 22 * Common helper for find_bit() function family 23 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) 24 * @MUNGE: The expression that post-processes a word containing found bit (may be empty) 25 * @size: The bitmap size in bits 26 */ 27#define FIND_FIRST_BIT(FETCH, MUNGE, size) \ 28({ \ 29 unsigned long idx, val, sz = (size); \ 30 \ 31 for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ 32 val = (FETCH); \ 33 if (val) { \ 34 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ 35 break; \ 36 } \ 37 } \ 38 \ 39 sz; \ 40}) 41 42/* 43 * Common helper for find_next_bit() function family 44 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) 45 * @MUNGE: The expression that post-processes a word containing found bit (may be empty) 46 * @size: The bitmap size in bits 47 * @start: The bitnumber to start searching at 48 */ 49#define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ 50({ \ 51 unsigned long mask, idx, tmp, sz = (size), __start = (start); \ 52 \ 53 if (unlikely(__start >= sz)) \ 54 goto out; \ 55 \ 56 mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ 57 idx = __start / BITS_PER_LONG; \ 58 \ 59 for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \ 60 if ((idx + 1) * BITS_PER_LONG >= sz) \ 61 goto out; \ 62 idx++; \ 63 } \ 64 \ 65 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ 66out: \ 67 sz; \ 68}) 69 70#ifndef find_first_bit 71/* 72 * Find the first set bit in a memory region. 73 */ 74unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) 75{ 76 return FIND_FIRST_BIT(addr[idx], /* nop */, size); 77} 78#endif 79 80#ifndef find_first_and_bit 81/* 82 * Find the first set bit in two memory regions. 83 */ 84unsigned long _find_first_and_bit(const unsigned long *addr1, 85 const unsigned long *addr2, 86 unsigned long size) 87{ 88 return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); 89} 90#endif 91 92#ifndef find_first_zero_bit 93/* 94 * Find the first cleared bit in a memory region. 95 */ 96unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) 97{ 98 return FIND_FIRST_BIT(~addr[idx], /* nop */, size); 99} 100#endif 101 102#ifndef find_next_bit 103unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start) 104{ 105 return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); 106} 107#endif 108 109#ifndef find_next_and_bit 110unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, 111 unsigned long nbits, unsigned long start) 112{ 113 return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); 114} 115#endif 116 117#ifndef find_next_zero_bit 118unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, 119 unsigned long start) 120{ 121 return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); 122} 123#endif 124