syncbase/key.go

// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package syncbase

import (
	"bytes"
	"crypto/rand"
	"encoding/base64"
	"encoding/binary"
	"fmt"
	"sync/atomic"
	"time"
)

const (
	// First character of UUID to make the UUID start with a valid identifier character.
	// Can be used for versioning.
	uuidPrefix string = "v"
	// Legal characters of Java identifiers in ASCII-encoding order.
	uuidCharacterSet string = "$0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"
)

var (
	invocationCounter uint32
	base64Encoding    *base64.Encoding
)

func init() {
	base64Encoding = base64.NewEncoding(uuidCharacterSet).WithPadding(base64.NoPadding)
}

// Truncates string 's' to 'length'. Will remove characters from the beginning of the string
// if 's' is too long.
func truncate(s string, length int) string {
	if len(s) > length {
		return s[len(s)-length:]
	} else {
		return s
	}
}

// Pad string 's' to 'length'. Will prefix 's' with sequences of 'padding' if the string
// is too short. If 'padding' has more than one character, the resulting string may be
// longer than 'length'.
func pad(s string, length int, padding string) string {
	for len(s) < length {
		s = padding + s
	}

	return s
}

// UUID generates a sequential and pseudo-random key that can be used as an ID within
// Syncbase. The generated IDs are of the format [a-zA-z][a-zA-Z0-9$_]{19}
//
// A UUID is made up of four parts:
// - a prefix which guarantees that the generated UUID is a valid variable name in most programming
//   languages
// - a time component which uses nanosecond precision
// - a counter component which is used to guarantee ordering between calls
// - a random component which achieves pseudo-randomness
func UUID() string {
	buffer := new(bytes.Buffer)

	// Encode the current time in nanoseconds as a base64-character string.
	// The maximum encoded length is 11 characters: 2^63/64^11 < 1
	currentTime := time.Now().UnixNano()
	binary.Write(buffer, binary.BigEndian, currentTime)
	uuidTime := base64Encoding.EncodeToString(buffer.Bytes())

	// Increment the global count of invocations and encode as a 3-character base64-string.
	// Note that overflows here are fine.
	buffer.Reset()
	currentInvocation := atomic.AddUint32(&invocationCounter, 1)
	binary.Write(buffer, binary.BigEndian, currentInvocation)
	uuidInvocation := base64Encoding.EncodeToString(buffer.Next(4)[1:])

	// Encode 4 bytes of randomness as a base64-string (maximum of 6 characters)
	random := make([]byte, 4)
	rand.Read(random)
	uuidRandNumber := base64Encoding.EncodeToString(random)

	return fmt.Sprintf(
		"%s%s%s%s",
		uuidPrefix,
		pad(uuidTime, 11, uuidCharacterSet[:1]),
		pad(truncate(uuidInvocation, 2), 2, uuidCharacterSet[:1]),
		pad(uuidRandNumber, 6, uuidCharacterSet[:1]))
}