Back to home page

LXR

 
 

    


0001 /* bit search implementation
0002  *
0003  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
0004  * Written by David Howells (dhowells@redhat.com)
0005  *
0006  * Copyright (C) 2008 IBM Corporation
0007  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
0008  * (Inspired by David Howell's find_next_bit implementation)
0009  *
0010  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
0011  * size and improve performance, 2015.
0012  *
0013  * This program is free software; you can redistribute it and/or
0014  * modify it under the terms of the GNU General Public License
0015  * as published by the Free Software Foundation; either version
0016  * 2 of the License, or (at your option) any later version.
0017  */
0018 
0019 #include <linux/bitops.h>
0020 #include <linux/bitmap.h>
0021 #include <linux/export.h>
0022 #include <linux/kernel.h>
0023 
0024 #if !defined(find_next_bit) || !defined(find_next_zero_bit)
0025 
0026 /*
0027  * This is a common helper function for find_next_bit and
0028  * find_next_zero_bit.  The difference is the "invert" argument, which
0029  * is XORed with each fetched word before searching it for one bits.
0030  */
0031 static unsigned long _find_next_bit(const unsigned long *addr,
0032         unsigned long nbits, unsigned long start, unsigned long invert)
0033 {
0034     unsigned long tmp;
0035 
0036     if (!nbits || start >= nbits)
0037         return nbits;
0038 
0039     tmp = addr[start / BITS_PER_LONG] ^ invert;
0040 
0041     /* Handle 1st word. */
0042     tmp &= BITMAP_FIRST_WORD_MASK(start);
0043     start = round_down(start, BITS_PER_LONG);
0044 
0045     while (!tmp) {
0046         start += BITS_PER_LONG;
0047         if (start >= nbits)
0048             return nbits;
0049 
0050         tmp = addr[start / BITS_PER_LONG] ^ invert;
0051     }
0052 
0053     return min(start + __ffs(tmp), nbits);
0054 }
0055 #endif
0056 
0057 #ifndef find_next_bit
0058 /*
0059  * Find the next set bit in a memory region.
0060  */
0061 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
0062                 unsigned long offset)
0063 {
0064     return _find_next_bit(addr, size, offset, 0UL);
0065 }
0066 EXPORT_SYMBOL(find_next_bit);
0067 #endif
0068 
0069 #ifndef find_next_zero_bit
0070 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
0071                  unsigned long offset)
0072 {
0073     return _find_next_bit(addr, size, offset, ~0UL);
0074 }
0075 EXPORT_SYMBOL(find_next_zero_bit);
0076 #endif
0077 
0078 #ifndef find_first_bit
0079 /*
0080  * Find the first set bit in a memory region.
0081  */
0082 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
0083 {
0084     unsigned long idx;
0085 
0086     for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
0087         if (addr[idx])
0088             return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
0089     }
0090 
0091     return size;
0092 }
0093 EXPORT_SYMBOL(find_first_bit);
0094 #endif
0095 
0096 #ifndef find_first_zero_bit
0097 /*
0098  * Find the first cleared bit in a memory region.
0099  */
0100 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
0101 {
0102     unsigned long idx;
0103 
0104     for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
0105         if (addr[idx] != ~0UL)
0106             return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
0107     }
0108 
0109     return size;
0110 }
0111 EXPORT_SYMBOL(find_first_zero_bit);
0112 #endif
0113 
0114 #ifndef find_last_bit
0115 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
0116 {
0117     if (size) {
0118         unsigned long val = BITMAP_LAST_WORD_MASK(size);
0119         unsigned long idx = (size-1) / BITS_PER_LONG;
0120 
0121         do {
0122             val &= addr[idx];
0123             if (val)
0124                 return idx * BITS_PER_LONG + __fls(val);
0125 
0126             val = ~0ul;
0127         } while (idx--);
0128     }
0129     return size;
0130 }
0131 EXPORT_SYMBOL(find_last_bit);
0132 #endif
0133 
0134 #ifdef __BIG_ENDIAN
0135 
0136 /* include/linux/byteorder does not support "unsigned long" type */
0137 static inline unsigned long ext2_swab(const unsigned long y)
0138 {
0139 #if BITS_PER_LONG == 64
0140     return (unsigned long) __swab64((u64) y);
0141 #elif BITS_PER_LONG == 32
0142     return (unsigned long) __swab32((u32) y);
0143 #else
0144 #error BITS_PER_LONG not defined
0145 #endif
0146 }
0147 
0148 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
0149 static unsigned long _find_next_bit_le(const unsigned long *addr,
0150         unsigned long nbits, unsigned long start, unsigned long invert)
0151 {
0152     unsigned long tmp;
0153 
0154     if (!nbits || start >= nbits)
0155         return nbits;
0156 
0157     tmp = addr[start / BITS_PER_LONG] ^ invert;
0158 
0159     /* Handle 1st word. */
0160     tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
0161     start = round_down(start, BITS_PER_LONG);
0162 
0163     while (!tmp) {
0164         start += BITS_PER_LONG;
0165         if (start >= nbits)
0166             return nbits;
0167 
0168         tmp = addr[start / BITS_PER_LONG] ^ invert;
0169     }
0170 
0171     return min(start + __ffs(ext2_swab(tmp)), nbits);
0172 }
0173 #endif
0174 
0175 #ifndef find_next_zero_bit_le
0176 unsigned long find_next_zero_bit_le(const void *addr, unsigned
0177         long size, unsigned long offset)
0178 {
0179     return _find_next_bit_le(addr, size, offset, ~0UL);
0180 }
0181 EXPORT_SYMBOL(find_next_zero_bit_le);
0182 #endif
0183 
0184 #ifndef find_next_bit_le
0185 unsigned long find_next_bit_le(const void *addr, unsigned
0186         long size, unsigned long offset)
0187 {
0188     return _find_next_bit_le(addr, size, offset, 0UL);
0189 }
0190 EXPORT_SYMBOL(find_next_bit_le);
0191 #endif
0192 
0193 #endif /* __BIG_ENDIAN */