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