code review 11874043: crypto/des: faster block expansion.

crypto/des: faster block expansion.

On amd64:

benchmark           old ns/op    new ns/op    delta
BenchmarkEncrypt         6170         3593  -41.77%
BenchmarkDecrypt         6209         3564  -42.60%

benchmark            old MB/s     new MB/s  speedup
BenchmarkEncrypt         1.30         2.23    1.72x
BenchmarkDecrypt         1.29         2.24    1.74x

Update issue 4299.

[remyoudompheng, 2013-07-25 21:50:49]

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

I'd like you to review this change to
https://go.googlecode.com/hg/

[remyoudompheng, 2013-07-25 21:52:33]

See the 6g assembly for expandBlock:

--- prog list "expandBlock" ---
0284 (block.go:68) TEXT    expandBlock+0(SB),$0-16
0285 (block.go:68) FUNCDATA $0,gc·5+0(SB)
0286 (block.go:68) TYPE    src+0(FP){uint32},$4
0287 (block.go:68) TYPE    block+8(FP){uint64},$8
0288 (block.go:68) MOVQ    $0,DX
0289 (block.go:68) MOVQ    DX,block+8(FP)
0290 (block.go:69) MOVL    src+0(FP),AX
0291 (block.go:69) ROLL    $5,AX
0292 (block.go:70) MOVQ    $0,CX
0293 (block.go:70) JMP     ,295
0294 (block.go:70) INCQ    ,CX
0295 (block.go:70) CMPQ    CX,$8
0296 (block.go:70) JGE     $0,304
0297 (block.go:71) SHLQ    $6,DX
0298 (block.go:72) MOVLQZX AX,BX
0299 (block.go:72) ANDQ    $63,BX
0300 (block.go:72) ORQ     BX,DX
0301 (block.go:72) MOVQ    DX,block+8(FP)
0302 (block.go:73) ROLL    $4,AX
0303 (block.go:70) JMP     ,294
0304 (block.go:75) RET     ,

[bradfitz, 2013-07-26 00:58:28]

LGTM

Nice.

Verified the functions produce equivalent output for all inputs, too.


On Thu, Jul 25, 2013 at 2:50 PM, <remyoudompheng@gmail.com> wrote:

> Reviewers: golang-dev1, agl,
>
> Message:
> Hello golang-dev@googlegroups.com, agl@chromium.org (cc:
> golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> crypto/des: faster block expansion.
>
> On amd64:
>
> benchmark           old ns/op    new ns/op    delta
> BenchmarkEncrypt         6170         3593  -41.77%
> BenchmarkDecrypt         6209         3564  -42.60%
>
> benchmark            old MB/s     new MB/s  speedup
> BenchmarkEncrypt         1.30         2.23    1.72x
> BenchmarkDecrypt         1.29         2.24    1.74x
>
> Update issue 4299.
>
> Please review this at
https://codereview.appspot.**com/11874043/<https://codereview.appspot.com/118...
>
> Affected files:
>   M src/pkg/crypto/des/block.go
>   M src/pkg/crypto/des/const.go
>   M src/pkg/crypto/des/des_test.go
>
>
> Index: src/pkg/crypto/des/block.go
> ==============================**==============================**=======
> --- a/src/pkg/crypto/des/block.go
> +++ b/src/pkg/crypto/des/block.go
> @@ -40,7 +40,7 @@
>
>  // DES Feistel function
>  func feistel(right uint32, key uint64) (result uint32) {
> -       sBoxLocations := key ^ permuteBlock(uint64(right),
> expansionFunction[:])
> +       sBoxLocations := key ^ expandBlock(right)
>         var sBoxResult uint32
>         for i := uint8(0); i < 8; i++ {
>                 sBoxLocation := uint8(sBoxLocations>>42) & 0x3f
> @@ -63,6 +63,18 @@
>         return
>  }
>
> +// expandBlock expands an input block of 32 bits,
> +// producing an output block of 48 bits.
> +func expandBlock(src uint32) (block uint64) {
> +       src = (src << 5) | (src >> 27)
> +       for i := 0; i < 8; i++ {
> +               block <<= 6
> +               block |= uint64(src) & (1<<6 - 1)
> +               src = (src << 4) | (src >> 28)
> +       }
> +       return
> +}
> +
>  // creates 16 28-bit blocks rotated according
>  // to the rotation schedule
>  func ksRotate(in uint32) (out []uint32) {
> Index: src/pkg/crypto/des/const.go
> ==============================**==============================**=======
> --- a/src/pkg/crypto/des/const.go
> +++ b/src/pkg/crypto/des/const.go
> @@ -32,17 +32,6 @@
>         31, 63, 23, 55, 15, 47, 7, 39,
>  }
>
> -// Used to expand an input block of 32 bits, producing an output block of
> 48
> -// bits.
> -var expansionFunction = [48]byte{
> -       0, 31, 30, 29, 28, 27, 28, 27,
> -       26, 25, 24, 23, 24, 23, 22, 21,
> -       20, 19, 20, 19, 18, 17, 16, 15,
> -       16, 15, 14, 13, 12, 11, 12, 11,
> -       10, 9, 8, 7, 8, 7, 6, 5,
> -       4, 3, 4, 3, 2, 1, 0, 31,
> -}
> -
>  // Yields a 32-bit output from a 32-bit input
>  var permutationFunction = [32]byte{
>         16, 25, 12, 11, 3, 20, 4, 15,
> Index: src/pkg/crypto/des/des_test.go
> ==============================**==============================**=======
> --- a/src/pkg/crypto/des/des_test.**go
> +++ b/src/pkg/crypto/des/des_test.**go
> @@ -1521,3 +1521,31 @@
>         // See crypto/cipher for how to use a cipher.Block for encryption
> and
>         // decryption.
>  }
> +
> +func BenchmarkEncrypt(b *testing.B) {
> +       tt := encryptDESTests[0]
> +       c, err := NewCipher(tt.key)
> +       if err != nil {
> +               b.Fatal("NewCipher:", err)
> +       }
> +       out := make([]byte, len(tt.in))
> +       b.SetBytes(int64(len(out)))
> +       b.ResetTimer()
> +       for i := 0; i < b.N; i++ {
> +               c.Encrypt(out, tt.in)
> +       }
> +}
> +
> +func BenchmarkDecrypt(b *testing.B) {
> +       tt := encryptDESTests[0]
> +       c, err := NewCipher(tt.key)
> +       if err != nil {
> +               b.Fatal("NewCipher:", err)
> +       }
> +       out := make([]byte, len(tt.out))
> +       b.SetBytes(int64(len(out)))
> +       b.ResetTimer()
> +       for i := 0; i < b.N; i++ {
> +               c.Decrypt(out, tt.out)
> +       }
> +}
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>

[rsc, 2013-07-26 02:51:34]

LGTM

[rsc, 2013-07-26 03:04:31]

Do you know why it flushes block to memory so often?

[remyoudompheng, 2013-07-26 07:00:02]

On 2013/07/26 03:04:31, rsc wrote:
> Do you know why it flushes block to memory so often?

I think it arranges so that the last instruction in the control flow flushes.
Since that instruction is inside the loop, well...

If you add a "block = block" line before the return it becomes like this:

--- prog list "expandBlock" ---
0284 (block.go:68) TEXT    expandBlock+0(SB),$0-16
0285 (block.go:68) FUNCDATA $0,gc·5+0(SB)
0286 (block.go:68) TYPE    src+0(FP){uint32},$4
0287 (block.go:68) TYPE    block+8(FP){uint64},$8
0288 (block.go:69) MOVL    src+0(FP),CX
0289 (block.go:68) MOVQ    $0,AX
0290 (block.go:69) ROLL    $5,CX
0291 (block.go:70) MOVQ    $0,DX
0292 (block.go:70) JMP     ,294
0293 (block.go:70) INCQ    ,DX
0294 (block.go:70) CMPQ    DX,$8
0295 (block.go:70) JGE     $0,302
0296 (block.go:71) SHLQ    $6,AX
0297 (block.go:72) MOVLQZX CX,BX
0298 (block.go:72) ANDQ    $63,BX
0299 (block.go:72) ORQ     BX,AX
0300 (block.go:73) ROLL    $4,CX
0301 (block.go:70) JMP     ,293
0302 (block.go:75) MOVQ    AX,block+8(FP)
0303 (block.go:76) RET     ,

[remyoudompheng, 2013-07-26 07:10:52]

*** Submitted as https://code.google.com/p/go/source/detail?r=654ca7de0282 ***

crypto/des: faster block expansion.

On amd64:

benchmark           old ns/op    new ns/op    delta
BenchmarkEncrypt         6170         3593  -41.77%
BenchmarkDecrypt         6209         3564  -42.60%

benchmark            old MB/s     new MB/s  speedup
BenchmarkEncrypt         1.30         2.23    1.72x
BenchmarkDecrypt         1.29         2.24    1.74x

Update issue 4299.

R=golang-dev, agl, bradfitz, rsc
CC=golang-dev
https://codereview.appspot.com/11874043