arch/sparc64/lib/find_bit.c

   1 #include <asm/bitops.h>
   2
   3 /**
   4  * find_next_bit - find the next set bit in a memory region
   5  * @addr: The address to base the search on
   6  * @offset: The bitnumber to start searching at
   7  * @size: The maximum size to search
   8  */
   9 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  10                                 unsigned long offset)
  11 {
  12         const unsigned long *p = addr + (offset >> 6);
  13         unsigned long result = offset & ~63UL;
  14         unsigned long tmp;
  15
  16         if (offset >= size)
  17                 return size;
  18         size -= result;
  19         offset &= 63UL;
  20         if (offset) {
  21                 tmp = *(p++);
  22                 tmp &= (~0UL << offset);
  23                 if (size < 64)
  24                         goto found_first;
  25                 if (tmp)
  26                         goto found_middle;
  27                 size -= 64;
  28                 result += 64;
  29         }
  30         while (size & ~63UL) {
  31                 if ((tmp = *(p++)))
  32                         goto found_middle;
  33                 result += 64;
  34                 size -= 64;
  35         }
  36         if (!size)
  37                 return result;
  38         tmp = *p;
  39
  40 found_first:
  41         tmp &= (~0UL >> (64 - size));
  42         if (tmp == 0UL)        /* Are any bits set? */
  43                 return result + size; /* Nope. */
  44 found_middle:
  45         return result + __ffs(tmp);
  46 }
  47
  48 /* find_next_zero_bit() finds the first zero bit in a bit string of length
  49  * 'size' bits, starting the search at bit 'offset'. This is largely based
  50  * on Linus's ALPHA routines, which are pretty portable BTW.
  51  */
  52
  53 unsigned long find_next_zero_bit(unsigned long *addr, unsigned long size, unsigned long offset)
  54 {
  55         unsigned long *p = addr + (offset >> 6);
  56         unsigned long result = offset & ~63UL;
  57         unsigned long tmp;
  58
  59         if (offset >= size)
  60                 return size;
  61         size -= result;
  62         offset &= 63UL;
  63         if (offset) {
  64                 tmp = *(p++);
  65                 tmp |= ~0UL >> (64-offset);
  66                 if (size < 64)
  67                         goto found_first;
  68                 if (~tmp)
  69                         goto found_middle;
  70                 size -= 64;
  71                 result += 64;
  72         }
  73         while (size & ~63UL) {
  74                 if (~(tmp = *(p++)))
  75                         goto found_middle;
  76                 result += 64;
  77                 size -= 64;
  78         }
  79         if (!size)
  80                 return result;
  81         tmp = *p;
  82
  83 found_first:
  84         tmp |= ~0UL << size;
  85         if (tmp == ~0UL)        /* Are any bits zero? */
  86                 return result + size; /* Nope. */
  87 found_middle:
  88         return result + ffz(tmp);
  89 }
  90
  91 unsigned long find_next_zero_le_bit(unsigned long *addr, unsigned long size, unsigned long offset)
  92 {
  93         unsigned long *p = addr + (offset >> 6);
  94         unsigned long result = offset & ~63UL;
  95         unsigned long tmp;
  96
  97         if (offset >= size)
  98                 return size;
  99         size -= result;
 100         offset &= 63UL;
 101         if(offset) {
 102                 tmp = __swab64p(p++);
 103                 tmp |= (~0UL >> (64-offset));
 104                 if(size < 64)
 105                         goto found_first;
 106                 if(~tmp)
 107                         goto found_middle;
 108                 size -= 64;
 109                 result += 64;
 110         }
 111         while(size & ~63) {
 112                 if(~(tmp = __swab64p(p++)))
 113                         goto found_middle;
 114                 result += 64;
 115                 size -= 64;
 116         }
 117         if(!size)
 118                 return result;
 119         tmp = __swab64p(p);
 120 found_first:
 121         tmp |= (~0UL << size);
 122         if (tmp == ~0UL)        /* Are any bits zero? */
 123                 return result + size; /* Nope. */
 124 found_middle:
 125         return result + ffz(tmp);
 126 }