arch/ppc64/kernel/bitops.c

   1 /*
   2  * These are too big to be inlined.
   3  */
   4
   5 #include <linux/kernel.h>
   6 #include <linux/module.h>
   7 #include <linux/bitops.h>
   8 #include <asm/byteorder.h>
   9
  10 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  11                                  unsigned long offset)
  12 {
  13         const unsigned long *p = addr + (offset >> 6);
  14         unsigned long result = offset & ~63UL;
  15         unsigned long tmp;
  16
  17         if (offset >= size)
  18                 return size;
  19         size -= result;
  20         offset &= 63UL;
  21         if (offset) {
  22                 tmp = *(p++);
  23                 tmp |= ~0UL >> (64 - offset);
  24                 if (size < 64)
  25                         goto found_first;
  26                 if (~tmp)
  27                         goto found_middle;
  28                 size -= 64;
  29                 result += 64;
  30         }
  31         while (size & ~63UL) {
  32                 if (~(tmp = *(p++)))
  33                         goto found_middle;
  34                 result += 64;
  35                 size -= 64;
  36         }
  37         if (!size)
  38                 return result;
  39         tmp = *p;
  40
  41 found_first:
  42         tmp |= ~0UL << size;
  43         if (tmp == ~0UL)        /* Are any bits zero? */
  44                 return result + size;   /* Nope. */
  45 found_middle:
  46         return result + ffz(tmp);
  47 }
  48
  49 EXPORT_SYMBOL(find_next_zero_bit);
  50
  51 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  52                             unsigned long offset)
  53 {
  54         const 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 << 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 >> (64 - size));
  84         if (tmp == 0UL)         /* Are any bits set? */
  85                 return result + size;   /* Nope. */
  86 found_middle:
  87         return result + __ffs(tmp);
  88 }
  89
  90 EXPORT_SYMBOL(find_next_bit);
  91
  92 static inline unsigned int ext2_ilog2(unsigned int x)
  93 {
  94         int lz;
  95
  96         asm("cntlzw %0,%1": "=r"(lz):"r"(x));
  97         return 31 - lz;
  98 }
  99
 100 static inline unsigned int ext2_ffz(unsigned int x)
 101 {
 102         u32 rc;
 103         if ((x = ~x) == 0)
 104                 return 32;
 105         rc = ext2_ilog2(x & -x);
 106         return rc;
 107 }
 108
 109 unsigned long find_next_zero_le_bit(const unsigned long *addr, unsigned long size,
 110                                     unsigned long offset)
 111 {
 112         const unsigned int *p = ((const unsigned int *)addr) + (offset >> 5);
 113         unsigned int result = offset & ~31;
 114         unsigned int tmp;
 115
 116         if (offset >= size)
 117                 return size;
 118         size -= result;
 119         offset &= 31;
 120         if (offset) {
 121                 tmp = cpu_to_le32p(p++);
 122                 tmp |= ~0U >> (32 - offset);    /* bug or feature ? */
 123                 if (size < 32)
 124                         goto found_first;
 125                 if (tmp != ~0)
 126                         goto found_middle;
 127                 size -= 32;
 128                 result += 32;
 129         }
 130         while (size >= 32) {
 131                 if ((tmp = cpu_to_le32p(p++)) != ~0)
 132                         goto found_middle;
 133                 result += 32;
 134                 size -= 32;
 135         }
 136         if (!size)
 137                 return result;
 138         tmp = cpu_to_le32p(p);
 139 found_first:
 140         tmp |= ~0 << size;
 141         if (tmp == ~0)          /* Are any bits zero? */
 142                 return result + size;   /* Nope. */
 143 found_middle:
 144         return result + ext2_ffz(tmp);
 145 }
 146
 147 EXPORT_SYMBOL(find_next_zero_le_bit);