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#ifndef __EWOK_BITMAP_H__ 21#define __EWOK_BITMAP_H__ 22 23#ifndef ewah_malloc 24# define ewah_malloc xmalloc 25#endif 26#ifndef ewah_realloc 27# define ewah_realloc xrealloc 28#endif 29#ifndef ewah_calloc 30# define ewah_calloc xcalloc 31#endif 32 33struct strbuf; 34typedef uint64_t eword_t; 35#define BITS_IN_EWORD (sizeof(eword_t) * 8) 36 37/** 38 * Do not use __builtin_popcountll. The GCC implementation 39 * is notoriously slow on all platforms. 40 * 41 * See: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36041 42 */ 43static inline uint32_t ewah_bit_popcount64(uint64_t x) 44{ 45 x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL); 46 x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL); 47 x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL); 48 return (x * 0x0101010101010101ULL) >> 56; 49} 50 51/* __builtin_ctzll was not available until 3.4.0 */ 52#if defined(__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR > 3)) 53#define ewah_bit_ctz64(x) __builtin_ctzll(x) 54#else 55static inline int ewah_bit_ctz64(uint64_t x) 56{ 57 int n = 0; 58 if ((x & 0xffffffff) == 0) { x >>= 32; n += 32; } 59 if ((x & 0xffff) == 0) { x >>= 16; n += 16; } 60 if ((x & 0xff) == 0) { x >>= 8; n += 8; } 61 if ((x & 0xf) == 0) { x >>= 4; n += 4; } 62 if ((x & 0x3) == 0) { x >>= 2; n += 2; } 63 if ((x & 0x1) == 0) { x >>= 1; n += 1; } 64 return n + !x; 65} 66#endif 67 68struct ewah_bitmap { 69 eword_t *buffer; 70 size_t buffer_size; 71 size_t alloc_size; 72 size_t bit_size; 73 eword_t *rlw; 74}; 75 76typedef void (*ewah_callback)(size_t pos, void *); 77 78struct ewah_bitmap *ewah_pool_new(void); 79void ewah_pool_free(struct ewah_bitmap *self); 80 81/** 82 * Allocate a new EWAH Compressed bitmap 83 */ 84struct ewah_bitmap *ewah_new(void); 85 86/** 87 * Clear all the bits in the bitmap. Does not free or resize 88 * memory. 89 */ 90void ewah_clear(struct ewah_bitmap *self); 91 92/** 93 * Free all the memory of the bitmap 94 */ 95void ewah_free(struct ewah_bitmap *self); 96 97int ewah_serialize_to(struct ewah_bitmap *self, 98 int (*write_fun)(void *out, const void *buf, size_t len), 99 void *out); 100int ewah_serialize(struct ewah_bitmap *self, int fd); 101int ewah_serialize_native(struct ewah_bitmap *self, int fd); 102int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *); 103 104int ewah_deserialize(struct ewah_bitmap *self, int fd); 105int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len); 106 107uint32_t ewah_checksum(struct ewah_bitmap *self); 108 109/** 110 * Logical not (bitwise negation) in-place on the bitmap 111 * 112 * This operation is linear time based on the size of the bitmap. 113 */ 114void ewah_not(struct ewah_bitmap *self); 115 116/** 117 * Call the given callback with the position of every single bit 118 * that has been set on the bitmap. 119 * 120 * This is an efficient operation that does not fully decompress 121 * the bitmap. 122 */ 123void ewah_each_bit(struct ewah_bitmap *self, ewah_callback callback, void *payload); 124 125/** 126 * Set a given bit on the bitmap. 127 * 128 * The bit at position `pos` will be set to true. Because of the 129 * way that the bitmap is compressed, a set bit cannot be unset 130 * later on. 131 * 132 * Furthermore, since the bitmap uses streaming compression, bits 133 * can only set incrementally. 134 * 135 * E.g. 136 * ewah_set(bitmap, 1); // ok 137 * ewah_set(bitmap, 76); // ok 138 * ewah_set(bitmap, 77); // ok 139 * ewah_set(bitmap, 8712800127); // ok 140 * ewah_set(bitmap, 25); // failed, assert raised 141 */ 142void ewah_set(struct ewah_bitmap *self, size_t i); 143 144struct ewah_iterator { 145 const eword_t *buffer; 146 size_t buffer_size; 147 148 size_t pointer; 149 eword_t compressed, literals; 150 eword_t rl, lw; 151 int b; 152}; 153 154/** 155 * Initialize a new iterator to run through the bitmap in uncompressed form. 156 * 157 * The iterator can be stack allocated. The underlying bitmap must not be freed 158 * before the iteration is over. 159 * 160 * E.g. 161 * 162 * struct ewah_bitmap *bitmap = ewah_new(); 163 * struct ewah_iterator it; 164 * 165 * ewah_iterator_init(&it, bitmap); 166 */ 167void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent); 168 169/** 170 * Yield every single word in the bitmap in uncompressed form. This is: 171 * yield single words (32-64 bits) where each bit represents an actual 172 * bit from the bitmap. 173 * 174 * Return: true if a word was yield, false if there are no words left 175 */ 176int ewah_iterator_next(eword_t *next, struct ewah_iterator *it); 177 178void ewah_or( 179 struct ewah_bitmap *ewah_i, 180 struct ewah_bitmap *ewah_j, 181 struct ewah_bitmap *out); 182 183void ewah_and_not( 184 struct ewah_bitmap *ewah_i, 185 struct ewah_bitmap *ewah_j, 186 struct ewah_bitmap *out); 187 188void ewah_xor( 189 struct ewah_bitmap *ewah_i, 190 struct ewah_bitmap *ewah_j, 191 struct ewah_bitmap *out); 192 193void ewah_and( 194 struct ewah_bitmap *ewah_i, 195 struct ewah_bitmap *ewah_j, 196 struct ewah_bitmap *out); 197 198/** 199 * Direct word access 200 */ 201size_t ewah_add_empty_words(struct ewah_bitmap *self, int v, size_t number); 202void ewah_add_dirty_words( 203 struct ewah_bitmap *self, const eword_t *buffer, size_t number, int negate); 204size_t ewah_add(struct ewah_bitmap *self, eword_t word); 205 206 207/** 208 * Uncompressed, old-school bitmap that can be efficiently compressed 209 * into an `ewah_bitmap`. 210 */ 211struct bitmap { 212 eword_t *words; 213 size_t word_alloc; 214}; 215 216struct bitmap *bitmap_new(void); 217void bitmap_set(struct bitmap *self, size_t pos); 218void bitmap_clear(struct bitmap *self, size_t pos); 219int bitmap_get(struct bitmap *self, size_t pos); 220void bitmap_reset(struct bitmap *self); 221void bitmap_free(struct bitmap *self); 222int bitmap_equals(struct bitmap *self, struct bitmap *other); 223int bitmap_is_subset(struct bitmap *self, struct bitmap *super); 224 225struct ewah_bitmap * bitmap_to_ewah(struct bitmap *bitmap); 226struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah); 227 228void bitmap_and_not(struct bitmap *self, struct bitmap *other); 229void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other); 230void bitmap_or(struct bitmap *self, const struct bitmap *other); 231 232void bitmap_each_bit(struct bitmap *self, ewah_callback callback, void *data); 233size_t bitmap_popcount(struct bitmap *self); 234 235#endif