/ Check-in [a57a77dc]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 Side-by-Side Diffs Ignore Whitespace Patch

Added 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  +}