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

vigna / dsi-bitstream-rs / 22241604103

20 Feb 2026 09:19PM UTC coverage: 53.913%. Remained the same
22241604103

push

github

vigna
Cosmetic changes

2108 of 3910 relevant lines covered (53.91%)

3096788.1 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
/// instantaneous 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
    #[must_use]
48
    pub fn new(data: WR) -> Self {
1,968✔
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
    const PEEK_BITS: usize = 32;
66

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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