Reviving the bit-data discussion

[engstad]

A question of syntax

If we did have a syntax for bit-fields, I’m obviously advocating a style using u{N} and i{N}, though I could be convinced otherwise. But we still have the issues regarding bit-data unions. Originally, I thought of:

bitdata Type : u16 {  // u16 is the carrier type
   Variant1 { a: u5, b: u5, c: u6 },
   Variant2 { d: u16 }
}

But this syntax is compersome when you only have a single variant (or straight C-like struct with bit-fields).

Perhaps instead, the syntax should be:

union MyUnion {
   v1: bitdata { a: u5, b: u5, c: u6 },  // carrier type inferred to be u16
   v2: bitdata { d: u16 } // carrier type inferred to be u16
}

In other words, we can do this in two steps. First, we introduce the bitdata data-type specification, and only then we consider unions of bits?

[engstad]

I actually want full {u,i}N types for static analysis purposes.

Would you mind exploring this in more detail? It sounds quite interesting!

[Ericson2314]

Two examples (I should go to sleep):

• Rust knows match (_: u4) { 0 => _, 1 => _, 2 => _, 3 => _, } is exhaustive.
• If we get “packed tuples” let #[packed] (b0: u1, b0: u1, r: u6) = transmute(1u8); just works.

Hopefully you can extrapolate form there :).

[nrc]

Could you explain a bit the semantics you expect for bitdata unions please? How would this differ from regular Rust unions?

[engstad]

@nrc Do you mean “unsafe enums”? I’m afraid I don’t know the status of that, is it in?

[nrc]

I mean unions there is an accepted RFC and an unstable implementation.

[engstad]

Thanks very much @nrc. Your link was very useful.

I think that RFC can work quite well with bit-data. The one amendment would be that you should be able to place tag patterns “inside” bit-fields.

The reason for having this feature is that it is not always entirely clear-cut where to put the tag. For instance, imagine an i86 machine code specification. Sometimes, the “tag” (determining the instruction type) is 1-bit, but sometimes it involves several bits.

Another example would be tricks used in the representation of dynamicaly typed languages. If pointers are forced to be 8-byte aligned, then you can use those 3 free bits to “tag” values differently:

|XXX....XXXXX|0| A 63-bit integer
|XXX....XXX|001| Symbol-table entry
|XXX....XXX|011| An inline string
|XXX....XX|0101| Nil/False
|XXX....XX|1101| True
|XXX....XXX|111| A 64-bit pointer 

I imagined this possible by adding “tag-specifiers.” They would comprise bit-patterns that would be set to determine and decode the meaning of the particular set of bits. I proposed the syntax

{field-name}: {bit-type} = {bit-value}

As an example, here’s the same example used in the RFC, but using only 32-bits while sacrificing a single bit of precision.

// Compact value storing 31-bit unsigned integers or 
// floating point with 1-less mantissa bit.
union Value {
    u: bitdata U { tag: u1 = 0, v: u31 },
    f: bitdata F { tag: u1 = 1, s: u1, e: u8, m: u22}
}

As you can see, the first bit indicates what the value refers to. If the first bit is 0, then it is a u31, otherwise it is a 31-bit floating point number. Because of this, you can determine if the U-arm or the F-arm should be taken:

// Regular IEEE representation of floating point
bitdata Fp32 : f32 {
    sgn: u1, exp: u8, mnt: u23
}

fn is_zero(v: Value) -> bool {
    // This match is possible, due to the tag specificiation in the bit-data.
    match v {
        U { v: 0 } => true,
        F { s, e, m } => Fp32 { sgn: s, exp: e, mnt: m<<1 } == 0.0
    }
}

Notice that the carrier type for Fp32 is f32, so the constructed value can be used directly as a f32. Also, note that the test works for the IEEE floating point -0.0.

[hannobraun]

I haven’t read the whole thread carefully, so I’m sorry if what I write is redundant, but the following stood out to me:

Awkward syntax: color.set_red(color.get_red() + 1), versus color.red += 1. I suppose the situation would improve if Rust supported properties.

I think something similar should already be possible, like this:

color.red() += 1

The implementation would look something like this (attention, untested pseudo-code):

struct Color(u32);

impl Color {
    fn red(&mut self) -> Red {
        Red(&mut self.0)
    }
}


struct Red<'a>(&'a mut u32);

impl AddAssign<u8> for Red {
    fn add_assign(&mut self, rhs: u8) {
        self.0 += rhs as u32 << 24;
    }
}

I haven’t bothered with #[derive(Copy)] and such, but the general concept should work.

[engstad]

Full-fledged {u,i}N support

@Ericson2314 made the interesting remark that perhaps it would be a good idea to allow generic bit-lengths as basic types. His reasoning was that the compiler could reason with packed data and statically infer more about ranges. I thought perhaps this was a bad idea, but after thinking about it, I tend to agree.

Another example is range-checking. The compiler can infer that the array access is safe without range bounds,

fn read(index: u4, array: &[u32; 16]) -> u32 {
    array.get_unchecked(index) // safe!
}

Random thoughts

• Literals: Extend it to accept any number: 15u4.
• Conversions: Just as before, you must use as: var as u24
• One note: i1 is a strange type, because the values are {0, -1}. (Since: i2 = {-2, -1, 0, 1}.)
• It makes sense to support bit concatenation, e.g.: [#bitpacked] (0b1111u4, 0b0000u4) == 0b1111_0000u8
• Alternatively: a # b could be bit concatenation.
• 15u4 # 0u4 == 0xF0 as u8
• For future compatibility with type-level naturals and generics, it may prudent to reserve Unsigned<> and Int<>:
• u4 == Unsigned<4>, and i4 == Int<4>.
• We’ll need bitsizeof::<T> and bitoffsetof::<T>.

Why not support it?

My main thought against it is that it might be hard to see the difference between types that can be stored in memory, and those that don’t. A new programmer would be surprised to learn that u8, u16, u32 all are special, but u24 is not. However, if the compiler is smart enough to warn and error out on misuse, then I don’t see a big problem.

How would it look?

For my RGB example:

// Complete spec; most significant bit first, little-endian, carrier type: u16
#[bitpacked(msbf, le, u16)] 
struct RGB565 {
    r: u5, g: u6, b: u5
}

The union-example:

// Compact value storing 31-bit unsigned integers or 
// floating point with 1-less mantissa bit.
union Value {
    u: #[bitpacked] struct U { tag: u1 = 0, v: u31 },
    f: #[bitpacked] struct F { tag: u1 = 1, s: u1, e: u8, m: u22}
}

Type-theoretic rant

This would require the type-checker to know more about type-level natural numbers, and I think this just might interest the more type-theoretic types out there. Indeed, to extend it generically, we’d get something like:

fn read<I, R>(index: I, array: &[R; N]) where I <: Nat<N> {
    array.get_unchecked(i) // safe!
}

And somehow the typechecker knows that u32 (or Unsigned<32>) equals Nat<Exp2(32)-1> (natural type number), which equals Nat(0xFFFF_FFFF), and I’ve invented the <: syntax to mean sub-type.

[bascule]

The main language-level bit structure mechanism I’m aware of is Erlang’s

I just wanted to +1 this, and also note that the real power of the Erlang bit syntax is combining it with pattern matching. Here’s an example from the linked page:

case Dgram of 
    <<?IP_VERSION:4, HLen:4, SrvcType:8, TotLen:16, 
      ID:16, Flgs:3, FragOff:13,
      TTL:8, Proto:8, HdrChkSum:16,
      SrcIP:32,
      DestIP:32, RestDgram/binary>> when HLen>=5, 4*HLen=<DgramSize ->
        OptsLen = 4*(HLen - ?IP_MIN_HDR_LEN),
        <<Opts:OptsLen/binary,Data/binary>> = RestDgram,
    ...
end.

As @cbiffle said, this is primarily useful specifically for the case of destructuring binary data i.e. protocol parsing as seen in the example above, but it’s an amazing feature of Erlang and one I think would fit quite well into Rust.

[newpavlov]

Personally I strongly dislike the idea of adding u1, u2, etc. to the language. In my opinion better approach will be introduction of something like BitArray<N> where N is the type level integer. If we add additional restraints on N (e.g. from this RFC) we could define convenience methods for conversion to other types with necessary limits on N if needed. (e.g. to_be_u8 and to_le_u8 will be defined only for 0<=N<=8, and to_bool only for N=1) So color example will look something like this:

// bitpacked will join booleans and BitArray, if struct has integers fields
// they will be stored as usual
#[bitpacked] 
struct RGB565 {
    r: BitArray<5>, g: BitArray<6>, b: BitArray<5>
}

impl RGB565 {
    fn r(self) -> u8 { self.r.to_le_u8() }
    fn g(self) -> u8 { self.g.to_le_u8() }
    fn b(self) -> u8 { self.b.to_le_u8() }
    // if r=>32 ignore significant bits
    fn set_r(&mut self, r: u8) { self.r.set_le_u8(r) }
    fn set_g(&mut self, g: u8) { self.r.set_le_u8(g) }
    fn set_b(&mut self, b: u8) { self.r.set_le_u8(b) }
}

[engstad]

@newpavlov I see that you dislike the idea of {u,i}N syntax, but you don’t explain why that is, so I am not sure how to respond. Note that the word “bit-array” has a very different connotation than what we are talking about here; we are thinking of u5 as a type for values {0, 1, ..., 31}, not as an array of bits.

Having said that; I could imagine combinations such as:

• UInt<N> and Int<N>
• UnsignedInt<N> and SignedInt<N>

The problem is that these types need a representation within the type-checker, and as such, they are “primitive types,” not something that resides in userland. The compiler needs to know the bit-size. So perhaps the right syntax should follow the lower-case convention:

Short | Long
------+---------
u<N>  | uint<N>
i<N>  |  int<N>

Keep in mind, the longer the type names are, you will get a more cluttered and unreadable type specification. I think that is something you want to avoid. As a matter of fact, I would probably always type define

type u1 = u<1>;
type u2 = u<2>;
type u3 = u<3>;
// and so on

[engstad]

#[bitpacked(network_order)] 
struct DataGramHdr {
  ip_version: u4, hdr_len: u4,
  srvc_type: u8,
  total_len : u16,
  id : u16,
  flags: u3, frag_offset: u13,
  ttl: u8, proto: u8, 
  hdr_checksum: u16,
  src_ip, dst_ip: u32  
}

{
  if dgram.hdr_len >= 5 && 4 * dgram.hdr_len <= dgram_size {
    // ...
  }
}

[matthieum]

Certainly storage.field += 1 should wrap around if storage.field == 15.

This would be a jarring departure from Rust’s behavior with other integral types. Note that today, underflow and overflow result in an unspecified value in Rust: by default they panic in Debug and wrap in Release, but the hope is to get them to always panic by default (once performance is sorted out).

A specific wrapping operation (or wrapper type) is necessary to get the wrapping behavior.

If you wish for i1 or u4, I strongly advise following the semantics of their predecessors.

[engstad]

@matthieum Thanks for pointing that out!

I wish there was a more ergonomic way of writing wrapping, saturating, and overflowing adds in Rust, but that’s for another RFC.

[newpavlov]

The main reason why I don’t like {u,i}N syntax is that it blends with existing types while behaving quite differently. Also I don’t know any languages which implement such types and this is a clearly a worrying sign.

In my opinion such types will add too much implicit magic behind curtains compared to something like BitArray which explicitly shows what we are working with bits with explicit conversion between bits to integers with regard to big and little endians. In other words cost of such solution will be too high for, lets be honest, quite niche use case.

Less extreme solution could be use of [bool; N] with compiler support for bit packing and some trait which will add convenience methods for bits conversion and representation. Yes, it will be significantly more verbose, but it can be done without drastic changes to the language and it will follow Rust’s explicitness inclination.

[engstad]

First, thank you for clarifying your position. I do see an issue with the difference between the native u8 type and the bitfield type u<8>, and I agree - unless the semantic of those types are the same, we can’t use the same syntax.

However, I’d like to challenge you on the “quite niche use case,” quote. I’m quite certain that it depends on what you program. If you’ve ever had the chance to work on microcontrollers, or low-level interfaces to hardware and binary formats, you would not think that way. As a matter of fact, for me, that comment comes off almost rude, though I’m sure that’s not what you intended!

So, let me just put it out there:

• For system programming dealing with low-level hardware and binary data, the main pain-point in using Rust is the lack of ergonomic bit-level access to binary data.

This is what we are trying to solve here. And that is why some people get excited about the idea of proper bit-field support in Rust.

[bascule]

I think you missed the part where the Erlang version is performing a pattern matching operation (see the original page for additional context). How would you unpack the binary data with pattern matching ala:

match dgram {
  DataGramHdr(...) => ...
}

[Ixrec]

I agree that mixing real integer types with arbitrary bit lengths is a bad idea, but I also find this point very persuasive:

… these types need a representation within the type-checker, and as such, they are “primitive types,” not something that resides in userland. The compiler needs to know the bit-size …

So what about using b instead of i or u?

#[bitpacked(network_order)] 
struct DataGramHdr {
  ip_version: b4, hdr_len: b4,
  srvc_type: b8,
  total_len : b16,
  id : b16,
  flags: b3, frag_offset: b13,
  ttl: b8, proto: b8, 
  hdr_checksum: b16,
  src_ip, dst_ip: b32  
}

[engstad]

My original RFC had something akin to normal match:

match dgram {
  DataGramHdr { hdr_len: hlen, .. } => ...
}