Merge master.kernel.org:/home/rmk/linux-2.6-serial
[linux-2.6] / 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);