about summary refs log tree commit diff
path: root/third_party/git/ewah/ewah_bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/git/ewah/ewah_bitmap.c')
-rw-r--r--third_party/git/ewah/ewah_bitmap.c484
1 files changed, 0 insertions, 484 deletions
diff --git a/third_party/git/ewah/ewah_bitmap.c b/third_party/git/ewah/ewah_bitmap.c
deleted file mode 100644
index d59b1afe3d6a..000000000000
--- a/third_party/git/ewah/ewah_bitmap.c
+++ /dev/null
@@ -1,484 +0,0 @@
-/**
- * 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;
-}