lib/find_next_bit.c

   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
  16 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  17
  18 /**
  19  * find_next_bit - find the next set bit in a memory region
  20  * @addr: The address to base the search on
  21  * @offset: The bitnumber to start searching at
  22  * @size: The maximum size to search
  23  */
  24 unsigned 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
  63 EXPORT_SYMBOL(find_next_bit);
  64
  65 /*
  66  * This implementation of find_{first,next}_zero_bit was stolen from
  67  * Linus' asm-alpha/bitops.h.
  68  */
  69 unsigned 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
 100 found_first:
 101         tmp |= ~0UL << size;
 102         if (tmp == ~0UL)        /* Are any bits zero? */
 103                 return result + size;   /* Nope. */
 104 found_middle:
 105         return result + ffz(tmp);
 106 }
 107
 108 EXPORT_SYMBOL(find_next_zero_bit);