1 /* 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/types.h> 13 #include <linux/bitops.h> 14 15 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) 16 17 /* 18 * Find the next set bit in a memory region. 19 */ find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)20unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 21 unsigned long offset) 22 { 23 const unsigned long *p = addr + BITOP_WORD(offset); 24 unsigned long result = offset & ~(BITS_PER_LONG-1); 25 unsigned long tmp; 26 27 if (offset >= size) 28 return size; 29 size -= result; 30 offset %= BITS_PER_LONG; 31 if (offset) { 32 tmp = *(p++); 33 tmp &= (~0UL << offset); 34 if (size < BITS_PER_LONG) 35 goto found_first; 36 if (tmp) 37 goto found_middle; 38 size -= BITS_PER_LONG; 39 result += BITS_PER_LONG; 40 } 41 while (size & ~(BITS_PER_LONG-1)) { 42 if ((tmp = *(p++))) 43 goto found_middle; 44 result += BITS_PER_LONG; 45 size -= BITS_PER_LONG; 46 } 47 if (!size) 48 return result; 49 tmp = *p; 50 51 found_first: 52 tmp &= (~0UL >> (BITS_PER_LONG - size)); 53 if (tmp == 0UL) /* Are any bits set? */ 54 return result + size; /* Nope. */ 55 found_middle: 56 return result + __ffs(tmp); 57 } 58