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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
#
#
# Nim's Runtime Library
# (c) Copyright 2018 Nim contributors
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## Note this API is still experimental! A variable length integer
## encoding implementation inspired by SQLite.
const
maxVarIntLen* = 9 ## the maximal number of bytes a varint can take
proc readVu64*(z: openArray[byte]; pResult: var uint64): int =
if z[0] <= 240:
pResult = z[0]
return 1
if z[0] <= 248:
if z.len < 2: return 0
pResult = (uint64 z[0] - 241) * 256 + uint64 z[1] + 240
return 2
if z.len < int(z[0]-246): return 0
if z[0] == 249:
pResult = 2288u64 + 256u64*z[1].uint64 + z[2].uint64
return 3
if z[0] == 250:
pResult = (z[1].uint64 shl 16u64) + (z[2].uint64 shl 8u64) + z[3].uint64
return 4
let x = (z[1].uint64 shl 24) + (z[2].uint64 shl 16) + (z[3].uint64 shl 8) + z[4].uint64
if z[0] == 251:
pResult = x
return 5
if z[0] == 252:
pResult = (((uint64)x) shl 8) + z[5].uint64
return 6
if z[0] == 253:
pResult = (((uint64)x) shl 16) + (z[5].uint64 shl 8) + z[6].uint64
return 7
if z[0] == 254:
pResult = (((uint64)x) shl 24) + (z[5].uint64 shl 16) + (z[6].uint64 shl 8) + z[7].uint64
return 8
pResult = (((uint64)x) shl 32) +
(0xffffffff'u64 and ((z[5].uint64 shl 24) +
(z[6].uint64 shl 16) + (z[7].uint64 shl 8) + z[8].uint64))
return 9
proc varintWrite32(z: var openArray[byte]; y: uint32) =
z[0] = uint8(y shr 24)
z[1] = uint8(y shr 16)
z[2] = uint8(y shr 8)
z[3] = uint8(y)
proc writeVu64*(z: var openArray[byte], x: uint64): int =
## Write a varint into z. The buffer z must be at least 9 characters
## long to accommodate the largest possible varint. Returns the number of
## bytes used.
if x <= 240:
z[0] = uint8 x
return 1
if x <= 2287:
let y = uint32(x - 240)
z[0] = uint8(y shr 8 + 241)
z[1] = uint8(y and 255)
return 2
if x <= 67823:
let y = uint32(x - 2288)
z[0] = 249
z[1] = uint8(y shr 8)
z[2] = uint8(y and 255)
return 3
let y = uint32 x
let w = uint32(x shr 32)
if w == 0:
if y <= 16777215:
z[0] = 250
z[1] = uint8(y shr 16)
z[2] = uint8(y shr 8)
z[3] = uint8(y)
return 4
z[0] = 251
varintWrite32(toOpenArray(z, 1, z.high-1), y)
return 5
if w <= 255:
z[0] = 252
z[1] = uint8 w
varintWrite32(toOpenArray(z, 2, z.high-2), y)
return 6
if w <= 65535:
z[0] = 253
z[1] = uint8(w shr 8)
z[2] = uint8 w
varintWrite32(toOpenArray(z, 3, z.high-3), y)
return 7
if w <= 16777215:
z[0] = 254
z[1] = uint8(w shr 16)
z[2] = uint8(w shr 8)
z[3] = uint8 w
varintWrite32(toOpenArray(z, 4, z.high-4), y)
return 8
z[0] = 255
varintWrite32(toOpenArray(z, 1, z.high-1), w)
varintWrite32(toOpenArray(z, 5, z.high-5), y)
return 9
proc sar(a, b: int64): int64 =
{.emit: [result, " = ", a, " >> ", b, ";"].}
proc sal(a, b: int64): int64 =
{.emit: [result, " = ", a, " << ", b, ";"].}
proc encodeZigzag*(x: int64): uint64 {.inline.} =
uint64(sal(x, 1)) xor uint64(sar(x, 63))
proc decodeZigzag*(x: uint64): int64 {.inline.} =
let casted = cast[int64](x)
result = (`shr`(casted, 1)) xor (-(casted and 1))
when isMainModule:
#import random
var dest: array[50, byte]
var got: uint64
for test in [0xFFFF_FFFF_FFFFF_FFFFu64, 77u64, 0u64, 10_000_000u64, uint64(high(int64)),
uint64(high(int32)),uint64(low(int32)),uint64(low(int64))]:
let wrLen = writeVu64(dest, test)
let rdLen = readVu64(dest, got)
assert wrLen == rdLen
echo(if got == test: "YES" else: "NO")
echo "number is ", got
if encodeZigzag(decodeZigzag(test)) != test:
echo "Failure for ", test, " ", encodeZigzag(decodeZigzag(test)), " ", decodeZigzag(test)
# check this also works for floats:
for test in [0.0, 0.1, 2.0, +Inf, Nan, NegInf]:
let t = cast[uint64](test)
let wrLenB = writeVu64(dest, t)
let rdLenB = readVu64(dest, got)
assert wrLenB == rdLenB
echo rdLenB
echo(if cast[float64](got) == test: "YES" else: "NO")
|