| 1 |
/* |
| 2 |
** 2018-02-09 |
| 3 |
** |
| 4 |
** The author disclaims copyright to this source code. In place of |
| 5 |
** a legal notice, here is a blessing: |
| 6 |
** |
| 7 |
** May you do good and not evil. |
| 8 |
** May you find forgiveness for yourself and forgive others. |
| 9 |
** May you share freely, never taking more than you give. |
| 10 |
** |
| 11 |
****************************************************************************** |
| 12 |
** |
| 13 |
** SQL functions for z-order (Morton code) transformations. |
| 14 |
** |
| 15 |
** zorder(X0,X0,..,xN) Generate an N+1 dimension Morton code |
| 16 |
** |
| 17 |
** unzorder(Z,N,I) Extract the I-th dimension from N-dimensional |
| 18 |
** Morton code Z. |
| 19 |
** |
| 20 |
** Compiling: |
| 21 |
** |
| 22 |
** (linux) gcc -fPIC -shared zorder.c -o zorder.so |
| 23 |
** (mac) clang -fPIC -dynamiclib zorder.c -o zorder.dylib |
| 24 |
** (windows) cl zorder.c -link -dll -out:zorder.dll |
| 25 |
** |
| 26 |
** Usage example: |
| 27 |
** |
| 28 |
** .load ./zorder |
| 29 |
** SELECT zorder(1,2,3,4); |
| 30 |
*/ |
| 31 |
#include "sqlite3ext.h" |
| 32 |
SQLITE_EXTENSION_INIT1 |
| 33 |
#include <assert.h> |
| 34 |
#include <string.h> |
| 35 |
|
| 36 |
/* |
| 37 |
** Functions: zorder(X0,X1,....) |
| 38 |
** |
| 39 |
** Convert integers X0, X1, ... into morton code. There must be at least |
| 40 |
** two arguments. There may be no more than 24 arguments. |
| 41 |
** |
| 42 |
** The output is a signed 64-bit integer. If any argument is too large |
| 43 |
** to be successfully encoded into a morton code, an error is raised. |
| 44 |
*/ |
| 45 |
static void zorderFunc( |
| 46 |
sqlite3_context *context, |
| 47 |
int argc, |
| 48 |
sqlite3_value **argv |
| 49 |
){ |
| 50 |
sqlite3_int64 z, x[24]; |
| 51 |
int i, j; |
| 52 |
z = 0; |
| 53 |
if( argc<2 || argc>24 ){ |
| 54 |
sqlite3_result_error(context, |
| 55 |
"zorder() needs between 2 and 24 arguments4", -1); |
| 56 |
return; |
| 57 |
} |
| 58 |
for(i=0; i<argc; i++){ |
| 59 |
x[i] = sqlite3_value_int64(argv[i]); |
| 60 |
} |
| 61 |
for(i=0; i<63; i++){ |
| 62 |
j = i%argc; |
| 63 |
z |= (x[j]&1)<<i; |
| 64 |
x[j] >>= 1; |
| 65 |
} |
| 66 |
sqlite3_result_int64(context, z); |
| 67 |
for(i=0; i<argc; i++){ |
| 68 |
if( x[i] ){ |
| 69 |
char *z = sqlite3_mprintf( |
| 70 |
"the %r argument to zorder() (%lld) is too large " |
| 71 |
"for a 64-bit %d-dimensional Morton code", |
| 72 |
i+1, sqlite3_value_int64(argv[i]), argc); |
| 73 |
sqlite3_result_error(context, z, -1); |
| 74 |
sqlite3_free(z); |
| 75 |
break; |
| 76 |
} |
| 77 |
} |
| 78 |
} |
| 79 |
|
| 80 |
|
| 81 |
/* |
| 82 |
** Function: unzorder(Z,N,K) |
| 83 |
** |
| 84 |
** Assuming that Z is an N-dimensional Morton code, extract the K-th |
| 85 |
** dimension. K is between 0 and N-1. N must be between 2 and 24. |
| 86 |
*/ |
| 87 |
static void unzorderFunc( |
| 88 |
sqlite3_context *context, |
| 89 |
int argc, |
| 90 |
sqlite3_value **argv |
| 91 |
){ |
| 92 |
sqlite3_int64 z, n, i, x; |
| 93 |
int j, k; |
| 94 |
z = sqlite3_value_int64(argv[0]); |
| 95 |
n = sqlite3_value_int64(argv[1]); |
| 96 |
if( n<2 || n>24 ){ |
| 97 |
sqlite3_result_error(context, |
| 98 |
"N argument to unzorder(Z,N,K) should be between 2 and 24", |
| 99 |
-1); |
| 100 |
return; |
| 101 |
} |
| 102 |
i = sqlite3_value_int64(argv[2]); |
| 103 |
if( i<0 || i>=n ){ |
| 104 |
sqlite3_result_error(context, |
| 105 |
"K argument to unzorder(Z,N,K) should be between 0 and N-1", -1); |
| 106 |
return; |
| 107 |
} |
| 108 |
x = 0; |
| 109 |
for(k=0, j=i; j<63; j+=n, k++){ |
| 110 |
x |= ((z>>j)&1)<<k; |
| 111 |
} |
| 112 |
sqlite3_result_int64(context, x); |
| 113 |
} |
| 114 |
|
| 115 |
|
| 116 |
#ifdef _WIN32 |
| 117 |
__declspec(dllexport) |
| 118 |
#endif |
| 119 |
int sqlite3_zorder_init( |
| 120 |
sqlite3 *db, |
| 121 |
char **pzErrMsg, |
| 122 |
const sqlite3_api_routines *pApi |
| 123 |
){ |
| 124 |
int rc = SQLITE_OK; |
| 125 |
SQLITE_EXTENSION_INIT2(pApi); |
| 126 |
(void)pzErrMsg; /* Unused parameter */ |
| 127 |
rc = sqlite3_create_function(db, "zorder", -1, SQLITE_UTF8, 0, |
| 128 |
zorderFunc, 0, 0); |
| 129 |
if( rc==SQLITE_OK ){ |
| 130 |
rc = sqlite3_create_function(db, "unzorder", 3, SQLITE_UTF8, 0, |
| 131 |
unzorderFunc, 0, 0); |
| 132 |
} |
| 133 |
return rc; |
| 134 |
} |