Skip to content

Instantly share code, notes, and snippets.

@stravant

stravant/DatastoreBytes.lua

Created October 24, 2023 04:50
Show Gist options
  • Save stravant/04312466d675c073a5e4052e95189808 to your computer and use it in GitHub Desktop.
Save stravant/04312466d675c073a5e4052e95189808 to your computer and use it in GitHub Desktop.
Download ZIP
Module which packs a sequence of variable length integers into a Datastore safe string at maximal density
Raw
DatastoreBytes.lua
local DS_INT_TO_INT = {} :: {[number]: number}
local INT_TO_DS_INT = {} :: {[number]: number}
local INT_TO_DS_CHAR = {} :: {[number]: string}
local DS_INT_MAX;
do
-- All characters under this are control characters, must avoid them because
-- they get expanded out into control sequences.
local MIN_DS_VALUE = 0x20
local MAX_DS_VALUE = 0x7E
local IGNORE_QUOTE = 0x22
local IGNORE_BACKSLASH = 0x5C
local translated = 0
for i = MIN_DS_VALUE, MAX_DS_VALUE do
if i ~= IGNORE_QUOTE and i ~= IGNORE_BACKSLASH then
DS_INT_TO_INT[i] = translated
INT_TO_DS_INT[translated] = i
INT_TO_DS_CHAR[translated] = string.char(i)
translated += 1
end
end
DS_INT_MAX = translated - 1
end
assert(DS_INT_MAX == 92, "DS_INT_MAX is not 92, something went terribly wrong")
local DatastoreBytes = {}
DatastoreBytes.DS_INT_TO_INT = DS_INT_TO_INT
DatastoreBytes.INT_TO_DS_INT = INT_TO_DS_INT
DatastoreBytes.INT_TO_DS_CHAR = INT_TO_DS_CHAR
DatastoreBytes.DS_INT_MAX = DS_INT_MAX
do
local N8_POSITIVE = 92
local N8_NEGATIVE = 91
local N4_POSITIVE = 90
local N4_NEGATIVE = 89
local N2_POSITIVE = 88
local N2_NEGATIVE = 87
local N1_NEGATIVE = 86
local MAX_RAW_VALUE = 85
local MAX_2_BYTE = DS_INT_MAX * DS_INT_MAX
local MAX_3_BYTE = MAX_2_BYTE * DS_INT_MAX
local MAX_4_BYTE = MAX_2_BYTE * MAX_2_BYTE
local MAX_5_BYTE = MAX_4_BYTE * DS_INT_MAX
local MAX_6_BYTE = MAX_4_BYTE * MAX_2_BYTE
local MAX_7_BYTE = MAX_4_BYTE * MAX_3_BYTE
local MAX_8_BYTE = MAX_4_BYTE * MAX_4_BYTE
function DatastoreBytes.writeVarint(value: number): string
-- Extract sign
local isNegative = value < 0
if isNegative then
value = -value
end
-- Small value
local fits1 = value <= MAX_RAW_VALUE
if fits1 then
if isNegative then
return string.char(INT_TO_DS_INT[N1_NEGATIVE], INT_TO_DS_INT[value])
else
return INT_TO_DS_CHAR[value]
end
end
-- Local shadow so we don't repeatedly hit the upvalue
local INT_TO_DS_INT = INT_TO_DS_INT
-- 2 byte value
local fits2 = value < MAX_2_BYTE
if fits2 then
local first = math.floor(value / DS_INT_MAX)
local second = value - first * DS_INT_MAX
if isNegative then
return string.char(
INT_TO_DS_INT[N2_NEGATIVE],
INT_TO_DS_INT[first],
INT_TO_DS_INT[second])
else
return string.char(
INT_TO_DS_INT[N2_POSITIVE],
INT_TO_DS_INT[first],
INT_TO_DS_INT[second])
end
end
-- 4 byte value
local fits4 = value <= MAX_4_BYTE
if fits4 then
local first = math.floor(value / MAX_3_BYTE)
value -= first * MAX_3_BYTE
local second = math.floor(value / MAX_2_BYTE)
value -= second * MAX_2_BYTE
local third = math.floor(value / DS_INT_MAX)
local fourth = value - third * DS_INT_MAX
if isNegative then
return string.char(
INT_TO_DS_INT[N4_NEGATIVE],
INT_TO_DS_INT[first],
INT_TO_DS_INT[second],
INT_TO_DS_INT[third],
INT_TO_DS_INT[fourth])
else
return string.char(
INT_TO_DS_INT[N4_POSITIVE],
INT_TO_DS_INT[first],
INT_TO_DS_INT[second],
INT_TO_DS_INT[third],
INT_TO_DS_INT[fourth])
end
end
-- 8 byte value
local fits8 = value <= MAX_8_BYTE
if fits8 then
local first = math.floor(value / MAX_7_BYTE)
value -= first * MAX_7_BYTE
local second = math.floor(value / MAX_6_BYTE)
value -= second * MAX_6_BYTE
local third = math.floor(value / MAX_5_BYTE)
value -= third * MAX_5_BYTE
local fourth = math.floor(value / MAX_4_BYTE)
value -= fourth * MAX_4_BYTE
local fifth = math.floor(value / MAX_3_BYTE)
value -= fifth * MAX_3_BYTE
local sixth = math.floor(value / MAX_2_BYTE)
value -= sixth * MAX_2_BYTE
local seventh = math.floor(value / DS_INT_MAX)
local eighth = value - seventh * DS_INT_MAX
if isNegative then
return string.char(
INT_TO_DS_INT[N8_NEGATIVE],
INT_TO_DS_INT[first],
INT_TO_DS_INT[second],
INT_TO_DS_INT[third],
INT_TO_DS_INT[fourth],
INT_TO_DS_INT[fifth],
INT_TO_DS_INT[sixth],
INT_TO_DS_INT[seventh],
INT_TO_DS_INT[eighth])
else
return string.char(
INT_TO_DS_INT[N8_POSITIVE],
INT_TO_DS_INT[first],
INT_TO_DS_INT[second],
INT_TO_DS_INT[third],
INT_TO_DS_INT[fourth],
INT_TO_DS_INT[fifth],
INT_TO_DS_INT[sixth],
INT_TO_DS_INT[seventh],
INT_TO_DS_INT[eighth])
end
else
error("Value too large to be written as a varint (> ~5e15)")
end
end
function DatastoreBytes.readVarint(blob: string, index: number): (number, number)
local DS_INT_TO_INT = DS_INT_TO_INT
local tag = DS_INT_TO_INT[string.byte(blob, index)]
if tag <= MAX_RAW_VALUE then
return tag, index + 1
elseif tag == N1_NEGATIVE then
local value = -DS_INT_TO_INT[string.byte(blob, index + 1)]
return value, index + 2
elseif tag == N2_NEGATIVE then
local b1, b2 = string.byte(blob, index + 1, index + 2)
local first = DS_INT_TO_INT[b1]
local second = DS_INT_TO_INT[b2]
local value = first * DS_INT_MAX + second
return -value, index + 3
elseif tag == N2_POSITIVE then
local b1, b2 = string.byte(blob, index + 1, index + 2)
local first = DS_INT_TO_INT[b1]
local second = DS_INT_TO_INT[b2]
local value = first * DS_INT_MAX + second
return value, index + 3
elseif tag == N4_NEGATIVE then
local b1, b2, b3, b4 = string.byte(blob, index + 1, index + 4)
local first = DS_INT_TO_INT[b1]
local second = DS_INT_TO_INT[b2]
local third = DS_INT_TO_INT[b3]
local fourth = DS_INT_TO_INT[b4]
local value =
first * MAX_3_BYTE +
second * MAX_2_BYTE +
third * DS_INT_MAX +
fourth
return -value, index + 5
elseif tag == N4_POSITIVE then
local b1, b2, b3, b4 = string.byte(blob, index + 1, index + 4)
local first = DS_INT_TO_INT[b1]
local second = DS_INT_TO_INT[b2]
local third = DS_INT_TO_INT[b3]
local fourth = DS_INT_TO_INT[b4]
local value =
first * MAX_3_BYTE +
second * MAX_2_BYTE +
third * DS_INT_MAX +
fourth
return value, index + 5
elseif tag == N8_NEGATIVE then
local b1, b2, b3, b4, b5, b6, b7, b8 = string.byte(blob, index + 1, index + 8)
local first = DS_INT_TO_INT[b1]
local second = DS_INT_TO_INT[b2]
local third = DS_INT_TO_INT[b3]
local fourth = DS_INT_TO_INT[b4]
local fifth = DS_INT_TO_INT[b5]
local sixth = DS_INT_TO_INT[b6]
local seventh = DS_INT_TO_INT[b7]
local eighth = DS_INT_TO_INT[b8]
local value =
first * MAX_7_BYTE +
second * MAX_6_BYTE +
third * MAX_5_BYTE +
fourth * MAX_4_BYTE +
fifth * MAX_3_BYTE +
sixth * MAX_2_BYTE +
seventh * DS_INT_MAX +
eighth
return -value, index + 9
elseif tag == N8_POSITIVE then
local b1, b2, b3, b4, b5, b6, b7, b8 = string.byte(blob, index + 1, index + 8)
local first = DS_INT_TO_INT[b1]
local second = DS_INT_TO_INT[b2]
local third = DS_INT_TO_INT[b3]
local fourth = DS_INT_TO_INT[b4]
local fifth = DS_INT_TO_INT[b5]
local sixth = DS_INT_TO_INT[b6]
local seventh = DS_INT_TO_INT[b7]
local eighth = DS_INT_TO_INT[b8]
local value =
first * MAX_7_BYTE +
second * MAX_6_BYTE +
third * MAX_5_BYTE +
fourth * MAX_4_BYTE +
fifth * MAX_3_BYTE +
sixth * MAX_2_BYTE +
seventh * DS_INT_MAX +
eighth
return value, index + 9
else
error("Invalid varint tag")
end
end
end
return DatastoreBytes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment