fcd465e9c24ef992b156a5242faabaf7272003be
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
24static inline size_t min_size(size_t a, size_t b)
25{
26 return a < b ? a : b;
27}
28
29static inline size_t max_size(size_t a, size_t b)
30{
31 return a > b ? a : b;
32}
33
34static 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 = xrealloc(self->buffer,
43 self->alloc_size * sizeof(eword_t));
44 self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
45}
46
47static 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
55static 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
61static 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
100size_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
109static 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
130void 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
166static 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
198size_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
211void 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
248void 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
281struct ewah_bitmap *ewah_new(void)
282{
283 struct ewah_bitmap *self;
284
285 self = xmalloc(sizeof(struct ewah_bitmap));
286 self->buffer = xmalloc(32 * sizeof(eword_t));
287 self->alloc_size = 32;
288
289 ewah_clear(self);
290 return self;
291}
292
293void ewah_clear(struct ewah_bitmap *self)
294{
295 self->buffer_size = 1;
296 self->buffer[0] = 0;
297 self->bit_size = 0;
298 self->rlw = self->buffer;
299}
300
301void ewah_free(struct ewah_bitmap *self)
302{
303 if (!self)
304 return;
305
306 if (self->alloc_size)
307 free(self->buffer);
308
309 free(self);
310}
311
312static void read_new_rlw(struct ewah_iterator *it)
313{
314 const eword_t *word = NULL;
315
316 it->literals = 0;
317 it->compressed = 0;
318
319 while (1) {
320 word = &it->buffer[it->pointer];
321
322 it->rl = rlw_get_running_len(word);
323 it->lw = rlw_get_literal_words(word);
324 it->b = rlw_get_run_bit(word);
325
326 if (it->rl || it->lw)
327 return;
328
329 if (it->pointer < it->buffer_size - 1) {
330 it->pointer++;
331 } else {
332 it->pointer = it->buffer_size;
333 return;
334 }
335 }
336}
337
338int ewah_iterator_next(eword_t *next, struct ewah_iterator *it)
339{
340 if (it->pointer >= it->buffer_size)
341 return 0;
342
343 if (it->compressed < it->rl) {
344 it->compressed++;
345 *next = it->b ? (eword_t)(~0) : 0;
346 } else {
347 assert(it->literals < it->lw);
348
349 it->literals++;
350 it->pointer++;
351
352 assert(it->pointer < it->buffer_size);
353
354 *next = it->buffer[it->pointer];
355 }
356
357 if (it->compressed == it->rl && it->literals == it->lw) {
358 if (++it->pointer < it->buffer_size)
359 read_new_rlw(it);
360 }
361
362 return 1;
363}
364
365void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)
366{
367 it->buffer = parent->buffer;
368 it->buffer_size = parent->buffer_size;
369 it->pointer = 0;
370
371 it->lw = 0;
372 it->rl = 0;
373 it->compressed = 0;
374 it->literals = 0;
375 it->b = 0;
376
377 if (it->pointer < it->buffer_size)
378 read_new_rlw(it);
379}
380
381void ewah_not(struct ewah_bitmap *self)
382{
383 size_t pointer = 0;
384
385 while (pointer < self->buffer_size) {
386 eword_t *word = &self->buffer[pointer];
387 size_t literals, k;
388
389 rlw_xor_run_bit(word);
390 ++pointer;
391
392 literals = rlw_get_literal_words(word);
393 for (k = 0; k < literals; ++k) {
394 self->buffer[pointer] = ~self->buffer[pointer];
395 ++pointer;
396 }
397 }
398}
399
400void ewah_xor(
401 struct ewah_bitmap *ewah_i,
402 struct ewah_bitmap *ewah_j,
403 struct ewah_bitmap *out)
404{
405 struct rlw_iterator rlw_i;
406 struct rlw_iterator rlw_j;
407 size_t literals;
408
409 rlwit_init(&rlw_i, ewah_i);
410 rlwit_init(&rlw_j, ewah_j);
411
412 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
413 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
414 struct rlw_iterator *prey, *predator;
415 size_t index;
416 int negate_words;
417
418 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
419 prey = &rlw_i;
420 predator = &rlw_j;
421 } else {
422 prey = &rlw_j;
423 predator = &rlw_i;
424 }
425
426 negate_words = !!predator->rlw.running_bit;
427 index = rlwit_discharge(prey, out,
428 predator->rlw.running_len, negate_words);
429
430 ewah_add_empty_words(out, negate_words,
431 predator->rlw.running_len - index);
432
433 rlwit_discard_first_words(predator,
434 predator->rlw.running_len);
435 }
436
437 literals = min_size(
438 rlw_i.rlw.literal_words,
439 rlw_j.rlw.literal_words);
440
441 if (literals) {
442 size_t k;
443
444 for (k = 0; k < literals; ++k) {
445 ewah_add(out,
446 rlw_i.buffer[rlw_i.literal_word_start + k] ^
447 rlw_j.buffer[rlw_j.literal_word_start + k]
448 );
449 }
450
451 rlwit_discard_first_words(&rlw_i, literals);
452 rlwit_discard_first_words(&rlw_j, literals);
453 }
454 }
455
456 if (rlwit_word_size(&rlw_i) > 0)
457 rlwit_discharge(&rlw_i, out, ~0, 0);
458 else
459 rlwit_discharge(&rlw_j, out, ~0, 0);
460
461 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
462}
463
464void ewah_and(
465 struct ewah_bitmap *ewah_i,
466 struct ewah_bitmap *ewah_j,
467 struct ewah_bitmap *out)
468{
469 struct rlw_iterator rlw_i;
470 struct rlw_iterator rlw_j;
471 size_t literals;
472
473 rlwit_init(&rlw_i, ewah_i);
474 rlwit_init(&rlw_j, ewah_j);
475
476 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
477 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
478 struct rlw_iterator *prey, *predator;
479
480 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
481 prey = &rlw_i;
482 predator = &rlw_j;
483 } else {
484 prey = &rlw_j;
485 predator = &rlw_i;
486 }
487
488 if (predator->rlw.running_bit == 0) {
489 ewah_add_empty_words(out, 0,
490 predator->rlw.running_len);
491 rlwit_discard_first_words(prey,
492 predator->rlw.running_len);
493 rlwit_discard_first_words(predator,
494 predator->rlw.running_len);
495 } else {
496 size_t index = rlwit_discharge(prey, out,
497 predator->rlw.running_len, 0);
498 ewah_add_empty_words(out, 0,
499 predator->rlw.running_len - index);
500 rlwit_discard_first_words(predator,
501 predator->rlw.running_len);
502 }
503 }
504
505 literals = min_size(
506 rlw_i.rlw.literal_words,
507 rlw_j.rlw.literal_words);
508
509 if (literals) {
510 size_t k;
511
512 for (k = 0; k < literals; ++k) {
513 ewah_add(out,
514 rlw_i.buffer[rlw_i.literal_word_start + k] &
515 rlw_j.buffer[rlw_j.literal_word_start + k]
516 );
517 }
518
519 rlwit_discard_first_words(&rlw_i, literals);
520 rlwit_discard_first_words(&rlw_j, literals);
521 }
522 }
523
524 if (rlwit_word_size(&rlw_i) > 0)
525 rlwit_discharge_empty(&rlw_i, out);
526 else
527 rlwit_discharge_empty(&rlw_j, out);
528
529 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
530}
531
532void ewah_and_not(
533 struct ewah_bitmap *ewah_i,
534 struct ewah_bitmap *ewah_j,
535 struct ewah_bitmap *out)
536{
537 struct rlw_iterator rlw_i;
538 struct rlw_iterator rlw_j;
539 size_t literals;
540
541 rlwit_init(&rlw_i, ewah_i);
542 rlwit_init(&rlw_j, ewah_j);
543
544 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
545 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
546 struct rlw_iterator *prey, *predator;
547
548 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
549 prey = &rlw_i;
550 predator = &rlw_j;
551 } else {
552 prey = &rlw_j;
553 predator = &rlw_i;
554 }
555
556 if ((predator->rlw.running_bit && prey == &rlw_i) ||
557 (!predator->rlw.running_bit && prey != &rlw_i)) {
558 ewah_add_empty_words(out, 0,
559 predator->rlw.running_len);
560 rlwit_discard_first_words(prey,
561 predator->rlw.running_len);
562 rlwit_discard_first_words(predator,
563 predator->rlw.running_len);
564 } else {
565 size_t index;
566 int negate_words;
567
568 negate_words = (&rlw_i != prey);
569 index = rlwit_discharge(prey, out,
570 predator->rlw.running_len, negate_words);
571 ewah_add_empty_words(out, negate_words,
572 predator->rlw.running_len - index);
573 rlwit_discard_first_words(predator,
574 predator->rlw.running_len);
575 }
576 }
577
578 literals = min_size(
579 rlw_i.rlw.literal_words,
580 rlw_j.rlw.literal_words);
581
582 if (literals) {
583 size_t k;
584
585 for (k = 0; k < literals; ++k) {
586 ewah_add(out,
587 rlw_i.buffer[rlw_i.literal_word_start + k] &
588 ~(rlw_j.buffer[rlw_j.literal_word_start + k])
589 );
590 }
591
592 rlwit_discard_first_words(&rlw_i, literals);
593 rlwit_discard_first_words(&rlw_j, literals);
594 }
595 }
596
597 if (rlwit_word_size(&rlw_i) > 0)
598 rlwit_discharge(&rlw_i, out, ~0, 0);
599 else
600 rlwit_discharge_empty(&rlw_j, out);
601
602 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
603}
604
605void ewah_or(
606 struct ewah_bitmap *ewah_i,
607 struct ewah_bitmap *ewah_j,
608 struct ewah_bitmap *out)
609{
610 struct rlw_iterator rlw_i;
611 struct rlw_iterator rlw_j;
612 size_t literals;
613
614 rlwit_init(&rlw_i, ewah_i);
615 rlwit_init(&rlw_j, ewah_j);
616
617 while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
618 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
619 struct rlw_iterator *prey, *predator;
620
621 if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
622 prey = &rlw_i;
623 predator = &rlw_j;
624 } else {
625 prey = &rlw_j;
626 predator = &rlw_i;
627 }
628
629 if (predator->rlw.running_bit) {
630 ewah_add_empty_words(out, 0,
631 predator->rlw.running_len);
632 rlwit_discard_first_words(prey,
633 predator->rlw.running_len);
634 rlwit_discard_first_words(predator,
635 predator->rlw.running_len);
636 } else {
637 size_t index = rlwit_discharge(prey, out,
638 predator->rlw.running_len, 0);
639 ewah_add_empty_words(out, 0,
640 predator->rlw.running_len - index);
641 rlwit_discard_first_words(predator,
642 predator->rlw.running_len);
643 }
644 }
645
646 literals = min_size(
647 rlw_i.rlw.literal_words,
648 rlw_j.rlw.literal_words);
649
650 if (literals) {
651 size_t k;
652
653 for (k = 0; k < literals; ++k) {
654 ewah_add(out,
655 rlw_i.buffer[rlw_i.literal_word_start + k] |
656 rlw_j.buffer[rlw_j.literal_word_start + k]
657 );
658 }
659
660 rlwit_discard_first_words(&rlw_i, literals);
661 rlwit_discard_first_words(&rlw_j, literals);
662 }
663 }
664
665 if (rlwit_word_size(&rlw_i) > 0)
666 rlwit_discharge(&rlw_i, out, ~0, 0);
667 else
668 rlwit_discharge(&rlw_j, out, ~0, 0);
669
670 out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
671}
672
673
674#define BITMAP_POOL_MAX 16
675static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
676static size_t bitmap_pool_size;
677
678struct ewah_bitmap *ewah_pool_new(void)
679{
680 if (bitmap_pool_size)
681 return bitmap_pool[--bitmap_pool_size];
682
683 return ewah_new();
684}
685
686void ewah_pool_free(struct ewah_bitmap *self)
687{
688 if (self == NULL)
689 return;
690
691 if (bitmap_pool_size == BITMAP_POOL_MAX ||
692 self->alloc_size == 0) {
693 ewah_free(self);
694 return;
695 }
696
697 ewah_clear(self);
698 bitmap_pool[bitmap_pool_size++] = self;
699}
700
701uint32_t ewah_checksum(struct ewah_bitmap *self)
702{
703 const uint8_t *p = (uint8_t *)self->buffer;
704 uint32_t crc = (uint32_t)self->bit_size;
705 size_t size = self->buffer_size * sizeof(eword_t);
706
707 while (size--)
708 crc = (crc << 5) - crc + (uint32_t)*p++;
709
710 return crc;
711}