Reverse Reader

[mpetri]

for a specific application I require to read the written bits in reverse order. What would be the easiest way to accomplish this?

Write a BitReaderReverse class with a custom BitQueue?

[tuffy]

It probably makes the most sense to implement them as different endianness types, like BigEndianReversed and LittleEndianReversed. The endianness implementations can push and pop values into and out of a bitqueue any way they'd like, and you'd get both a reader and writer for free.

All the numeric types do have a reverse_bits method which could make this relatively straightforward. Unfortunately, it's a nightly-only experimental API for now.

[mpetri]

Hmm, I think I have expressed this incorrectly. What I'm interested in doing is

let mut buf: Vec<u8> = Vec::new();
let a: u32 = 123;
let b: u32 = 4321;
let c: u32 = 5;
let d: u32 = 12;
let e: u32 = 1;
let f: u32 = 0;
{
    let mut writer = BitWriter::endian(&mut buf, BigEndian);

    writer.write(7, a).unwrap();
    writer.write(13, b).unwrap();
    writer.write(3, c).unwrap();
    writer.write(4, d).unwrap();
    writer.write(1, e).unwrap();
    writer.write(1, f).unwrap();
}
let mut cursor = Cursor::new(&buf);
cursor.seek(SeekFrom::End(0))?;
{
    
    let mut reader = BitReaderBackToFront::endian(&mut cursor, BigEndian);

    let recover_f: u32 = reader.read(1).unwrap();
    let recover_e: u32 = reader.read(1).unwrap();
    let recover_d: u32 = reader.read(4).unwrap();
    let recover_c: u32 = reader.read(3).unwrap();
    let recover_b: u32 = reader.read(13).unwrap();
    let recover_a: u32 = reader.read(7).unwrap();

    assert_eq!(a, recover_a);
    assert_eq!(b, recover_b);
    assert_eq!(c, recover_c);
    assert_eq!(d, recover_d);
    assert_eq!(e, recover_e);
    assert_eq!(f, recover_f);
}

So I want to seek to the end of the buffer and read the things I have written in reverse order.

The use case for this is a new kind of entropy coder (ANS) which recovers the encoded sequence by processing the written bits in reverse order they are written to the output stream.

[tuffy]

Yes, I see what you mean. In that instance, you're definitely going to overhaul how the reader processes the stream's input, turning it into more of a bit stack. Having some sort of reversible byte source for the reader would make life easier, but even then the internal queue will need to be consumed in the opposite order.

It's a tough nut to crack that I'm still pondering an efficient solution to accomplish.

[tuffy]

After giving it a bit more thought, simply reversing the endianness should be sufficient once the byte stream is reversed in order to pop off values in the opposite order. The difficulty is coming up with an implementation of Read that traverses the stream backwards - assuming it's not feasible to simply read in the whole file to a buffer and reverse it that way. It appears Crates.io has an old buggy reverse IO implementation and one that returns chunks in reverse order (though the chunks themselves would need reversing), but neither is exactly what you need.

use bitstream_io::{BigEndian, BitReader, BitWriter, LittleEndian};
use std::io;

fn main() -> Result<(), io::Error> {
    let mut data = Vec::new();

    {
        let mut w = BitWriter::endian(&mut data, BigEndian);
        w.write(2, 2)?;
        w.write(3, 6)?;
        w.write(5, 7)?;
        w.write(3, 5)?;
        w.write(19, 0x53BC1)?;
    }

    data.reverse();

    {
        let mut r = BitReader::endian(io::Cursor::new(&data), LittleEndian);
        assert_eq!(r.read::<u32>(19)?, 0x53BC1);
        assert_eq!(r.read::<u32>(3)?, 5);
        assert_eq!(r.read::<u32>(5)?, 7);
        assert_eq!(r.read::<u32>(3)?, 6);
        assert_eq!(r.read::<u32>(2)?, 2);
    }

    Ok(())
}