korlibs
Fixed Point Integer classes lack some math functions and still use float / doubles in some of their underlying operations.
Introduction
Float / Double calculations are unreliable in many cases because they are often only locally deterministic. Meaning that two computers may provide different results when doing lots of floating point math. The reason people might find this important is because in some networking architectures simulations are run locally and only 'actions' are broadcast to other clients, requiring multiple simulations to match 1:1. This kind of networking architecture is used in some fighting games / RTS games and other genres, and is referred to as "Deterministic lockstep"
To achieve "deterministic lockstep", one solution is by refactoring away any floating point calculations and 'fake' them with integers, also known as Fixed Point Integers. (FP Integer)
Korlibs has some FP Integer classes but they were secretly using doubles under the hood in certain cases, as well as having some minor bugs. (eg.: "0.9".toFixedLong() printing "0.0" instead of "0.9"), this threw me for a loop for a bit, so I decided to try and look for other implementations.
soywiz recommended I post the implementation here to avoid 'losing' it in the messages on Discord, so here is the snippet. The snippet may require some cleanup.
References and notes:
Eventually I implemented a basic FP Integer and square root function, the implementations are based on: Sunshine's article on FP Integer calculations chmike's implementation of Christophe Meessen's formula
There are additional trigonometric functions and other methods that are not implemented yet as I did not need them.
Some clarification:
fracNum refers to the number of 'fraction' bits (not digits)
MASK_FRAC_BITS is currently hardcoded (it should have fracNum amount of bits set on the right side)
Therefore for a 26.6 FP Integer the FRAC bits mask should be 00000000000000000000000000111111 = 0x3F
MASK_INT_BITS is currently hardcoded (it should have 32-fracNum amount of bits set on the left side)
Therefore for a 26.6 FP Integer the INT bits mask should be 11111111111111111111111111000000 = 0xFFFFFFC0
The big commented chunk is a square root calculation for 16.16 FP Int numbers, but is left in for archival purposes. It is rendered obsolete by the non-commented sqrt64() and sqrt() functions.
Example Usage
println("2 / 4 = ${FInt(2) / FInt(4)}")
println("sqrt(9) = ${sqrt(FInt(9))}")
Code
package utils
import kotlin.jvm.*
/**
* Fixed point class, to handle decimal values with a fixed precision.
* @param[raw] represents a scaled value (already representing decimal)
*/
@JvmInline
value class FInt private constructor(val raw: Int) : Comparable<FInt> {
companion object {
val fracNum = 6
val ONE = 1 shl fracNum
val MASK_FRAC_BITS = 0x00003F //Fracnum # bits active on the right side
val MASK_INT_BITS = 0xFFFFFFC0 //Fracnum # bits active on the left side
operator fun invoke(x: Int) = FInt(x shl fracNum)
operator fun invoke(x: Long) = FInt(x.toInt() shl fracNum)
operator fun invoke(x: String): FInt {
if (x.contains('.')) {
val split = x.split('.', limit = 2)
var intValue = split[0].toInt() shl fracNum
var decValue = split[1].toInt()
val decDigits = split[1].length
decValue = decValue * ONE / ipow(10, decDigits)
if (decValue < 0) {
intValue -= ONE
decValue = ONE - decValue
}
intValue = intValue or (decValue and MASK_FRAC_BITS)
return FInt(intValue)
} else {
return FInt(x.toInt() shl fracNum)
}
}
fun fromRaw(x: Int) = FInt(x)
fun fromRaw(x: Long) = FInt(x.toInt())
private fun ipow(base: Int, exp: Int): Int {
var base = base
var exp = exp
var result = 1
while (exp != 0) {
if ((exp and 1) == 1) result *= base
exp = exp shr 1
base *= base
}
return result
}
}
operator fun plus(o: FInt) = FInt(raw + o.raw)
operator fun minus(o: FInt) = FInt(raw - o.raw)
operator fun times(o: FInt) = FInt(((raw.toLong() * o.raw) shr fracNum).toInt())
operator fun div(o: FInt) = FInt(((raw.toLong() shl fracNum) / o.raw).toInt())
override fun compareTo(other: FInt): Int = raw.compareTo(other.raw)
override fun toString(): String {
val sb = StringBuilder()
var frac = raw and MASK_FRAC_BITS
var int = (raw.toLong() and MASK_INT_BITS).toInt()
var isNegativeWithFracPart = false
if (int < 0 && frac != 0) {
int += ONE
isNegativeWithFracPart = true
if (int == 0) sb.append("-")
}
sb.append((int shr fracNum))
if (frac != 0) {
sb.append(".")
if (isNegativeWithFracPart) frac = ONE - frac
while (frac > 0) {
frac *= 10
sb.append('0' + (frac shr fracNum))
frac = frac and ((1 shl fracNum) - 1)
}
}
return sb.toString()
}
}
fun Int.minus(o: FInt) = FInt(this) - o
fun FInt.toDouble() = (raw.toLong() / FInt.ONE).toDouble()
fun abs(x: FInt) = if (x.raw >= 0) x else FInt(0) - x
fun sqrt32(x: Int): Int {
var b = 1 shl 30
var q = 0
var r = x
while (b > r) b = b shr 2
while (b > 0) {
var t = q +b;
var q = q shr 1
if (r >= t) {
r -= t;
q += b;
}
b = b shr 2
}
return q;
}
fun sqrt64(x: Long): Long {
var b = 1L shl 62
var q = 0L
var r = x
while (b > r) b = b shr 2
while (b > 0) {
val t = q + b
q = q shr 1
if (r >= t) {
r -= t
q += b
}
b = b shr 2
}
return q
}
//Calculates the square root of an arbitrary fixed integer number
fun sqrt(x: FInt): FInt = FInt.fromRaw(sqrt64(x.raw.toLong() shl FInt.fracNum))
fun Long.toFInt() = FInt(this)
fun Int.toFInt() = FInt(this)
fun String.toFInt() = FInt(this)
//Sqrt function for 16bit Fixed Integer -> 16bitFixed Integer.
//Rendered obsolete by the other sqrt() and sqrt64() functions
//fun sqrt(x: FInt): FInt {
// var t: ULong
// var r = x.raw.toULong()
// var q = 0UL
// var b = 0x40000000UL
// if (r < 0x40000200UL) {
// while (b != 0x40UL) {
// t = q + b
// if (r >= t) {
// r -= t
// q = t + b // equivalent to q += 2*b
// }
// r = r shl 1
// b = b shr 1
// }
// q = q shr 8
// return FInt.fromRaw(q.toInt())
// }
// while (b > 0x40UL) {
// t = q + b
// if (r >= t) {
// r -= t
// q = t + b // equivalent to q += 2*b
// }
// if ((r and 0x80000000UL) != 0UL) {
// q = q shr 1
// b = b shr 1
// r = r shr 1
// while (b > 0x20UL) {
// t = q + b
// if (r >= t) {
// r -= t
// q = t + b
// }
// r = r shl 11
// b = b shr 1
// }
// q = q shr 7
// return FInt.fromRaw(q.toInt())
// }
// r = r shl 1
// b = b shr 1
// }
// q = q shr 8
// return FInt.fromRaw(q.toInt())
//}
