/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
#include <stdint.h>
// OSS: https://github.com/chmike/fpsqrt/blob/master/fpsqrt.c#L51
// sqrt_uint32 computes the squrare root of a 32bit integer and returns
// a 32bit integer value. It requires that v is positive.
uint32_t
sqrt_uint32(uint32_t v)
{
uint32_t b = 1 << 30, q = 0, r = v;
while (b > r)
b >>= 2;
while (b > 0)
{
uint32_t t = q + b;
q >>= 1;
if (r >= t)
{
r -= t;
q += b;
}
b >>= 2;
}
return q;
}
// distance_uint32 computes the distance between two coordinates using
// 32bit integers and returns a 32bit integer value.
uint32_t
distance_uint32(
int32_t x1,
int32_t y1,
int32_t x2,
int32_t y2
)
{
uint32_t dx = (x1 > x2 ? x1 - x2 : x2 - x1);
uint32_t dy = (y1 > y2 ? y1 - y2 : y2 - y1);
uint32_t a = dx > dy ? dx : dy;
uint32_t b = dx > dy ? dy : dx;
int i;
uint32_t h;
if (b == 0) return a;
h = 0;
for (i = 8; i >= 0; i--)
{
uint32_t e = (1 << (2 * i));
uint32_t r;
// to get accurate division we as many fixed points as it fits
r = (a << (2 * i));
if ((r >> (2 * i)) != a) continue;
// the division
r = r / b;
// the ratio neet to be fitting to 16bit
if (((r + 1)>>16) == 0)
{
r = r * r >> (2 * i);
r = e + r;
r = sqrt_uint32 (r);
r = b*r;
h = (r + (1 << (i-1))) >> i; // we add 0.5 to round
break;
}
if (i == 0)
{
// ratio is too large anyways
h = a;
break;
}
}
return h;
}
// distance_approx_uint32 computes the distance between two coordinates using
// 32bit integers and returns a 32bit integer value.
uint32_t
distance_approx_uint32(
int32_t x1,
int32_t y1,
int32_t x2,
int32_t y2
)
{
uint32_t dx = (x1 > x2 ? x1 - x2 : x2 - x1);
uint32_t dy = (y1 > y2 ? y1 - y2 : y2 - y1);
uint32_t a = dx > dy ? dy : dx;
uint32_t b = dx > dy ? dx : dy;
// OSS: https://stackoverflow.com/a/26607206/5770014
uint32_t h = b + (345 * a >> 10);
return h;
}
int
main ()
{
uint32_t h;
h = distance_approx_uint32(10, 10, 1000000, 2000);
printf ("The result of distance approximation is: %d\n", h);
h = distance_uint32(10, 10, 1000000, 2000);
printf ("The result of distance calculation is: %d\n", h);
return 0;
}
