]>
Commit | Line | Data |
---|---|---|
e1273106 VM |
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 | } |