LXR linux/lib/find_next

   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