// SPDX-License-Identifier: GPL-2.0-or-later
/* bit search implementation
 *
 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 *
 * Copyright (C) 2008 IBM Corporation
 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
 * (Inspired by David Howell's find_next_bit implementation)
 *
 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
 * size and improve performance, 2015.
 */

#include <linux/bitops.h>
#include <linux/bitmap.h>
#include <linux/export.h>
#include <linux/math.h>
#include <linux/minmax.h>
#include <linux/swab.h>

#define BIT_FIND_SETUP(addr, size, start)			\
	unsigned long val, idx;					\
	if (unlikely(start >= size))				\
		return size;					\
	idx = start / BITS_PER_LONG;

#define BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION)	\
	if (!IS_ALIGNED(start, BITS_PER_LONG)) {		\
		unsigned long mask;				\
		mask = BITMAP_FIRST_WORD_MASK(start);		\
		if ((val = mask & (EXPRESSION)) != 0)		\
			goto found;				\
		idx++;						\
	}

#define BIT_WORD_LOOP(ptr, size, idx, val, EXPRESSION)		\
	do {							\
		if ((val = (EXPRESSION)) != 0)			\
			 goto found;				\
		idx++;						\
	} while ((idx)*BITS_PER_LONG < (size));

#define BIT_FIND_BODY(addr, size, start, EXPRESSION)		\
	BIT_FIND_SETUP(addr, size, start)			\
	BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION)	\
	BIT_WORD_LOOP(addr, size, idx, val, EXPRESSION)	\
	return size;						\
found:	BIT_WORD_SWAB(val);					\
	return min((idx)*BITS_PER_LONG + __ffs(val), size)

#define BIT_WORD_SWAB(x) /* Nothing */

unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
{ BIT_FIND_BODY(addr, size, 0, addr[idx]); }

unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
{ BIT_FIND_BODY(addr, size, 0, ~addr[idx]); }

unsigned long _find_next_bit(const unsigned long *addr, unsigned long size, unsigned long start)
{ BIT_FIND_BODY(addr, size, start, addr[idx]); }

unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long size, unsigned long start)
{ BIT_FIND_BODY(addr, size, start, ~addr[idx]); }

unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size)
{ BIT_FIND_BODY(addr, size, 0, addr1[idx] & addr2[idx]); }

unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long start)
{ BIT_FIND_BODY(addr, size, start, addr1[idx] & addr2[idx]); }

#ifdef __BIG_ENDIAN

#undef BIT_WORD_SWAB
#define BIT_WORD_SWAB(val) val = swab(val)

.. FIXME: same as above, now with _find_first_bit_le() etc ..

#endif

#ifndef find_last_bit
unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
{
	if (size) {
		unsigned long val = BITMAP_LAST_WORD_MASK(size);
		unsigned long idx = (size-1) / BITS_PER_LONG;

		do {
			val &= addr[idx];
			if (val)
				return idx * BITS_PER_LONG + __fls(val);

			val = ~0ul;
		} while (idx--);
	}
	return size;
}
EXPORT_SYMBOL(_find_last_bit);
#endif

unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
			       unsigned long size, unsigned long offset)
{
	offset = find_next_bit(addr, size, offset);
	if (offset == size)
		return size;

	offset = round_down(offset, 8);
	*clump = bitmap_get_value8(addr, offset);

	return offset;
}
EXPORT_SYMBOL(find_next_clump8);