git.oblomov.eu Git - linux-2.6/blob - arch/sparc64/lib/find_bit.c

   1 #include <linux/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(const unsigned long *addr,
  54                         unsigned long size, unsigned long offset)
  55 {
  56         const unsigned long *p = addr + (offset >> 6);
  57         unsigned long result = offset & ~63UL;
  58         unsigned long tmp;
  59
  60         if (offset >= size)
  61                 return size;
  62         size -= result;
  63         offset &= 63UL;
  64         if (offset) {
  65                 tmp = *(p++);
  66                 tmp |= ~0UL >> (64-offset);
  67                 if (size < 64)
  68                         goto found_first;
  69                 if (~tmp)
  70                         goto found_middle;
  71                 size -= 64;
  72                 result += 64;
  73         }
  74         while (size & ~63UL) {
  75                 if (~(tmp = *(p++)))
  76                         goto found_middle;
  77                 result += 64;
  78                 size -= 64;
  79         }
  80         if (!size)
  81                 return result;
  82         tmp = *p;
  83
  84 found_first:
  85         tmp |= ~0UL << size;
  86         if (tmp == ~0UL)        /* Are any bits zero? */
  87                 return result + size; /* Nope. */
  88 found_middle:
  89         return result + ffz(tmp);
  90 }
  91
  92 unsigned long find_next_zero_le_bit(unsigned long *addr, unsigned long size, unsigned long offset)
  93 {
  94         unsigned long *p = addr + (offset >> 6);
  95         unsigned long result = offset & ~63UL;
  96         unsigned long tmp;
  97
  98         if (offset >= size)
  99                 return size;
 100         size -= result;
 101         offset &= 63UL;
 102         if(offset) {
 103                 tmp = __swab64p(p++);
 104                 tmp |= (~0UL >> (64-offset));
 105                 if(size < 64)
 106                         goto found_first;
 107                 if(~tmp)
 108                         goto found_middle;
 109                 size -= 64;
 110                 result += 64;
 111         }
 112         while(size & ~63) {
 113                 if(~(tmp = __swab64p(p++)))
 114                         goto found_middle;
 115                 result += 64;
 116                 size -= 64;
 117         }
 118         if(!size)
 119                 return result;
 120         tmp = __swab64p(p);
 121 found_first:
 122         tmp |= (~0UL << size);
 123         if (tmp == ~0UL)        /* Are any bits zero? */
 124                 return result + size; /* Nope. */
 125 found_middle:
 126         return result + ffz(tmp);
 127 }