Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

DRAFT: Add bit_order support #373

Closed
wants to merge 5 commits into from
Closed

Conversation

wcampbell0x2a
Copy link
Collaborator

@wcampbell0x2a wcampbell0x2a commented Nov 3, 2023

  • Add Read/Write bit_order Support

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.

Copy link

github-actions bot commented Nov 3, 2023

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%

Copy link

github-actions bot commented Nov 3, 2023

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%

Copy link

github-actions bot commented Nov 3, 2023

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%

Copy link

github-actions bot commented Nov 3, 2023

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%

Copy link

github-actions bot commented Nov 3, 2023

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%

Copy link

github-actions bot commented Nov 3, 2023

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
Copy link

tpisto commented Nov 14, 2023

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
Copy link

tpisto commented Nov 14, 2023

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
Copy link

tpisto commented Nov 14, 2023

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
Copy link

tpisto commented Nov 14, 2023

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

@tpisto
Copy link

tpisto commented Nov 14, 2023

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
Copy link
Collaborator Author

Thanks for testing this and finding bugs!

@wcampbell0x2a
Copy link
Collaborator Author

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?

Add from_reader and use Read internally to improve the codegen of deku,
the performance of derived parsers. Internally, this is implemented
using the new src/reader.rs interface in deku parses. This has a waterfall
effect on DekuReader implementations and the deku-derive/deku_read Derived impl.
Previous usage with from_bytes and other API's are unchanged.
There is somewhat of a performance hit for bit-only parses,
but I find the major improvments in the bytes-wise parsing to be great enough
to warrent this change.

The following are some sample benchmarks:
> critcmp before after
group                  after                                  before
-----                  -----                                  ------
deku_read_bits         1.24   845.8±14.29ns        ? ?/sec    1.00   679.5±11.83ns        ? ?/sec
deku_read_byte         1.00     17.8±0.25ns        ? ?/sec    2.12     37.8±3.35ns        ? ?/sec
deku_read_enum         1.00     15.3±0.15ns        ? ?/sec    2.04     31.2±0.81ns        ? ?/sec
deku_read_vec          1.00    676.8±7.04ns        ? ?/sec    2.16  1459.5±40.22ns        ? ?/sec
deku_write_bits        1.00    125.3±3.10ns        ? ?/sec    1.04   130.2±11.12ns        ? ?/sec
deku_write_byte        1.00    161.6±4.86ns        ? ?/sec    1.02    165.0±5.91ns        ? ?/sec
deku_write_enum        1.00    105.6±1.06ns        ? ?/sec    1.03    109.0±7.20ns        ? ?/sec
deku_write_vec         1.00      4.6±0.04µs        ? ?/sec    1.06      4.9±0.07µs        ? ?/sec

The above change removes DekuRead, and replaces it with DekuReader. This contains
the from_reader_with_ctx. DekuContainerRead contains from_reader.

The crate no_std_io was picked to supply a Read impl
for the no_std feature. These are "re-export"ed.

Add "`Read` enabled" docs to lib.rs

Add tests/test_tuple.rs tests

Update CHANGELOG.md to reflect changes and help migration to this usage

Use llvm-cov in ci for the generation of more accurate coverage reports

Update benchmarks to test more complex parser speeds

Disable Miri CI

Update ensure_no_std to work with new Read usage. Remove wee-alloc in favour
of an updated crate for the allocator.

Add inline to small functions
@wcampbell0x2a
Copy link
Collaborator Author

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

Copy link

github-actions bot commented Dec 2, 2023

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%

Copy link

github-actions bot commented Dec 6, 2023

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%

@wcampbell0x2a wcampbell0x2a changed the title Add bit_order support DRAFT: Add bit_order support Dec 14, 2023
@wcampbell0x2a wcampbell0x2a force-pushed the impl-writer branch 2 times, most recently from 6f17200 to c2a3dc8 Compare December 14, 2023 12:43
@Lehona
Copy link

Lehona commented Feb 21, 2024

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.

Base automatically changed from impl-writer to master April 29, 2024 22:03
@joelreymont
Copy link

Is anyone working on this?

@wcampbell0x2a
Copy link
Collaborator Author

Is anyone working on this?

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

@wcampbell0x2a
Copy link
Collaborator Author

Closing in favor of rebased #468

@wcampbell0x2a
Copy link
Collaborator Author

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 #468

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

bit order in reader Question: Is it possible to parse this bit layout? Selecting bit order
4 participants