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

vigna / dsi-bitstream-rs / 22237719643

20 Feb 2026 07:16PM UTC coverage: 54.824% (-0.5%) from 55.302%
22237719643

push

github

vigna
Cosmetic changes

2108 of 3845 relevant lines covered (54.82%)

3125840.71 hits per line

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

88.65
/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
use core::error::Error;
11
#[cfg(feature = "mem_dbg")]
12
use mem_dbg::{MemDbg, MemSize};
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 {
1,968✔
48
        Self {
49
            data,
50
            bit_index: 0,
51
            _marker: core::marker::PhantomData,
52
        }
53
    }
54
}
55

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

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

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

78
        assert!(n_bits <= 64);
59,764✔
79

80
        self.data.set_word_pos(self.bit_index / 64)?;
89,646✔
81
        let in_word_offset = (self.bit_index % 64) as usize;
59,764✔
82

83
        let res = if (in_word_offset + n_bits) <= 64 {
59,764✔
84
            // single word access
85
            let word = self.data.read_word()?.to_be();
91,232✔
86
            (word << in_word_offset) >> (64 - n_bits)
22,808✔
87
        } else {
88
            // double word access
89
            let high_word = self.data.read_word()?.to_be();
28,296✔
90
            let low_word = self.data.read_word()?.to_be();
28,296✔
91
            let shamt1 = 64 - n_bits;
14,148✔
92
            let shamt2 = 128 - in_word_offset - n_bits;
14,148✔
93
            ((high_word << in_word_offset) >> shamt1) | (low_word >> shamt2)
14,148✔
94
        };
95
        self.bit_index += n_bits as u64;
29,882✔
96
        Ok(res)
29,882✔
97
    }
98

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

105
        assert!(n_bits <= 32);
12,642✔
106

107
        self.data.set_word_pos(self.bit_index / 64)?;
18,963✔
108
        let in_word_offset = (self.bit_index % 64) as usize;
12,642✔
109

110
        let res = if (in_word_offset + n_bits) <= 64 {
12,642✔
111
            // single word access
112
            let word = self.data.read_word()?.to_be();
23,096✔
113
            (word << in_word_offset) >> (64 - n_bits)
5,774✔
114
        } else {
115
            // double word access
116
            let high_word = self.data.read_word()?.to_be();
2,188✔
117
            let low_word = self.data.read_word()?.to_be();
2,188✔
118
            let shamt1 = 64 - n_bits;
1,094✔
119
            let shamt2 = 128 - in_word_offset - n_bits;
1,094✔
120
            ((high_word << in_word_offset) >> shamt1) | (low_word >> shamt2)
1,094✔
121
        };
122
        Ok(res as u32)
6,321✔
123
    }
124

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

132
        let mut word = self.data.read_word()?.to_be();
26,856✔
133
        word <<= in_word_offset;
6,714✔
134
        loop {
×
135
            let zeros = word.leading_zeros() as u64;
133,642✔
136
            // the unary code fits in the word
137
            if zeros < bits_in_word {
66,821✔
138
                self.bit_index += total + zeros + 1;
6,714✔
139
                return Ok(total + zeros);
6,714✔
140
            }
141
            total += bits_in_word;
60,107✔
142
            bits_in_word = 64;
60,107✔
143
            word = self.data.read_word()?.to_be();
180,321✔
144
        }
145
    }
146

147
    #[inline(always)]
148
    fn skip_bits_after_peek(&mut self, n: usize) {
3,209✔
149
        self.bit_index += n as u64;
3,209✔
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> {
36,143✔
157
        Ok(self.bit_index)
36,143✔
158
    }
159

160
    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
×
161
        self.bit_index = bit_index;
×
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> {
36,143✔
170
        Ok(self.bit_index)
36,143✔
171
    }
172

173
    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
×
174
        self.bit_index = bit_index;
×
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
    const PEEK_BITS: usize = 32;
188

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

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

200
        if n_bits == 0 {
30,141✔
201
            return Ok(0);
259✔
202
        }
203

204
        self.data.set_word_pos(self.bit_index / 64)?;
89,646✔
205
        let in_word_offset = (self.bit_index % 64) as usize;
59,764✔
206

207
        let res = if (in_word_offset + n_bits) <= 64 {
59,764✔
208
            // single word access
209
            let word = self.data.read_word()?.to_le();
91,232✔
210
            let shamt = 64 - n_bits;
45,616✔
211
            (word << (shamt - in_word_offset)) >> shamt
45,616✔
212
        } else {
213
            // double word access
214
            let low_word = self.data.read_word()?.to_le();
28,296✔
215
            let high_word = self.data.read_word()?.to_le();
28,296✔
216
            let shamt1 = 128 - in_word_offset - n_bits;
14,148✔
217
            let shamt2 = 64 - n_bits;
14,148✔
218
            ((high_word << shamt1) >> shamt2) | (low_word >> in_word_offset)
14,148✔
219
        };
220
        self.bit_index += n_bits as u64;
29,882✔
221
        Ok(res)
29,882✔
222
    }
223

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

230
        assert!(n_bits <= 32);
12,642✔
231

232
        self.data.set_word_pos(self.bit_index / 64)?;
18,963✔
233
        let in_word_offset = (self.bit_index % 64) as usize;
12,642✔
234

235
        let res = if (in_word_offset + n_bits) <= 64 {
12,642✔
236
            // single word access
237
            let word = self.data.read_word()?.to_le();
23,096✔
238
            let shamt = 64 - n_bits;
11,548✔
239
            (word << (shamt - in_word_offset)) >> shamt
11,548✔
240
        } else {
241
            // double word access
242
            let low_word = self.data.read_word()?.to_le();
2,188✔
243
            let high_word = self.data.read_word()?.to_le();
2,188✔
244
            let shamt1 = 128 - in_word_offset - n_bits;
1,094✔
245
            let shamt2 = 64 - n_bits;
1,094✔
246
            ((high_word << shamt1) >> shamt2) | (low_word >> in_word_offset)
1,094✔
247
        };
248
        Ok(res as u32)
6,321✔
249
    }
250

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

258
        let mut word = self.data.read_word()?.to_le();
26,856✔
259
        word >>= in_word_offset;
6,714✔
260
        loop {
×
261
            let zeros = word.trailing_zeros() as u64;
133,642✔
262
            // the unary code fits in the word
263
            if zeros < bits_in_word {
66,821✔
264
                self.bit_index += total + zeros + 1;
6,714✔
265
                return Ok(total + zeros);
6,714✔
266
            }
267
            total += bits_in_word;
60,107✔
268
            bits_in_word = 64;
60,107✔
269
            word = self.data.read_word()?.to_le();
180,321✔
270
        }
271
    }
272

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

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

289
        for chunk in &mut iter {
2,198✔
290
            let word = self
2,106✔
291
                .read_bits(64)
292
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
1,053✔
293
            chunk.copy_from_slice(&word.to_le_bytes());
3,159✔
294
        }
295

296
        let rem = iter.into_remainder();
3,435✔
297
        if !rem.is_empty() {
1,145✔
298
            let word = self
2,172✔
299
                .read_bits(rem.len() * 8)
2,172✔
300
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
1,086✔
301
            rem.copy_from_slice(&word.to_le_bytes()[..rem.len()]);
4,344✔
302
        }
303

304
        Ok(buf.len())
1,145✔
305
    }
306
}
307

308
#[cfg(feature = "std")]
309
impl<
310
    E: Error + Send + Sync + 'static,
311
    WR: WordRead<Error = E, Word = u64> + WordSeek<Error = E>,
312
    RP: ReadParams,
313
> std::io::Read for BitReader<BE, WR, RP>
314
{
315
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
1,145✔
316
        let mut iter = buf.chunks_exact_mut(8);
3,435✔
317

318
        for chunk in &mut iter {
2,198✔
319
            let word = self
2,106✔
320
                .read_bits(64)
321
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
1,053✔
322
            chunk.copy_from_slice(&word.to_be_bytes());
3,159✔
323
        }
324

325
        let rem = iter.into_remainder();
3,435✔
326
        if !rem.is_empty() {
1,145✔
327
            let word = self
2,172✔
328
                .read_bits(rem.len() * 8)
2,172✔
329
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
1,086✔
330
            rem.copy_from_slice(&word.to_be_bytes()[8 - rem.len()..]);
4,344✔
331
        }
332

333
        Ok(buf.len())
1,145✔
334
    }
335
}
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