LXR linux/tools/lib/find

   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#if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
  22                !defined(find_next_and_bit)
  23
  24/*
  25 * This is a common helper function for find_next_bit, find_next_zero_bit, and
  26 * find_next_and_bit. The differences are:
  27 *  - The "invert" argument, which is XORed with each fetched word before
  28 *    searching it for one bits.
  29 *  - The optional "addr2", which is anded with "addr1" if present.
  30 */
  31static inline unsigned long _find_next_bit(const unsigned long *addr1,
  32                const unsigned long *addr2, unsigned long nbits,
  33                unsigned long start, unsigned long invert)
  34{
  35        unsigned long tmp;
  36
  37        if (unlikely(start >= nbits))
  38                return nbits;
  39
  40        tmp = addr1[start / BITS_PER_LONG];
  41        if (addr2)
  42                tmp &= addr2[start / BITS_PER_LONG];
  43        tmp ^= invert;
  44
  45        /* Handle 1st word. */
  46        tmp &= BITMAP_FIRST_WORD_MASK(start);
  47        start = round_down(start, BITS_PER_LONG);
  48
  49        while (!tmp) {
  50                start += BITS_PER_LONG;
  51                if (start >= nbits)
  52                        return nbits;
  53
  54                tmp = addr1[start / BITS_PER_LONG];
  55                if (addr2)
  56                        tmp &= addr2[start / BITS_PER_LONG];
  57                tmp ^= invert;
  58        }
  59
  60        return min(start + __ffs(tmp), nbits);
  61}
  62#endif
  63
  64#ifndef find_next_bit
  65/*
  66 * Find the next set bit in a memory region.
  67 */
  68unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  69                            unsigned long offset)
  70{
  71        return _find_next_bit(addr, NULL, size, offset, 0UL);
  72}
  73#endif
  74
  75#ifndef find_first_bit
  76/*
  77 * Find the first set bit in a memory region.
  78 */
  79unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  80{
  81        unsigned long idx;
  82
  83        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  84                if (addr[idx])
  85                        return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  86        }
  87
  88        return 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        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}
 107#endif
 108
 109#ifndef find_next_zero_bit
 110unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 111                                 unsigned long offset)
 112{
 113        return _find_next_bit(addr, NULL, size, offset, ~0UL);
 114}
 115#endif
 116
 117#ifndef find_next_and_bit
 118unsigned long find_next_and_bit(const unsigned long *addr1,
 119                const unsigned long *addr2, unsigned long size,
 120                unsigned long offset)
 121{
 122        return _find_next_bit(addr1, addr2, size, offset, 0UL);
 123}
 124#endif
 125