sharksforarms / deku

Declarative binary reading and writing: bit-level, symmetric, serialization/deserialization
Apache License 2.0
1.15k stars 55 forks source link

DRAFT: Add bit_order support #373

Closed wcampbell0x2a closed 3 months ago

wcampbell0x2a commented 1 year ago

Something like this:

#[derive(Debug, DekuRead, DekuWrite, PartialEq)]
#[deku(bit_order = "lsb")]
pub struct SquashfsV3 {
    #[deku(bits = "4")]
    inode_type: u32,
    #[deku(bits = "12")]
    mode: u32,
    #[deku(bits = "8")]
    uid: u32,
    #[deku(bits = "8")]
    guid: u32,
    mtime: u32,
    inode_number: u32,
}

See tests/bit_order.rs in this MR for more examples.

github-actions[bot] commented 1 year ago

Benchmark for 01edc23

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | **1400.1±1.29ns** | 1413.3±1.43ns | **+0.94%** | | deku_read_byte | 25.9±0.08ns | **25.1±0.09ns** | **-3.09%** | | deku_read_enum | **10.1±0.08ns** | 11.9±0.07ns | **+17.82%** | | deku_read_vec | 67.5±0.55ns | **58.3±0.44ns** | **-13.63%** | | deku_write_bits | **242.0±1.46ns** | 261.3±0.48ns | **+7.98%** | | deku_write_byte | **40.4±0.16ns** | 42.1±0.13ns | **+4.21%** | | deku_write_enum | 34.8±0.13ns | 34.8±0.16ns | 0.00% | | deku_write_vec | 538.0±3.60ns | **411.0±4.09ns** | **-23.61%** |
github-actions[bot] commented 1 year ago

Benchmark for 02fe189

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | **1325.2±18.48ns** | 1348.6±12.81ns | **+1.77%** | | deku_read_byte | **21.1±0.57ns** | 22.1±0.44ns | **+4.74%** | | deku_read_enum | **9.4±0.17ns** | 10.1±0.17ns | **+7.45%** | | deku_read_vec | 57.4±0.84ns | **53.6±0.68ns** | **-6.62%** | | deku_write_bits | **197.5±3.47ns** | 202.3±3.70ns | **+2.43%** | | deku_write_byte | **37.5±0.56ns** | 38.6±0.71ns | **+2.93%** | | deku_write_enum | **31.7±0.68ns** | 31.9±0.17ns | **+0.63%** | | deku_write_vec | 279.6±3.49ns | 281.4±3.43ns | +0.64% |
github-actions[bot] commented 1 year ago

Benchmark for e6e42a6

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | **1262.3±8.69ns** | 1280.9±28.21ns | **+1.47%** | | deku_read_byte | **21.1±0.22ns** | 21.8±0.53ns | **+3.32%** | | deku_read_enum | **9.5±0.19ns** | 10.4±0.25ns | **+9.47%** | | deku_read_vec | 58.6±0.57ns | **54.1±0.70ns** | **-7.68%** | | deku_write_bits | **197.6±3.86ns** | 203.3±4.29ns | **+2.88%** | | deku_write_byte | 39.4±0.65ns | **37.3±0.71ns** | **-5.33%** | | deku_write_enum | 32.0±0.29ns | 32.0±0.48ns | 0.00% | | deku_write_vec | 298.7±3.53ns | **285.4±1.97ns** | **-4.45%** |
github-actions[bot] commented 1 year ago

Benchmark for 27866fa

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | 2.2±0.09µs | **2.1±0.10µs** | **-4.55%** | | deku_read_byte | **30.4±1.00ns** | 31.9±1.03ns | **+4.93%** | | deku_read_enum | **14.2±0.52ns** | 15.3±0.95ns | **+7.75%** | | deku_read_vec | 85.9±3.96ns | **76.4±3.89ns** | **-11.06%** | | deku_write_bits | 409.4±24.44ns | **386.3±20.04ns** | **-5.64%** | | deku_write_byte | 51.5±2.31ns | 52.9±1.93ns | +2.72% | | deku_write_enum | 43.9±1.86ns | 43.7±2.38ns | -0.46% | | deku_write_vec | 647.0±34.64ns | 640.3±50.71ns | -1.04% |
github-actions[bot] commented 1 year ago

Benchmark for 04c62aa

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | 1353.2±12.61ns | **1248.0±19.10ns** | **-7.77%** | | deku_read_byte | **20.8±0.64ns** | 22.2±0.70ns | **+6.73%** | | deku_read_enum | **9.5±0.10ns** | 10.1±0.22ns | **+6.32%** | | deku_read_vec | 58.1±0.87ns | **54.5±0.89ns** | **-6.20%** | | deku_write_bits | **196.2±3.06ns** | 202.2±4.09ns | **+3.06%** | | deku_write_byte | 39.1±0.70ns | **37.2±0.38ns** | **-4.86%** | | deku_write_enum | 31.7±0.41ns | 32.0±0.55ns | +0.95% | | deku_write_vec | **276.4±5.06ns** | 286.2±3.88ns | **+3.55%** |
github-actions[bot] commented 1 year ago

Benchmark for 7fe1cb1

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | **1773.5±124.43ns** | 1980.8±188.06ns | **+11.69%** | | deku_read_bits_lsb | 1908.6±146.98ns | N/A | N/A | | deku_read_byte | 26.3±2.40ns | 27.8±2.58ns | +5.70% | | deku_read_enum | **12.1±0.90ns** | 15.8±0.78ns | **+30.58%** | | deku_read_vec | 81.8±7.06ns | **71.4±4.99ns** | **-12.71%** | | deku_write_bits | **322.2±22.45ns** | 358.0±27.39ns | **+11.11%** | | deku_write_bits_lsb | 668.0±50.87ns | N/A | N/A | | deku_write_byte | **44.2±2.77ns** | 50.3±5.44ns | **+13.80%** | | deku_write_enum | **41.6±2.01ns** | 45.3±3.00ns | **+8.89%** | | deku_write_vec | 575.3±24.40ns | 556.5±55.24ns | -3.27% |
tpisto commented 1 year ago

I'm facing problem here:

Using Hex: 8BF3DC7B9438984278B85E

#[derive(DekuRead, Debug, PartialEq)]
#[deku(endian = "little", bit_order = "lsb")]
pub struct TestStruct {
    #[deku(bits = 4)]
    a: u16,

    #[deku(bits = 11)]
    b: u16,

    #[deku(bits = 13)]
    c: u16,
}

A and B are correct (11 and 1848), but C translates to 6108, but it should be 6073 instead.

Screenshot 2023-11-14 at 11 15 22
tpisto commented 1 year ago

Here is also test for deku bit_order.rs. When added it fails with message:

thread 'test_bit_order_little' panicked at tests/bit_order.rs:383:5:
assertion `left == right` failed
  left: BitOrderLittle { value_a: 11, value_b: 1848, value_c: 6108, value_d: 327, value_e: 226, value_f: 96, value_g: 133, value_h: 120, value_i: 56, value_j: 189 }
 right: BitOrderLittle { value_a: 11, value_b: 1848, value_c: 6073, value_d: 327, value_e: 226, value_f: 96, value_g: 133, value_h: 120, value_i: 56, value_j: 189 }

Seems every other value is handled correctly, but the value_c has some weird problem. I have validated multiple times that the 6073 is correct value, so the test is valid.

#[derive(Debug, DekuRead, DekuWrite, PartialEq)]
#[deku(endian = "little", bit_order = "lsb")]
pub struct BitOrderLittle {
    #[deku(bits = 4)]
    value_a: u16,

    #[deku(bits = 11)]
    value_b: u16,

    #[deku(bits = 13)]
    value_c: u16,

    #[deku(bits = 10)]
    value_d: u16,

    #[deku(bits = 8)]
    value_e: u16,

    #[deku(bits = 9)]
    value_f: u16,

    #[deku(bits = 9)]
    value_g: u16,

    #[deku(bits = 8)]
    value_h: u16,

    #[deku(bits = 7)]
    value_i: u16,

    #[deku(bits = 9)]
    value_j: u16,
}

#[test]
fn test_bit_order_little() {
    let data = vec![
        0x8B, 0xF3, 0xDC, 0x7B, 0x94, 0x38, 0x98, 0x42, 0x78, 0xB8, 0x5E,
    ];
    let bit_order_little = BitOrderLittle::try_from(data.as_ref()).unwrap();
    assert_eq!(
        bit_order_little,
        BitOrderLittle {
            value_a: 11,
            value_b: 1848,
            value_c: 6073,
            value_d: 327,
            value_e: 226,
            value_f: 96,
            value_g: 133,
            value_h: 120,
            value_i: 56,
            value_j: 189,
        }
    );

    let bytes = bit_order_little.to_bytes().unwrap();
    assert_eq_hex!(bytes, data);
}
tpisto commented 1 year ago

Found the bug in reader.rs:

                match order {
                    Order::Lsb0 => {
                        let (rest, used) = rest.split_at(rest.len() - bits_left);
                        ret.extend_from_bitslice(used);
                        ret.extend_from_bitslice(&self.leftover);
                        if let Some(front_bits) = front_bits {
                            ret.extend_from_bitslice(front_bits);
                        }

                        self.leftover = rest.to_bitvec();

                        println!("read_bits: ret:      {}", ret);
                    }
                    ret.extend_from_bitslice(&self.leftover);

should be below

                    if let Some(front_bits) = front_bits {
                        ret.extend_from_bitslice(front_bits);
                    }

Working code:

                    Order::Lsb0 => {
                        let (rest, used) = rest.split_at(rest.len() - bits_left);
                        ret.extend_from_bitslice(used);
                        if let Some(front_bits) = front_bits {
                            ret.extend_from_bitslice(front_bits);
                        }
                        ret.extend_from_bitslice(&self.leftover);

                        self.leftover = rest.to_bitvec();

                        println!("read_bits: ret:      {}", ret);
                    }
tpisto commented 1 year ago

You can find the fix and related test from here: https://github.com/tpisto/deku/tree/impl-reader-bit-order2

tpisto commented 1 year ago

New problem - even with the fix I did for the previous error:

With data: 0xE8, 0x25, 0xF4

#[deku(endian = "little", bit_order = "lsb")]
pub struct Test {
    #[deku(bits = 1)]
    field_a: bool,

    #[deku(bits = 23)]
    field_b: u32,
}

field_b should be 8000244, but instead deku parses it as 1243764

wcampbell0x2a commented 1 year ago

Thanks for testing this and finding bugs!

wcampbell0x2a commented 1 year ago

New problem - even with the fix I did for the previous error:

With data: 0xE8, 0x25, 0xF4

#[deku(endian = "little", bit_order = "lsb")]
pub struct Test {
    #[deku(bits = 1)]
    field_a: bool,

    #[deku(bits = 23)]
    field_b: u32,
}

field_b should be 8000244, but instead deku parses it as 1243764

Just so I understand the problem. The following is the current behavior:

    #[derive(Debug, DekuRead, DekuWrite, PartialEq)]
    #[deku(endian = "little", bit_order = "lsb")]
    pub struct Test {
        #[deku(bits = 1)]
        field_a: bool,

        #[deku(bits = 23)]
        field_b: u32,
    }

    //                |||| ||| <-
    let data = vec![0b1111_1110, 0b1111_0000, 0b1111_0000];
    let bit_order_little = Test::try_from(data.as_ref()).unwrap();
    assert_eq_hex!(
        bit_order_little,
        Test {
            field_a: false,
            //                             ||| |||| <-
            field_b: 0b111_1000_0111_1000_0111_1111,
        }
    );

Where do those bits that I outlined fall in the correct assertion?

wcampbell0x2a commented 1 year ago

New problem - even with the fix I did for the previous error: With data: 0xE8, 0x25, 0xF4

#[deku(endian = "little", bit_order = "lsb")]
pub struct Test {
    #[deku(bits = 1)]
    field_a: bool,

    #[deku(bits = 23)]
    field_b: u32,
}

field_b should be 8000244, but instead deku parses it as 1243764

Just so I understand the problem. The following is the current behavior:

    #[derive(Debug, DekuRead, DekuWrite, PartialEq)]
    #[deku(endian = "little", bit_order = "lsb")]
    pub struct Test {
        #[deku(bits = 1)]
        field_a: bool,

        #[deku(bits = 23)]
        field_b: u32,
    }

    //                |||| ||| <-
    let data = vec![0b1111_1110, 0b1111_0000, 0b1111_0000];
    let bit_order_little = Test::try_from(data.as_ref()).unwrap();
    assert_eq_hex!(
        bit_order_little,
        Test {
            field_a: false,
            //                             ||| |||| <-
            field_b: 0b111_1000_0111_1000_0111_1111,
        }
    );

Where do those bits that I outlined fall in the correct assertion?

@tpisto could you elaborate? Thanks

github-actions[bot] commented 12 months ago

Benchmark for d401fcd

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | **1206.8±26.61ns** | 1327.3±19.30ns | **+9.99%** | | deku_read_bits_lsb | 1240.6±24.61ns | N/A | N/A | | deku_read_byte | **22.1±0.36ns** | 22.5±1.48ns | **+1.81%** | | deku_read_enum | **9.3±0.12ns** | 10.3±0.30ns | **+10.75%** | | deku_read_vec | 58.8±0.69ns | **54.7±1.60ns** | **-6.97%** | | deku_write_bits | 201.0±7.37ns | 205.5±6.56ns | +2.24% | | deku_write_bits_lsb | 362.9±7.34ns | N/A | N/A | | deku_write_byte | **35.5±1.60ns** | 36.9±0.48ns | **+3.94%** | | deku_write_enum | **29.8±0.25ns** | 31.4±2.78ns | **+5.37%** | | deku_write_vec | **303.1±2.40ns** | 315.4±21.99ns | **+4.06%** |
github-actions[bot] commented 11 months ago

Benchmark for 5500508

Click to view benchmark | Test | Base | PR | % | |------|--------------|------------------|---| | deku_read_bits | **1274.2±9.66ns** | 1286.4±20.26ns | **+0.96%** | | deku_read_bits_lsb | 1228.0±16.08ns | N/A | N/A | | deku_read_byte | 22.1±0.51ns | 22.1±0.38ns | 0.00% | | deku_read_enum | **9.5±0.15ns** | 10.6±0.32ns | **+11.58%** | | deku_read_vec | 58.5±0.53ns | **53.5±1.03ns** | **-8.55%** | | deku_write_bits | 216.4±7.23ns | **206.6±4.09ns** | **-4.53%** | | deku_write_bits_lsb | 361.5±6.04ns | N/A | N/A | | deku_write_byte | 20.9±0.75ns | 21.5±0.61ns | +2.87% | | deku_write_enum | 20.8±0.14ns | 20.8±0.32ns | 0.00% | | deku_write_vec | **296.3±1.44ns** | 300.8±15.10ns | **+1.52%** |
Lehona commented 9 months ago

I think the bit_order setting is not working in conjunction with padding bits yet. Consider this testcase:

    #[derive(DekuRead, DekuWrite, Debug)]
    #[deku(bit_order = "lsb")]
    struct DekuTest {
        pad: u8,
        #[deku(bits=6, pad_bits_after = "10")]
        flag: u16,
        sent: u8,
    }

    #[test]
    fn dekutest() -> Result<(), DekuError> {
        let data = vec![0x13, 0x75, 0x0, 0xFF];
        let (_, dt) = DekuTest::from_bytes((&data, 0))?;
        let to_bytes = dt.to_bytes()?;
        println!("{:?}", data);
        println!("{:?}", to_bytes);
        Ok(())
    }

Output is

[19, 117, 0, 255]
[19, 0, 53, 255]

Although as far as I can tell the value in dt.flag is correct, so reading works, but writing back doesn't.

joelreymont commented 6 months ago

Is anyone working on this?

wcampbell0x2a commented 6 months ago

Is anyone working on this?

Not currently. I needs a fun rebase on top of current master.

wcampbell0x2a commented 3 months ago

Closing in favor of rebased https://github.com/sharksforarms/deku/pull/468

wcampbell0x2a commented 3 months ago

I think the bit_order setting is not working in conjunction with padding bits yet. Consider this testcase:

    #[derive(DekuRead, DekuWrite, Debug)]
    #[deku(bit_order = "lsb")]
    struct DekuTest {
        pad: u8,
        #[deku(bits=6, pad_bits_after = "10")]
        flag: u16,
        sent: u8,
    }

    #[test]
    fn dekutest() -> Result<(), DekuError> {
        let data = vec![0x13, 0x75, 0x0, 0xFF];
        let (_, dt) = DekuTest::from_bytes((&data, 0))?;
        let to_bytes = dt.to_bytes()?;
        println!("{:?}", data);
        println!("{:?}", to_bytes);
        Ok(())
    }

Output is

[19, 117, 0, 255]
[19, 0, 53, 255]

Although as far as I can tell the value in dt.flag is correct, so reading works, but writing back doesn't.

this is fixed in https://github.com/sharksforarms/deku/pull/468