aboutsummaryrefslogtreecommitdiffstats
path: root/arch/x86_64/lib/bitops.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /arch/x86_64/lib/bitops.c
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'arch/x86_64/lib/bitops.c')
-rw-r--r--arch/x86_64/lib/bitops.c141
1 files changed, 141 insertions, 0 deletions
diff --git a/arch/x86_64/lib/bitops.c b/arch/x86_64/lib/bitops.c
new file mode 100644
index 000000000000..a29fb75b33ac
--- /dev/null
+++ b/arch/x86_64/lib/bitops.c
@@ -0,0 +1,141 @@
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 */
16inline 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 */
44long 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
71static 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 */
100long 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 */
111long 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
138EXPORT_SYMBOL(find_next_bit);
139EXPORT_SYMBOL(find_first_bit);
140EXPORT_SYMBOL(find_first_zero_bit);
141EXPORT_SYMBOL(find_next_zero_bit);