Andrew's git - gitweb.git/blob - ewah/ewah

   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
  24static inline size_t min_size(size_t a, size_t b)
  25{
  26        return a < b ? a : b;
  27}
  28
  29static inline size_t max_size(size_t a, size_t b)
  30{
  31        return a > b ? a : b;
  32}
  33
  34static 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
  46static 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
  54static 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
  60static 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
  99size_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
 108static 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
 129void 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
 165static 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
 197size_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
 210void 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
 247void 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
 280struct 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
 292void 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
 300void 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
 311static 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
 337int 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
 364void 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
 380void 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
 399void 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
 463void 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
 531void 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
 604void 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
 674static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
 675static size_t bitmap_pool_size;
 676
 677struct 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
 685void 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
 700uint32_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}