diff options
Diffstat (limited to 'third_party/git/ewah/ewah_bitmap.c')
| -rw-r--r-- | third_party/git/ewah/ewah_bitmap.c | 484 |
1 files changed, 484 insertions, 0 deletions
diff --git a/third_party/git/ewah/ewah_bitmap.c b/third_party/git/ewah/ewah_bitmap.c new file mode 100644 index 0000000000..d59b1afe3d --- /dev/null +++ b/third_party/git/ewah/ewah_bitmap.c @@ -0,0 +1,484 @@ +/** + * Copyright 2013, GitHub, Inc + * Copyright 2009-2013, Daniel Lemire, Cliff Moon, + * David McIntosh, Robert Becho, Google Inc. and Veronika Zenz + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see <http://www.gnu.org/licenses/>. + */ +#include "git-compat-util.h" +#include "ewok.h" +#include "ewok_rlw.h" + +static inline size_t min_size(size_t a, size_t b) +{ + return a < b ? a : b; +} + +static inline size_t max_size(size_t a, size_t b) +{ + return a > b ? a : b; +} + +static inline void buffer_grow(struct ewah_bitmap *self, size_t new_size) +{ + size_t rlw_offset = (uint8_t *)self->rlw - (uint8_t *)self->buffer; + + if (self->alloc_size >= new_size) + return; + + self->alloc_size = new_size; + REALLOC_ARRAY(self->buffer, self->alloc_size); + self->rlw = self->buffer + (rlw_offset / sizeof(eword_t)); +} + +static inline void buffer_push(struct ewah_bitmap *self, eword_t value) +{ + if (self->buffer_size + 1 >= self->alloc_size) + buffer_grow(self, self->buffer_size * 3 / 2); + + self->buffer[self->buffer_size++] = value; +} + +static void buffer_push_rlw(struct ewah_bitmap *self, eword_t value) +{ + buffer_push(self, value); + self->rlw = self->buffer + self->buffer_size - 1; +} + +static size_t add_empty_words(struct ewah_bitmap *self, int v, size_t number) +{ + size_t added = 0; + eword_t runlen, can_add; + + if (rlw_get_run_bit(self->rlw) != v && rlw_size(self->rlw) == 0) { + rlw_set_run_bit(self->rlw, v); + } else if (rlw_get_literal_words(self->rlw) != 0 || + rlw_get_run_bit(self->rlw) != v) { + buffer_push_rlw(self, 0); + if (v) rlw_set_run_bit(self->rlw, v); + added++; + } + + runlen = rlw_get_running_len(self->rlw); + can_add = min_size(number, RLW_LARGEST_RUNNING_COUNT - runlen); + + rlw_set_running_len(self->rlw, runlen + can_add); + number -= can_add; + + while (number >= RLW_LARGEST_RUNNING_COUNT) { + buffer_push_rlw(self, 0); + added++; + if (v) rlw_set_run_bit(self->rlw, v); + rlw_set_running_len(self->rlw, RLW_LARGEST_RUNNING_COUNT); + number -= RLW_LARGEST_RUNNING_COUNT; + } + + if (number > 0) { + buffer_push_rlw(self, 0); + added++; + + if (v) rlw_set_run_bit(self->rlw, v); + rlw_set_running_len(self->rlw, number); + } + + return added; +} + +size_t ewah_add_empty_words(struct ewah_bitmap *self, int v, size_t number) +{ + if (number == 0) + return 0; + + self->bit_size += number * BITS_IN_EWORD; + return add_empty_words(self, v, number); +} + +static size_t add_literal(struct ewah_bitmap *self, eword_t new_data) +{ + eword_t current_num = rlw_get_literal_words(self->rlw); + + if (current_num >= RLW_LARGEST_LITERAL_COUNT) { + buffer_push_rlw(self, 0); + + rlw_set_literal_words(self->rlw, 1); + buffer_push(self, new_data); + return 2; + } + + rlw_set_literal_words(self->rlw, current_num + 1); + + /* sanity check */ + assert(rlw_get_literal_words(self->rlw) == current_num + 1); + + buffer_push(self, new_data); + return 1; +} + +void ewah_add_dirty_words( + struct ewah_bitmap *self, const eword_t *buffer, + size_t number, int negate) +{ + size_t literals, can_add; + + while (1) { + literals = rlw_get_literal_words(self->rlw); + can_add = min_size(number, RLW_LARGEST_LITERAL_COUNT - literals); + + rlw_set_literal_words(self->rlw, literals + can_add); + + if (self->buffer_size + can_add >= self->alloc_size) + buffer_grow(self, (self->buffer_size + can_add) * 3 / 2); + + if (negate) { + size_t i; + for (i = 0; i < can_add; ++i) + self->buffer[self->buffer_size++] = ~buffer[i]; + } else { + memcpy(self->buffer + self->buffer_size, + buffer, can_add * sizeof(eword_t)); + self->buffer_size += can_add; + } + + self->bit_size += can_add * BITS_IN_EWORD; + + if (number - can_add == 0) + break; + + buffer_push_rlw(self, 0); + buffer += can_add; + number -= can_add; + } +} + +static size_t add_empty_word(struct ewah_bitmap *self, int v) +{ + int no_literal = (rlw_get_literal_words(self->rlw) == 0); + eword_t run_len = rlw_get_running_len(self->rlw); + + if (no_literal && run_len == 0) { + rlw_set_run_bit(self->rlw, v); + assert(rlw_get_run_bit(self->rlw) == v); + } + + if (no_literal && rlw_get_run_bit(self->rlw) == v && + run_len < RLW_LARGEST_RUNNING_COUNT) { + rlw_set_running_len(self->rlw, run_len + 1); + assert(rlw_get_running_len(self->rlw) == run_len + 1); + return 0; + } else { + buffer_push_rlw(self, 0); + + assert(rlw_get_running_len(self->rlw) == 0); + assert(rlw_get_run_bit(self->rlw) == 0); + assert(rlw_get_literal_words(self->rlw) == 0); + + rlw_set_run_bit(self->rlw, v); + assert(rlw_get_run_bit(self->rlw) == v); + + rlw_set_running_len(self->rlw, 1); + assert(rlw_get_running_len(self->rlw) == 1); + assert(rlw_get_literal_words(self->rlw) == 0); + return 1; + } +} + +size_t ewah_add(struct ewah_bitmap *self, eword_t word) +{ + self->bit_size += BITS_IN_EWORD; + + if (word == 0) + return add_empty_word(self, 0); + + if (word == (eword_t)(~0)) + return add_empty_word(self, 1); + + return add_literal(self, word); +} + +void ewah_set(struct ewah_bitmap *self, size_t i) +{ + const size_t dist = + DIV_ROUND_UP(i + 1, BITS_IN_EWORD) - + DIV_ROUND_UP(self->bit_size, BITS_IN_EWORD); + + assert(i >= self->bit_size); + + self->bit_size = i + 1; + + if (dist > 0) { + if (dist > 1) + add_empty_words(self, 0, dist - 1); + + add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD)); + return; + } + + if (rlw_get_literal_words(self->rlw) == 0) { + rlw_set_running_len(self->rlw, + rlw_get_running_len(self->rlw) - 1); + add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD)); + return; + } + + self->buffer[self->buffer_size - 1] |= + ((eword_t)1 << (i % BITS_IN_EWORD)); + + /* check if we just completed a stream of 1s */ + if (self->buffer[self->buffer_size - 1] == (eword_t)(~0)) { + self->buffer[--self->buffer_size] = 0; + rlw_set_literal_words(self->rlw, + rlw_get_literal_words(self->rlw) - 1); + add_empty_word(self, 1); + } +} + +void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), void *payload) +{ + size_t pos = 0; + size_t pointer = 0; + size_t k; + + while (pointer < self->buffer_size) { + eword_t *word = &self->buffer[pointer]; + + if (rlw_get_run_bit(word)) { + size_t len = rlw_get_running_len(word) * BITS_IN_EWORD; + for (k = 0; k < len; ++k, ++pos) + callback(pos, payload); + } else { + pos += rlw_get_running_len(word) * BITS_IN_EWORD; + } + + ++pointer; + + for (k = 0; k < rlw_get_literal_words(word); ++k) { + int c; + + /* todo: zero count optimization */ + for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) { + if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0) + callback(pos, payload); + } + + ++pointer; + } + } +} + +/** + * Clear all the bits in the bitmap. Does not free or resize + * memory. + */ +static void ewah_clear(struct ewah_bitmap *self) +{ + self->buffer_size = 1; + self->buffer[0] = 0; + self->bit_size = 0; + self->rlw = self->buffer; +} + +struct ewah_bitmap *ewah_new(void) +{ + struct ewah_bitmap *self; + + self = xmalloc(sizeof(struct ewah_bitmap)); + self->alloc_size = 32; + ALLOC_ARRAY(self->buffer, self->alloc_size); + + ewah_clear(self); + return self; +} + +void ewah_free(struct ewah_bitmap *self) +{ + if (!self) + return; + + if (self->alloc_size) + free(self->buffer); + + free(self); +} + +static void read_new_rlw(struct ewah_iterator *it) +{ + const eword_t *word = NULL; + + it->literals = 0; + it->compressed = 0; + + while (1) { + word = &it->buffer[it->pointer]; + + it->rl = rlw_get_running_len(word); + it->lw = rlw_get_literal_words(word); + it->b = rlw_get_run_bit(word); + + if (it->rl || it->lw) + return; + + if (it->pointer < it->buffer_size - 1) { + it->pointer++; + } else { + it->pointer = it->buffer_size; + return; + } + } +} + +int ewah_iterator_next(eword_t *next, struct ewah_iterator *it) +{ + if (it->pointer >= it->buffer_size) + return 0; + + if (it->compressed < it->rl) { + it->compressed++; + *next = it->b ? (eword_t)(~0) : 0; + } else { + assert(it->literals < it->lw); + + it->literals++; + it->pointer++; + + assert(it->pointer < it->buffer_size); + + *next = it->buffer[it->pointer]; + } + + if (it->compressed == it->rl && it->literals == it->lw) { + if (++it->pointer < it->buffer_size) + read_new_rlw(it); + } + + return 1; +} + +void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent) +{ + it->buffer = parent->buffer; + it->buffer_size = parent->buffer_size; + it->pointer = 0; + + it->lw = 0; + it->rl = 0; + it->compressed = 0; + it->literals = 0; + it->b = 0; + + if (it->pointer < it->buffer_size) + read_new_rlw(it); +} + +void ewah_xor( + struct ewah_bitmap *ewah_i, + struct ewah_bitmap *ewah_j, + struct ewah_bitmap *out) +{ + struct rlw_iterator rlw_i; + struct rlw_iterator rlw_j; + size_t literals; + + rlwit_init(&rlw_i, ewah_i); + rlwit_init(&rlw_j, ewah_j); + + while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) { + while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) { + struct rlw_iterator *prey, *predator; + size_t index; + int negate_words; + + if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { + prey = &rlw_i; + predator = &rlw_j; + } else { + prey = &rlw_j; + predator = &rlw_i; + } + + negate_words = !!predator->rlw.running_bit; + index = rlwit_discharge(prey, out, + predator->rlw.running_len, negate_words); + + ewah_add_empty_words(out, negate_words, + predator->rlw.running_len - index); + + rlwit_discard_first_words(predator, + predator->rlw.running_len); + } + + literals = min_size( + rlw_i.rlw.literal_words, + rlw_j.rlw.literal_words); + + if (literals) { + size_t k; + + for (k = 0; k < literals; ++k) { + ewah_add(out, + rlw_i.buffer[rlw_i.literal_word_start + k] ^ + rlw_j.buffer[rlw_j.literal_word_start + k] + ); + } + + rlwit_discard_first_words(&rlw_i, literals); + rlwit_discard_first_words(&rlw_j, literals); + } + } + + if (rlwit_word_size(&rlw_i) > 0) + rlwit_discharge(&rlw_i, out, ~0, 0); + else + rlwit_discharge(&rlw_j, out, ~0, 0); + + out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size); +} + +#define BITMAP_POOL_MAX 16 +static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX]; +static size_t bitmap_pool_size; + +struct ewah_bitmap *ewah_pool_new(void) +{ + if (bitmap_pool_size) + return bitmap_pool[--bitmap_pool_size]; + + return ewah_new(); +} + +void ewah_pool_free(struct ewah_bitmap *self) +{ + if (self == NULL) + return; + + if (bitmap_pool_size == BITMAP_POOL_MAX || + self->alloc_size == 0) { + ewah_free(self); + return; + } + + ewah_clear(self); + bitmap_pool[bitmap_pool_size++] = self; +} + +uint32_t ewah_checksum(struct ewah_bitmap *self) +{ + const uint8_t *p = (uint8_t *)self->buffer; + uint32_t crc = (uint32_t)self->bit_size; + size_t size = self->buffer_size * sizeof(eword_t); + + while (size--) + crc = (crc << 5) - crc + (uint32_t)*p++; + + return crc; +} |