bitarray.c   [plain text]

/*
 * Copyright (c) 1999, 2000, 2003, 2005, 2008, 2012 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */
//
//  bitarray.c
//  bitarray
//
//  Created by Bertrand Serlet on 9/26/10.
//  Copyright (c) 2010 Apple. All rights reserved.
//

#include "internal.h"

/******************************** Utilities ***************************/

#define STATIC_INLINE static __inline

STATIC_INLINE unsigned
__ffsll(uint64_t xx)
{
#if defined(__LP64__)
	return __builtin_ffsl(xx);
#else
	return __builtin_ffsll(xx);
#endif
}

#define BIT_SET(old, bit) ((old) | (1ULL << (bit)))
#define BIT_GET(old, bit) ((old) & (1ULL << (bit)))
#define BIT_ZAP(old, bit) ((old) & ~(1ULL << (bit)))

// several variants below of bit setting or zapping to generate minimal code
// All these do 1 memory read and (maybe) 1 memory write
STATIC_INLINE bool
word_get_bit_simple(uint64_t *word, unsigned bit)
{
	uint64_t old = *word;
	return BIT_GET(old, bit) != 0;
}

STATIC_INLINE void
word_set_bit_simple(uint64_t *word, unsigned bit)
{
	uint64_t old = *word;
	*word = BIT_SET(old, bit);
}

STATIC_INLINE bool
word_set_bit_changed(uint64_t *word, unsigned bit)
{
	// returns 1 iff word has changed
	uint64_t old = *word;
	uint64_t new = BIT_SET(old, bit);
	if (old == new) {
		return 0;
	}
	*word = new;
	return 1;
}

STATIC_INLINE bool
word_set_bit_changed_go_down(uint64_t *word, unsigned bit, bool *was_non_zero)
{
	// returns 1 iff word changed
	// sets was_non_zero (when something changed)
	uint64_t old = *word;
	uint64_t new = BIT_SET(old, bit);
	if (old == new) {
		return 0;
	}
	*word = new;
	*was_non_zero = old != 0;
	return 1;
}

STATIC_INLINE bool
word_set_bit_go_down(uint64_t *word, unsigned bit)
{
	// returns 1 iff level below should be set too
	uint64_t old = *word;
	uint64_t new = BIT_SET(old, bit);
	if (old == new) {
		return 0;
	}
	*word = new;
	return !old;
}

STATIC_INLINE void
word_zap_bit_simple(uint64_t *word, unsigned bit)
{
	uint64_t old = *word;
	*word = BIT_ZAP(old, bit);
}

STATIC_INLINE bool
word_zap_bit_changed(uint64_t *word, unsigned bit)
{
	// returns 1 iff word changed
	uint64_t old = *word;
	uint64_t new = BIT_ZAP(old, bit);
	if (old == new) {
		return 0;
	}
	*word = new;
	return 1;
}

STATIC_INLINE bool
word_zap_bit_changed_go_down(uint64_t *word, unsigned bit, bool *is_now_zero)
{
	// returns 1 iff word changed
	// sets is_now_zero (when something changed)
	uint64_t old = *word;
	uint64_t new = BIT_ZAP(old, bit);
	if (old == new) {
		return 0;
	}
	*word = new;
	*is_now_zero = !new;
	return 1;
}

STATIC_INLINE bool
word_zap_bit_go_down(uint64_t *word, unsigned bit)
{
	// returns 1 iff level below might require a bit-zeroing
	uint64_t old = *word;
	uint64_t new = BIT_ZAP(old, bit);
	if (old == new) {
		return 0;
	}
	*word = new;
	return !new;
}

/******************************** Helpers ***************************/

#define NB 9 // number of bits we process at once
// must be at least 6 (64-bit) and 9 seems the best on x86
#define MASKNB ((1 << NB) - 1)  // to just keep these bits
#define NUM_64b (1 << (NB - 6)) // number of 64-bit words we process at once

// number of uint64_t of summaries
#define LEVEL0 (NUM_64b)
#define LEVEL1 (LEVEL0 + (1 << NB) * NUM_64b)
#define LEVEL2 (LEVEL1 + (1 << (NB + NB)) * NUM_64b)
#define LEVEL3 (LEVEL2 + (1 << (NB + NB + NB)) * NUM_64b)

#define MAX_LEVEL 5

static const unsigned levels_num_words[] = {
		LEVEL0, LEVEL1, LEVEL2, LEVEL3}; // this encodes the number of words reserved for the bitmap summaries at various levels

STATIC_INLINE bool
GET_SIMPLE(uint64_t *word, unsigned bit)
{
	return word_get_bit_simple(word + (bit >> 6), bit & 63);
}

STATIC_INLINE void
SET_SIMPLE(uint64_t *word, unsigned bit)
{
	word_set_bit_simple(word + (bit >> 6), bit & 63);
}

STATIC_INLINE bool
SET_CHANGED(uint64_t *word, unsigned bit)
{
	// returns 1 iff word changed
	return word_set_bit_changed(word + (bit >> 6), bit & 63);
}

STATIC_INLINE bool
SET_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *was_non_zero)
{
	// returns 1 iff word changed
	// sets was_non_zero (when something changed)
	return word_set_bit_changed_go_down(word + (bit >> 6), bit & 63, was_non_zero);
}

STATIC_INLINE bool
SET_GO_DOWN(uint64_t *word, unsigned bit)
{
	// returns 1 iff level below should be set too
	return word_set_bit_go_down(word + (bit >> 6), bit & 63);
}

STATIC_INLINE void
ZAP_SIMPLE(uint64_t *word, unsigned bit)
{
	return word_zap_bit_simple(word + (bit >> 6), bit & 63);
}

STATIC_INLINE bool
ZAP_CHANGED(uint64_t *word, unsigned bit)
{
	// returns 1 iff word changed
	return word_zap_bit_changed(word + (bit >> 6), bit & 63);
}

STATIC_INLINE bool
all_zeros(uint64_t *words)
{
	for (unsigned w = 0; w < NUM_64b; w++) {
		if (words[w]) {
			return 0;
		}
	}
	return 1;
}

STATIC_INLINE bool
ZAP_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *is_now_zero)
{
	// returns 1 iff word changed
	// sets is_now_zero (when something changed)
	bool changed = word_zap_bit_changed_go_down(word + (bit >> 6), bit & 63, is_now_zero);
	if (changed && (NUM_64b != 1)) {
		// One component went entirely zero, now examine all components in the level
		if (!all_zeros(word)) {
			*is_now_zero = 0;
		}
	}
	return changed;
}

STATIC_INLINE bool
ZAP_GO_DOWN(uint64_t *word, unsigned bit)
{
	// returns 1 iff level below should be changed too
	bool changed = word_zap_bit_go_down(word + (bit >> 6), bit & 63);
	if (changed && (NUM_64b != 1)) {
		// One component went entirely zero, now examine all components in the level
		if (!all_zeros(word)) {
			return 0;
		}
	}
	return changed;
}

STATIC_INLINE unsigned
FFS(uint64_t *word)
{
// does NUM_64b memory reads, at most
#if NB == 6
	return __ffsll(*word);
#else
	for (unsigned w = 0; w < NUM_64b; w++) {
		unsigned f = __ffsll(word[w]);
		if (f) {
			return f + (w << 6);
		}
	}
	return 0;
#endif
}

/******************************** Entry Points ***************************/

size_t
bitarray_size(unsigned log_size)
{
	assert(log_size <= MAX_LEVEL * NB);
	unsigned num = NUM_64b;
	if (log_size > NB) {
		unsigned level = (log_size - NB - 1) / NB;
		num = levels_num_words[level] + (1 << (log_size - 6));
	}
	return num * sizeof(uint64_t);
}

bitarray_t
bitarray_create(unsigned log_size)
{
	return calloc(1, bitarray_size(log_size));
}

bool
bitarray_get(bitarray_t bits, unsigned log_size, index_t index)
{
	assert(log_size <= MAX_LEVEL * NB);
	assert(index < (1 << log_size));
	if (log_size <= NB) {
		return GET_SIMPLE(bits, index);
	}
	unsigned level = (log_size - NB - 1) / NB;
	unsigned bit;
	bit = index & MASKNB;
	index >>= NB;
	return GET_SIMPLE(bits + levels_num_words[level] + index * NUM_64b, bit);
}

bool
bitarray_set(bitarray_t bits, unsigned log_size, index_t index)
{
	// returns whether changed
	assert(log_size <= MAX_LEVEL * NB);
	assert(index < (1 << log_size));
	if (log_size <= NB) {
		return SET_CHANGED(bits, index);
	}
	unsigned level = (log_size - NB - 1) / NB;
	bool was_non_zero;
	unsigned bit;
	bit = index & MASKNB;
	index >>= NB;
	// printf("SET_CHANGED_GO_DOWN(bits + %d, %d,…)\n", levels_num_words[level] + index, bit);
	if (!SET_CHANGED_GO_DOWN(bits + levels_num_words[level] + index * NUM_64b, bit, &was_non_zero)) {
		return 0;
	}
	if (was_non_zero) {
		return 1;
	}
	switch (level) {
	case 3:
		bit = index & MASKNB;
		index >>= NB;
		if (!SET_GO_DOWN(bits + LEVEL2 + index * NUM_64b, bit)) {
			return 1;
		}
	/* no break */
	case 2:
		bit = index & MASKNB;
		index >>= NB;
		if (!SET_GO_DOWN(bits + LEVEL1 + index * NUM_64b, bit)) {
			return 1;
		}
	/* no break */
	case 1:
		bit = index & MASKNB;
		index >>= NB;
		if (!SET_GO_DOWN(bits + LEVEL0 + index * NUM_64b, bit)) {
			return 1;
		}
	/* no break */
	case 0:
		SET_SIMPLE(bits, index & MASKNB);
		return 1;
	default:
		MALLOC_FATAL_ERROR(level, "invalid bitarray level");
	}
}

bool
bitarray_zap(bitarray_t bits, unsigned log_size, index_t index)
{
	assert(log_size <= MAX_LEVEL * NB);
	assert(index < (1 << log_size));
	if (log_size <= NB) {
		return ZAP_CHANGED(bits, index);
	}
	unsigned level = (log_size - NB - 1) / NB;
	bool is_now_zero;
	unsigned bit;
	bit = index & MASKNB;
	index >>= NB;
	if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + index * NUM_64b, bit, &is_now_zero)) {
		return 0;
	}
	if (!is_now_zero) {
		return 1;
	}
	switch (level) {
	case 3:
		bit = index & MASKNB;
		index >>= NB;
		if (!ZAP_GO_DOWN(bits + LEVEL2 + index * NUM_64b, bit)) {
			return 1;
		}
	/* no break */
	case 2:
		bit = index & MASKNB;
		index >>= NB;
		if (!ZAP_GO_DOWN(bits + LEVEL1 + index * NUM_64b, bit)) {
			return 1;
		}
	/* no break */
	case 1:
		bit = index & MASKNB;
		index >>= NB;
		if (!ZAP_GO_DOWN(bits + LEVEL0 + index * NUM_64b, bit)) {
			return 1;
		}
	/* no break */
	case 0:
		ZAP_SIMPLE(bits, index & MASKNB);
		return 1;
	default:
		MALLOC_FATAL_ERROR(level, "invalid bitarray level");
	}
}

// Note in the following macro that "words" and "base" are variables being written
#define ADJUST_OFFSET_FOR_FFS(words, base, current_level)      \
	{                                                          \
		words += (1 << (NB * current_level)) * NUM_64b;        \
		base = (base << NB) + FFS(words + base * NUM_64b) - 1; \
	}

// Note in the following macro that "words" and "base" are variables being written
#define ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level) \
	{                                                              \
		switch (level) {                                           \
		case 4:                                                    \
			ADJUST_OFFSET_FOR_FFS(words, base, 0);                 \
			ADJUST_OFFSET_FOR_FFS(words, base, 1);                 \
			ADJUST_OFFSET_FOR_FFS(words, base, 2);                 \
			break;                                                 \
		case 3:                                                    \
			ADJUST_OFFSET_FOR_FFS(words, base, 0);                 \
			ADJUST_OFFSET_FOR_FFS(words, base, 1);                 \
			break;                                                 \
		case 2:                                                    \
			ADJUST_OFFSET_FOR_FFS(words, base, 0);                 \
			break;                                                 \
		case 1:                                                    \
			break;                                                 \
		default:                                                   \
			MALLOC_FATAL_ERROR(level, "invalid bitarray level");   \
		}                                                          \
	}

// Note in the following macro that "ix" and "bit" are variables being written
#define ZAP_SUMMARIES(bits, ix, level)                             \
	{                                                              \
		unsigned bit;                                              \
		switch (level) {                                           \
		case 3:                                                    \
			bit = ix & MASKNB;                                     \
			ix >>= NB;                                             \
			if (!ZAP_GO_DOWN(bits + LEVEL2 + ix * NUM_64b, bit)) { \
				break;                                             \
			}                                                      \
		case 2:                                                    \
			bit = ix & MASKNB;                                     \
			ix >>= NB;                                             \
			if (!ZAP_GO_DOWN(bits + LEVEL1 + ix * NUM_64b, bit)) { \
				break;                                             \
			}                                                      \
		case 1:                                                    \
			bit = ix & MASKNB;                                     \
			ix >>= NB;                                             \
			if (!ZAP_GO_DOWN(bits + LEVEL0 + ix * NUM_64b, bit)) { \
				break;                                             \
			}                                                      \
		case 0:                                                    \
			ZAP_SIMPLE(bits, ix &MASKNB);                          \
			break;                                                 \
		default:                                                   \
			MALLOC_FATAL_ERROR(level, "invalid bitarray level");   \
		}                                                          \
	}

index_t
bitarray_first_set(const bitarray_t bits, unsigned log_size)
{
	// return 0 if none set
	assert(log_size <= MAX_LEVEL * NB);
	uint64_t *words = bits;
	unsigned bit = FFS(words);
	if (log_size <= NB) {
		return bit;
	}
	if (!bit) {
		return 0;
	}
	unsigned level = (log_size - 1) / NB;
	index_t base = bit - 1; // offset, in number of uin64_t words
	ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
	words += (1 << (NB * (level - 1))) * NUM_64b;
	base = (base << NB) + FFS(words + base * NUM_64b) - 1;
	return base + 1; //+1 because bit N is encoded as N+1
}

bool
bitarray_zap_first_set(bitarray_t bits, unsigned log_size, index_t *index)
{
	assert(log_size <= MAX_LEVEL * NB);
	uint64_t *words = bits;
	index_t ix = FFS(words);
	if (!ix) {
		return 0;
	}
	unsigned level = (log_size - 1) / NB;
	if (!level) {
		ix--;
		*index = ix;
		ZAP_SIMPLE(bits, ix);
		return 1;
	}
	index_t base = ix - 1; // offset, in number of uin64_t words
	ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
	words += (1 << (NB * (level - 1))) * NUM_64b;
	base = (base << NB) + FFS(words + base * NUM_64b) - 1;
	ix = base;
	*index = ix;
	assert(ix < (1 << log_size));
	level--;
	bool is_now_zero;
	unsigned bit;
	bit = ix & MASKNB;
	ix >>= NB;
	if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + ix * NUM_64b, bit, &is_now_zero)) {
		return 1;
	}
	if (!is_now_zero) {
		return 1;
	}
	ZAP_SUMMARIES(bits, ix, level);
	return 1;
}

static unsigned
FFS_and_zap_word(uint64_t *words, unsigned max, index_t *indices, index_t to_be_added)
{
	// returns the number of bits zapped
	unsigned zapped = 0;
	for (unsigned w = 0; w < NUM_64b; w++) {
		uint64_t word = words[w];
		if (!word) {
			continue;
		}
		while (1) {
			unsigned f = __ffsll(word);
			assert(f);
			f--;
			// printf("%d ", f);
			indices[zapped++] = f + (w << 6) + to_be_added;
			word = BIT_ZAP(word, f);
			if (!word) {
				break;
			}
			if (zapped >= max) {
				break;
			}
		}
		words[w] = word;
		// printf("word=%lld \n", word);
		if (zapped >= max) {
			break;
		}
	}
	return zapped;
}

unsigned
bitarray_zap_first_set_multiple(bitarray_t bits, unsigned log_size, unsigned max, index_t *indices)
{
	assert(log_size <= MAX_LEVEL * NB);
	if (log_size <= NB) {
		return FFS_and_zap_word(bits, max, indices, 0);
	}
	unsigned zapped = 0;
	unsigned level = (log_size - 1) / NB;
	while (zapped < max) {
		/*
		 * the lines in loop could be written just as:
		 *		if (! bitarray_zap_first_set(bits, log_size, indices + zapped)) break;
		 *			zapped++;
		 * but the code is faster because it wont go up and down in the summaries
		 */
		uint64_t *words = bits;
		index_t ix = FFS(words);
		if (!ix) {
			return zapped; // if the top level summary is 0, no bit is set
		}
		index_t base = ix - 1; // offset, in number of uin64_t words
		ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
		words += (1 << (NB * (level - 1))) * NUM_64b; // the beginning of the non-summarized bitarray
		uint64_t *word = words + base * NUM_64b;	  // the first non-zero word
		ix = base;
		// the idea here is that we zap a whole bunch of bits at once
		unsigned z = FFS_and_zap_word(word, max - zapped, indices + zapped, base << NB);
		assert(z);
		zapped += z;
		if ((zapped < max) /* entire word was zapped */ || all_zeros(word) /* partial zap, a priori */) {
			// adjust summaries to reflect all zeros in the bitarray
			ZAP_SUMMARIES(bits, ix, level - 1);
		}
	}
	return zapped;
}

#if 0
/******************************** Test and debug utilities ***************************/

static void print_ones(const uint64_t *bits, unsigned num_big_words) {
	unsigned base = 0;
	unsigned num = num_big_words * NUM_64b;
	// printf("In print_ones; num=%d, num_big=%d \n", num, num_big_words);
	while (num--) {
		uint64_t word = *(bits++);
		if (word) {
			for (unsigned bit = 0; bit < 64; bit++) {
				if (word & (1ULL << bit)) { printf("%d ", base + bit); }
			}
		}
		base += 64;
	}
}

void bitarray_print(bitarray_t bits, unsigned log_size) {
	assert(log_size <= MAX_LEVEL * NB);
	printf("bitarray %p log_size=%d\n", bits, log_size);
	if (log_size > 4 * NB) {
		printf("Level 4: "); print_ones(bits, 1); printf("\n");
		printf("Level 3: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
		printf("Level 2: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n");
		printf("Level 1: "); print_ones(bits + LEVEL2, 1 << NB); printf("\n");
		printf("Level 0: "); print_ones(bits + LEVEL3, 1 << (log_size - NB)); printf("\n");
	} else if (log_size > 3 * NB) {
		printf("Level 3: "); print_ones(bits, 1); printf("\n");
		printf("Level 2: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
		printf("Level 1: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n");
		printf("Level 0: "); print_ones(bits + LEVEL2, 1 << (log_size - NB)); printf("\n");
	} else if (log_size > 2 * NB) {
		printf("Level 2: "); print_ones(bits, 1); printf("\n");
		printf("Level 1: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
		printf("Level 0: "); print_ones(bits + LEVEL1, 1 << (log_size - NB)); printf("\n");
	} else if (log_size > NB) {
		printf("Level 1: "); print_ones(bits, 1); printf("\n");
		printf("Level 0: "); print_ones(bits + LEVEL0, 1 << (log_size - NB)); printf("\n");
	} else {
		printf("Level 0: "); print_ones(bits, 1); printf("\n");
	}
}

bool compare_to_truth(bitarray_t bits, unsigned nbits, const bool *truth) {
	uint64_t     *start = bits;
	if (nbits > NB) {
		unsigned level = (nbits - NB - 1) / NB;
		start += levels_num_words[level];
	}
	bool ok = 1;
	for (unsigned bit = 0; bit < (1 << nbits); bit++) {
		bool expected = truth[bit];
		uint64_t word = start[bit >> 6];
		bool actual = (word >> (bit & 63)) & 1;
		if (actual != expected) {
			printf("*** # for bit %d, expected=%d actual=%d\n", bit, expected, actual);
			ok = 0;
		}
	}
	return ok;
}

unsigned first_set_in_truth(const bool *truth, unsigned log_size) {
	for (unsigned bit = 0; bit < (1 << log_size); bit++) {
		if (truth[bit]) { return bit + 1; }
	}
	return 0;
}

void truth_print(const bool *truth, unsigned log_size) {
	printf("Truth:  ");
	for (unsigned bit = 0; bit < (1 << log_size); bit++) {
		if (truth[bit]) { printf("%d ", bit); }
	}
	printf("\n");
}
#endif

/* vim: set noet:ts=4:sw=4:cindent: */