Skip to content

/ go

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

Jump to bottom

crypto, x/crypto: use math.bits rotate functions instead of ad-hoc implementations #31456

Open
vitaminniy opened this issue Apr 13, 2019 · 11 comments
Open

crypto, x/crypto: use math.bits rotate functions instead of ad-hoc implementations #31456

vitaminniy opened this issue Apr 13, 2019 · 11 comments
Labels
NeedsInvestigation
Milestone
Unplanned

Comments

@vitaminniy
Copy link
Contributor

@vitaminniy vitaminniy commented Apr 13, 2019

No description provided.

@gopherbot

This comment has been minimized.

Sign in to view
Copy link

@gopherbot gopherbot commented Apr 13, 2019

Change https://golang.org/cl/171729 mentions this issue: crypto/sha1: use math/bits.RotateLeft32 instead of ad-hoc implementation.
gopherbot pushed a commit that referenced this issue Apr 13, 2019
@vitaminniy @TocarIP
crypto/sha1: use math/bits.RotateLeft32 instead of ad-hoc implementat…
7cd39de 
…ion.

This makes code more idiomatic and shows small performance gains of generic benchmarks.

Updates: #31456

name            old time/op    new time/op    delta
Hash8Bytes-8       275ns ± 4%     270ns ± 0%    ~     (p=0.213 n=9+8)
Hash320Bytes-8    1.46µs ± 5%    1.39µs ± 1%  -4.54%  (p=0.000 n=10+10)
Hash1K-8          3.99µs ± 5%    3.86µs ± 1%  -3.38%  (p=0.023 n=10+10)
Hash8K-8          28.9µs ± 0%    28.9µs ± 1%    ~     (p=0.315 n=10+10)

name            old speed      new speed      delta
Hash8Bytes-8    28.8MB/s ± 9%  29.6MB/s ± 0%    ~     (p=0.151 n=10+8)
Hash320Bytes-8   220MB/s ± 5%   230MB/s ± 1%  +4.65%  (p=0.000 n=10+10)
Hash1K-8         257MB/s ± 5%   265MB/s ± 1%  +3.38%  (p=0.023 n=10+10)
Hash8K-8         283MB/s ± 0%   284MB/s ± 1%    ~     (p=0.315 n=10+10)

Change-Id: Iee63aa042614e3bbeda9aaf5236180d4153f03c4
Reviewed-on: https://go-review.googlesource.com/c/go/+/171729
Reviewed-by: Ilya Tokar <tocarip@gmail.com>
Run-TryBot: Ilya Tokar <tocarip@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot

This comment has been minimized.

Sign in to view
Copy link

@gopherbot gopherbot commented Apr 13, 2019

Change https://golang.org/cl/171731 mentions this issue: crypto/sha256: Use bits.RotateLeft32 instead of ad-hoc implementation
@gopherbot

This comment has been minimized.

Sign in to view
Copy link

@gopherbot gopherbot commented Apr 13, 2019

Change https://golang.org/cl/171736 mentions this issue: crypto/sha512: use math/bits.RotateLeft64 instead of ad-hoc implementation.
@andybons andybons changed the title Use math.bits rotate functions instead of ad-hoc implementation in crypto packages crypto: use math.bits rotate functions instead of ad-hoc implementations Apr 13, 2019
@andybons

This comment has been minimized.

Sign in to view
Copy link
Member

@andybons andybons commented Apr 13, 2019

@FiloSottile
@andybons andybons added this to the Unplanned milestone Apr 13, 2019
@dgryski dgryski mentioned this issue Apr 15, 2019
Closed
@dgryski

This comment has been minimized.

Sign in to view
Copy link
Contributor

@dgryski dgryski commented Apr 15, 2019 •
edited

The following query finds a number of additional cases in /x/crypto when run with GOARCH=arm64 to scan the non-amd64-assembly versions.

gogrep -x       '$a >> $k | $a << (64 - $k)' ./...
gogrep -x       '($a >> $k) | ($a << (64 - $k))' ./...
gogrep -x       '$a << $k | $a >> (64 - $k)' ./...
gogrep -x       '($a << $k) | ($a >> (64 - $k))' ./...
gogrep -x       '$a >> (64 - $k) | $a << $k' ./...
gogrep -x       '($a >> (64 - $k)) | ($a<< $k)' ./...
gogrep -x       '$a << (64 - $k) | $a >> $k' ./...
gogrep -x       '($a << (64 - $k)) | ($a >> $k)' ./...
gogrep -x       '$a >> $k | $a << (32 - $k)' ./...
gogrep -x       '($a >> $k) | ($a << (32 - $k))' ./...
gogrep -x       '$a << $k | $a >> (32 - $k)' ./...
gogrep -x       '($a << $k) | ($a >> (32 - $k))' ./...
gogrep -x       '$a >> (32 - $k) | $a << $k' ./...
gogrep -x       '($a >> (32 - $k)) | ($a<< $k)' ./...
gogrep -x       '$a << (32 - $k) | $a >> $k' ./...
gogrep -x       '($a << (32 - $k)) | ($a >> $k)' ./...

Edit:
And a 16-bit one in my rc2 code :D

golang.org/x/crypto/pkcs12/internal/rc2/rc2.go:84:9: (x >> (16 - b)) | (x << b)
@FiloSottile FiloSottile mentioned this issue Apr 15, 2019
Open
@FiloSottile FiloSottile changed the title crypto: use math.bits rotate functions instead of ad-hoc implementations crypto, x/crypto: use math.bits rotate functions instead of ad-hoc implementations Apr 15, 2019
gopherbot pushed a commit that referenced this issue Apr 15, 2019
@vitaminniy @FiloSottile
crypto/sha512: use math/bits.RotateLeft64 instead of ad-hoc implement…
827044e 
…ation

This makes code more readable and idiomatic and slightly increase performance.

Updates #31456

Benchstat:
name          old time/op    new time/op    delta
Hash8Bytes-8     281ns ± 4%     280ns ± 3%    ~     (p=0.640 n=10+10)
Hash1K-8        2.01µs ± 6%    2.02µs ± 3%    ~     (p=0.481 n=10+10)
Hash8K-8        14.2µs ± 6%    13.5µs ± 1%  -4.90%  (p=0.001 n=10+10)

name          old speed      new speed      delta
Hash8Bytes-8  28.5MB/s ± 4%  28.5MB/s ± 3%    ~     (p=0.516 n=10+10)
Hash1K-8       510MB/s ± 6%   507MB/s ± 4%    ~     (p=0.481 n=10+10)
Hash8K-8       576MB/s ± 6%   605MB/s ± 1%  +5.02%  (p=0.001 n=10+10)

Tested on macbook pro 2018 Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz

Change-Id: I1f5b78096dd49d14ffcb9129142c4a4e05b81ff9
Reviewed-on: https://go-review.googlesource.com/c/go/+/171736
Reviewed-by: Filippo Valsorda <filippo@golang.org>
@vitaminniy

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

@vitaminniy vitaminniy commented Apr 15, 2019

Probably we can close this one as soon as the #171731 would be merged.

➜  src git:(master) find crypto -type f -name "*.go" -exec egrep ".+>>(\d)+ \| .+<<\((\d)+-(\d)+\)" {} \+
crypto/sha256/sha256block.go: t1 := (v1>>17 | v1<<(32-17)) ^ (v1>>19 | v1<<(32-19)) ^ (v1 >> 10)
crypto/sha256/sha256block.go: t2 := (v2>>7 | v2<<(32-7)) ^ (v2>>18 | v2<<(32-18)) ^ (v2 >> 3)
crypto/sha256/sha256block.go: t1 := h + ((e>>6 | e<<(32-6)) ^ (e>>11 | e<<(32-11)) ^ (e>>25 | e<<(32-25))) + ((e & f) ^ (^e & g)) + _K[i] + w[i]
crypto/sha256/sha256block.go: t2 := ((a>>2 | a<<(32-2)) ^ (a>>13 | a<<(32-13)) ^ (a>>22 | a<<(32-22))) + ((a & b) ^ (a & c) ^ (b & c))

@FiloSottile
@vitaminniy

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

@vitaminniy vitaminniy commented Apr 15, 2019

Probably we can close this one as soon as the #171731 would be merged.

➜  src git:(master) find crypto -type f -name "*.go" -exec egrep ".+>>(\d)+ \| .+<<\((\d)+-(\d)+\)" {} \+
crypto/sha256/sha256block.go: t1 := (v1>>17 | v1<<(32-17)) ^ (v1>>19 | v1<<(32-19)) ^ (v1 >> 10)
crypto/sha256/sha256block.go: t2 := (v2>>7 | v2<<(32-7)) ^ (v2>>18 | v2<<(32-18)) ^ (v2 >> 3)
crypto/sha256/sha256block.go: t1 := h + ((e>>6 | e<<(32-6)) ^ (e>>11 | e<<(32-11)) ^ (e>>25 | e<<(32-25))) + ((e & f) ^ (^e & g)) + _K[i] + w[i]
crypto/sha256/sha256block.go: t2 := ((a>>2 | a<<(32-2)) ^ (a>>13 | a<<(32-13)) ^ (a>>22 | a<<(32-22))) + ((a & b) ^ (a & c) ^ (b & c))

@FiloSottile

There is code in x/crypto that contains bit rotation operations. Should it be changed in case of this particular issue?
@FiloSottile

This comment has been minimized.

Sign in to view
Copy link
Member

@FiloSottile FiloSottile commented Apr 16, 2019

I would be happy to take two global CLs, one for crypto/... and one for x/crypto/..., fixing all cases identified by gogrep according to #31456 (comment).
gopherbot pushed a commit that referenced this issue Apr 16, 2019
@iosadchiy @TocarIP
crypto/sha256: Use bits.RotateLeft32 instead of ad-hoc implementation
36b0593 
Improves readability of the generic implementation.

Updates #31456.

Benchmarks (i7-4980HQ CPU)

name          old time/op    new time/op    delta
Hash8Bytes-8     339ns ± 3%     337ns ± 2%   ~     (p=0.595 n=5+5)
Hash1K-8        5.12µs ± 6%    4.97µs ± 6%   ~     (p=0.310 n=5+5)
Hash8K-8        37.6µs ± 5%    38.1µs ± 6%   ~     (p=0.841 n=5+5)

name          old speed      new speed      delta
Hash8Bytes-8  23.6MB/s ± 3%  23.8MB/s ± 3%   ~     (p=0.690 n=5+5)
Hash1K-8       200MB/s ± 6%   206MB/s ± 5%   ~     (p=0.310 n=5+5)
Hash8K-8       218MB/s ± 5%   215MB/s ± 6%   ~     (p=0.841 n=5+5)

Change-Id: Ic488841699138efde76e900bce1dd38fdbc88ec6
Reviewed-on: https://go-review.googlesource.com/c/go/+/171731
Reviewed-by: Ilya Tokar <tocarip@gmail.com>
Run-TryBot: Ilya Tokar <tocarip@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot

This comment has been minimized.

Sign in to view
Copy link

@gopherbot gopherbot commented Apr 22, 2019

Change https://golang.org/cl/173277 mentions this issue: blake2b: use math.bits rotate functions instead of ad-hoc implementations
gopherbot pushed a commit to golang/crypto that referenced this issue Apr 22, 2019
@vitaminniy @bradfitz
blake2b: use math.bits rotate functions instead of ad-hoc implementat…
af44ce2 
…ions

This makes code more readable and idiomatic and slightly improves performance.

Updates golang/go#31456

Benchstat:
name        old time/op    new time/op    delta
Write128-4     271ns ± 4%     250ns ± 2%  -7.78%  (p=0.000 n=10+9)
Write1K-4     2.01µs ± 6%    1.97µs ± 5%    ~     (p=0.393 n=10+10)
Sum128-4       271ns ± 6%     276ns ± 5%    ~     (p=0.342 n=10+10)
Sum1K-4       1.98µs ±11%    2.03µs ± 4%    ~     (p=0.093 n=10+10)

name        old speed      new speed      delta
Write128-4   471MB/s ± 4%   511MB/s ± 2%  +8.34%  (p=0.000 n=10+9)
Write1K-4    511MB/s ± 6%   521MB/s ± 5%    ~     (p=0.393 n=10+10)
Sum128-4     472MB/s ± 6%   463MB/s ± 6%    ~     (p=0.315 n=10+10)
Sum1K-4      520MB/s ±10%   504MB/s ± 4%    ~     (p=0.105 n=10+10)

Change-Id: I7e18379c02a78c77afcf8195d42307f71bc49fe0
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/173277
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot

This comment has been minimized.

Sign in to view
Copy link

@gopherbot gopherbot commented Apr 22, 2019

Change https://golang.org/cl/173278 mentions this issue: blake2s: use math.bits rotate functions instead of ad-hoc implementation
gopherbot pushed a commit to golang/crypto that referenced this issue Apr 22, 2019
@vitaminniy @bradfitz
blake2s: use math.bits rotate functions instead of ad-hoc implementation
d864b10 
This makes code more readable and idiomatic.

Updates golang/go#31456

Benchstat:
name       old time/op   new time/op   delta
Write64-8    211ns ± 6%    205ns ± 2%    ~     (p=0.243 n=10+9)
Write1K-8   3.26µs ± 3%   3.12µs ± 2%  -4.44%  (p=0.000 n=9+9)
Sum64-8      227ns ± 5%    217ns ± 6%  -4.58%  (p=0.009 n=10+10)
Sum1K-8     3.28µs ± 2%   3.31µs ± 4%    ~     (p=0.412 n=10+9)

name       old speed     new speed     delta
Write64-8  303MB/s ± 6%  312MB/s ± 1%    ~     (p=0.203 n=10+8)
Write1K-8  314MB/s ± 3%  329MB/s ± 2%  +4.64%  (p=0.000 n=9+9)
Sum64-8    281MB/s ± 5%  295MB/s ± 5%  +4.93%  (p=0.009 n=10+10)
Sum1K-8    313MB/s ± 2%  310MB/s ± 4%    ~     (p=0.447 n=10+9)

Change-Id: Iee0e88f4405d4da1feacddaf24835e86d8ddeff7
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/173278
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot

This comment has been minimized.

Sign in to view
Copy link

@gopherbot gopherbot commented Apr 26, 2019

Change https://golang.org/cl/174137 mentions this issue: scrypt: use math.bits rotate functions instead of ad-hoc implementation
gopherbot pushed a commit to golang/crypto that referenced this issue Apr 26, 2019
@vitaminniy @bradfitz
scrypt: use math.bits rotate functions instead of ad-hoc implementation
a29dc8f 
This makes code more readable and idiomatic. No change in benchmarks.

Updates golang/go#31456

Change-Id: I010bbff33580350019ce2b0ff13847261905d32f
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/174137
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsInvestigation
Projects
None yet
Milestone
  Unplanned
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
@vitaminniy @gopherbot @andybons @dgryski @FiloSottile
You can’t perform that action at this time.