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 */
  31unsigned long _find_next_bit(const unsigned long *addr1,
  32                const unsigned long *addr2, unsigned long nbits,
  33                unsigned long start, unsigned long invert, unsigned long le)
  34{
  35        unsigned long tmp, mask;
  36        (void) le;
  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
  49        /*
  50         * Due to the lack of swab() in tools, and the fact that it doesn't
  51         * need little-endian support, just comment it out
  52         */
  53#if (0)
  54        if (le)
  55                mask = swab(mask);
  56#endif
  57
  58        tmp &= mask;
  59
  60        start = round_down(start, BITS_PER_LONG);
  61
  62        while (!tmp) {
  63                start += BITS_PER_LONG;
  64                if (start >= nbits)
  65                        return nbits;
  66
  67                tmp = addr1[start / BITS_PER_LONG];
  68                if (addr2)
  69                        tmp &= addr2[start / BITS_PER_LONG];
  70                tmp ^= invert;
  71        }
  72
  73#if (0)
  74        if (le)
  75                tmp = swab(tmp);
  76#endif
  77
  78        return min(start + __ffs(tmp), nbits);
  79}
  80#endif
  81
  82#ifndef find_first_bit
  83/*
  84 * Find the first set bit in a memory region.
  85 */
  86unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
  87{
  88        unsigned long idx;
  89
  90        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  91                if (addr[idx])
  92                        return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  93        }
  94
  95        return size;
  96}
  97#endif
  98
  99#ifndef find_first_and_bit
 100/*
 101 * Find the first set bit in two memory regions.
 102 */
 103unsigned long _find_first_and_bit(const unsigned long *addr1,
 104                                  const unsigned long *addr2,
 105                                  unsigned long size)
 106{
 107        unsigned long idx, val;
 108
 109        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 110                val = addr1[idx] & addr2[idx];
 111                if (val)
 112                        return min(idx * BITS_PER_LONG + __ffs(val), size);
 113        }
 114
 115        return size;
 116}
 117#endif
 118
 119#ifndef find_first_zero_bit
 120/*
 121 * Find the first cleared bit in a memory region.
 122 */
 123unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
 124{
 125        unsigned long idx;
 126
 127        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 128                if (addr[idx] != ~0UL)
 129                        return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 130        }
 131
 132        return size;
 133}
 134#endif
 135