math/bits: an integer bit twiddling library

brtzsnr commented 7 years ago

Previous discussions at https://github.com/golang/go/issues/17373 and https://github.com/golang/go/issues/10757.

Abstract

This proposal introduces a set of API for integer bit twiddling.

Background

This proposal introduces a set of API for integer bit twiddling. For this proposal we are interested in the following functions:

ctz - count trailing zeros.
clz - count leading zeros; log_2.
popcnt - count population; hamming distance; integer parity.
bswap - reverses the order of bytes.

These functions were picked by surveying:

Go compiler and tools
Popular libraries
golang-nuts@ discussions list
Bit Twiddling Hacks - https://graphics.stanford.edu/~seander/bithacks.html
A curated list of awesome bitwise operations and tricks - https://github.com/keonkim/awesome-bits

We limited ourselves to these four functions because other twiddling tricks are very simple to implement using the proposed library, or already available Go constructs.

We found implementations for a subset of the selected twiddling functions in many packages including runtime, compiler and tools:

package	clz	ctz	popcnt	bswap
math/big	X	X
runtime/internal/sys	X	X		X
tools/container/intsets	X		X
cmd/compile/internal/ssa	X		X
code.google.com/p/intmath	X	X
github.com/hideo55/go-popcount			X (asm)
github.com/RoaringBitmap/roaring		X	X (asm)
github.com/tHinqa/bitset	X	X	X
github.com/willf/bitset	X		X (asm)
gopl.io/ch2/popcount			X
GCC builtins	X	X	X	X

Many other packages implement a subset of these functions:

http://go-search.org/search?q=popcount returns 58 packages.
http://go-search.org/search?q=popcnt returns 11 packages.
TODO(mosoi): Other relevant searches?

Similarly hardware providers have recognized the importance of such functions and included machine level support. Without hardware support these operations are very expensive.

arch	clz	ctz	popcnt	bswap
AMD64	X	X	X	X
ARM	X	X	?	X
ARM64	X	X	?	X
S390X	X	X	?	X

All bit twiddling functions, except popcnt, are already implemented by runtime/internal/sys and receive special support from the compiler in order to "to help get the very best performance". However, the compiler support is limited to the runtime package and other Golang users have to reimplement the slower variant of these functions.

Proposal

We introduce a new std library math/bits with the following external API, to provides compiler / hardware optimized implementations of clz, ctz, popcnt and bswap functions.

package bits

// SwapBytes16 reverses the order of bytes in a 16-bit integer.
func SwapBytes16(uint16) uint16
// SwapBytes32 reverses the order of bytes in a 32-bit integer.
func SwapBytes32(uint32) uint32
// SwapBytes64 reverses the order of bytes in a 64-bit integer.
func SwapBytes64(uint64) uint64

// TrailingZeros32 counts the number of trailing zeros in a 32-bit integer, and if all are zero, then 32.
func TrailingZeros32(uint32) uint
// TrailingZeros64 counts the number of trailing zeros in a 64-bit integer, and if all are zero, then 64.
func TrailingZeros64(uint64) uint

// LeadingZeros32 counts the number of trailing zeros in a 32-bit integer, and if all are zero, then 32.
func LeadingZeros32(uint32) uint
// LeadingZeros64 counts the number of trailing zeros in a 64-bit integer, and if all are zero, then 64.
func LeadingZeros64(uint64) uint

// Ones32 counts the number of bits set in a 32-bit integer.
func Ones32(uint32) uint
// Ones64 counts the number of bits set in a 64-bit integer.
func Ones64(uint64) uint

Rationale

Alternatives to this proposal are:

Bit twiddling functions are implemented in an external library not supported by the compiler. This approach works and is the current state of affairs. Runtime uses the compiler supported methods, while Golang users continue to use the slower implementations.
The external library is supported by the compiler. Given that we expect this library to replace runtime/internal/sys it means that this library must be in lock with the compiler and live in the standard library.

Compatibility

This proposal does not change or breaks any existing stdlib API and it conforms to compatibly guidelines.

Implementation

SwapBytes, TrailingZeros and LeadingZeros are already implemented. The only missing function is Ones which can be implemented similarly to the other functions. If this proposal is accepted it can be implemented in time for Go1.9.

Open issues (if applicable)

Names are hard, bike shed is in the comments.

Please suggest additional functions to be included in the comments. Ideally, please include where such function is used in stdlib (e.g. math/big), tools or popular packages.

So far the following functions have been proposed and are under consideration:

RotateLeft / RotateRight
- Pros: &63 is no longer need to compile a rotate with non-const argument to a single instruction on x86, x86-64..
- Cons: very short/simple to implement and inline.
- Used: crypto/ uses the constant rotate which is handled properly by the compiler.
ReverseBits
- Pros: ?
- Cons: ?
- Used: ?
Add/Sub with carry return
- Pros: Expensive otherwise
- Cons: ?
- Used: math/big

History

14.Jan: Clarified the output of TrailingZeros and LeadingZeros when the argument is 0. 14.Jan: Renamed methods: CountTrailingZeros -> TrailingZeros, CountLeadingZeros -> LeadingZeros, CountOnes -> Ones. 13.Jan: Fixed architecture name. 11.Jan: Initial proposal opened to public.

cespare commented 7 years ago

@brtzsnr perhaps you should submit this document to the proposal repo as outlined in the proposal process steps?

Since it's already markdown following the template, it should be easy to copy-paste into a CL creating a file design/18616-bit-twiddling.md (or whatever).

brtzsnr commented 7 years ago

@cespare from https://github.com/golang/proposal "if the author wants to write a design doc, then they can write one". It started as a design doc, if there is strong feeling that I should submit this, I'm totally fine.

griesemer commented 7 years ago

I'd be ok with this, it's common enough functionality used in many algorithmic libraries and math/bits seems like an appropriate place.

(For one, math/big also implements nlz (== clz).)

There's probably some bike shedding about the names. I for one would prefer the functions to say what they return rather than what they do; which in turn may lead to shorter names. For instance:

bits.TrailingZeros64(x) rather than bits.CountTrailingZeros64(x)

and so forth.

griesemer commented 7 years ago

The proposal seems pretty clear and minimal - a design doc seems overkill. I think a CL would be more appropriate at this point.

(That is a CL with API and basic implementation - for purpose of discussion in place of a design doc. We still need to decide if this proposal should be accepted or not.)

cespare commented 7 years ago

@brtzsnr has already written the design document: it's in the issue description and it follows the the template. I assumed that there was some value in having these documents all in one location.

cespare commented 7 years ago

The last arch listed in the hardware support table is "BSWAP" -- typo?

josharian commented 7 years ago

Thanks for writing this up.

The doc string for ctz and clz should specify the result when passed 0.

I also prefer (e.g.) TrailingZeros32 to CountTrailingZeros32. I'd also be happy with Ctz32. It is concise, familiar to most, and easily googleable for the rest.

cherrymui commented 7 years ago

Thanks for the proposal. I just want to add that we probably also want to focus on the use, instead of focusing only on the instructions. For example, @dr2chase once found there are several log2 functions in the compiler/assembler. It is close to CLZ but not the same. Functions like this should probably also in the bit twiddling package. And maybe also include useful functions that are not related to these instructions.

minux commented 7 years ago

How about we provide a package for all bit twiddling primitives defined by the Hacker's Delight?

When designing the package, we don't need to consider whether the function can be intrinsicified or not. The optimization can happen later. That is, don't let low level implementation control the upper level package interface. We want a good package interface, even if some of them can not be mapped to single instruction.

dsnet commented 7 years ago

@minux, fortunately, every bit twiddling function I've needed so far is exactly the ones that are in this proposal.

dr2chase commented 7 years ago

Following Hacker's Delight has the advantage that we don't need to waste time arguing about the names.

minux commented 7 years ago

I'd like to add the following:

ReverseBits (for uint32 and uint64) RotateLeft/Right (can be expanded inline with two shifts, but the compiler can't always do the transformation due to shift range issues)

Maybe also two results form of add and substract? E.g.

func AddUint32(x, y, carryin uint32) (carryout, sum uint32) // carryin must be 0 or 1. And similarly for uint64.

And SqrtInt.

Many of my suggestions can't be implemented in a single instruction, but that is the point: we want a good bit twiddling package, not a mere intrisics package. Don't let the hardware limit high level package interface.

josharian commented 7 years ago

Relatedly, functions to check whether an add/multiply will overflow.

thepudds commented 7 years ago

A related data point: there are various issues that have been filed for faster cgo. In one such example (proposal #16051), the fact that fast implementation of bsr/ctz/etc. might happen was mentioned as hopefully chipping away at the set of use cases where people writing go are tempted to use cgo.

@aclements commented on Jul 1, 2016:

@eloff, there's been some discussion (though no concrete proposals to my knowledge) to add functions for things like popcount and bsr that would be compiled as intrinsics where supported (like math.Sqrt is today). With 1.7 we're trying this out in the runtime, which now has a ctz intrinsic available to it on amd64 SSA. Obviously that doesn't solve the overall problem, but it would chip away at one more reason to use cgo in a low-overhead context.

Many people (myself included) are attracted to go because of the performance, so things like this current proposal for bit twiddling would help. (And yes, cgo is also now faster in 1.8, which is nice as well).

brtzsnr commented 7 years ago

RotateLeft/Right (can be expanded inline with two shifts, but the compiler can't always do the transformation due to shift range issues)

@minux Can you elaborate what is the problem?

randall77 commented 7 years ago

@brtzsnr : I think what Minux is referring to is that when you write (x << k) | (x >> (64-k)), you know you're using 0 <= k < 64, but the compiler can't read your mind, and it is not obviously derivable from the code. If we had the function

func leftRot(x uint64, k uint) uint64 {
   k &= 63
   return (x << k) | (x >> (64-k))
}

Then we can make sure (via the &63) that the compiler knows that the range of k is bounded. So if the compiler can't prove the input is bounded, then we need an extra AND. That's better than not generating the rotate assembly at all.

minux commented 7 years ago

On Fri, Jan 13, 2017 at 10:37 PM, Keith Randall notifications@github.com wrote:

@brtzsnr https://github.com/brtzsnr : I think what Minux is referring to is that when you write (x << k) | (x >> (64-k)), you know you're using 0 <= k < 64, but the compiler can't read your mind, and it is not obviously derivable from the code. If we had the function

func leftRot(x uint64, k uint) uint64 { k &= 63 return (x << k) | (x >> (64-k)) }

Then we can make sure (via the &63) that the compiler knows that the range of k is bounded. So if the compiler can't prove the input is bounded, then we need an extra AND. That's better than not generating the rotate assembly at all.

Right. If we define RotateLeft and RotateRight functions, we can formally define the function rotate left/right k bits (no matter what k is). This is similar to how our shift operations are defined. And this definition also maps to actual rotate instruction nicely (unlike shifts, where our more intuitive definition requires a compare on certain architectures).

ghost commented 7 years ago

How about byte and bit shuffling (and unshuffling) functions that are used by the blosc compression library? The slides (the shuffling starts from the slide 17). These functions can be SSE2/AVX2 accelerated.

minux commented 7 years ago

On Fri, Jan 13, 2017 at 11:24 PM, opennota notifications@github.com wrote:

How about byte and bit shuffling functions that are used by the blosc https://github.com/Blosc/c-blosc compression library? The slides http://www.slideshare.net/PyData/blosc-py-data-2014 (the shuffling starts from the slide 17). These functions can be SSE2/AVX2 accelerated.

SIMD is a bigger problem and it is out of the scope of this package. It's

17373.

brtzsnr commented 7 years ago

The current proposed functions have a Go native implementation much larger and disproportionally more expensive than optimum. On the other hand rotate is easy to write inline in a way that the compiler can recognize.

@minux and also everyone else: Do you know where rotate left/right is used with a non-constant number of rotated bits? crypto/sha256 uses rotate for example, but with constant number of bits.

josharian commented 7 years ago

rotate is easy to write inline in a way that the compiler can recognize.

It is easy for those who are familiar with the compiler's internals. Putting it in a math/bits package makes it easy for everyone.

Do you know where rotate left/right is used with a non-constant number of rotated bits?

Here's an example from #9337:

https://play.golang.org/p/rmDG7MR5F9

In each invocation it is a constant number of rotated bits each time, but the function itself is not currently inlined, so it compiles without any rotate instructions. A math/bits library function would definitely help here.

minux commented 7 years ago

On Sat, Jan 14, 2017 at 5:05 AM, Alexandru Moșoi notifications@github.com wrote:

The current proposed functions have a Go native implementation much larger and disproportionally more expensive than optimum. On the other hand rotate is easy to write inline in a way that the compiler can recognize.

As I stressed many times in this issue, this is not the correct way to design a Go package. It ties too much to the underlying hardware. What we want is a good bit twiddling package that is generally useful. Whether functions can be expanded into a single instruction is irrelevant as long as the API interface is well-known and generally useful.

@minux https://github.com/minux and also everyone else: Do you know where rotate left/right is used with a non-constant number of rotated bits? crypto/sha256 uses rotate for example, but with constant number of bits.

Even if in the actual problem the number of bits of rotate is constant, the compiler might not be able to see that. E.g. when the shift count is stored in an array, or hide in loop counter or even caller of a not inlined function.

One simple example of using variable number of rotate is an interesting implementation of popcount: // https://play.golang.org/p/ctNRXsBt0z

func RotateRight(x, k uint32) uint32
func Popcount(x uint32) int {
    var v uint32
    for i := v - v; i < 32; i++ {
        v += RotateRight(x, i)
    }
    return int(-int32(v))
}

brtzsnr commented 7 years ago

@josharian The example looks like a bad inliner decision if rot is not inlined. Did you try to write the function as func rot(x, n) instead of rot = func(x, n)?

@minux: I agree with you. I'm not trying to tie the API to a particular instruction set; the hardware support is a nice bonus. My main focus is to find usages in the real code (not toy code) to understand the context, what is the best signature and how important is to provide everyone's favorite function. Compatibility promise will bite us later if we don't this properly now.

For example: What should be the signature of add with carry return? Add(x, y uint64) (c, s uint64)? Looking at math/big we probably need Add(x, y uintptr) (c, s uintptr) too.

josharian commented 7 years ago

The example looks like a bad inliner decision if rot is not inlined.

Yes. It is part of a bug complaining about inlining. :)

Did you try to write the function as func rot(x, n) instead of rot = func(x, n)?

It's not my code--and that's part of the point. And anyway, it is reasonable code.

mundaym commented 7 years ago

It would be nice to guarantee (in the package documentation?) that the rotate and byte-swap functions are constant-time operations so that they can be safely used in crypto algorithms. Possibly something to think about for other functions too.

minux commented 7 years ago

On Thu, Jan 19, 2017 at 11:50 AM, Michael Munday notifications@github.com wrote:

It would be nice to guarantee (in the package documentation?) that the rotate and byte-swap functions are constant-time operations so that they can be safely used in crypto algorithms. Possibly something to think about for other functions too.

trivial implementation of byte swap is constant time, but if the underlying architecture doesn't provide variable shift instructions, it will be hard to guarantee constant time rotate implementation. Perhaps Go will never run on those architectures though.

That said, there is also non-negligible chance that the underlying microarchitecture uses a multi-cycle shifter, and we can't guarantee constant time rotate on those implementations.

If strict constant time is required, perhaps the only way is write assembly (and even in that case, it makes strong assumptions that all the used instructions are itself constant time, which implicitly depends on the microarchitecture.)

While I understand the need for such guarantees, but it's actually beyond our control.

randall77 commented 7 years ago

I'm inclined to agree with @minux. If you want constant-time crypto primitives, they should live in crypto/subtle. crypto/subtle can easily redirect to math/bits on platforms where those implementations have been verified. They can do something else if a slower but constant-time implementation is required.

rsc commented 7 years ago

This seems worth doing. Leaving for @griesemer and @randall77 to vet. The next step seems like a design doc checked into the usual place (I do see the sketch above).

griesemer commented 7 years ago

Now that this proposal can go forward, we should agree on the details of the API. Questions I see at the moment:

which functions to include?
which types to handle (uint64, uint32 only, or uint64, uint32, uint16, uint8, or uintptr)?
signature details (e.g. TrailingZeroesxx(x uintxx) uint, with xx = 64, 32, etc., vs TrailingZeroes(x uint64, size uint) uint where size is one of 64, 32, etc. - the latter would lead to a smaller API and may still be fast enough dep. on implementation)
some name bike shedding (I like the "Hacker's Delight" terminology but spelling it out may be more appropriate)
is there a better place than math/bits for this package.

@brtzsnr Would you like to continue spearheading this effort? I'm ok if you want to take your initial design and iterate upon it in this issue or if you prefer setting up a dedicated design doc. Alternatively, I can pick this up and push it forward. I like to see this getting in during the 1.9 phase.

jimmyfrasche commented 7 years ago

I prefer the spelled out xx names, personally: bits.TrailingZeroes(uint64(x), 32) is more cumbersome and less readable than bits.TrailingZeroes32(x), imo, and that naming scheme would work with the platform-variable-sized uintptr more easily (xx = Ptr?).

It would also make it more apparent if you, say, didn't include uint8 in the first release but added it later—suddenly there'd be a lot of new xx = 8 functions instead of a bunch of updated doc comments that add 8 to the list of valid sizes with a note in the release docs that's easy to miss.

If the spelled out names are used, I think the Hacker's delight terms should be included in the descriptions as an "also known as" so that searches (in page or via search engine) find the canonical name easily if you search for the wrong spelling.

I think math/bits is a fine place—it's math with bits.

dsnet commented 7 years ago

I should note that SwapBytes{16,32,64} is more consistent with functions in sync/atomic than SwapBytes(..., bitSize uint).

Although the strconv package does use the ParseInt(..., bitSize int) pattern, there is more relation between bits and atomic, than there is with strconv.

minux commented 7 years ago

Three reasons I don't like SwapBytes(uint64, size uint):

people might use it in cases where size is not compile time constant (at least to the current compiler),
it necessitate a lot of type conversions. First to convert a uint32 to uint64, and then to convert it back.
we should reserve the generic name SwapBytes for a future generic version of the function (when Go gets generics support).

brtzsnr commented 7 years ago

@griesemer Robert, please take over the proposal. I will have time to push this proposal forward in one month, but progress should not stall till then.

griesemer commented 7 years ago

It looks like there's a clear preference for signatures of the form:

func fffNN(x uintNN) uint

which leaves open which NN to support. Let's focus on NN=64 for the purpose of the continuing discussion. It will be straight-forward to add the remaining types as needed (incl. uintptr).

Which leads us straight back to the original proposal by @brtzsnr and the following functions (and their respective variations for different types), plus what people have suggested in the meantime:

// LeadingZeros64 returns the number of leading zero bits in x.
// The result is 64 if x == 0.
func LeadingZeros64(x uint64) uint

// TrailingZeros64 returns the number of trailing zero bits in x.
// The result is 64 if x == 0.
func TrailingZeros64(x uint64) uint

// Ones64 returns the number of bits set in x.
func Ones64(x uint64) uint

// RotateLeft64 returns the value of x rotated left by n%64 bits.
func RotateLeft64(x uint64, n uint) uint64

// RotateRight64 returns the value of x rotated right by n%64 bits.
func RotateRight64(x uint64, n uint) uint64

We may have a set of Swap functions as well. Personally I am skeptical about these: 1) I've never needed a SwapBits, and most uses of SwapBytes are due to code that is endian-aware when it shouldn't be. Comments?

// SwapBits64 reverses the order of the bits in x.
func SwapBits64(x uint64) uint64

// SwapBytes64 reverses the order of the bytes in x.
func SwapBytes64(x uint64) uint64

Then there may be a set of integer operations. They would only be in this package because some of them (e.g. Log2) may be close to other functions in this package. These functions could be elsewhere. Perhaps the package name bits needs to be adjusted. Comments?

// Log2 returns the integer binary logarithm of x.
// The result is the integer n for which 2^n <= x < 2^(n+1).
// If x == 0, the result is -1.
func Log2(x uint64) int

// Sqrt returns the integer square root of x.
// The result is the value n such that n^2 <= x < (n+1)^2.
func Sqrt(x uint64) uint64

Finally, @minux suggested operations such as AddUint32 etc. I'm going to leave those out for now because I think they are more tricky to specify correctly (and there's more variety). We can get back to them later. Let's get to some consensus on the above.

Questions:

Any opinions about function names?
Any opinions about the integer ops?
Any opinions about the package name/location?

bradfitz commented 7 years ago

I'd prefer long functions names. Go avoids abbreviating in function names. The comments can say their nicknames ("nlz", "ntz", etc) for people searching the package that way.

dsnet commented 7 years ago

@griesemer, you seem to have typos in your message. The comments don't match the function signatures.

I use SwapBits in compression applications. That said, do the major architectures provide any ability to do bit reversal efficiently? I was planning on just doing in my own code:

v := bits.SwapBytes64(v)
v = (v&0xaaaaaaaaaaaaaaaa)>>1 | (v&0x5555555555555555)<<1
v = (v&0xcccccccccccccccc)>>2 | (v&0x3333333333333333)<<2
v = (v&0xf0f0f0f0f0f0f0f0)>>4 | (v&0x0f0f0f0f0f0f0f0f)<<4

griesemer commented 7 years ago

@bradfitz , @dsnet : Updated signatures (fixed typos). Also updated questions (people prefer explicit names of shortcuts).

dsnet commented 7 years ago

Unless there's native support for bit-swapping, I would vote to leave out SwapBits. It can be a little ambiguous by name alone whether bits are only swapped within each byte, or across the entire uint64.

minux commented 7 years ago

Why exclude something based solely on instruction availability? Reverse bit has notable uses in FFT.

To answer your question of reverse bit instruction availability: arm has the RBIT instruction.

jimmyfrasche commented 7 years ago

@griesemer As far as the type signatures of functions like

func Ones64(x uint64) uint
func RotateLeft64(x uint64, n uint) uint64

Does RotateLeftN etc take uints because that's necessary for easy intrinisifying (when possible) or just because that's the domain? If there's not a strong technical need, there's a stronger precedent for taking ints, even if negative values don't make sense. If there is a strong technical need, should they be uintN for the appropriate N for regularity?

Regardless OnesN and its ilk should return ints unless it's so these operations can be composed with other bit operations in which case they should return a uintN for the appropriate N.

griesemer commented 7 years ago

@jimmyfrasche Because it's the domain. The cpu doesn't care. Whether somethings is an int or a uint is irrelevant for most operations except comparisons. That said, if we make it an int, we have to explain that it is never negative (result), or that it must not be negative (argument), or specify what it's supposed to do when it's negative (argument for rotation). We might be able to get away with just one Rotate in that case which would be nice.

I'm not convinced that using int makes things easier. If properly designed, uints will flow to uints (that's the case in math/big) and no conversions are needed. But even if a conversion is needed, it's going to be free in terms of CPU cost (though not in terms of readability).

But I'm happy to hear/see convincing arguments otherwise.

minux commented 7 years ago

The rotate bit count should be uint (with no specific size) to match the shift operator of the language.

The reason for not using int is that there will be ambiguity whether RotateRight -2 bits is equal to RotateLeft 2 bits.

griesemer commented 7 years ago

@minux There's no ambiguity when Rotate(x, n) is defined to rotate x by n mod 64 bits: Rotate left by 10 bits is the same as rotate right by 64-10 = 54 bits, or (if we allow int arguments) by -10 bits (assuming a positive value means rotate left). -10 mod 64 = 54. Most possibly we get the effect for free even with a CPU instruction. For instance, the 32bit x86 ROL/ROR instructions already only look at the bottom 5 bits of the CL register, effectively performing mod 32 for 32 bit rotates.

jimmyfrasche commented 7 years ago

The only real argument is regularity with the rest of the stdlib. There are numerous places where uints make a lot of sense but ints are used instead.

Since math/big is a notable exception, I don't have a problem with this being another, but it is something to consider.

I assume @minux meant ambiguity for someone reading/debugging code rather than ambiguity in the implementation, which is a persuasive argument for it taking uint.

as commented 7 years ago

Should bits.SwapBits really be named with a bits suffix when the name of the package is already called bits? How about bits.Swap?

Another idea is a bits.SwapN(v uint64, n int) rather than bits.SwapBytes where n represents the number of bits to group by for the swap. When n=1 the bits are reversed, when n=8, the bytes are swapped. One benefit is that bits.SwapBytes no longer has to exist, although I've never seen a necessity for any other value of n, maybe others will disagree.

josharian commented 7 years ago

As specified above, LeadingZeros64, TrailingZeros64, Ones64 all LGTM.

A single Rotate64 with a signed rotate amount is appealing. Most rotates will be by a constant amount, too, so (if/when this becomes an intrinsic) there'll be no runtime cost to not having separate Right/Left functions.

I have no strong opinion about bit/byte shuffling/swapping/reversing. For reversing bits, bits.Reverse64 seems like a better name. And perhaps bits.ReverseBytes64? I find Swap64 a bit unclear. I see the appeal of having Swap64 take a group size, but what is the behavior when the group size doesn't evenly divide 64? If the only group sizes that matter are 1 and 8, it'd be simpler to just give them separate functions. I also wonder whether some kind of general bit field manipulation might be better, maybe looking at arm64 and amd64 BMI2 instructions for inspiration.

I'm not convinced that integer math functions belong in this package. They seem more like they belong in package math, where they could use bits functions in their implementation. Related, why not func Sqrt(x uint64) uint32 (instead of returning uint64)?

Though AddUint32 and friends are complicated, I hope we do revisit them eventually. Along other things, MulUint64 would provide access to HMUL, which even the super-minimalist RISC-V ISA provides as an instruction. But yes, let's get something in first; we can always expand later.

bits seems clearly like the right package name. I'm tempted to say the import path should be just bits, not math/bits, but I don't feel strongly.

dsnet commented 7 years ago

bits seems clearly like the right package name. I'm tempted to say the import path should be just bits, not math/bits, but I don't feel strongly.

IMO, if it were just bits, (without reading the package docs) I would expect it to be somewhat similar to package bytes. That is, in addition to functions to operate on bits, I would expect to find a Reader and Writer for reading and writing bits to/from a byte stream. Making it math/bits makes it more obvious its just a set of stateless functions.

(I'm not proposing that we add Reader/Writer for bit streams)

mdlayher commented 7 years ago

A single Rotate64 with a signed rotate amount is appealing. Most rotates will be by a constant amount, too, so (if/when this becomes an intrinsic) there'll be no runtime cost to not having separate Right/Left functions.

I can see how it could be convenient to have a slightly smaller package API by combining rotate left/right into a single Rotate, but then there is also the matter of effectively documenting the n parameter to indicate that:

negative n results in a left rotate
zero n results in no change
positive n results in a right rotate

To me, the added mental and documentation overhead doesn't seem to justify combining the two into a single Rotate. Having an explicit RotateLeft and RotateRight where n is a uint feels more intuitive to me.

griesemer commented 7 years ago

@mdlayher Keep in mind that for an n-bit word rotating by k bits to the left is the same as rotating n-k bits to the right. Even if you separate this in two functions you still need to understand that rotating by k bits to the left always means rotating by (k mod n) bits (if you rotate by more than n bits, you start again). Once you do that, you can just say that the rotate function always rotates by k mod n bits and you're done. There's no need to explain the negative value or a second function. It just works out. It is actually simpler.

On top of that, hardware (eg on x86) even does this for you automatically, even for non-constant k.

aclements commented 7 years ago

@griesemer, a downside of Rotate is that it doesn't say which direction is positive. Does Rotate32(1, 1) equal 2 or 0x80000000? For example, if I were reading code that used that, I would expect the result to be 2, but apparently @mdlayher would expect it to be 0x80000000. On the other hand, RotateLeft and RotateRight are unambiguous names, independent of whether they take a signed or unsigned argument. (I disagree with @minux that it's ambiguous whether RotateRight by -2 is equal to RotateLeft 2. These seem obviously equivalent to me and I don't see how else you could specify them.)

golang / go