arch/x86_64/lib/bitops.c

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