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