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 = xrealloc(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_EWORD;
 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_EWORD;
 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_EWORD;
 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_EWORD) / BITS_IN_EWORD -
 215                 (self->bit_size + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
 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_EWORD));
 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_EWORD));
 233                 return;
 234         }
 235
 236         self->buffer[self->buffer_size - 1] |=
 237                 ((eword_t)1 << (i % BITS_IN_EWORD));
 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_EWORD;
 259                         for (k = 0; k < len; ++k, ++pos)
 260                                 callback(pos, payload);
 261                 } else {
 262                         pos += rlw_get_running_len(word) * BITS_IN_EWORD;
 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_EWORD; ++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 = xmalloc(sizeof(struct ewah_bitmap));
 286         self->buffer = xmalloc(32 * sizeof(eword_t));
 287         self->alloc_size = 32;
 288
 289         ewah_clear(self);
 290         return self;
 291 }
 292
 293 void ewah_clear(struct ewah_bitmap *self)
 294 {
 295         self->buffer_size = 1;
 296         self->buffer[0] = 0;
 297         self->bit_size = 0;
 298         self->rlw = self->buffer;
 299 }
 300
 301 void ewah_free(struct ewah_bitmap *self)
 302 {
 303         if (!self)
 304                 return;
 305
 306         if (self->alloc_size)
 307                 free(self->buffer);
 308
 309         free(self);
 310 }
 311
 312 static void read_new_rlw(struct ewah_iterator *it)
 313 {
 314         const eword_t *word = NULL;
 315
 316         it->literals = 0;
 317         it->compressed = 0;
 318
 319         while (1) {
 320                 word = &it->buffer[it->pointer];
 321
 322                 it->rl = rlw_get_running_len(word);
 323                 it->lw = rlw_get_literal_words(word);
 324                 it->b = rlw_get_run_bit(word);
 325
 326                 if (it->rl || it->lw)
 327                         return;
 328
 329                 if (it->pointer < it->buffer_size - 1) {
 330                         it->pointer++;
 331                 } else {
 332                         it->pointer = it->buffer_size;
 333                         return;
 334                 }
 335         }
 336 }
 337
 338 int ewah_iterator_next(eword_t *next, struct ewah_iterator *it)
 339 {
 340         if (it->pointer >= it->buffer_size)
 341                 return 0;
 342
 343         if (it->compressed < it->rl) {
 344                 it->compressed++;
 345                 *next = it->b ? (eword_t)(~0) : 0;
 346         } else {
 347                 assert(it->literals < it->lw);
 348
 349                 it->literals++;
 350                 it->pointer++;
 351
 352                 assert(it->pointer < it->buffer_size);
 353
 354                 *next = it->buffer[it->pointer];
 355         }
 356
 357         if (it->compressed == it->rl && it->literals == it->lw) {
 358                 if (++it->pointer < it->buffer_size)
 359                         read_new_rlw(it);
 360         }
 361
 362         return 1;
 363 }
 364
 365 void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)
 366 {
 367         it->buffer = parent->buffer;
 368         it->buffer_size = parent->buffer_size;
 369         it->pointer = 0;
 370
 371         it->lw = 0;
 372         it->rl = 0;
 373         it->compressed = 0;
 374         it->literals = 0;
 375         it->b = 0;
 376
 377         if (it->pointer < it->buffer_size)
 378                 read_new_rlw(it);
 379 }
 380
 381 void ewah_not(struct ewah_bitmap *self)
 382 {
 383         size_t pointer = 0;
 384
 385         while (pointer < self->buffer_size) {
 386                 eword_t *word = &self->buffer[pointer];
 387                 size_t literals, k;
 388
 389                 rlw_xor_run_bit(word);
 390                 ++pointer;
 391
 392                 literals = rlw_get_literal_words(word);
 393                 for (k = 0; k < literals; ++k) {
 394                         self->buffer[pointer] = ~self->buffer[pointer];
 395                         ++pointer;
 396                 }
 397         }
 398 }
 399
 400 void ewah_xor(
 401         struct ewah_bitmap *ewah_i,
 402         struct ewah_bitmap *ewah_j,
 403         struct ewah_bitmap *out)
 404 {
 405         struct rlw_iterator rlw_i;
 406         struct rlw_iterator rlw_j;
 407         size_t literals;
 408
 409         rlwit_init(&rlw_i, ewah_i);
 410         rlwit_init(&rlw_j, ewah_j);
 411
 412         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 413                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 414                         struct rlw_iterator *prey, *predator;
 415                         size_t index;
 416                         int negate_words;
 417
 418                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 419                                 prey = &rlw_i;
 420                                 predator = &rlw_j;
 421                         } else {
 422                                 prey = &rlw_j;
 423                                 predator = &rlw_i;
 424                         }
 425
 426                         negate_words = !!predator->rlw.running_bit;
 427                         index = rlwit_discharge(prey, out,
 428                                 predator->rlw.running_len, negate_words);
 429
 430                         ewah_add_empty_words(out, negate_words,
 431                                 predator->rlw.running_len - index);
 432
 433                         rlwit_discard_first_words(predator,
 434                                 predator->rlw.running_len);
 435                 }
 436
 437                 literals = min_size(
 438                         rlw_i.rlw.literal_words,
 439                         rlw_j.rlw.literal_words);
 440
 441                 if (literals) {
 442                         size_t k;
 443
 444                         for (k = 0; k < literals; ++k) {
 445                                 ewah_add(out,
 446                                         rlw_i.buffer[rlw_i.literal_word_start + k] ^
 447                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 448                                 );
 449                         }
 450
 451                         rlwit_discard_first_words(&rlw_i, literals);
 452                         rlwit_discard_first_words(&rlw_j, literals);
 453                 }
 454         }
 455
 456         if (rlwit_word_size(&rlw_i) > 0)
 457                 rlwit_discharge(&rlw_i, out, ~0, 0);
 458         else
 459                 rlwit_discharge(&rlw_j, out, ~0, 0);
 460
 461         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 462 }
 463
 464 void ewah_and(
 465         struct ewah_bitmap *ewah_i,
 466         struct ewah_bitmap *ewah_j,
 467         struct ewah_bitmap *out)
 468 {
 469         struct rlw_iterator rlw_i;
 470         struct rlw_iterator rlw_j;
 471         size_t literals;
 472
 473         rlwit_init(&rlw_i, ewah_i);
 474         rlwit_init(&rlw_j, ewah_j);
 475
 476         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 477                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 478                         struct rlw_iterator *prey, *predator;
 479
 480                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 481                                 prey = &rlw_i;
 482                                 predator = &rlw_j;
 483                         } else {
 484                                 prey = &rlw_j;
 485                                 predator = &rlw_i;
 486                         }
 487
 488                         if (predator->rlw.running_bit == 0) {
 489                                 ewah_add_empty_words(out, 0,
 490                                         predator->rlw.running_len);
 491                                 rlwit_discard_first_words(prey,
 492                                         predator->rlw.running_len);
 493                                 rlwit_discard_first_words(predator,
 494                                         predator->rlw.running_len);
 495                         } else {
 496                                 size_t index = rlwit_discharge(prey, out,
 497                                         predator->rlw.running_len, 0);
 498                                 ewah_add_empty_words(out, 0,
 499                                         predator->rlw.running_len - index);
 500                                 rlwit_discard_first_words(predator,
 501                                         predator->rlw.running_len);
 502                         }
 503                 }
 504
 505                 literals = min_size(
 506                         rlw_i.rlw.literal_words,
 507                         rlw_j.rlw.literal_words);
 508
 509                 if (literals) {
 510                         size_t k;
 511
 512                         for (k = 0; k < literals; ++k) {
 513                                 ewah_add(out,
 514                                         rlw_i.buffer[rlw_i.literal_word_start + k] &
 515                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 516                                 );
 517                         }
 518
 519                         rlwit_discard_first_words(&rlw_i, literals);
 520                         rlwit_discard_first_words(&rlw_j, literals);
 521                 }
 522         }
 523
 524         if (rlwit_word_size(&rlw_i) > 0)
 525                 rlwit_discharge_empty(&rlw_i, out);
 526         else
 527                 rlwit_discharge_empty(&rlw_j, out);
 528
 529         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 530 }
 531
 532 void ewah_and_not(
 533         struct ewah_bitmap *ewah_i,
 534         struct ewah_bitmap *ewah_j,
 535         struct ewah_bitmap *out)
 536 {
 537         struct rlw_iterator rlw_i;
 538         struct rlw_iterator rlw_j;
 539         size_t literals;
 540
 541         rlwit_init(&rlw_i, ewah_i);
 542         rlwit_init(&rlw_j, ewah_j);
 543
 544         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 545                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 546                         struct rlw_iterator *prey, *predator;
 547
 548                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 549                                 prey = &rlw_i;
 550                                 predator = &rlw_j;
 551                         } else {
 552                                 prey = &rlw_j;
 553                                 predator = &rlw_i;
 554                         }
 555
 556                         if ((predator->rlw.running_bit && prey == &rlw_i) ||
 557                                 (!predator->rlw.running_bit && prey != &rlw_i)) {
 558                                 ewah_add_empty_words(out, 0,
 559                                         predator->rlw.running_len);
 560                                 rlwit_discard_first_words(prey,
 561                                         predator->rlw.running_len);
 562                                 rlwit_discard_first_words(predator,
 563                                         predator->rlw.running_len);
 564                         } else {
 565                                 size_t index;
 566                                 int negate_words;
 567
 568                                 negate_words = (&rlw_i != prey);
 569                                 index = rlwit_discharge(prey, out,
 570                                         predator->rlw.running_len, negate_words);
 571                                 ewah_add_empty_words(out, negate_words,
 572                                         predator->rlw.running_len - index);
 573                                 rlwit_discard_first_words(predator,
 574                                         predator->rlw.running_len);
 575                         }
 576                 }
 577
 578                 literals = min_size(
 579                         rlw_i.rlw.literal_words,
 580                         rlw_j.rlw.literal_words);
 581
 582                 if (literals) {
 583                         size_t k;
 584
 585                         for (k = 0; k < literals; ++k) {
 586                                 ewah_add(out,
 587                                         rlw_i.buffer[rlw_i.literal_word_start + k] &
 588                                         ~(rlw_j.buffer[rlw_j.literal_word_start + k])
 589                                 );
 590                         }
 591
 592                         rlwit_discard_first_words(&rlw_i, literals);
 593                         rlwit_discard_first_words(&rlw_j, literals);
 594                 }
 595         }
 596
 597         if (rlwit_word_size(&rlw_i) > 0)
 598                 rlwit_discharge(&rlw_i, out, ~0, 0);
 599         else
 600                 rlwit_discharge_empty(&rlw_j, out);
 601
 602         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 603 }
 604
 605 void ewah_or(
 606         struct ewah_bitmap *ewah_i,
 607         struct ewah_bitmap *ewah_j,
 608         struct ewah_bitmap *out)
 609 {
 610         struct rlw_iterator rlw_i;
 611         struct rlw_iterator rlw_j;
 612         size_t literals;
 613
 614         rlwit_init(&rlw_i, ewah_i);
 615         rlwit_init(&rlw_j, ewah_j);
 616
 617         while (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {
 618                 while (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {
 619                         struct rlw_iterator *prey, *predator;
 620
 621                         if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {
 622                                 prey = &rlw_i;
 623                                 predator = &rlw_j;
 624                         } else {
 625                                 prey = &rlw_j;
 626                                 predator = &rlw_i;
 627                         }
 628
 629                         if (predator->rlw.running_bit) {
 630                                 ewah_add_empty_words(out, 0,
 631                                         predator->rlw.running_len);
 632                                 rlwit_discard_first_words(prey,
 633                                         predator->rlw.running_len);
 634                                 rlwit_discard_first_words(predator,
 635                                         predator->rlw.running_len);
 636                         } else {
 637                                 size_t index = rlwit_discharge(prey, out,
 638                                         predator->rlw.running_len, 0);
 639                                 ewah_add_empty_words(out, 0,
 640                                         predator->rlw.running_len - index);
 641                                 rlwit_discard_first_words(predator,
 642                                         predator->rlw.running_len);
 643                         }
 644                 }
 645
 646                 literals = min_size(
 647                         rlw_i.rlw.literal_words,
 648                         rlw_j.rlw.literal_words);
 649
 650                 if (literals) {
 651                         size_t k;
 652
 653                         for (k = 0; k < literals; ++k) {
 654                                 ewah_add(out,
 655                                         rlw_i.buffer[rlw_i.literal_word_start + k] |
 656                                         rlw_j.buffer[rlw_j.literal_word_start + k]
 657                                 );
 658                         }
 659
 660                         rlwit_discard_first_words(&rlw_i, literals);
 661                         rlwit_discard_first_words(&rlw_j, literals);
 662                 }
 663         }
 664
 665         if (rlwit_word_size(&rlw_i) > 0)
 666                 rlwit_discharge(&rlw_i, out, ~0, 0);
 667         else
 668                 rlwit_discharge(&rlw_j, out, ~0, 0);
 669
 670         out->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);
 671 }
 672
 673
 674 #define BITMAP_POOL_MAX 16
 675 static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
 676 static size_t bitmap_pool_size;
 677
 678 struct ewah_bitmap *ewah_pool_new(void)
 679 {
 680         if (bitmap_pool_size)
 681                 return bitmap_pool[--bitmap_pool_size];
 682
 683         return ewah_new();
 684 }
 685
 686 void ewah_pool_free(struct ewah_bitmap *self)
 687 {
 688         if (self == NULL)
 689                 return;
 690
 691         if (bitmap_pool_size == BITMAP_POOL_MAX ||
 692                 self->alloc_size == 0) {
 693                 ewah_free(self);
 694                 return;
 695         }
 696
 697         ewah_clear(self);
 698         bitmap_pool[bitmap_pool_size++] = self;
 699 }
 700
 701 uint32_t ewah_checksum(struct ewah_bitmap *self)
 702 {
 703         const uint8_t *p = (uint8_t *)self->buffer;
 704         uint32_t crc = (uint32_t)self->bit_size;
 705         size_t size = self->buffer_size * sizeof(eword_t);
 706
 707         while (size--)
 708                 crc = (crc << 5) - crc + (uint32_t)*p++;
 709
 710         return crc;
 711 }