blob: 6ed74f78380ce1f6e69568fad0c28d685a5f2048 [file] [log] [blame]
Yury Norov8f6f19d2015-04-16 12:43:16 -07001/* bit search implementation
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 *
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
5 *
Yury Norov8f6f19d2015-04-16 12:43:16 -07006 * Copyright (C) 2008 IBM Corporation
7 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
8 * (Inspired by David Howell's find_next_bit implementation)
9 *
Yury Norov2c57a0e2015-04-16 12:43:13 -070010 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
11 * size and improve performance, 2015.
12 *
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License
15 * as published by the Free Software Foundation; either version
16 * 2 of the License, or (at your option) any later version.
17 */
18
19#include <linux/bitops.h>
Yury Norov8f6f19d2015-04-16 12:43:16 -070020#include <linux/bitmap.h>
Paul Gortmaker8bc3bcc2011-11-16 21:29:17 -050021#include <linux/export.h>
Yury Norov2c57a0e2015-04-16 12:43:13 -070022#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070023
Yury Norov2c57a0e2015-04-16 12:43:13 -070024#if !defined(find_next_bit) || !defined(find_next_zero_bit)
25
26/*
27 * This is a common helper function for find_next_bit and
28 * find_next_zero_bit. The difference is the "invert" argument, which
29 * is XORed with each fetched word before searching it for one bits.
30 */
31static unsigned long _find_next_bit(const unsigned long *addr,
32 unsigned long nbits, unsigned long start, unsigned long invert)
33{
34 unsigned long tmp;
35
Matthew Wilcoxe4afd2e2017-02-24 15:00:58 -080036 if (unlikely(start >= nbits))
Yury Norov2c57a0e2015-04-16 12:43:13 -070037 return nbits;
38
39 tmp = addr[start / BITS_PER_LONG] ^ invert;
40
41 /* Handle 1st word. */
42 tmp &= BITMAP_FIRST_WORD_MASK(start);
43 start = round_down(start, BITS_PER_LONG);
44
45 while (!tmp) {
46 start += BITS_PER_LONG;
47 if (start >= nbits)
48 return nbits;
49
50 tmp = addr[start / BITS_PER_LONG] ^ invert;
51 }
52
53 return min(start + __ffs(tmp), nbits);
54}
55#endif
Akinobu Mitac7f612c2006-03-26 01:39:11 -080056
Akinobu Mita19de85e2011-05-26 16:26:09 -070057#ifndef find_next_bit
Alexander van Heukelum64970b62008-03-11 16:17:19 +010058/*
59 * Find the next set bit in a memory region.
Akinobu Mitac7f612c2006-03-26 01:39:11 -080060 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020061unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
62 unsigned long offset)
Linus Torvalds1da177e2005-04-16 15:20:36 -070063{
Yury Norov2c57a0e2015-04-16 12:43:13 -070064 return _find_next_bit(addr, size, offset, 0UL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070065}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020066EXPORT_SYMBOL(find_next_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -070067#endif
Akinobu Mitac7f612c2006-03-26 01:39:11 -080068
Akinobu Mita19de85e2011-05-26 16:26:09 -070069#ifndef find_next_zero_bit
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020070unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71 unsigned long offset)
Akinobu Mitac7f612c2006-03-26 01:39:11 -080072{
Yury Norov2c57a0e2015-04-16 12:43:13 -070073 return _find_next_bit(addr, size, offset, ~0UL);
Akinobu Mitac7f612c2006-03-26 01:39:11 -080074}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020075EXPORT_SYMBOL(find_next_zero_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -070076#endif
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020077
Akinobu Mita19de85e2011-05-26 16:26:09 -070078#ifndef find_first_bit
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020079/*
80 * Find the first set bit in a memory region.
81 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020082unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020083{
Yury Norov2c57a0e2015-04-16 12:43:13 -070084 unsigned long idx;
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020085
Yury Norov2c57a0e2015-04-16 12:43:13 -070086 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
87 if (addr[idx])
88 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020089 }
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020090
Yury Norov2c57a0e2015-04-16 12:43:13 -070091 return size;
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020092}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020093EXPORT_SYMBOL(find_first_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -070094#endif
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020095
Akinobu Mita19de85e2011-05-26 16:26:09 -070096#ifndef find_first_zero_bit
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +020097/*
98 * Find the first cleared bit in a memory region.
99 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200100unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200101{
Yury Norov2c57a0e2015-04-16 12:43:13 -0700102 unsigned long idx;
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200103
Yury Norov2c57a0e2015-04-16 12:43:13 -0700104 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
105 if (addr[idx] != ~0UL)
106 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200107 }
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200108
Yury Norov2c57a0e2015-04-16 12:43:13 -0700109 return size;
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200110}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200111EXPORT_SYMBOL(find_first_zero_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700112#endif
Akinobu Mita930ae742006-03-26 01:39:15 -0800113
Yury Norov8f6f19d2015-04-16 12:43:16 -0700114#ifndef find_last_bit
115unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
116{
117 if (size) {
118 unsigned long val = BITMAP_LAST_WORD_MASK(size);
119 unsigned long idx = (size-1) / BITS_PER_LONG;
120
121 do {
122 val &= addr[idx];
123 if (val)
124 return idx * BITS_PER_LONG + __fls(val);
125
126 val = ~0ul;
127 } while (idx--);
128 }
129 return size;
130}
131EXPORT_SYMBOL(find_last_bit);
132#endif
133
Akinobu Mita930ae742006-03-26 01:39:15 -0800134#ifdef __BIG_ENDIAN
135
136/* include/linux/byteorder does not support "unsigned long" type */
Akinobu Mita930ae742006-03-26 01:39:15 -0800137static inline unsigned long ext2_swab(const unsigned long y)
138{
139#if BITS_PER_LONG == 64
140 return (unsigned long) __swab64((u64) y);
141#elif BITS_PER_LONG == 32
142 return (unsigned long) __swab32((u32) y);
143#else
144#error BITS_PER_LONG not defined
145#endif
146}
147
Yury Norov2c57a0e2015-04-16 12:43:13 -0700148#if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
149static unsigned long _find_next_bit_le(const unsigned long *addr,
150 unsigned long nbits, unsigned long start, unsigned long invert)
151{
152 unsigned long tmp;
153
Matthew Wilcoxe4afd2e2017-02-24 15:00:58 -0800154 if (unlikely(start >= nbits))
Yury Norov2c57a0e2015-04-16 12:43:13 -0700155 return nbits;
156
157 tmp = addr[start / BITS_PER_LONG] ^ invert;
158
159 /* Handle 1st word. */
160 tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
161 start = round_down(start, BITS_PER_LONG);
162
163 while (!tmp) {
164 start += BITS_PER_LONG;
165 if (start >= nbits)
166 return nbits;
167
168 tmp = addr[start / BITS_PER_LONG] ^ invert;
169 }
170
171 return min(start + __ffs(ext2_swab(tmp)), nbits);
172}
173#endif
174
Akinobu Mita19de85e2011-05-26 16:26:09 -0700175#ifndef find_next_zero_bit_le
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700176unsigned long find_next_zero_bit_le(const void *addr, unsigned
Akinobu Mita930ae742006-03-26 01:39:15 -0800177 long size, unsigned long offset)
178{
Yury Norov2c57a0e2015-04-16 12:43:13 -0700179 return _find_next_bit_le(addr, size, offset, ~0UL);
Akinobu Mita930ae742006-03-26 01:39:15 -0800180}
Akinobu Mitac4945b92011-03-23 16:41:47 -0700181EXPORT_SYMBOL(find_next_zero_bit_le);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700182#endif
Akinobu Mita930ae742006-03-26 01:39:15 -0800183
Akinobu Mita19de85e2011-05-26 16:26:09 -0700184#ifndef find_next_bit_le
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700185unsigned long find_next_bit_le(const void *addr, unsigned
Aneesh Kumar K.Vaa02ad62008-01-28 23:58:27 -0500186 long size, unsigned long offset)
187{
Yury Norov2c57a0e2015-04-16 12:43:13 -0700188 return _find_next_bit_le(addr, size, offset, 0UL);
Aneesh Kumar K.Vaa02ad62008-01-28 23:58:27 -0500189}
Akinobu Mitac4945b92011-03-23 16:41:47 -0700190EXPORT_SYMBOL(find_next_bit_le);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700191#endif
Akinobu Mita06649962011-03-23 16:41:59 -0700192
Akinobu Mita930ae742006-03-26 01:39:15 -0800193#endif /* __BIG_ENDIAN */