Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: math/bits: add Select to select bit fields #66200

Open
dsnet opened this issue Mar 8, 2024 · 4 comments
Open

proposal: math/bits: add Select to select bit fields #66200

dsnet opened this issue Mar 8, 2024 · 4 comments
Labels
Milestone

Comments

@dsnet
Copy link
Member

dsnet commented Mar 8, 2024

Proposal Details

In many wire formats (e.g., CBOR, zstandard, brotli, etc.), it is common to have fields in a integer semantically represent something else. Examples: zstd frame descriptor, window descriptor, CBOR packing for major type and "additional information", etc.

Bit fields can be trivial selected out an integer through bit-shift and mask operations, but the code is not as readable:

blockType := (blockHeader >> 1) & 3

I propose adding:

// Selects selects n bits starting at the ith bit.
// Indexing begins with the least-significant bit.
// Bit fields beyond the representation are implicitly treated as zero.
func Select(x uint, i, n uint) uint {
    return (x >> i) & ((1 <<  n) - 1)
}

along with the 8, 16, 32, and 64 variants.

Example usage:

lastBlock := bits.Select32(blockHeader, 0, 1)
blockType := bits.Select32(blockHeader, 1, 2)
blockSize := bits.Select32(blockHeader, 3, 21)

The goal of this API is for readability of bit-twiddling code, rather than performance (which should not be affected).
Since Select is inlineable, it will practically be identical to the bitwise code that someone may write after the compiler applies constant folding.

An open API question is whether to represent a selection as:

  • an offset and length as currently proposed, or
  • a start offset and inclusive end offset, or
  • a start offset and exclusive end offset (similar to slicing).

I chose to represent it as a length as this avoids any edge cases for when the end offset is before the start offset.

@dsnet dsnet added the Proposal label Mar 8, 2024
@gopherbot gopherbot added this to the Proposal milestone Mar 8, 2024
@ianlancetaylor
Copy link
Contributor

This operation is often called extract, as in the Intel BEXTR instruction or the Rust bextr method (https://docs.rs/bitintr/latest/bitintr/trait.Bextr.html). I think Extract would be a better name than Select.

That said I'm not 100% sold on a function that takes three arguments all of the same type. It seems easy to mix things up. And why are i and n type uint anyhow? Wouldn't it be more typical of Go to make them type int?

@randall77
Copy link
Contributor

I feel like if we're going to include this, we probably want the other direction (Insert) as well?

They both seem pretty simple, not sure they need to be in math/bits. Most of the stuff there constitutes intrinsics that can't be easily written in Go.

@apparentlymart
Copy link

apparentlymart commented Mar 9, 2024

Could this be written as a generic function over a constraint including all of the unsigned integer types?

type Bits interface {
    uint | uint8 | uint16 | uint32 | uint64
}

func Extract[B Bits](x B, i, n int) B {
    return (x >> i) & ((1 <<  n) - 1)
}

I see that the functions already in that package are not generic, but I'm not sure if that's just because this package predated generics or if there's an important implementation reason. (I do notice that some of them have tailored implementations for each size, and so could not be trivially generalized.)

FWIW, I do kinda agree that this function isn't clearly needed. I don't think I'd go looking for a function like this in stdlib if I hadn't seen this proposal, because I'm accustomed to having to do this sort of thing directly with arithmetic operators in other languages. It does seem like it would improve readability of code that uses it, though.

@renthraysk
Copy link

There was a proposal for the parallel versions, PDEP & PEXT.

#45455 proposal: math/bits: add Deposit and Extract functions

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Incoming
Development

No branches or pull requests

6 participants