Repository navigation
Undefined Behaviour in volk_32f_invsqrt_32f #686
Description
Activity
This is: Wikipedia fast inverse square root
It is sometimes called John Carmack reverse because of its use in Q3A.Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF
It is an approximation. It works. It is a hack.
Since this is actually a floating point operation, I suggest to ignore this specific error.
I suspect the signed integer overflow occurs because the input is negative. So this could just be a case where the test input (uniformly distributed floats in the range -1 .. +1) doesn't make sense.
As long as the output signature is
32f, roots of negative values do not exist.The C reference for sqrt says:
+-0should return the input value- Values smaller
+-0are NaN. SinceNaN == NaNisfalse, such input should make the test fail.
According to
https://en.wikipedia.org/wiki/Fast_inverse_square_root.. the way to avoid undefined behaviour is to use std::bit_cast
Modern compilers are much more likely than older ones to generate crazy code for undefined behavior; unclear if this is actually a problem here.
According to https://en.wikipedia.org/wiki/Fast_inverse_square_root
.. the way to avoid undefined behaviour is to use std::bit_cast
Modern compilers are much more likely than older ones to generate crazy code for undefined behavior; unclear if this is actually a problem here.
Unfortunately, the kernels as well as the library itself are written in C, unlike all the test code. Thus, we can't use
std::bit_cast. There seem to be hacks according to SO. If available, we probably want to use CPU FPUs for the task anyways, or their vector equivalent.This function is probably a good candidate to implement a test with the new googletest based CI, where we implement a naive invsqrt and compare against this result. As long as the result is approximately equal, we know the compiler didn't start to mess with our hack.
This looks fixed by #811 (merged in January): the generic
Q_rsqrtpath now does the magic-number step onuint32_t(0x5f3759df - (conv.u >> 1)), so there is no signed overflow any more. Maybe this can be closed?
UBSAN shows the following Undefined Behaviour in volk_32f_invsqrt_32f:
/home/argilo/git/volk/kernels/volk/volk_32f_invsqrt_32f.h:71:22: runtime error: signed integer overflow: 1597463007 - -569061536 cannot be represented in type 'int'This is the problematic line:
volk/kernels/volk/volk_32f_invsqrt_32f.h
Line 71 in e853e9b