LXR linux/arch/x86/lib/bitops

   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
   8static inline long
   9__find_first_zero_bit(const unsigned long * addr, unsigned long size)
  10{
  11        long d0, d1, d2;
  12        long res;
  13
  14        /*
  15         * We must test the size in words, not in bits, because
  16         * otherwise incoming sizes in the range -63..-1 will not run
  17         * any scasq instructions, and then the flags used by the je
  18         * instruction will have whatever random value was in place
  19         * before.  Nobody should call us like that, but
  20         * find_next_zero_bit() does when offset and size are at the
  21         * same word and it fails to find a zero itself.
  22         */
  23        size += 63;
  24        size >>= 6;
  25        if (!size)
  26                return 0;
  27        asm volatile(
  28                "  repe; scasq\n"
  29                "  je 1f\n"
  30                "  xorq -8(%%rdi),%%rax\n"
  31                "  subq $8,%%rdi\n"
  32                "  bsfq %%rax,%%rdx\n"
  33                "1:  subq %[addr],%%rdi\n"
  34                "  shlq $3,%%rdi\n"
  35                "  addq %%rdi,%%rdx"
  36                :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
  37                :"0" (0ULL), "1" (size), "2" (addr), "3" (-1ULL),
  38                 [addr] "S" (addr) : "memory");
  39        /*
  40         * Any register would do for [addr] above, but GCC tends to
  41         * prefer rbx over rsi, even though rsi is readily available
  42         * and doesn't have to be saved.
  43         */
  44        return res;
  45}
  46
  47/**
  48 * find_first_zero_bit - find the first zero bit in a memory region
  49 * @addr: The address to start the search at
  50 * @size: The maximum size to search
  51 *
  52 * Returns the bit-number of the first zero bit, not the number of the byte
  53 * containing a bit.
  54 */
  55long find_first_zero_bit(const unsigned long * addr, unsigned long size)
  56{
  57        return __find_first_zero_bit (addr, size);
  58}
  59
  60/**
  61 * find_next_zero_bit - find the next zero bit in a memory region
  62 * @addr: The address to base the search on
  63 * @offset: The bitnumber to start searching at
  64 * @size: The maximum size to search
  65 */
  66long find_next_zero_bit (const unsigned long * addr, long size, long offset)
  67{
  68        const unsigned long * p = addr + (offset >> 6);
  69        unsigned long set = 0;
  70        unsigned long res, bit = offset&63;
  71
  72        if (bit) {
  73                /*
  74                 * Look for zero in first word
  75                 */
  76                asm("bsfq %1,%0\n\t"
  77                    "cmoveq %2,%0"
  78                    : "=r" (set)
  79                    : "r" (~(*p >> bit)), "r"(64L));
  80                if (set < (64 - bit))
  81                        return set + offset;
  82                set = 64 - bit;
  83                p++;
  84        }
  85        /*
  86         * No zero yet, search remaining full words for a zero
  87         */
  88        res = __find_first_zero_bit (p, size - 64 * (p - addr));
  89
  90        return (offset + set + res);
  91}
  92
  93static inline long
  94__find_first_bit(const unsigned long * addr, unsigned long size)
  95{
  96        long d0, d1;
  97        long res;
  98
  99        /*
 100         * We must test the size in words, not in bits, because
 101         * otherwise incoming sizes in the range -63..-1 will not run
 102         * any scasq instructions, and then the flags used by the jz
 103         * instruction will have whatever random value was in place
 104         * before.  Nobody should call us like that, but
 105         * find_next_bit() does when offset and size are at the same
 106         * word and it fails to find a one itself.
 107         */
 108        size += 63;
 109        size >>= 6;
 110        if (!size)
 111                return 0;
 112        asm volatile(
 113                "   repe; scasq\n"
 114                "   jz 1f\n"
 115                "   subq $8,%%rdi\n"
 116                "   bsfq (%%rdi),%%rax\n"
 117                "1: subq %[addr],%%rdi\n"
 118                "   shlq $3,%%rdi\n"
 119                "   addq %%rdi,%%rax"
 120                :"=a" (res), "=&c" (d0), "=&D" (d1)
 121                :"0" (0ULL), "1" (size), "2" (addr),
 122                 [addr] "r" (addr) : "memory");
 123        return res;
 124}
 125
 126/**
 127 * find_first_bit - find the first set bit in a memory region
 128 * @addr: The address to start the search at
 129 * @size: The maximum size to search
 130 *
 131 * Returns the bit-number of the first set bit, not the number of the byte
 132 * containing a bit.
 133 */
 134long find_first_bit(const unsigned long * addr, unsigned long size)
 135{
 136        return __find_first_bit(addr,size);
 137}
 138
 139/**
 140 * find_next_bit - find the first set bit in a memory region
 141 * @addr: The address to base the search on
 142 * @offset: The bitnumber to start searching at
 143 * @size: The maximum size to search
 144 */
 145long find_next_bit(const unsigned long * addr, long size, long offset)
 146{
 147        const unsigned long * p = addr + (offset >> 6);
 148        unsigned long set = 0, bit = offset & 63, res;
 149
 150        if (bit) {
 151                /*
 152                 * Look for nonzero in the first 64 bits:
 153                 */
 154                asm("bsfq %1,%0\n\t"
 155                    "cmoveq %2,%0\n\t"
 156                    : "=r" (set)
 157                    : "r" (*p >> bit), "r" (64L));
 158                if (set < (64 - bit))
 159                        return set + offset;
 160                set = 64 - bit;
 161                p++;
 162        }
 163        /*
 164         * No set bit yet, search remaining full words for a bit
 165         */
 166        res = __find_first_bit (p, size - 64 * (p - addr));
 167        return (offset + set + res);
 168}
 169
 170#include <linux/module.h>
 171
 172EXPORT_SYMBOL(find_next_bit);
 173EXPORT_SYMBOL(find_first_bit);
 174EXPORT_SYMBOL(find_first_zero_bit);
 175EXPORT_SYMBOL(find_next_zero_bit);
 176