modules/ulid.zzm

=encoding utf8

=head1 NAME

ulid - Universally Unique Lexicographically Sortable Identifiers.

=head1 SYNOPSIS

  from ulid import create_ulid, create_ulid_binary;
  
  let text := create_ulid();
  let raw := create_ulid_binary();

=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()>

Parameters: none. Returns: C<BinaryString>. Returns a single ULID as 16
raw bytes in network byte order.

=item * C<create_ulid()>

Parameters: none. Returns: C<String>. Returns a single ULID as 26
uppercase Crockford Base32 characters.

=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 substr;
from std/string/base64 import decode;
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 _div_floor ( Number n, Number d ) {
	return floor( n / d );
}

function _mod ( Number n, Number d ) {
	return n - _div_floor( n, d ) * d;
}

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 := _div_floor( b0, 4 );
		let c1 := _mod( b0, 4 ) * 16;
		let c2 := 64;
		let c3 := 64;

		if ( b1 ≢ null ) {
			c1 += _div_floor( b1, 16 );
			c2 := _mod( b1, 16 ) * 4;
			if ( b2 ≢ null ) {
				c2 += _div_floor( b2, 64 );
				c3 := _mod( b2, 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 [
		_mod( _div_floor( timestamp, 1099511627776 ), 256 ),
		_mod( _div_floor( timestamp, 4294967296 ), 256 ),
		_mod( _div_floor( timestamp, 16777216 ), 256 ),
		_mod( _div_floor( timestamp, 65536 ), 256 ),
		_mod( _div_floor( timestamp, 256 ), 256 ),
		_mod( timestamp, 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 _create_ulid_bytes () {
	let timestamp := floor( new 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 := _div_floor( buffer, divisor );
			buffer := _mod( buffer, divisor );
			out _= substr( _B32_ALPHABET, digit, 1 );
		}
	}

	return out;
}

function create_ulid_binary () {
	return _bytes_to_binary( _create_ulid_bytes() );
}

function create_ulid () {
	return _bytes_to_ulid_text( _create_ulid_bytes() );
}