1
2 #include <xen/bitops.h>
3 #include <xen/lib.h>
4
__find_first_bit(const unsigned long * addr,unsigned int size)5 unsigned int __find_first_bit(
6 const unsigned long *addr, unsigned int size)
7 {
8 unsigned long d0, d1, res;
9
10 asm volatile (
11 "1: xor %%eax,%%eax\n\t" /* also ensures ZF==1 if size==0 */
12 " repe; scas"__OS"\n\t"
13 " je 2f\n\t"
14 " bsf -"STR(BITS_PER_LONG/8)"(%2),%0\n\t"
15 " jz 1b\n\t"
16 " lea -"STR(BITS_PER_LONG/8)"(%2),%2\n\t"
17 "2: sub %%ebx,%%edi\n\t"
18 " shl $3,%%edi\n\t"
19 " add %%edi,%%eax"
20 : "=&a" (res), "=&c" (d0), "=&D" (d1)
21 : "1" (BITS_TO_LONGS(size)), "2" (addr), "b" ((int)(long)addr)
22 : "memory" );
23
24 return res;
25 }
26
__find_next_bit(const unsigned long * addr,unsigned int size,unsigned int offset)27 unsigned int __find_next_bit(
28 const unsigned long *addr, unsigned int size, unsigned int offset)
29 {
30 const unsigned long *p = addr + (offset / BITS_PER_LONG);
31 unsigned int set, bit = offset & (BITS_PER_LONG - 1);
32
33 ASSERT(offset <= size);
34
35 if ( bit != 0 )
36 {
37 /* Look for a bit in the first word. */
38 set = __scanbit(*p >> bit, BITS_PER_LONG - bit);
39 if ( set < (BITS_PER_LONG - bit) )
40 return (offset + set);
41 offset += BITS_PER_LONG - bit;
42 p++;
43 }
44
45 if ( offset >= size )
46 return size;
47
48 /* Search remaining full words for a bit. */
49 set = __find_first_bit(p, size - offset);
50 return (offset + set);
51 }
52
__find_first_zero_bit(const unsigned long * addr,unsigned int size)53 unsigned int __find_first_zero_bit(
54 const unsigned long *addr, unsigned int size)
55 {
56 unsigned long d0, d1, d2, res;
57
58 asm volatile (
59 "1: xor %%eax,%%eax ; not %3\n\t" /* rAX == ~0ul */
60 " xor %%edx,%%edx\n\t" /* also ensures ZF==1 if size==0 */
61 " repe; scas"__OS"\n\t"
62 " je 2f\n\t"
63 " xor -"STR(BITS_PER_LONG/8)"(%2),%3\n\t"
64 " jz 1b\n\t"
65 " rep; bsf %3,%0\n\t"
66 " lea -"STR(BITS_PER_LONG/8)"(%2),%2\n\t"
67 "2: sub %%ebx,%%edi\n\t"
68 " shl $3,%%edi\n\t"
69 " add %%edi,%%edx"
70 : "=&d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
71 : "1" (BITS_TO_LONGS(size)), "2" (addr), "b" ((int)(long)addr)
72 : "memory" );
73
74 return res;
75 }
76
__find_next_zero_bit(const unsigned long * addr,unsigned int size,unsigned int offset)77 unsigned int __find_next_zero_bit(
78 const unsigned long *addr, unsigned int size, unsigned int offset)
79 {
80 const unsigned long *p = addr + (offset / BITS_PER_LONG);
81 unsigned int set, bit = offset & (BITS_PER_LONG - 1);
82
83 ASSERT(offset <= size);
84
85 if ( bit != 0 )
86 {
87 /* Look for zero in the first word. */
88 set = __scanbit(~(*p >> bit), BITS_PER_LONG - bit);
89 if ( set < (BITS_PER_LONG - bit) )
90 return (offset + set);
91 offset += BITS_PER_LONG - bit;
92 p++;
93 }
94
95 if ( offset >= size )
96 return size;
97
98 /* Search remaining full words for a zero. */
99 set = __find_first_zero_bit(p, size - offset);
100 return (offset + set);
101 }
102