1 | /* |
2 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. |
3 | * Written by David Howells (dhowells@redhat.com) |
4 | * Copyright (C) 2008 IBM Corporation |
5 | * Written by Rusty Russell <rusty@rustcorp.com.au> |
6 | * (Inspired by David Howell's find_next_bit implementation) |
7 | * |
8 | * This program is free software; you can redistribute it and/or |
9 | * modify it under the terms of the GNU General Public License |
10 | * as published by the Free Software Foundation; either version |
11 | * 2 of the License, or (at your option) any later version. |
12 | */ |
13 | |
14 | #include "qemu/osdep.h" |
15 | #include "qemu/bitops.h" |
16 | |
17 | /* |
18 | * Find the next set bit in a memory region. |
19 | */ |
20 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
21 | unsigned long offset) |
22 | { |
23 | const unsigned long *p = addr + BIT_WORD(offset); |
24 | unsigned long result = offset & ~(BITS_PER_LONG-1); |
25 | unsigned long tmp; |
26 | |
27 | if (offset >= size) { |
28 | return size; |
29 | } |
30 | size -= result; |
31 | offset %= BITS_PER_LONG; |
32 | if (offset) { |
33 | tmp = *(p++); |
34 | tmp &= (~0UL << offset); |
35 | if (size < BITS_PER_LONG) { |
36 | goto found_first; |
37 | } |
38 | if (tmp) { |
39 | goto found_middle; |
40 | } |
41 | size -= BITS_PER_LONG; |
42 | result += BITS_PER_LONG; |
43 | } |
44 | while (size >= 4*BITS_PER_LONG) { |
45 | unsigned long d1, d2, d3; |
46 | tmp = *p; |
47 | d1 = *(p+1); |
48 | d2 = *(p+2); |
49 | d3 = *(p+3); |
50 | if (tmp) { |
51 | goto found_middle; |
52 | } |
53 | if (d1 | d2 | d3) { |
54 | break; |
55 | } |
56 | p += 4; |
57 | result += 4*BITS_PER_LONG; |
58 | size -= 4*BITS_PER_LONG; |
59 | } |
60 | while (size >= BITS_PER_LONG) { |
61 | if ((tmp = *(p++))) { |
62 | goto found_middle; |
63 | } |
64 | result += BITS_PER_LONG; |
65 | size -= BITS_PER_LONG; |
66 | } |
67 | if (!size) { |
68 | return result; |
69 | } |
70 | tmp = *p; |
71 | |
72 | found_first: |
73 | tmp &= (~0UL >> (BITS_PER_LONG - size)); |
74 | if (tmp == 0UL) { /* Are any bits set? */ |
75 | return result + size; /* Nope. */ |
76 | } |
77 | found_middle: |
78 | return result + ctzl(tmp); |
79 | } |
80 | |
81 | /* |
82 | * This implementation of find_{first,next}_zero_bit was stolen from |
83 | * Linus' asm-alpha/bitops.h. |
84 | */ |
85 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
86 | unsigned long offset) |
87 | { |
88 | const unsigned long *p = addr + BIT_WORD(offset); |
89 | unsigned long result = offset & ~(BITS_PER_LONG-1); |
90 | unsigned long tmp; |
91 | |
92 | if (offset >= size) { |
93 | return size; |
94 | } |
95 | size -= result; |
96 | offset %= BITS_PER_LONG; |
97 | if (offset) { |
98 | tmp = *(p++); |
99 | tmp |= ~0UL >> (BITS_PER_LONG - offset); |
100 | if (size < BITS_PER_LONG) { |
101 | goto found_first; |
102 | } |
103 | if (~tmp) { |
104 | goto found_middle; |
105 | } |
106 | size -= BITS_PER_LONG; |
107 | result += BITS_PER_LONG; |
108 | } |
109 | while (size & ~(BITS_PER_LONG-1)) { |
110 | if (~(tmp = *(p++))) { |
111 | goto found_middle; |
112 | } |
113 | result += BITS_PER_LONG; |
114 | size -= BITS_PER_LONG; |
115 | } |
116 | if (!size) { |
117 | return result; |
118 | } |
119 | tmp = *p; |
120 | |
121 | found_first: |
122 | tmp |= ~0UL << size; |
123 | if (tmp == ~0UL) { /* Are any bits zero? */ |
124 | return result + size; /* Nope. */ |
125 | } |
126 | found_middle: |
127 | return result + ctzl(~tmp); |
128 | } |
129 | |
130 | unsigned long find_last_bit(const unsigned long *addr, unsigned long size) |
131 | { |
132 | unsigned long words; |
133 | unsigned long tmp; |
134 | |
135 | /* Start at final word. */ |
136 | words = size / BITS_PER_LONG; |
137 | |
138 | /* Partial final word? */ |
139 | if (size & (BITS_PER_LONG-1)) { |
140 | tmp = (addr[words] & (~0UL >> (BITS_PER_LONG |
141 | - (size & (BITS_PER_LONG-1))))); |
142 | if (tmp) { |
143 | goto found; |
144 | } |
145 | } |
146 | |
147 | while (words) { |
148 | tmp = addr[--words]; |
149 | if (tmp) { |
150 | found: |
151 | return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp); |
152 | } |
153 | } |
154 | |
155 | /* Not found */ |
156 | return size; |
157 | } |
158 | |