runtime: Remove now unnecessary pad field from ParFor.

    
    It is not needed due to the removal of the ctx field.
    
    Reviewed-on: https://go-review.googlesource.com/16525

From-SVN: r229616

4 files changed, 114 insertions, 3 deletions

diff --git a/libgo/go/hash/crc32/crc32.go b/libgo/go/hash/crc32/crc32.go
index 6a6b947..234d929 100644
--- a/libgo/go/hash/crc32/crc32.go
+++ b/libgo/go/hash/crc32/crc32.go
@@ -5,6 +5,11 @@
 // Package crc32 implements the 32-bit cyclic redundancy check, or CRC-32,
 // checksum. See http://en.wikipedia.org/wiki/Cyclic_redundancy_check for
 // information.
+//
+// Polynomials are represented in LSB-first form also known as reversed representation.
+//
+// See http://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Reversed_representations_and_reciprocal_polynomials
+// for information.
 package crc32
 
 import (
@@ -49,6 +54,13 @@ func castagnoliInit() {
 // IEEETable is the table for the IEEE polynomial.
 var IEEETable = makeTable(IEEE)
 
+// slicing8Table is array of 8 Tables
+type slicing8Table [8]Table
+
+// iEEETable8 is the slicing8Table for IEEE
+var iEEETable8 *slicing8Table
+var iEEETable8Once sync.Once
+
 // MakeTable returns the Table constructed from the specified polynomial.
 func MakeTable(poly uint32) *Table {
 	switch poly {
@@ -78,6 +90,20 @@ func makeTable(poly uint32) *Table {
 	return t
 }
 
+// makeTable8 returns slicing8Table constructed from the specified polynomial.
+func makeTable8(poly uint32) *slicing8Table {
+	t := new(slicing8Table)
+	t[0] = *makeTable(poly)
+	for i := 0; i < 256; i++ {
+		crc := t[0][i]
+		for j := 1; j < 8; j++ {
+			crc = t[0][crc&0xFF] ^ (crc >> 8)
+			t[j][i] = crc
+		}
+	}
+	return t
+}
+
 // digest represents the partial evaluation of a checksum.
 type digest struct {
 	crc uint32
@@ -106,11 +132,32 @@ func update(crc uint32, tab *Table, p []byte) uint32 {
 	return ^crc
 }
 
+// updateSlicingBy8 updates CRC using Slicing-by-8
+func updateSlicingBy8(crc uint32, tab *slicing8Table, p []byte) uint32 {
+	crc = ^crc
+	for len(p) > 8 {
+		crc ^= uint32(p[0]) | uint32(p[1])<<8 | uint32(p[2])<<16 | uint32(p[3])<<24
+		crc = tab[0][p[7]] ^ tab[1][p[6]] ^ tab[2][p[5]] ^ tab[3][p[4]] ^
+			tab[4][crc>>24] ^ tab[5][(crc>>16)&0xFF] ^
+			tab[6][(crc>>8)&0xFF] ^ tab[7][crc&0xFF]
+		p = p[8:]
+	}
+	crc = ^crc
+	return update(crc, &tab[0], p)
+}
+
 // Update returns the result of adding the bytes in p to the crc.
 func Update(crc uint32, tab *Table, p []byte) uint32 {
 	if tab == castagnoliTable {
 		return updateCastagnoli(crc, p)
 	}
+	// only use slicing-by-8 when input is larger than 4KB
+	if tab == IEEETable && len(p) >= 4096 {
+		iEEETable8Once.Do(func() {
+			iEEETable8 = makeTable8(IEEE)
+		})
+		return updateSlicingBy8(crc, iEEETable8, p)
+	}
 	return update(crc, tab, p)
 }
 
@@ -132,4 +179,4 @@ func Checksum(data []byte, tab *Table) uint32 { return Update(0, tab, data) }
 
 // ChecksumIEEE returns the CRC-32 checksum of data
 // using the IEEE polynomial.
-func ChecksumIEEE(data []byte) uint32 { return update(0, IEEETable, data) }
+func ChecksumIEEE(data []byte) uint32 { return Update(0, IEEETable, data) }
diff --git a/libgo/go/hash/crc32/crc32_generic.go b/libgo/go/hash/crc32/crc32_generic.go
index c3fdcd6..416c1b7 100644
--- a/libgo/go/hash/crc32/crc32_generic.go
+++ b/libgo/go/hash/crc32/crc32_generic.go
@@ -2,7 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// +build 386 arm
+// +build 386 arm arm64 ppc64 ppc64le
 
 package crc32
 
diff --git a/libgo/go/hash/crc32/crc32_test.go b/libgo/go/hash/crc32/crc32_test.go
index 75dc26e..1ca3ac2 100644
--- a/libgo/go/hash/crc32/crc32_test.go
+++ b/libgo/go/hash/crc32/crc32_test.go
@@ -81,7 +81,7 @@ func TestGolden(t *testing.T) {
 	}
 }
 
-func BenchmarkCrc32KB(b *testing.B) {
+func BenchmarkIEEECrc1KB(b *testing.B) {
 	b.SetBytes(1024)
 	data := make([]byte, 1024)
 	for i := range data {
@@ -97,3 +97,37 @@ func BenchmarkCrc32KB(b *testing.B) {
 		h.Sum(in)
 	}
 }
+
+func BenchmarkIEEECrc4KB(b *testing.B) {
+	b.SetBytes(4096)
+	data := make([]byte, 4096)
+	for i := range data {
+		data[i] = byte(i)
+	}
+	h := NewIEEE()
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
+	}
+}
+
+func BenchmarkCastagnoliCrc1KB(b *testing.B) {
+	b.SetBytes(1024)
+	data := make([]byte, 1024)
+	for i := range data {
+		data[i] = byte(i)
+	}
+	h := New(MakeTable(Castagnoli))
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
+	}
+}
diff --git a/libgo/go/hash/crc32/example_test.go b/libgo/go/hash/crc32/example_test.go
new file mode 100644
index 0000000..a1d9e16
--- /dev/null
+++ b/libgo/go/hash/crc32/example_test.go
@@ -0,0 +1,30 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// +build ignore
+
+package crc32_test
+
+import (
+	"fmt"
+	"hash/crc32"
+)
+
+func ExampleMakeTable() {
+	// In this package, the CRC polynomial is represented in reversed notation,
+	// or LSB-first representation.
+	//
+	// LSB-first representation is a hexadecimal number with n bits, in which the
+	// most significant bit represents the coefficient of x⁰ and the least significant
+	// bit represents the coefficient of xⁿ⁻¹ (the coefficient for xⁿ is implicit).
+	//
+	// For example, CRC32-Q, as defined by the following polynomial,
+	//	x³²+ x³¹+ x²⁴+ x²²+ x¹⁶+ x¹⁴+ x⁸+ x⁷+ x⁵+ x³+ x¹+ x⁰
+	// has the reversed notation 0b11010101100000101000001010000001, so the value
+	// that should be passed to MakeTable is 0xD5828281.
+	crc32q := crc32.MakeTable(0xD5828281)
+	fmt.Printf("%08x\n", crc32.Checksum([]byte("Hello world"), crc32q))
+	// Output:
+	// 2964d064
+}