ext/misc/zorder.c

   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 #include "sqlite3ext.h"
  21 SQLITE_EXTENSION_INIT1
  22 #include <assert.h>
  23 #include <string.h>
  24
  25 /*
  26 ** Functions:     zorder(X0,X1,....)
  27 **
  28 ** Convert integers X0, X1, ... into morton code.
  29 **
  30 ** The output is a signed 64-bit integer.  If any argument is too large,
  31 ** an error is thrown.
  32 */
  33 static void zorderFunc(
  34   sqlite3_context *context,
  35   int argc,
  36   sqlite3_value **argv
  37 ){
  38   sqlite3_int64 z, x[63];
  39   int i, j;
  40   z = 0;
  41   for(i=0; i<argc; i++){
  42     x[i] = sqlite3_value_int64(argv[i]);
  43   }
  44   if( argc>0 ){
  45     for(i=0; i<63; i++){
  46       j = i%argc;
  47       z |= (x[j]&1)<<i;
  48       x[j] >>= 1;
  49     }
  50   }
  51   sqlite3_result_int64(context, z);
  52   for(i=0; i<argc; i++){
  53     if( x[i] ){
  54       sqlite3_result_error(context, "parameter too large", -1);
  55     }
  56   }
  57 }
  58
  59
  60 /*
  61 ** Functions:     unzorder(Z,N,I)
  62 **
  63 ** Assuming that Z is an N-dimensional Morton code, extract the I-th
  64 ** dimension.
  65 */
  66 static void unzorderFunc(
  67   sqlite3_context *context,
  68   int argc,
  69   sqlite3_value **argv
  70 ){
  71   sqlite3_int64 z, n, i, x;
  72   int j, k;
  73   z = sqlite3_value_int64(argv[0]);
  74   n = sqlite3_value_int64(argv[1]);
  75   i = sqlite3_value_int64(argv[2]);
  76   x = 0;
  77   for(k=0, j=i; j<63; j+=n, k++){
  78     x |= ((z>>j)&1)<<k;
  79   }
  80   sqlite3_result_int64(context, x);
  81 }
  82
  83
  84 #ifdef _WIN32
  85 __declspec(dllexport)
  86 #endif
  87 int sqlite3_zorder_init(
  88   sqlite3 *db,
  89   char **pzErrMsg,
  90   const sqlite3_api_routines *pApi
  91 ){
  92   int rc = SQLITE_OK;
  93   SQLITE_EXTENSION_INIT2(pApi);
  94   (void)pzErrMsg;  /* Unused parameter */
  95   rc = sqlite3_create_function(db, "zorder", -1, SQLITE_UTF8, 0,
  96                                zorderFunc, 0, 0);
  97   if( rc==SQLITE_OK ){
  98     rc = sqlite3_create_function(db, "unzorder", 3, SQLITE_UTF8, 0,
  99                                unzorderFunc, 0, 0);
 100   }
 101   return rc;
 102 }