arch/s390/lib/find.c

   1 /*
   2  * MSB0 numbered special bitops handling.
   3  *
   4  * The bits are numbered:
   5  *   |0..............63|64............127|128...........191|192...........255|
   6  *
   7  * The reason for this bit numbering is the fact that the hardware sets bits
   8  * in a bitmap starting at bit 0 (MSB) and we don't want to scan the bitmap
   9  * from the 'wrong end'.
  10  */
  11
  12 #include <linux/compiler.h>
  13 #include <linux/bitops.h>
  14 #include <linux/export.h>
  15
  16 unsigned long find_first_bit_inv(const unsigned long *addr, unsigned long size)
  17 {
  18         const unsigned long *p = addr;
  19         unsigned long result = 0;
  20         unsigned long tmp;
  21
  22         while (size & ~(BITS_PER_LONG - 1)) {
  23                 if ((tmp = *(p++)))
  24                         goto found;
  25                 result += BITS_PER_LONG;
  26                 size -= BITS_PER_LONG;
  27         }
  28         if (!size)
  29                 return result;
  30         tmp = (*p) & (~0UL << (BITS_PER_LONG - size));
  31         if (!tmp)               /* Are any bits set? */
  32                 return result + size;   /* Nope. */
  33 found:
  34         return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
  35 }
  36 EXPORT_SYMBOL(find_first_bit_inv);
  37
  38 unsigned long find_next_bit_inv(const unsigned long *addr, unsigned long size,
  39                                 unsigned long offset)
  40 {
  41         const unsigned long *p = addr + (offset / BITS_PER_LONG);
  42         unsigned long result = offset & ~(BITS_PER_LONG - 1);
  43         unsigned long tmp;
  44
  45         if (offset >= size)
  46                 return size;
  47         size -= result;
  48         offset %= BITS_PER_LONG;
  49         if (offset) {
  50                 tmp = *(p++);
  51                 tmp &= (~0UL >> offset);
  52                 if (size < BITS_PER_LONG)
  53                         goto found_first;
  54                 if (tmp)
  55                         goto found_middle;
  56                 size -= BITS_PER_LONG;
  57                 result += BITS_PER_LONG;
  58         }
  59         while (size & ~(BITS_PER_LONG-1)) {
  60                 if ((tmp = *(p++)))
  61                         goto found_middle;
  62                 result += BITS_PER_LONG;
  63                 size -= BITS_PER_LONG;
  64         }
  65         if (!size)
  66                 return result;
  67         tmp = *p;
  68 found_first:
  69         tmp &= (~0UL << (BITS_PER_LONG - size));
  70         if (!tmp)               /* Are any bits set? */
  71                 return result + size;   /* Nope. */
  72 found_middle:
  73         return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
  74 }
  75 EXPORT_SYMBOL(find_next_bit_inv);