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