modules/ulid.zzm

=encoding utf8

=head1 NAME

ulid - Universally Unique Lexicographically Sortable Identifiers.

=head1 SYNOPSIS

  from std/time import Time;
  from ulid import create_ulid, create_ulid_binary, ulid_time;
  
  let text := create_ulid();
  let raw := create_ulid_binary();
  let historical := create_ulid( time: new Time(946684800) );
  let timestamp := ulid_time(text);

=head1 IMPLEMENTATION SUPPORT

This module is supported by all implementations of ZuzuScript.

=head1 DESCRIPTION

This module generates ULIDs using a 48-bit Unix timestamp in
milliseconds and 80 bits of cryptographically secure randomness.
The text form uses canonical uppercase Crockford Base32.

Identifiers generated within the same millisecond are monotonic: the
random component is incremented so that each later identifier sorts
after the previous one.

=head1 EXPORTS

=head2 Functions

=over

=item * C<create_ulid_binary(time: Time?)>

Parameters: optional C<time> supplies the timestamp; when omitted, the
current time is used. Returns: C<BinaryString>. Returns a single ULID
as 16 raw bytes in network byte order.

=item * C<create_ulid(time: Time?)>

Parameters: optional C<time> supplies the timestamp; when omitted, the
current time is used. Returns: C<String>. Returns a single ULID as 26
uppercase Crockford Base32 characters.

=item * C<ulid_time(String|BinaryString ulid)>

Parameters: C<ulid> is a valid 26-character ULID, accepted
case-insensitively, or a 16-byte binary ULID. Returns: C<Time>. Returns the
timestamp encoded in the ULID, with millisecond precision. The input form is
detected automatically. Throws an exception if C<ulid> is not valid.

=back

=head1 COPYRIGHT AND LICENCE

B<ulid> is copyright Toby Inkster.

It is free software; you may redistribute it and/or modify it under
the terms of either the Artistic License 1.0 or the GNU General Public
License version 2.

=cut

from std/secure import SecureRandom;
from std/string import index, substr;
from std/string/base64 import decode, encode;
from std/time import Time;

const _B32_ALPHABET := "0123456789ABCDEFGHJKMNPQRSTVWXYZ";
const _B64_ALPHABET :=
	"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
const _MAX_TIMESTAMP := 281474976710655;

let _last_timestamp := -1;
let _last_random := [];

function _bytes_to_binary ( Array bytes ) {
	let out := "";
	let i := 0;
	let n := bytes.length();

	while ( i < n ) {
		let b0 := bytes[i];
		let b1 := null;
		let b2 := null;
		if ( i + 1 < n ) {
			b1 := bytes[i + 1];
		}
		if ( i + 2 < n ) {
			b2 := bytes[i + 2];
		}

		let c0 := ⌊ b0 ÷ 4 ⌋;
		let c1 := ( b0 mod 4 ) * 16;
		let c2 := 64;
		let c3 := 64;

		if ( b1 ≢ null ) {
			c1 += ⌊ b1 ÷ 16 ⌋;
			c2 := ( b1 mod 16 ) * 4;
			if ( b2 ≢ null ) {
				c2 += ⌊ b2 ÷ 64 ⌋;
				c3 := b2 mod 64;
			}
		}

		out _= substr( _B64_ALPHABET, c0, 1 );
		out _= substr( _B64_ALPHABET, c1, 1 );
		out _= c2 ≡ 64
			? "="
			: substr( _B64_ALPHABET, c2, 1 );
		out _= c3 ≡ 64
			? "="
			: substr( _B64_ALPHABET, c3, 1 );
		i += 3;
	}

	return decode(out);
}

function _timestamp_to_bytes ( Number timestamp ) {
	if (
		timestamp < 0
		or timestamp > _MAX_TIMESTAMP
		or timestamp ≢ floor(timestamp)
	) {
		die "ULID timestamp must be an integer from 0 to 2^48 - 1";
	}

	return [
		⌊ timestamp ÷ 1099511627776 ⌋ mod 256,
		⌊ timestamp ÷ 4294967296 ⌋ mod 256,
		⌊ timestamp ÷ 16777216 ⌋ mod 256,
		⌊ timestamp ÷ 65536 ⌋ mod 256,
		⌊ timestamp ÷ 256 ⌋ mod 256,
		timestamp mod 256,
	];
}

function _random_bytes () {
	let bytes := [];
	while ( bytes.length() < 10 ) {
		bytes.push( SecureRandom.int(256) );
	}
	return bytes;
}

function _increment_random ( Array bytes ) {
	let i := 9;
	while ( i >= 0 ) {
		if ( bytes[i] < 255 ) {
			bytes[i]++;
			return bytes;
		}
		bytes[i] := 0;
		i--;
	}

	die "ULID random component overflow";
}

function _time_option ( PairList options ) {
	let time := null;
	let seen_time := false;

	for ( let option in options.enumerate() ) {
		if ( option.key ne "time" ) {
			die `ULID option '${option.key}' is not supported`;
		}
		if ( seen_time ) {
			die "ULID option 'time' may only be supplied once";
		}
		if ( not( option.value instanceof Time ) ) {
			die "ULID option 'time' must be a Time object";
		}
		time := option.value;
		seen_time := true;
	}

	return time;
}

function _create_ulid_bytes ( Time time? ) {
	let source_time := time ≡ null ? new Time() : time;
	let timestamp := floor( source_time.epoch() * 1000 );
	let random := [];

	if ( timestamp ≡ _last_timestamp ) {
		random := _last_random.copy();
		_increment_random(random);
	}
	else {
		random := _random_bytes();
	}

	_last_timestamp := timestamp;
	_last_random := random.copy();

	let bytes := _timestamp_to_bytes(timestamp);
	for ( let byte in random ) {
		bytes.push(byte);
	}
	return bytes;
}

function _bytes_to_ulid_text ( Array bytes ) {
	if ( bytes.length() ≢ 16 ) {
		die "ULID binary value must contain exactly 16 bytes";
	}

	let out := "";
	let buffer := 0;
	let bits := 2;

	for ( let byte in bytes ) {
		if ( byte < 0 or byte > 255 or byte ≢ floor(byte) ) {
			die "ULID byte values must be integers from 0 to 255";
		}

		buffer := buffer * 256 + byte;
		bits += 8;

		while ( bits >= 5 ) {
			bits -= 5;
			let divisor := 2 ** bits;
			let digit := ⌊ buffer ÷ divisor ⌋;
			buffer := buffer mod divisor;
			out _= substr( _B32_ALPHABET, digit, 1 );
		}
	}

	return out;
}

function _binary_ulid_time ( BinaryString ulid ) {
	if ( length ulid ≢ 16 ) {
		die "ULID binary value must contain exactly 16 bytes";
	}

	let encoded := encode(ulid);
	let timestamp := 0;
	let i := 0;

	while ( i < 8 ) {
		let c0 := index( _B64_ALPHABET, substr( encoded, i, 1 ) );
		let c1 := index( _B64_ALPHABET, substr( encoded, i + 1, 1 ) );
		let c2 := index( _B64_ALPHABET, substr( encoded, i + 2, 1 ) );
		let c3 := index( _B64_ALPHABET, substr( encoded, i + 3, 1 ) );
		timestamp :=
			timestamp * 16777216
			+ c0 * 262144
			+ c1 * 4096
			+ c2 * 64
			+ c3;
		i += 4;
	}

	return new Time( timestamp ÷ 1000 );
}

function ulid_time ( ulid ) {
	if ( ulid instanceof BinaryString ) {
		return _binary_ulid_time(ulid);
	}
	if ( not( ulid instanceof String ) ) {
		die "ULID value must be a String or BinaryString";
	}
	if ( length ulid ≢ 26 ) {
		die "ULID text must contain exactly 26 characters";
	}

	let text := uc(ulid);
	let timestamp := 0;
	let i := 0;

	while ( i < 26 ) {
		let digit := index( _B32_ALPHABET, substr( text, i, 1 ) );
		if ( digit < 0 ) {
			die "ULID text contains an invalid Crockford Base32 character";
		}
		if ( i ≡ 0 and digit > 7 ) {
			die "ULID text exceeds 128 bits";
		}
		if ( i < 10 ) {
			timestamp := timestamp * 32 + digit;
		}
		i++;
	}

	return new Time( timestamp ÷ 1000 );
}

function create_ulid_binary ( ... PairList options ) {
	return _bytes_to_binary( _create_ulid_bytes( _time_option(options) ) );
}

function create_ulid ( ... PairList options ) {
	return _bytes_to_ulid_text( _create_ulid_bytes( _time_option(options) ) );
}