blob: c05b4b19cf6cac90e407eac98e870130bbb3e66a [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/* find_next_bit.c: fallback find next bit implementation
2 *
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 */
11
12#include <linux/bitops.h>
David Howells40234402006-01-08 01:01:19 -080013#include <linux/module.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070014
15int find_next_bit(const unsigned long *addr, int size, int offset)
16{
17 const unsigned long *base;
18 const int NBITS = sizeof(*addr) * 8;
19 unsigned long tmp;
20
21 base = addr;
22 if (offset) {
23 int suboffset;
24
25 addr += offset / NBITS;
26
27 suboffset = offset % NBITS;
28 if (suboffset) {
29 tmp = *addr;
30 tmp >>= suboffset;
31 if (tmp)
32 goto finish;
33 }
34
35 addr++;
36 }
37
38 while ((tmp = *addr) == 0)
39 addr++;
40
41 offset = (addr - base) * NBITS;
42
43 finish:
44 /* count the remaining bits without using __ffs() since that takes a 32-bit arg */
45 while (!(tmp & 0xff)) {
46 offset += 8;
47 tmp >>= 8;
48 }
49
50 while (!(tmp & 1)) {
51 offset++;
52 tmp >>= 1;
53 }
54
55 return offset;
56}
David Howells40234402006-01-08 01:01:19 -080057
58EXPORT_SYMBOL(find_next_bit);