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