Selecting bit order

[spacemeowx2]

I wanted to write a IEEE 802.11 frame parser, and I found that the bit order is not matched. So I have to define fields in reversed order.

I want to define fields in right order, so I can make less mistakes.

Here is the code:

use deku::prelude::*;
use deku::ctx::BitSize;

#[derive(Debug, DekuRead, DekuWrite, PartialEq)]
#[deku(type = "u8", bits = "2", ctx = "_bitsize: BitSize")]
pub enum FrameType {
    #[deku(id = "0")]
    Management,
    #[deku(id = "1")]
    Control,
    #[deku(id = "2")]
    Data,
}

#[derive(Debug, DekuRead, DekuWrite, PartialEq)]
pub struct Flags {
    #[deku(bits = 1)]
    pub order: u8,
    #[deku(bits = 1)]
    pub protected_frame: u8,
    #[deku(bits = 1)]
    pub more_data: u8,
    #[deku(bits = 1)]
    pub power_management: u8,
    #[deku(bits = 1)]
    pub retry: u8,
    #[deku(bits = 1)]
    pub more_fragments: u8,
    #[deku(bits = 1)]
    pub from_ds: u8,
    #[deku(bits = 1)]
    pub to_ds: u8,
}

#[derive(Debug, DekuRead, DekuWrite, PartialEq)]
pub struct FrameControl {
    #[deku(bits = 4)]
    pub sub_type: u8,
    #[deku(bits = 2)]
    pub frame_type: FrameType,
    #[deku(bits = 2)]
    pub protocol_version: u8,

    pub flags: Flags,
}

fn main() {
    let data = vec![0x88u8, 0x41];
    let (_, control_frame) = FrameControl::from_bytes((data.as_ref(), 0)).unwrap();
    assert_eq!(control_frame, FrameControl {
        protocol_version: 0,
        frame_type: FrameType::Data,
        sub_type: 8,

        flags: Flags {
            to_ds: 1,
            from_ds: 0,
            more_fragments: 0,
            retry: 0,
            power_management: 0,
            more_data: 0,
            protected_frame: 1,
            order: 0,
        }
    });
    println!("{:#?}", control_frame);
}

[sharksforarms]

Interesting! I did not think of this. Currently Deku assumes and works with Most Significant Bit (MSB) where this format seems to be LSB. You could do some bit arithmetic to make this work but would be much more hacky then to put the fields in reverse order....

This is something I'd like to support in the future.

[wcampbell0x2a]

This was something I came across while playing around with risc-v. Either you parse as MSB, or have a reverse attribute for parsing fields from LSB reversed.

I like the global read from LSB better.

[myrrlyn]

Hi! We have finally encountered in-the-wild the exact reason I wrote bitvec Like This.

This is a long-standing problem in C. GCC, for example, defines that bitfields are laid out in the architectural byte-endianness ordering: on LE platforms, the first field is at the least significant edge, then the next field abuts it in the more significant direction; on BE platforms, the first field as at the most significant edge, then the next field abuts it in the less significant direction. I can personally attest that this is an awful experience, so I would prefer to avoid doing so here.

I think this can be handled by using the struct-level #[deku] attribute to provide a BitOrder implementor name, and have the Deku{Read,Write} derive implementations use the provided (or default) name as the type parameter used to govern de/serialization. We want source order of fields to translate to logical progression through the buffer, and rely on bitvec's type parameters to handle the translation to specific bit position.

Let's try threading a struct-level BitOrder name through the codegen emitted by the derive macros and see what that does?

[sharksforarms]

Thanks @myrrlyn! I may be able to experiment a bit with this tomorrow,

If I understand correctly, you mean passing a Msb0 or Lsb0 to the codegen? This is exactly how I'd like to approach it, something like:

#[deku(bit_order = "lsb")]
struct MyStruct { 
...

The main issue I'm facing now is the way I'm consuming bits. I'm using split_at which works well for Msb (left to right) but not so much with Lsb...

If there's a better method to use let me know!

For example:

fn main() {
    let data = vec![0x88u8, 0x41];

    let bits = data.view_bits::<Lsb0>();

    dbg!(&bits); // [0b00010001, 0b10000010]
    //  we consume   --^^
    //  we want to consume --^^

    let (left, right) = bits.split_at(2);

    dbg!(&left); // [0b00] <-- we want 0b01 here (0b10 would also work w/ reversing)
    dbg!(&right); // [0b00010001, 0b10000010]
}

I have two alternative ideas:

• use proc-macro to reverse the struct fields if LSB by modifying AST (would work but not ideal)
• Keep track of index position instead of reference slice, do arithmetic to get proper slice (api change)

[myrrlyn]

I've been looking around at the implementation and stated goals and I think I'm settling on the notion of passing Msb0 or Lsb0 through the macro generation. I've started playing with the concept in myrrlyn/deku#features/ordering. I'm not necessarily married to the associated type; we could use an ordering type parameter on the trait or even the method and thereby sidestep picking one and only one ordering in #[deku] entirely. I just went with an associated type first since that doesn't change the trait or method names.

[sharksforarms]

@myrrlyn I went down the generic route, I put an example ieee to reflect the desired outcome: https://github.com/sharksforarms/deku/tree/bit_order

cargo run --example ieee

[wcampbell0x2a]

@myrrlyn I went down the generic route, I put an example ieee to reflect the desired outcome: https://github.com/sharksforarms/deku/tree/bit_order

cargo run --example ieee

is this example working? it gives me the following error:

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Parse("Could not match enum variant id = 64 on enum `FrameType`")', examples/ieee.rs:51:64

[sharksforarms]

@myrrlyn I went down the generic route, I put an example ieee to reflect the desired outcome: https://github.com/sharksforarms/deku/tree/bit_order
cargo run --example ieee

is this example working? it gives me the following error:

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Parse("Could not match enum variant id = 64 on enum `FrameType`")', examples/ieee.rs:51:64

Nope it panics! That's right. The goal is to not make it panic... :)

[Shadlock0133]

just lost few hours debugging my parsing code, and noticed this issue. it would be good idea to at least put in the docs that bit order is currently only msb.

[sharksforarms]

just lost few hours debugging my parsing code, and noticed this issue. it would be good idea to at least put in the docs that bit order is currently only msb.

Sorry about that.

Would using a 'reader' attribute help you out here? The data is given as Msb, but could be massaged to your liking.

[Shadlock0133]

i think i will just cut the dependency and write parsing code myself

[IvarWithoutBones]

Hi, i was wondering if there is still interest in moving this issue forwards? Matching the bit ordering with the documentation I'm referencing would be very helpful.

Would using a 'reader' attribute help you out here? The data is given as Msb, but could be massaged to your liking.

This seems promising. Is it possible to apply a custom reader to all fields of a struct, without annotating every field individually? This would get very verbose very quickly otherwise.

[sharksforarms]

still interest in moving this issue forwards

Yes, if anyone would like to work on this issue I'd gladly review a PR

Is it possible to apply a custom reader to all fields of a struct

This isn't possible no, but may be an interesting addition.

[kitlith]

I've been poking at the bit_order branch recently, it basically seems down to assumptions that Msb bit order is being used.

On the write side, I was able to produce correct looking behaviour by swapping out instances of <slice>[<slice>.len() - remaining_bits..] with a function that behaves differently depending on the bitorder type that's been passed. The names used here are... kinda bad, because I was thinking I would need to tweak something else originally.

pub trait BitOrderEndian: bitvec::order::BitOrder {
    const PREFERRED_ENDIAN: Endian;
}

impl BitOrderEndian for bitvec::order::Msb0 {
    const PREFERRED_ENDIAN: Endian = Endian::Big;
}

impl BitOrderEndian for bitvec::order::Lsb0 {
    const PREFERRED_ENDIAN: Endian = Endian::Little;
}

fn extract_bits<B: BitOrderEndian>(s: &BitSlice<B, u8>, remaining: usize) -> &BitSlice<B, u8> {
    if B::PREFERRED_ENDIAN == Endian::Big {
        &s[s.len() - remaining..]
    } else {
        &s[..remaining]
    }
}

I don't know if there's a way to restructure this so we don't need to explicitly work with the bit slice endian.

My test case has been to write 3 5 bit integers in a row, 0b00001, 0b00011, and 0b00111, and confirm they produce the result (in bytes) [0b01100001, 0b0011100]

On the read side, at a glance it looks like the issues have to do with padding, because commenting out the following padding loop caused the ieee example to pass:

for _ in 0..pad {
    bits.insert(index, false);
}

we might be able to put that behind an if statement of "using Msb0", i guess? but it's possible there's behavior I'm missing because Lsb0 is not currently rigorously tested.

[kitlith]

As a side note, we could probably use the methods on the BitField trait from bitvec to simplify the implementation. I'm assuming there's some reason why it doesn't seem to be in use, as it seems to have come into existance before deku.

[wcampbell0x2a]

I don't know the implications as far as this issue, but #352 changes the read API quite a bit if you are working on this issue.

[wcampbell0x2a]

I don't know the implications as far as this issue, but #352 changes the read API quite a bit if you are working on this issue.

I pushed https://github.com/sharksforarms/deku/tree/impl-reader-bit-order that is based on that MR and does an (vastly untested) good job of supporting the idea of lsb and msb bit_orders. See https://github.com/sharksforarms/deku/blob/impl-reader-bit-order/examples/ieee.rs for a example file.

I'll need this to correctly parse without hacks a squashfs v3 image, so expect some amount of push from myself to get this API done. (I'm not sure I care as much about DekuWrite for this, but it might be weird to only have this attribute work on DekuRead.

⚠️ this doesn't support DekuWrite (as this will take another refactor to get right(?)

[wcampbell0x2a]

If interested, I pushed my read-only changes to an MR: #367