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 <common.h>
  13 #include <errno.h>
  14 #include <string.h>
  15 #include <init.h>
  16 #include <linux/bitops.h>
  17 #include <asm/types.h>
  18 #include <asm/byteorder.h>
  19
  20 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  21
  22 #ifdef CONFIG_GENERIC_FIND_NEXT_BIT
  23 /*
  24  * Find the next set bit in a memory region.
  25  */
  26 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  27                             unsigned long offset)
  28 {
  29         const unsigned long *p = addr + BITOP_WORD(offset);
  30         unsigned long result = offset & ~(BITS_PER_LONG-1);
  31         unsigned long tmp;
  32
  33         if (offset >= size)
  34                 return size;
  35         size -= result;
  36         offset %= BITS_PER_LONG;
  37         if (offset) {
  38                 tmp = *(p++);
  39                 tmp &= (~0UL << offset);
  40                 if (size < BITS_PER_LONG)
  41                         goto found_first;
  42                 if (tmp)
  43                         goto found_middle;
  44                 size -= BITS_PER_LONG;
  45                 result += BITS_PER_LONG;
  46         }
  47         while (size & ~(BITS_PER_LONG-1)) {
  48                 if ((tmp = *(p++)))
  49                         goto found_middle;
  50                 result += BITS_PER_LONG;
  51                 size -= BITS_PER_LONG;
  52         }
  53         if (!size)
  54                 return result;
  55         tmp = *p;
  56
  57 found_first:
  58         tmp &= (~0UL >> (BITS_PER_LONG - size));
  59         if (tmp == 0UL)         /* Are any bits set? */
  60                 return result + size;   /* Nope. */
  61 found_middle:
  62         return result + __ffs(tmp);
  63 }
  64 EXPORT_SYMBOL(find_next_bit);
  65
  66 /*
  67  * This implementation of find_{first,next}_zero_bit was stolen from
  68  * Linus' asm-alpha/bitops.h.
  69  */
  70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  71                                  unsigned long offset)
  72 {
  73         const unsigned long *p = addr + BITOP_WORD(offset);
  74         unsigned long result = offset & ~(BITS_PER_LONG-1);
  75         unsigned long tmp;
  76
  77         if (offset >= size)
  78                 return size;
  79         size -= result;
  80         offset %= BITS_PER_LONG;
  81         if (offset) {
  82                 tmp = *(p++);
  83                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
  84                 if (size < BITS_PER_LONG)
  85                         goto found_first;
  86                 if (~tmp)
  87                         goto found_middle;
  88                 size -= BITS_PER_LONG;
  89                 result += BITS_PER_LONG;
  90         }
  91         while (size & ~(BITS_PER_LONG-1)) {
  92                 if (~(tmp = *(p++)))
  93                         goto found_middle;
  94                 result += BITS_PER_LONG;
  95                 size -= BITS_PER_LONG;
  96         }
  97         if (!size)
  98                 return result;
  99         tmp = *p;
 100
 101 found_first:
 102         tmp |= ~0UL << size;
 103         if (tmp == ~0UL)        /* Are any bits zero? */
 104                 return result + size;   /* Nope. */
 105 found_middle:
 106         return result + ffz(tmp);
 107 }
 108  EXPORT_SYMBOL(find_next_zero_bit);
 109 #endif /* CONFIG_GENERIC_FIND_NEXT_BIT */