A simple ULID implement in Java with unit test

ULID.java

import com.google.common.annotations.VisibleForTesting;

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;

/**
 * A ULID generator that follows the <a href="https://github.com/ulid/spec">ULID spec.</a>
 */
public class ULID {

    // Crockford's Base32
    private static final char[] ALPHABET = "0123456789ABCDEFGHJKMNPQRSTVWXYZ".toCharArray();
    private static final int TIME_BYTES = 6;
    private static final int RAMDOM_BYTES = 10;

    private static final AtomicLong lastTime = new AtomicLong(Long.MIN_VALUE);
    private static final AtomicReference<byte[]> lastBytes = new AtomicReference<>(new byte[17]);


    public static String next() {
        byte[] ulidBytes;

        while (true) {
            final long last = lastTime.get();
            final long cur = System.currentTimeMillis();

            if (last == cur) {
                final byte[] lastBytesVal = lastBytes.get();
                ulidBytes = lastBytesVal.clone();
                if (!incrementLastRandom(ulidBytes)) {
                    // overflow, retry
                    continue;
                }
                if (!lastBytes.compareAndSet(lastBytesVal, ulidBytes)) {
                    continue;
                }
            } else {
                ulidBytes = new byte[TIME_BYTES + RAMDOM_BYTES + 1];
                ThreadLocalRandom.current().nextBytes(ulidBytes);
                // ulidBytes[0]: padding 0 so that we have 130 bits in total (26 chars * 5 bit/char)
                ulidBytes[0] = 0;

                // set first 6B, 48bits: timestamp, big-endian
                ulidBytes[1] = (byte) ((cur >>> 40) & 0xFF);
                ulidBytes[2] = (byte) ((cur >>> 32) & 0xFF);
                ulidBytes[3] = (byte) ((cur >>> 24) & 0xFF);
                ulidBytes[4] = (byte) ((cur >>> 16) & 0xFF);
                ulidBytes[5] = (byte) ((cur >>> 8) & 0xFF);
                ulidBytes[6] = (byte) (cur & 0xFF);

                lastBytes.set(ulidBytes);
            }

            if (lastTime.compareAndSet(last, cur)) {
                break;
            }
        }

        // encode
        final char[] chars = new char[26];
        for (int i = 0; i < 26; i++) {
            int bitIndex = 6 + i * 5; // skip the redundant 6 bits (17*8 - 26char * 5)
            int val = readFiveBits(ulidBytes, bitIndex);
            chars[i] = ALPHABET[val];
        }

        return new String(chars);
    }

    @VisibleForTesting
    static boolean incrementLastRandom(final byte[] last) {
        for (int i = last.length - 1; i >= last.length - RAMDOM_BYTES; i--) {
            int v = (last[i] & 0xFF) + 1;
            last[i] = (byte) v;
            if ((v & 0x100) == 0) {
                // no carry bit
                return true;
            }
        }
        return false;
    }

    /**
     * Read 5 bits from the byte array starting at the specified bit offset, as an int.
     *
     * @return [0, 31]
     */
    private static int readFiveBits(byte[] bytes, int bitOffset) {
        int value = 0;

        for (int i = 0; i < 5; i++) {
            final int bitIndex = bitOffset + i;
            final int byteIndex = bitIndex / 8;
            final int bitIndexInByte = bitIndex - byteIndex * 8;

            int bit = (bytes[byteIndex] >> (7 - bitIndexInByte)) & 1;
            value = (value << 1) | bit;
        }

        return value;
    }
}

ULIDTest.java

import org.junit.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import javax.annotation.Nullable;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class ULIDTest {

    @Test
    public void generateULID() {
        final String id = ULID.next();

        assert id.length() == 26;
        // the largest valid ULID encoded in base32 is 7ZZZZZZZZZZZZZZZZZZZZZZZZZ (2bits padding 0 + 48bits 1 + 80bits 1)
        assert id.charAt(0) <= '7';
        assert id.charAt(1) <= 'Z';
    }

    @Test
    public void ulidShouldMonotonous() {
        final List<String> ids = IntStream.range(0, 2000)
            .mapToObj(i -> ULID.next())
            .collect(Collectors.toList());

        for (int i = 1; i < ids.size(); i++) {
            assert ids.get(i).compareTo(ids.get(i - 1)) > 0;
        }
    }

    private static Stream<Arguments> incrementTestCases() {
        return Stream.of(
            Arguments.of(
                new int[]{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
                null
            ), // overflow
            Arguments.of(
                new int[]{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE},
                new int[]{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
            ), // no carry
            Arguments.of(
                new int[]{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x11, 0xFF, 0xFF, 0xFF},
                new int[]{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x12, 0x00, 0x00, 0x00}
            ) // continues carry
        );
    }

    @ParameterizedTest
    @MethodSource("incrementTestCases")
    public void increment(final int[] before, @Nullable final int[] after) {
        assert after == null || before.length == after.length : "Expect before and after have same length";

        final byte[] bytes = new byte[before.length];
        for (int i = 0; i < before.length; i++) {
            bytes[i] = (byte) before[i];
        }
        final boolean succeed = ULID.incrementLastRandom(bytes);

        if (after == null) {
            assert !succeed : "Expect failed to increment, but succeed.";
            return;
        }

        assert succeed : "Expect to succeed, but it failed.";
        final byte[] expect = new byte[after.length];
        for (int i = 0; i < expect.length; i++) {
            expect[i] = (byte) after[i];
        }
        for (int i = 0; i < expect.length; i++) {
            assert bytes[i] == (expect[i]) : String.format("Expect bytes[%d] is 0x%02X but got 0x%02X", i, expect[i], bytes[i]);
        }
    }
}