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