msysGit-based Git for Windows 1.x was superseded by Git for Windows 2.x
[git/mingw/4msysgit.git] / ewah / ewah_rlw.c
blobc723f1aefd42113bf28162d5cd955e4bf5c36cd8
1 /**
2 * Copyright 2013, GitHub, Inc
3 * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
4 * David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
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.
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.
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.
20 #include "git-compat-util.h"
21 #include "ewok.h"
22 #include "ewok_rlw.h"
24 static inline int next_word(struct rlw_iterator *it)
26 if (it->pointer >= it->size)
27 return 0;
29 it->rlw.word = &it->buffer[it->pointer];
30 it->pointer += rlw_get_literal_words(it->rlw.word) + 1;
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;
37 return 1;
40 void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *from_ewah)
42 it->buffer = from_ewah->buffer;
43 it->size = from_ewah->buffer_size;
44 it->pointer = 0;
46 next_word(it);
48 it->literal_word_start = rlwit_literal_words(it) +
49 it->rlw.literal_word_offset;
52 void rlwit_discard_first_words(struct rlw_iterator *it, size_t x)
54 while (x > 0) {
55 size_t discard;
57 if (it->rlw.running_len > x) {
58 it->rlw.running_len -= x;
59 return;
62 x -= it->rlw.running_len;
63 it->rlw.running_len = 0;
65 discard = (x > it->rlw.literal_words) ? it->rlw.literal_words : x;
67 it->literal_word_start += discard;
68 it->rlw.literal_words -= discard;
69 x -= discard;
71 if (x > 0 || rlwit_word_size(it) == 0) {
72 if (!next_word(it))
73 break;
75 it->literal_word_start =
76 rlwit_literal_words(it) + it->rlw.literal_word_offset;
81 size_t rlwit_discharge(
82 struct rlw_iterator *it, struct ewah_bitmap *out, size_t max, int negate)
84 size_t index = 0;
86 while (index < max && rlwit_word_size(it) > 0) {
87 size_t pd, pl = it->rlw.running_len;
89 if (index + pl > max)
90 pl = max - index;
92 ewah_add_empty_words(out, it->rlw.running_bit ^ negate, pl);
93 index += pl;
95 pd = it->rlw.literal_words;
96 if (pd + index > max)
97 pd = max - index;
99 ewah_add_dirty_words(out,
100 it->buffer + it->literal_word_start, pd, negate);
102 rlwit_discard_first_words(it, pd + pl);
103 index += pd;
106 return index;
109 void rlwit_discharge_empty(struct rlw_iterator *it, struct ewah_bitmap *out)
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));