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, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  */
  20 #include "git-compat-util.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
  38         if (self->alloc_size >= new_size)
  39                 return;
  40
  41         self->alloc_size = new_size;
  42         self->buffer = ewah_realloc(self->buffer,
  43                 self->alloc_size * sizeof(eword_t));
  44         self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
  45 }
  46
  47 static inline void buffer_push(struct ewah_bitmap *self, eword_t value)
  48 {
  49         if (self->buffer_size + 1 >= self->alloc_size)
  50                 buffer_grow(self, self->buffer_size * 3 / 2);
  51
  52         self->buffer[self->buffer_size++] = value;
  53 }
  54
  55 static void buffer_push_rlw(struct ewah_bitmap *self, eword_t value)
  56 {
  57         buffer_push(self, value);
  58         self->rlw = self->buffer + self->buffer_size - 1;
  59 }
  60
  61 static size_t add_empty_words(struct ewah_bitmap *self, int v, size_t number)
  62 {
  63         size_t added = 0;
  64         eword_t runlen, can_add;
  65
  66         if (rlw_get_run_bit(self->rlw) != v && rlw_size(self->rlw) == 0) {
  67                 rlw_set_run_bit(self->rlw, v);
  68         } else if (rlw_get_literal_words(self->rlw) != 0 ||
  69                         rlw_get_run_bit(self->rlw) != v) {
  70                 buffer_push_rlw(self, 0);
  71                 if (v) rlw_set_run_bit(self->rlw, v);
  72                 added++;
  73         }
  74
  75         runlen = rlw_get_running_len(self->rlw);
  76         can_add = min_size(number, RLW_LARGEST_RUNNING_COUNT - runlen);
  77
  78         rlw_set_running_len(self->rlw, runlen + can_add);
  79         number -= can_add;
  80
  81         while (number >= RLW_LARGEST_RUNNING_COUNT) {
  82                 buffer_push_rlw(self, 0);
  83                 added++;
  84                 if (v) rlw_set_run_bit(self->rlw, v);
  85                 rlw_set_running_len(self->rlw, RLW_LARGEST_RUNNING_COUNT);
  86                 number -= RLW_LARGEST_RUNNING_COUNT;
  87         }
  88
  89         if (number > 0) {
  90                 buffer_push_rlw(self, 0);
  91                 added++;
  92
  93                 if (v) rlw_set_run_bit(self->rlw, v);
  94                 rlw_set_running_len(self->rlw, number);
  95         }
  96
  97         return added;
  98 }
  99
 100 size_t ewah_add_empty_words(struct ewah_bitmap *self, int v, size_t number)
 101 {
 102         if (number == 0)
 103                 return 0;
 104
 105         self->bit_size += number * BITS_IN_WORD;
 106         return add_empty_words(self, v, number);
 107 }
 108
 109 static size_t add_literal(struct ewah_bitmap *self, eword_t new_data)
 110 {
 111         eword_t current_num = rlw_get_literal_words(self->rlw);
 112
 113         if (current_num >= RLW_LARGEST_LITERAL_COUNT) {
 114                 buffer_push_rlw(self, 0);
 115
 116                 rlw_set_literal_words(self->rlw, 1);
 117                 buffer_push(self, new_data);
 118                 return 2;
 119         }
 120
 121         rlw_set_literal_words(self->rlw, current_num + 1);
 122
 123         /* sanity check */
 124         assert(rlw_get_literal_words(self->rlw) == current_num + 1);
 125
 126         buffer_push(self, new_data);
 127         return 1;
 128 }
 129
 130 void ewah_add_dirty_words(
 131         struct ewah_bitmap *self, const eword_t *buffer,
 132         size_t number, int negate)
 133 {
 134         size_t literals, can_add;
 135
 136         while (1) {
 137                 literals = rlw_get_literal_words(self->rlw);
 138                 can_add = min_size(number, RLW_LARGEST_LITERAL_COUNT - literals);
 139
 140                 rlw_set_literal_words(self->rlw, literals + can_add);
 141
 142                 if (self->buffer_size + can_add >= self->alloc_size)
 143                         buffer_grow(self, (self->buffer_size + can_add) * 3 / 2);
 144
 145                 if (negate) {
 146                         size_t i;
 147                         for (i = 0; i < can_add; ++i)
 148                                 self->buffer[self->buffer_size++] = ~buffer[i];
 149                 } else {
 150                         memcpy(self->buffer + self->buffer_size,
 151                                 buffer, can_add * sizeof(eword_t));
 152                         self->buffer_size += can_add;
 153                 }
 154
 155                 self->bit_size += can_add * BITS_IN_WORD;
 156
 157                 if (number - can_add == 0)
 158                         break;
 159
 160                 buffer_push_rlw(self, 0);
 161                 buffer += can_add;
 162                 number -= can_add;
 163         }
 164 }
 165
 166 static size_t add_empty_word(struct ewah_bitmap *self, int v)
 167 {
 168         int no_literal = (rlw_get_literal_words(self->rlw) == 0);
 169         eword_t run_len = rlw_get_running_len(self->rlw);
 170
 171         if (no_literal && run_len == 0) {
 172                 rlw_set_run_bit(self->rlw, v);
 173                 assert(rlw_get_run_bit(self->rlw) == v);
 174         }
 175
 176         if (no_literal && rlw_get_run_bit(self->rlw) == v &&
 177                 run_len < RLW_LARGEST_RUNNING_COUNT) {
 178                 rlw_set_running_len(self->rlw, run_len + 1);
 179                 assert(rlw_get_running_len(self->rlw) == run_len + 1);
 180                 return 0;
 181         } else {
 182                 buffer_push_rlw(self, 0);
 183
 184                 assert(rlw_get_running_len(self->rlw) == 0);
 185                 assert(rlw_get_run_bit(self->rlw) == 0);
 186                 assert(rlw_get_literal_words(self->rlw) == 0);
 187
 188                 rlw_set_run_bit(self->rlw, v);
 189                 assert(rlw_get_run_bit(self->rlw) == v);
 190
 191                 rlw_set_running_len(self->rlw, 1);
 192                 assert(rlw_get_running_len(self->rlw) == 1);
 193                 assert(rlw_get_literal_words(self->rlw) == 0);
 194                 return 1;
 195         }
 196 }
 197
 198 size_t ewah_add(struct ewah_bitmap *self, eword_t word)
 199 {
 200         self->bit_size += BITS_IN_WORD;
 201
 202         if (word == 0)
 203                 return add_empty_word(self, 0);
 204
 205         if (word == (eword_t)(~0))
 206                 return add_empty_word(self, 1);
 207
 208         return add_literal(self, word);
 209 }
 210
 211 void ewah_set(struct ewah_bitmap *self, size_t i)
 212 {
 213         const size_t dist =
 214                 (i + BITS_IN_WORD) / BITS_IN_WORD -
 215                 (self->bit_size + BITS_IN_WORD - 1) / BITS_IN_WORD;
 216
 217         assert(i >= self->bit_size);
 218
 219         self->bit_size = i + 1;
 220
 221         if (dist > 0) {
 222                 if (dist > 1)
 223                         add_empty_words(self, 0, dist - 1);
 224
 225                 add_literal(self, (eword_t)1 << (i % BITS_IN_WORD));
 226                 return;
 227         }
 228
 229         if (rlw_get_literal_words(self->rlw) == 0) {
 230                 rlw_set_running_len(self->rlw,
 231                         rlw_get_running_len(self->rlw) - 1);
 232                 add_literal(self, (eword_t)1 << (i % BITS_IN_WORD));
 233                 return;
 234         }
 235
 236         self->buffer[self->buffer_size - 1] |=
 237                 ((eword_t)1 << (i % BITS_IN_WORD));
 238
 239         /* check if we just completed a stream of 1s */
 240         if (self->buffer[self->buffer_size - 1] == (eword_t)(~0)) {
 241                 self->buffer[--self->buffer_size] = 0;
 242                 rlw_set_literal_words(self->rlw,
 243                         rlw_get_literal_words(self->rlw) - 1);
 244                 add_empty_word(self, 1);
 245         }
 246 }
 247
 248 void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), void *payload)
 249 {
 250         size_t pos = 0;
 251         size_t pointer = 0;
 252         size_t k;
 253
 254         while (pointer < self->buffer_size) {
 255                 eword_t *word = &self->buffer[pointer];
 256
 257                 if (rlw_get_run_bit(word)) {
 258                         size_t len = rlw_get_running_len(word) * BITS_IN_WORD;
 259                         for (k = 0; k < len; ++k, ++pos)
 260                                 callback(pos, payload);
 261                 } else {
 262                         pos += rlw_get_running_len(word) * BITS_IN_WORD;
 263                 }
 264
 265                 ++pointer;
 266
 267                 for (k = 0; k < rlw_get_literal_words(word); ++k) {
 268                         int c;
 269
 270                         /* todo: zero count optimization */
 271                         for (c = 0; c < BITS_IN_WORD; ++c, ++pos) {
 272                                 if ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)
 273                                         callback(pos, payload);
 274                         }
 275
 276                         ++pointer;
 277                 }
 278         }
 279 }
 280
 281 struct ewah_bitmap *ewah_new(void)
 282 {
 283         struct ewah_bitmap *self;
 284
 285         self = ewah_malloc(sizeof(struct ewah_bitmap));
 286         if (self == NULL)
 287                 return NULL;
 288
 289         self->buffer = ewah_malloc(32 * sizeof(eword_t));
 290         self->alloc_size = 32;
 291
 292         ewah_clear(self);
 293         return self;
 294 }
 295
 296 void ewah_clear(struct ewah_bitmap *self)
 297 {
 298         self->buffer_size = 1;
 299         self->buffer[0] = 0;
 300         self->bit_size = 0;
 301         self->rlw = self->buffer;
 302 }
 303
 304 void ewah_free(struct ewah_bitmap *self)
 305 {
 306         if (!self)
 307                 return;
 308
 309         if (self->alloc_size)
 310                 free(self->buffer);
 311
 312         free(self);
 313 }
 314
 315 static void read_new_rlw(struct ewah_iterator *it)
 316 {
 317         const eword_t *word = NULL;
 318
 319         it->literals = 0;
 320         it->compressed = 0;
 321
 322         while (1) {
 323                 word = &it->buffer[it->pointer];
 324
 325                 it->rl = rlw_get_running_len(word);
 326                 it->lw = rlw_get_literal_words(word);
 327                 it->b = rlw_get_run_bit(word);
 328
 329                 if (it->rl || it->lw)
 330                         return;
 331
 332                 if (it->pointer < it->buffer_size - 1) {
 333                         it->pointer++;
 334                 } else {
 335                         it->pointer = it->buffer_size;
 336                         return;
 337                 }
 338         }
 339 }
 340
 341 int ewah_iterator_next(eword_t *next, struct ewah_iterator *it)
 342 {
 343         if (it->pointer >= it->buffer_size)
 344                 return 0;
 345
 346         if (it->compressed < it->rl) {
 347                 it->compressed++;
 348                 *next = it->b ? (eword_t)(~0) : 0;
 349         } else {
 350                 assert(it->literals < it->lw);
 351
 352                 it->literals++;
 353                 it->pointer++;
 354
 355                 assert(it->pointer < it->buffer_size);
 356
 357                 *next = it->buffer[it->pointer];
 358         }
 359
 360         if (it->compressed == it->rl && it->literals == it->lw) {
 361                 if (++it->pointer < it->buffer_size)
 362                         read_new_rlw(it);
 363         }
 364
 365         return 1;
 366 }
 367
 368 void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)
 369 {
 370         it->buffer = parent->buffer;
 371         it->buffer_size = parent->buffer_size;
 372         it->pointer = 0;
 373
 374         it->lw = 0;
 375         it->rl = 0;
 376         it->compressed = 0;
 377         it->literals = 0;
 378         it->b = 0;
 379
 380         if (it->pointer < it->buffer_size)
 381                 read_new_rlw(it);
 382 }
 383
 384 void ewah_not(struct ewah_bitmap *self)
 385 {
 386         size_t pointer = 0;
 387
 388         while (pointer < self->buffer_size) {
 389                 eword_t *word = &self->buffer[pointer];
 390                 size_t literals, k;
 391
 392                 rlw_xor_run_bit(word);
 393                 ++pointer;
 394
 395                 literals = rlw_get_literal_words(word);
 396                 for (k = 0; k < literals; ++k) {
 397                         self->buffer[pointer] = ~self->buffer[pointer];
 398                         ++pointer;
 399                 }
 400         }
 401 }
 402
 403 void ewah_xor(
 404         struct ewah_bitmap *ewah_i,
 405         struct ewah_bitmap *ewah_j,
 406         struct ewah_bitmap *out)
 407 {
 408         struct rlw_iterator rlw_i;
 409         struct rlw_iterator rlw_j;
 410         size_t literals;
 411
 412         rlwit_init(&rlw_i, ewah_i);
 413         rlwit_init(&rlw_j, ewah_j);
 414
 415         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 416                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 417                         struct rlw_iterator *prey, *predator;
 418                         size_t index;
 419                         int negate_words;
 420
 421                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 422                                 prey = &rlw_i;
 423                                 predator = &rlw_j;
 424                         } else {
 425                                 prey = &rlw_j;
 426                                 predator = &rlw_i;
 427                         }
 428
 429                         negate_words = !!predator->rlw.running_bit;
 430                         index = rlwit_discharge(prey, out,
 431                                 predator->rlw.running_len, negate_words);
 432
 433                         ewah_add_empty_words(out, negate_words,
 434                                 predator->rlw.running_len - index);
 435
 436                         rlwit_discard_first_words(predator,
 437                                 predator->rlw.running_len);
 438                 }
 439
 440                 literals = min_size(
 441                         rlw_i.rlw.literal_words,
 442                         rlw_j.rlw.literal_words);
 443
 444                 if (literals) {
 445                         size_t k;
 446
 447                         for (k = 0; k < literals; ++k) {
 448                                 ewah_add(out,
 449                                         rlw_i.buffer[rlw_i.literal_word_start + k] ^
 450                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 451                                 );
 452                         }
 453
 454                         rlwit_discard_first_words(&rlw_i, literals);
 455                         rlwit_discard_first_words(&rlw_j, literals);
 456                 }
 457         }
 458
 459         if (rlwit_word_size(&rlw_i) > 0)
 460                 rlwit_discharge(&rlw_i, out, ~0, 0);
 461         else
 462                 rlwit_discharge(&rlw_j, out, ~0, 0);
 463
 464         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 465 }
 466
 467 void ewah_and(
 468         struct ewah_bitmap *ewah_i,
 469         struct ewah_bitmap *ewah_j,
 470         struct ewah_bitmap *out)
 471 {
 472         struct rlw_iterator rlw_i;
 473         struct rlw_iterator rlw_j;
 474         size_t literals;
 475
 476         rlwit_init(&rlw_i, ewah_i);
 477         rlwit_init(&rlw_j, ewah_j);
 478
 479         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 480                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 481                         struct rlw_iterator *prey, *predator;
 482
 483                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 484                                 prey = &rlw_i;
 485                                 predator = &rlw_j;
 486                         } else {
 487                                 prey = &rlw_j;
 488                                 predator = &rlw_i;
 489                         }
 490
 491                         if (predator->rlw.running_bit == 0) {
 492                                 ewah_add_empty_words(out, 0,
 493                                         predator->rlw.running_len);
 494                                 rlwit_discard_first_words(prey,
 495                                         predator->rlw.running_len);
 496                                 rlwit_discard_first_words(predator,
 497                                         predator->rlw.running_len);
 498                         } else {
 499                                 size_t index = rlwit_discharge(prey, out,
 500                                         predator->rlw.running_len, 0);
 501                                 ewah_add_empty_words(out, 0,
 502                                         predator->rlw.running_len - index);
 503                                 rlwit_discard_first_words(predator,
 504                                         predator->rlw.running_len);
 505                         }
 506                 }
 507
 508                 literals = min_size(
 509                         rlw_i.rlw.literal_words,
 510                         rlw_j.rlw.literal_words);
 511
 512                 if (literals) {
 513                         size_t k;
 514
 515                         for (k = 0; k < literals; ++k) {
 516                                 ewah_add(out,
 517                                         rlw_i.buffer[rlw_i.literal_word_start + k] &
 518                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 519                                 );
 520                         }
 521
 522                         rlwit_discard_first_words(&rlw_i, literals);
 523                         rlwit_discard_first_words(&rlw_j, literals);
 524                 }
 525         }
 526
 527         if (rlwit_word_size(&rlw_i) > 0)
 528                 rlwit_discharge_empty(&rlw_i, out);
 529         else
 530                 rlwit_discharge_empty(&rlw_j, out);
 531
 532         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 533 }
 534
 535 void ewah_and_not(
 536         struct ewah_bitmap *ewah_i,
 537         struct ewah_bitmap *ewah_j,
 538         struct ewah_bitmap *out)
 539 {
 540         struct rlw_iterator rlw_i;
 541         struct rlw_iterator rlw_j;
 542         size_t literals;
 543
 544         rlwit_init(&rlw_i, ewah_i);
 545         rlwit_init(&rlw_j, ewah_j);
 546
 547         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 548                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 549                         struct rlw_iterator *prey, *predator;
 550
 551                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 552                                 prey = &rlw_i;
 553                                 predator = &rlw_j;
 554                         } else {
 555                                 prey = &rlw_j;
 556                                 predator = &rlw_i;
 557                         }
 558
 559                         if ((predator->rlw.running_bit && prey == &rlw_i) ||
 560                                 (!predator->rlw.running_bit && prey != &rlw_i)) {
 561                                 ewah_add_empty_words(out, 0,
 562                                         predator->rlw.running_len);
 563                                 rlwit_discard_first_words(prey,
 564                                         predator->rlw.running_len);
 565                                 rlwit_discard_first_words(predator,
 566                                         predator->rlw.running_len);
 567                         } else {
 568                                 size_t index;
 569                                 int negate_words;
 570
 571                                 negate_words = (&rlw_i != prey);
 572                                 index = rlwit_discharge(prey, out,
 573                                         predator->rlw.running_len, negate_words);
 574                                 ewah_add_empty_words(out, negate_words,
 575                                         predator->rlw.running_len - index);
 576                                 rlwit_discard_first_words(predator,
 577                                         predator->rlw.running_len);
 578                         }
 579                 }
 580
 581                 literals = min_size(
 582                         rlw_i.rlw.literal_words,
 583                         rlw_j.rlw.literal_words);
 584
 585                 if (literals) {
 586                         size_t k;
 587
 588                         for (k = 0; k < literals; ++k) {
 589                                 ewah_add(out,
 590                                         rlw_i.buffer[rlw_i.literal_word_start + k] &
 591                                         ~(rlw_j.buffer[rlw_j.literal_word_start + k])
 592                                 );
 593                         }
 594
 595                         rlwit_discard_first_words(&rlw_i, literals);
 596                         rlwit_discard_first_words(&rlw_j, literals);
 597                 }
 598         }
 599
 600         if (rlwit_word_size(&rlw_i) > 0)
 601                 rlwit_discharge(&rlw_i, out, ~0, 0);
 602         else
 603                 rlwit_discharge_empty(&rlw_j, out);
 604
 605         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 606 }
 607
 608 void ewah_or(
 609         struct ewah_bitmap *ewah_i,
 610         struct ewah_bitmap *ewah_j,
 611         struct ewah_bitmap *out)
 612 {
 613         struct rlw_iterator rlw_i;
 614         struct rlw_iterator rlw_j;
 615         size_t literals;
 616
 617         rlwit_init(&rlw_i, ewah_i);
 618         rlwit_init(&rlw_j, ewah_j);
 619
 620         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 621                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 622                         struct rlw_iterator *prey, *predator;
 623
 624                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 625                                 prey = &rlw_i;
 626                                 predator = &rlw_j;
 627                         } else {
 628                                 prey = &rlw_j;
 629                                 predator = &rlw_i;
 630                         }
 631
 632                         if (predator->rlw.running_bit) {
 633                                 ewah_add_empty_words(out, 0,
 634                                         predator->rlw.running_len);
 635                                 rlwit_discard_first_words(prey,
 636                                         predator->rlw.running_len);
 637                                 rlwit_discard_first_words(predator,
 638                                         predator->rlw.running_len);
 639                         } else {
 640                                 size_t index = rlwit_discharge(prey, out,
 641                                         predator->rlw.running_len, 0);
 642                                 ewah_add_empty_words(out, 0,
 643                                         predator->rlw.running_len - index);
 644                                 rlwit_discard_first_words(predator,
 645                                         predator->rlw.running_len);
 646                         }
 647                 }
 648
 649                 literals = min_size(
 650                         rlw_i.rlw.literal_words,
 651                         rlw_j.rlw.literal_words);
 652
 653                 if (literals) {
 654                         size_t k;
 655
 656                         for (k = 0; k < literals; ++k) {
 657                                 ewah_add(out,
 658                                         rlw_i.buffer[rlw_i.literal_word_start + k] |
 659                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 660                                 );
 661                         }
 662
 663                         rlwit_discard_first_words(&rlw_i, literals);
 664                         rlwit_discard_first_words(&rlw_j, literals);
 665                 }
 666         }
 667
 668         if (rlwit_word_size(&rlw_i) > 0)
 669                 rlwit_discharge(&rlw_i, out, ~0, 0);
 670         else
 671                 rlwit_discharge(&rlw_j, out, ~0, 0);
 672
 673         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 674 }
 675
 676
 677 #define BITMAP_POOL_MAX 16
 678 static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
 679 static size_t bitmap_pool_size;
 680
 681 struct ewah_bitmap *ewah_pool_new(void)
 682 {
 683         if (bitmap_pool_size)
 684                 return bitmap_pool[--bitmap_pool_size];
 685
 686         return ewah_new();
 687 }
 688
 689 void ewah_pool_free(struct ewah_bitmap *self)
 690 {
 691         if (self == NULL)
 692                 return;
 693
 694         if (bitmap_pool_size == BITMAP_POOL_MAX ||
 695                 self->alloc_size == 0) {
 696                 ewah_free(self);
 697                 return;
 698         }
 699
 700         ewah_clear(self);
 701         bitmap_pool[bitmap_pool_size++] = self;
 702 }
 703
 704 uint32_t ewah_checksum(struct ewah_bitmap *self)
 705 {
 706         const uint8_t *p = (uint8_t *)self->buffer;
 707         uint32_t crc = (uint32_t)self->bit_size;
 708         size_t size = self->buffer_size * sizeof(eword_t);
 709
 710         while (size--)
 711                 crc = (crc << 5) - crc + (uint32_t)*p++;
 712
 713         return crc;
 714 }