Andrew's git - gitweb.git/blob

fcd465e9c24ef992b156a5242faabaf7272003be
   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        self->buffer = xrealloc(self->buffer,
  43                self->alloc_size * sizeof(eword_t));
  44        self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
  45}
  46
  47static 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
  55static 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
  61static 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
 100size_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
 109static 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
 130void 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
 166static 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
 198size_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
 211void 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
 248void 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
 281struct 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
 293void 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
 301void 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
 312static 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
 338int 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
 365void 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
 381void 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
 400void 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
 464void 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
 532void 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
 605void 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
 675static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];
 676static size_t bitmap_pool_size;
 677
 678struct 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
 686void 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
 701uint32_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}