5 ms·

A Better Way to Implement Bit Fields

159 points by luu 8y ago

nneonneo 8y ago
IMHO it would be better to capitalize the OTG structure field names according to the standard. This would turn "avalidoven" into "AvalidOvEn", which makes much more sense: it's the "A-side session valid override enable bit", which allows the software to override the "Avalid" signal with the value from AvalidOvVal. Also, this needs a (2017) tag.
- eps 8y ago
  How is your comment even remotely relevant to the post topic?
  - nneonneo 8y ago
    The post discusses bit-fields in the context of implementing some part of the USB OTG specification. Author makes a joke about USB having bits for “a valid oven”.
  - henry_bone 8y ago
    Read the article. At the end the author says > By the way it's nice to know that the USB protocol has a bit to indicate "a valid oven". I wonder when that is used. The bit fields he uses as an example related to USB protocol implementation.
  - deleted 8y ago
    [deleted]
- coldtea 8y ago
  >which allows the software to override the "Avalid" signal with the value from AvalidOvVal. How is "Avalid" any more meaningful though? "The AValid signal is used to indicate if the session for an A-peripheral is valid. This signal is 1b when Vbus is above 2V" They could use some better naming.
ChickeNES 8y ago
Now if only Rust had bitfields like this. It was proposed years ago but nothing has come from it.
- dbcurtis 8y ago
  Yes, well, now that Rust is aiming for first class support for embedded by the end of 2018, I expect there to be more pressure to find a good solution for bitfields. For that target audience, many will consider the current situation a show stopper.
  - burfog 8y ago
    Bitfield support is far more useful for emulators and for dealing with binary file formats and binary network protocols. Embedded stuff typically means kernels and drivers. For that, the bitfields are in hardware registers. This is troublesome because the hardware might not act like normal RAM. Issues you will encounter: 1. The hardware demands a particular access size. For example, a nice big array of 4-bit values may need to be accessed only by 16-bit operations because it is on a 16-bit data bus that lacks byte enable lines. Another example is that different access sizes may go to different registers. 2. The hardware takes an abnormal action when accessed. Reading and writing might go to separate registers. Reading could fetch a byte from a FIFO, so the language/compiler is not free to do speculative or repeated reads. Writing could output to a FIFO. Reading or writing could clear bits, possibly in a different register, or initiate a coprocessor action. 3. The bus might allow reordering that can affect the device. For example, the bus might cancel operations that seem to be superseded by later operations (write after write, or read after read) but enforce ordering in other cases. The compiler must respect this in some way, possibly by suppressing optimization or by generating a compile error when the constraints appear to be violated. You also get ugly layout issues like split fields, but that hits emulators and file formats too.
  - cormacrelf 8y ago
    There are a few crates around that help you get over the hurdle with some (but not too much) awkwardness, like https://github.com/dzamlo/rust-bitfield https://github.com/dzamlo/rust-bitfield
loeg 8y ago
Hm. I like the approach except for the overloaded meaning of packed. In C, packing means byte-aligned packing, rather than bit-packing. These seem like separate concepts. (Both are useful! I just think bit-packing should get its own special name.)
- vvanders 8y ago
  Yeah, packing is a pretty well defined to mean adding additional empty bits to keep fields word-aligned.
  - iainmerrick 8y ago
    Word-aligned? No, that's the opposite of packing! I'd say "packing" is ambiguous and could refer to either bit-aligned or byte-aligned data. But if your fields are less than 8 bits wide, I would assume "packing" means bit-packing.
    - loeg 8y ago
      E.g., if your packed struct is { bool a; uint32_t b; }, you probably don't want a totally misaligned-by-one-bit 'b'.
  - platinumrad 8y ago
    In my experience that's referred to as padding, not packing. A packed struct is what you get when you remove all of the padding. Packing is therefore removing padding, not adding it.
  - loeg 8y ago
    Byte-aligned, in C.
hinkley 8y ago
I can't remember what programming language it was, but I recall one that had managed to eliminate primitive numeric and bitwise logical operations by treating them as arrays of bits (booleans).
- mrtnmcc 8y ago
  Verilog?
- EdwardCoffin 8y ago
  I think BitC might have done something like this.
primeblue 8y ago
Excellent work with Zig and great documentation with detailed examples. Beautiful syntax.
lifthrasiir 8y ago
I recall that Herb Sutter's C++ Metaclasses proposal has an example of bitfield metaclass [1]. Zig's design is reasonable if it also makes use of those non-2^k-bit integer types in other places, and indeed it does (e.g. alignment is commonly `u29`). However if it is not doable, I think Sutter's design (auto-generated overlay on normal integers) makes more sense. [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0707r0.pdf#page=26 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p070...
rwmj 8y ago
C bitfields are terrible. But Erlang has brilliant handling of bitfields, I think he should look at those and compare his implementation to that.
- rusk 8y ago
  Lua does these very well too in my opinion. No messing around with bit-wise operators or masks - it's just an array of bits!
  - masklinn 8y ago
    Could you give an example? E.g. if you have a 3 bits signed integer V followed by two 1-bit flags (F1 and F2), followed by a 3-bits unsigned integer L, followed by binary data D of length L bytes, followed by a little-endian signed integer I over two bytes, how do you parse it? IIRC in Erlang it's something along the lines of <<V:3/signed, F1:1, F2:1, L:3, D:L/binary, I:16/signed-little>>
    - rusk 8y ago
      I went to look this up... I think actually the features I describe are more features of Wireshark which provides a Lua API, which is what confused me. That Erlang syntax reminds of the python 'struct' [0], except it's generating the unpacking logic at compile time, am I right? Yes that is indeed very cool - it doesn't even seem that hard to do I'd wonder why other languages don't have a similar facility! [0] https://docs.python.org/2/library/struct.html https://docs.python.org/2/library/struct.html
      - rusk 8y ago
        > I'd wonder why other languages don't have a similar facility Actually this is the kind of thing lex/yacc/Bison, javacc etc. do ... except I think only for text ...
      - rwmj 8y ago
        I wrote ocaml-bitstring (based on Erlang) and it also works by generating the code to handle the bits at compile time. It's fully general too - eg. if you describe a structure of 1 bit followed by an array of bytes then it will add the necessary bit shifts automatically when reading the bytes. Or if you describe a struct where everything is aligned then at compile time it will generate the most efficient code. You can even have variable length bitfields (a huge headache when implementing, but it does deliver the best possible code based on what it can prove at compile time). [1] https://rwmj.wordpress.com/2010/02/03/on-the-awesomeness-of-ocaml-bitstring/ https://rwmj.wordpress.com/2010/02/03/on-the-awesomeness-of-...
leni536 8y ago
I have several questions. If I have too bool bit fields next to each other, how are these ordered in a given byte? Even when I have a less then 8 bit field it can span over a byte boundary. Are the low bits go into the next byte or the high bits? The blog post only mentions fields greater than 8 bits. If a field greater than 8 bits is byte-aligned, it is represented in memory with the endianness of the host. If the field is not byte-aligned, it is represented in memory in big-endian. So is a 12 bit fild is byte-aligned if it starts at the "first" bit of a byte (whatever that is)? Is there a way to manually specify the endianness of a field? There are certainly cases where a byte-aligned big-endian field is needed on a little-endian host. I also don't like that keeping track of the fields' address happens in comments. It would be great if there were a language element that would specify the address of a field inside a packed struct, so the compiler could verify its correctness.
touisteur 8y ago
Bitfields are integrated in Ada and created through representation clauses : http://sworthodoxy.blogspot.com/2014/03/ada-vs-c-bit-fields.html http://sworthodoxy.blogspot.com/2014/03/ada-vs-c-bit-fields.... You can also set the endianness (bit and byte order) : https://www.adacore.com/gems/gem-140-bridging-the-endianness-gap https://www.adacore.com/gems/gem-140-bridging-the-endianness... (I think it was added in a recent language revision). Add to that the 'Component_Size attribute and the ability to specialize representation information easily : https://www.adacore.com/gems/gem-27 https://www.adacore.com/gems/gem-27 and https://www.adacore.com/gems/gem-28 https://www.adacore.com/gems/gem-28) and also the ability to recursively bound-check record structures (see https://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/implementation_defined_attributes.html#attribute-valid-scalars https://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/i... and https://dwheeler.com/lovelace/s17s4.htm https://dwheeler.com/lovelace/s17s4.htm for some background on 'valid and specific Ada safety extensions) you get a pretty elegant and powerful way to interact with low-level constructs.
- MisterTea 8y ago
  Ah Ada. Reminded me of my high school years playing with Turbo pascal before moving to c/c++. First concurrent language I ever worked with. Thought that feature was brilliant, so much nicer than pthreads. I took a small threaded c project of mine and replaced the pthreading with Ada and linked the c logic to it using gnat/gcc. Then along came Go, et al, and my interest in Ada unfortunately faded. Now you got me thinking about Ada again.
  - touisteur 8y ago
    To jog your memory and for the curious reading this, a chapter of the new 'learn Ada' interactive tutorial by AdaCore introduces tasking: https://learn.adacore.com/courses/intro-to-ada/chapters/tasking.html https://learn.adacore.com/courses/intro-to-ada/chapters/task... The whole interactive book deserves a look. You can then jump to the Spark book :-D https://learn.adacore.com/courses/intro-to-spark/index.html https://learn.adacore.com/courses/intro-to-spark/index.html that sadly doesn't seem to talk about tasking but Spark supports part of it. I'm actually looking forward the next few years, as AdaCore seems to be working on memory ownership-based guarantees a la rust (at least partially) and this might make Ada (or Spark in a first pass) a good candidate for truly fearless concurrency :-D.

159 points by luu 8y ago

IMHO it would be better to capitalize the OTG structure field names according to the standard. This would turn "avalidoven" into "AvalidOvEn", which makes much more sense: it's the "A-side session valid override enable bit", which allows the software to override the "Avalid" signal with the value from AvalidOvVal. Also, this needs a (2017) tag.

eps 8y ago
How is your comment even remotely relevant to the post topic?
- nneonneo 8y ago
  The post discusses bit-fields in the context of implementing some part of the USB OTG specification. Author makes a joke about USB having bits for “a valid oven”.
- henry_bone 8y ago
  Read the article. At the end the author says > By the way it's nice to know that the USB protocol has a bit to indicate "a valid oven". I wonder when that is used. The bit fields he uses as an example related to USB protocol implementation.
- deleted 8y ago
  [deleted]
coldtea 8y ago
>which allows the software to override the "Avalid" signal with the value from AvalidOvVal. How is "Avalid" any more meaningful though? "The AValid signal is used to indicate if the session for an A-peripheral is valid. This signal is 1b when Vbus is above 2V" They could use some better naming.

ChickeNES 8y ago

Now if only Rust had bitfields like this. It was proposed years ago but nothing has come from it.

dbcurtis 8y ago
Yes, well, now that Rust is aiming for first class support for embedded by the end of 2018, I expect there to be more pressure to find a good solution for bitfields. For that target audience, many will consider the current situation a show stopper.
- burfog 8y ago
  Bitfield support is far more useful for emulators and for dealing with binary file formats and binary network protocols. Embedded stuff typically means kernels and drivers. For that, the bitfields are in hardware registers. This is troublesome because the hardware might not act like normal RAM. Issues you will encounter: 1. The hardware demands a particular access size. For example, a nice big array of 4-bit values may need to be accessed only by 16-bit operations because it is on a 16-bit data bus that lacks byte enable lines. Another example is that different access sizes may go to different registers. 2. The hardware takes an abnormal action when accessed. Reading and writing might go to separate registers. Reading could fetch a byte from a FIFO, so the language/compiler is not free to do speculative or repeated reads. Writing could output to a FIFO. Reading or writing could clear bits, possibly in a different register, or initiate a coprocessor action. 3. The bus might allow reordering that can affect the device. For example, the bus might cancel operations that seem to be superseded by later operations (write after write, or read after read) but enforce ordering in other cases. The compiler must respect this in some way, possibly by suppressing optimization or by generating a compile error when the constraints appear to be violated. You also get ugly layout issues like split fields, but that hits emulators and file formats too.
- cormacrelf 8y ago
  There are a few crates around that help you get over the hurdle with some (but not too much) awkwardness, like https://github.com/dzamlo/rust-bitfield https://github.com/dzamlo/rust-bitfield

loeg 8y ago

Hm. I like the approach except for the overloaded meaning of packed. In C, packing means byte-aligned packing, rather than bit-packing. These seem like separate concepts. (Both are useful! I just think bit-packing should get its own special name.)

vvanders 8y ago
Yeah, packing is a pretty well defined to mean adding additional empty bits to keep fields word-aligned.
- iainmerrick 8y ago
  Word-aligned? No, that's the opposite of packing! I'd say "packing" is ambiguous and could refer to either bit-aligned or byte-aligned data. But if your fields are less than 8 bits wide, I would assume "packing" means bit-packing.
  - loeg 8y ago
    E.g., if your packed struct is { bool a; uint32_t b; }, you probably don't want a totally misaligned-by-one-bit 'b'.
- platinumrad 8y ago
  In my experience that's referred to as padding, not packing. A packed struct is what you get when you remove all of the padding. Packing is therefore removing padding, not adding it.
- loeg 8y ago
  Byte-aligned, in C.

hinkley 8y ago

I can't remember what programming language it was, but I recall one that had managed to eliminate primitive numeric and bitwise logical operations by treating them as arrays of bits (booleans).

mrtnmcc 8y ago
Verilog?
EdwardCoffin 8y ago
I think BitC might have done something like this.

primeblue 8y ago

Excellent work with Zig and great documentation with detailed examples. Beautiful syntax.

lifthrasiir 8y ago

I recall that Herb Sutter's C++ Metaclasses proposal has an example of bitfield metaclass [1]. Zig's design is reasonable if it also makes use of those non-2^k-bit integer types in other places, and indeed it does (e.g. alignment is commonly `u29`). However if it is not doable, I think Sutter's design (auto-generated overlay on normal integers) makes more sense. [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0707r0.pdf#page=26 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p070...

rwmj 8y ago

C bitfields are terrible. But Erlang has brilliant handling of bitfields, I think he should look at those and compare his implementation to that.

rusk 8y ago
Lua does these very well too in my opinion. No messing around with bit-wise operators or masks - it's just an array of bits!
- masklinn 8y ago
  Could you give an example? E.g. if you have a 3 bits signed integer V followed by two 1-bit flags (F1 and F2), followed by a 3-bits unsigned integer L, followed by binary data D of length L bytes, followed by a little-endian signed integer I over two bytes, how do you parse it? IIRC in Erlang it's something along the lines of <<V:3/signed, F1:1, F2:1, L:3, D:L/binary, I:16/signed-little>>
  - rusk 8y ago
    I went to look this up... I think actually the features I describe are more features of Wireshark which provides a Lua API, which is what confused me. That Erlang syntax reminds of the python 'struct' [0], except it's generating the unpacking logic at compile time, am I right? Yes that is indeed very cool - it doesn't even seem that hard to do I'd wonder why other languages don't have a similar facility! [0] https://docs.python.org/2/library/struct.html https://docs.python.org/2/library/struct.html
    - rusk 8y ago
      > I'd wonder why other languages don't have a similar facility Actually this is the kind of thing lex/yacc/Bison, javacc etc. do ... except I think only for text ...
    - rwmj 8y ago
      I wrote ocaml-bitstring (based on Erlang) and it also works by generating the code to handle the bits at compile time. It's fully general too - eg. if you describe a structure of 1 bit followed by an array of bytes then it will add the necessary bit shifts automatically when reading the bytes. Or if you describe a struct where everything is aligned then at compile time it will generate the most efficient code. You can even have variable length bitfields (a huge headache when implementing, but it does deliver the best possible code based on what it can prove at compile time). [1] https://rwmj.wordpress.com/2010/02/03/on-the-awesomeness-of-ocaml-bitstring/ https://rwmj.wordpress.com/2010/02/03/on-the-awesomeness-of-...

leni536 8y ago

I have several questions. If I have too bool bit fields next to each other, how are these ordered in a given byte? Even when I have a less then 8 bit field it can span over a byte boundary. Are the low bits go into the next byte or the high bits? The blog post only mentions fields greater than 8 bits. If a field greater than 8 bits is byte-aligned, it is represented in memory with the endianness of the host. If the field is not byte-aligned, it is represented in memory in big-endian. So is a 12 bit fild is byte-aligned if it starts at the "first" bit of a byte (whatever that is)? Is there a way to manually specify the endianness of a field? There are certainly cases where a byte-aligned big-endian field is needed on a little-endian host. I also don't like that keeping track of the fields' address happens in comments. It would be great if there were a language element that would specify the address of a field inside a packed struct, so the compiler could verify its correctness.

touisteur 8y ago

Bitfields are integrated in Ada and created through representation clauses : http://sworthodoxy.blogspot.com/2014/03/ada-vs-c-bit-fields.html http://sworthodoxy.blogspot.com/2014/03/ada-vs-c-bit-fields.... You can also set the endianness (bit and byte order) : https://www.adacore.com/gems/gem-140-bridging-the-endianness-gap https://www.adacore.com/gems/gem-140-bridging-the-endianness... (I think it was added in a recent language revision). Add to that the 'Component_Size attribute and the ability to specialize representation information easily : https://www.adacore.com/gems/gem-27 https://www.adacore.com/gems/gem-27 and https://www.adacore.com/gems/gem-28 https://www.adacore.com/gems/gem-28) and also the ability to recursively bound-check record structures (see https://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/implementation_defined_attributes.html#attribute-valid-scalars https://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/i... and https://dwheeler.com/lovelace/s17s4.htm https://dwheeler.com/lovelace/s17s4.htm for some background on 'valid and specific Ada safety extensions) you get a pretty elegant and powerful way to interact with low-level constructs.

MisterTea 8y ago
Ah Ada. Reminded me of my high school years playing with Turbo pascal before moving to c/c++. First concurrent language I ever worked with. Thought that feature was brilliant, so much nicer than pthreads. I took a small threaded c project of mine and replaced the pthreading with Ada and linked the c logic to it using gnat/gcc. Then along came Go, et al, and my interest in Ada unfortunately faded. Now you got me thinking about Ada again.
- touisteur 8y ago
  To jog your memory and for the curious reading this, a chapter of the new 'learn Ada' interactive tutorial by AdaCore introduces tasking: https://learn.adacore.com/courses/intro-to-ada/chapters/tasking.html https://learn.adacore.com/courses/intro-to-ada/chapters/task... The whole interactive book deserves a look. You can then jump to the Spark book :-D https://learn.adacore.com/courses/intro-to-spark/index.html https://learn.adacore.com/courses/intro-to-spark/index.html that sadly doesn't seem to talk about tasking but Spark supports part of it. I'm actually looking forward the next few years, as AdaCore seems to be working on memory ownership-based guarantees a la rust (at least partially) and this might make Ada (or Spark in a first pass) a good candidate for truly fearless concurrency :-D.