summaryrefslogtreecommitdiff
path: root/src/math/big
Commit message (Collapse)AuthorAgeFilesLines
* math/big: fix Add, Sub when receiver aliases 2nd operandAlberto Donizetti2017-05-312-2/+39
| | | | | | | | | | Fixes #20490 Change-Id: I9cfa604f9ff94df779cb9b4cbbd706258fc473ac Reviewed-on: https://go-review.googlesource.com/44150 Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
* math/big: improve performance for addVV/subVV for ppc64xCarlos Eduardo Seo2017-04-251-12/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change adds a better asm implementation of addVV for ppc64x, with speedups up to nearly 3x in the best cases. benchmark old ns/op new ns/op delta BenchmarkAddVV/1-8 7.33 5.81 -20.74% BenchmarkAddVV/2-8 8.72 6.49 -25.57% BenchmarkAddVV/3-8 10.5 7.08 -32.57% BenchmarkAddVV/4-8 12.7 7.57 -40.39% BenchmarkAddVV/5-8 14.3 8.06 -43.64% BenchmarkAddVV/10-8 27.6 11.1 -59.78% BenchmarkAddVV/100-8 218 82.4 -62.20% BenchmarkAddVV/1000-8 2064 718 -65.21% BenchmarkAddVV/10000-8 20536 7153 -65.17% BenchmarkAddVV/100000-8 211004 72403 -65.69% benchmark old MB/s new MB/s speedup BenchmarkAddVV/1-8 8729.74 11006.26 1.26x BenchmarkAddVV/2-8 14683.65 19707.55 1.34x BenchmarkAddVV/3-8 18226.96 27103.63 1.49x BenchmarkAddVV/4-8 20204.50 33805.81 1.67x BenchmarkAddVV/5-8 22348.64 39694.06 1.78x BenchmarkAddVV/10-8 23212.74 57631.08 2.48x BenchmarkAddVV/100-8 29300.07 77629.53 2.65x BenchmarkAddVV/1000-8 31000.56 89094.54 2.87x BenchmarkAddVV/10000-8 31163.61 89469.16 2.87x BenchmarkAddVV/100000-8 30331.16 88393.73 2.91x It also adds the use of CTR for the loop counter in subVV, instead of manually updating the loop counter. This is slightly faster. Change-Id: Ic4b05cad384fd057972d46a5618ed5c3039d7460 Reviewed-on: https://go-review.googlesource.com/41010 Run-TryBot: Lynn Boger <laboger@linux.vnet.ibm.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Lynn Boger <laboger@linux.vnet.ibm.com>
* all: fix minor misspellingsEric Lagergren2017-04-031-1/+1
| | | | | | | | Change-Id: I1f1cfb161640eb8756fb1a283892d06b30b7a8fa Reviewed-on: https://go-review.googlesource.com/39356 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: Unify divWW implementation for ppc64 and ppc64le.Carlos Eduardo Seo2017-03-313-64/+39
| | | | | | | | | | | | | | Starting in go1.9, the minimum processor requirement for ppc64 is POWER8. So it may now use the same divWW implementation as ppc64le. Updates #19074 Change-Id: If1a85f175cda89eee06a1024ccd468da6124c844 Reviewed-on: https://go-review.googlesource.com/39010 Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Reviewed-by: Lynn Boger <laboger@linux.vnet.ibm.com>
* math/big: replace local versions of bitLen, nlz with math/bits versionsRobert Griesemer2017-03-2317-141/+17
| | | | | | | | | | | | Verified that BenchmarkBitLen time went down from 2.25 ns/op to 0.65 ns/op an a 2.3 GHz Intel Core i7, before removing that benchmark (now covered by math/bits benchmarks). Change-Id: I3890bb7d1889e95b9a94bd68f0bdf06f1885adeb Reviewed-on: https://go-review.googlesource.com/38464 Run-TryBot: Robert Griesemer <gri@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: fix TestFloatSetFloat64StringRobert Griesemer2017-03-231-11/+13
| | | | | | | | | | | | | A -0 constant is the same as 0. Use explicit negative zero for float64 -0.0. Also, fix two test cases that were wrong. Fixes #19673. Change-Id: Ic09775f29d9bc2ee7814172e59c4a693441ea730 Reviewed-on: https://go-review.googlesource.com/38463 Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org>
* math/big: make nat.setUint64 vet-friendlyJosh Bleecher Snyder2017-03-111-15/+5
| | | | | | | | | | | | | | | | | | | nat.setUint64 is nicely generic. By assuming 32- or 64-bit words, however, we can write simpler code, and eliminate some shifts in dead code that vet complains about. Generated code for 64 bit systems is unaltered. Generated code for 32 bit systems is much better. For 386, the routine length drops from 325 bytes of code to 271 bytes of code, with fewer loops. Change-Id: I1bc14c06272dee37a7fcb48d33dd1e621eba945d Reviewed-on: https://go-review.googlesource.com/38070 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@golang.org>
* all: remove the the duplicate wordsEitan Adler2017-03-061-1/+1
| | | | | | | | | Change-Id: I6343c162e27e2e492547c96f1fc504909b1c03c0 Reviewed-on: https://go-review.googlesource.com/37793 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: use math/bits where appropriateRobert Griesemer2017-02-244-97/+18
| | | | | | | | | | | | | | This change adds math/bits as a new dependency of math/big. - use bits.LeadingZeroes instead of local implementation (they are identical, so there's no performance loss here) - leave other functionality local (ntz, bitLen) since there's faster implementations in math/big at the moment Change-Id: I1218aa8a1df0cc9783583b090a4bb5a8a145c4a2 Reviewed-on: https://go-review.googlesource.com/37141 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: define Word as uint instead of uintptrRobert Griesemer2017-02-211-1/+1
| | | | | | | | | | | | | | | | | | | | For compatibility with math/bits uint operations. When math/big was written originally, the Go compiler used 32bit int/uint values even on a 64bit machine. uintptr was the type that represented the machine register size. Now, the int/uint types are sized to the native machine register size, so they are the natural machine Word type. On most machines, the size of int/uint correspond to the size of uintptr. On platforms where uint and uintptr have different sizes, this change may lead to performance differences (e.g., amd64p32). Change-Id: Ief249c160b707b6441848f20041e32e9e9d8d8ca Reviewed-on: https://go-review.googlesource.com/37372 Run-TryBot: Robert Griesemer <gri@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: simplify bool expressionDaniel Martí2017-02-141-1/+1
| | | | | | | | Change-Id: I280c53be455f2fe0474ad577c0f7b7908a4eccb2 Reviewed-on: https://go-review.googlesource.com/36993 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: fix s390x test build tagsMichael Munday2017-02-141-1/+1
| | | | | | | | | | | The tests failed to compile when using the math_big_pure_go tag on s390x. Change-Id: I2a09f53ff6562ab9bc9b886cffc0f6205bbfcfbb Reviewed-on: https://go-review.googlesource.com/36956 Run-TryBot: Michael Munday <munday@ca.ibm.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* all: fix some printf format stringsJosh Bleecher Snyder2017-02-141-1/+1
| | | | | | | | | | Appease vet. Change-Id: Ie88de08b91041990c0eaf2e15628cdb98d40c660 Reviewed-on: https://go-review.googlesource.com/36938 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: add IsInt64/IsUint64 predicatesRobert Griesemer2017-02-072-47/+110
| | | | | | Change-Id: Ia5ed3919cb492009ac8f66d175b47a69f83ee4f1 Reviewed-on: https://go-review.googlesource.com/36487 Reviewed-by: Alan Donovan <adonovan@google.com>
* crypto/*: document use or non-use of constant-time algorithmsRuss Cox2016-12-071-1/+4
| | | | | | | | | | Fixes #16821. Change-Id: I63d5f3d7cfba1c76259912d754025c5f3cbe4a56 Reviewed-on: https://go-review.googlesource.com/31573 Run-TryBot: Russ Cox <rsc@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: add Baillie-PSW test to (*Int).ProbablyPrimeRuss Cox2016-11-222-57/+381
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | After x.ProbablyPrime(n) passes the n Miller-Rabin rounds, add a Baillie-PSW test before declaring x probably prime. Although the provable error bounds are unchanged, the empirical error bounds drop dramatically: there are no known inputs for which Baillie-PSW gives the wrong answer. For example, before this CL, big.NewInt(443*1327).ProbablyPrime(1) == true. Now it is (correctly) false. The new Baillie-PSW test is two pieces: an added Miller-Rabin round with base 2, and a so-called extra strong Lucas test. (See the references listed in prime.go for more details.) The Lucas test takes about 3.5x as long as the Miller-Rabin round, which is close to theoretical expectations. name time/op ProbablyPrime/Lucas 2.91ms ± 2% ProbablyPrime/MillerRabinBase2 850µs ± 1% ProbablyPrime/n=0 3.75ms ± 3% The speed of prime testing for a prime input does get slower: name old time/op new time/op delta ProbablyPrime/n=1 849µs ± 1% 4521µs ± 1% +432.31% (p=0.000 n=10+9) ProbablyPrime/n=5 4.31ms ± 3% 7.87ms ± 1% +82.70% (p=0.000 n=10+10) ProbablyPrime/n=10 8.52ms ± 3% 12.28ms ± 1% +44.11% (p=0.000 n=10+10) ProbablyPrime/n=20 16.9ms ± 2% 21.4ms ± 2% +26.35% (p=0.000 n=9+10) However, because the Baillie-PSW test is only added when the old ProbablyPrime(n) would return true, testing composites runs at the same speed as before, except in the case where the result would have been incorrect and is now correct. In particular, the most important use of this code is for generating random primes in crypto/rand. That use spends essentially all its time testing composites, so it is not slowed down by the new Baillie-PSW check: name old time/op new time/op delta Prime 104ms ±22% 111ms ±16% ~ (p=0.165 n=10+10) Thanks to Serhat Şevki Dinçer for CL 20170, which this CL builds on. Fixes #13229. Change-Id: Id26dde9b012c7637c85f2e96355d029b6382812a Reviewed-on: https://go-review.googlesource.com/30770 Run-TryBot: Russ Cox <rsc@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@golang.org>
* all: spell "marshal" and "unmarshal" consistentlyDmitri Shuralyov2016-11-122-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The tree is inconsistent about single l vs double l in those words in documentation, test messages, and one error value text. $ git grep -E '[Mm]arshall(|s|er|ers|ed|ing)' | wc -l 42 $ git grep -E '[Mm]arshal(|s|er|ers|ed|ing)' | wc -l 1694 Make it consistently a single l, per earlier decisions. This means contributors won't be confused by misleading precedence, and it helps consistency. Change the spelling in one error value text in newRawAttributes of crypto/x509 package to be consistent. This change was generated with: perl -i -npe 's,([Mm]arshal)l(|s|er|ers|ed|ing),$1$2,' $(git grep -l -E '[Mm]arshall' | grep -v AUTHORS | grep -v CONTRIBUTORS) Updates #12431. Follows https://golang.org/cl/14150. Change-Id: I85d28a2d7692862ccb02d6a09f5d18538b6049a2 Reviewed-on: https://go-review.googlesource.com/33017 Run-TryBot: Minux Ma <minux@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math, math/big: add support for GOARCH=mips{,le}Vladimir Stefanovic2016-11-031-0/+46
| | | | | | Change-Id: I54e100cced5b49674937fb87d1e0f585f962aeb7 Reviewed-on: https://go-review.googlesource.com/31484 Reviewed-by: Cherry Zhang <cherryyz@google.com>
* math/big: flip long/short flag on TestFloat32DistributionCherry Zhang2016-10-271-1/+1
| | | | | | | | | | It looks like a typo in CL 30707. Change-Id: Ia2d013567dbd1a49901d9be0cd2d5a103e6e38cf Reviewed-on: https://go-review.googlesource.com/32187 Run-TryBot: Cherry Zhang <cherryyz@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Russ Cox <rsc@golang.org>
* math/big: uses SIMD for some math big functions on s390xBill O'Farrell2016-10-263-270/+1019
| | | | | | | | | | | | | | | | | | | | | | | The following benchmarks are improved by the amounts shown (Others unaffected beyond the level of noise.) Also adds a test to confirm non-SIMD implementation still correct, even when run on SIMD-capable machine Benchmark old new BenchmarkAddVV/100-18 66148.08 MB/s 117546.19 MB/s 1.8x BenchmarkAddVV/1000-18 70168.27 MB/s 133478.96 MB/s 1.9x BenchmarkAddVV/10000-18 67489.80 MB/s 100010.79 MB/s 1.5x BenchmarkAddVV/100000-18 54329.99 MB/s 69232.45 MB/s 1.3x BenchmarkAddVW/100-18 9929.10 MB/s 14841.31 MB/s 1.5x BenchmarkAddVW/1000-18 10583.31 MB/s 18674.44 MB/s 1.76x BenchmarkAddVW/10000-18 10521.15 MB/s 17484.10 MB/s 1.66x BenchmarkAddVW/100000-18 10616.56 MB/s 18084.27 MB/s 1.7x Change-Id: Ic9234c41a43f6c5e9d0e9377de8b4deeefc428a7 Reviewed-on: https://go-review.googlesource.com/32211 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: fix alignment in Float.Parse docsMohit Agarwal2016-10-241-2/+2
| | | | | | | | | | | | | | | | | | | | | | Leading spaces in a couple of lines instead of tabs cause those to be misaligned (as seen on <https://golang.org/pkg/math/big/#Float.Parse>): <<< number = [ sign ] [ prefix ] mantissa [ exponent ] | infinity . sign = "+" | "-" . prefix = "0" ( "x" | "X" | "b" | "B" ) . mantissa = digits | digits "." [ digits ] | "." digits . exponent = ( "E" | "e" | "p" ) [ sign ] digits . digits = digit { digit } . digit = "0" ... "9" | "a" ... "z" | "A" ... "Z" . infinity = [ sign ] ( "inf" | "Inf" ) . >>> Replace the leading spaces with tabs so that those align well. Change-Id: Ibba6cd53f340001bbd929067dc587feb071dc3bd Reviewed-on: https://go-review.googlesource.com/31830 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: implement Float.Scan, type assert fmt interfaces to enforce docsEmmanuel Odeke2016-10-196-0/+89
| | | | | | | | | | | | | | | | | | Implements Float.Scan which satisfies fmt.Scanner interface. Also enforces docs' interface implementation claims with compile time type assertions, that is: + Float always implements fmt.Formatter and fmt.Scanner + Int always implements fmt.Formatter and fmt.Scanner + Rat always implements fmt.Formatter which will ensure that the API claims are strictly matched. Also note that Float.Scan doesn't handle ±Inf. Fixes #17391 Change-Id: I3d3dfbe7f602066975c7a7794fe25b4c645440ce Reviewed-on: https://go-review.googlesource.com/30723 Reviewed-by: Robert Griesemer <gri@golang.org>
* math/big: add benchmarks for big.Float StringAlberto Donizetti2016-10-181-1/+17
| | | | | | | | | | | | | | In addition to the DecimalConversion benchmark, that exercises the String method of the internal decimal type on a range of small shifts, add a few benchmarks for the big.Float String method. They can be used to obtain more realistic data on the real-world performance of big.Float printing. Change-Id: I7ada324e7603cb1ce7492ccaf3382db0096223ba Reviewed-on: https://go-review.googlesource.com/31275 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: add (*Int).SqrtRuss Cox2016-10-173-0/+87
| | | | | | | | | | | | This is needed for some of the more complex primality tests (to filter out exact squares), and while the code is simple the boundary conditions are not obvious, so it seems worth having in the library. Change-Id: Ica994a6b6c1e412a6f6d9c3cf823f9b653c6bcbd Reviewed-on: https://go-review.googlesource.com/30706 Run-TryBot: Russ Cox <rsc@golang.org> Reviewed-by: Robert Griesemer <gri@golang.org>
* math/big: slightly faster float->decimal conversionRobert Griesemer2016-10-171-3/+4
| | | | | | | | | | | | | | | | | | Inspired by Alberto Donizetti's observations in https://go-review.googlesource.com/#/c/30099/. name old time/op new time/op delta DecimalConversion-8 138µs ± 1% 136µs ± 2% -1.85% (p=0.000 n=10+10) 10 runs each, measured on a Mac Mini, 2.3 GHz Intel Core i7. Performance improvements varied between -1.25% to -4.4%; -1.85% is about in the middle of the observed improvement. The generated code is slightly shorter in the inner loops of the conversion code. Change-Id: I10fb3b2843da527691c39ad5e5e5bd37ed63e2fa Reviewed-on: https://go-review.googlesource.com/31250 Reviewed-by: Alan Donovan <adonovan@google.com>
* encoding/json: fix decoding of null into Unmarshaler, TextUnmarshalerRuss Cox2016-10-171-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 1. Define behavior for Unmarshal of JSON null into Unmarshaler and TextUnmarshaler. Specifically, an Unmarshaler will be given the literal null and can decide what to do (because otherwise json.RawMessage is impossible to implement), and a TextUnmarshaler will be skipped over (because there is no text to unmarshal), like most other inappropriate types. Document this in Unmarshal, with a reminder in UnmarshalJSON about handling null. 2. Test all this. 3. Fix the TextUnmarshaler case, which was returning an unmarshalling error, to match the definition. 4. Fix the error that had been used for the TextUnmarshaler, since it was claiming that there was a JSON string when in fact the problem was NOT having a string. 5. Adjust time.Time and big.Int's UnmarshalJSON to ignore null, as is conventional. Fixes #9037. Change-Id: If78350414eb8dda712867dc8f4ca35a9db041b0c Reviewed-on: https://go-review.googlesource.com/30944 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: move ProbablyPrime into its own source fileRuss Cox2016-10-115-193/+210
| | | | | | | | | A later CL will be adding more code here. It will help to keep it separate from the other code. Change-Id: I971ba53de819cd10991b51fdec665984939a5f9b Reviewed-on: https://go-review.googlesource.com/30709 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: test and optimize Exp(2, y, n) for large y, odd nRuss Cox2016-10-112-1/+34
| | | | | | | | | | | | | | | | | | The Montgomery multiply code is applicable to this case but was being bypassed. Don't do that. The old test len(x) > 1 was really just a bad approximation to x > 1. name old time/op new time/op delta Exp-8 5.56ms ± 4% 5.73ms ± 3% ~ (p=0.095 n=5+5) Exp2-8 7.59ms ± 1% 5.66ms ± 1% -25.40% (p=0.008 n=5+5) This comes up especially when doing Fermat (Miller-Rabin) primality tests with base 2. Change-Id: I4cc02978db6dfa93f7f3c8f32718e25eedb4f5ed Reviewed-on: https://go-review.googlesource.com/30708 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: move exhaustive tests behind -long flagRuss Cox2016-10-113-11/+14
| | | | | | | | | This way you can still run 'go test' or 'go bench -run Foo' without wondering why it is taking so very long. Change-Id: Icfa097a6deb1d6682acb7be9f34729215c29eabb Reviewed-on: https://go-review.googlesource.com/30707 Reviewed-by: Robert Griesemer <gri@golang.org>
* math/big: make division fasterRuss Cox2016-10-103-18/+86
| | | | | | | | | | | | | | | | | | | | | - Add new BenchmarkQuoRem. - Eliminate allocation in divLarge nat pool - Unroll mulAddVWW body 4x - Remove some redundant slice loads in divLarge name old time/op new time/op delta QuoRem-8 2.18µs ± 1% 1.93µs ± 1% -11.38% (p=0.000 n=19+18) The starting point in the comparison here is Cherry's pending CL to turn mulWW and divWW into intrinsics. The optimizations in divLarge work best because all the function calls are gone. The effect of this CL is not as large if you don't assume Cherry's CL. Change-Id: Ia6138907489c5b9168497912e43705634e163b35 Reviewed-on: https://go-review.googlesource.com/30613 Run-TryBot: Russ Cox <rsc@golang.org> Reviewed-by: Cherry Zhang <cherryyz@google.com>
* math/big: Rat.SetString to report error if input is not consumed entirelyRobert Griesemer2016-10-064-10/+23
| | | | | | | | | | Also, document behavior explicitly for all SetString implementations. Fixes #17001. Change-Id: Iccc882b4bc7f8b61b6092f330e405c146a80dc98 Reviewed-on: https://go-review.googlesource.com/30472 Reviewed-by: Matthew Dempsky <mdempsky@google.com>
* math/big: support negative numbers in ModInverseMichal Bohuslávek2016-09-272-0/+6
| | | | | | | | | | Fixes #16984 Change-Id: I3a330e82941a068ca6097985af4ab221275fd336 Reviewed-on: https://go-review.googlesource.com/29299 Run-TryBot: Adam Langley <agl@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Adam Langley <agl@golang.org>
* math/big: better SetFloat64 example in docAlberto Donizetti2016-09-261-1/+1
| | | | | | | | Fixes #17221 Change-Id: Idaa2af6b8646651ea72195671d1a4b5c370a5a22 Reviewed-on: https://go-review.googlesource.com/29711 Reviewed-by: Robert Griesemer <gri@golang.org>
* cmd/compile: intrinsify Ctz{32,64} and Bswap{32,64} on s390xMichael Munday2016-09-191-5/+5
| | | | | | | | | | | Also adds the 'find leftmost one' instruction (FLOGR) and replaces the WORD-encoded use of FLOGR in math/big with it. Change-Id: I18e7cd19e75b8501a6ae8bd925471f7e37ded206 Reviewed-on: https://go-review.googlesource.com/29372 Reviewed-by: Cherry Zhang <cherryyz@google.com> Run-TryBot: Michael Munday <munday@ca.ibm.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: cut 2 minutes off race testsBrad Fitzpatrick2016-09-144-0/+28
| | | | | | | | | | | | | No need to test so many sizes in race mode, especially for a package which doesn't use goroutines. Reduces test time from 2.5 minutes to 25 seconds. Updates #17104 Change-Id: I7065b39273f82edece385c0d67b3f2d83d4934b8 Reviewed-on: https://go-review.googlesource.com/29163 Reviewed-by: David Crawshaw <crawshaw@golang.org>
* runtime, math/big: allow R0 on s390x to contain values other than 0Michael Munday2016-09-121-0/+2
| | | | | | | | | | | | The new SSA backend for s390x can use R0 as a general purpose register. This change modifies assembly code to either avoid using R0 entirely or explicitly set R0 to 0. R0 can still be safely used as 0 in address calculations. Change-Id: I3efa723e9ef322a91a408bd8c31768d7858526c8 Reviewed-on: https://go-review.googlesource.com/28976 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
* math/big: add assembly implementation of arith for ppc64{le}Ethan Miller2016-08-293-19/+223
| | | | | | | | | | | | | | | | | | | | | | | | | | The existing implementation used a pure go implementation, leading to slow cryptographic performance. Implemented mulWW, subVV, mulAddVWW, addMulVVW, and bitLen for ppc64{le}. Implemented divWW for ppc64le only, as the DIVDEU instruction is only available on Power8 or newer. benchcmp output: benchmark old ns/op new ns/op delta BenchmarkSignP384 28934360 10877330 -62.41% BenchmarkRSA2048Decrypt 41261033 5139930 -87.54% BenchmarkRSA2048Sign 45231300 7610985 -83.17% Benchmark3PrimeRSA2048Decrypt 20487300 2481408 -87.89% Fixes #16621 Change-Id: If8b68963bb49909bde832f2bda08a3791c4f5b7a Reviewed-on: https://go-review.googlesource.com/26951 Run-TryBot: Michael Munday <munday@ca.ibm.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Michael Munday <munday@ca.ibm.com>
* math/big: avoid allocation in float.{Add, Sub} when there's no aliasingAlberto Donizetti2016-08-172-12/+70
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | name old time/op new time/op delta FloatAdd/10-4 116ns ± 1% 82ns ± 0% -28.74% (p=0.008 n=5+5) FloatAdd/100-4 124ns ± 0% 86ns ± 1% -30.34% (p=0.016 n=4+5) FloatAdd/1000-4 192ns ± 1% 123ns ± 0% -35.94% (p=0.008 n=5+5) FloatAdd/10000-4 826ns ± 0% 438ns ± 0% -46.99% (p=0.000 n=4+5) FloatAdd/100000-4 6.82µs ± 1% 3.36µs ± 0% -50.74% (p=0.008 n=5+5) FloatSub/10-4 108ns ± 1% 77ns ± 1% -29.06% (p=0.008 n=5+5) FloatSub/100-4 115ns ± 0% 79ns ± 0% -31.48% (p=0.029 n=4+4) FloatSub/1000-4 168ns ± 0% 99ns ± 0% -41.09% (p=0.029 n=4+4) FloatSub/10000-4 690ns ± 2% 288ns ± 1% -58.24% (p=0.008 n=5+5) FloatSub/100000-4 5.37µs ± 1% 2.10µs ± 1% -60.89% (p=0.008 n=5+5) name old alloc/op new alloc/op delta FloatAdd/10-4 48.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/100-4 64.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/1000-4 176B ± 0% 0B ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/10000-4 1.41kB ± 0% 0.00kB ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/100000-4 13.6kB ± 0% 0.0kB ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/10-4 48.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/100-4 64.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/1000-4 176B ± 0% 0B ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/10000-4 1.41kB ± 0% 0.00kB ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/100000-4 13.6kB ± 0% 0.0kB ±NaN% -100.00% (p=0.008 n=5+5) Fixes #14868 Change-Id: Ia2b8b1a8ef0868288ecb25f812b17bd03ff40d1c Reviewed-on: https://go-review.googlesource.com/23568 Reviewed-by: Robert Griesemer <gri@golang.org>
* crypto/cipher, math/big: fix example namesJosh Bleecher Snyder2016-08-161-3/+3
| | | | | | | | | | | | Fixes (legit) vet warnings. Fix some verb tenses while we're here. Updates #11041 Change-Id: I27e995f55b38f4cf584e97a67b8545e8247e83d6 Reviewed-on: https://go-review.googlesource.com/27122 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: David Crawshaw <crawshaw@golang.org>
* all: fix "result not used" vet warningsJosh Bleecher Snyder2016-08-161-1/+3
| | | | | | | | | | | | | For tests, assign to _. For benchmarks, assign to a sink. Updates #11041 Change-Id: I87c5543245c7bc74dceb38902f4551768dd37948 Reviewed-on: https://go-review.googlesource.com/27116 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: use array instead of slice for deBruijn lookupsJosh Bleecher Snyder2016-08-161-2/+2
| | | | | | | | | | | | | This allows the compiler to remove a bounds check. math/big/nat.go:681: index bounds check elided math/big/nat.go:683: index bounds check elided Change-Id: Ieecb89ec5e988761b06764bd671672015cd58e9d Reviewed-on: https://go-review.googlesource.com/26663 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: special-case a 0 mantissa during Rat parsingNathan VanBenschoten2016-06-242-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | Previously, a 0 mantissa was special-cased during big.Float parsing, but not during big.Rat parsing. This meant that a value like 0e9999999999 would parse successfully in big.Float.SetString, but would hang in big.Rat.SetString. This discrepancy became an issue in https://golang.org/src/go/constant/value.go?#L250, where the big.Float would report an exponent of 0, so big.Rat.SetString would be used and would subsequently hang. A Go Playground example of this is https://play.golang.org/p/3fy28eUJuF The solution is to special-case a zero mantissa during big.Rat parsing as well, so that neither big.Rat nor big.Float will hang when parsing a value with 0 mantissa but a large exponent. This was discovered using go-fuzz on CockroachDB: https://github.com/cockroachdb/go-fuzz/blob/master/examples/parser/main.go Fixes #16176 Change-Id: I775558a8682adbeba1cc9d20ba10f8ed26259c56 Reviewed-on: https://go-review.googlesource.com/24430 Reviewed-by: Robert Griesemer <gri@golang.org> Run-TryBot: Robert Griesemer <gri@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: avoid panic in float.Text with negative precAlberto Donizetti2016-06-012-2/+10
| | | | | | | | | | Fixes #15918 Change-Id: I4b434aed262960a2e6c659d4c2296fbf662c3a52 Reviewed-on: https://go-review.googlesource.com/23633 Run-TryBot: Robert Griesemer <gri@golang.org> Reviewed-by: Robert Griesemer <gri@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: using Run for some more benchmarksMarcel van Lohuizen2016-05-262-103/+57
| | | | | | | | Change-Id: I3ede8098f405de5d88e51c8370d3b68446d40744 Reviewed-on: https://go-review.googlesource.com/23428 Run-TryBot: Marcel van Lohuizen <mpvl@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@golang.org>
* math/big: simplify benchmarking code some moreRobert Griesemer2016-05-261-31/+17
| | | | | | | | Follow-up cleanup to https://golang.org/cl/23424/ . Change-Id: Ifb05c1ff5327df6bc5f4cbc554e18363293f7960 Reviewed-on: https://go-review.googlesource.com/23446 Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
* math/big: use run for benchmarksMarcel van Lohuizen2016-05-251-75/+60
| | | | | | | | | | shortens code and gives an example of the use of Run. Change-Id: I75ffaf762218a589274b4b62e19022e31e805d1b Reviewed-on: https://go-review.googlesource.com/23424 Reviewed-by: Russ Cox <rsc@golang.org> Run-TryBot: Marcel van Lohuizen <mpvl@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: write t*10 to multiply t by 10Russ Cox2016-05-241-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The compiler has caught up. In fact the compiler is ahead; it knows about a magic multiply-by-5 instruction: // compute '0' + byte(r - t*10) in AX MOVQ t, AX LEAQ (AX)(AX*4), AX SHLQ $1, AX MOVQ r, CX SUBQ AX, CX LEAL 48(CX), AX For comparison, the shifty version compiles to: // compute '0' + byte(r - t*10) in AX MOVQ t, AX MOVQ AX, CX SHLQ $3, AX MOVQ r, DX SUBQ AX, DX SUBQ CX, DX SUBQ CX, DX LEAL 48(DX), AX Fixes #2671. Change-Id: Ifbf23dbfeb19c0bb020fa44eb2f025943969fb6b Reviewed-on: https://go-review.googlesource.com/23372 Run-TryBot: Russ Cox <rsc@golang.org> Reviewed-by: Andrew Gerrand <adg@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
* math/big: more tests, documentation for Flot gob marshallingRobert Griesemer2016-04-202-36/+79
| | | | | | | | | | | | | | | | | | | | | | | | | | Follow-up to https://golang.org/cl/21755. This turned out to be a bit more than just a few nits as originally expected in that CL. 1) The actual mantissa may be shorter than required for the given precision (because of trailing 0's): no need to allocate space for it (and transmit 0's). This can save a lot of space when the precision is high: E.g., for prec == 1000, 16 words or 128 bytes are required at the most, but if the actual number is short, it may be much less (for the test cases present, it's significantly less). 2) The actual mantissa may be longer than the number of words required for the given precision: make sure to not overflow when encoding in bytes. 3) Add more documentation. 4) Add more tests. Change-Id: I9f40c408cfdd9183a8e81076d2f7d6c75e7a00e9 Reviewed-on: https://go-review.googlesource.com/22324 Reviewed-by: Alan Donovan <adonovan@google.com>
* math/big: implement GobDecode/Encode for big.FloatOneOfOne2016-04-202-1/+127
| | | | | | | | | | Added GobEncode/Decode and a test for them. Fixes #14593 Change-Id: Ic8d3efd24d0313a1a66f01da293c4c1fd39764a8 Reviewed-on: https://go-review.googlesource.com/21755 Reviewed-by: Robert Griesemer <gri@golang.org>
* all: remove unnecessary type conversionsMatthew Dempsky2016-04-153-4/+4
| | | | | | | | | | | | | cmd and runtime were handled separately, and I'm intentionally skipped syscall. This is the rest of the standard library. CL generated mechanically with github.com/mdempsky/unconvert. Change-Id: I9e0eff886974dedc37adb93f602064b83e469122 Reviewed-on: https://go-review.googlesource.com/22104 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
View Lorry Controller Status