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