code review 217116: Implementation of the symmetric block cipher Blowfish.

Implementation of the symmetric block cipher Blowfish.

[rsn, 2010-02-25 08:29:24]

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

I'd like you to review this change.

[rsc, 2010-02-25 09:01:01]

thanks for writing this.
the code looks great.  i've pointed out a few
small things below that either make it more 
go-like or a little faster.

there are a bunch of comment nits, to make them
fit more into the comment style of the rest of the
packages.  in general it's never a bad idea to
copy comments from code that does the same
thing - crypto/aes is a good template.

http://codereview.appspot.com/217116/diff/2001/3003
File src/pkg/crypto/blowfish/block.go (right):

http://codereview.appspot.com/217116/diff/2001/3003#newcode14
src/pkg/crypto/blowfish/block.go:14: var j int = 0
j := 0

http://codereview.appspot.com/217116/diff/2001/3003#newcode15
src/pkg/crypto/blowfish/block.go:15: var d uint32
delete (can be declared inside loop)

http://codereview.appspot.com/217116/diff/2001/3003#newcode17
src/pkg/crypto/blowfish/block.go:17: d = 0x00000000
var d uint32

http://codereview.appspot.com/217116/diff/2001/3003#newcode19
src/pkg/crypto/blowfish/block.go:19: d = d<<8 | (uint32(key[j]) & 0x000000FF)
can drop parens - & binds tighter than |, and
gofmt will adjust the spacing to emphasize that
once the parens are gone.

http://codereview.appspot.com/217116/diff/2001/3003#newcode28
src/pkg/crypto/blowfish/block.go:28: var l, r uint32 = 0x00000000, 0x00000000
no need to initialize these.
(the values are never used.)

var l, r uint32

http://codereview.appspot.com/217116/diff/2001/3003#newcode73
src/pkg/crypto/blowfish/block.go:73: xr ^= ((c.s0[xl>>24] + c.s1[xl>>16&0xFF]) ^
c.s2[xl>>8&0xFF]) + c.s3[xl&0xFF] ^ c.p[1]
If you say [byte(x1>>24] and [byte(x1>>16)] and [byte(x1>>8)] etc
the compiler will do a better job optimizing away the 
bounds checks.  (try benchmarking encryption before
and after that change.)

http://codereview.appspot.com/217116/diff/2001/3003#newcode103
src/pkg/crypto/blowfish/block.go:103: xr ^= ((c.s0[xl>>24] + c.s1[xl>>16&0xFF])
^ c.s2[xl>>8&0xFF]) + c.s3[xl&0xFF] ^ c.p[16]
same comment about byte() conversion in place of &0xff.
(and also on the >>24 variant)

http://codereview.appspot.com/217116/diff/2001/3004
File src/pkg/crypto/blowfish/blowfish_test.go (right):

http://codereview.appspot.com/217116/diff/2001/3004#newcode18
src/pkg/crypto/blowfish/blowfish_test.go:18: var encryptTests = []CryptTest{
add a comment saying where these tests came from.

http://codereview.appspot.com/217116/diff/2001/3004#newcode194
src/pkg/crypto/blowfish/blowfish_test.go:194: func BenchmarkEncoding(b
*testing.B) {
you can probably delete the benchmarks now.
it's fine if you want to add a benchmark of 
encrypting 1 KB or something like that.

http://codereview.appspot.com/217116/diff/2001/3005
File src/pkg/crypto/blowfish/cipher.go (right):

http://codereview.appspot.com/217116/diff/2001/3005#newcode5
src/pkg/crypto/blowfish/cipher.go:5: // This package implements Blowfish: a
symmetric 64-bit block cipher designed
the package comment should say what users need to know:
the rest can go after the package statement.

// This package implements Bruce Schneier's Blowfish encryption algorithm.
package blowfish

// The code is a port of Bruce Schneier's C implementation.
// See http://www.schneier.com/blowfish.html.

http://codereview.appspot.com/217116/diff/2001/3005#newcode16
src/pkg/crypto/blowfish/cipher.go:16: // The Blowfish block size (64 bits) in
bytes.
can drop (64 bits) which is redundant given the definition below

http://codereview.appspot.com/217116/diff/2001/3005#newcode19
src/pkg/crypto/blowfish/cipher.go:19: // Cipher is an instance of the internal
Blowfish key constructed from user
please copy the comments from the AES implementation
(crypto/aes), both here and for all the functions below.
they are more concise.

http://codereview.appspot.com/217116/diff/2001/3005#newcode22
src/pkg/crypto/blowfish/cipher.go:22: p, s0, s1, s2, s3 []uint32
Since these are fixed size, the slice is unnecessary.
You can use a single array and do the allocation in
one chunk.

More importantly, having the fixed array will let the
compiler eliminate bounds checks for constant indexes
smaller than the array size:

type Cipher struct {
    p [18]uint32
    s0, s1, s2, s3 [256]uint32
}

http://codereview.appspot.com/217116/diff/2001/3005#newcode28
src/pkg/crypto/blowfish/cipher.go:28: return "crypto/blowfish: Invalid key size
" + strconv.Itoa(int(k))
lowercase letter after : please.  (invalid not Invalid).
(see crypto/aes)

http://codereview.appspot.com/217116/diff/2001/3005#newcode31
src/pkg/crypto/blowfish/cipher.go:31: // NewCipher creates and returns a new
Blowfish Cipher.  The 'key' argument
you're in package blowfish already.
no need for quotes.  break line.
(see crypto/aes)

// NewCipher creates and returns a Cipher.
// The key argument should be the Blowfish key, 4 to 56 bytes.

http://codereview.appspot.com/217116/diff/2001/3005#newcode38
src/pkg/crypto/blowfish/cipher.go:38: // allocate space for the cipher's context
with the changed Cipher above this shortens to

var c Cipher
expandKey(key, &c)
return &c, nil

http://codereview.appspot.com/217116/diff/2001/3005#newcode50
src/pkg/crypto/blowfish/cipher.go:50: // satisfy the Key interface in the
package "crypto/modes".
re-copy aes comment now that it says crypto/block.  ;-)

// BlockSize returns the Blowfish block size, 8 bytes.
// It is necessary to satisfy the Cipher interface in the
// package "crypto/block".

http://codereview.appspot.com/217116/diff/2001/3005#newcode53
src/pkg/crypto/blowfish/cipher.go:53: // Encrypt enciphers the first 8 bytes (64
bits) in 'src' using the Cipher's
copy aes comment

http://codereview.appspot.com/217116/diff/2001/3005#newcode61
src/pkg/crypto/blowfish/cipher.go:61: l, r = 0, 0
delete
(compiler will just optimize away)

http://codereview.appspot.com/217116/diff/2001/3005#newcode64
src/pkg/crypto/blowfish/cipher.go:64: // Decrypt deciphers the first 8 bytes (64
bits) in 'src' using the Cipher's
copy aes comment

http://codereview.appspot.com/217116/diff/2001/3005#newcode72
src/pkg/crypto/blowfish/cipher.go:72: l, r = 0, 0
delete

http://codereview.appspot.com/217116/diff/2001/3005#newcode75
src/pkg/crypto/blowfish/cipher.go:75: // Reset zeroes the cipher's internal key.
copy aes comment

http://codereview.appspot.com/217116/diff/2001/3005#newcode77
src/pkg/crypto/blowfish/cipher.go:77: var i int = 0
i suggest writing a helper

func zero(x []uint32) {
    for i := range x {
        x[i] = 0
    }
}

and then call it here on each slice.
the compiler is much more likely to 
get the bounds checks eliminated
in a single loop, and it's clearer what's going on.
the loop constants here are magic otherwise.

when you get rid of the slices as mentioned above,
you'll have to say zero(&c.p) or zero(c.p[0:]).

http://codereview.appspot.com/217116/diff/2001/3006
File src/pkg/crypto/blowfish/const.go (right):

http://codereview.appspot.com/217116/diff/2001/3006#newcode10
src/pkg/crypto/blowfish/const.go:10: var _S0 = []uint32{
please call this s0, s1, s2, ...
there are some files that use _UPPER
instead of lower, but those are dregs
and we need to weed them out.
(it took us a little while to come to grips
with the case-based export rules.)

http://codereview.appspot.com/217116/diff/2001/3006#newcode53
src/pkg/crypto/blowfish/const.go:53: 0x53b02d5d, 0xa99f8fa1, 0x08ba4799,
0x6e85076a}
please move the } down to the next line.
you'll have to end this line with a , to do that.

same applies to rest of file.

[rsn, 2010-02-25 12:23:07]

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

Please take another look.

[rsn, 2010-02-25 12:23:34]

hello Russ,

thanks for your comments and suggestions!  this is really what i was hoping for
especially the performance and memory allocation issues.


cheers;
rsn

http://codereview.appspot.com/217116/diff/2001/3003
File src/pkg/crypto/blowfish/block.go (right):

http://codereview.appspot.com/217116/diff/2001/3003#newcode14
src/pkg/crypto/blowfish/block.go:14: var j int = 0
On 2010/02/25 09:01:02, rsc wrote:
> j := 0
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3003#newcode15
src/pkg/crypto/blowfish/block.go:15: var d uint32
On 2010/02/25 09:01:02, rsc wrote:
> delete (can be declared inside loop)
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3003#newcode17
src/pkg/crypto/blowfish/block.go:17: d = 0x00000000
On 2010/02/25 09:01:02, rsc wrote:
> var d uint32
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3003#newcode19
src/pkg/crypto/blowfish/block.go:19: d = d<<8 | (uint32(key[j]) & 0x000000FF)
On 2010/02/25 09:01:02, rsc wrote:
> can drop parens - & binds tighter than |, and
> gofmt will adjust the spacing to emphasize that
> once the parens are gone.
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3003#newcode28
src/pkg/crypto/blowfish/block.go:28: var l, r uint32 = 0x00000000, 0x00000000
On 2010/02/25 09:01:02, rsc wrote:
> no need to initialize these.
> (the values are never used.)
> 
> var l, r uint32
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3003#newcode73
src/pkg/crypto/blowfish/block.go:73: xr ^= ((c.s0[xl>>24] + c.s1[xl>>16&0xFF]) ^
c.s2[xl>>8&0xFF]) + c.s3[xl&0xFF] ^ c.p[1]
On 2010/02/25 09:01:02, rsc wrote:
> If you say [byte(x1>>24] and [byte(x1>>16)] and [byte(x1>>8)] etc
> the compiler will do a better job optimizing away the 
> bounds checks.  (try benchmarking encryption before
> and after that change.)
> 

i've added 2 new benchmark methods to test this.  here is what i get on my
"Intel(R) Core(TM)2 Duo CPU U9400 @ 1.40GHz":

blowfish.BenchmarkUint32Index	 5000000	       372 ns/op	 172.04 MB/s
blowfish.BenchmarkByteIndex	 5000000	       378 ns/op	 169.31 MB/s

i've added the code which you suggested but commented it out in case i
misunderstood what you meant --using, for example, c.s1[byte(xl>>16)] instead of
c.s1[byte(xr>>16&0xFF)] causes an exception similar to this:

throw: index out of range

panic PC=0x11c870
throw+0x46 /opt/go/src/pkg/runtime/runtime.c:74
	throw(0x8088f10, 0x0)
runtime.throwindex+0x24 /opt/go/src/pkg/runtime/runtime.c:47
	runtime.throwindex()
crypto/blowfish.encryptBlock+0x8e /opt/go/src/pkg/crypto/blowfish/block.go:104
	crypto/blowfish.encryptBlock(0x0, 0x0, 0x116280, 0x80ad558, 0x100, ...)
crypto/blowfish.expandKey+0x1f2 /opt/go/src/pkg/crypto/blowfish/block.go:29
	crypto/blowfish.expandKey(0x1104e8, 0x8, 0x8, 0x116280, 0x100, ...)
crypto/blowfish.NewCipher+0x196 /opt/go/src/pkg/crypto/blowfish/cipher.go:45
	crypto/blowfish.NewCipher(0x1104e8, 0x8, 0x8, 0x0, 0x0, ...)
crypto/blowfish.TestCipherEncrypt+0xbf
/opt/go/src/pkg/crypto/blowfish/blowfish_test.go:160
	crypto/blowfish.TestCipherEncrypt(0x114130, 0x0)
testing.tRunner+0x2c /opt/go/src/pkg/testing/testing.go:132
	testing.tRunner(0x114130, 0x80a73bc, 0x0)
goexit /opt/go/src/pkg/runtime/proc.c:140
	goexit()
0x114130 unknown pc

http://codereview.appspot.com/217116/diff/2001/3003#newcode103
src/pkg/crypto/blowfish/block.go:103: xr ^= ((c.s0[xl>>24] + c.s1[xl>>16&0xFF])
^ c.s2[xl>>8&0xFF]) + c.s3[xl&0xFF] ^ c.p[16]
On 2010/02/25 09:01:02, rsc wrote:
> same comment about byte() conversion in place of &0xff.
> (and also on the >>24 variant)
> 

see previous comment.

http://codereview.appspot.com/217116/diff/2001/3004
File src/pkg/crypto/blowfish/blowfish_test.go (right):

http://codereview.appspot.com/217116/diff/2001/3004#newcode18
src/pkg/crypto/blowfish/blowfish_test.go:18: var encryptTests = []CryptTest{
On 2010/02/25 09:01:02, rsc wrote:
> add a comment saying where these tests came from.
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3004#newcode194
src/pkg/crypto/blowfish/blowfish_test.go:194: func BenchmarkEncoding(b
*testing.B) {
On 2010/02/25 09:01:02, rsc wrote:
> you can probably delete the benchmarks now.
> it's fine if you want to add a benchmark of 
> encrypting 1 KB or something like that.
> 

if you don't mind i'd rather keep them since they justify some coding decisions
which may change in the future.  but if removing them will make the code look
more uniform in the source tree then by all means pls. remove them --i'm
assuming you'll commit this patch once it's reviewed.

http://codereview.appspot.com/217116/diff/2001/3005
File src/pkg/crypto/blowfish/cipher.go (right):

http://codereview.appspot.com/217116/diff/2001/3005#newcode5
src/pkg/crypto/blowfish/cipher.go:5: // This package implements Blowfish: a
symmetric 64-bit block cipher designed
On 2010/02/25 09:01:02, rsc wrote:
> the package comment should say what users need to know:
> the rest can go after the package statement.
> 
> // This package implements Bruce Schneier's Blowfish encryption algorithm.
> package blowfish
> 
> // The code is a port of Bruce Schneier's C implementation.
> // See http://www.schneier.com/blowfish.html.
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode5
src/pkg/crypto/blowfish/cipher.go:5: // This package implements Blowfish: a
symmetric 64-bit block cipher designed
On 2010/02/25 09:01:02, rsc wrote:
> the package comment should say what users need to know:
> the rest can go after the package statement.
> 
> // This package implements Bruce Schneier's Blowfish encryption algorithm.
> package blowfish
> 
> // The code is a port of Bruce Schneier's C implementation.
> // See http://www.schneier.com/blowfish.html.
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode16
src/pkg/crypto/blowfish/cipher.go:16: // The Blowfish block size (64 bits) in
bytes.
On 2010/02/25 09:01:02, rsc wrote:
> can drop (64 bits) which is redundant given the definition below
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode19
src/pkg/crypto/blowfish/cipher.go:19: // Cipher is an instance of the internal
Blowfish key constructed from user
On 2010/02/25 09:01:02, rsc wrote:
> please copy the comments from the AES implementation
> (crypto/aes), both here and for all the functions below.
> they are more concise.
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode22
src/pkg/crypto/blowfish/cipher.go:22: p, s0, s1, s2, s3 []uint32
On 2010/02/25 09:01:02, rsc wrote:
> Since these are fixed size, the slice is unnecessary.
> You can use a single array and do the allocation in
> one chunk.
> 
> More importantly, having the fixed array will let the
> compiler eliminate bounds checks for constant indexes
> smaller than the array size:
> 
> type Cipher struct {
>     p [18]uint32
>     s0, s1, s2, s3 [256]uint32
> }
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode28
src/pkg/crypto/blowfish/cipher.go:28: return "crypto/blowfish: Invalid key size
" + strconv.Itoa(int(k))
On 2010/02/25 09:01:02, rsc wrote:
> lowercase letter after : please.  (invalid not Invalid).
> (see crypto/aes)
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode31
src/pkg/crypto/blowfish/cipher.go:31: // NewCipher creates and returns a new
Blowfish Cipher.  The 'key' argument
On 2010/02/25 09:01:02, rsc wrote:
> you're in package blowfish already.
> no need for quotes.  break line.
> (see crypto/aes)
> 
> // NewCipher creates and returns a Cipher.
> // The key argument should be the Blowfish key, 4 to 56 bytes.
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode38
src/pkg/crypto/blowfish/cipher.go:38: // allocate space for the cipher's context
On 2010/02/25 09:01:02, rsc wrote:
> with the changed Cipher above this shortens to
> 
> var c Cipher
> expandKey(key, &c)
> return &c, nil
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode50
src/pkg/crypto/blowfish/cipher.go:50: // satisfy the Key interface in the
package "crypto/modes".
On 2010/02/25 09:01:02, rsc wrote:
> re-copy aes comment now that it says crypto/block.  ;-)
> 
> // BlockSize returns the Blowfish block size, 8 bytes.
> // It is necessary to satisfy the Cipher interface in the
> // package "crypto/block".

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode53
src/pkg/crypto/blowfish/cipher.go:53: // Encrypt enciphers the first 8 bytes (64
bits) in 'src' using the Cipher's
On 2010/02/25 09:01:02, rsc wrote:
> copy aes comment
> 

done but note that this and the next one (for the Decrypt) refer to k which does
not exist in the signature of the method.

http://codereview.appspot.com/217116/diff/2001/3005#newcode61
src/pkg/crypto/blowfish/cipher.go:61: l, r = 0, 0
On 2010/02/25 09:01:02, rsc wrote:
> delete
> (compiler will just optimize away)
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode64
src/pkg/crypto/blowfish/cipher.go:64: // Decrypt deciphers the first 8 bytes (64
bits) in 'src' using the Cipher's
On 2010/02/25 09:01:02, rsc wrote:
> copy aes comment
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode72
src/pkg/crypto/blowfish/cipher.go:72: l, r = 0, 0
On 2010/02/25 09:01:02, rsc wrote:
> delete
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode75
src/pkg/crypto/blowfish/cipher.go:75: // Reset zeroes the cipher's internal key.
On 2010/02/25 09:01:02, rsc wrote:
> copy aes comment
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3005#newcode77
src/pkg/crypto/blowfish/cipher.go:77: var i int = 0
On 2010/02/25 09:01:02, rsc wrote:
> i suggest writing a helper
> 
> func zero(x []uint32) {
>     for i := range x {
>         x[i] = 0
>     }
> }
> 
> and then call it here on each slice.
> the compiler is much more likely to 
> get the bounds checks eliminated
> in a single loop, and it's clearer what's going on.
> the loop constants here are magic otherwise.
> 
> when you get rid of the slices as mentioned above,
> you'll have to say zero(&c.p) or zero(c.p[0:]).
> 

Done.

http://codereview.appspot.com/217116/diff/2001/3006
File src/pkg/crypto/blowfish/const.go (right):

http://codereview.appspot.com/217116/diff/2001/3006#newcode10
src/pkg/crypto/blowfish/const.go:10: var _S0 = []uint32{
On 2010/02/25 09:01:02, rsc wrote:
> please call this s0, s1, s2, ...
> there are some files that use _UPPER
> instead of lower, but those are dregs
> and we need to weed them out.
> (it took us a little while to come to grips
> with the case-based export rules.)

Done.

http://codereview.appspot.com/217116/diff/2001/3006#newcode53
src/pkg/crypto/blowfish/const.go:53: 0x53b02d5d, 0xa99f8fa1, 0x08ba4799,
0x6e85076a}
On 2010/02/25 09:01:02, rsc wrote:
> please move the } down to the next line.
> you'll have to end this line with a , to do that.
> 
> same applies to rest of file.
> 

Done.

[rsc, 2010-02-25 17:35:27]

your benchmark didn't see a speedup because you were using
the global s0 instead of a Cipher.s0, and the global s0 is still
a slice.  you can make those arrays by writing [...]uint32 in the
declaration instead of []uint32, and the compiler will count how
many elements are in the array and substitute that count for the ...
(var s0 = [...]uint32{numbers}).

with that change:

blowfish.BenchmarkUint32Index	10000000	       143 ns/op	 447.55 MB/s
blowfish.BenchmarkByteIndex	20000000	       135 ns/op	 474.07 MB/s

this is what i meant as far as byte conversions:

func newEncryptBlock(l, r uint32, c *Cipher) (uint32, uint32) {
	xl, xr := l, r
	xl ^= c.p[0]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[1]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[2]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[3]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[4]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[5]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[6]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[7]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[8]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[9]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[10]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[11]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[12]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[13]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[14]
	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
c.s3[byte(xl)] ^ c.p[15]
	xl ^= ((c.s0[byte(xr>>24)] + c.s1[byte(xr>>16)]) ^ c.s2[byte(xr>>8)]) +
c.s3[byte(xr)] ^ c.p[16]
	xr ^= c.p[17]
	return xr, xl
}

it does matter a little:

blowfish.BenchmarkEncryptBlock	10000000	       155 ns/op	 412.90 MB/s
blowfish.BenchmarkNewEncryptBlock	20000000	       124 ns/op	 516.13 MB/s

regarding the tiny timing benchmarks, if you want to keep them for yourself,
that's fine - move them to a separate timing_test.go that isn't part of the 
CL and they'll still run when you run gotest.  i'd rather not have them as part
of blowfish, because they're not blowfish.  all the benchmarks get run every
time a checkin happens, so throwaway benchmarks really do need to get
thrown away (http://godashboard.appspot.com/benchmarks).

> if you don't mind i'd rather keep them since they justify some coding
decisions
> which may change in the future.  but if removing them will make the code look
> more uniform in the source tree then by all means pls. remove them --i'm
> assuming you'll commit this patch once it's reviewed.

i will commit the patch, but i don't edit the patch before committing it,
so you need to take care of things like moving the benchmarks 
and adding the byte conversions.  (among other things, if i made local
edits that would cause a merge conflict for you when you did "hg sync".
also it's your CL, not mine.)

[rsn, 2010-02-26 09:38:23]

hello Russ,

On 2010/02/25 17:35:27, rsc wrote:
> your benchmark didn't see a speedup because you were using
> the global s0 instead of a Cipher.s0, and the global s0 is still
> a slice.

noted.


>  you can make those arrays by writing [...]uint32 in the
> declaration instead of []uint32, and the compiler will count how
> many elements are in the array and substitute that count for the ...
> (var s0 = [...]uint32{numbers}).

ok.  i changed those to be [256]uint32{numbers} since i know already how many
there are.

 
> with that change:
> 
> blowfish.BenchmarkUint32Index	10000000	       143 ns/op	 447.55 MB/s
> blowfish.BenchmarkByteIndex	20000000	       135 ns/op	 474.07 MB/s
> 
> this is what i meant as far as byte conversions:
> 
> func newEncryptBlock(l, r uint32, c *Cipher) (uint32, uint32) {
> 	xl, xr := l, r
> 	xl ^= c.p[0]
> 	xr ^= ((c.s0[byte(xl>>24)] + c.s1[byte(xl>>16)]) ^ c.s2[byte(xl>>8)]) +
> c.s3[byte(xl)] ^ c.p[1]
> [...snip]

when i do that i get an exception as stated in a previous reply.  here is a
short program that reproduces the issue (file named b1.go):

package main

import "fmt"

func main() {
	x := uint32(0x01020304)
	y := [...]uint32{1, 2, 3, 4, 5}
	z := y[byte(x)]
	fmt.Printf("done z = %#x", z)
}

when compiled, linked and run i get the following:

$ 8g b1.go
$ 8l b1.8
$ ./8.out 
throw: index out of range

panic PC=0x11c040
throw+0x46 /opt/go/src/pkg/runtime/runtime.c:74
	throw(0x808410c, 0x80899a8)
runtime.throwindex+0x24 /opt/go/src/pkg/runtime/runtime.c:47
	runtime.throwindex()
main.main+0x41 /home/raif/Documents/b1.go:8
	main.main()
mainstart+0xf /opt/go/src/pkg/runtime/386/asm.s:83
	mainstart()
goexit /opt/go/src/pkg/runtime/proc.c:140
	goexit()

i must be doing something wrong but what is it?

[rsc, 2010-02-26 16:22:01]

> package main
>
> import "fmt"
>
> func main() {
>        x := uint32(0x01020304)
>        y := [...]uint32{1, 2, 3, 4, 5}
>        z := y[byte(x)]
>        fmt.Printf("done z = %#x", z)
> }
>
> when compiled, linked and run i get the following:
>
> $ 8g b1.go
> $ 8l b1.8
> $ ./8.out
> throw: index out of range

Looks like a compiler bug, sorry.
I was using 6g, which apparently doesn't have the bug.
Will fix.

Russ

[rsn, 2010-02-26 21:14:52]

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

Please take another look.

[rsc, 2010-02-26 21:19:12]

Looks good.

If you hg sync and then re-run all.bash you can take the &0xFF out.

Russ

[rsn, 2010-02-26 21:31:45]

hello Russ,

On 2010/02/26 21:19:12, rsc wrote:
> Looks good.
> 
> If you hg sync and then re-run all.bash you can take the &0xFF out.

when all.bash is invoked it exists w/:

cd crypto/blowfish && /home/raif/bin/gomake install
make[1]: Entering directory `/opt/go/src/pkg/crypto/blowfish'
/home/raif/bin/8g -o _go_.8 block.go cipher.go const.go 
cp _obj/reflect.a "/opt/go/pkg/linux_386/reflect.a"
registers allocated at
	AX	0
	CX	0
	DX	0
	BX	0x804bb84
	SP	0
	BP	0x805454e
	SI	0x805454e
	DI	0x805222d
block.go:55: out of fixed registers
block.go:55: fatal error: regfree: reg not allocated
make[1]: Leaving directory `/opt/go/src/pkg/reflect'
cd crypto/rc4 && /home/raif/bin/gomake install
make[1]: *** [_go_.8] Error 1
make[1]: Leaving directory `/opt/go/src/pkg/crypto/blowfish'

thoughts?

[rsc, 2010-02-26 21:33:06]

cool, another bug.
(there are so few registers on the 386...)
please run hg upload to push out the latest
copy of your code and i will patch it into
my client and make sure 8g can handle it.

thanks.
russ

[rsn, 2010-02-26 21:43:08]

hello Russ,

On 2010/02/26 21:33:06, rsc wrote:
> cool, another bug.
> (there are so few registers on the 386...)
> please run hg upload to push out the latest
> copy of your code and i will patch it into
> my client and make sure 8g can handle it.

done --patch set #5.

thanks for all your help :-)

[rsn, 2010-02-26 22:32:19]

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

Please take another look.

[rsn, 2010-02-26 22:35:06]

hello Russ,

just re-built Go with your latest fix and verified that it works.  i removed the
0xFF from the code and the TODO comments.

see latest patch-set #6.

thanks for your prompt intervention.

cheers;
rsn

[rsc, 2010-02-26 22:57:46]

LGTM

but one final nit:
when i run "godoc crypto/blowfish" it prints

PACKAGE

package blowfish
import "crypto/blowfish"

The startup permutation array and substitution boxes.
They are the hexadecimal digits of PI; see:
http://www.schneier.com/code/constants.txt.

...

there needs to be a blank line between that
comment (about digits of PI) and the line
"package blowfish", so that the other package
doc comment will be used instead.  ;-)

russ

[rsn, 2010-02-26 23:06:04]

On 2010/02/26 22:57:46, rsc wrote:
> [...snip]
> there needs to be a blank line between that
> comment (about digits of PI) and the line
> "package blowfish", so that the other package
> doc comment will be used instead.  ;-)

nice!  fixed and verified.  will mail a new patch-set soon.

cheers;
rsn

[rsn, 2010-02-26 23:08:04]

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

Please take another look.

[rsc, 2010-02-26 23:24:51]

*** Submitted as http://code.google.com/p/go/source/detail?r=2a602fdb373e ***

crypto/blowfish: new package

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

Committer: Russ Cox <rsc@golang.org>