code review 5786045: go.crypto/curve25519: add package.

go.crypto/curve25519: add package.

This consists of ~2000 lines of amd64 assembly and a, much slower,
generic Go version in curve25519.go. The assembly has been ported from
djb's public domain sources and the only semantic alterations are to
deal with Go's split stacks.

[agl1, 2012-03-07 23:00:31]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://agl%40golang.org@code.google.com/p/go.crypto/

[rsc, 2012-03-08 14:49:32]

LGTM

http://codereview.appspot.com/5786045/diff/3019/curve25519/const_amd64.s
File curve25519/const_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/const_amd64.s#newc...
curve25519/const_amd64.s:20: DATA ·_4P0(SB)/8, $0x1FFFFFFFFFFFB4
Everything from here down appears to be unused?

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go
File curve25519/curve25519.go (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:45: func (c *context) add(xn, zn, xm, zm *big.Int) (x,
z *big.Int) {
You might want to let the caller pass in x and z so as to control when they get
allocated/reused.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:46: // x₃ = 4(x·x′ - z·z′)² · z1
I don't see the · z1 in the code below.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:54: // z₃ = 4(x·z′ - z·x′)² · x1
Same about · x1.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:68: func (c *context) double(x, z *big.Int) (outx, outz
*big.Int) {
Same about controlling allocation.

http://codereview.appspot.com/5786045/diff/3019/curve25519/freeze_amd64.s
File curve25519/freeze_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/freeze_amd64.s#new...
curve25519/freeze_amd64.s:9: TEXT ·freeze(SB),7,$96
$96-8 to futureproof (see comment in next file for explanation).

http://codereview.appspot.com/5786045/diff/3019/curve25519/freeze_amd64.s#new...
curve25519/freeze_amd64.s:34: REDUCELOOP:
please unindent this label

http://codereview.appspot.com/5786045/diff/3019/curve25519/ladderstep_amd64.s
File curve25519/ladderstep_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/ladderstep_amd64.s...
curve25519/ladderstep_amd64.s:9: TEXT ·ladderstep(SB),0,$384
Because you're not using (can't use) 7 here, the linker/runtime will 
do a stack split check on entry to this function, so you need
to tell the assembler how many bytes of arguments need to
be copied into the new stack frame if a split is necessary.
It looks like there are 8 bytes of arguments (one pointer)
so:

TEXT ·ladderstep(SB),0,$384-8

The - is a separator between two numbers, not a subtraction.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go
File curve25519/mont25519_amd64.go (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:45: // ScalarMult sets out to in*base where out
and base are the x coordinates of
"sets out to" sounds like it is starting on a journey or something.
Maybe s/out/dst/
s/in*base/the product in*base/

One way to avoid the duplicated docs (here and in the portable file)
is to create a file doc.go that contains

package curve25519

// ScalarMult ...
func ScalarMult(dst, in, base *[32]byte) {
    scalarMult(dst, in, base)
}
etc

and then have these files implement scalarMult.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:63: var basePoint = [32]byte{9, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Maybe move this to doc.go too.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:65: // ScalarBaseMult sets out to in*base where
out and base are the x coordinates of
And this.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:83: (*r)[0] = uint64((*x)[0])
Indexing into a pointer to an array does not require the explicit deference
(see setint above).

,s/(*r)/r/g
,s/(*x)/x/g

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:84: (*r)[0] += uint64((*x)[1]) << 8
FWIW I think this will compile a little nicer if you use a big | instead of a
sequence of +=.

r[0] = uint64((*x)[0]) |
    uint64((*x)[1]) << 8 |
    ...

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:131: (*out)[0] = byte(t[0])
,s/(*out)/out/g

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:177: /* 2 */ square(&z2, x)
Is it possible to swap the comments to the end of the line?
Hardly a big deal but I think it would be more legible, and
gofmt will line them up for you.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mul_amd64.s
File curve25519/mul_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/mul_amd64.s#newcode9
curve25519/mul_amd64.s:9: TEXT ·mul(SB),0,$128
Same comment about the split: $128-24

http://codereview.appspot.com/5786045/diff/3019/curve25519/square_amd64.s
File curve25519/square_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/square_amd64.s#new...
curve25519/square_amd64.s:9: TEXT ·square(SB),7,$96
It's not required here until the 7 goes away,
but just in case that should happen, $96-16.

[agl1, 2012-03-12 14:59:21]

*** Submitted as
http://code.google.com/p/go/source/detail?r=83d3a9be6c0e&repo=crypto ***

go.crypto/curve25519: add package.

This consists of ~2000 lines of amd64 assembly and a, much slower,
generic Go version in curve25519.go. The assembly has been ported from
djb's public domain sources and the only semantic alterations are to
deal with Go's split stacks.

R=rsc
CC=golang-dev
http://codereview.appspot.com/5786045

http://codereview.appspot.com/5786045/diff/3019/curve25519/const_amd64.s
File curve25519/const_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/const_amd64.s#newc...
curve25519/const_amd64.s:20: DATA ·_4P0(SB)/8, $0x1FFFFFFFFFFFB4
On 2012/03/08 14:49:32, rsc wrote:
> Everything from here down appears to be unused?

Good point, thanks. I didn't end up using these.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go
File curve25519/curve25519.go (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:45: func (c *context) add(xn, zn, xm, zm *big.Int) (x,
z *big.Int) {
On 2012/03/08 14:49:32, rsc wrote:
> You might want to let the caller pass in x and z so as to control when they
get
> allocated/reused.

Yea, I was being lazy here since this is the slow path. Have altered to pass in
outx and outz and saved a number of allocations in the main ladder.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:46: // x₃ = 4(x·x′ - z·z′)² · z1
On 2012/03/08 14:49:32, rsc wrote:
> I don't see the · z1 in the code below.

z1 is known to be 1 here. Have amended comment.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:54: // z₃ = 4(x·z′ - z·x′)² · x1
On 2012/03/08 14:49:32, rsc wrote:
> Same about · x1.

x1 is known to be 1 here. Have amended comment.

http://codereview.appspot.com/5786045/diff/3019/curve25519/curve25519.go#newc...
curve25519/curve25519.go:68: func (c *context) double(x, z *big.Int) (outx, outz
*big.Int) {
On 2012/03/08 14:49:32, rsc wrote:
> Same about controlling allocation.

ditto

http://codereview.appspot.com/5786045/diff/3019/curve25519/freeze_amd64.s
File curve25519/freeze_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/freeze_amd64.s#new...
curve25519/freeze_amd64.s:9: TEXT ·freeze(SB),7,$96
On 2012/03/08 14:49:32, rsc wrote:
> $96-8 to futureproof (see comment in next file for explanation).

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/ladderstep_amd64.s
File curve25519/ladderstep_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/ladderstep_amd64.s...
curve25519/ladderstep_amd64.s:9: TEXT ·ladderstep(SB),0,$384
On 2012/03/08 14:49:32, rsc wrote:
> TEXT ·ladderstep(SB),0,$384-8

Thanks!

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go
File curve25519/mont25519_amd64.go (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:45: // ScalarMult sets out to in*base where out
and base are the x coordinates of
On 2012/03/08 14:49:32, rsc wrote:
> "sets out to" sounds like it is starting on a journey or something.
> Maybe s/out/dst/
> s/in*base/the product in*base/
> 
> One way to avoid the duplicated docs (here and in the portable file)
> is to create a file doc.go that contains
> 
> package curve25519
> 
> // ScalarMult ...
> func ScalarMult(dst, in, base *[32]byte) {
>     scalarMult(dst, in, base)
> }
> etc
> 
> and then have these files implement scalarMult.

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:63: var basePoint = [32]byte{9, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
On 2012/03/08 14:49:32, rsc wrote:
> Maybe move this to doc.go too.

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:65: // ScalarBaseMult sets out to in*base where
out and base are the x coordinates of
On 2012/03/08 14:49:32, rsc wrote:
> And this.

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:83: (*r)[0] = uint64((*x)[0])
On 2012/03/08 14:49:32, rsc wrote:
> Indexing into a pointer to an array does not require the explicit deference
> (see setint above).
> 
> ,s/(*r)/r/g
> ,s/(*x)/x/g

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:84: (*r)[0] += uint64((*x)[1]) << 8
On 2012/03/08 14:49:32, rsc wrote:
> FWIW I think this will compile a little nicer if you use a big | instead of a
> sequence of +=.
> 
> r[0] = uint64((*x)[0]) |
>     uint64((*x)[1]) << 8 |
>     ...

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/mont25519_amd64.go...
curve25519/mont25519_amd64.go:177: /* 2 */ square(&z2, x)
On 2012/03/08 14:49:32, rsc wrote:
> Is it possible to swap the comments to the end of the line?

Done (one regexp did the trick)

http://codereview.appspot.com/5786045/diff/3019/curve25519/mul_amd64.s
File curve25519/mul_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/mul_amd64.s#newcode9
curve25519/mul_amd64.s:9: TEXT ·mul(SB),0,$128
On 2012/03/08 14:49:32, rsc wrote:
> Same comment about the split: $128-24

Done.

http://codereview.appspot.com/5786045/diff/3019/curve25519/square_amd64.s
File curve25519/square_amd64.s (right):

http://codereview.appspot.com/5786045/diff/3019/curve25519/square_amd64.s#new...
curve25519/square_amd64.s:9: TEXT ·square(SB),7,$96
On 2012/03/08 14:49:32, rsc wrote:
> It's not required here until the 7 goes away,
> but just in case that should happen, $96-16.

Done.