1// SPDX-License-Identifier: GPL-2.0-or-later
  2/* bit search implementation
  3 *
  4 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  5 * Written by David Howells (dhowells@redhat.com)
  6 *
  7 * Copyright (C) 2008 IBM Corporation
  8 * '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 decrease
 12 * 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#if !defined(find_next_bit) || !defined(find_next_zero_bit) ||			\
 23	!defined(find_next_bit_le) || !defined(find_next_zero_bit_le) ||	\
 24	!defined(find_next_and_bit)
 25/*
 26 * This is a common helper function for find_next_bit, find_next_zero_bit, and
 27 * find_next_and_bit. The differences are:
 28 *  - The "invert" argument, which is XORed with each fetched word before
 29 *    searching it for one bits.
 30 *  - The optional "addr2", which is anded with "addr1" if present.
 31 */
 32unsigned long _find_next_bit(const unsigned long *addr1,
 33		const unsigned long *addr2, unsigned long nbits,
 34		unsigned long start, unsigned long invert, unsigned long le)
 35{
 36	unsigned long tmp, mask;
 37
 38	if (unlikely(start >= nbits))
 39		return nbits;
 40
 41	tmp = addr1[start / BITS_PER_LONG];
 42	if (addr2)
 43		tmp &= addr2[start / BITS_PER_LONG];
 44	tmp ^= invert;
 45
 46	/* Handle 1st word. */
 47	mask = BITMAP_FIRST_WORD_MASK(start);
 48	if (le)
 49		mask = swab(mask);
 50
 51	tmp &= mask;
 52
 53	start = round_down(start, BITS_PER_LONG);
 54
 55	while (!tmp) {
 56		start += BITS_PER_LONG;
 57		if (start >= nbits)
 58			return nbits;
 59
 60		tmp = addr1[start / BITS_PER_LONG];
 61		if (addr2)
 62			tmp &= addr2[start / BITS_PER_LONG];
 63		tmp ^= invert;
 64	}
 65
 66	if (le)
 67		tmp = swab(tmp);
 68
 69	return min(start + __ffs(tmp), nbits);
 70}
 71EXPORT_SYMBOL(_find_next_bit);
 72#endif
 73
 74#ifndef find_first_bit
 75/*
 76 * Find the first set bit in a memory region.
 77 */
 78unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
 79{
 80	unsigned long idx;
 81
 82	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 83		if (addr[idx])
 84			return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
 85	}
 86
 87	return size;
 88}
 89EXPORT_SYMBOL(_find_first_bit);
 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	unsigned long idx;
 99
100	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
101		if (addr[idx] != ~0UL)
102			return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
103	}
104
105	return size;
106}
107EXPORT_SYMBOL(_find_first_zero_bit);
108#endif
109
110#ifndef find_last_bit
111unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
112{
113	if (size) {
114		unsigned long val = BITMAP_LAST_WORD_MASK(size);
115		unsigned long idx = (size-1) / BITS_PER_LONG;
116
117		do {
118			val &= addr[idx];
119			if (val)
120				return idx * BITS_PER_LONG + __fls(val);
121
122			val = ~0ul;
123		} while (idx--);
124	}
125	return size;
126}
127EXPORT_SYMBOL(_find_last_bit);
128#endif
129
130unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
131			       unsigned long size, unsigned long offset)
132{
133	offset = find_next_bit(addr, size, offset);
134	if (offset == size)
135		return size;
136
137	offset = round_down(offset, 8);
138	*clump = bitmap_get_value8(addr, offset);
139
140	return offset;
141}
142EXPORT_SYMBOL(find_next_clump8);