Runtime: Proposal: Expose existing BitOps methods

[grant-d]

In a series of recent PRs (LZCNT, LOG2, TZCNT, ROTL/R, POPCNT) we consolidated and perf-tuned a basic set of bit-twiddling routines into a coreclr internal static class.
The ask is to expose these methods as public in corefx (via ref assembly).

Rationale and Usage

Background & justification in the related issue https://github.com/dotnet/corefx/issues/32269 (which also proposes BT, BTS, BTR, BTC intrinsics)

Here is a brief summary to avoid reading the miles of comments there:

Duplicate implementations of the proposed functions were already implemented pervasively throughout the stack (coreclr, corert, corefx), often with different algorithms and certainly with different performance characteristics and little to no explicit test coverage.
Some existing callsites listed here
Some of the implementation had suboptimal performance or bugs.

These issues have been attended to, but the class is internal and so not easily available for consumption by downstream projects.

Scope

This issue is scoped to exposing just the existing methods.
There is no intent to add new signatures in this issue (unless required by api review)

Proposed API

Existing implementation here: BitOps.cs

namespace System
{
    ...
    public static partial class BitOps
    {
        public static int LeadingZeroCount(uint value) { throw null; }
        public static int LeadingZeroCount(ulong value) { throw null; }

        public static int Log2(uint value) { throw null; }
        public static int Log2(ulong value) { throw null; }

        public static int PopCount(uint value) { throw null; }
        public static int PopCount(ulong value) { throw null; }

        public static uint RotateLeft(uint value, int bitOffset) { throw null; }
        public static ulong RotateLeft(ulong value, int bitOffset) { throw null; }
        public static uint RotateRight(uint value, int bitOffset) { throw null; }
        public static ulong RotateRight(ulong value, int bitOffset) { throw null; }

        public static int TrailingZeroCount(int value) { throw null; }
        public static int TrailingZeroCount(long value) { throw null; }
        public static int TrailingZeroCount(uint value) { throw null; }
        public static int TrailingZeroCount(ulong value) { throw null; }
    }
    ...
}

Details

The internal routines have already been implemented as follows:

• Centralized & standardized implementation of several intrinsics (LZCNT, LOG2, TZCNT, ROTL/R, POPCNT)
• Uses hardware intrinsics where possible
• Optimized software fallbacks
• Updated all known callsites in coreclr
• Added unit tests for all BitOps methods (in corefx)

There are downstream callsites in corefx and corert as well as externals such as roslyn that would benefit from these intrinsics, as well as external (3rd party) projects.

cc @tannergooding, @jkotas

[jkotas]

Should Log2 return int?

[grant-d]

Should Log2 return int?

Sorry, that was a typo - the existing code does indeed return an int. Fixed spec.

[fanoI]

Why the are no SetBit(), InsertBit() and ExtractBit()?

[jkotas]

They will be discussed in the next phase. This first phase is adding the APIs that proved to be valuable by having many use cases in our own coreclr/corefx.

[dzmitry-lahoda]

@fanol, it seems all other operations are here https://github.com/k2workflow/Clay/blob/master/src/SourceCode.Clay/BitOps.cs . Seems developer of proposal owns that repo and maintains all other operations here. I will use it, until will be able to swap to corefx implementations (hopefully with zero changes).

[grant-d]

Any progress on getting this approved in api-review?

[tannergooding]

The next API review is tomorrow (and generally speaking, every Tuesday). We'll see if we can get to it.

[khellang]

Any reason these couldn't be in BinaryPrimitives? 🤔

[terrajobst]

Video

Having a separate type makes sense as the existing types don't make sense (Math, BitConverter). We shouldn't put it in the System namespace though?

C# namespace System.Numerics { public static partial class BitOperations { } }

[jkotas]

Exposed by https://github.com/dotnet/corefx/pull/35606