From 510fea885e5b4841a57d13c21958ce650029f408 Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Fri, 9 Feb 2018 20:49:15 +0000
Subject: [PATCH] Add the zorder.c extension implementing zorder() and
 unzorder() SQL functions.

FossilOrigin-Name: a57a77dc0cc9fbaa9d5b134422f7a8cc8d4c2851ed3c2bdd449800c6a5d2aae0
---
 ext/misc/zorder.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++
 manifest          |  13 +++---
 manifest.uuid     |   2 +-
 3 files changed, 110 insertions(+), 7 deletions(-)
 create mode 100644 ext/misc/zorder.c

diff --git a/ext/misc/zorder.c b/ext/misc/zorder.c
new file mode 100644
index 0000000000..c385d3c3c3
--- /dev/null
+++ b/ext/misc/zorder.c
@@ -0,0 +1,102 @@
+/*
+** 2018-02-09
+**
+** The author disclaims copyright to this source code.  In place of
+** a legal notice, here is a blessing:
+**
+**    May you do good and not evil.
+**    May you find forgiveness for yourself and forgive others.
+**    May you share freely, never taking more than you give.
+**
+******************************************************************************
+**
+** SQL functions for z-order (Morton code) transformations.
+**
+**      zorder(X0,X0,..,xN)      Generate an N+1 dimension Morton code
+**
+**      unzorder(Z,N,I)          Extract the I-th dimension from N-dimensional
+**                               Morton code Z.
+*/
+#include "sqlite3ext.h"
+SQLITE_EXTENSION_INIT1
+#include <assert.h>
+#include <string.h>
+
+/*
+** Functions:     zorder(X0,X1,....)
+**
+** Convert integers X0, X1, ... into morton code.
+**
+** The output is a signed 64-bit integer.  If any argument is too large,
+** an error is thrown.
+*/
+static void zorderFunc(
+  sqlite3_context *context,
+  int argc,
+  sqlite3_value **argv
+){
+  sqlite3_int64 z, x[63];
+  int i, j;
+  z = 0;
+  for(i=0; i<argc; i++){
+    x[i] = sqlite3_value_int64(argv[i]);
+  }
+  if( argc>0 ){
+    for(i=0; i<63; i++){
+      j = i%argc;
+      z |= (x[j]&1)<<i;
+      x[j] >>= 1;
+    }
+  }
+  sqlite3_result_int64(context, z);
+  for(i=0; i<argc; i++){
+    if( x[i] ){
+      sqlite3_result_error(context, "parameter too large", -1);
+    }
+  }
+}
+
+
+/*
+** Functions:     unzorder(Z,N,I)
+**
+** Assuming that Z is an N-dimensional Morton code, extract the I-th
+** dimension.
+*/
+static void unzorderFunc(
+  sqlite3_context *context,
+  int argc,
+  sqlite3_value **argv
+){
+  sqlite3_int64 z, n, i, x;
+  int j, k;
+  z = sqlite3_value_int64(argv[0]);
+  n = sqlite3_value_int64(argv[1]);
+  i = sqlite3_value_int64(argv[2]);
+  x = 0;
+  for(k=0, j=i; j<63; j+=n, k++){
+    x |= ((z>>j)&1)<<k;
+  }
+  sqlite3_result_int64(context, x);
+}
+
+
+#ifdef _WIN32
+__declspec(dllexport)
+#endif
+int sqlite3_zorder_init(
+  sqlite3 *db, 
+  char **pzErrMsg, 
+  const sqlite3_api_routines *pApi
+){
+  int rc = SQLITE_OK;
+  SQLITE_EXTENSION_INIT2(pApi);
+  (void)pzErrMsg;  /* Unused parameter */
+  rc = sqlite3_create_function(db, "zorder", -1, SQLITE_UTF8, 0,
+                               zorderFunc, 0, 0);
+  if( rc==SQLITE_OK ){
+    rc = sqlite3_create_function(db, "unzorder", 3, SQLITE_UTF8, 0,
+                               unzorderFunc, 0, 0);
+  }
+  return rc;
+}
diff --git a/manifest b/manifest
index a0ff58b5eb..6cda78885d 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Make\sthe\stests\sin\sfunc6.test\smore\srobust\sagainst\simplementation\schanges.
-D 2018-02-09T15:42:40.632
+C Add\sthe\szorder.c\sextension\simplementing\szorder()\sand\sunzorder()\sSQL\sfunctions.
+D 2018-02-09T20:49:15.905
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
 F Makefile.in 7a3f714b4fcf793108042b7b0a5c720b0b310ec84314d61ba7f3f49f27e550ea
@@ -305,6 +305,7 @@ F ext/misc/vtablog.c 31d0d8f4406795679dcd3a67917c213d3a2a5fb3ea5de35f6e773491ed7
 F ext/misc/vtshim.c 1976e6dd68dd0d64508c91a6dfab8e75f8aaf6cd
 F ext/misc/wholenumber.c 784b12543d60702ebdd47da936e278aa03076212
 F ext/misc/zipfile.c 3c3e21d0351a44c34c67ca7e833ba04e0de34421b4c9359aa764919ee36b37ef
+F ext/misc/zorder.c b0ff58fa643afa1d846786d51ea8d5c4b6b35aa0254ab5a82617db92f3adda64
 F ext/rbu/rbu.c ea7d1b7eb44c123a2a619332e19fe5313500705c4a58aaa1887905c0d83ffc2e
 F ext/rbu/rbu1.test 43836fac8c7179a358eaf38a8a1ef3d6e6285842
 F ext/rbu/rbu10.test 1846519a438697f45e9dcb246908af81b551c29e1078d0304fae83f1fed7e9ee
@@ -1704,7 +1705,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P a6c3115483d597fc77ab19fdcfd1d3437cad7e467081ad8c5315fb98c115eed9
-R f6c1b3a83bf1fd9e6dbd920e348c4245
-U dan
-Z baeba07272c3f575c3e3036aa614a6dd
+P b685d3231097fb90e7d61d9ac01cc560e8bf2671d49390ae7af5bfdbd6d04f11
+R 574de61b6452baa1e71eeeef413a6e94
+U drh
+Z 5935918b7bd1bd1e30b211bf68154f29
diff --git a/manifest.uuid b/manifest.uuid
index 3dcc2798f8..c0133280c0 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-b685d3231097fb90e7d61d9ac01cc560e8bf2671d49390ae7af5bfdbd6d04f11
\ No newline at end of file
+a57a77dc0cc9fbaa9d5b134422f7a8cc8d4c2851ed3c2bdd449800c6a5d2aae0
\ No newline at end of file
-- 
2.47.2