base36.go

package main

import (
	"math/big"
	"strings"
)

const (
	idLength     = 12
	lookupString = "0123456789abcdefghijklmnopqrstuvwxyz"
)

func partition(start, end string, partitions int) []string {
	startNum := base36ToBig(start)
	endNum := base36ToBig(end)

	// Sanity check inputs - end must be greater than start
	if startNum.Cmp(endNum) >= 0 {
		return []string{}
	}

	// Calculate the keyspace included in each partition
	difference := big.NewInt(0).Sub(endNum, startNum)
	partitionSize := big.NewInt(0).Div(difference, big.NewInt(int64(partitions)))

	// Generate readable strings representing the start of each partition
	var partitionStrings []string
	for i := 0; i < partitions; i++ {
		partitionAdditive := big.NewInt(0).Mul(partitionSize, big.NewInt(int64(i)))
		partitionStart := big.NewInt(0).Add(startNum, partitionAdditive)

		partitionStrings = append(partitionStrings, bigToBase36(partitionStart))
	}

	// We assume that the caller will re-use the end string themselves,
	// so we don't need to include it in the partition slice.
	return partitionStrings
}

func base36ToBig(input string) *big.Int {
	// Boundary check to make sure we have a string of idLength length
	if len(input) < idLength {
		input += strings.Repeat("0", idLength-len(input))
	}
	if len(input) > idLength {
		input = input[:12]
	}

	num := big.NewInt(0)

	for i := 0; i < idLength; i++ {
		// Turn the current character in the string to its numerical value
		// from the lookup table.
		c := charToIndex(input[i])

		// Create the multiplier for the current input string position.
		// It is basically 36^position.
		mul := big.NewInt(0).Exp(big.NewInt(36), big.NewInt(int64(idLength-i)), nil)

		// Calculate the current character position's magnitude in the final
		// result number.
		tmp := big.NewInt(0).Mul(mul, big.NewInt(int64(c)))
		num.Add(num, tmp)
	}

	return num
}

func bigToBase36(input *big.Int) string {
	result := make([]byte, idLength)

	for i := 0; i < idLength; i++ {
		divisor := big.NewInt(0).Exp(big.NewInt(36), big.NewInt(int64(idLength-i)), nil)

		// Dividing the remaining input number by 36^i should yield an index
		// into our lookup string.
		mod := big.NewInt(0)
		posIndex, _ := big.NewInt(0).DivMod(input, divisor, mod)

		result[i] = indexToChar(int(posIndex.Int64()))

		// Set the remainder of the division for the next loop
		input = mod
	}

	return string(result)
}

func charToIndex(c byte) int {
	return strings.IndexByte(lookupString, c)
}

func indexToChar(index int) byte {
	return lookupString[index]
}