/ Check-in [61bdb53a]
Login

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

Overview
Comment:New varint encoding gives a maximum varint length of 9 instead of 10. (CVS 1395)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 61bdb53a363644074d01682fab8220078523676b
User & Date: drh 2004-05-18 15:57:42
Context
2004-05-18
22:03
Remove dead code from util.c (CVS 1396) check-in: 3ce42e85 user: drh tags: trunk
15:57
New varint encoding gives a maximum varint length of 9 instead of 10. (CVS 1395) check-in: 61bdb53a user: drh tags: trunk
12:50
Additional debugging output from btree.c (CVS 1394) check-in: b2def185 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/test3.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183

1184
1185

1186
1187
1188
1189
1190
1191
1192
1193
1194
1195

1196
1197
1198
1199








1200
1201
1202
1203
1204
1205
1206
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.37 2004/05/14 16:50:06 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  u32 start, mult, count, incr;
  u64 in, out;
  int n1, n2, i;
  unsigned char zBuf[100];
  if( argc!=5 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " START MULTIPLIER COUNT INCREMENT\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&start) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[2], (int*)&mult) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[3], (int*)&count) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[4], (int*)&incr) ) return TCL_ERROR;
  in = start;
  in *= mult;
  for(i=0; i<count; i++){

    n1 = sqlite3PutVarint(zBuf, in);
    if( n1>9 || n1<1 ){

      Tcl_AppendResult(interp, "PutVarint returned value out of range", 0);
      return TCL_ERROR;
    }
    n2 = sqlite3GetVarint(zBuf, &out);
    if( n1!=n2 ){
      Tcl_AppendResult(interp, \
         "GetVarint returned value different from PutVarint", 0);
      return TCL_ERROR;
    }
    if( in!=out ){

      Tcl_AppendResult(interp, \
         "Value read is different from value written", 0);
      return TCL_ERROR;
    }








    in += incr;
  }
  return TCL_OK;
}

/*
** Register commands with the TCL interpreter.







|







 







|













>


>
|




|
|



>
|
<


>
>
>
>
>
>
>
>







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199

1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.38 2004/05/18 15:57:42 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  u32 start, mult, count, incr;
  u64 in, out;
  int n1, n2, i, j;
  unsigned char zBuf[100];
  if( argc!=5 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " START MULTIPLIER COUNT INCREMENT\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&start) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[2], (int*)&mult) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[3], (int*)&count) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[4], (int*)&incr) ) return TCL_ERROR;
  in = start;
  in *= mult;
  for(i=0; i<count; i++){
    char zErr[200];
    n1 = sqlite3PutVarint(zBuf, in);
    if( n1>9 || n1<1 ){
      sprintf(zErr, "PutVarint returned %d - should be between 1 and 9", n1);
      Tcl_AppendResult(interp, zErr, 0);
      return TCL_ERROR;
    }
    n2 = sqlite3GetVarint(zBuf, &out);
    if( n1!=n2 ){
      sprintf(zErr, "PutVarint returned %d and GetVarint returned %d", n1, n2);
      Tcl_AppendResult(interp, zErr, 0);
      return TCL_ERROR;
    }
    if( in!=out ){
      sprintf(zErr, "Wrote 0x%016llx and got back 0x%016llx", in, out);
      Tcl_AppendResult(interp, zErr, 0);

      return TCL_ERROR;
    }

    /* In order to get realistic timings, run getVarint 19 more times.
    ** This is because getVarint is called about 20 times more often
    ** than putVarint.
    */
    for(j=0; j<19; j++){
      sqlite3GetVarint(zBuf, &out);
    }
    in += incr;
  }
  return TCL_OK;
}

/*
** Register commands with the TCL interpreter.

Changes to src/util.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
....
1135
1136
1137
1138
1139
1140
1141



















1142
1143
1144
1145
1146
1147
1148
1149

1150
1151
1152
1153









1154
1155
1156
1157
1158
1159

1160
1161
1162
1163
1164
1165
1166
....
1195
1196
1197
1198
1199
1200
1201




1202
1203
1204
1205
1206
1207
1208
....
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
....
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.82 2004/05/14 16:50:06 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................
  if( db->pVdbe!=0 ){
    db->magic = SQLITE_MAGIC_ERROR;
    return 1;
  }
  return 0;
}




















/*
** Write a 64-bit variable-length integer to memory starting at p[0].
** The length of data write will be between 1 and 9 bytes.  The number
** of bytes written is returned.
**
** A variable-length integer consists of the lower 7 bits of each byte
** for all bytes that have the 8th bit set and one byte with the 8th
** bit clear.

*/
int sqlite3PutVarint(unsigned char *p, u64 v){
  int i, j, n;
  u8 buf[10];









  n = 0;
  do{
    buf[n++] = (v & 0x7f) | 0x80;
    v >>= 7;
  }while( v!=0 );
  buf[0] &= 0x7f;

  for(i=0, j=n-1; j>=0; j--, i++){
    p[i] = buf[j];
  }
  return n;
}

/*
................................................................................
    *v = (x<<7) | c;
    return 4;
  }
  x64 = (x<<7) | (c&0x7f);
  n = 4;
  do{
    c = p[n++];




    x64 = (x64<<7) | (c&0x7f);
  }while( (c & 0x80)!=0 );
  *v = x64;
  return n;
}

/*
................................................................................
** Read a 32-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read.  The value is stored in *v.
*/
int sqlite3GetVarint32(const unsigned char *p, u32 *v){
  int n = 1;
  unsigned char c = p[0];
  u32 x = c & 0x7f;
  while( (c & 0x80)!=0 ){
    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }
  *v = x;
  return n;
}

................................................................................
** 64-bit integer.
*/
int sqlite3VarintLen(u64 v){
  int i = 0;
  do{
    i++;
    v >>= 7;
  }while( v!=0 );
  return i;
}







|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







|
>




>
>
>
>
>
>
>
>
>






>







 







>
>
>
>







 







|







 







|


10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
....
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
....
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
....
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
....
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.83 2004/05/18 15:57:42 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................
  if( db->pVdbe!=0 ){
    db->magic = SQLITE_MAGIC_ERROR;
    return 1;
  }
  return 0;
}

/*
** The variable-length integer encoding is as follows:
**
** KEY:
**         A = 0xxxxxxx    7 bits of data and one flag bit
**         B = 1xxxxxxx    7 bits of data and one flag bit
**         C = xxxxxxxx    8 bits of data
**
**  7 bits - A
** 14 bits - BA
** 21 bits - BBA
** 28 bits - BBBA
** 35 bits - BBBBA
** 42 bits - BBBBBA
** 49 bits - BBBBBBA
** 56 bits - BBBBBBBA
** 64 bits - BBBBBBBBC
*/

/*
** Write a 64-bit variable-length integer to memory starting at p[0].
** The length of data write will be between 1 and 9 bytes.  The number
** of bytes written is returned.
**
** A variable-length integer consists of the lower 7 bits of each byte
** for all bytes that have the 8th bit set and one byte with the 8th
** bit clear.  Except, if we get to the 9th byte, it stores the full
** 8 bits and is the last byte.
*/
int sqlite3PutVarint(unsigned char *p, u64 v){
  int i, j, n;
  u8 buf[10];
  if( v & 0xff00000000000000 ){
    p[8] = v;
    v >>= 8;
    for(i=7; i>=0; i--){
      p[i] = (v & 0x7f) | 0x80;
      v >>= 7;
    }
    return 9;
  }    
  n = 0;
  do{
    buf[n++] = (v & 0x7f) | 0x80;
    v >>= 7;
  }while( v!=0 );
  buf[0] &= 0x7f;
  assert( n<=9 );
  for(i=0, j=n-1; j>=0; j--, i++){
    p[i] = buf[j];
  }
  return n;
}

/*
................................................................................
    *v = (x<<7) | c;
    return 4;
  }
  x64 = (x<<7) | (c&0x7f);
  n = 4;
  do{
    c = p[n++];
    if( n==9 ){
      x64 = (x64<<8) | c;
      break;
    }
    x64 = (x64<<7) | (c&0x7f);
  }while( (c & 0x80)!=0 );
  *v = x64;
  return n;
}

/*
................................................................................
** Read a 32-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read.  The value is stored in *v.
*/
int sqlite3GetVarint32(const unsigned char *p, u32 *v){
  int n = 1;
  unsigned char c = p[0];
  u32 x = c & 0x7f;
  while( (c & 0x80)!=0 && n<9 ){
    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }
  *v = x;
  return n;
}

................................................................................
** 64-bit integer.
*/
int sqlite3VarintLen(u64 v){
  int i = 0;
  do{
    i++;
    v >>= 7;
  }while( v!=0 && i<9 );
  return i;
}

Changes to test/btree.test.

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
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.24 2004/05/14 16:50:07 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Testing of varint reading writing.
#
do_test btree-0.1 {
  btree_varint_test 0 0 500 1
} {}
do_test btree-0.2 {
  btree_varint_test 1024 1 500 1
} {}
do_test btree-0.3 {
  btree_varint_test -1 1 500 1
} {}
do_test btree-0.4 {
  btree_varint_test -1 100000 500 1
} {}

# Basic functionality.  Open and close a database.
#
do_test btree-1.1 {
  file delete -force test1.bt
  file delete -force test1.bt-journal
  set rc [catch {btree_open test1.bt 2000 0} ::b1]
} {0}







|





<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







7
8
9
10
11
12
13
14
15
16
17
18
19















20
21
22
23
24
25
26
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.25 2004/05/18 15:57:42 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl
















# Basic functionality.  Open and close a database.
#
do_test btree-1.1 {
  file delete -force test1.bt
  file delete -force test1.bt-journal
  set rc [catch {btree_open test1.bt 2000 0} ::b1]
} {0}

Added test/varint.test.

































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
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
# 2001 September 15
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is variable-length integer encoding scheme.
#
# $Id: varint.test,v 1.1 2004/05/18 15:57:42 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Test reading and writing of varints.
#
set cnt 0
foreach start {0 100 10000 1000000 0x10000000} {
  foreach mult {1 0x10 0x100 0x1000 0x10000 0x100000 0x1000000 0x10000000} {
    foreach incr {1 500 10000 50000000} {
      incr cnt
      do_test varint-1.$cnt {
        btree_varint_test $start $mult 5000 $incr
      } {}
    }
  }
}