Merge branch 'jc/decorate-leaky-separator-color'
[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_WORD;
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_WORD;
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_WORD;
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_WORD) / BITS_IN_WORD -
215                 (self->bit_size + BITS_IN_WORD - 1) / BITS_IN_WORD;
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_WORD));
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_WORD));
233                 return;
234         }
235
236         self->buffer[self->buffer_size - 1] |=
237                 ((eword_t)1 << (i % BITS_IN_WORD));
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_WORD;
259                         for (k = 0; k < len; ++k, ++pos)
260                                 callback(pos, payload);
261                 } else {
262                         pos += rlw_get_running_len(word) * BITS_IN_WORD;
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_WORD; ++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 }