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/bitops.h> 13#include <linux/export.h> 14#include <asm/types.h> 15#include <asm/byteorder.h> 16 17#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) 18 19#ifndef find_next_bit 20/* 21 * Find the next set bit in a memory region. 22 */ 23unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 24 unsigned long offset) 25{ 26 const unsigned long *p = addr + BITOP_WORD(offset); 27 unsigned long result = offset & ~(BITS_PER_LONG-1); 28 unsigned long tmp; 29 30 if (offset >= size) 31 return size; 32 size -= result; 33 offset %= BITS_PER_LONG; 34 if (offset) { 35 tmp = *(p++); 36 tmp &= (~0UL << offset); 37 if (size < BITS_PER_LONG) 38 goto found_first; 39 if (tmp) 40 goto found_middle; 41 size -= BITS_PER_LONG; 42 result += BITS_PER_LONG; 43 } 44 while (size & ~(BITS_PER_LONG-1)) { 45 if ((tmp = *(p++))) 46 goto found_middle; 47 result += BITS_PER_LONG; 48 size -= BITS_PER_LONG; 49 } 50 if (!size) 51 return result; 52 tmp = *p; 53 54found_first: 55 tmp &= (~0UL >> (BITS_PER_LONG - size)); 56 if (tmp == 0UL) /* Are any bits set? */ 57 return result + size; /* Nope. */ 58found_middle: 59 return result + __ffs(tmp); 60} 61EXPORT_SYMBOL(find_next_bit); 62#endif 63 64#ifndef find_next_zero_bit 65/* 66 * This implementation of find_{first,next}_zero_bit was stolen from 67 * Linus' asm-alpha/bitops.h. 68 */ 69unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 70 unsigned long offset) 71{ 72 const unsigned long *p = addr + BITOP_WORD(offset); 73 unsigned long result = offset & ~(BITS_PER_LONG-1); 74 unsigned long tmp; 75 76 if (offset >= size) 77 return size; 78 size -= result; 79 offset %= BITS_PER_LONG; 80 if (offset) { 81 tmp = *(p++); 82 tmp |= ~0UL >> (BITS_PER_LONG - offset); 83 if (size < BITS_PER_LONG) 84 goto found_first; 85 if (~tmp) 86 goto found_middle; 87 size -= BITS_PER_LONG; 88 result += BITS_PER_LONG; 89 } 90 while (size & ~(BITS_PER_LONG-1)) { 91 if (~(tmp = *(p++))) 92 goto found_middle; 93 result += BITS_PER_LONG; 94 size -= BITS_PER_LONG; 95 } 96 if (!size) 97 return result; 98 tmp = *p; 99 100found_first: 101 tmp |= ~0UL << size; 102 if (tmp == ~0UL) /* Are any bits zero? */ 103 return result + size; /* Nope. */ 104found_middle: 105 return result + ffz(tmp); 106} 107EXPORT_SYMBOL(find_next_zero_bit); 108#endif 109 110#ifndef find_first_bit 111/* 112 * Find the first set bit in a memory region. 113 */ 114unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 115{ 116 const unsigned long *p = addr; 117 unsigned long result = 0; 118 unsigned long tmp; 119 120 while (size & ~(BITS_PER_LONG-1)) { 121 if ((tmp = *(p++))) 122 goto found; 123 result += BITS_PER_LONG; 124 size -= BITS_PER_LONG; 125 } 126 if (!size) 127 return result; 128 129 tmp = (*p) & (~0UL >> (BITS_PER_LONG - size)); 130 if (tmp == 0UL) /* Are any bits set? */ 131 return result + size; /* Nope. */ 132found: 133 return result + __ffs(tmp); 134} 135EXPORT_SYMBOL(find_first_bit); 136#endif 137 138#ifndef find_first_zero_bit 139/* 140 * Find the first cleared bit in a memory region. 141 */ 142unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 143{ 144 const unsigned long *p = addr; 145 unsigned long result = 0; 146 unsigned long tmp; 147 148 while (size & ~(BITS_PER_LONG-1)) { 149 if (~(tmp = *(p++))) 150 goto found; 151 result += BITS_PER_LONG; 152 size -= BITS_PER_LONG; 153 } 154 if (!size) 155 return result; 156 157 tmp = (*p) | (~0UL << size); 158 if (tmp == ~0UL) /* Are any bits zero? */ 159 return result + size; /* Nope. */ 160found: 161 return result + ffz(tmp); 162} 163EXPORT_SYMBOL(find_first_zero_bit); 164#endif 165 166#ifdef __BIG_ENDIAN 167 168/* include/linux/byteorder does not support "unsigned long" type */ 169static inline unsigned long ext2_swabp(const unsigned long * x) 170{ 171#if BITS_PER_LONG == 64 172 return (unsigned long) __swab64p((u64 *) x); 173#elif BITS_PER_LONG == 32 174 return (unsigned long) __swab32p((u32 *) x); 175#else 176#error BITS_PER_LONG not defined 177#endif 178} 179 180/* include/linux/byteorder doesn't support "unsigned long" type */ 181static inline unsigned long ext2_swab(const unsigned long y) 182{ 183#if BITS_PER_LONG == 64 184 return (unsigned long) __swab64((u64) y); 185#elif BITS_PER_LONG == 32 186 return (unsigned long) __swab32((u32) y); 187#else 188#error BITS_PER_LONG not defined 189#endif 190} 191 192#ifndef find_next_zero_bit_le 193unsigned long find_next_zero_bit_le(const void *addr, unsigned 194 long size, unsigned long offset) 195{ 196 const unsigned long *p = addr; 197 unsigned long result = offset & ~(BITS_PER_LONG - 1); 198 unsigned long tmp; 199 200 if (offset >= size) 201 return size; 202 p += BITOP_WORD(offset); 203 size -= result; 204 offset &= (BITS_PER_LONG - 1UL); 205 if (offset) { 206 tmp = ext2_swabp(p++); 207 tmp |= (~0UL >> (BITS_PER_LONG - offset)); 208 if (size < BITS_PER_LONG) 209 goto found_first; 210 if (~tmp) 211 goto found_middle; 212 size -= BITS_PER_LONG; 213 result += BITS_PER_LONG; 214 } 215 216 while (size & ~(BITS_PER_LONG - 1)) { 217 if (~(tmp = *(p++))) 218 goto found_middle_swap; 219 result += BITS_PER_LONG; 220 size -= BITS_PER_LONG; 221 } 222 if (!size) 223 return result; 224 tmp = ext2_swabp(p); 225found_first: 226 tmp |= ~0UL << size; 227 if (tmp == ~0UL) /* Are any bits zero? */ 228 return result + size; /* Nope. Skip ffz */ 229found_middle: 230 return result + ffz(tmp); 231 232found_middle_swap: 233 return result + ffz(ext2_swab(tmp)); 234} 235EXPORT_SYMBOL(find_next_zero_bit_le); 236#endif 237 238#ifndef find_next_bit_le 239unsigned long find_next_bit_le(const void *addr, unsigned 240 long size, unsigned long offset) 241{ 242 const unsigned long *p = addr; 243 unsigned long result = offset & ~(BITS_PER_LONG - 1); 244 unsigned long tmp; 245 246 if (offset >= size) 247 return size; 248 p += BITOP_WORD(offset); 249 size -= result; 250 offset &= (BITS_PER_LONG - 1UL); 251 if (offset) { 252 tmp = ext2_swabp(p++); 253 tmp &= (~0UL << offset); 254 if (size < BITS_PER_LONG) 255 goto found_first; 256 if (tmp) 257 goto found_middle; 258 size -= BITS_PER_LONG; 259 result += BITS_PER_LONG; 260 } 261 262 while (size & ~(BITS_PER_LONG - 1)) { 263 tmp = *(p++); 264 if (tmp) 265 goto found_middle_swap; 266 result += BITS_PER_LONG; 267 size -= BITS_PER_LONG; 268 } 269 if (!size) 270 return result; 271 tmp = ext2_swabp(p); 272found_first: 273 tmp &= (~0UL >> (BITS_PER_LONG - size)); 274 if (tmp == 0UL) /* Are any bits set? */ 275 return result + size; /* Nope. */ 276found_middle: 277 return result + __ffs(tmp); 278 279found_middle_swap: 280 return result + __ffs(ext2_swab(tmp)); 281} 282EXPORT_SYMBOL(find_next_bit_le); 283#endif 284 285#endif /* __BIG_ENDIAN */ 286