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