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 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 40void 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 52void 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 81size_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 109void 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}