Skip to content

Commit a4599ef

Browse files
griesemergriesemer
committed
cmd/compile: update vendored copy of math/big
- obtained by running sh vendor.bash - contains updated tests and some bug fixes for Montgomery mult. (not used by compiler) - for consistency of math/big versions only Change-Id: Ib47e48d5b7f6d0e05d7837b1bc74bdb03f2b094e Reviewed-on: https://go-review.googlesource.com/18831 Run-TryBot: Robert Griesemer <[email protected]> TryBot-Result: Gobot Gobot <[email protected]> Reviewed-by: Brad Fitzpatrick <[email protected]>
1 parent 445c685 commit a4599ef

4 files changed

Lines changed: 67 additions & 26 deletions

File tree

‎src/cmd/compile/internal/big/int.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -273,7 +273,7 @@ func (z *Int) Mod(x, y *Int) *Int {
273273
// DivMod implements Euclidean division and modulus (unlike Go):
274274
//
275275
// q = x div y such that
276-
// m = x - y*q with 0 <= m < |q|
276+
// m = x - y*q with 0 <= m < |y|
277277
//
278278
// (See Raymond T. Boute, ``The Euclidean definition of the functions
279279
// div and mod''. ACM Transactions on Programming Languages and

‎src/cmd/compile/internal/big/int_test.go‎

Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -544,19 +544,34 @@ var expTests = []struct {
544544
{"0x8000000000000000", "1000", "6719", "1603"},
545545
{"0x8000000000000000", "1000000", "6719", "3199"},
546546
{"0x8000000000000000", "-1000000", "6719", "1"},
547+
548+
{"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
549+
547550
{
548551
"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
549552
"298472983472983471903246121093472394872319615612417471234712061",
550553
"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
551554
"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
552555
},
553556
// test case for issue 8822
557+
{
558+
"11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
559+
"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
560+
"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
561+
"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
562+
},
554563
{
555564
"-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
556565
"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
557566
"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
558567
"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
559568
},
569+
570+
// test cases for issue 13907
571+
{"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
572+
{"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
573+
{"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
574+
{"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
560575
}
561576

562577
func TestExp(t *testing.T) {
@@ -584,7 +599,7 @@ func TestExp(t *testing.T) {
584599
t.Errorf("#%d: %v is not normalized", i, *z1)
585600
}
586601
if z1.Cmp(out) != 0 {
587-
t.Errorf("#%d: got %s want %s", i, z1, out)
602+
t.Errorf("#%d: got %x want %x", i, z1, out)
588603
}
589604

590605
if m == nil {
@@ -593,7 +608,7 @@ func TestExp(t *testing.T) {
593608
m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
594609
z2 := new(Int).Exp(x, y, m)
595610
if z2.Cmp(z1) != 0 {
596-
t.Errorf("#%d: got %s want %s", i, z2, z1)
611+
t.Errorf("#%d: got %x want %x", i, z2, z1)
597612
}
598613
}
599614
}
@@ -1369,6 +1384,14 @@ func TestModSqrt(t *testing.T) {
13691384
t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
13701385
}
13711386
}
1387+
1388+
if testing.Short() && i > 2 {
1389+
break
1390+
}
1391+
}
1392+
1393+
if testing.Short() {
1394+
return
13721395
}
13731396

13741397
// exhaustive test for small values

‎src/cmd/compile/internal/big/nat.go‎

Lines changed: 35 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -213,25 +213,25 @@ func (z nat) montgomery(x, y, m nat, k Word, n int) nat {
213213
if len(x) != n || len(y) != n || len(m) != n {
214214
panic("math/big: mismatched montgomery number lengths")
215215
}
216-
var c1, c2, c3 Word
217216
z = z.make(n)
218217
z.clear()
218+
var c Word
219219
for i := 0; i < n; i++ {
220220
d := y[i]
221-
c2 = addMulVVW(z, x, d)
221+
c2 := addMulVVW(z, x, d)
222222
t := z[0] * k
223-
c3 = addMulVVW(z, m, t)
223+
c3 := addMulVVW(z, m, t)
224224
copy(z, z[1:])
225-
cx := c1 + c2
225+
cx := c + c2
226226
cy := cx + c3
227227
z[n-1] = cy
228228
if cx < c2 || cy < c3 {
229-
c1 = 1
229+
c = 1
230230
} else {
231-
c1 = 0
231+
c = 0
232232
}
233233
}
234-
if c1 != 0 {
234+
if c != 0 {
235235
subVV(z, z, m)
236236
}
237237
return z
@@ -1056,23 +1056,19 @@ func (z nat) expNNWindowed(x, y, m nat) nat {
10561056
// expNNMontgomery calculates x**y mod m using a fixed, 4-bit window.
10571057
// Uses Montgomery representation.
10581058
func (z nat) expNNMontgomery(x, y, m nat) nat {
1059-
var zz, one, rr, RR nat
1060-
10611059
numWords := len(m)
10621060

10631061
// We want the lengths of x and m to be equal.
1062+
// It is OK if x >= m as long as len(x) == len(m).
10641063
if len(x) > numWords {
1065-
_, rr = rr.div(rr, x, m)
1066-
} else if len(x) < numWords {
1067-
rr = rr.make(numWords)
1068-
rr.clear()
1069-
for i := range x {
1070-
rr[i] = x[i]
1071-
}
1072-
} else {
1073-
rr = x
1064+
_, x = nat(nil).div(nil, x, m)
1065+
// Note: now len(x) <= numWords, not guaranteed ==.
1066+
}
1067+
if len(x) < numWords {
1068+
rr := make(nat, numWords)
1069+
copy(rr, x)
1070+
x = rr
10741071
}
1075-
x = rr
10761072

10771073
// Ideally the precomputations would be performed outside, and reused
10781074
// k0 = -m**-1 mod 2**_W. Algorithm from: Dumas, J.G. "On Newton–Raphson
@@ -1086,17 +1082,16 @@ func (z nat) expNNMontgomery(x, y, m nat) nat {
10861082
k0 = -k0
10871083

10881084
// RR = 2**(2*_W*len(m)) mod m
1089-
RR = RR.setWord(1)
1090-
zz = zz.shl(RR, uint(2*numWords*_W))
1085+
RR := nat(nil).setWord(1)
1086+
zz := nat(nil).shl(RR, uint(2*numWords*_W))
10911087
_, RR = RR.div(RR, zz, m)
10921088
if len(RR) < numWords {
10931089
zz = zz.make(numWords)
10941090
copy(zz, RR)
10951091
RR = zz
10961092
}
10971093
// one = 1, with equal length to that of m
1098-
one = one.make(numWords)
1099-
one.clear()
1094+
one := make(nat, numWords)
11001095
one[0] = 1
11011096

11021097
const n = 4
@@ -1131,6 +1126,23 @@ func (z nat) expNNMontgomery(x, y, m nat) nat {
11311126
}
11321127
// convert to regular number
11331128
zz = zz.montgomery(z, one, m, k0, numWords)
1129+
1130+
// One last reduction, just in case.
1131+
// See golang.org/issue/13907.
1132+
if zz.cmp(m) >= 0 {
1133+
// Common case is m has high bit set; in that case,
1134+
// since zz is the same length as m, there can be just
1135+
// one multiple of m to remove. Just subtract.
1136+
// We think that the subtract should be sufficient in general,
1137+
// so do that unconditionally, but double-check,
1138+
// in case our beliefs are wrong.
1139+
// The div is not expected to be reached.
1140+
zz = zz.sub(zz, m)
1141+
if zz.cmp(m) >= 0 {
1142+
_, zz = nat(nil).div(nil, zz, m)
1143+
}
1144+
}
1145+
11341146
return zz.norm()
11351147
}
11361148

‎src/cmd/compile/internal/big/nat_test.go‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -483,6 +483,12 @@ var expNNTests = []struct {
483483
"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
484484
"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
485485
},
486+
{
487+
"11521922904531591643048817447554701904414021819823889996244743037378330903763518501116638828335352811871131385129455853417360623007349090150042001944696604737499160174391019030572483602867266711107136838523916077674888297896995042968746762200926853379",
488+
"426343618817810911523",
489+
"444747819283133684179",
490+
"42",
491+
},
486492
}
487493

488494
func TestExpNN(t *testing.T) {

0 commit comments

Comments
 (0)