root / bitmap.c @ 1de7afc9
History | View | Annotate | Download (6.3 kB)
1 | e0e53b2f | Corentin Chary | /*
|
---|---|---|---|
2 | e0e53b2f | Corentin Chary | * Bitmap Module
|
3 | e0e53b2f | Corentin Chary | *
|
4 | e0e53b2f | Corentin Chary | * Stolen from linux/src/lib/bitmap.c
|
5 | e0e53b2f | Corentin Chary | *
|
6 | e0e53b2f | Corentin Chary | * Copyright (C) 2010 Corentin Chary
|
7 | e0e53b2f | Corentin Chary | *
|
8 | e0e53b2f | Corentin Chary | * This source code is licensed under the GNU General Public License,
|
9 | e0e53b2f | Corentin Chary | * Version 2.
|
10 | e0e53b2f | Corentin Chary | */
|
11 | e0e53b2f | Corentin Chary | |
12 | 1de7afc9 | Paolo Bonzini | #include "qemu/bitops.h" |
13 | 1de7afc9 | Paolo Bonzini | #include "qemu/bitmap.h" |
14 | e0e53b2f | Corentin Chary | |
15 | e0e53b2f | Corentin Chary | /*
|
16 | e0e53b2f | Corentin Chary | * bitmaps provide an array of bits, implemented using an an
|
17 | e0e53b2f | Corentin Chary | * array of unsigned longs. The number of valid bits in a
|
18 | e0e53b2f | Corentin Chary | * given bitmap does _not_ need to be an exact multiple of
|
19 | e0e53b2f | Corentin Chary | * BITS_PER_LONG.
|
20 | e0e53b2f | Corentin Chary | *
|
21 | e0e53b2f | Corentin Chary | * The possible unused bits in the last, partially used word
|
22 | e0e53b2f | Corentin Chary | * of a bitmap are 'don't care'. The implementation makes
|
23 | e0e53b2f | Corentin Chary | * no particular effort to keep them zero. It ensures that
|
24 | e0e53b2f | Corentin Chary | * their value will not affect the results of any operation.
|
25 | e0e53b2f | Corentin Chary | * The bitmap operations that return Boolean (bitmap_empty,
|
26 | e0e53b2f | Corentin Chary | * for example) or scalar (bitmap_weight, for example) results
|
27 | e0e53b2f | Corentin Chary | * carefully filter out these unused bits from impacting their
|
28 | e0e53b2f | Corentin Chary | * results.
|
29 | e0e53b2f | Corentin Chary | *
|
30 | e0e53b2f | Corentin Chary | * These operations actually hold to a slightly stronger rule:
|
31 | e0e53b2f | Corentin Chary | * if you don't input any bitmaps to these ops that have some
|
32 | e0e53b2f | Corentin Chary | * unused bits set, then they won't output any set unused bits
|
33 | e0e53b2f | Corentin Chary | * in output bitmaps.
|
34 | e0e53b2f | Corentin Chary | *
|
35 | e0e53b2f | Corentin Chary | * The byte ordering of bitmaps is more natural on little
|
36 | e0e53b2f | Corentin Chary | * endian architectures.
|
37 | e0e53b2f | Corentin Chary | */
|
38 | e0e53b2f | Corentin Chary | |
39 | e0e53b2f | Corentin Chary | int slow_bitmap_empty(const unsigned long *bitmap, int bits) |
40 | e0e53b2f | Corentin Chary | { |
41 | e0e53b2f | Corentin Chary | int k, lim = bits/BITS_PER_LONG;
|
42 | e0e53b2f | Corentin Chary | |
43 | e0e53b2f | Corentin Chary | for (k = 0; k < lim; ++k) { |
44 | e0e53b2f | Corentin Chary | if (bitmap[k]) {
|
45 | e0e53b2f | Corentin Chary | return 0; |
46 | e0e53b2f | Corentin Chary | } |
47 | e0e53b2f | Corentin Chary | } |
48 | e0e53b2f | Corentin Chary | if (bits % BITS_PER_LONG) {
|
49 | e0e53b2f | Corentin Chary | if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
|
50 | e0e53b2f | Corentin Chary | return 0; |
51 | e0e53b2f | Corentin Chary | } |
52 | e0e53b2f | Corentin Chary | } |
53 | e0e53b2f | Corentin Chary | |
54 | e0e53b2f | Corentin Chary | return 1; |
55 | e0e53b2f | Corentin Chary | } |
56 | e0e53b2f | Corentin Chary | |
57 | e0e53b2f | Corentin Chary | int slow_bitmap_full(const unsigned long *bitmap, int bits) |
58 | e0e53b2f | Corentin Chary | { |
59 | e0e53b2f | Corentin Chary | int k, lim = bits/BITS_PER_LONG;
|
60 | e0e53b2f | Corentin Chary | |
61 | e0e53b2f | Corentin Chary | for (k = 0; k < lim; ++k) { |
62 | e0e53b2f | Corentin Chary | if (~bitmap[k]) {
|
63 | e0e53b2f | Corentin Chary | return 0; |
64 | e0e53b2f | Corentin Chary | } |
65 | e0e53b2f | Corentin Chary | } |
66 | e0e53b2f | Corentin Chary | |
67 | e0e53b2f | Corentin Chary | if (bits % BITS_PER_LONG) {
|
68 | e0e53b2f | Corentin Chary | if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
|
69 | e0e53b2f | Corentin Chary | return 0; |
70 | e0e53b2f | Corentin Chary | } |
71 | e0e53b2f | Corentin Chary | } |
72 | e0e53b2f | Corentin Chary | |
73 | e0e53b2f | Corentin Chary | return 1; |
74 | e0e53b2f | Corentin Chary | } |
75 | e0e53b2f | Corentin Chary | |
76 | e0e53b2f | Corentin Chary | int slow_bitmap_equal(const unsigned long *bitmap1, |
77 | e0e53b2f | Corentin Chary | const unsigned long *bitmap2, int bits) |
78 | e0e53b2f | Corentin Chary | { |
79 | e0e53b2f | Corentin Chary | int k, lim = bits/BITS_PER_LONG;
|
80 | e0e53b2f | Corentin Chary | |
81 | e0e53b2f | Corentin Chary | for (k = 0; k < lim; ++k) { |
82 | e0e53b2f | Corentin Chary | if (bitmap1[k] != bitmap2[k]) {
|
83 | e0e53b2f | Corentin Chary | return 0; |
84 | e0e53b2f | Corentin Chary | } |
85 | e0e53b2f | Corentin Chary | } |
86 | e0e53b2f | Corentin Chary | |
87 | e0e53b2f | Corentin Chary | if (bits % BITS_PER_LONG) {
|
88 | e0e53b2f | Corentin Chary | if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
|
89 | e0e53b2f | Corentin Chary | return 0; |
90 | e0e53b2f | Corentin Chary | } |
91 | e0e53b2f | Corentin Chary | } |
92 | e0e53b2f | Corentin Chary | |
93 | e0e53b2f | Corentin Chary | return 1; |
94 | e0e53b2f | Corentin Chary | } |
95 | e0e53b2f | Corentin Chary | |
96 | e0e53b2f | Corentin Chary | void slow_bitmap_complement(unsigned long *dst, const unsigned long *src, |
97 | e0e53b2f | Corentin Chary | int bits)
|
98 | e0e53b2f | Corentin Chary | { |
99 | e0e53b2f | Corentin Chary | int k, lim = bits/BITS_PER_LONG;
|
100 | e0e53b2f | Corentin Chary | |
101 | e0e53b2f | Corentin Chary | for (k = 0; k < lim; ++k) { |
102 | e0e53b2f | Corentin Chary | dst[k] = ~src[k]; |
103 | e0e53b2f | Corentin Chary | } |
104 | e0e53b2f | Corentin Chary | |
105 | e0e53b2f | Corentin Chary | if (bits % BITS_PER_LONG) {
|
106 | e0e53b2f | Corentin Chary | dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); |
107 | e0e53b2f | Corentin Chary | } |
108 | e0e53b2f | Corentin Chary | } |
109 | e0e53b2f | Corentin Chary | |
110 | e0e53b2f | Corentin Chary | int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1, |
111 | e0e53b2f | Corentin Chary | const unsigned long *bitmap2, int bits) |
112 | e0e53b2f | Corentin Chary | { |
113 | e0e53b2f | Corentin Chary | int k;
|
114 | e0e53b2f | Corentin Chary | int nr = BITS_TO_LONGS(bits);
|
115 | e0e53b2f | Corentin Chary | unsigned long result = 0; |
116 | e0e53b2f | Corentin Chary | |
117 | e0e53b2f | Corentin Chary | for (k = 0; k < nr; k++) { |
118 | e0e53b2f | Corentin Chary | result |= (dst[k] = bitmap1[k] & bitmap2[k]); |
119 | e0e53b2f | Corentin Chary | } |
120 | e0e53b2f | Corentin Chary | return result != 0; |
121 | e0e53b2f | Corentin Chary | } |
122 | e0e53b2f | Corentin Chary | |
123 | e0e53b2f | Corentin Chary | void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1, |
124 | e0e53b2f | Corentin Chary | const unsigned long *bitmap2, int bits) |
125 | e0e53b2f | Corentin Chary | { |
126 | e0e53b2f | Corentin Chary | int k;
|
127 | e0e53b2f | Corentin Chary | int nr = BITS_TO_LONGS(bits);
|
128 | e0e53b2f | Corentin Chary | |
129 | e0e53b2f | Corentin Chary | for (k = 0; k < nr; k++) { |
130 | e0e53b2f | Corentin Chary | dst[k] = bitmap1[k] | bitmap2[k]; |
131 | e0e53b2f | Corentin Chary | } |
132 | e0e53b2f | Corentin Chary | } |
133 | e0e53b2f | Corentin Chary | |
134 | e0e53b2f | Corentin Chary | void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, |
135 | e0e53b2f | Corentin Chary | const unsigned long *bitmap2, int bits) |
136 | e0e53b2f | Corentin Chary | { |
137 | e0e53b2f | Corentin Chary | int k;
|
138 | e0e53b2f | Corentin Chary | int nr = BITS_TO_LONGS(bits);
|
139 | e0e53b2f | Corentin Chary | |
140 | e0e53b2f | Corentin Chary | for (k = 0; k < nr; k++) { |
141 | e0e53b2f | Corentin Chary | dst[k] = bitmap1[k] ^ bitmap2[k]; |
142 | e0e53b2f | Corentin Chary | } |
143 | e0e53b2f | Corentin Chary | } |
144 | e0e53b2f | Corentin Chary | |
145 | e0e53b2f | Corentin Chary | int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, |
146 | e0e53b2f | Corentin Chary | const unsigned long *bitmap2, int bits) |
147 | e0e53b2f | Corentin Chary | { |
148 | e0e53b2f | Corentin Chary | int k;
|
149 | e0e53b2f | Corentin Chary | int nr = BITS_TO_LONGS(bits);
|
150 | e0e53b2f | Corentin Chary | unsigned long result = 0; |
151 | e0e53b2f | Corentin Chary | |
152 | e0e53b2f | Corentin Chary | for (k = 0; k < nr; k++) { |
153 | e0e53b2f | Corentin Chary | result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); |
154 | e0e53b2f | Corentin Chary | } |
155 | e0e53b2f | Corentin Chary | return result != 0; |
156 | e0e53b2f | Corentin Chary | } |
157 | e0e53b2f | Corentin Chary | |
158 | e0e53b2f | Corentin Chary | #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) |
159 | e0e53b2f | Corentin Chary | |
160 | e0e53b2f | Corentin Chary | void bitmap_set(unsigned long *map, int start, int nr) |
161 | e0e53b2f | Corentin Chary | { |
162 | e0e53b2f | Corentin Chary | unsigned long *p = map + BIT_WORD(start); |
163 | e0e53b2f | Corentin Chary | const int size = start + nr; |
164 | e0e53b2f | Corentin Chary | int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
|
165 | e0e53b2f | Corentin Chary | unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); |
166 | e0e53b2f | Corentin Chary | |
167 | e0e53b2f | Corentin Chary | while (nr - bits_to_set >= 0) { |
168 | e0e53b2f | Corentin Chary | *p |= mask_to_set; |
169 | e0e53b2f | Corentin Chary | nr -= bits_to_set; |
170 | e0e53b2f | Corentin Chary | bits_to_set = BITS_PER_LONG; |
171 | e0e53b2f | Corentin Chary | mask_to_set = ~0UL;
|
172 | e0e53b2f | Corentin Chary | p++; |
173 | e0e53b2f | Corentin Chary | } |
174 | e0e53b2f | Corentin Chary | if (nr) {
|
175 | e0e53b2f | Corentin Chary | mask_to_set &= BITMAP_LAST_WORD_MASK(size); |
176 | e0e53b2f | Corentin Chary | *p |= mask_to_set; |
177 | e0e53b2f | Corentin Chary | } |
178 | e0e53b2f | Corentin Chary | } |
179 | e0e53b2f | Corentin Chary | |
180 | e0e53b2f | Corentin Chary | void bitmap_clear(unsigned long *map, int start, int nr) |
181 | e0e53b2f | Corentin Chary | { |
182 | e0e53b2f | Corentin Chary | unsigned long *p = map + BIT_WORD(start); |
183 | e0e53b2f | Corentin Chary | const int size = start + nr; |
184 | e0e53b2f | Corentin Chary | int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
|
185 | e0e53b2f | Corentin Chary | unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); |
186 | e0e53b2f | Corentin Chary | |
187 | e0e53b2f | Corentin Chary | while (nr - bits_to_clear >= 0) { |
188 | e0e53b2f | Corentin Chary | *p &= ~mask_to_clear; |
189 | e0e53b2f | Corentin Chary | nr -= bits_to_clear; |
190 | e0e53b2f | Corentin Chary | bits_to_clear = BITS_PER_LONG; |
191 | e0e53b2f | Corentin Chary | mask_to_clear = ~0UL;
|
192 | e0e53b2f | Corentin Chary | p++; |
193 | e0e53b2f | Corentin Chary | } |
194 | e0e53b2f | Corentin Chary | if (nr) {
|
195 | e0e53b2f | Corentin Chary | mask_to_clear &= BITMAP_LAST_WORD_MASK(size); |
196 | e0e53b2f | Corentin Chary | *p &= ~mask_to_clear; |
197 | e0e53b2f | Corentin Chary | } |
198 | e0e53b2f | Corentin Chary | } |
199 | e0e53b2f | Corentin Chary | |
200 | e0e53b2f | Corentin Chary | #define ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
|
201 | e0e53b2f | Corentin Chary | |
202 | e0e53b2f | Corentin Chary | /**
|
203 | e0e53b2f | Corentin Chary | * bitmap_find_next_zero_area - find a contiguous aligned zero area
|
204 | e0e53b2f | Corentin Chary | * @map: The address to base the search on
|
205 | e0e53b2f | Corentin Chary | * @size: The bitmap size in bits
|
206 | e0e53b2f | Corentin Chary | * @start: The bitnumber to start searching at
|
207 | e0e53b2f | Corentin Chary | * @nr: The number of zeroed bits we're looking for
|
208 | e0e53b2f | Corentin Chary | * @align_mask: Alignment mask for zero area
|
209 | e0e53b2f | Corentin Chary | *
|
210 | e0e53b2f | Corentin Chary | * The @align_mask should be one less than a power of 2; the effect is that
|
211 | e0e53b2f | Corentin Chary | * the bit offset of all zero areas this function finds is multiples of that
|
212 | e0e53b2f | Corentin Chary | * power of 2. A @align_mask of 0 means no alignment is required.
|
213 | e0e53b2f | Corentin Chary | */
|
214 | e0e53b2f | Corentin Chary | unsigned long bitmap_find_next_zero_area(unsigned long *map, |
215 | e0e53b2f | Corentin Chary | unsigned long size, |
216 | e0e53b2f | Corentin Chary | unsigned long start, |
217 | e0e53b2f | Corentin Chary | unsigned int nr, |
218 | e0e53b2f | Corentin Chary | unsigned long align_mask) |
219 | e0e53b2f | Corentin Chary | { |
220 | e0e53b2f | Corentin Chary | unsigned long index, end, i; |
221 | e0e53b2f | Corentin Chary | again:
|
222 | e0e53b2f | Corentin Chary | index = find_next_zero_bit(map, size, start); |
223 | e0e53b2f | Corentin Chary | |
224 | e0e53b2f | Corentin Chary | /* Align allocation */
|
225 | e0e53b2f | Corentin Chary | index = ALIGN_MASK(index, align_mask); |
226 | e0e53b2f | Corentin Chary | |
227 | e0e53b2f | Corentin Chary | end = index + nr; |
228 | e0e53b2f | Corentin Chary | if (end > size) {
|
229 | e0e53b2f | Corentin Chary | return end;
|
230 | e0e53b2f | Corentin Chary | } |
231 | e0e53b2f | Corentin Chary | i = find_next_bit(map, end, index); |
232 | e0e53b2f | Corentin Chary | if (i < end) {
|
233 | e0e53b2f | Corentin Chary | start = i + 1;
|
234 | e0e53b2f | Corentin Chary | goto again;
|
235 | e0e53b2f | Corentin Chary | } |
236 | e0e53b2f | Corentin Chary | return index;
|
237 | e0e53b2f | Corentin Chary | } |
238 | e0e53b2f | Corentin Chary | |
239 | e0e53b2f | Corentin Chary | int slow_bitmap_intersects(const unsigned long *bitmap1, |
240 | e0e53b2f | Corentin Chary | const unsigned long *bitmap2, int bits) |
241 | e0e53b2f | Corentin Chary | { |
242 | e0e53b2f | Corentin Chary | int k, lim = bits/BITS_PER_LONG;
|
243 | e0e53b2f | Corentin Chary | |
244 | e0e53b2f | Corentin Chary | for (k = 0; k < lim; ++k) { |
245 | e0e53b2f | Corentin Chary | if (bitmap1[k] & bitmap2[k]) {
|
246 | e0e53b2f | Corentin Chary | return 1; |
247 | e0e53b2f | Corentin Chary | } |
248 | e0e53b2f | Corentin Chary | } |
249 | e0e53b2f | Corentin Chary | |
250 | e0e53b2f | Corentin Chary | if (bits % BITS_PER_LONG) {
|
251 | e0e53b2f | Corentin Chary | if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
|
252 | e0e53b2f | Corentin Chary | return 1; |
253 | e0e53b2f | Corentin Chary | } |
254 | e0e53b2f | Corentin Chary | } |
255 | e0e53b2f | Corentin Chary | return 0; |
256 | e0e53b2f | Corentin Chary | } |