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: need an arbitrary bit shifter for byte slices #43552

Closed
pschou opened this issue Jan 6, 2021 · 23 comments
Closed

proposal: math/bits: need an arbitrary bit shifter for byte slices #43552

pschou opened this issue Jan 6, 2021 · 23 comments

Comments

@pschou
Copy link

pschou commented Jan 6, 2021

While working with hashing tools, I found there is a lack of good shifting tools to operate on arbitrary byte slices. These two functions, Lsh and Rsh, would allow for any slice to be shifted 0 to N number of bits without copying the whole array.

See pull request:

#43550

Relates to the proposal:
https://go-review.googlesource.com/c/go/+/281832

@mundaym This would make future Rsh and Lsh calls trivial. :)

@mvdan
Copy link
Member

mvdan commented Jan 6, 2021

Have you seen https://golang.org/doc/faq#x_in_std?

@pschou
Copy link
Author

pschou commented Jan 6, 2021

Thank you comment and pointer @mvdan. I really appreciate the logic behind Go, and am perfectly fine with these suggestions being rejected. I'd like to read the reasons why or why not, and if not for anything else but to see where people are coming from and the logic. I value the thought experiment greatly!

Rsh and Lsh are very common in crypto, and given they may not be a trivial thing to code by hand-- I'm all for making this something that anyone could use with ease. :)

All the best!

@randall77
Copy link
Contributor

randall77 commented Jan 6, 2021

If this is for crypto, is there a reason why you are using []byte instead of big.Int? That type already provides shift operations.

@ianlancetaylor ianlancetaylor changed the title bytes: proposal: need an arbitrary bit shifter for byte slices proposal: bytes: need an arbitrary bit shifter for byte slices Jan 6, 2021
@gopherbot gopherbot added this to the Proposal milestone Jan 6, 2021
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Jan 6, 2021
@pschou
Copy link
Author

pschou commented Jan 6, 2021

@randall77 good point. I was working the,
crypto/ecdsa: hashToBytes optimization,
and was surprised to find there was no in-place function call to shift bytes in a slice. The Big.Int Set() works well, but the TODO asked to not call Big.Int

Hope this helps explain the logic.

All the best!

@icholy
Copy link

icholy commented Jan 7, 2021

This could be reduced down to a single func Shift(data []byte, bits int) function which can accept positive and negative values.

@gopherbot
Copy link

gopherbot commented Jan 7, 2021

Change https://golang.org/cl/282052 mentions this issue: bytes: Left and right bit shifter for byte slices

@pschou
Copy link
Author

pschou commented Jan 7, 2021

@icholy Thank you for the comment. I really appreciate your input here and I fully understand and am sure I have exploited this type of logic before to simplify code.

The biggest question that plagues me here is this: which direction should be positive? I ask this as cartesian coordinates imply that the right is positive, however, when dealing with big-endian numbers the left is positive.

@icholy
Copy link

icholy commented Jan 7, 2021

I'd assume negative would be left and positive would be right.

@randall77
Copy link
Contributor

randall77 commented Jan 7, 2021

In math/bits, we chose left=positive. We should probably do the same here. https://golang.org/pkg/math/bits/#RotateLeft
(But this proposal seems unlikely to make the cut, see @mvdan 's comment.)

@icholy
Copy link

icholy commented Jan 7, 2021

This is something that I've needed to re-implement more than once when parsing annoying (not byte aligned) binary formats. It's tricky to get right, and I think it would be a great addition to the encoding/binary package.

edit: here's an example implementation:

// ShiftLeft performs a left bit shift operation on the provided bytes.
// If the bits count is negative, a right bit shift is performed.
func ShiftLeft(data []byte, bits int) {
	n := len(data)
	if bits < 0 {
		bits = -bits
		for i := n - 1; i > 0; i-- {
			data[i] = data[i]>>bits | data[i-1]<<(8-bits)
		}
		data[0] >>= bits
	} else {
		for i := 0; i < n-1; i++ {
			data[i] = data[i]<<bits | data[i+1]>>(8-bits)
		}
		data[n-1] <<= bits
	}
}

It's large/finicky enough that I don't want to rewrite it in each project, but it's not big enough to live in its own module either.

@pschou
Copy link
Author

pschou commented Jan 8, 2021

PR has been updated with both suggestions.

I completely understand, @icholy your frustrations of having to re-implement it each time. I thought, "maybe others would also value this," so I greatly appreciate your agreement here. I found this utility is missing when working on some crypto/encoding libraries.

Yes, and thank you for that valuable shout-out, @randall77. I agree that staying consistent is very important for lowering the learning curve for new and experienced developers.

@pschou
Copy link
Author

pschou commented Jan 8, 2021

This is something that I've needed to re-implement more than once when parsing annoying (not byte aligned) binary formats. It's tricky to get right, and I think it would be a great addition to the encoding/binary package.

edit: here's an example implementation:

// ShiftLeft performs a left bit shift operation on the provided bytes.
// If the bits count is negative, a right bit shift is performed.
func ShiftLeft(data []byte, bits int) {
	n := len(data)
	if bits < 0 {
		bits = -bits
		for i := n - 1; i > 0; i-- {
			data[i] = data[i]>>bits | data[i-1]<<(8-bits)
		}
		data[0] >>= bits
	} else {
		for i := 0; i < n-1; i++ {
			data[i] = data[i]<<bits | data[i+1]>>(8-bits)
		}
		data[n-1] <<= bits
	}
}

It's large/finicky enough that I don't want to rewrite it in each project, but it's not big enough to live in its own module either.

This implementation does exactly what you suggest, though it grabs the value from the array to a variable and encourages the compiler to hold it in a register, so as to avoid pulling from memory twice.

@rsc
Copy link
Contributor

rsc commented Jan 13, 2021

This function is inappropriate for package bytes, which is primarily about text, not math on uint8 values.
It is also almost certainly too special for the Go standard library.
But it looks like you have an implementation you are happy with.
I encourage publishing it as a package that others can use.

@pschou
Copy link
Author

pschou commented Jan 13, 2021

@rsc : Thank you for your valuable feedback, and yes it is something that I am proud of. On this subject, and before I take any more of your valuable time, would this be something to consider in any other go package (like for example the suggested encoding/binary)?

@pschou pschou changed the title proposal: bytes: need an arbitrary bit shifter for byte slices proposal: math/bits: need an arbitrary bit shifter for byte slices Jan 15, 2021
@icholy
Copy link

icholy commented Jan 16, 2021

Unfortunately, the combined function is too complex to be inlined (in 1.16) https://pkg.go.dev/github.com/icholy/bitshift

@pschou
Copy link
Author

pschou commented Jan 16, 2021

@icholy please excuse my ignorance, I don't follow what you mean by too complex to be in-lined fully. What I think you are saying is that there are many lines of code. The link to your repo is very much the same thing, but here I was hoping to add the ability to handle shifts greater than 8, even up to 8*len(src). What do you think, crazy?

@davecheney
Copy link
Contributor

davecheney commented Jan 16, 2021

Each function has a complexity budget of 80 units, use go build -gcflags=-m=2 to see what the compiler things of each function

@icholy
Copy link

icholy commented Jan 17, 2021

@pschou Ive never needed to shift more than 8 bits. I wanted to add a panic if bits was greater than 8, but that also prevents inlining.

@mohmmedlbr mohmmedlbr mentioned this issue Jan 17, 2021
@pschou
Copy link
Author

pschou commented Jan 17, 2021

@davecheney Thank you for the heads up on this and even more the ability the budget check! I very much appreciate and respect this limit.

@icholy Your implementation is really nice! I very much appreciate it and I wonder if one could squeeze in an & operator, at the top to limit / mod the bits down to 0-7 along with allow alternate src and dst, aka *in and *out...

@rsc
Copy link
Contributor

rsc commented Jan 20, 2021

This function seems inappropriate for the standard library generally.
It is not (apparently) something people need frequently, nor is it
something where the compiler can cut it down to a single instruction
(like most things in math/bits).

@pschou
Copy link
Author

pschou commented Jan 20, 2021

This function seems inappropriate for the standard library generally.
It is not (apparently) something people need frequently, nor is it
something where the compiler can cut it down to a single instruction
(like most things in math/bits).

Thank you for the reply. This makes perfect sense and I appreciate your insight and oversight in this matter. Feel free to close this request as desired.

All the best!

@rsc rsc closed this as completed May 19, 2021
@rsc rsc moved this from Incoming to Declined in Proposals (old) May 19, 2021
@rsc
Copy link
Contributor

rsc commented May 19, 2021

No change in consensus, so declined.
— rsc for the proposal review group

@golang golang locked and limited conversation to collaborators May 19, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
No open projects
Development

No branches or pull requests

7 participants