22518245728

Committed 28 Feb 2026 09:40AM UTC coverage: 57.751% (+3.1%) from 54.618%

Build # 22518245728

Build Type

push

github

Committed by

vigna

Commit Message

delta_gamma in filenames

Run Details

2213 of 3832 relevant lines covered (57.75%)

2595204.38 hits per line

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

90.44

/src/impls/bit_reader.rs

/*
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 * SPDX-FileCopyrightText: 2023 Inria
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use core::convert::Infallible;
#[cfg(feature = "mem_dbg")]
use mem_dbg::{MemDbg, MemSize};

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

/// An implementation of [`BitRead`] for a [`WordRead`] with word `u64` and of
/// [`BitSeek`] for a [`WordSeek`].
///
/// This implementation randomly accesses the underlying [`WordRead`] without
/// any buffering. It is usually slower than
/// [`BufBitReader`](crate::impls::BufBitReader).
///
/// The peek word is `u32`. The value returned by
/// [`peek_bits`](crate::traits::BitRead::peek_bits) contains at least 32 bits
/// (extended with zeros beyond end of stream), that is, a full peek word.
///
/// The additional type parameter `RP` is used to select the parameters for the
/// instantaneous codes, but the casual user should be happy with the default
/// value. See [`ReadParams`] for more details.
///
/// For additional flexibility, when the `std` feature is enabled, this
/// structure implements [`std::io::Read`]. Note that because of coherence
/// rules it is not possible to implement [`std::io::Read`] for a generic
/// [`BitRead`].

#[derive(Debug, Clone)]
#[cfg_attr(feature = "mem_dbg", derive(MemDbg, MemSize))]
pub struct BitReader<E: Endianness, WR, RP: ReadParams = DefaultReadParams> {
    /// The backend from which we will read words.
    backend: WR,
    /// The index of the current bit.
    bit_index: u64,
    _marker: core::marker::PhantomData<(E, RP)>,
}

impl<E: Endianness, WR, RP: ReadParams> BitReader<E, WR, RP> {
    /// Creates a new [`BitReader`] with the given word reader.
    #[must_use]
    pub fn new(backend: WR) -> Self {
        Self {
            backend,
            bit_index: 0,
            _marker: core::marker::PhantomData,
        }
    }
}

impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
    BitRead<BE> for BitReader<BE, WR, RP>
{
    type Error = <WR as WordRead>::Error;
    type PeekWord = u32;
    const PEEK_BITS: usize = 32;

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

    #[inline]
    fn read_bits(&mut self, num_bits: usize) -> Result<u64, Self::Error> {
        #[cfg(feature = "checks")]
        assert!(num_bits <= 64);

        if num_bits == 0 {
            return Ok(0);
        }

        self.backend.set_word_pos(self.bit_index / 64)?;
        let in_word_offset = (self.bit_index % 64) as usize;

        let res = if (in_word_offset + num_bits) <= 64 {
            // single word access
            let word = self.backend.read_word()?.to_be();
            (word << in_word_offset) >> (64 - num_bits)
        } else {
            // double word access
            let high_word = self.backend.read_word()?.to_be();
            let low_word = self.backend.read_word()?.to_be();
            let shamt1 = 64 - num_bits;
            let shamt2 = 128 - in_word_offset - num_bits;
            ((high_word << in_word_offset) >> shamt1) | (low_word >> shamt2)
        };
        self.bit_index += num_bits as u64;
        Ok(res)
    }

    #[inline]
    fn peek_bits(&mut self, n_bits: usize) -> Result<u32, Self::Error> {
        if n_bits == 0 {
            return Ok(0);
        }

        #[cfg(feature = "checks")]
        assert!(n_bits <= 32);

        self.backend.set_word_pos(self.bit_index / 64)?;
        let in_word_offset = (self.bit_index % 64) as usize;

        let res = if (in_word_offset + n_bits) <= 64 {
            // single word access
            let word = self.backend.read_word()?.to_be();
            (word << in_word_offset) >> (64 - n_bits)
        } else {
            // double word access
            let high_word = self.backend.read_word()?.to_be();
            let low_word = self.backend.read_word()?.to_be();
            let shamt1 = 64 - n_bits;
            let shamt2 = 128 - in_word_offset - n_bits;
            ((high_word << in_word_offset) >> shamt1) | (low_word >> shamt2)
        };
        Ok(res as u32)
    }

    #[inline]
    fn read_unary(&mut self) -> Result<u64, Self::Error> {
        self.backend.set_word_pos(self.bit_index / 64)?;
        let in_word_offset = self.bit_index % 64;
        let mut bits_in_word = 64 - in_word_offset;
        let mut total = 0;

        let mut word = self.backend.read_word()?.to_be();
        word <<= in_word_offset;
        loop {
            let zeros = word.leading_zeros() as u64;
            // the unary code fits in the word
            if zeros < bits_in_word {
                self.bit_index += total + zeros + 1;
                return Ok(total + zeros);
            }
            total += bits_in_word;
            bits_in_word = 64;
            word = self.backend.read_word()?.to_be();
        }
    }

    #[inline(always)]
    fn skip_bits_after_peek(&mut self, n: usize) {
        self.bit_index += n as u64;
    }
}

impl<E: Endianness, WR: WordSeek, RP: ReadParams> BitSeek for BitReader<E, WR, RP> {
    type Error = Infallible;

    fn bit_pos(&mut self) -> Result<u64, Self::Error> {
        Ok(self.bit_index)
    }

    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
        self.bit_index = bit_index;
        Ok(())
    }
}

impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
    BitRead<LE> for BitReader<LE, WR, RP>
{
    type Error = <WR as WordRead>::Error;
    type PeekWord = u32;
    const PEEK_BITS: usize = 32;

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

    #[inline]
    fn read_bits(&mut self, num_bits: usize) -> Result<u64, Self::Error> {
        #[cfg(feature = "checks")]
        assert!(num_bits <= 64);

        if num_bits == 0 {
            return Ok(0);
        }

        self.backend.set_word_pos(self.bit_index / 64)?;
        let in_word_offset = (self.bit_index % 64) as usize;

        let res = if (in_word_offset + num_bits) <= 64 {
            // single word access
            let word = self.backend.read_word()?.to_le();
            let shamt = 64 - num_bits;
            (word << (shamt - in_word_offset)) >> shamt
        } else {
            // double word access
            let low_word = self.backend.read_word()?.to_le();
            let high_word = self.backend.read_word()?.to_le();
            let shamt1 = 128 - in_word_offset - num_bits;
            let shamt2 = 64 - num_bits;
            ((high_word << shamt1) >> shamt2) | (low_word >> in_word_offset)
        };
        self.bit_index += num_bits as u64;
        Ok(res)
    }

    #[inline]
    fn peek_bits(&mut self, n_bits: usize) -> Result<u32, Self::Error> {
        if n_bits == 0 {
            return Ok(0);
        }

        #[cfg(feature = "checks")]
        assert!(n_bits <= 32);

        self.backend.set_word_pos(self.bit_index / 64)?;
        let in_word_offset = (self.bit_index % 64) as usize;

        let res = if (in_word_offset + n_bits) <= 64 {
            // single word access
            let word = self.backend.read_word()?.to_le();
            let shamt = 64 - n_bits;
            (word << (shamt - in_word_offset)) >> shamt
        } else {
            // double word access
            let low_word = self.backend.read_word()?.to_le();
            let high_word = self.backend.read_word()?.to_le();
            let shamt1 = 128 - in_word_offset - n_bits;
            let shamt2 = 64 - n_bits;
            ((high_word << shamt1) >> shamt2) | (low_word >> in_word_offset)
        };
        Ok(res as u32)
    }

    #[inline]
    fn read_unary(&mut self) -> Result<u64, Self::Error> {
        self.backend.set_word_pos(self.bit_index / 64)?;
        let in_word_offset = self.bit_index % 64;
        let mut bits_in_word = 64 - in_word_offset;
        let mut total = 0;

        let mut word = self.backend.read_word()?.to_le();
        word >>= in_word_offset;
        loop {
            let zeros = word.trailing_zeros() as u64;
            // the unary code fits in the word
            if zeros < bits_in_word {
                self.bit_index += total + zeros + 1;
                return Ok(total + zeros);
            }
            total += bits_in_word;
            bits_in_word = 64;
            word = self.backend.read_word()?.to_le();
        }
    }

    #[inline(always)]
    fn skip_bits_after_peek(&mut self, n: usize) {
        self.bit_index += n as u64;
    }
}

#[cfg(feature = "std")]
impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
    std::io::Read for BitReader<LE, WR, RP>
{
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
        let mut iter = buf.chunks_exact_mut(8);

        for chunk in &mut iter {
            let word = self
                .read_bits(64)
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
            chunk.copy_from_slice(&word.to_le_bytes());
        }

        let rem = iter.into_remainder();
        if !rem.is_empty() {
            let word = self
                .read_bits(rem.len() * 8)
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
            rem.copy_from_slice(&word.to_le_bytes()[..rem.len()]);
        }

        Ok(buf.len())
    }
}

#[cfg(feature = "std")]
impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
    std::io::Read for BitReader<BE, WR, RP>
{
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
        let mut iter = buf.chunks_exact_mut(8);

        for chunk in &mut iter {
            let word = self
                .read_bits(64)
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
            chunk.copy_from_slice(&word.to_be_bytes());
        }

        let rem = iter.into_remainder();
        if !rem.is_empty() {
            let word = self
                .read_bits(rem.len() * 8)
                .map_err(|_| std::io::ErrorKind::UnexpectedEof)?;
            rem.copy_from_slice(&word.to_be_bytes()[8 - rem.len()..]);
        }

        Ok(buf.len())
    }
}

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
13	use crate::codes::params::{DefaultReadParams, ReadParams};
14	use crate::traits::*;
15
16	/// An implementation of [`BitRead`] for a [`WordRead`] with word `u64` and of
17	/// [`BitSeek`] for a [`WordSeek`].
18	///
19	/// This implementation randomly accesses the underlying [`WordRead`] without
20	/// any buffering. It is usually slower than
21	/// [`BufBitReader`](crate::impls::BufBitReader).
22	///
23	/// The peek word is `u32`. The value returned by
24	/// [`peek_bits`](crate::traits::BitRead::peek_bits) contains at least 32 bits
25	/// (extended with zeros beyond end of stream), that is, a full peek word.
26	///
27	/// The additional type parameter `RP` is used to select the parameters for the
28	/// instantaneous codes, but the casual user should be happy with the default
29	/// value. See [`ReadParams`] for more details.
30	///
31	/// For additional flexibility, when the `std` feature is enabled, this
32	/// structure implements [`std::io::Read`]. Note that because of coherence
33	/// rules it is not possible to implement [`std::io::Read`] for a generic
34	/// [`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 backend from which we will read words.
40	backend: 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	/// Creates a new [`BitReader`] with the given word reader.
48	#[must_use]
49	pub fn new(backend: WR) -> Self {	1,968✔
50	Self {
51	backend,
52	bit_index: 0,
53	_marker: core::marker::PhantomData,
54	}
55	}
56	}
57
58	impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
59	BitRead<BE> for BitReader<BE, WR, RP>
60	{
61	type Error = <WR as WordRead>::Error;
62	type PeekWord = u32;
63	const PEEK_BITS: usize = 32;
64
65	#[inline]
66	fn skip_bits(&mut self, n_bits: usize) -> Result<(), Self::Error> {	×
67	self.bit_index += n_bits as u64;	×
68	Ok(())	×
69	}
70
71	#[inline]
72	fn read_bits(&mut self, num_bits: usize) -> Result<u64, Self::Error> {	26,994✔
73	#[cfg(feature = "checks")]
74	assert!(num_bits <= 64);	53,988✔
75
76	if num_bits == 0 {	26,994✔
77	return Ok(0);	261✔
78	}
79
80	self.backend.set_word_pos(self.bit_index / 64)?;	80,199✔
81	let in_word_offset = (self.bit_index % 64) as usize;	53,466✔
82
83	let res = if (in_word_offset + num_bits) <= 64 {	53,466✔
84	// single word access
85	let word = self.backend.read_word()?.to_be();	83,704✔
86	(word << in_word_offset) >> (64 - num_bits)	20,926✔
87	} else {
88	// double word access
89	let high_word = self.backend.read_word()?.to_be();	23,228✔
90	let low_word = self.backend.read_word()?.to_be();	23,228✔
91	let shamt1 = 64 - num_bits;	11,614✔
92	let shamt2 = 128 - in_word_offset - num_bits;	11,614✔
93	((high_word << in_word_offset) >> shamt1) \| (low_word >> shamt2)	11,614✔
94	};
95	self.bit_index += num_bits as u64;	26,733✔
96	Ok(res)	26,733✔
97	}
98
99	#[inline]
100	fn peek_bits(&mut self, n_bits: usize) -> Result<u32, Self::Error> {	4,724✔
101	if n_bits == 0 {	4,724✔
102	return Ok(0);	×
103	}
104
105	#[cfg(feature = "checks")]
106	assert!(n_bits <= 32);	9,448✔
107
108	self.backend.set_word_pos(self.bit_index / 64)?;	14,172✔
109	let in_word_offset = (self.bit_index % 64) as usize;	9,448✔
110
111	let res = if (in_word_offset + n_bits) <= 64 {	9,448✔
112	// single word access
113	let word = self.backend.read_word()?.to_be();	17,144✔
114	(word << in_word_offset) >> (64 - n_bits)	4,286✔
115	} else {
116	// double word access
117	let high_word = self.backend.read_word()?.to_be();	1,752✔
118	let low_word = self.backend.read_word()?.to_be();	1,752✔
119	let shamt1 = 64 - n_bits;	876✔
120	let shamt2 = 128 - in_word_offset - n_bits;	876✔
121	((high_word << in_word_offset) >> shamt1) \| (low_word >> shamt2)	876✔
122	};
123	Ok(res as u32)	4,724✔
124	}
125
126	#[inline]
127	fn read_unary(&mut self) -> Result<u64, Self::Error> {	6,352✔
128	self.backend.set_word_pos(self.bit_index / 64)?;	19,056✔
129	let in_word_offset = self.bit_index % 64;	12,704✔
130	let mut bits_in_word = 64 - in_word_offset;	12,704✔
131	let mut total = 0;	12,704✔
132
133	let mut word = self.backend.read_word()?.to_be();	25,408✔
134	word <<= in_word_offset;	6,352✔
135	loop {	×
136	let zeros = word.leading_zeros() as u64;	127,084✔
137	// the unary code fits in the word
138	if zeros < bits_in_word {	63,542✔
139	self.bit_index += total + zeros + 1;	6,352✔
140	return Ok(total + zeros);	6,352✔
141	}
142	total += bits_in_word;	57,190✔
143	bits_in_word = 64;	57,190✔
144	word = self.backend.read_word()?.to_be();	171,570✔
145	}
146	}
147
148	#[inline(always)]
149	fn skip_bits_after_peek(&mut self, n: usize) {	2,261✔
150	self.bit_index += n as u64;	2,261✔
151	}
152	}
153
154	impl<E: Endianness, WR: WordSeek, RP: ReadParams> BitSeek for BitReader<E, WR, RP> {
155	type Error = Infallible;
156
157	fn bit_pos(&mut self) -> Result<u64, Self::Error> {	64,076✔
158	Ok(self.bit_index)	64,076✔
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: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
168	BitRead<LE> for BitReader<LE, WR, RP>
169	{
170	type Error = <WR as WordRead>::Error;
171	type PeekWord = u32;
172	const PEEK_BITS: usize = 32;
173
174	#[inline]
175	fn skip_bits(&mut self, n_bits: usize) -> Result<(), Self::Error> {	×
176	self.bit_index += n_bits as u64;	×
177	Ok(())	×
178	}
179
180	#[inline]
181	fn read_bits(&mut self, num_bits: usize) -> Result<u64, Self::Error> {	26,994✔
182	#[cfg(feature = "checks")]
183	assert!(num_bits <= 64);	53,988✔
184
185	if num_bits == 0 {	26,994✔
186	return Ok(0);	261✔
187	}
188
189	self.backend.set_word_pos(self.bit_index / 64)?;	80,199✔
190	let in_word_offset = (self.bit_index % 64) as usize;	53,466✔
191
192	let res = if (in_word_offset + num_bits) <= 64 {	53,466✔
193	// single word access
194	let word = self.backend.read_word()?.to_le();	83,704✔
195	let shamt = 64 - num_bits;	41,852✔
196	(word << (shamt - in_word_offset)) >> shamt	41,852✔
197	} else {
198	// double word access
199	let low_word = self.backend.read_word()?.to_le();	23,228✔
200	let high_word = self.backend.read_word()?.to_le();	23,228✔
201	let shamt1 = 128 - in_word_offset - num_bits;	11,614✔
202	let shamt2 = 64 - num_bits;	11,614✔
203	((high_word << shamt1) >> shamt2) \| (low_word >> in_word_offset)	11,614✔
204	};
205	self.bit_index += num_bits as u64;	26,733✔
206	Ok(res)	26,733✔
207	}
208
209	#[inline]
210	fn peek_bits(&mut self, n_bits: usize) -> Result<u32, Self::Error> {	4,724✔
211	if n_bits == 0 {	4,724✔
212	return Ok(0);	×
213	}
214
215	#[cfg(feature = "checks")]
216	assert!(n_bits <= 32);	9,448✔
217
218	self.backend.set_word_pos(self.bit_index / 64)?;	14,172✔
219	let in_word_offset = (self.bit_index % 64) as usize;	9,448✔
220
221	let res = if (in_word_offset + n_bits) <= 64 {	9,448✔
222	// single word access
223	let word = self.backend.read_word()?.to_le();	17,144✔
224	let shamt = 64 - n_bits;	8,572✔
225	(word << (shamt - in_word_offset)) >> shamt	8,572✔
226	} else {
227	// double word access
228	let low_word = self.backend.read_word()?.to_le();	1,752✔
229	let high_word = self.backend.read_word()?.to_le();	1,752✔
230	let shamt1 = 128 - in_word_offset - n_bits;	876✔
231	let shamt2 = 64 - n_bits;	876✔
232	((high_word << shamt1) >> shamt2) \| (low_word >> in_word_offset)	876✔
233	};
234	Ok(res as u32)	4,724✔
235	}
236
237	#[inline]
238	fn read_unary(&mut self) -> Result<u64, Self::Error> {	6,352✔
239	self.backend.set_word_pos(self.bit_index / 64)?;	19,056✔
240	let in_word_offset = self.bit_index % 64;	12,704✔
241	let mut bits_in_word = 64 - in_word_offset;	12,704✔
242	let mut total = 0;	12,704✔
243
244	let mut word = self.backend.read_word()?.to_le();	25,408✔
245	word >>= in_word_offset;	6,352✔
246	loop {	×
247	let zeros = word.trailing_zeros() as u64;	127,084✔
248	// the unary code fits in the word
249	if zeros < bits_in_word {	63,542✔
250	self.bit_index += total + zeros + 1;	6,352✔
251	return Ok(total + zeros);	6,352✔
252	}
253	total += bits_in_word;	57,190✔
254	bits_in_word = 64;	57,190✔
255	word = self.backend.read_word()?.to_le();	171,570✔
256	}
257	}
258
259	#[inline(always)]
260	fn skip_bits_after_peek(&mut self, n: usize) {	2,261✔
261	self.bit_index += n as u64;	2,261✔
262	}
263	}
264
265	#[cfg(feature = "std")]
266	impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
267	std::io::Read for BitReader<LE, WR, RP>
268	{
269	fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {	854✔
270	let mut iter = buf.chunks_exact_mut(8);	2,562✔
271
272	for chunk in &mut iter {	1,542✔
273	let word = self	1,376✔
274	.read_bits(64)
275	.map_err(\|_\| std::io::ErrorKind::UnexpectedEof)?;	688✔
276	chunk.copy_from_slice(&word.to_le_bytes());	2,064✔
277	}
278
279	let rem = iter.into_remainder();	2,562✔
280	if !rem.is_empty() {	854✔
281	let word = self	1,624✔
282	.read_bits(rem.len() * 8)	1,624✔
283	.map_err(\|_\| std::io::ErrorKind::UnexpectedEof)?;	812✔
284	rem.copy_from_slice(&word.to_le_bytes()[..rem.len()]);	3,248✔
285	}
286
287	Ok(buf.len())	854✔
288	}
289	}
290
291	#[cfg(feature = "std")]
292	impl<WR: WordRead<Word = u64> + WordSeek<Error = <WR as WordRead>::Error>, RP: ReadParams>
293	std::io::Read for BitReader<BE, WR, RP>
294	{
295	fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {	854✔
296	let mut iter = buf.chunks_exact_mut(8);	2,562✔
297
298	for chunk in &mut iter {	1,542✔
299	let word = self	1,376✔
300	.read_bits(64)
301	.map_err(\|_\| std::io::ErrorKind::UnexpectedEof)?;	688✔
302	chunk.copy_from_slice(&word.to_be_bytes());	2,064✔
303	}
304
305	let rem = iter.into_remainder();	2,562✔
306	if !rem.is_empty() {	854✔
307	let word = self	1,624✔
308	.read_bits(rem.len() * 8)	1,624✔
309	.map_err(\|_\| std::io::ErrorKind::UnexpectedEof)?;	812✔
310	rem.copy_from_slice(&word.to_be_bytes()[8 - rem.len()..]);	3,248✔
311	}
312
313	Ok(buf.len())	854✔
314	}
315	}

vigna / dsi-bitstream-rs / 22518245728

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

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