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

vigna / dsi-bitstream-rs / 12468275135

23 Dec 2024 02:21PM UTC coverage: 57.076% (-1.8%) from 58.86%
12468275135

push

github

zommiommy
Fixed issue #18 and applied clippy fixes from new version

3 of 4 new or added lines in 3 files covered. (75.0%)

77 existing lines in 10 files now uncovered.

1835 of 3215 relevant lines covered (57.08%)

2945514.46 hits per line

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

69.01
/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]
67
    fn skip_bits(&mut self, n_bits: usize) -> Result<(), Self::Error> {
91✔
68
        self.bit_index += n_bits as u64;
91✔
69
        Ok(())
91✔
70
    }
71

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

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

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

83
        let res = if (in_word_offset + n_bits) <= 64 {
2,000✔
84
            // single word access
85
            let word = self.data.read_word()?.to_be();
3,196✔
UNCOV
86
            (word << in_word_offset) >> (64 - n_bits)
×
87
        } else {
88
            // double word access
89
            let high_word = self.data.read_word()?.to_be();
804✔
90
            let low_word = self.data.read_word()?.to_be();
402✔
UNCOV
91
            let shamt1 = 64 - n_bits;
×
UNCOV
92
            let shamt2 = 128 - in_word_offset - n_bits;
×
UNCOV
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> {
362✔
101
        if n_bits == 0 {
362✔
102
            return Ok(0);
×
103
        }
104

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

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

110
        let res = if (in_word_offset + n_bits) <= 64 {
362✔
111
            // single word access
112
            let word = self.data.read_word()?.to_be();
720✔
UNCOV
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✔
UNCOV
118
            let shamt1 = 64 - n_bits;
×
UNCOV
119
            let shamt2 = 128 - in_word_offset - n_bits;
×
UNCOV
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> {
771✔
127
        self.data.set_word_pos(self.bit_index / 64)?;
771✔
128
        let in_word_offset = self.bit_index % 64;
771✔
129
        let mut bits_in_word = 64 - in_word_offset;
771✔
130
        let mut total = 0;
771✔
131

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

147
    fn skip_bits_after_table_lookup(&mut self, n: usize) {
×
148
        self.bit_index += n as u64;
×
149
    }
150
}
151

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

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

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

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

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

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

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

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

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

198
        if n_bits == 0 {
2,011✔
199
            return Ok(0);
11✔
200
        }
201

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

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

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

228
        assert!(n_bits <= 32);
362✔
229

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

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

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

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

271
    fn skip_bits_after_table_lookup(&mut self, n: usize) {
×
272
        self.bit_index += n as u64;
×
273
    }
274
}
275

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

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

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

300
        Ok(buf.len())
8✔
301
    }
302
}
303

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

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

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

328
        Ok(buf.len())
8✔
329
    }
330
}
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