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_strbuf(struct ewah_bitmap *self,struct strbuf *); 90 91ssize_t ewah_read_mmap(struct ewah_bitmap *self,const void*map,size_t len); 92 93uint32_tewah_checksum(struct ewah_bitmap *self); 94 95/** 96 * Call the given callback with the position of every single bit 97 * that has been set on the bitmap. 98 * 99 * This is an efficient operation that does not fully decompress 100 * the bitmap. 101 */ 102voidewah_each_bit(struct ewah_bitmap *self, ewah_callback callback,void*payload); 103 104/** 105 * Set a given bit on the bitmap. 106 * 107 * The bit at position `pos` will be set to true. Because of the 108 * way that the bitmap is compressed, a set bit cannot be unset 109 * later on. 110 * 111 * Furthermore, since the bitmap uses streaming compression, bits 112 * can only set incrementally. 113 * 114 * E.g. 115 * ewah_set(bitmap, 1); // ok 116 * ewah_set(bitmap, 76); // ok 117 * ewah_set(bitmap, 77); // ok 118 * ewah_set(bitmap, 8712800127); // ok 119 * ewah_set(bitmap, 25); // failed, assert raised 120 */ 121voidewah_set(struct ewah_bitmap *self,size_t i); 122 123struct ewah_iterator { 124const eword_t *buffer; 125size_t buffer_size; 126 127size_t pointer; 128 eword_t compressed, literals; 129 eword_t rl, lw; 130int b; 131}; 132 133/** 134 * Initialize a new iterator to run through the bitmap in uncompressed form. 135 * 136 * The iterator can be stack allocated. The underlying bitmap must not be freed 137 * before the iteration is over. 138 * 139 * E.g. 140 * 141 * struct ewah_bitmap *bitmap = ewah_new(); 142 * struct ewah_iterator it; 143 * 144 * ewah_iterator_init(&it, bitmap); 145 */ 146voidewah_iterator_init(struct ewah_iterator *it,struct ewah_bitmap *parent); 147 148/** 149 * Yield every single word in the bitmap in uncompressed form. This is: 150 * yield single words (32-64 bits) where each bit represents an actual 151 * bit from the bitmap. 152 * 153 * Return: true if a word was yield, false if there are no words left 154 */ 155intewah_iterator_next(eword_t *next,struct ewah_iterator *it); 156 157voidewah_xor( 158struct ewah_bitmap *ewah_i, 159struct ewah_bitmap *ewah_j, 160struct ewah_bitmap *out); 161 162/** 163 * Direct word access 164 */ 165size_tewah_add_empty_words(struct ewah_bitmap *self,int v,size_t number); 166voidewah_add_dirty_words( 167struct ewah_bitmap *self,const eword_t *buffer,size_t number,int negate); 168size_tewah_add(struct ewah_bitmap *self, eword_t word); 169 170 171/** 172 * Uncompressed, old-school bitmap that can be efficiently compressed 173 * into an `ewah_bitmap`. 174 */ 175struct bitmap { 176 eword_t *words; 177size_t word_alloc; 178}; 179 180struct bitmap *bitmap_new(void); 181voidbitmap_set(struct bitmap *self,size_t pos); 182intbitmap_get(struct bitmap *self,size_t pos); 183voidbitmap_reset(struct bitmap *self); 184voidbitmap_free(struct bitmap *self); 185intbitmap_equals(struct bitmap *self,struct bitmap *other); 186intbitmap_is_subset(struct bitmap *self,struct bitmap *super); 187 188struct ewah_bitmap *bitmap_to_ewah(struct bitmap *bitmap); 189struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah); 190 191voidbitmap_and_not(struct bitmap *self,struct bitmap *other); 192voidbitmap_or_ewah(struct bitmap *self,struct ewah_bitmap *other); 193voidbitmap_or(struct bitmap *self,const struct bitmap *other); 194 195size_tbitmap_popcount(struct bitmap *self); 196 197#endif