arch/x86_64/lib/bitops.c

   1 #include <linux/bitops.h>
   2
   3 #undef find_first_zero_bit
   4 #undef find_next_zero_bit
   5 #undef find_first_bit
   6 #undef find_next_bit
   7
   8 /**
   9  * find_first_zero_bit - find the first zero bit in a memory region
  10  * @addr: The address to start the search at
  11  * @size: The maximum size to search
  12  *
  13  * Returns the bit-number of the first zero bit, not the number of the byte
  14  * containing a bit.
  15  */
  16 inline long find_first_zero_bit(const unsigned long * addr, unsigned long size)
  17 {
  18         long d0, d1, d2;
  19         long res;
  20
  21         if (!size)
  22                 return 0;
  23         asm volatile(
  24                 "  repe; scasq\n"
  25                 "  je 1f\n"
  26                 "  xorq -8(%%rdi),%%rax\n"
  27                 "  subq $8,%%rdi\n"
  28                 "  bsfq %%rax,%%rdx\n"
  29                 "1:  subq %[addr],%%rdi\n"
  30                 "  shlq $3,%%rdi\n"
  31                 "  addq %%rdi,%%rdx"
  32                 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
  33                 :"0" (0ULL), "1" ((size + 63) >> 6), "2" (addr), "3" (-1ULL),
  34                  [addr] "r" (addr) : "memory");
  35         return res;
  36 }
  37
  38 /**
  39  * find_next_zero_bit - find the first zero bit in a memory region
  40  * @addr: The address to base the search on
  41  * @offset: The bitnumber to start searching at
  42  * @size: The maximum size to search
  43  */
  44 long find_next_zero_bit (const unsigned long * addr, long size, long offset)
  45 {
  46         unsigned long * p = ((unsigned long *) addr) + (offset >> 6);
  47         unsigned long set = 0;
  48         unsigned long res, bit = offset&63;
  49
  50         if (bit) {
  51                 /*
  52                  * Look for zero in first word
  53                  */
  54                 asm("bsfq %1,%0\n\t"
  55                     "cmoveq %2,%0"
  56                     : "=r" (set)
  57                     : "r" (~(*p >> bit)), "r"(64L));
  58                 if (set < (64 - bit))
  59                         return set + offset;
  60                 set = 64 - bit;
  61                 p++;
  62         }
  63         /*
  64          * No zero yet, search remaining full words for a zero
  65          */
  66         res = find_first_zero_bit ((const unsigned long *)p,
  67                                    size - 64 * (p - (unsigned long *) addr));
  68         return (offset + set + res);
  69 }
  70
  71 static inline long
  72 __find_first_bit(const unsigned long * addr, unsigned long size)
  73 {
  74         long d0, d1;
  75         long res;
  76
  77         asm volatile(
  78                 "   repe; scasq\n"
  79                 "   jz 1f\n"
  80                 "   subq $8,%%rdi\n"
  81                 "   bsfq (%%rdi),%%rax\n"
  82                 "1: subq %[addr],%%rdi\n"
  83                 "   shlq $3,%%rdi\n"
  84                 "   addq %%rdi,%%rax"
  85                 :"=a" (res), "=&c" (d0), "=&D" (d1)
  86                 :"0" (0ULL),
  87                  "1" ((size + 63) >> 6), "2" (addr),
  88                  [addr] "r" (addr) : "memory");
  89         return res;
  90 }
  91
  92 /**
  93  * find_first_bit - find the first set bit in a memory region
  94  * @addr: The address to start the search at
  95  * @size: The maximum size to search
  96  *
  97  * Returns the bit-number of the first set bit, not the number of the byte
  98  * containing a bit.
  99  */
 100 long find_first_bit(const unsigned long * addr, unsigned long size)
 101 {
 102         return __find_first_bit(addr,size);
 103 }
 104
 105 /**
 106  * find_next_bit - find the first set bit in a memory region
 107  * @addr: The address to base the search on
 108  * @offset: The bitnumber to start searching at
 109  * @size: The maximum size to search
 110  */
 111 long find_next_bit(const unsigned long * addr, long size, long offset)
 112 {
 113         const unsigned long * p = addr + (offset >> 6);
 114         unsigned long set = 0, bit = offset & 63, res;
 115
 116         if (bit) {
 117                 /*
 118                  * Look for nonzero in the first 64 bits:
 119                  */
 120                 asm("bsfq %1,%0\n\t"
 121                     "cmoveq %2,%0\n\t"
 122                     : "=r" (set)
 123                     : "r" (*p >> bit), "r" (64L));
 124                 if (set < (64 - bit))
 125                         return set + offset;
 126                 set = 64 - bit;
 127                 p++;
 128         }
 129         /*
 130          * No set bit yet, search remaining full words for a bit
 131          */
 132         res = __find_first_bit (p, size - 64 * (p - addr));
 133         return (offset + set + res);
 134 }
 135
 136 #include <linux/module.h>
 137
 138 EXPORT_SYMBOL(find_next_bit);
 139 EXPORT_SYMBOL(find_first_bit);
 140 EXPORT_SYMBOL(find_first_zero_bit);
 141 EXPORT_SYMBOL(find_next_zero_bit);