korlibs / korlibs/korge

Fixed Point Integer classes lack some math functions and still use float / doubles in some of their underlying operations.

Open
#2,125 0 comments 1 reaction 0 assignees View on GitHub
enhancement
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.