add bitrotate

[matthias314]

This seems to be missing so far. The implementation follows that for Julia integers, taking into account that the bit length may not be a power of 2.

Strangely, bit rotations are faster than shifts on my machine although they use two shifts:

julia> x = rand(UInt256); k = 50
julia> @btime bitrotate($x, $k); @btime $x << $k; @btime $x >>> $k;
  5.437 ns (0 allocations: 0 bytes)
  6.362 ns (0 allocations: 0 bytes)
  6.360 ns (0 allocations: 0 bytes)

julia> x = rand(UInt512); k = 50
julia> @btime bitrotate($x, $k); @btime $x << $k; @btime $x >>> $k;
  9.523 ns (0 allocations: 0 bytes)
  27.259 ns (0 allocations: 0 bytes)
  26.233 ns (0 allocations: 0 bytes)

julia> x = rand(UInt1024); k = 50
julia> @btime bitrotate($x, $k); @btime $x << $k; @btime $x >>> $k;
  30.658 ns (0 allocations: 0 bytes)
  126.578 ns (0 allocations: 0 bytes)
  129.565 ns (0 allocations: 0 bytes)

This is on master. For Julia 1.10.0-rc2 the timings fot bitrotate with UInt256 and UInt512 are twice the values above.

EDIT: bitrotate was added in Julia 1.5. Currently, BitIntegers.jl accepts all 1.x versions of Julia. This would have to be adjusted somehow. What about requiring Julia 1.5 for BitIntegers.jl?

EDIT 2: The poor timings for << and >>> seems to improve for k >= 64:

julia> x = rand(UInt1024); k = 64
julia> @btime bitrotate($x, $k); @btime $x << $k; @btime $x >>> $k;
  32.790 ns (0 allocations: 0 bytes)
  15.624 ns (0 allocations: 0 bytes)
  14.275 ns (0 allocations: 0 bytes)

This seems to be a separate issue.

[rfourquet]

Awesome! Thanks, and sorry for the delay.

[matthias314]

As I mentioned before, your current Project.toml accepts any Julia >= 1. Since bitrotate was introduced in Julia 1.5, importing that symbol will give an error for older Julia versions. What about bumping up your Julia requirement to 1.6 (LTS)?

[rfourquet]

Yes I considered doing so, but thougth it wasn't hard to keep compatibility, cf. https://github.com/rfourquet/BitIntegers.jl/pull/49/files where I conditionally import bitrotate from Base and import it in tests. Thanks again!