git.oblomov.eu Git - git/blob - ewah/ewah_rlw.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 int next_word(struct rlw_iterator *it)
  25 {
  26         if (it->pointer >= it->size)
  27                 return 0;
  28
  29         it->rlw.word = &it->buffer[it->pointer];
  30         it->pointer += rlw_get_literal_words(it->rlw.word) + 1;
  31
  32         it->rlw.literal_words = rlw_get_literal_words(it->rlw.word);
  33         it->rlw.running_len = rlw_get_running_len(it->rlw.word);
  34         it->rlw.running_bit = rlw_get_run_bit(it->rlw.word);
  35         it->rlw.literal_word_offset = 0;
  36
  37         return 1;
  38 }
  39
  40 void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *from_ewah)
  41 {
  42         it->buffer = from_ewah->buffer;
  43         it->size = from_ewah->buffer_size;
  44         it->pointer = 0;
  45
  46         next_word(it);
  47
  48         it->literal_word_start = rlwit_literal_words(it) +
  49                 it->rlw.literal_word_offset;
  50 }
  51
  52 void rlwit_discard_first_words(struct rlw_iterator *it, size_t x)
  53 {
  54         while (x > 0) {
  55                 size_t discard;
  56
  57                 if (it->rlw.running_len > x) {
  58                         it->rlw.running_len -= x;
  59                         return;
  60                 }
  61
  62                 x -= it->rlw.running_len;
  63                 it->rlw.running_len = 0;
  64
  65                 discard = (x > it->rlw.literal_words) ? it->rlw.literal_words : x;
  66
  67                 it->literal_word_start += discard;
  68                 it->rlw.literal_words -= discard;
  69                 x -= discard;
  70
  71                 if (x > 0 || rlwit_word_size(it) == 0) {
  72                         if (!next_word(it))
  73                                 break;
  74
  75                         it->literal_word_start =
  76                                 rlwit_literal_words(it) + it->rlw.literal_word_offset;
  77                 }
  78         }
  79 }
  80
  81 size_t rlwit_discharge(
  82         struct rlw_iterator *it, struct ewah_bitmap *out, size_t max, int negate)
  83 {
  84         size_t index = 0;
  85
  86         while (index < max && rlwit_word_size(it) > 0) {
  87                 size_t pd, pl = it->rlw.running_len;
  88
  89                 if (index + pl > max)
  90                         pl = max - index;
  91
  92                 ewah_add_empty_words(out, it->rlw.running_bit ^ negate, pl);
  93                 index += pl;
  94
  95                 pd = it->rlw.literal_words;
  96                 if (pd + index > max)
  97                         pd = max - index;
  98
  99                 ewah_add_dirty_words(out,
 100                         it->buffer + it->literal_word_start, pd, negate);
 101
 102                 rlwit_discard_first_words(it, pd + pl);
 103                 index += pd;
 104         }
 105
 106         return index;
 107 }
 108
 109 void rlwit_discharge_empty(struct rlw_iterator *it, struct ewah_bitmap *out)
 110 {
 111         while (rlwit_word_size(it) > 0) {
 112                 ewah_add_empty_words(out, 0, rlwit_word_size(it));
 113                 rlwit_discard_first_words(it, rlwit_word_size(it));
 114         }
 115 }