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