1 /* find_next_bit.c: fallback find next bit implementation 2 * 3 * Copied from lib/find_next_bit.c to tools/lib/next_bit.c 4 * 5 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 6 * Written by David Howells (dhowells@redhat.com) 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License 10 * as published by the Free Software Foundation; either version 11 * 2 of the License, or (at your option) any later version. 12 */ 13 14 #include <linux/bitops.h> 15 #include <asm/types.h> 16 #include <asm/byteorder.h> 17 18 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) 19 20 #ifndef find_next_bit 21 /* 22 * Find the next set bit in a memory region. 23 */ find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)24unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 25 unsigned long offset) 26 { 27 const unsigned long *p = addr + BITOP_WORD(offset); 28 unsigned long result = offset & ~(BITS_PER_LONG-1); 29 unsigned long tmp; 30 31 if (offset >= size) 32 return size; 33 size -= result; 34 offset %= BITS_PER_LONG; 35 if (offset) { 36 tmp = *(p++); 37 tmp &= (~0UL << offset); 38 if (size < BITS_PER_LONG) 39 goto found_first; 40 if (tmp) 41 goto found_middle; 42 size -= BITS_PER_LONG; 43 result += BITS_PER_LONG; 44 } 45 while (size & ~(BITS_PER_LONG-1)) { 46 if ((tmp = *(p++))) 47 goto found_middle; 48 result += BITS_PER_LONG; 49 size -= BITS_PER_LONG; 50 } 51 if (!size) 52 return result; 53 tmp = *p; 54 55 found_first: 56 tmp &= (~0UL >> (BITS_PER_LONG - size)); 57 if (tmp == 0UL) /* Are any bits set? */ 58 return result + size; /* Nope. */ 59 found_middle: 60 return result + __ffs(tmp); 61 } 62 #endif 63 64 #ifndef find_first_bit 65 /* 66 * Find the first set bit in a memory region. 67 */ find_first_bit(const unsigned long * addr,unsigned long size)68unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 69 { 70 const unsigned long *p = addr; 71 unsigned long result = 0; 72 unsigned long tmp; 73 74 while (size & ~(BITS_PER_LONG-1)) { 75 if ((tmp = *(p++))) 76 goto found; 77 result += BITS_PER_LONG; 78 size -= BITS_PER_LONG; 79 } 80 if (!size) 81 return result; 82 83 tmp = (*p) & (~0UL >> (BITS_PER_LONG - size)); 84 if (tmp == 0UL) /* Are any bits set? */ 85 return result + size; /* Nope. */ 86 found: 87 return result + __ffs(tmp); 88 } 89 #endif 90