[thirdparty/git.git] / ewah / ewah_bitmap.c

/**
 * 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, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */
#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 =
		(i + BITS_IN_EWORD) / BITS_IN_EWORD -
		(self->bit_size + BITS_IN_EWORD - 1) / 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;
}
Commit	Line	Data
e1273106 VM	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;
08c95df8	42	REALLOC_ARRAY(self->buffer, self->alloc_size);
68f4e1fc	43	self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
e1273106 VM	44	}
	45
	46	static inline void buffer_push(struct ewah_bitmap *self, eword_t value)
	47	{
	48	if (self->buffer_size + 1 >= self->alloc_size)
	49	buffer_grow(self, self->buffer_size * 3 / 2);
	50
	51	self->buffer[self->buffer_size++] = value;
	52	}
	53
	54	static void buffer_push_rlw(struct ewah_bitmap *self, eword_t value)
	55	{
	56	buffer_push(self, value);
	57	self->rlw = self->buffer + self->buffer_size - 1;
	58	}
	59
	60	static size_t add_empty_words(struct ewah_bitmap *self, int v, size_t number)
	61	{
	62	size_t added = 0;
	63	eword_t runlen, can_add;
	64
	65	if (rlw_get_run_bit(self->rlw) != v && rlw_size(self->rlw) == 0) {
	66	rlw_set_run_bit(self->rlw, v);
	67	} else if (rlw_get_literal_words(self->rlw) != 0 \|\|
	68	rlw_get_run_bit(self->rlw) != v) {
	69	buffer_push_rlw(self, 0);
	70	if (v) rlw_set_run_bit(self->rlw, v);
	71	added++;
	72	}
	73
	74	runlen = rlw_get_running_len(self->rlw);
	75	can_add = min_size(number, RLW_LARGEST_RUNNING_COUNT - runlen);
	76
	77	rlw_set_running_len(self->rlw, runlen + can_add);
	78	number -= can_add;
	79
	80	while (number >= RLW_LARGEST_RUNNING_COUNT) {
	81	buffer_push_rlw(self, 0);
	82	added++;
	83	if (v) rlw_set_run_bit(self->rlw, v);
	84	rlw_set_running_len(self->rlw, RLW_LARGEST_RUNNING_COUNT);
	85	number -= RLW_LARGEST_RUNNING_COUNT;
	86	}
	87
	88	if (number > 0) {
	89	buffer_push_rlw(self, 0);
	90	added++;
	91
	92	if (v) rlw_set_run_bit(self->rlw, v);
	93	rlw_set_running_len(self->rlw, number);
	94	}
	95
	96	return added;
	97	}
	98
	99	size_t ewah_add_empty_words(struct ewah_bitmap *self, int v, size_t number)
	100	{
	101	if (number == 0)
	102	return 0;
	103
34b935c0	104	self->bit_size += number * BITS_IN_EWORD;
e1273106 VM	105	return add_empty_words(self, v, number);
	106	}
	107
	108	static size_t add_literal(struct ewah_bitmap *self, eword_t new_data)
	109	{
	110	eword_t current_num = rlw_get_literal_words(self->rlw);
	111
	112	if (current_num >= RLW_LARGEST_LITERAL_COUNT) {
	113	buffer_push_rlw(self, 0);
	114
	115	rlw_set_literal_words(self->rlw, 1);
	116	buffer_push(self, new_data);
	117	return 2;
	118	}
	119
	120	rlw_set_literal_words(self->rlw, current_num + 1);
	121
	122	/* sanity check */
	123	assert(rlw_get_literal_words(self->rlw) == current_num + 1);
	124
	125	buffer_push(self, new_data);
	126	return 1;
	127	}
	128
	129	void ewah_add_dirty_words(
	130	struct ewah_bitmap self, const eword_t buffer,
	131	size_t number, int negate)
	132	{
	133	size_t literals, can_add;
	134
	135	while (1) {
	136	literals = rlw_get_literal_words(self->rlw);
	137	can_add = min_size(number, RLW_LARGEST_LITERAL_COUNT - literals);
	138
	139	rlw_set_literal_words(self->rlw, literals + can_add);
	140
	141	if (self->buffer_size + can_add >= self->alloc_size)
	142	buffer_grow(self, (self->buffer_size + can_add) * 3 / 2);
	143
	144	if (negate) {
	145	size_t i;
	146	for (i = 0; i < can_add; ++i)
	147	self->buffer[self->buffer_size++] = ~buffer[i];
	148	} else {
	149	memcpy(self->buffer + self->buffer_size,
	150	buffer, can_add * sizeof(eword_t));
	151	self->buffer_size += can_add;
	152	}
	153
34b935c0	154	self->bit_size += can_add * BITS_IN_EWORD;
e1273106 VM	155
	156	if (number - can_add == 0)
	157	break;
	158
	159	buffer_push_rlw(self, 0);
	160	buffer += can_add;
	161	number -= can_add;
	162	}
	163	}
	164
	165	static size_t add_empty_word(struct ewah_bitmap *self, int v)
	166	{
	167	int no_literal = (rlw_get_literal_words(self->rlw) == 0);
	168	eword_t run_len = rlw_get_running_len(self->rlw);
	169
	170	if (no_literal && run_len == 0) {
	171	rlw_set_run_bit(self->rlw, v);
	172	assert(rlw_get_run_bit(self->rlw) == v);
	173	}
	174
	175	if (no_literal && rlw_get_run_bit(self->rlw) == v &&
	176	run_len < RLW_LARGEST_RUNNING_COUNT) {
	177	rlw_set_running_len(self->rlw, run_len + 1);
	178	assert(rlw_get_running_len(self->rlw) == run_len + 1);
	179	return 0;
	180	} else {
	181	buffer_push_rlw(self, 0);
	182
	183	assert(rlw_get_running_len(self->rlw) == 0);
	184	assert(rlw_get_run_bit(self->rlw) == 0);
	185	assert(rlw_get_literal_words(self->rlw) == 0);
	186
	187	rlw_set_run_bit(self->rlw, v);
	188	assert(rlw_get_run_bit(self->rlw) == v);
	189
	190	rlw_set_running_len(self->rlw, 1);
	191	assert(rlw_get_running_len(self->rlw) == 1);
	192	assert(rlw_get_literal_words(self->rlw) == 0);
	193	return 1;
	194	}
	195	}
	196
	197	size_t ewah_add(struct ewah_bitmap *self, eword_t word)
	198	{
34b935c0	199	self->bit_size += BITS_IN_EWORD;
e1273106 VM	200
	201	if (word == 0)
	202	return add_empty_word(self, 0);
	203
	204	if (word == (eword_t)(~0))
	205	return add_empty_word(self, 1);
	206
	207	return add_literal(self, word);
	208	}
	209
	210	void ewah_set(struct ewah_bitmap *self, size_t i)
	211	{
	212	const size_t dist =
34b935c0 JK	213	(i + BITS_IN_EWORD) / BITS_IN_EWORD -
34b935c0 JK	214	(self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
e1273106 VM	215
	216	assert(i >= self->bit_size);
	217
	218	self->bit_size = i + 1;
	219
	220	if (dist > 0) {
	221	if (dist > 1)
	222	add_empty_words(self, 0, dist - 1);
	223
34b935c0	224	add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD));
e1273106 VM	225	return;
	226	}
	227
	228	if (rlw_get_literal_words(self->rlw) == 0) {
	229	rlw_set_running_len(self->rlw,
	230	rlw_get_running_len(self->rlw) - 1);
34b935c0	231	add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD));
e1273106 VM	232	return;
	233	}
	234
	235	self->buffer[self->buffer_size - 1] \|=
34b935c0	236	((eword_t)1 << (i % BITS_IN_EWORD));
e1273106 VM	237
	238	/* check if we just completed a stream of 1s */
	239	if (self->buffer[self->buffer_size - 1] == (eword_t)(~0)) {
	240	self->buffer[--self->buffer_size] = 0;
	241	rlw_set_literal_words(self->rlw,
	242	rlw_get_literal_words(self->rlw) - 1);
	243	add_empty_word(self, 1);
	244	}
	245	}
	246
	247	void ewah_each_bit(struct ewah_bitmap self, void (callback)(size_t, void), void payload)
	248	{
	249	size_t pos = 0;
	250	size_t pointer = 0;
	251	size_t k;
	252
	253	while (pointer < self->buffer_size) {
	254	eword_t *word = &self->buffer[pointer];
	255
	256	if (rlw_get_run_bit(word)) {
34b935c0	257	size_t len = rlw_get_running_len(word) * BITS_IN_EWORD;
e1273106 VM	258	for (k = 0; k < len; ++k, ++pos)
	259	callback(pos, payload);
	260	} else {
34b935c0	261	pos += rlw_get_running_len(word) * BITS_IN_EWORD;
e1273106 VM	262	}
	263
	264	++pointer;
	265
	266	for (k = 0; k < rlw_get_literal_words(word); ++k) {
	267	int c;
	268
	269	/* todo: zero count optimization */
34b935c0	270	for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
e1273106 VM	271	if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)
	272	callback(pos, payload);
	273	}
	274
	275	++pointer;
	276	}
	277	}
	278	}
	279
	280	struct ewah_bitmap *ewah_new(void)
	281	{
	282	struct ewah_bitmap *self;
	283
fb7dbf3e	284	self = xmalloc(sizeof(struct ewah_bitmap));
e1273106	285	self->alloc_size = 32;
08c95df8	286	ALLOC_ARRAY(self->buffer, self->alloc_size);
e1273106 VM	287
	288	ewah_clear(self);
	289	return self;
	290	}
	291
	292	void ewah_clear(struct ewah_bitmap *self)
	293	{
	294	self->buffer_size = 1;
	295	self->buffer[0] = 0;
	296	self->bit_size = 0;
	297	self->rlw = self->buffer;
	298	}
	299
	300	void ewah_free(struct ewah_bitmap *self)
	301	{
	302	if (!self)
	303	return;
	304
	305	if (self->alloc_size)
	306	free(self->buffer);
	307
	308	free(self);
	309	}
	310
	311	static void read_new_rlw(struct ewah_iterator *it)
	312	{
	313	const eword_t *word = NULL;
	314
	315	it->literals = 0;
	316	it->compressed = 0;
	317
	318	while (1) {
	319	word = &it->buffer[it->pointer];
	320
	321	it->rl = rlw_get_running_len(word);
	322	it->lw = rlw_get_literal_words(word);
	323	it->b = rlw_get_run_bit(word);
	324
	325	if (it->rl \|\| it->lw)
	326	return;
	327
	328	if (it->pointer < it->buffer_size - 1) {
	329	it->pointer++;
	330	} else {
	331	it->pointer = it->buffer_size;
	332	return;
	333	}
	334	}
	335	}
	336
	337	int ewah_iterator_next(eword_t next, struct ewah_iterator it)
	338	{
	339	if (it->pointer >= it->buffer_size)
	340	return 0;
	341
	342	if (it->compressed < it->rl) {
	343	it->compressed++;
	344	*next = it->b ? (eword_t)(~0) : 0;
	345	} else {
	346	assert(it->literals < it->lw);
	347
	348	it->literals++;
	349	it->pointer++;
	350
351	assert(it->pointer < it->buffer_size);
352
353	*next = it->buffer[it->pointer];
354	}
355
356	if (it->compressed == it->rl && it->literals == it->lw) {
357	if (++it->pointer < it->buffer_size)
358	read_new_rlw(it);
359	}
360
361	return 1;
362	}
363
364	void ewah_iterator_init(struct ewah_iterator it, struct ewah_bitmap parent)
365	{
366	it->buffer = parent->buffer;
367	it->buffer_size = parent->buffer_size;
368	it->pointer = 0;
369
370	it->lw = 0;
371	it->rl = 0;
372	it->compressed = 0;
373	it->literals = 0;
374	it->b = 0;
375
376	if (it->pointer < it->buffer_size)
377	read_new_rlw(it);
378	}
379
380	void ewah_not(struct ewah_bitmap *self)
381	{
382	size_t pointer = 0;
383
384	while (pointer < self->buffer_size) {
385	eword_t *word = &self->buffer[pointer];
386	size_t literals, k;
387
388	rlw_xor_run_bit(word);
389	++pointer;
390
391	literals = rlw_get_literal_words(word);
392	for (k = 0; k < literals; ++k) {
393	self->buffer[pointer] = ~self->buffer[pointer];
394	++pointer;
395	}
396	}
397	}
398
399	void ewah_xor(
400	struct ewah_bitmap *ewah_i,
401	struct ewah_bitmap *ewah_j,
402	struct ewah_bitmap *out)
403	{
404	struct rlw_iterator rlw_i;
405	struct rlw_iterator rlw_j;
406	size_t literals;
407
408	rlwit_init(&rlw_i, ewah_i);
409	rlwit_init(&rlw_j, ewah_j);
410
411	while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
412	while (rlw_i.rlw.running_len > 0 \|\| rlw_j.rlw.running_len > 0) {
413	struct rlw_iterator prey, predator;
414	size_t index;
415	int negate_words;
416
417	if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
418	prey = &rlw_i;
419	predator = &rlw_j;
420	} else {
421	prey = &rlw_j;
422	predator = &rlw_i;
423	}
424
425	negate_words = !!predator->rlw.running_bit;
426	index = rlwit_discharge(prey, out,
427	predator->rlw.running_len, negate_words);
428
429	ewah_add_empty_words(out, negate_words,
430	predator->rlw.running_len - index);
431
432	rlwit_discard_first_words(predator,
433	predator->rlw.running_len);
434	}
435
436	literals = min_size(
437	rlw_i.rlw.literal_words,
438	rlw_j.rlw.literal_words);
439
440	if (literals) {
441	size_t k;
442
443	for (k = 0; k < literals; ++k) {
444	ewah_add(out,
445	rlw_i.buffer[rlw_i.literal_word_start + k] ^
446	rlw_j.buffer[rlw_j.literal_word_start + k]
447	);
448	}
449
450	rlwit_discard_first_words(&rlw_i, literals);
451	rlwit_discard_first_words(&rlw_j, literals);
452	}
453	}
454
455	if (rlwit_word_size(&rlw_i) > 0)
456	rlwit_discharge(&rlw_i, out, ~0, 0);
457	else
458	rlwit_discharge(&rlw_j, out, ~0, 0);
459
460	out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
461	}
462
463	void ewah_and(
464	struct ewah_bitmap *ewah_i,
465	struct ewah_bitmap *ewah_j,
466	struct ewah_bitmap *out)
467	{
468	struct rlw_iterator rlw_i;
469	struct rlw_iterator rlw_j;
470	size_t literals;
471
472	rlwit_init(&rlw_i, ewah_i);
473	rlwit_init(&rlw_j, ewah_j);
474
475	while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
476	while (rlw_i.rlw.running_len > 0 \|\| rlw_j.rlw.running_len > 0) {
477	struct rlw_iterator prey, predator;
478
479	if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
480	prey = &rlw_i;
481	predator = &rlw_j;
482	} else {
483	prey = &rlw_j;
484	predator = &rlw_i;
485	}
486
487	if (predator->rlw.running_bit == 0) {
488	ewah_add_empty_words(out, 0,
489	predator->rlw.running_len);
490	rlwit_discard_first_words(prey,
491	predator->rlw.running_len);
492	rlwit_discard_first_words(predator,
493	predator->rlw.running_len);
494	} else {
495	size_t index = rlwit_discharge(prey, out,
496	predator->rlw.running_len, 0);
497	ewah_add_empty_words(out, 0,
498	predator->rlw.running_len - index);
499	rlwit_discard_first_words(predator,
500	predator->rlw.running_len);
501	}
502	}
503
504	literals = min_size(
505	rlw_i.rlw.literal_words,
506	rlw_j.rlw.literal_words);
507
508	if (literals) {
509	size_t k;
510
511	for (k = 0; k < literals; ++k) {
512	ewah_add(out,
513	rlw_i.buffer[rlw_i.literal_word_start + k] &
514	rlw_j.buffer[rlw_j.literal_word_start + k]
515	);
516	}
517
518	rlwit_discard_first_words(&rlw_i, literals);
519	rlwit_discard_first_words(&rlw_j, literals);
520	}
521	}
522
523	if (rlwit_word_size(&rlw_i) > 0)
524	rlwit_discharge_empty(&rlw_i, out);
525	else
526	rlwit_discharge_empty(&rlw_j, out);
527
528	out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
529	}
530
531	void ewah_and_not(
532	struct ewah_bitmap *ewah_i,
533	struct ewah_bitmap *ewah_j,
534	struct ewah_bitmap *out)
535	{
536	struct rlw_iterator rlw_i;
537	struct rlw_iterator rlw_j;
538	size_t literals;
539
540	rlwit_init(&rlw_i, ewah_i);
541	rlwit_init(&rlw_j, ewah_j);
542
543	while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
544	while (rlw_i.rlw.running_len > 0 \|\| rlw_j.rlw.running_len > 0) {
545	struct rlw_iterator prey, predator;
546
547	if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
548	prey = &rlw_i;
549	predator = &rlw_j;
550	} else {
551	prey = &rlw_j;
552	predator = &rlw_i;
553	}
554
555	if ((predator->rlw.running_bit && prey == &rlw_i) \|\|
556	(!predator->rlw.running_bit && prey != &rlw_i)) {
557	ewah_add_empty_words(out, 0,
558	predator->rlw.running_len);
559	rlwit_discard_first_words(prey,
560	predator->rlw.running_len);
561	rlwit_discard_first_words(predator,
562	predator->rlw.running_len);
563	} else {
564	size_t index;
565	int negate_words;
566
567	negate_words = (&rlw_i != prey);
568	index = rlwit_discharge(prey, out,
569	predator->rlw.running_len, negate_words);
570	ewah_add_empty_words(out, negate_words,
571	predator->rlw.running_len - index);
572	rlwit_discard_first_words(predator,
573	predator->rlw.running_len);
574	}
575	}
576
577	literals = min_size(
578	rlw_i.rlw.literal_words,
579	rlw_j.rlw.literal_words);
580
581	if (literals) {
582	size_t k;
583
584	for (k = 0; k < literals; ++k) {
585	ewah_add(out,
586	rlw_i.buffer[rlw_i.literal_word_start + k] &
587	~(rlw_j.buffer[rlw_j.literal_word_start + k])
588	);
589	}
590
591	rlwit_discard_first_words(&rlw_i, literals);
592	rlwit_discard_first_words(&rlw_j, literals);
593	}
594	}
595
596	if (rlwit_word_size(&rlw_i) > 0)
597	rlwit_discharge(&rlw_i, out, ~0, 0);
598	else
599	rlwit_discharge_empty(&rlw_j, out);
600
601	out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
602	}
603
604	void ewah_or(
605	struct ewah_bitmap *ewah_i,
606	struct ewah_bitmap *ewah_j,
607	struct ewah_bitmap *out)
608	{
609	struct rlw_iterator rlw_i;
610	struct rlw_iterator rlw_j;
611	size_t literals;
612
613	rlwit_init(&rlw_i, ewah_i);
614	rlwit_init(&rlw_j, ewah_j);
615
616	while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
617	while (rlw_i.rlw.running_len > 0 \|\| rlw_j.rlw.running_len > 0) {
618	struct rlw_iterator prey, predator;
619
620	if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
621	prey = &rlw_i;
622	predator = &rlw_j;
623	} else {
624	prey = &rlw_j;
625	predator = &rlw_i;
626	}
627
628	if (predator->rlw.running_bit) {
629	ewah_add_empty_words(out, 0,
630	predator->rlw.running_len);
631	rlwit_discard_first_words(prey,
632	predator->rlw.running_len);
633	rlwit_discard_first_words(predator,
634	predator->rlw.running_len);
635	} else {
636	size_t index = rlwit_discharge(prey, out,
637	predator->rlw.running_len, 0);
638	ewah_add_empty_words(out, 0,
639	predator->rlw.running_len - index);
640	rlwit_discard_first_words(predator,
641	predator->rlw.running_len);
642	}
643	}
644
645	literals = min_size(
646	rlw_i.rlw.literal_words,
647	rlw_j.rlw.literal_words);
648
649	if (literals) {
650	size_t k;
651
652	for (k = 0; k < literals; ++k) {
653	ewah_add(out,
654	rlw_i.buffer[rlw_i.literal_word_start + k] \|
655	rlw_j.buffer[rlw_j.literal_word_start + k]
656	);
657	}
658
659	rlwit_discard_first_words(&rlw_i, literals);
660	rlwit_discard_first_words(&rlw_j, literals);
661	}
662	}
663
664	if (rlwit_word_size(&rlw_i) > 0)
665	rlwit_discharge(&rlw_i, out, ~0, 0);
666	else
667	rlwit_discharge(&rlw_j, out, ~0, 0);
668
669	out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
670	}
671
672
673	#define BITMAP_POOL_MAX 16
674	static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
675	static size_t bitmap_pool_size;
676
677	struct ewah_bitmap *ewah_pool_new(void)
678	{
679	if (bitmap_pool_size)
680	return bitmap_pool[--bitmap_pool_size];
681
682	return ewah_new();
683	}
684
685	void ewah_pool_free(struct ewah_bitmap *self)
686	{
687	if (self == NULL)
688	return;
689
690	if (bitmap_pool_size == BITMAP_POOL_MAX \|\|
691	self->alloc_size == 0) {
692	ewah_free(self);
693	return;
694	}
695
696	ewah_clear(self);
697	bitmap_pool[bitmap_pool_size++] = self;
698	}
699
700	uint32_t ewah_checksum(struct ewah_bitmap *self)
701	{
702	const uint8_t p = (uint8_t )self->buffer;
703	uint32_t crc = (uint32_t)self->bit_size;
704	size_t size = self->buffer_size * sizeof(eword_t);
705
706	while (size--)
707	crc = (crc << 5) - crc + (uint32_t)*p++;
708
709	return crc;
710	}