Why does my Go implementation of xorshift128+ not produce the same results as JavaScript?

I am trying to implement a PNRG (xorshift128+) that will match when generated on the client (Go) and the server (Node).

Here is the JS code:

function xor128(aT, Gj) {
    var SM = aT;
    var tn = Gj;
    return function() {
        var Fv = SM;
        Fv ^= Fv << 23;
        Fv ^= Fv >> 17;
        var RW = tn;
        Fv ^= RW;
        SM = RW;
        Fv ^= RW >> 26;
        tn = Fv;
        return (SM + tn) % 4294967296;
    };
}

function buildKeyArray() {
    const randomNumberGenerator = xor128(2328399149, 142609045);
    const outputArray = [];

    let results = []
    for (let index = 0; index < 36; index++) {
        const a = randomNumberGenerator()
        results.push(a)
        outputArray.push(a & 255);
    }

    console.log(results)

    return outputArray;
}


const keyArray = buildKeyArray()
console.log(keyArray)

And here is my attempted implementation of the client (Go) code:

type Xor128Generator struct {
    SM int64
    tn int64
}

func NewXor128Generator(aT, Gj int64) *Xor128Generator {
    return &Xor128Generator{SM: aT, tn: Gj}
}

func (x *Xor128Generator) Generate() int64 {
    Fv := x.SM
    Fv ^= Fv << 23
    Fv ^= Fv >> 17
    RW := x.tn
    Fv ^= RW
    x.SM = RW
    Fv ^= RW >> 26
    x.tn = Fv

    result := x.SM + x.tn
    return result
}

func buildKeyArray() ([]int64, []int64) {
    gen := NewXor128Generator(2328399149, 142609045)
    outputArray := make([]int64, 36)

    var results []int64
    for index := 0; index < 36; index++ {
        var a = gen.Generate()
        results = append(results, a)
        outputArray[index] = a & 255
    }
    return results, outputArray
}

func main() {
    values, keyArray := buildKeyArray()
    fmt.Println(values)

    fmt.Println(keyArray)
}

The issue is that my Go implementation is generating different numbers from the xor128 code. I understand this is because of Node making use of 32-bit integers, and Go using 64-bit integers. However how can I fix the Go code so that it will be consistent with the JS code and generate the same numbers on both platforms.

To be clear, the JS code is generating the correct values, and the Go code needs to match.

Go Produces:

[19532156995605555 37868041544647872 3645753149831174622 3914742122792178859 6482499940806067135 -5207728244564407674 -6706392508791742131 8463068253430543312 -8850847552257225555 -5174435155821538382 -5705071601501578122 5373630501739814080 5425966726755816670 -4614015746072156434 -763532337158309354 -6525296991365564020 7693461687529358624 5442354594852915993 826752733575144291 7316642277527303790 -4276413025089434854 -5793540278689307453 5441912080818885102 6631677623209932643 -4988641122236323495 -8214349991732447071 -8825762148124582880 -8133528416753405310 -7995457241030690464 -9107384432430222800 7092317743401552008 7193567733535422658 3242336753115407133 4324214562848624085 6924581763658767475 5051352225382088672]

[51 192 222 171 191 134 77 208 173 178 118 192 222 238 22 140 32 25 99 110 26 195 238 99 89 161 32 130 96 48 136 194 29 213 115 224]

Whereas the same input in JS produce:

[491295795, 1804676012, 3385354351, 2520191736, 2222979160, 1799913174, 2177403719, 2198954679, 1892208726, 2445857146, 2332030108, 3090638876, 3627508608, 3405775416, 1707643167, 1942520827, 2115064167, 1254667045, 2026413111, 2635145295, 2261282668, 1966548985, 2818575144, 2789794800, 2320029362, 3019906560, 3099019638, 2864128632, 2030039371, 2420666380, 2764603533, 1770008048, 1396156547, 1169650895, 879668527, 1983349687]

[51, 172, 111, 248, 88, 214, 71, 183, 86, 122, 156, 28, 128, 56, 31, 251, 103, 37, 55, 79, 108, 249, 40, 240, 178, 0, 118, 120, 75, 12, 141, 240, 131, 207, 47, 183]

You did not provide any example values, and there may be a multiple issues with the code, but I’ll point out the first one I spotted.

Consider the javascript:

Fv ^= Fv << 23;
Fv ^= Fv >> 17;

If the result of Fv << 23 results in the high bit being set, then Fv >> 17 will propagate the sign; it’s probably easier to see this in code (>>> is an Unsigned right shift):

function dec2bin(dec) {
  return (dec >>> 0).toString(2);
}

let Fv = 0b11000000000000000000000000000000
console.log(Fv >> 23, dec2bin(Fv >> 23));
console.log(Fv >>> 23, dec2bin(Fv >>> 23));

The output is:

-128  11111111111111111111111110000000
384   110000000

When you now use the result in the ^= you can see how the sign propagation will have an impact.

In your Go code you are using uint32 throughout; as this is unsigned the shift operations will not propagate the sign, which will lead to differences. Lets compare the use of signed vs unsigned integers:

package main

import "fmt"

type Xor128Generator[T interface{ int32 | uint32 }] struct {
    SM T
    tn T
}

func (x *Xor128Generator[T]) Generate() T {
    Fv := x.SM
    Fv ^= Fv << 23
    Fv ^= Fv >> 17
    RW := x.tn
    Fv ^= RW
    x.SM = RW
    Fv ^= RW >> 26
    x.tn = Fv

    return x.SM + x.tn
}

func main() {
    u := Xor128Generator[uint32]{SM: 65535, tn: 1}
    fmt.Println(u.Generate()) // output: 4286611519

    i := Xor128Generator[int32]{SM: 65535, tn: 1}
    fmt.Println(i.Generate()) // output: 8323135
}

The second result (int32) matches the output of your Javascript (I ran console.log(xor128(65535,1)());).

Ref your last edit. Your Javascript may be “correct” but it’s not doing what you think it is; in Javascript numbers are converted to int32 in order to perform bitwise operations. This means that 2328399149 becomes -1966568147. So you can duplicate the updated Javascript in Go using:

Edit: Changes output from buildKeyArray to []float64 to match Javascript (with int32 you will get some overflows).

package main

import "fmt"

func main() {
    x := 2328399149
    fmt.Printf("%.0f", buildKeyArray(int32(x), 36, 142609045))
}

type Xor128Generator struct {
    SM int32
    tn int32
}

func NewXor128Generator(aT, Gj int32) *Xor128Generator {
    return &Xor128Generator{SM: aT, tn: Gj}
}

func (x *Xor128Generator) Generate() float64 {
    Fv := x.SM
    Fv ^= Fv << 23
    Fv ^= Fv >> 17
    RW := x.tn
    Fv ^= RW
    x.SM = RW
    Fv ^= RW >> 26
    x.tn = Fv

    return float64(x.SM) + float64(x.tn)
}

func buildKeyArray(XorSection int32, max int, Xor128Seed int32) []float64 {
    gen := NewXor128Generator(XorSection, Xor128Seed)
    outputArray := make([]float64, max)

    for index := 0; index < max; index++ {
        outputArray[index] = gen.Generate()
    }

    return outputArray
}

The output matches your Javascript (playground):

[491295795 1804676012 3385354351 2520191736 2222979160 1799913174 2177403719 2198954679 1892208726 2445857146 2332030108 3090638876 3627508608 3405775416 1707643167 1942520827 2115064167 1254667045 2026413111 2635145295 2261282668 1966548985 2818575144 2789794800 2320029362 3019906560 3099019638 2864128632 2030039371 2420666380 2764603533 1770008048 1396156547 1169650895 879668527 1983349687]

However, as you have hopefully realised, this is not using 64-bit integers (so your Javascript may not be as correct as you believe). Javascript numbers are float64’s which mean they cannot store the full range of an int64 (you need BigInt for that).

You cannot just change the size of the variables in Xor128Generator because doing so alters the algorithm (which we had, I believe, already established now matches the javascript).

Suggestion: When debugging something like this start at the base level (e.g. with the output of Generate()😉 once things work at that level then move up to buildKeyArray. Please consider editing your question to reinstate your original code (perhaps with the int32 output) so this question/answer might help others (completely changing the code in the question makes the answer confusion).

Filed under: Kiến thức lập trình - @ 05:09

Thẻ: go

Thiết kế website giá rẻ

Danh mục

Why does my Go implementation of xorshift128+ not produce the same results as JavaScript?