ewah/ewah_bitmap.c

   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 #include "git-compat-util.h"
  20 #include "ewok.h"
  21 #include "ewok_rlw.h"
  22
  23 static inline size_t min_size(size_t a, size_t b)
  24 {
  25         return a < b ? a : b;
  26 }
  27
  28 static inline size_t max_size(size_t a, size_t b)
  29 {
  30         return a > b ? a : b;
  31 }
  32
  33 static inline void buffer_grow(struct ewah_bitmap *self, size_t new_size)
  34 {
  35         size_t rlw_offset = (uint8_t *)self->rlw - (uint8_t *)self->buffer;
  36
  37         if (self->alloc_size >= new_size)
  38                 return;
  39
  40         self->alloc_size = new_size;
  41         REALLOC_ARRAY(self->buffer, self->alloc_size);
  42         self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
  43 }
  44
  45 static inline void buffer_push(struct ewah_bitmap *self, eword_t value)
  46 {
  47         if (self->buffer_size + 1 >= self->alloc_size)
  48                 buffer_grow(self, self->buffer_size * 3 / 2);
  49
  50         self->buffer[self->buffer_size++] = value;
  51 }
  52
  53 static void buffer_push_rlw(struct ewah_bitmap *self, eword_t value)
  54 {
  55         buffer_push(self, value);
  56         self->rlw = self->buffer + self->buffer_size - 1;
  57 }
  58
  59 static size_t add_empty_words(struct ewah_bitmap *self, int v, size_t number)
  60 {
  61         size_t added = 0;
  62         eword_t runlen, can_add;
  63
  64         if (rlw_get_run_bit(self->rlw) != v && rlw_size(self->rlw) == 0) {
  65                 rlw_set_run_bit(self->rlw, v);
  66         } else if (rlw_get_literal_words(self->rlw) != 0 ||
  67                         rlw_get_run_bit(self->rlw) != v) {
  68                 buffer_push_rlw(self, 0);
  69                 if (v) rlw_set_run_bit(self->rlw, v);
  70                 added++;
  71         }
  72
  73         runlen = rlw_get_running_len(self->rlw);
  74         can_add = min_size(number, RLW_LARGEST_RUNNING_COUNT - runlen);
  75
  76         rlw_set_running_len(self->rlw, runlen + can_add);
  77         number -= can_add;
  78
  79         while (number >= RLW_LARGEST_RUNNING_COUNT) {
  80                 buffer_push_rlw(self, 0);
  81                 added++;
  82                 if (v) rlw_set_run_bit(self->rlw, v);
  83                 rlw_set_running_len(self->rlw, RLW_LARGEST_RUNNING_COUNT);
  84                 number -= RLW_LARGEST_RUNNING_COUNT;
  85         }
  86
  87         if (number > 0) {
  88                 buffer_push_rlw(self, 0);
  89                 added++;
  90
  91                 if (v) rlw_set_run_bit(self->rlw, v);
  92                 rlw_set_running_len(self->rlw, number);
  93         }
  94
  95         return added;
  96 }
  97
  98 size_t ewah_add_empty_words(struct ewah_bitmap *self, int v, size_t number)
  99 {
 100         if (number == 0)
 101                 return 0;
 102
 103         self->bit_size += number * BITS_IN_EWORD;
 104         return add_empty_words(self, v, number);
 105 }
 106
 107 static size_t add_literal(struct ewah_bitmap *self, eword_t new_data)
 108 {
 109         eword_t current_num = rlw_get_literal_words(self->rlw);
 110
 111         if (current_num >= RLW_LARGEST_LITERAL_COUNT) {
 112                 buffer_push_rlw(self, 0);
 113
 114                 rlw_set_literal_words(self->rlw, 1);
 115                 buffer_push(self, new_data);
 116                 return 2;
 117         }
 118
 119         rlw_set_literal_words(self->rlw, current_num + 1);
 120
 121         /* sanity check */
 122         assert(rlw_get_literal_words(self->rlw) == current_num + 1);
 123
 124         buffer_push(self, new_data);
 125         return 1;
 126 }
 127
 128 void ewah_add_dirty_words(
 129         struct ewah_bitmap *self, const eword_t *buffer,
 130         size_t number, int negate)
 131 {
 132         size_t literals, can_add;
 133
 134         while (1) {
 135                 literals = rlw_get_literal_words(self->rlw);
 136                 can_add = min_size(number, RLW_LARGEST_LITERAL_COUNT - literals);
 137
 138                 rlw_set_literal_words(self->rlw, literals + can_add);
 139
 140                 if (self->buffer_size + can_add >= self->alloc_size)
 141                         buffer_grow(self, (self->buffer_size + can_add) * 3 / 2);
 142
 143                 if (negate) {
 144                         size_t i;
 145                         for (i = 0; i < can_add; ++i)
 146                                 self->buffer[self->buffer_size++] = ~buffer[i];
 147                 } else {
 148                         memcpy(self->buffer + self->buffer_size,
 149                                 buffer, can_add * sizeof(eword_t));
 150                         self->buffer_size += can_add;
 151                 }
 152
 153                 self->bit_size += can_add * BITS_IN_EWORD;
 154
 155                 if (number - can_add == 0)
 156                         break;
 157
 158                 buffer_push_rlw(self, 0);
 159                 buffer += can_add;
 160                 number -= can_add;
 161         }
 162 }
 163
 164 static size_t add_empty_word(struct ewah_bitmap *self, int v)
 165 {
 166         int no_literal = (rlw_get_literal_words(self->rlw) == 0);
 167         eword_t run_len = rlw_get_running_len(self->rlw);
 168
 169         if (no_literal && run_len == 0) {
 170                 rlw_set_run_bit(self->rlw, v);
 171                 assert(rlw_get_run_bit(self->rlw) == v);
 172         }
 173
 174         if (no_literal && rlw_get_run_bit(self->rlw) == v &&
 175                 run_len < RLW_LARGEST_RUNNING_COUNT) {
 176                 rlw_set_running_len(self->rlw, run_len + 1);
 177                 assert(rlw_get_running_len(self->rlw) == run_len + 1);
 178                 return 0;
 179         } else {
 180                 buffer_push_rlw(self, 0);
 181
 182                 assert(rlw_get_running_len(self->rlw) == 0);
 183                 assert(rlw_get_run_bit(self->rlw) == 0);
 184                 assert(rlw_get_literal_words(self->rlw) == 0);
 185
 186                 rlw_set_run_bit(self->rlw, v);
 187                 assert(rlw_get_run_bit(self->rlw) == v);
 188
 189                 rlw_set_running_len(self->rlw, 1);
 190                 assert(rlw_get_running_len(self->rlw) == 1);
 191                 assert(rlw_get_literal_words(self->rlw) == 0);
 192                 return 1;
 193         }
 194 }
 195
 196 size_t ewah_add(struct ewah_bitmap *self, eword_t word)
 197 {
 198         self->bit_size += BITS_IN_EWORD;
 199
 200         if (word == 0)
 201                 return add_empty_word(self, 0);
 202
 203         if (word == (eword_t)(~0))
 204                 return add_empty_word(self, 1);
 205
 206         return add_literal(self, word);
 207 }
 208
 209 void ewah_set(struct ewah_bitmap *self, size_t i)
 210 {
 211         const size_t dist =
 212                 DIV_ROUND_UP(i + 1, BITS_IN_EWORD) -
 213                 DIV_ROUND_UP(self->bit_size, BITS_IN_EWORD);
 214
 215         assert(i >= self->bit_size);
 216
 217         self->bit_size = i + 1;
 218
 219         if (dist > 0) {
 220                 if (dist > 1)
 221                         add_empty_words(self, 0, dist - 1);
 222
 223                 add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD));
 224                 return;
 225         }
 226
 227         if (rlw_get_literal_words(self->rlw) == 0) {
 228                 rlw_set_running_len(self->rlw,
 229                         rlw_get_running_len(self->rlw) - 1);
 230                 add_literal(self, (eword_t)1 << (i % BITS_IN_EWORD));
 231                 return;
 232         }
 233
 234         self->buffer[self->buffer_size - 1] |=
 235                 ((eword_t)1 << (i % BITS_IN_EWORD));
 236
 237         /* check if we just completed a stream of 1s */
 238         if (self->buffer[self->buffer_size - 1] == (eword_t)(~0)) {
 239                 self->buffer[--self->buffer_size] = 0;
 240                 rlw_set_literal_words(self->rlw,
 241                         rlw_get_literal_words(self->rlw) - 1);
 242                 add_empty_word(self, 1);
 243         }
 244 }
 245
 246 void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), void *payload)
 247 {
 248         size_t pos = 0;
 249         size_t pointer = 0;
 250         size_t k;
 251
 252         while (pointer < self->buffer_size) {
 253                 eword_t *word = &self->buffer[pointer];
 254
 255                 if (rlw_get_run_bit(word)) {
 256                         size_t len = rlw_get_running_len(word) * BITS_IN_EWORD;
 257                         for (k = 0; k < len; ++k, ++pos)
 258                                 callback(pos, payload);
 259                 } else {
 260                         pos += rlw_get_running_len(word) * BITS_IN_EWORD;
 261                 }
 262
 263                 ++pointer;
 264
 265                 for (k = 0; k < rlw_get_literal_words(word); ++k) {
 266                         int c;
 267
 268                         /* todo: zero count optimization */
 269                         for (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {
 270                                 if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)
 271                                         callback(pos, payload);
 272                         }
 273
 274                         ++pointer;
 275                 }
 276         }
 277 }
 278
 279 /**
 280  * Clear all the bits in the bitmap. Does not free or resize
 281  * memory.
 282  */
 283 static void ewah_clear(struct ewah_bitmap *self)
 284 {
 285         self->buffer_size = 1;
 286         self->buffer[0] = 0;
 287         self->bit_size = 0;
 288         self->rlw = self->buffer;
 289 }
 290
 291 struct ewah_bitmap *ewah_new(void)
 292 {
 293         struct ewah_bitmap *self;
 294
 295         self = xmalloc(sizeof(struct ewah_bitmap));
 296         self->alloc_size = 32;
 297         ALLOC_ARRAY(self->buffer, self->alloc_size);
 298
 299         ewah_clear(self);
 300         return self;
 301 }
 302
 303 void ewah_free(struct ewah_bitmap *self)
 304 {
 305         if (!self)
 306                 return;
 307
 308         if (self->alloc_size)
 309                 free(self->buffer);
 310
 311         free(self);
 312 }
 313
 314 static void read_new_rlw(struct ewah_iterator *it)
 315 {
 316         const eword_t *word = NULL;
 317
 318         it->literals = 0;
 319         it->compressed = 0;
 320
 321         while (1) {
 322                 word = &it->buffer[it->pointer];
 323
 324                 it->rl = rlw_get_running_len(word);
 325                 it->lw = rlw_get_literal_words(word);
 326                 it->b = rlw_get_run_bit(word);
 327
 328                 if (it->rl || it->lw)
 329                         return;
 330
 331                 if (it->pointer < it->buffer_size - 1) {
 332                         it->pointer++;
 333                 } else {
 334                         it->pointer = it->buffer_size;
 335                         return;
 336                 }
 337         }
 338 }
 339
 340 int ewah_iterator_next(eword_t *next, struct ewah_iterator *it)
 341 {
 342         if (it->pointer >= it->buffer_size)
 343                 return 0;
 344
 345         if (it->compressed < it->rl) {
 346                 it->compressed++;
 347                 *next = it->b ? (eword_t)(~0) : 0;
 348         } else {
 349                 assert(it->literals < it->lw);
 350
 351                 it->literals++;
 352                 it->pointer++;
 353
 354                 assert(it->pointer < it->buffer_size);
 355
 356                 *next = it->buffer[it->pointer];
 357         }
 358
 359         if (it->compressed == it->rl && it->literals == it->lw) {
 360                 if (++it->pointer < it->buffer_size)
 361                         read_new_rlw(it);
 362         }
 363
 364         return 1;
 365 }
 366
 367 void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)
 368 {
 369         it->buffer = parent->buffer;
 370         it->buffer_size = parent->buffer_size;
 371         it->pointer = 0;
 372
 373         it->lw = 0;
 374         it->rl = 0;
 375         it->compressed = 0;
 376         it->literals = 0;
 377         it->b = 0;
 378
 379         if (it->pointer < it->buffer_size)
 380                 read_new_rlw(it);
 381 }
 382
 383 void ewah_xor(
 384         struct ewah_bitmap *ewah_i,
 385         struct ewah_bitmap *ewah_j,
 386         struct ewah_bitmap *out)
 387 {
 388         struct rlw_iterator rlw_i;
 389         struct rlw_iterator rlw_j;
 390         size_t literals;
 391
 392         rlwit_init(&rlw_i, ewah_i);
 393         rlwit_init(&rlw_j, ewah_j);
 394
 395         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 396                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 397                         struct rlw_iterator *prey, *predator;
 398                         size_t index;
 399                         int negate_words;
 400
 401                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 402                                 prey = &rlw_i;
 403                                 predator = &rlw_j;
 404                         } else {
 405                                 prey = &rlw_j;
 406                                 predator = &rlw_i;
 407                         }
 408
 409                         negate_words = !!predator->rlw.running_bit;
 410                         index = rlwit_discharge(prey, out,
 411                                 predator->rlw.running_len, negate_words);
 412
 413                         ewah_add_empty_words(out, negate_words,
 414                                 predator->rlw.running_len - index);
 415
 416                         rlwit_discard_first_words(predator,
 417                                 predator->rlw.running_len);
 418                 }
 419
 420                 literals = min_size(
 421                         rlw_i.rlw.literal_words,
 422                         rlw_j.rlw.literal_words);
 423
 424                 if (literals) {
 425                         size_t k;
 426
 427                         for (k = 0; k < literals; ++k) {
 428                                 ewah_add(out,
 429                                         rlw_i.buffer[rlw_i.literal_word_start + k] ^
 430                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 431                                 );
 432                         }
 433
 434                         rlwit_discard_first_words(&rlw_i, literals);
 435                         rlwit_discard_first_words(&rlw_j, literals);
 436                 }
 437         }
 438
 439         if (rlwit_word_size(&rlw_i) > 0)
 440                 rlwit_discharge(&rlw_i, out, ~0, 0);
 441         else
 442                 rlwit_discharge(&rlw_j, out, ~0, 0);
 443
 444         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 445 }
 446
 447 #define BITMAP_POOL_MAX 16
 448 static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
 449 static size_t bitmap_pool_size;
 450
 451 struct ewah_bitmap *ewah_pool_new(void)
 452 {
 453         if (bitmap_pool_size)
 454                 return bitmap_pool[--bitmap_pool_size];
 455
 456         return ewah_new();
 457 }
 458
 459 void ewah_pool_free(struct ewah_bitmap *self)
 460 {
 461         if (self == NULL)
 462                 return;
 463
 464         if (bitmap_pool_size == BITMAP_POOL_MAX ||
 465                 self->alloc_size == 0) {
 466                 ewah_free(self);
 467                 return;
 468         }
 469
 470         ewah_clear(self);
 471         bitmap_pool[bitmap_pool_size++] = self;
 472 }
 473
 474 uint32_t ewah_checksum(struct ewah_bitmap *self)
 475 {
 476         const uint8_t *p = (uint8_t *)self->buffer;
 477         uint32_t crc = (uint32_t)self->bit_size;
 478         size_t size = self->buffer_size * sizeof(eword_t);
 479
 480         while (size--)
 481                 crc = (crc << 5) - crc + (uint32_t)*p++;
 482
 483         return crc;
 484 }