Runtime: Reading bits from arbitrary data types (especially byte[array])

[juliusfriedman]

Background and Motivation

Is very common, we have BitVector BitSet both of which are little endian only afaik.

Proposed API

namespace System.Buffers
{
//nuint instead of int ,long maybe better?
+public static long ReadBits(byte[] bytes, int bitOffset, int bitCount, bool reverse);
+public static void WriteBits(byte[] bytes, int bitOffset, int bitCount, long value, bool reverse)
     }

Usage Examples

Writing a LE 16 bit value on BE

c# var value = System.Buffers.WriteBits(someByteArray, 0, 16, false == BitConverter.IsLittleEndian)
Writing a BE 16 bit value on LE

```c#
var value = System.Buffers.WriteBits(someByteArray, 0, 16, ushort.MaxValue, BitConverter.IsLittleEndian)
````

Alternative Designs

Not sure, Prior art here

Risks

LOW, People get this wrong all the time.

cc @danmosemsft

[Dotnet-GitSync-Bot]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[mburbea]

Are you missing some parameters in your example?
What's wrong with the existing BinaryPrimitives?

BinaryPrimitives.TryWriteInt64LittleEndian(bytes.AsSpan(offset), 8675309u);
BinaryPrimitives.TryWriteInt64BigEndian(bytes.AsSpan(offset), 8675309u);

[juliusfriedman]

Are you missing some parameters in your example?
What's wrong with the existing BinaryPrimitives?

BinaryPrimitives.TryWriteInt64LittleEndian(bytes.AsSpan(offset), 8675309u);
BinaryPrimitives.TryWriteInt64BigEndian(bytes.AsSpan(offset), 8675309u);

Nothing but I just want the higher level class that can do both as the same time, I think my proposed API is more user friendly.

Additionally what if you wanted 3 bits?

Skip 2 bits and then read 1 bit?

Yes a mask is probably better but the API / JIT can maybe even optimize that depending on certain things.

This API allows reading from any position and any number of bits up to 64 but technically not limited to such.

[msftbot[bot]]

Tagging subscribers to this area: @tannergooding, @pgovind
Notify danmosemsft if you want to be subscribed.

[mburbea]

Your api lists a method for write with 5 parameters, yet you're calling it with 4.

[FiniteReality]

I don't think users get this wrong enough to warrant APIs like this. BinaryPrimitives works good enough for >8 bits, and just getting the byte out of the array works for <=8 bits.

[juliusfriedman]

People need to read nibbles and bits. Sometimes 1 likely more, mostly not aligned.

https://tools.ietf.org/html/rfc3550#section-5.1

[danmosemsft]

@juliusfriedman some examples of evidence of need we see in API proposals are - existing .NET libraries that are widely used to solve this problem; popular examples in other major ecosystems; several customers or community members sharing examples of how they would use it; examples of code in this repo or other repos (grep.app) that would be improved if this API exists; etc.

Every API has a cost - as well as design/implementation there is also maintenance, docs, and cognitive load on users. That API will exist likely for 10-20 years or more. So we have to have fairly solid evidence it will be used and valued - it has to be more than some apparent value.

[juliusfriedman]

I understand you. Thank you for your input!

I would also like to see Endian agnostic support but myself was only able to cope with Big, Little and the middles, who knows what I missed and I did not propose anything hard IMHO or that would not provide value. I did not propose the Endian converter or other such types like BitOrder/ByteOrder etc which I have implemented and do actually work.

With that typed, how would you suggest users handling something like a MPEG TS bit stream? Most of the fields are bit packed there and also mostly not aligned.

Yes they can read in bytes, mask and shift but this is work which users will get wrong where as these API's cannot.

I will find the examples but SNIPacket I believe as well as TDSStream are going to use these as well as in any other place where you want to read more than 1 bit from a byte at an unaligned location.

I know R2R also has methods for reading bits separated from the runtime but no writing bit capabilities. Those methods are optimized and do not use BinaryPrimitives.

https://github.com/dotnet/runtime/blob/6072e4d3a7a2a1493f514cdf4be75a3d56580e84/src/coreclr/src/tools/aot/ILCompiler.Reflection.ReadyToRun/Amd64/GcInfo.cs#L113

https://github.com/dotnet/runtime/search?q=ReadBits&unscoped_q=ReadBits

Thank you for the link

(AsnReader,KerberosAPRequestAuthenticationToken, etc)
https://grep.app/search?q=ReadBits&filter[path.pattern][0]=dotnet

I also also fairly certain that in HTTP2, Compression and various other places this API will be useful and performance oriented vs the user trying to mask and shift themselves.

[john-h-k]

why not just MemoryMarshal.Read<T> and shift the outputted bits (as that is probably the most efficient way anyway)?

[FiniteReality]

With that typed, how would you suggest users handling something like a MPEG TS bit stream? Most of the fields are bit packed there and also mostly not aligned.

Most of the values in MPEG streams are actually aligned to some useful position: each set of related values is packed into a single byte, so you can easily use masking and shifting to read them. Looking at the documentation on wikipedia, I can do this:

// Expects a packet aligned to the first sync byte
bool TryReadMpegTsPacket(ReadOnlySpan<byte> packet)
{
    var syncByte = stream[0];
    if (syncByte != 0x74) return false; // invalid sync byte

    if (!BinaryPrimitives.TryReadUInt16BigEndian(packet.Slice(1), out ushort packetMetadata))
        return false; // not enough bytes

    var packetFields = stream[3];

    var errorIndicator = (packetMetadata & 0x8000) >> 15;
    var startIndicator = (packetMetadata & 0x4000) >> 14;
    var priority = (packetMetadata & 0x2000) >> 13;
    var packetId = packetMetadata & 0x1FFF);
    var scramblingControl = (packetFields & 0xC0) >> 6;
    var fieldControl = (packetFields & 0x30) >> 4;
    var continuityCounter = (packetFields & 0x0F);

    // TODO: validate, likely assign out parameters, etc.
    return true;
}

[juliusfriedman]

why not just MemoryMarshal.Read<T> and shift the outputted bits (as that is probably the most efficient way anyway)?

Endian and BitOrder are seperate things and not all bits are contiguous...

[juliusfriedman]

With that typed, how would you suggest users handling something like a MPEG TS bit stream? Most of the fields are bit packed there and also mostly not aligned.

Most of the values in MPEG streams are actually aligned to some useful position: each set of related values is packed into a single byte, so you can easily use masking and shifting to read them. Looking at the documentation on wikipedia, I can do this:

// Expects a packet aligned to the first sync byte
bool TryReadMpegTsPacket(ReadOnlySpan<byte> packet)
{
    var syncByte = stream[0];
    if (syncByte != 0x74) return false; // invalid sync byte

    if (!BinaryPrimitives.TryReadUInt16BigEndian(packet.Slice(1), out ushort packetMetadata))
        return false; // not enough bytes

    var packetFields = stream[3];

    var errorIndicator = (packetMetadata & 0x8000) >> 15;
    var startIndicator = (packetMetadata & 0x4000) >> 14;
    var priority = (packetMetadata & 0x2000) >> 13;
    var packetId = packetMetadata & 0x1FFF);
    var scramblingControl = (packetFields & 0xC0) >> 6;
    var fieldControl = (packetFields & 0x30) >> 4;
    var continuityCounter = (packetFields & 0x0F);

    // TODO: validate, likely assign out parameters, etc.
    return true;
}

The point is that this can give a more general API, see some of the RFC's for accessing things like AAC Audio headers

[FiniteReality]

The same applies to RTP streams - most related values are bitpacked into a single byte, and then you read the stream using masking and shifting on single bytes.

As for "AAC audio headers", I believe the RFC you linked is not the correct one, since that RFC only goes over the RTP stream header for MPEG-4 streams. RTP is designed so that the payload of a packet is opaque, meaning that the RTP layer doesn't know how to read any of the information you seem to be suggesting it can.

[juliusfriedman]

The same applies to RTP streams - most related values are bitpacked into a single byte, and then you read the stream using masking and shifting on single bytes.

As for "AAC audio headers", I believe the RFC you linked is not the correct one, since that RFC only goes over the RTP stream header for MPEG-4 streams. RTP is designed so that the payload of a packet is opaque, meaning that the RTP layer doesn't know how to read any of the information you seem to be suggesting it can.

Sorry try this:

https://github.com/juliusfriedman/net7mma_core/blob/fd895adbce2f4776eee5695431c7b35eb9c1be78/RtspServer/MediaTypes/RFC3640Media.cs#L106

You see the 2 styles there, you tell me which which one is more correct, better looking and has the better performance potential?

WRT to the technicalities, if I have code like that in my project I shouldn't need to justify it's doing what it's doing on every platform I run on, I need an API I can just use everywhere....

Consider a data-structure I define:

https://gist.github.com/juliusfriedman/51877ed34a9cf874e700ead77e57a782

[FiniteReality]

I'm going to be honest, the bit shifting one looks more correct and better looking. And it also has the better performance potential, since it's O(1) rather than what looks like at least O(N). Shifts and masks can be confirmed and checked just by looking over the code with more than one set of eyes, while your other code is pretty hard to skim through; especially since you're not saying clearly where various fields are.

[juliusfriedman]

I'm going to be honest, the bit shifting one looks more correct and better looking. And it also has the better performance potential, since it's O(1) rather than what looks like at least O(N). Shifts and masks can be confirmed and checked just by looking over the code with more than one set of eyes, while your other code is pretty hard to skim through; especially since you're not saying clearly where various fields are.

I am not sure what you mean, just because my current impl is not optimized does not it cannot be done, see R2R ReadBits linked above, it uses shifts and masks that it computes so why not share this logic every similar to Hex conversion? What makes it cleaner to do this manually?

[FiniteReality]

Could you link that as a gist, please? It's hard to browse through code in issue comments unless it's short snippets. However, from what I can see, it's much harder to understand where each bit is going, which is important when you're doing bit packing.

Compare:

var myPackedValue = (myByte & 0b00_11_11_00 << 2) | myOtherByte;
// versus
byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, 0, 4, myByte, 2);
WriteBits(myPackedValue, 4, 4, myOtherByte, 4);

It's hard to actually know what 0, 4, and 2 actually mean, so you'd end up documenting them:

byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, startBit: 0, length: 4, value: myByte, bitOffset: 2);
WriteBits(myPackedValue, startBit: 4, length: 4, value: myOtherByte, bitOffset: 0);

And even then, the argument order is a bit screwy, so you'd end up changing it, and that necessitates renaming parameters to avoid confusion:

byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, value: myByte, valueBitOffset: 2 writeBitOffset: 0, length: 4);
WriteBits(myPackedValue, value: myOtherByte, valueBitOffset: 0, writeBitOffset: 4, length: 4);

And now, compared to the initial shifting, masking and packing, we've got:

var myPackedValue = (myByte & 0b00_11_11_00 << 2) | myOtherByte;
// versus
byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, value: myByte, valueBitOffset: 2 writeBitOffset: 0, length: 4);
WriteBits(myPackedValue, value: myOtherByte, valueBitOffset: 0, writeBitOffset: 4, length: 4);

That's 64 characters versus 221 characters. The shifting, masking and packing is objectively shorter, and in my opinion, a lot easier to read.

[juliusfriedman]

Could you link that as a gist, please? It's hard to browse through code in issue comments unless it's short snippets. However, from what I can see, it's much harder to understand _where_ each bit is going, which is important when you're doing bit packing.

Compare:

var myPackedValue = (myByte & 0b00_11_11_00 << 2) | myOtherByte;
// versus
byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, 0, 4, myByte, 2);
WriteBits(myPackedValue, 4, 4, myOtherByte, 4);

It's hard to actually know what 0, 4, and 2 actually mean, so you'd end up documenting them:

byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, startBit: 0, length: 4, value: myByte, bitOffset: 2);
WriteBits(myPackedValue, startBit: 4, length: 4, value: myOtherByte, bitOffset: 0);

And even then, the argument order is a bit screwy, so you'd end up changing it, and that necessitates renaming parameters to avoid confusion:

byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, value: myByte, valueBitOffset: 2 writeBitOffset: 0, length: 4);
WriteBits(myPackedValue, value: myOtherByte, valueBitOffset: 0, writeBitOffset: 4, length: 4);

And now, compared to the initial shifting, masking and packing, we've got:

var myPackedValue = (myByte & 0b00_11_11_00 << 2) | myOtherByte;
// versus
byte[] myPackedValue = new byte[1];
WriteBits(myPackedValue, value: myByte, valueBitOffset: 2 writeBitOffset: 0, length: 4);
WriteBits(myPackedValue, value: myOtherByte, valueBitOffset: 0, writeBitOffset: 4, length: 4);

That's 64 characters versus 221 characters. The shifting, masking and packing is objectively shorter, and in my opinion, a _lot_ easier to read.

I didn't realize we measure performance with typed characters, and you named every single parameter... I think the example you give is a bit contrived. Thank you for your input.

[FiniteReality]

Performance is hard to improve if the code is unreadable. The easier to read and understand you can make things, the easier it is to focus on the algorithm at work and actually writing the high performance code.

I don't think my scenario is too contrived, and I named the parameters because WriteBits(myPackedValue, myByte, 2, 0, 4) is a bit vague when you look at it. If I've been away from the code for a week, and I come back to random number parameters without context, I'll be a little confused for the first few minutes. Meanwhile, with named parameters, I'd at least easily understand at a glance what the parameters mean.

With the bitshifting method, I can pretty easily figure out exactly what bits and offsets I'm looking for, due to the obvious nature of operators like << and &, so for a proposal like this to take off, such methods need to be at least as clear as shifting and masking.

[eanova]

With MPEG my bitstream api is built around this functionality.
void Write(int value, int #bits) and uint Read(int #bits)

Endianness is not really an issue in bitstreams unless you are reading multiple bytes from the stream at which point your position in the bitstream is always byte aligned so you can read them as bytes instead.