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, see <http://www.gnu.org/licenses/>. 18 */ 19#ifndef __EWOK_BITMAP_H__ 20#define __EWOK_BITMAP_H__ 21 22struct strbuf; 23typedefuint64_t eword_t; 24#define BITS_IN_EWORD (sizeof(eword_t) * 8) 25 26/** 27 * Do not use __builtin_popcountll. The GCC implementation 28 * is notoriously slow on all platforms. 29 * 30 * See: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36041 31 */ 32staticinlineuint32_tewah_bit_popcount64(uint64_t x) 33{ 34 x = (x &0x5555555555555555ULL) + ((x >>1) &0x5555555555555555ULL); 35 x = (x &0x3333333333333333ULL) + ((x >>2) &0x3333333333333333ULL); 36 x = (x &0x0F0F0F0F0F0F0F0FULL) + ((x >>4) &0x0F0F0F0F0F0F0F0FULL); 37return(x *0x0101010101010101ULL) >>56; 38} 39 40/* __builtin_ctzll was not available until 3.4.0 */ 41#if defined(__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR > 3)) 42#define ewah_bit_ctz64(x) __builtin_ctzll(x) 43#else 44staticinlineintewah_bit_ctz64(uint64_t x) 45{ 46int n =0; 47if((x &0xffffffff) ==0) { x >>=32; n +=32; } 48if((x &0xffff) ==0) { x >>=16; n +=16; } 49if((x &0xff) ==0) { x >>=8; n +=8; } 50if((x &0xf) ==0) { x >>=4; n +=4; } 51if((x &0x3) ==0) { x >>=2; n +=2; } 52if((x &0x1) ==0) { x >>=1; n +=1; } 53return n + !x; 54} 55#endif 56 57struct ewah_bitmap { 58 eword_t *buffer; 59size_t buffer_size; 60size_t alloc_size; 61size_t bit_size; 62 eword_t *rlw; 63}; 64 65typedefvoid(*ewah_callback)(size_t pos,void*); 66 67struct ewah_bitmap *ewah_pool_new(void); 68voidewah_pool_free(struct ewah_bitmap *self); 69 70/** 71 * Allocate a new EWAH Compressed bitmap 72 */ 73struct ewah_bitmap *ewah_new(void); 74 75/** 76 * Clear all the bits in the bitmap. Does not free or resize 77 * memory. 78 */ 79voidewah_clear(struct ewah_bitmap *self); 80 81/** 82 * Free all the memory of the bitmap 83 */ 84voidewah_free(struct ewah_bitmap *self); 85 86intewah_serialize_to(struct ewah_bitmap *self, 87int(*write_fun)(void*out,const void*buf,size_t len), 88void*out); 89intewah_serialize(struct ewah_bitmap *self,int fd); 90intewah_serialize_native(struct ewah_bitmap *self,int fd); 91intewah_serialize_strbuf(struct ewah_bitmap *self,struct strbuf *); 92 93intewah_deserialize(struct ewah_bitmap *self,int fd); 94ssize_t ewah_read_mmap(struct ewah_bitmap *self,const void*map,size_t len); 95 96uint32_tewah_checksum(struct ewah_bitmap *self); 97 98/** 99 * Call the given callback with the position of every single bit 100 * that has been set on the bitmap. 101 * 102 * This is an efficient operation that does not fully decompress 103 * the bitmap. 104 */ 105voidewah_each_bit(struct ewah_bitmap *self, ewah_callback callback,void*payload); 106 107/** 108 * Set a given bit on the bitmap. 109 * 110 * The bit at position `pos` will be set to true. Because of the 111 * way that the bitmap is compressed, a set bit cannot be unset 112 * later on. 113 * 114 * Furthermore, since the bitmap uses streaming compression, bits 115 * can only set incrementally. 116 * 117 * E.g. 118 * ewah_set(bitmap, 1); // ok 119 * ewah_set(bitmap, 76); // ok 120 * ewah_set(bitmap, 77); // ok 121 * ewah_set(bitmap, 8712800127); // ok 122 * ewah_set(bitmap, 25); // failed, assert raised 123 */ 124voidewah_set(struct ewah_bitmap *self,size_t i); 125 126struct ewah_iterator { 127const eword_t *buffer; 128size_t buffer_size; 129 130size_t pointer; 131 eword_t compressed, literals; 132 eword_t rl, lw; 133int b; 134}; 135 136/** 137 * Initialize a new iterator to run through the bitmap in uncompressed form. 138 * 139 * The iterator can be stack allocated. The underlying bitmap must not be freed 140 * before the iteration is over. 141 * 142 * E.g. 143 * 144 * struct ewah_bitmap *bitmap = ewah_new(); 145 * struct ewah_iterator it; 146 * 147 * ewah_iterator_init(&it, bitmap); 148 */ 149voidewah_iterator_init(struct ewah_iterator *it,struct ewah_bitmap *parent); 150 151/** 152 * Yield every single word in the bitmap in uncompressed form. This is: 153 * yield single words (32-64 bits) where each bit represents an actual 154 * bit from the bitmap. 155 * 156 * Return: true if a word was yield, false if there are no words left 157 */ 158intewah_iterator_next(eword_t *next,struct ewah_iterator *it); 159 160voidewah_xor( 161struct ewah_bitmap *ewah_i, 162struct ewah_bitmap *ewah_j, 163struct ewah_bitmap *out); 164 165/** 166 * Direct word access 167 */ 168size_tewah_add_empty_words(struct ewah_bitmap *self,int v,size_t number); 169voidewah_add_dirty_words( 170struct ewah_bitmap *self,const eword_t *buffer,size_t number,int negate); 171size_tewah_add(struct ewah_bitmap *self, eword_t word); 172 173 174/** 175 * Uncompressed, old-school bitmap that can be efficiently compressed 176 * into an `ewah_bitmap`. 177 */ 178struct bitmap { 179 eword_t *words; 180size_t word_alloc; 181}; 182 183struct bitmap *bitmap_new(void); 184voidbitmap_set(struct bitmap *self,size_t pos); 185intbitmap_get(struct bitmap *self,size_t pos); 186voidbitmap_reset(struct bitmap *self); 187voidbitmap_free(struct bitmap *self); 188intbitmap_equals(struct bitmap *self,struct bitmap *other); 189intbitmap_is_subset(struct bitmap *self,struct bitmap *super); 190 191struct ewah_bitmap *bitmap_to_ewah(struct bitmap *bitmap); 192struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah); 193 194voidbitmap_and_not(struct bitmap *self,struct bitmap *other); 195voidbitmap_or_ewah(struct bitmap *self,struct ewah_bitmap *other); 196voidbitmap_or(struct bitmap *self,const struct bitmap *other); 197 198size_tbitmap_popcount(struct bitmap *self); 199 200#endif