• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

vigna / dsi-bitstream-rs / 13900776091

17 Mar 2025 01:33PM UTC coverage: 51.712% (-5.4%) from 57.076%
13900776091

push

github

zommiommy
fixed fuzz

55 of 63 new or added lines in 1 file covered. (87.3%)

352 existing lines in 17 files now uncovered.

1843 of 3564 relevant lines covered (51.71%)

1876724.76 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

67.61
/src/impls/bit_reader.rs
1
/*
2
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
3
 * SPDX-FileCopyrightText: 2023 Inria
4
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
5
 *
6
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7
 */
8

9
use core::convert::Infallible;
10
#[cfg(feature = "mem_dbg")]
11
use mem_dbg::{MemDbg, MemSize};
12
use std::error::Error;
13

14
use crate::codes::params::{DefaultReadParams, ReadParams};
15
use crate::traits::*;
16

17
/// An implementation of [`BitRead`] for a [`WordRead`] with word `u64` and of
18
/// [`BitSeek`] for a [`WordSeek`].
19
///
20
/// This implementation accesses randomly the underlying [`WordRead`] without
21
/// any buffering. It is usually slower than
22
/// [`BufBitReader`](crate::impls::BufBitReader).
23
///
24
/// The peek word is `u32`. The value returned by
25
/// [`peek_bits`](crate::traits::BitRead::peek_bits) contains at least 32 bits
26
/// (extended with zeros beyond end of stream), that is, a full peek word.
27
///
28
/// The additional type parameter `RP` is used to select the parameters for the
29
/// instantanous codes, but the casual user should be happy with the default
30
/// value. See [`ReadParams`] for more details.
31
///
32
/// For additional flexibility, this structures implements [`std::io::Read`].
33
/// Note that because of coherence rules it is not possible to implement
34
/// [`std::io::Read`] for a generic [`BitRead`].
35

36
#[derive(Debug, Clone)]
37
#[cfg_attr(feature = "mem_dbg", derive(MemDbg, MemSize))]
38
pub struct BitReader<E: Endianness, WR, RP: ReadParams = DefaultReadParams> {
39
    /// The stream which we will read words from.
40
    data: WR,
41
    /// The index of the current bit.
42
    bit_index: u64,
43
    _marker: core::marker::PhantomData<(E, RP)>,
44
}
45

46
impl<E: Endianness, WR, RP: ReadParams> BitReader<E, WR, RP> {
47
    pub fn new(data: WR) -> Self {
938✔
48
        check_tables(32);
938✔
49
        Self {
50
            data,
51
            bit_index: 0,
52
            _marker: core::marker::PhantomData,
53
        }
54
    }
55
}
56

57
impl<
58
        E: Error + Send + Sync + 'static,
59
        WR: WordRead<Error = E, Word = u64> + WordSeek<Error = E>,
60
        RP: ReadParams,
61
    > BitRead<BE> for BitReader<BE, WR, RP>
62
{
63
    type Error = <WR as WordRead>::Error;
64
    type PeekWord = u32;
65

66
    #[inline]
UNCOV
67
    fn skip_bits(&mut self, n_bits: usize) -> Result<(), Self::Error> {
×
UNCOV
68
        self.bit_index += n_bits as u64;
×
UNCOV
69
        Ok(())
×
70
    }
71

72
    #[inline]
73
    fn read_bits(&mut self, n_bits: usize) -> Result<u64, Self::Error> {
2,497✔
74
        if n_bits == 0 {
2,497✔
75
            return Ok(0);
12✔
76
        }
77

78
        assert!(n_bits <= 64);
2,485✔
79

80
        self.data.set_word_pos(self.bit_index / 64)?;
2,485✔
81
        let in_word_offset = (self.bit_index % 64) as usize;
2,485✔
82

83
        let res = if (in_word_offset + n_bits) <= 64 {
2,485✔
84
            // single word access
85
            let word = self.data.read_word()?.to_be();
4,180✔
86
            (word << in_word_offset) >> (64 - n_bits)
×
87
        } else {
88
            // double word access
89
            let high_word = self.data.read_word()?.to_be();
790✔
90
            let low_word = self.data.read_word()?.to_be();
395✔
91
            let shamt1 = 64 - n_bits;
×
92
            let shamt2 = 128 - in_word_offset - n_bits;
×
93
            ((high_word << in_word_offset) >> shamt1) | (low_word >> shamt2)
×
94
        };
95
        self.bit_index += n_bits as u64;
×
96
        Ok(res)
×
97
    }
98

99
    #[inline]
100
    fn peek_bits(&mut self, n_bits: usize) -> Result<u32, Self::Error> {
66✔
101
        if n_bits == 0 {
66✔
102
            return Ok(0);
×
103
        }
104

105
        assert!(n_bits <= 32);
66✔
106

107
        self.data.set_word_pos(self.bit_index / 64)?;
66✔
108
        let in_word_offset = (self.bit_index % 64) as usize;
66✔
109

110
        let res = if (in_word_offset + n_bits) <= 64 {
66✔
111
            // single word access
112
            let word = self.data.read_word()?.to_be();
128✔
113
            (word << in_word_offset) >> (64 - n_bits)
×
114
        } else {
115
            // double word access
116
            let high_word = self.data.read_word()?.to_be();
4✔
117
            let low_word = self.data.read_word()?.to_be();
2✔
118
            let shamt1 = 64 - n_bits;
×
119
            let shamt2 = 128 - in_word_offset - n_bits;
×
120
            ((high_word << in_word_offset) >> shamt1) | (low_word >> shamt2)
×
121
        };
122
        Ok(res as u32)
×
123
    }
124

125
    #[inline]
126
    fn read_unary(&mut self) -> Result<u64, Self::Error> {
814✔
127
        self.data.set_word_pos(self.bit_index / 64)?;
814✔
128
        let in_word_offset = self.bit_index % 64;
814✔
129
        let mut bits_in_word = 64 - in_word_offset;
814✔
130
        let mut total = 0;
814✔
131

132
        let mut word = self.data.read_word()?.to_be();
814✔
133
        word <<= in_word_offset;
×
134
        loop {
×
135
            let zeros = word.leading_zeros() as u64;
7,087✔
136
            // the unary code fits in the word
137
            if zeros < bits_in_word {
7,087✔
138
                self.bit_index += total + zeros + 1;
814✔
139
                return Ok(total + zeros);
814✔
140
            }
141
            total += bits_in_word;
6,273✔
142
            bits_in_word = 64;
6,273✔
143
            word = self.data.read_word()?.to_be();
12,546✔
144
        }
145
    }
146

147
    #[inline(always)]
148
    fn skip_bits_after_peek(&mut self, n: usize) {
10✔
149
        self.bit_index += n as u64;
10✔
150
    }
151
}
152

153
impl<WR: WordSeek, RP: ReadParams> BitSeek for BitReader<LE, WR, RP> {
154
    type Error = Infallible;
155

156
    fn bit_pos(&mut self) -> Result<u64, Self::Error> {
3,225✔
157
        Ok(self.bit_index)
3,225✔
158
    }
159

160
    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
×
161
        self.bit_index = bit_index;
×
UNCOV
162
        Ok(())
×
163
    }
164
}
165

166
impl<WR: WordSeek, RP: ReadParams> BitSeek for BitReader<BE, WR, RP> {
167
    type Error = Infallible;
168

169
    fn bit_pos(&mut self) -> Result<u64, Self::Error> {
3,225✔
170
        Ok(self.bit_index)
3,225✔
171
    }
172

173
    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
×
174
        self.bit_index = bit_index;
×
UNCOV
175
        Ok(())
×
176
    }
177
}
178

179
impl<
180
        E: Error + Send + Sync + 'static,
181
        WR: WordRead<Error = E, Word = u64> + WordSeek<Error = E>,
182
        RP: ReadParams,
183
    > BitRead<LE> for BitReader<LE, WR, RP>
184
{
185
    type Error = <WR as WordRead>::Error;
186
    type PeekWord = u32;
187

188
    #[inline]
UNCOV
189
    fn skip_bits(&mut self, n_bits: usize) -> Result<(), Self::Error> {
×
UNCOV
190
        self.bit_index += n_bits as u64;
×
UNCOV
191
        Ok(())
×
192
    }
193

194
    #[inline]
195
    fn read_bits(&mut self, n_bits: usize) -> Result<u64, Self::Error> {
2,497✔
196
        #[cfg(feature = "checks")]
197
        assert!(n_bits <= 64);
2,497✔
198

199
        if n_bits == 0 {
2,497✔
200
            return Ok(0);
12✔
201
        }
202

203
        self.data.set_word_pos(self.bit_index / 64)?;
2,485✔
204
        let in_word_offset = (self.bit_index % 64) as usize;
2,485✔
205

206
        let res = if (in_word_offset + n_bits) <= 64 {
2,485✔
207
            // single word access
208
            let word = self.data.read_word()?.to_le();
4,180✔
209
            let shamt = 64 - n_bits;
×
UNCOV
210
            (word << (shamt - in_word_offset)) >> shamt
×
211
        } else {
212
            // double word access
213
            let low_word = self.data.read_word()?.to_le();
790✔
214
            let high_word = self.data.read_word()?.to_le();
395✔
215
            let shamt1 = 128 - in_word_offset - n_bits;
×
216
            let shamt2 = 64 - n_bits;
×
UNCOV
217
            ((high_word << shamt1) >> shamt2) | (low_word >> in_word_offset)
×
218
        };
219
        self.bit_index += n_bits as u64;
×
UNCOV
220
        Ok(res)
×
221
    }
222

223
    #[inline]
224
    fn peek_bits(&mut self, n_bits: usize) -> Result<u32, Self::Error> {
66✔
225
        if n_bits == 0 {
66✔
UNCOV
226
            return Ok(0);
×
227
        }
228

229
        assert!(n_bits <= 32);
66✔
230

231
        self.data.set_word_pos(self.bit_index / 64)?;
66✔
232
        let in_word_offset = (self.bit_index % 64) as usize;
66✔
233

234
        let res = if (in_word_offset + n_bits) <= 64 {
66✔
235
            // single word access
236
            let word = self.data.read_word()?.to_le();
128✔
237
            let shamt = 64 - n_bits;
×
UNCOV
238
            (word << (shamt - in_word_offset)) >> shamt
×
239
        } else {
240
            // double word access
241
            let low_word = self.data.read_word()?.to_le();
4✔
242
            let high_word = self.data.read_word()?.to_le();
2✔
243
            let shamt1 = 128 - in_word_offset - n_bits;
×
244
            let shamt2 = 64 - n_bits;
×
UNCOV
245
            ((high_word << shamt1) >> shamt2) | (low_word >> in_word_offset)
×
246
        };
UNCOV
247
        Ok(res as u32)
×
248
    }
249

250
    #[inline]
251
    fn read_unary(&mut self) -> Result<u64, Self::Error> {
814✔
252
        self.data.set_word_pos(self.bit_index / 64)?;
814✔
253
        let in_word_offset = self.bit_index % 64;
814✔
254
        let mut bits_in_word = 64 - in_word_offset;
814✔
255
        let mut total = 0;
814✔
256

257
        let mut word = self.data.read_word()?.to_le();
814✔
258
        word >>= in_word_offset;
×
UNCOV
259
        loop {
×
260
            let zeros = word.trailing_zeros() as u64;
7,087✔
261
            // the unary code fits in the word
262
            if zeros < bits_in_word {
7,087✔
263
                self.bit_index += total + zeros + 1;
814✔
264
                return Ok(total + zeros);
814✔
265
            }
266
            total += bits_in_word;
6,273✔
267
            bits_in_word = 64;
6,273✔
268
            word = self.data.read_word()?.to_le();
12,546✔
269
        }
270
    }
271

272
    #[inline(always)]
273
    fn skip_bits_after_peek(&mut self, n: usize) {
10✔
274
        self.bit_index += n as u64;
10✔
275
    }
276
}
277

278
impl<
279
        E: Error + Send + Sync + 'static,
280
        WR: WordRead<Error = E, Word = u64> + WordSeek<Error = E>,
281
        RP: ReadParams,
282
    > std::io::Read for BitReader<LE, WR, RP>
283
{
284
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
7✔
285
        let mut iter = buf.chunks_exact_mut(8);
7✔
286

287
        for chunk in &mut iter {
33✔
288
            let word = self
26✔
289
                .read_bits(64)
290
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
26✔
UNCOV
291
            chunk.copy_from_slice(&word.to_le_bytes());
×
292
        }
293

294
        let rem = iter.into_remainder();
7✔
295
        if !rem.is_empty() {
7✔
296
            let word = self
12✔
297
                .read_bits(rem.len() * 8)
6✔
298
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
6✔
UNCOV
299
            rem.copy_from_slice(&word.to_le_bytes()[..rem.len()]);
×
300
        }
301

302
        Ok(buf.len())
7✔
303
    }
304
}
305

306
impl<
307
        E: Error + Send + Sync + 'static,
308
        WR: WordRead<Error = E, Word = u64> + WordSeek<Error = E>,
309
        RP: ReadParams,
310
    > std::io::Read for BitReader<BE, WR, RP>
311
{
312
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
7✔
313
        let mut iter = buf.chunks_exact_mut(8);
7✔
314

315
        for chunk in &mut iter {
33✔
316
            let word = self
26✔
317
                .read_bits(64)
318
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
26✔
UNCOV
319
            chunk.copy_from_slice(&word.to_be_bytes());
×
320
        }
321

322
        let rem = iter.into_remainder();
7✔
323
        if !rem.is_empty() {
7✔
324
            let word = self
12✔
325
                .read_bits(rem.len() * 8)
6✔
326
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
6✔
UNCOV
327
            rem.copy_from_slice(&word.to_be_bytes()[8 - rem.len()..]);
×
328
        }
329

330
        Ok(buf.len())
7✔
331
    }
332
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc