Converting big.Int to [2]int64, vice-versa and two's complement-CodePudding

I am trying to convert Go big.Int, which will represent a 128-bit integer to [2]int64. The idea is to be able to match Rust's i128::to_le_bytes(), which encodes 128-bit signed integer into little-endian byte order. The example matches Rust's i128::to_le_bytes(). Whenever I try to convert it back to big.Int, I do not get the same value. Is there any bit lost when doing the initial right shift? Thanks.

package main
 
import (
    "encoding/binary"
    "fmt"
    "math/big"
)
 
func main() {
    initial := new(big.Int)
    initial.SetString("-42", 10)
 
    value, _ := new(big.Int).SetString("-42", 10)
 
    var result [2]int64
 
    result[0] = value.Int64()
    result[1] = value.Rsh(value, 64).Int64()
 
    leRepresentation := make([]byte, 16)
 
    binary.LittleEndian.PutUint64(leRepresentation[:8], uint64(result[0]))
    binary.LittleEndian.PutUint64(leRepresentation[8:], uint64(result[1]))
 
    fmt.Println(leRepresentation)
 
    fmt.Println(result)
 
    reverse := big.NewInt(result[1])
    reverse.Lsh(reverse, 64)
    reverse.Add(reverse, big.NewInt(result[0]))
 
    fmt.Println(reverse.String())
 
    fmt.Println(initial.String() == reverse.String())
}

CodePudding user response：

There are a number of problems here:

value cannot be represented by an int64, so the result of value.Int64() is undefined.

Your lower bits are not taking into account the signed result of Int64, so you could be adding a negative number to the result. You need to use a uint64 (or at at least convert it before adding it to the big.Int).

You are mutating value in the Rsh method, so the comparison at the end would fail even if the value were recreated correctly. Create a new big.Int to store the original value if you want to compare it.

If you want a raw data representation for the big.Int with exactly 128bits, you can use the FillBytes method. We can take that big-endian data and build the 2 64bit values like so:

b := make([]byte, 16)
value.FillBytes(b)  

var result [2]uint64
result[0] = binary.BigEndian.Uint64(b[:8])
result[1] = binary.BigEndian.Uint64(b[8:])

Now that the byte order is fixed, add the sign bit to the result. In order to make this work like an int128 however, we need to use two's compliment to set the sign

const sign = uint64(1 << 63)
if value.Sign() < 0 {
    // convert the unsigned value to two's compliment
    result[0] = ^result[0]
    result[1] = ^result[1]

    result[1]  
    // check for carry
    if result[1] == 0 {
        result[0]  
    }
}

To create a new big.Int, reverse the entire process:

neg := uint128[0]&sign != 0
if neg {
    // reverse the two's compliment
    if uint128[1] == 0 {
        uint128[0]--
    }
    uint128[1]--

    uint128[0] = ^uint128[0]
    uint128[1] = ^uint128[1]
}

b := make([]byte, 16)
binary.BigEndian.PutUint64(b[:8], uint128[0])
binary.BigEndian.PutUint64(b[8:], uint128[1])

result := new(big.Int).SetBytes(b)
if neg {
    result.Neg(result)
}

An example testing a number of key values: https://go.dev/play/p/E1E-5CilFlr

Because the output is written as an unsigned value, if it's possible to start with values > MaxInt128, you should also add a check to make sure you're not overflowing the signed value. Storing these as [2]int64 is a lot messier because we need uint64 values for the bitwise operations, and we need to make sure the int64 values aren't rolled over via their own two's compliment. In that case it's easier to convert the [2]int64 to and from [2]uint64 around the given functions.