Fixed Point Integer classes lack some math functions and still use float / doubles in some of their underlying operations.
- Dominant language
- Kotlin
- Stars
- 3k
- Forks
- 148
- Avg merge
- 13h 44m
- Merged PRs (30d)
- 1
Description
## 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](http://www.sunshine2k.de/articles/coding/fp/sunfp.html#ch4)
[chmike's implementation of Christophe Meessen's formula](https://github.com/chmike/fpsqrt)
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
```kotlin
println("2 / 4 = ${FInt(2) / FInt(4)}")
println("sqrt(9) = ${sqrt(FInt(9))}")
```
## Code
```kotlin
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 {
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())
//}
```
Contributor guide
No contributing guide indexed for this repository
Research direction
The report does not name repository files or tests; start by locating the existing fixed-point integer classes and the FInt, sqrt, and String.toFInt entry points shown here. Compare their behavior with the stated requirements, then establish coverage for parsing, formatting, arithmetic, and square-root behavior; done means the missing functions are defined and the reported floating-point and 0.9 formatting problems are resolved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- kotlin
- Domain
- game-dev
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100