54 lines
987 B
C
54 lines
987 B
C
// SPDX-License-Identifier: ISC
|
|
// this file is directly included by idx.c
|
|
// conversion between hilbert curve distance and x,y values
|
|
|
|
#include <inttypes.h>
|
|
|
|
// rotate/flip a quadrant appropriately
|
|
static void y16t_hilbert_rot(
|
|
uint32_t n,
|
|
uint32_t *x,
|
|
uint32_t *y,
|
|
uint32_t rx,
|
|
uint32_t ry
|
|
) {
|
|
if (ry == 0) {
|
|
if (rx == 1) {
|
|
*x = n-1 - *x;
|
|
*y = n-1 - *y;
|
|
}
|
|
|
|
//Swap x and y
|
|
uint32_t t = *x;
|
|
*x = *y;
|
|
*y = t;
|
|
}
|
|
}
|
|
|
|
__attribute__((pure))
|
|
static uint32_t y16t_hilbert_xy2d(uint32_t n, uint32_t x, uint32_t y) {
|
|
uint32_t rx, ry, s, d=0;
|
|
for (s=n/2; s>0; s/=2) {
|
|
rx = (x & s) > 0;
|
|
ry = (y & s) > 0;
|
|
d += s * s * ((3 * rx) ^ ry);
|
|
y16t_hilbert_rot(n, &x, &y, rx, ry);
|
|
}
|
|
return d;
|
|
}
|
|
|
|
/*
|
|
static void y16t_hilbert_d2xy(uint32_t n, uint32_t d, uint32_t *x, uint32_t *y) {
|
|
uint32_t rx, ry, s, t=d;
|
|
*x = *y = 0;
|
|
for (s=1; s<n; s*=2) {
|
|
rx = 1 & (t/2);
|
|
ry = 1 & (t ^ rx);
|
|
y16t_hilbert_rot(s, x, y, rx, ry);
|
|
*x += s * rx;
|
|
*y += s * ry;
|
|
t /= 4;
|
|
}
|
|
}
|
|
*/
|