Module which packs a sequence of variable length integers into a Datastore safe string at maximal density

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