LXR linux/arch/s390/lib/find.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * MSB0 numbered special bitops handling.
   4 *
   5 * The bits are numbered:
   6 *   |0..............63|64............127|128...........191|192...........255|
   7 *
   8 * The reason for this bit numbering is the fact that the hardware sets bits
   9 * in a bitmap starting at bit 0 (MSB) and we don't want to scan the bitmap
  10 * from the 'wrong end'.
  11 */
  12
  13#include <linux/compiler.h>
  14#include <linux/bitops.h>
  15#include <linux/export.h>
  16
  17unsigned long find_first_bit_inv(const unsigned long *addr, unsigned long size)
  18{
  19        const unsigned long *p = addr;
  20        unsigned long result = 0;
  21        unsigned long tmp;
  22
  23        while (size & ~(BITS_PER_LONG - 1)) {
  24                if ((tmp = *(p++)))
  25                        goto found;
  26                result += BITS_PER_LONG;
  27                size -= BITS_PER_LONG;
  28        }
  29        if (!size)
  30                return result;
  31        tmp = (*p) & (~0UL << (BITS_PER_LONG - size));
  32        if (!tmp)               /* Are any bits set? */
  33                return result + size;   /* Nope. */
  34found:
  35        return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
  36}
  37EXPORT_SYMBOL(find_first_bit_inv);
  38
  39unsigned long find_next_bit_inv(const unsigned long *addr, unsigned long size,
  40                                unsigned long offset)
  41{
  42        const unsigned long *p = addr + (offset / BITS_PER_LONG);
  43        unsigned long result = offset & ~(BITS_PER_LONG - 1);
  44        unsigned long tmp;
  45
  46        if (offset >= size)
  47                return size;
  48        size -= result;
  49        offset %= BITS_PER_LONG;
  50        if (offset) {
  51                tmp = *(p++);
  52                tmp &= (~0UL >> offset);
  53                if (size < BITS_PER_LONG)
  54                        goto found_first;
  55                if (tmp)
  56                        goto found_middle;
  57                size -= BITS_PER_LONG;
  58                result += BITS_PER_LONG;
  59        }
  60        while (size & ~(BITS_PER_LONG-1)) {
  61                if ((tmp = *(p++)))
  62                        goto found_middle;
  63                result += BITS_PER_LONG;
  64                size -= BITS_PER_LONG;
  65        }
  66        if (!size)
  67                return result;
  68        tmp = *p;
  69found_first:
  70        tmp &= (~0UL << (BITS_PER_LONG - size));
  71        if (!tmp)               /* Are any bits set? */
  72                return result + size;   /* Nope. */
  73found_middle:
  74        return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
  75}
  76EXPORT_SYMBOL(find_next_bit_inv);
  77