arith128_test.go

Documentation: go.mongodb.org/mongo-driver/internal/rand

     1  // Copied from https://cs.opensource.google/go/x/exp/+/24438e51023af3bfc1db8aed43c1342817e8cfcd:rand/arith128_test.go
     2  
     3  // Copyright 2017 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package rand
     8  
     9  import (
    10  	"math/big"
    11  	"math/rand"
    12  	"testing"
    13  )
    14  
    15  var bigMaxUint64 = big.NewInt(0).SetUint64(maxUint64)
    16  
    17  func bigInt(xHi, xLo uint64) *big.Int {
    18  	b := big.NewInt(0).SetUint64(xHi)
    19  	b.Lsh(b, 64)
    20  	b.Or(b, big.NewInt(0).SetUint64(xLo))
    21  	return b
    22  }
    23  
    24  func splitBigInt(b *big.Int) (outHi, outLo uint64) {
    25  	outHi = big.NewInt(0).Rsh(b, 64).Uint64()
    26  	outLo = big.NewInt(0).And(b, bigMaxUint64).Uint64()
    27  	return
    28  }
    29  
    30  func bigMulMod128bits(xHi, xLo, yHi, yLo uint64) (outHi, outLo uint64) {
    31  	bigX := bigInt(xHi, xLo)
    32  	bigY := bigInt(yHi, yLo)
    33  	return splitBigInt(bigX.Mul(bigX, bigY))
    34  }
    35  
    36  func bigAddMod128bits(xHi, xLo, yHi, yLo uint64) (outHi, outLo uint64) {
    37  	bigX := bigInt(xHi, xLo)
    38  	bigY := bigInt(yHi, yLo)
    39  	return splitBigInt(bigX.Add(bigX, bigY))
    40  }
    41  
    42  type arithTest struct {
    43  	xHi, xLo uint64
    44  }
    45  
    46  const (
    47  	iLo = increment & maxUint64
    48  	iHi = (increment >> 64) & maxUint64
    49  )
    50  
    51  var arithTests = []arithTest{
    52  	{0, 0},
    53  	{0, 1},
    54  	{1, 0},
    55  	{0, maxUint64},
    56  	{maxUint64, 0},
    57  	{maxUint64, maxUint64},
    58  	// Randomly generated 64-bit integers.
    59  	{3757956613005209672, 17983933746665545631},
    60  	{511324141977587414, 5626651684620191081},
    61  	{1534313104606153588, 2415006486399353367},
    62  	{6873586429837825902, 13854394671140464137},
    63  	{6617134480561088940, 18421520694158684312},
    64  }
    65  
    66  func TestPCGAdd(t *testing.T) {
    67  	for i, test := range arithTests {
    68  		p := &PCGSource{
    69  			low:  test.xLo,
    70  			high: test.xHi,
    71  		}
    72  		p.add()
    73  		expectHi, expectLo := bigAddMod128bits(test.xHi, test.xLo, iHi, iLo)
    74  		if p.low != expectLo || p.high != expectHi {
    75  			t.Errorf("%d: got hi=%d lo=%d; expect hi=%d lo=%d", i, p.high, p.low, expectHi, expectLo)
    76  		}
    77  	}
    78  }
    79  
    80  const (
    81  	mLo = multiplier & maxUint64
    82  	mHi = (multiplier >> 64) & maxUint64
    83  )
    84  
    85  func TestPCGMultiply(t *testing.T) {
    86  	for i, test := range arithTests {
    87  		p := &PCGSource{
    88  			low:  test.xLo,
    89  			high: test.xHi,
    90  		}
    91  		p.multiply()
    92  		expectHi, expectLo := bigMulMod128bits(test.xHi, test.xLo, mHi, mLo)
    93  		if p.low != expectLo || p.high != expectHi {
    94  			t.Errorf("%d: got hi=%d lo=%d; expect hi=%d lo=%d", i, p.high, p.low, expectHi, expectLo)
    95  		}
    96  	}
    97  }
    98  
    99  func TestPCGMultiplyLong(t *testing.T) {
   100  	if testing.Short() {
   101  		return
   102  	}
   103  	for i := 0; i < 1e6; i++ {
   104  		low := rand.Uint64()
   105  		high := rand.Uint64()
   106  		p := &PCGSource{
   107  			low:  low,
   108  			high: high,
   109  		}
   110  		p.multiply()
   111  		expectHi, expectLo := bigMulMod128bits(high, low, mHi, mLo)
   112  		if p.low != expectLo || p.high != expectHi {
   113  			t.Fatalf("%d: (%d,%d): got hi=%d lo=%d; expect hi=%d lo=%d", i, high, low, p.high, p.low, expectHi, expectLo)
   114  		}
   115  	}
   116  }
   117  
   118  func BenchmarkPCGMultiply(b *testing.B) {
   119  	low := rand.Uint64()
   120  	high := rand.Uint64()
   121  	p := &PCGSource{
   122  		low:  low,
   123  		high: high,
   124  	}
   125  	for i := 0; i < b.N; i++ {
   126  		p.multiply()
   127  	}
   128  }
   129
View as plain text