123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697 |
- // Copyright 2009 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.
- package big
- import (
- "fmt"
- "internal/testenv"
- "math/bits"
- "math/rand"
- "strings"
- "testing"
- )
- var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race")
- type funVV func(z, x, y []Word) (c Word)
- type argVV struct {
- z, x, y nat
- c Word
- }
- var sumVV = []argVV{
- {},
- {nat{0}, nat{0}, nat{0}, 0},
- {nat{1}, nat{1}, nat{0}, 0},
- {nat{0}, nat{_M}, nat{1}, 1},
- {nat{80235}, nat{12345}, nat{67890}, 0},
- {nat{_M - 1}, nat{_M}, nat{_M}, 1},
- {nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
- {nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
- {nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
- }
- func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
- z := make(nat, len(a.z))
- c := f(z, a.x, a.y)
- for i, zi := range z {
- if zi != a.z[i] {
- t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
- break
- }
- }
- if c != a.c {
- t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
- }
- }
- func TestFunVV(t *testing.T) {
- for _, a := range sumVV {
- arg := a
- testFunVV(t, "addVV_g", addVV_g, arg)
- testFunVV(t, "addVV", addVV, arg)
- arg = argVV{a.z, a.y, a.x, a.c}
- testFunVV(t, "addVV_g symmetric", addVV_g, arg)
- testFunVV(t, "addVV symmetric", addVV, arg)
- arg = argVV{a.x, a.z, a.y, a.c}
- testFunVV(t, "subVV_g", subVV_g, arg)
- testFunVV(t, "subVV", subVV, arg)
- arg = argVV{a.y, a.z, a.x, a.c}
- testFunVV(t, "subVV_g symmetric", subVV_g, arg)
- testFunVV(t, "subVV symmetric", subVV, arg)
- }
- }
- // Always the same seed for reproducible results.
- var rnd = rand.New(rand.NewSource(0))
- func rndW() Word {
- return Word(rnd.Int63()<<1 | rnd.Int63n(2))
- }
- func rndV(n int) []Word {
- v := make([]Word, n)
- for i := range v {
- v[i] = rndW()
- }
- return v
- }
- var benchSizes = []int{1, 2, 3, 4, 5, 1e1, 1e2, 1e3, 1e4, 1e5}
- func BenchmarkAddVV(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- y := rndV(n)
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _W))
- for i := 0; i < b.N; i++ {
- addVV(z, x, y)
- }
- })
- }
- }
- func BenchmarkSubVV(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- y := rndV(n)
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _W))
- for i := 0; i < b.N; i++ {
- subVV(z, x, y)
- }
- })
- }
- }
- type funVW func(z, x []Word, y Word) (c Word)
- type argVW struct {
- z, x nat
- y Word
- c Word
- }
- var sumVW = []argVW{
- {},
- {nil, nil, 2, 2},
- {nat{0}, nat{0}, 0, 0},
- {nat{1}, nat{0}, 1, 0},
- {nat{1}, nat{1}, 0, 0},
- {nat{0}, nat{_M}, 1, 1},
- {nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
- {nat{585}, nat{314}, 271, 0},
- }
- var lshVW = []argVW{
- {},
- {nat{0}, nat{0}, 0, 0},
- {nat{0}, nat{0}, 1, 0},
- {nat{0}, nat{0}, 20, 0},
- {nat{_M}, nat{_M}, 0, 0},
- {nat{_M << 1 & _M}, nat{_M}, 1, 1},
- {nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
- {nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
- {nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
- {nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
- }
- var rshVW = []argVW{
- {},
- {nat{0}, nat{0}, 0, 0},
- {nat{0}, nat{0}, 1, 0},
- {nat{0}, nat{0}, 20, 0},
- {nat{_M}, nat{_M}, 0, 0},
- {nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
- {nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
- {nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
- {nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
- {nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
- }
- func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
- z := make(nat, len(a.z))
- c := f(z, a.x, a.y)
- for i, zi := range z {
- if zi != a.z[i] {
- t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
- break
- }
- }
- if c != a.c {
- t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
- }
- }
- func testFunVWext(t *testing.T, msg string, f funVW, f_g funVW, a argVW) {
- // using the result of addVW_g/subVW_g as golden
- z_g := make(nat, len(a.z))
- c_g := f_g(z_g, a.x, a.y)
- c := f(a.z, a.x, a.y)
- for i, zi := range a.z {
- if zi != z_g[i] {
- t.Errorf("%s\n\tgot z[%d] = %#x; want %#x", msg, i, zi, z_g[i])
- break
- }
- }
- if c != c_g {
- t.Errorf("%s\n\tgot c = %#x; want %#x", msg, c, c_g)
- }
- }
- func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
- return func(z, x []Word, s Word) (c Word) {
- return f(z, x, uint(s))
- }
- }
- func TestFunVW(t *testing.T) {
- for _, a := range sumVW {
- arg := a
- testFunVW(t, "addVW_g", addVW_g, arg)
- testFunVW(t, "addVW", addVW, arg)
- arg = argVW{a.x, a.z, a.y, a.c}
- testFunVW(t, "subVW_g", subVW_g, arg)
- testFunVW(t, "subVW", subVW, arg)
- }
- shlVW_g := makeFunVW(shlVU_g)
- shlVW := makeFunVW(shlVU)
- for _, a := range lshVW {
- arg := a
- testFunVW(t, "shlVU_g", shlVW_g, arg)
- testFunVW(t, "shlVU", shlVW, arg)
- }
- shrVW_g := makeFunVW(shrVU_g)
- shrVW := makeFunVW(shrVU)
- for _, a := range rshVW {
- arg := a
- testFunVW(t, "shrVU_g", shrVW_g, arg)
- testFunVW(t, "shrVU", shrVW, arg)
- }
- }
- // Construct a vector comprising the same word, usually '0' or 'maximum uint'
- func makeWordVec(e Word, n int) []Word {
- v := make([]Word, n)
- for i := range v {
- v[i] = e
- }
- return v
- }
- // Extended testing to addVW and subVW using various kinds of input data.
- // We utilize the results of addVW_g and subVW_g as golden reference to check
- // correctness.
- func TestFunVWExt(t *testing.T) {
- // 32 is the current threshold that triggers an optimized version of
- // calculation for large-sized vector, ensure we have sizes around it tested.
- var vwSizes = []int{0, 1, 3, 4, 5, 8, 9, 23, 31, 32, 33, 34, 35, 36, 50, 120}
- for _, n := range vwSizes {
- // vector of random numbers, using the result of addVW_g/subVW_g as golden
- x := rndV(n)
- y := rndW()
- z := make(nat, n)
- arg := argVW{z, x, y, 0}
- testFunVWext(t, "addVW, random inputs", addVW, addVW_g, arg)
- testFunVWext(t, "subVW, random inputs", subVW, subVW_g, arg)
- // vector of random numbers, but make 'x' and 'z' share storage
- arg = argVW{x, x, y, 0}
- testFunVWext(t, "addVW, random inputs, sharing storage", addVW, addVW_g, arg)
- testFunVWext(t, "subVW, random inputs, sharing storage", subVW, subVW_g, arg)
- // vector of maximum uint, to force carry flag set in each 'add'
- y = ^Word(0)
- x = makeWordVec(y, n)
- arg = argVW{z, x, y, 0}
- testFunVWext(t, "addVW, vector of max uint", addVW, addVW_g, arg)
- // vector of '0', to force carry flag set in each 'sub'
- x = makeWordVec(0, n)
- arg = argVW{z, x, 1, 0}
- testFunVWext(t, "subVW, vector of zero", subVW, subVW_g, arg)
- }
- }
- type argVU struct {
- d []Word // d is a Word slice, the input parameters x and z come from this array.
- l uint // l is the length of the input parameters x and z.
- xp uint // xp is the starting position of the input parameter x, x := d[xp:xp+l].
- zp uint // zp is the starting position of the input parameter z, z := d[zp:zp+l].
- s uint // s is the shift number.
- r []Word // r is the expected output result z.
- c Word // c is the expected return value.
- m string // message.
- }
- var argshlVUIn = []Word{1, 2, 4, 8, 16, 32, 64, 0, 0, 0}
- var argshlVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
- var argshlVUr1 = []Word{2, 4, 8, 16, 32, 64, 128}
- var argshlVUrWm1 = []Word{1 << (_W - 1), 0, 1, 2, 4, 8, 16}
- var argshlVU = []argVU{
- // test cases for shlVU
- {[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0}, 7, 0, 0, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "complete overlap of shlVU"},
- {[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0, 0, 0, 0}, 7, 0, 3, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "partial overlap by half of shlVU"},
- {[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0, 0, 0, 0, 0, 0, 0}, 7, 0, 6, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "partial overlap by 1 Word of shlVU"},
- {[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0, 0, 0, 0, 0, 0, 0, 0}, 7, 0, 7, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "no overlap of shlVU"},
- // additional test cases with shift values of 0, 1 and (_W-1)
- {argshlVUIn, 7, 0, 0, 0, argshlVUr0, 0, "complete overlap of shlVU and shift of 0"},
- {argshlVUIn, 7, 0, 0, 1, argshlVUr1, 0, "complete overlap of shlVU and shift of 1"},
- {argshlVUIn, 7, 0, 0, _W - 1, argshlVUrWm1, 32, "complete overlap of shlVU and shift of _W - 1"},
- {argshlVUIn, 7, 0, 1, 0, argshlVUr0, 0, "partial overlap by 6 Words of shlVU and shift of 0"},
- {argshlVUIn, 7, 0, 1, 1, argshlVUr1, 0, "partial overlap by 6 Words of shlVU and shift of 1"},
- {argshlVUIn, 7, 0, 1, _W - 1, argshlVUrWm1, 32, "partial overlap by 6 Words of shlVU and shift of _W - 1"},
- {argshlVUIn, 7, 0, 2, 0, argshlVUr0, 0, "partial overlap by 5 Words of shlVU and shift of 0"},
- {argshlVUIn, 7, 0, 2, 1, argshlVUr1, 0, "partial overlap by 5 Words of shlVU and shift of 1"},
- {argshlVUIn, 7, 0, 2, _W - 1, argshlVUrWm1, 32, "partial overlap by 5 Words of shlVU abd shift of _W - 1"},
- {argshlVUIn, 7, 0, 3, 0, argshlVUr0, 0, "partial overlap by 4 Words of shlVU and shift of 0"},
- {argshlVUIn, 7, 0, 3, 1, argshlVUr1, 0, "partial overlap by 4 Words of shlVU and shift of 1"},
- {argshlVUIn, 7, 0, 3, _W - 1, argshlVUrWm1, 32, "partial overlap by 4 Words of shlVU and shift of _W - 1"},
- }
- var argshrVUIn = []Word{0, 0, 0, 1, 2, 4, 8, 16, 32, 64}
- var argshrVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
- var argshrVUr1 = []Word{0, 1, 2, 4, 8, 16, 32}
- var argshrVUrWm1 = []Word{4, 8, 16, 32, 64, 128, 0}
- var argshrVU = []argVU{
- // test cases for shrVU
- {[]Word{0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 1, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "complete overlap of shrVU"},
- {[]Word{0, 0, 0, 0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 4, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "partial overlap by half of shrVU"},
- {[]Word{0, 0, 0, 0, 0, 0, 0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 7, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "partial overlap by 1 Word of shrVU"},
- {[]Word{0, 0, 0, 0, 0, 0, 0, 0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 8, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "no overlap of shrVU"},
- // additional test cases with shift values of 0, 1 and (_W-1)
- {argshrVUIn, 7, 3, 3, 0, argshrVUr0, 0, "complete overlap of shrVU and shift of 0"},
- {argshrVUIn, 7, 3, 3, 1, argshrVUr1, 1 << (_W - 1), "complete overlap of shrVU and shift of 1"},
- {argshrVUIn, 7, 3, 3, _W - 1, argshrVUrWm1, 2, "complete overlap of shrVU and shift of _W - 1"},
- {argshrVUIn, 7, 3, 2, 0, argshrVUr0, 0, "partial overlap by 6 Words of shrVU and shift of 0"},
- {argshrVUIn, 7, 3, 2, 1, argshrVUr1, 1 << (_W - 1), "partial overlap by 6 Words of shrVU and shift of 1"},
- {argshrVUIn, 7, 3, 2, _W - 1, argshrVUrWm1, 2, "partial overlap by 6 Words of shrVU and shift of _W - 1"},
- {argshrVUIn, 7, 3, 1, 0, argshrVUr0, 0, "partial overlap by 5 Words of shrVU and shift of 0"},
- {argshrVUIn, 7, 3, 1, 1, argshrVUr1, 1 << (_W - 1), "partial overlap by 5 Words of shrVU and shift of 1"},
- {argshrVUIn, 7, 3, 1, _W - 1, argshrVUrWm1, 2, "partial overlap by 5 Words of shrVU and shift of _W - 1"},
- {argshrVUIn, 7, 3, 0, 0, argshrVUr0, 0, "partial overlap by 4 Words of shrVU and shift of 0"},
- {argshrVUIn, 7, 3, 0, 1, argshrVUr1, 1 << (_W - 1), "partial overlap by 4 Words of shrVU and shift of 1"},
- {argshrVUIn, 7, 3, 0, _W - 1, argshrVUrWm1, 2, "partial overlap by 4 Words of shrVU and shift of _W - 1"},
- }
- func testShiftFunc(t *testing.T, f func(z, x []Word, s uint) Word, a argVU) {
- // work on copy of a.d to preserve the original data.
- b := make([]Word, len(a.d))
- copy(b, a.d)
- z := b[a.zp : a.zp+a.l]
- x := b[a.xp : a.xp+a.l]
- c := f(z, x, a.s)
- for i, zi := range z {
- if zi != a.r[i] {
- t.Errorf("d := %v, %s(d[%d:%d], d[%d:%d], %d)\n\tgot z[%d] = %#x; want %#x", a.d, a.m, a.zp, a.zp+a.l, a.xp, a.xp+a.l, a.s, i, zi, a.r[i])
- break
- }
- }
- if c != a.c {
- t.Errorf("d := %v, %s(d[%d:%d], d[%d:%d], %d)\n\tgot c = %#x; want %#x", a.d, a.m, a.zp, a.zp+a.l, a.xp, a.xp+a.l, a.s, c, a.c)
- }
- }
- func TestShiftOverlap(t *testing.T) {
- for _, a := range argshlVU {
- arg := a
- testShiftFunc(t, shlVU, arg)
- }
- for _, a := range argshrVU {
- arg := a
- testShiftFunc(t, shrVU, arg)
- }
- }
- func TestIssue31084(t *testing.T) {
- // compute 10^n via 5^n << n.
- const n = 165
- p := nat(nil).expNN(nat{5}, nat{n}, nil)
- p = p.shl(p, n)
- got := string(p.utoa(10))
- want := "1" + strings.Repeat("0", n)
- if got != want {
- t.Errorf("shl(%v, %v)\n\tgot %s\n\twant %s", p, n, got, want)
- }
- }
- const issue42838Value = "159309191113245227702888039776771180559110455519261878607388585338616290151305816094308987472018268594098344692611135542392730712890625"
- func TestIssue42838(t *testing.T) {
- const s = 192
- z, _, _, _ := nat(nil).scan(strings.NewReader(issue42838Value), 0, false)
- z = z.shl(z, s)
- got := string(z.utoa(10))
- want := "1" + strings.Repeat("0", s)
- if got != want {
- t.Errorf("shl(%v, %v)\n\tgot %s\n\twant %s", z, s, got, want)
- }
- }
- func BenchmarkAddVW(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- y := rndW()
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _S))
- for i := 0; i < b.N; i++ {
- addVW(z, x, y)
- }
- })
- }
- }
- // Benchmarking addVW using vector of maximum uint to force carry flag set
- func BenchmarkAddVWext(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- y := ^Word(0)
- x := makeWordVec(y, n)
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _S))
- for i := 0; i < b.N; i++ {
- addVW(z, x, y)
- }
- })
- }
- }
- func BenchmarkSubVW(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- y := rndW()
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _S))
- for i := 0; i < b.N; i++ {
- subVW(z, x, y)
- }
- })
- }
- }
- // Benchmarking subVW using vector of zero to force carry flag set
- func BenchmarkSubVWext(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := makeWordVec(0, n)
- y := Word(1)
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _S))
- for i := 0; i < b.N; i++ {
- subVW(z, x, y)
- }
- })
- }
- }
- type funVWW func(z, x []Word, y, r Word) (c Word)
- type argVWW struct {
- z, x nat
- y, r Word
- c Word
- }
- var prodVWW = []argVWW{
- {},
- {nat{0}, nat{0}, 0, 0, 0},
- {nat{991}, nat{0}, 0, 991, 0},
- {nat{0}, nat{_M}, 0, 0, 0},
- {nat{991}, nat{_M}, 0, 991, 0},
- {nat{0}, nat{0}, _M, 0, 0},
- {nat{991}, nat{0}, _M, 991, 0},
- {nat{1}, nat{1}, 1, 0, 0},
- {nat{992}, nat{1}, 1, 991, 0},
- {nat{22793}, nat{991}, 23, 0, 0},
- {nat{22800}, nat{991}, 23, 7, 0},
- {nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
- {nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
- {nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
- {nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
- {nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
- {nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
- {nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
- {nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
- {nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
- {nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
- {nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
- {nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
- }
- func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
- z := make(nat, len(a.z))
- c := f(z, a.x, a.y, a.r)
- for i, zi := range z {
- if zi != a.z[i] {
- t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
- break
- }
- }
- if c != a.c {
- t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
- }
- }
- // TODO(gri) mulAddVWW and divWVW are symmetric operations but
- // their signature is not symmetric. Try to unify.
- type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
- type argWVW struct {
- z nat
- xn Word
- x nat
- y Word
- r Word
- }
- func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
- z := make(nat, len(a.z))
- r := f(z, a.xn, a.x, a.y)
- for i, zi := range z {
- if zi != a.z[i] {
- t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
- break
- }
- }
- if r != a.r {
- t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
- }
- }
- func TestFunVWW(t *testing.T) {
- for _, a := range prodVWW {
- arg := a
- testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
- testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
- if a.y != 0 && a.r < a.y {
- arg := argWVW{a.x, a.c, a.z, a.y, a.r}
- testFunWVW(t, "divWVW", divWVW, arg)
- }
- }
- }
- var mulWWTests = []struct {
- x, y Word
- q, r Word
- }{
- {_M, _M, _M - 1, 1},
- // 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
- }
- func TestMulWW(t *testing.T) {
- for i, test := range mulWWTests {
- q, r := mulWW_g(test.x, test.y)
- if q != test.q || r != test.r {
- t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
- }
- }
- }
- var mulAddWWWTests = []struct {
- x, y, c Word
- q, r Word
- }{
- // TODO(agl): These will only work on 64-bit platforms.
- // {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
- // {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
- {_M, _M, 0, _M - 1, 1},
- {_M, _M, _M, _M, 0},
- }
- func TestMulAddWWW(t *testing.T) {
- for i, test := range mulAddWWWTests {
- q, r := mulAddWWW_g(test.x, test.y, test.c)
- if q != test.q || r != test.r {
- t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
- }
- }
- }
- var divWWTests = []struct {
- x1, x0, y Word
- q, r Word
- }{
- {_M >> 1, 0, _M, _M >> 1, _M >> 1},
- {_M - (1 << (_W - 2)), _M, 3 << (_W - 2), _M, _M - (1 << (_W - 2))},
- }
- const testsNumber = 1 << 16
- func TestDivWW(t *testing.T) {
- i := 0
- for i, test := range divWWTests {
- rec := reciprocalWord(test.y)
- q, r := divWW(test.x1, test.x0, test.y, rec)
- if q != test.q || r != test.r {
- t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
- }
- }
- //random tests
- for ; i < testsNumber; i++ {
- x1 := rndW()
- x0 := rndW()
- y := rndW()
- if x1 >= y {
- continue
- }
- rec := reciprocalWord(y)
- qGot, rGot := divWW(x1, x0, y, rec)
- qWant, rWant := bits.Div(uint(x1), uint(x0), uint(y))
- if uint(qGot) != qWant || uint(rGot) != rWant {
- t.Errorf("#%d got (%x, %x) want (%x, %x)", i, qGot, rGot, qWant, rWant)
- }
- }
- }
- func BenchmarkMulAddVWW(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- z := make([]Word, n+1)
- x := rndV(n)
- y := rndW()
- r := rndW()
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _W))
- for i := 0; i < b.N; i++ {
- mulAddVWW(z, x, y, r)
- }
- })
- }
- }
- func BenchmarkAddMulVVW(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- y := rndW()
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _W))
- for i := 0; i < b.N; i++ {
- addMulVVW(z, x, y)
- }
- })
- }
- }
- func BenchmarkDivWVW(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- y := rndW()
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _W))
- for i := 0; i < b.N; i++ {
- divWVW(z, 0, x, y)
- }
- })
- }
- }
- func BenchmarkNonZeroShifts(b *testing.B) {
- for _, n := range benchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- x := rndV(n)
- s := uint(rand.Int63n(_W-2)) + 1 // avoid 0 and over-large shifts
- z := make([]Word, n)
- b.Run(fmt.Sprint(n), func(b *testing.B) {
- b.SetBytes(int64(n * _W))
- b.Run("shrVU", func(b *testing.B) {
- for i := 0; i < b.N; i++ {
- _ = shrVU(z, x, s)
- }
- })
- b.Run("shlVU", func(b *testing.B) {
- for i := 0; i < b.N; i++ {
- _ = shlVU(z, x, s)
- }
- })
- })
- }
- }
|