API proposal: bitwise operations on Span(of byte) buffers

[GrabYourPitchforks]

Currently we have some bitwise operators for the Vector<T> type. It would be useful for some scenarios (especially cryptography, where xoring two long buffers is common) to extend these bitwise operators to arbitrary-length spans.

A strawman API follows.

namespace System.Buffers {
    public static class Span {
        public static void And(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b, Span<byte> output);
        public static void AndNot(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b, Span<byte> output);
        public static void Not(ReadOnlySpan<byte> input, Span<byte> output);
        public static void Or(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b, Span<byte> output);
        public static void Xor(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b, Span<byte> output);
    }
}

Since these are all bitwise operations, they operate on a bit-by-bit level. (This means that Not is actually the bitwise inverse operation.)

If we had a T : numeric constraint, we could use that and have generic Span<T> overloads instead of simply Span<byte>. I don't think it would be good to have a broad T : struct constraint because it's not valid to perform bitwise operations over arbitrary structs, even if those structs don't contain references.

Proposed behaviors: The input length(s) must match the output length exactly, otherwise an exception is thrown. It should also be possible to pass one of the input buffers as the destination buffer as long as the buffers overlap exactly. Passing an output buffer that partially overlaps with one of the input buffers will have undefined behavior.

The implementations can take advantage of vectorization or hardware intrinsics when available. But the APIs should be able to accept inputs of arbitrary length, even if the length isn't an exact multiple of the platform's native SIMD size.

[benaadams]

Websocket is an example of xoring Spans https://github.com/dotnet/corefx/blob/e36eaec682d5fa81bc1754e89787b0353b9c46b8/src/Common/src/System/Net/WebSockets/ManagedWebSocket.cs#L1255-L1269

[GrabYourPitchforks]

I considered WebSockets for this example but I don't know if it would benefit. The target mask for WebSockets is 32 bits (repeated indefinitely), so it would fail the length check. And I don't think we'd want to say that the behavior of this routine as a policy is to repeat whichever input is shorter.

[vcsjones]

This looks great!

It should also be possible to pass one of the input buffers as the destination buffer

That is a "big want" from me.

Passing an output buffer that partially overlaps with one of the input buffers will have undefined behavior.

Makes sense, but is there any way to give a runtime exception instead?

public static void AndNot(ReadOnlySpan<byte> a, ReadOnlySpan<byte> b, Span<byte> output)

Why a dedicated operation for AndNot when there is And and Not already? What about Nor, Xnor, etc?

Is this because AndNot has more perceived value than other combinations?

[vcsjones]

Passing an output buffer that partially overlaps with one of the input buffers will have undefined behavior.

Would it make more sense to have overloads like

public static void Xor(ReadOnlySpan<byte> src1, Span<byte> src2AndDest);

This seems to guarantee they overlap then since it is the same parameter? This way there would be no runtime cost for performing a check.

Although I suppose src1 and src2AndDest could partially overlap and you're back at the same problem.

[GrabYourPitchforks]

Re: AndNot, it's mainly because processors already provide intrinsics for this. I have no real need for this specific API.

[am11]

Would Xnor (which is identical to if and only if - iff) API make sense, as there are related intrinsics in AVX 512?

[mgravell]

I assume this pattern would be repeated for other data types? i.e.

public static void And(ReadOnlySpan<int> a, ReadOnlySpan<int> b, Span<byte> output);
...
public static void And(ReadOnlySpan<long> a, ReadOnlySpan<long> b, Span<long> output);

using MemoryMarshal.Cast to do the heavy lifting to share implementations here.

---

re the websocket "repeating mask" scenario... actually, I suspect that is a not uncommon scenario; maybe there should also be operators that take a single value to mean exactly this, i.e.

public static void And(ReadOnlySpan<long> a, long b, Span<long> output);
public static void Xor(ReadOnlySpan<long> a, long b, Span<long> output);

(noting that you only have to implement it once per bit-width; ulong and long can use MemoryMarshal.Cast to share a single implementation)

which is also readily vectorized. In the case of web-sockets, the caller would have to deal with any trailing bits themselves; I think that is perfectly reasonable! Meaning: we should not consider:

public static void Xor(ReadOnlySpan<byte> a, long b, Span<byte> output);

(meaning "apply b as many times as possible to a, including any trailing bits)

[vcsjones]

@mgravell

I assume this pattern would be repeated for other data types? i.e.

I think for simplicity's sake the types must always match. I'm not sure if your first example:

public static void And(ReadOnlySpan<int> a, ReadOnlySpan<int> b, Span<byte> output);

Where the last parameter is a Span<byte> for output was a copy-and-paste error or if you meant Span<int>.

"repeating mask" scenario... actually, I suspect that is a not uncommon scenario

Perhaps? I would be interested in knowing more use cases for that myself.

the caller would have to deal with any trailing bits themselves; I think that is perfectly reasonable!

Agreed, that is a reasonable idea.

[mgravell]

@vcsjones - yes, copy/pasta - should have matched

[omariom]

Other than byte overloads will be hiding non-portability.

[GrabYourPitchforks]

Yeah, I'm not sure about the int overloads that take a repeating pattern (as in the WebSockets scenario). The caller would need to use an unsafe cast in order to get the input span from byte to int, and we shouldn't encourage the use of unsafe code by consumers of this API.

(I think this is the point @omariom was making above.)

[ahsonkhan]

Should these go under an existing class, like BinaryPrimitives (within System.Buffers.Binary)?

[vcsjones]

I would suggest a new class, nothing existing leaps out at me as a good candidate. I like the namespace in the proposal, but not the class name. Two types named Span is confusing.

I'm also not sold on the overloads accepting non-byte spans like int.

[tannergooding]

Worth noting that most elsewhere we've exposed Not as OnesComplement.

Its typically been: BitwiseAnd, BitwiseOr, AndNot, OnesComplement, Xor. It's definitely not the most consistent overall, however.

[stephentoub]

These are now available on TensorPrimitives.