| 1 | |
|---|
| 2 | #include <xen/bitops.h> |
|---|
| 3 | #include <xen/lib.h> |
|---|
| 4 | |
|---|
| 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 | " xor %%eax,%%eax\n\t" /* also ensures ZF==1 if size==0 */ |
|---|
| 12 | " repe; scas"__OS"\n\t" |
|---|
| 13 | " je 1f\n\t" |
|---|
| 14 | " lea -"STR(BITS_PER_LONG/8)"(%2),%2\n\t" |
|---|
| 15 | " bsf (%2),%0\n" |
|---|
| 16 | "1: sub %%ebx,%%edi\n\t" |
|---|
| 17 | " shl $3,%%edi\n\t" |
|---|
| 18 | " add %%edi,%%eax" |
|---|
| 19 | : "=&a" (res), "=&c" (d0), "=&D" (d1) |
|---|
| 20 | : "1" ((size + BITS_PER_LONG - 1) / BITS_PER_LONG), |
|---|
| 21 | "2" (addr), "b" ((int)(long)addr) : "memory" ); |
|---|
| 22 | |
|---|
| 23 | return res; |
|---|
| 24 | } |
|---|
| 25 | |
|---|
| 26 | unsigned int __find_next_bit( |
|---|
| 27 | const unsigned long *addr, unsigned int size, unsigned int offset) |
|---|
| 28 | { |
|---|
| 29 | const unsigned long *p = addr + (offset / BITS_PER_LONG); |
|---|
| 30 | unsigned int set, bit = offset & (BITS_PER_LONG - 1); |
|---|
| 31 | |
|---|
| 32 | ASSERT(offset <= size); |
|---|
| 33 | |
|---|
| 34 | if ( bit != 0 ) |
|---|
| 35 | { |
|---|
| 36 | /* Look for a bit in the first word. */ |
|---|
| 37 | __asm__ ( "bsf %1,%%"__OP"ax" |
|---|
| 38 | : "=a" (set) : "r" (*p >> bit), "0" (BITS_PER_LONG) ); |
|---|
| 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 | |
|---|
| 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__ ( |
|---|
| 59 | " xor %%edx,%%edx\n\t" /* also ensures ZF==1 if size==0 */ |
|---|
| 60 | " repe; scas"__OS"\n\t" |
|---|
| 61 | " je 1f\n\t" |
|---|
| 62 | " lea -"STR(BITS_PER_LONG/8)"(%2),%2\n\t" |
|---|
| 63 | " xor (%2),%3\n\t" |
|---|
| 64 | " bsf %3,%0\n" |
|---|
| 65 | "1: sub %%ebx,%%edi\n\t" |
|---|
| 66 | " shl $3,%%edi\n\t" |
|---|
| 67 | " add %%edi,%%edx" |
|---|
| 68 | : "=&d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2) |
|---|
| 69 | : "1" ((size + BITS_PER_LONG - 1) / BITS_PER_LONG), |
|---|
| 70 | "2" (addr), "b" ((int)(long)addr), "3" (-1L) : "memory" ); |
|---|
| 71 | |
|---|
| 72 | return res; |
|---|
| 73 | } |
|---|
| 74 | |
|---|
| 75 | unsigned int __find_next_zero_bit( |
|---|
| 76 | const unsigned long *addr, unsigned int size, unsigned int offset) |
|---|
| 77 | { |
|---|
| 78 | const unsigned long *p = addr + (offset / BITS_PER_LONG); |
|---|
| 79 | unsigned int set, bit = offset & (BITS_PER_LONG - 1); |
|---|
| 80 | |
|---|
| 81 | ASSERT(offset <= size); |
|---|
| 82 | |
|---|
| 83 | if ( bit != 0 ) |
|---|
| 84 | { |
|---|
| 85 | /* Look for zero in the first word. */ |
|---|
| 86 | __asm__ ( "bsf %1,%%"__OP"ax" : "=a" (set) : "r" (~(*p >> bit)) ); |
|---|
| 87 | if ( set < (BITS_PER_LONG - bit) ) |
|---|
| 88 | return (offset + set); |
|---|
| 89 | offset += BITS_PER_LONG - bit; |
|---|
| 90 | p++; |
|---|
| 91 | } |
|---|
| 92 | |
|---|
| 93 | if ( offset >= size ) |
|---|
| 94 | return size; |
|---|
| 95 | |
|---|
| 96 | /* Search remaining full words for a zero. */ |
|---|
| 97 | set = __find_first_zero_bit(p, size - offset); |
|---|
| 98 | return (offset + set); |
|---|
| 99 | } |
|---|
