| /** |
| * 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; |
| } |
| } |
| } |
| |
| 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_clear(struct ewah_bitmap *self) |
| { |
| self->buffer_size = 1; |
| self->buffer[0] = 0; |
| self->bit_size = 0; |
| self->rlw = self->buffer; |
| } |
| |
| 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_not(struct ewah_bitmap *self) |
| { |
| size_t pointer = 0; |
| |
| while (pointer < self->buffer_size) { |
| eword_t *word = &self->buffer[pointer]; |
| size_t literals, k; |
| |
| rlw_xor_run_bit(word); |
| ++pointer; |
| |
| literals = rlw_get_literal_words(word); |
| for (k = 0; k < literals; ++k) { |
| self->buffer[pointer] = ~self->buffer[pointer]; |
| ++pointer; |
| } |
| } |
| } |
| |
| 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); |
| } |
| |
| void ewah_and( |
| 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; |
| |
| if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { |
| prey = &rlw_i; |
| predator = &rlw_j; |
| } else { |
| prey = &rlw_j; |
| predator = &rlw_i; |
| } |
| |
| if (predator->rlw.running_bit == 0) { |
| ewah_add_empty_words(out, 0, |
| predator->rlw.running_len); |
| rlwit_discard_first_words(prey, |
| predator->rlw.running_len); |
| rlwit_discard_first_words(predator, |
| predator->rlw.running_len); |
| } else { |
| size_t index = rlwit_discharge(prey, out, |
| predator->rlw.running_len, 0); |
| ewah_add_empty_words(out, 0, |
| 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_empty(&rlw_i, out); |
| else |
| rlwit_discharge_empty(&rlw_j, out); |
| |
| out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size); |
| } |
| |
| void ewah_and_not( |
| 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; |
| |
| if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { |
| prey = &rlw_i; |
| predator = &rlw_j; |
| } else { |
| prey = &rlw_j; |
| predator = &rlw_i; |
| } |
| |
| if ((predator->rlw.running_bit && prey == &rlw_i) || |
| (!predator->rlw.running_bit && prey != &rlw_i)) { |
| ewah_add_empty_words(out, 0, |
| predator->rlw.running_len); |
| rlwit_discard_first_words(prey, |
| predator->rlw.running_len); |
| rlwit_discard_first_words(predator, |
| predator->rlw.running_len); |
| } else { |
| size_t index; |
| int negate_words; |
| |
| negate_words = (&rlw_i != prey); |
| 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_empty(&rlw_j, out); |
| |
| out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size); |
| } |
| |
| void ewah_or( |
| 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; |
| |
| if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { |
| prey = &rlw_i; |
| predator = &rlw_j; |
| } else { |
| prey = &rlw_j; |
| predator = &rlw_i; |
| } |
| |
| if (predator->rlw.running_bit) { |
| ewah_add_empty_words(out, 0, |
| predator->rlw.running_len); |
| rlwit_discard_first_words(prey, |
| predator->rlw.running_len); |
| rlwit_discard_first_words(predator, |
| predator->rlw.running_len); |
| } else { |
| size_t index = rlwit_discharge(prey, out, |
| predator->rlw.running_len, 0); |
| ewah_add_empty_words(out, 0, |
| 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; |
| } |