Debian Codegraph @

ext/misc/zorder.c

raw
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 }