Merge branch 'es/osx-header-pollutes-mask-macro' into maint
[git/git.git] / ewah / ewah_bitmap.c
1 /**
2 * Copyright 2013, GitHub, Inc
3 * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
4 * David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 */
20 #include "git-compat-util.h"
21 #include "ewok.h"
22 #include "ewok_rlw.h"
23
24 static inline size_t min_size(size_t a, size_t b)
25 {
26 return a < b ? a : b;
27 }
28
29 static inline size_t max_size(size_t a, size_t b)
30 {
31 return a > b ? a : b;
32 }
33
34 static inline void buffer_grow(struct ewah_bitmap *self, size_t new_size)
35 {
36 size_t rlw_offset = (uint8_t *)self->rlw - (uint8_t *)self->buffer;
37
38 if (self->alloc_size >= new_size)
39 return;
40
41 self->alloc_size = new_size;
42 self->buffer = ewah_realloc(self->buffer,
43 self->alloc_size * sizeof(eword_t));
44 self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
45 }
46
47 static inline void buffer_push(struct ewah_bitmap *self, eword_t value)
48 {
49 if (self->buffer_size + 1 >= self->alloc_size)
50 buffer_grow(self, self->buffer_size * 3 / 2);
51
52 self->buffer[self->buffer_size++] = value;
53 }
54
55 static void buffer_push_rlw(struct ewah_bitmap *self, eword_t value)
56 {
57 buffer_push(self, value);
58 self->rlw = self->buffer + self->buffer_size - 1;
59 }
60
61 static size_t add_empty_words(struct ewah_bitmap *self, int v, size_t number)
62 {
63 size_t added = 0;
64 eword_t runlen, can_add;
65
66 if (rlw_get_run_bit(self->rlw) != v && rlw_size(self->rlw) == 0) {
67 rlw_set_run_bit(self->rlw, v);
68 } else if (rlw_get_literal_words(self->rlw) != 0 ||
69 rlw_get_run_bit(self->rlw) != v) {
70 buffer_push_rlw(self, 0);
71 if (v) rlw_set_run_bit(self->rlw, v);
72 added++;
73 }
74
75 runlen = rlw_get_running_len(self->rlw);
76 can_add = min_size(number, RLW_LARGEST_RUNNING_COUNT - runlen);
77
78 rlw_set_running_len(self->rlw, runlen + can_add);
79 number -= can_add;
80
81 while (number >= RLW_LARGEST_RUNNING_COUNT) {
82 buffer_push_rlw(self, 0);
83 added++;
84 if (v) rlw_set_run_bit(self->rlw, v);
85 rlw_set_running_len(self->rlw, RLW_LARGEST_RUNNING_COUNT);
86 number -= RLW_LARGEST_RUNNING_COUNT;
87 }
88
89 if (number > 0) {
90 buffer_push_rlw(self, 0);
91 added++;
92
93 if (v) rlw_set_run_bit(self->rlw, v);
94 rlw_set_running_len(self->rlw, number);
95 }
96
97 return added;
98 }
99
100 size_t ewah_add_empty_words(struct ewah_bitmap *self, int v, size_t number)
101 {
102 if (number == 0)
103 return 0;
104
105 self->bit_size += number * BITS_IN_EWORD;
106 return add_empty_words(self, v, number);
107 }
108
109 static size_t add_literal(struct ewah_bitmap *self, eword_t new_data)
110 {
111 eword_t current_num = rlw_get_literal_words(self->rlw);
112
113 if (current_num >= RLW_LARGEST_LITERAL_COUNT) {
114 buffer_push_rlw(self, 0);
115
116 rlw_set_literal_words(self->rlw, 1);
117 buffer_push(self, new_data);
118 return 2;
119 }
120
121 rlw_set_literal_words(self->rlw, current_num + 1);
122
123 /* sanity check */
124 assert(rlw_get_literal_words(self->rlw) == current_num + 1);
125
126 buffer_push(self, new_data);
127 return 1;
128 }
129
130 void ewah_add_dirty_words(
131 struct ewah_bitmap *self, const eword_t *buffer,
132 size_t number, int negate)
133 {
134 size_t literals, can_add;
135
136 while (1) {
137 literals = rlw_get_literal_words(self->rlw);
138 can_add = min_size(number, RLW_LARGEST_LITERAL_COUNT - literals);
139
140 rlw_set_literal_words(self->rlw, literals + can_add);
141
142 if (self->buffer_size + can_add >= self->alloc_size)
143 buffer_grow(self, (self->buffer_size + can_add) * 3 / 2);
144
145 if (negate) {
146 size_t i;
147 for (i = 0; i < can_add; ++i)
148 self->buffer[self->buffer_size++] = ~buffer[i];
149 } else {
150 memcpy(self->buffer + self->buffer_size,
151 buffer, can_add * sizeof(eword_t));
152 self->buffer_size += can_add;
153 }
154
155 self->bit_size += can_add * BITS_IN_EWORD;
156
157 if (number - can_add == 0)
158 break;
159
160 buffer_push_rlw(self, 0);
161 buffer += can_add;
162 number -= can_add;
163 }
164 }
165
166 static size_t add_empty_word(struct ewah_bitmap *self, int v)
167 {
168 int no_literal = (rlw_get_literal_words(self->rlw) == 0);
169 eword_t run_len = rlw_get_running_len(self->rlw);
170
171 if (no_literal && run_len == 0) {
172 rlw_set_run_bit(self->rlw, v);
173 assert(rlw_get_run_bit(self->rlw) == v);
174 }
175
176 if (no_literal && rlw_get_run_bit(self->rlw) == v &&
177 run_len < RLW_LARGEST_RUNNING_COUNT) {
178 rlw_set_running_len(self->rlw, run_len + 1);
179 assert(rlw_get_running_len(self->rlw) == run_len + 1);
180 return 0;
181 } else {
182 buffer_push_rlw(self, 0);
183
184 assert(rlw_get_running_len(self->rlw) == 0);
185 assert(rlw_get_run_bit(self->rlw) == 0);
186 assert(rlw_get_literal_words(self->rlw) == 0);
187
188 rlw_set_run_bit(self->rlw, v);
189 assert(rlw_get_run_bit(self->rlw) == v);
190
191 rlw_set_running_len(self->rlw, 1);
192 assert(rlw_get_running_len(self->rlw) == 1);
193 assert(rlw_get_literal_words(self->rlw) == 0);
194 return 1;
195 }
196 }
197
198 size_t ewah_add(struct ewah_bitmap *self, eword_t word)
199 {
200 self->bit_size += BITS_IN_EWORD;
201
202 if (word == 0)
203 return add_empty_word(self, 0);
204
205 if (word == (eword_t)(~0))
206 return add_empty_word(self, 1);
207
208 return add_literal(self, word);
209 }
210
211 void ewah_set(struct ewah_bitmap *self, size_t i)
212 {
213 const size_t dist =
214 (i + BITS_IN_EWORD) / BITS_IN_EWORD -
215 (self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
216
217 assert(i >= self->bit_size);
218
219 self->bit_size = i + 1;
220
221 if (dist > 0) {
222 if (dist > 1)
223 add_empty_words(self, 0, dist - 1);
224
225 add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD));
226 return;
227 }
228
229 if (rlw_get_literal_words(self->rlw) == 0) {
230 rlw_set_running_len(self->rlw,
231 rlw_get_running_len(self->rlw) - 1);
232 add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD));
233 return;
234 }
235
236 self->buffer[self->buffer_size - 1] |=
237 ((eword_t)1 << (i % BITS_IN_EWORD));
238
239 /* check if we just completed a stream of 1s */
240 if (self->buffer[self->buffer_size - 1] == (eword_t)(~0)) {
241 self->buffer[--self->buffer_size] = 0;
242 rlw_set_literal_words(self->rlw,
243 rlw_get_literal_words(self->rlw) - 1);
244 add_empty_word(self, 1);
245 }
246 }
247
248 void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), void *payload)
249 {
250 size_t pos = 0;
251 size_t pointer = 0;
252 size_t k;
253
254 while (pointer < self->buffer_size) {
255 eword_t *word = &self->buffer[pointer];
256
257 if (rlw_get_run_bit(word)) {
258 size_t len = rlw_get_running_len(word) * BITS_IN_EWORD;
259 for (k = 0; k < len; ++k, ++pos)
260 callback(pos, payload);
261 } else {
262 pos += rlw_get_running_len(word) * BITS_IN_EWORD;
263 }
264
265 ++pointer;
266
267 for (k = 0; k < rlw_get_literal_words(word); ++k) {
268 int c;
269
270 /* todo: zero count optimization */
271 for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
272 if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)
273 callback(pos, payload);
274 }
275
276 ++pointer;
277 }
278 }
279 }
280
281 struct ewah_bitmap *ewah_new(void)
282 {
283 struct ewah_bitmap *self;
284
285 self = ewah_malloc(sizeof(struct ewah_bitmap));
286 if (self == NULL)
287 return NULL;
288
289 self->buffer = ewah_malloc(32 * sizeof(eword_t));
290 self->alloc_size = 32;
291
292 ewah_clear(self);
293 return self;
294 }
295
296 void ewah_clear(struct ewah_bitmap *self)
297 {
298 self->buffer_size = 1;
299 self->buffer[0] = 0;
300 self->bit_size = 0;
301 self->rlw = self->buffer;
302 }
303
304 void ewah_free(struct ewah_bitmap *self)
305 {
306 if (!self)
307 return;
308
309 if (self->alloc_size)
310 free(self->buffer);
311
312 free(self);
313 }
314
315 static void read_new_rlw(struct ewah_iterator *it)
316 {
317 const eword_t *word = NULL;
318
319 it->literals = 0;
320 it->compressed = 0;
321
322 while (1) {
323 word = &it->buffer[it->pointer];
324
325 it->rl = rlw_get_running_len(word);
326 it->lw = rlw_get_literal_words(word);
327 it->b = rlw_get_run_bit(word);
328
329 if (it->rl || it->lw)
330 return;
331
332 if (it->pointer < it->buffer_size - 1) {
333 it->pointer++;
334 } else {
335 it->pointer = it->buffer_size;
336 return;
337 }
338 }
339 }
340
341 int ewah_iterator_next(eword_t *next, struct ewah_iterator *it)
342 {
343 if (it->pointer >= it->buffer_size)
344 return 0;
345
346 if (it->compressed < it->rl) {
347 it->compressed++;
348 *next = it->b ? (eword_t)(~0) : 0;
349 } else {
350 assert(it->literals < it->lw);
351
352 it->literals++;
353 it->pointer++;
354
355 assert(it->pointer < it->buffer_size);
356
357 *next = it->buffer[it->pointer];
358 }
359
360 if (it->compressed == it->rl && it->literals == it->lw) {
361 if (++it->pointer < it->buffer_size)
362 read_new_rlw(it);
363 }
364
365 return 1;
366 }
367
368 void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)
369 {
370 it->buffer = parent->buffer;
371 it->buffer_size = parent->buffer_size;
372 it->pointer = 0;
373
374 it->lw = 0;
375 it->rl = 0;
376 it->compressed = 0;
377 it->literals = 0;
378 it->b = 0;
379
380 if (it->pointer < it->buffer_size)
381 read_new_rlw(it);
382 }
383
384 void ewah_not(struct ewah_bitmap *self)
385 {
386 size_t pointer = 0;
387
388 while (pointer < self->buffer_size) {
389 eword_t *word = &self->buffer[pointer];
390 size_t literals, k;
391
392 rlw_xor_run_bit(word);
393 ++pointer;
394
395 literals = rlw_get_literal_words(word);
396 for (k = 0; k < literals; ++k) {
397 self->buffer[pointer] = ~self->buffer[pointer];
398 ++pointer;
399 }
400 }
401 }
402
403 void ewah_xor(
404 struct ewah_bitmap *ewah_i,
405 struct ewah_bitmap *ewah_j,
406 struct ewah_bitmap *out)
407 {
408 struct rlw_iterator rlw_i;
409 struct rlw_iterator rlw_j;
410 size_t literals;
411
412 rlwit_init(&rlw_i, ewah_i);
413 rlwit_init(&rlw_j, ewah_j);
414
415 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
416 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
417 struct rlw_iterator *prey, *predator;
418 size_t index;
419 int negate_words;
420
421 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
422 prey = &rlw_i;
423 predator = &rlw_j;
424 } else {
425 prey = &rlw_j;
426 predator = &rlw_i;
427 }
428
429 negate_words = !!predator->rlw.running_bit;
430 index = rlwit_discharge(prey, out,
431 predator->rlw.running_len, negate_words);
432
433 ewah_add_empty_words(out, negate_words,
434 predator->rlw.running_len - index);
435
436 rlwit_discard_first_words(predator,
437 predator->rlw.running_len);
438 }
439
440 literals = min_size(
441 rlw_i.rlw.literal_words,
442 rlw_j.rlw.literal_words);
443
444 if (literals) {
445 size_t k;
446
447 for (k = 0; k < literals; ++k) {
448 ewah_add(out,
449 rlw_i.buffer[rlw_i.literal_word_start + k] ^
450 rlw_j.buffer[rlw_j.literal_word_start + k]
451 );
452 }
453
454 rlwit_discard_first_words(&rlw_i, literals);
455 rlwit_discard_first_words(&rlw_j, literals);
456 }
457 }
458
459 if (rlwit_word_size(&rlw_i) > 0)
460 rlwit_discharge(&rlw_i, out, ~0, 0);
461 else
462 rlwit_discharge(&rlw_j, out, ~0, 0);
463
464 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
465 }
466
467 void ewah_and(
468 struct ewah_bitmap *ewah_i,
469 struct ewah_bitmap *ewah_j,
470 struct ewah_bitmap *out)
471 {
472 struct rlw_iterator rlw_i;
473 struct rlw_iterator rlw_j;
474 size_t literals;
475
476 rlwit_init(&rlw_i, ewah_i);
477 rlwit_init(&rlw_j, ewah_j);
478
479 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
480 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
481 struct rlw_iterator *prey, *predator;
482
483 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
484 prey = &rlw_i;
485 predator = &rlw_j;
486 } else {
487 prey = &rlw_j;
488 predator = &rlw_i;
489 }
490
491 if (predator->rlw.running_bit == 0) {
492 ewah_add_empty_words(out, 0,
493 predator->rlw.running_len);
494 rlwit_discard_first_words(prey,
495 predator->rlw.running_len);
496 rlwit_discard_first_words(predator,
497 predator->rlw.running_len);
498 } else {
499 size_t index = rlwit_discharge(prey, out,
500 predator->rlw.running_len, 0);
501 ewah_add_empty_words(out, 0,
502 predator->rlw.running_len - index);
503 rlwit_discard_first_words(predator,
504 predator->rlw.running_len);
505 }
506 }
507
508 literals = min_size(
509 rlw_i.rlw.literal_words,
510 rlw_j.rlw.literal_words);
511
512 if (literals) {
513 size_t k;
514
515 for (k = 0; k < literals; ++k) {
516 ewah_add(out,
517 rlw_i.buffer[rlw_i.literal_word_start + k] &
518 rlw_j.buffer[rlw_j.literal_word_start + k]
519 );
520 }
521
522 rlwit_discard_first_words(&rlw_i, literals);
523 rlwit_discard_first_words(&rlw_j, literals);
524 }
525 }
526
527 if (rlwit_word_size(&rlw_i) > 0)
528 rlwit_discharge_empty(&rlw_i, out);
529 else
530 rlwit_discharge_empty(&rlw_j, out);
531
532 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
533 }
534
535 void ewah_and_not(
536 struct ewah_bitmap *ewah_i,
537 struct ewah_bitmap *ewah_j,
538 struct ewah_bitmap *out)
539 {
540 struct rlw_iterator rlw_i;
541 struct rlw_iterator rlw_j;
542 size_t literals;
543
544 rlwit_init(&rlw_i, ewah_i);
545 rlwit_init(&rlw_j, ewah_j);
546
547 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
548 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
549 struct rlw_iterator *prey, *predator;
550
551 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
552 prey = &rlw_i;
553 predator = &rlw_j;
554 } else {
555 prey = &rlw_j;
556 predator = &rlw_i;
557 }
558
559 if ((predator->rlw.running_bit && prey == &rlw_i) ||
560 (!predator->rlw.running_bit && prey != &rlw_i)) {
561 ewah_add_empty_words(out, 0,
562 predator->rlw.running_len);
563 rlwit_discard_first_words(prey,
564 predator->rlw.running_len);
565 rlwit_discard_first_words(predator,
566 predator->rlw.running_len);
567 } else {
568 size_t index;
569 int negate_words;
570
571 negate_words = (&rlw_i != prey);
572 index = rlwit_discharge(prey, out,
573 predator->rlw.running_len, negate_words);
574 ewah_add_empty_words(out, negate_words,
575 predator->rlw.running_len - index);
576 rlwit_discard_first_words(predator,
577 predator->rlw.running_len);
578 }
579 }
580
581 literals = min_size(
582 rlw_i.rlw.literal_words,
583 rlw_j.rlw.literal_words);
584
585 if (literals) {
586 size_t k;
587
588 for (k = 0; k < literals; ++k) {
589 ewah_add(out,
590 rlw_i.buffer[rlw_i.literal_word_start + k] &
591 ~(rlw_j.buffer[rlw_j.literal_word_start + k])
592 );
593 }
594
595 rlwit_discard_first_words(&rlw_i, literals);
596 rlwit_discard_first_words(&rlw_j, literals);
597 }
598 }
599
600 if (rlwit_word_size(&rlw_i) > 0)
601 rlwit_discharge(&rlw_i, out, ~0, 0);
602 else
603 rlwit_discharge_empty(&rlw_j, out);
604
605 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
606 }
607
608 void ewah_or(
609 struct ewah_bitmap *ewah_i,
610 struct ewah_bitmap *ewah_j,
611 struct ewah_bitmap *out)
612 {
613 struct rlw_iterator rlw_i;
614 struct rlw_iterator rlw_j;
615 size_t literals;
616
617 rlwit_init(&rlw_i, ewah_i);
618 rlwit_init(&rlw_j, ewah_j);
619
620 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
621 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
622 struct rlw_iterator *prey, *predator;
623
624 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
625 prey = &rlw_i;
626 predator = &rlw_j;
627 } else {
628 prey = &rlw_j;
629 predator = &rlw_i;
630 }
631
632 if (predator->rlw.running_bit) {
633 ewah_add_empty_words(out, 0,
634 predator->rlw.running_len);
635 rlwit_discard_first_words(prey,
636 predator->rlw.running_len);
637 rlwit_discard_first_words(predator,
638 predator->rlw.running_len);
639 } else {
640 size_t index = rlwit_discharge(prey, out,
641 predator->rlw.running_len, 0);
642 ewah_add_empty_words(out, 0,
643 predator->rlw.running_len - index);
644 rlwit_discard_first_words(predator,
645 predator->rlw.running_len);
646 }
647 }
648
649 literals = min_size(
650 rlw_i.rlw.literal_words,
651 rlw_j.rlw.literal_words);
652
653 if (literals) {
654 size_t k;
655
656 for (k = 0; k < literals; ++k) {
657 ewah_add(out,
658 rlw_i.buffer[rlw_i.literal_word_start + k] |
659 rlw_j.buffer[rlw_j.literal_word_start + k]
660 );
661 }
662
663 rlwit_discard_first_words(&rlw_i, literals);
664 rlwit_discard_first_words(&rlw_j, literals);
665 }
666 }
667
668 if (rlwit_word_size(&rlw_i) > 0)
669 rlwit_discharge(&rlw_i, out, ~0, 0);
670 else
671 rlwit_discharge(&rlw_j, out, ~0, 0);
672
673 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
674 }
675
676
677 #define BITMAP_POOL_MAX 16
678 static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
679 static size_t bitmap_pool_size;
680
681 struct ewah_bitmap *ewah_pool_new(void)
682 {
683 if (bitmap_pool_size)
684 return bitmap_pool[--bitmap_pool_size];
685
686 return ewah_new();
687 }
688
689 void ewah_pool_free(struct ewah_bitmap *self)
690 {
691 if (self == NULL)
692 return;
693
694 if (bitmap_pool_size == BITMAP_POOL_MAX ||
695 self->alloc_size == 0) {
696 ewah_free(self);
697 return;
698 }
699
700 ewah_clear(self);
701 bitmap_pool[bitmap_pool_size++] = self;
702 }
703
704 uint32_t ewah_checksum(struct ewah_bitmap *self)
705 {
706 const uint8_t *p = (uint8_t *)self->buffer;
707 uint32_t crc = (uint32_t)self->bit_size;
708 size_t size = self->buffer_size * sizeof(eword_t);
709
710 while (size--)
711 crc = (crc << 5) - crc + (uint32_t)*p++;
712
713 return crc;
714 }