/ Check-in [a57a77dc]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add the zorder.c extension implementing zorder() and unzorder() SQL functions.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: a57a77dc0cc9fbaa9d5b134422f7a8cc8d4c2851ed3c2bdd449800c6a5d2aae0
User & Date: drh 2018-02-09 20:49:15
Context
2018-02-09
23:25
Improve the performance of the built-in REPLACE() function in cases where it does many substitutions that make the string larger. OSSFuzz is reporting intermittant timeouts when running a test where it does a REPLACE() on a 930KB random blob. Perhaps this enhancement will fix that. check-in: fab2c2b0 user: drh tags: trunk
20:49
Add the zorder.c extension implementing zorder() and unzorder() SQL functions. check-in: a57a77dc user: drh tags: trunk
15:42
Make the tests in func6.test more robust against implementation changes. check-in: b685d323 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Added ext/misc/zorder.c.













































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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;
}