Really the Cuid2 algorithm?

[sdavids]

Describe the bug

I am unsure if this implementation is the same algorithm as the original.

To Reproduce

The entropy is computed differently:

https://github.com/paralleldrive/cuid2/blob/53e246b0919c8123e492e6b6bbab41fe66f4b462/src/index.js#L7-L14

cuid-java/src/main/java/io/github/thibaultmeyer/cuid/CUID.java

Lines 265 to 275 in c55aa79

	private static String createEntropy(final int length) {
	int primeNumber;
	final StringBuilder stringBuilder = new StringBuilder(length);
	while (stringBuilder.length() < length) {
	primeNumber = PRIME_NUMBER_ARRAY[Math.abs(Common.nextIntValue()) % PRIME_NUMBER_ARRAY.length];
	stringBuilder.append(Integer.toString(primeNumber * Common.nextIntValue(), NUMBER_BASE));
	}
	return stringBuilder.toString();

---

The hash is computed differently:

https://github.com/paralleldrive/cuid2/blob/53e246b0919c8123e492e6b6bbab41fe66f4b462/src/index.js#L31-L35

cuid-java/src/main/java/io/github/thibaultmeyer/cuid/CUID.java

Lines 283 to 292 in c55aa79

	private static String computeHash(final String content, final int saltLength) {
	final String salt = createEntropy(saltLength);
	try {
	return new BigInteger(MessageDigest.getInstance("SHA3-256").digest((content + salt).getBytes(StandardCharsets.UTF_8)))
	.toString(NUMBER_BASE);
	} catch (final NoSuchAlgorithmException exception) {
	throw new CUIDGenerationException(exception);
	}
	}

---

The alphabet is accessed differently:

https://github.com/paralleldrive/cuid2/blob/53e246b0919c8123e492e6b6bbab41fe66f4b462/src/index.js#L37-L39

cuid-java/src/main/java/io/github/thibaultmeyer/cuid/CUID.java

Line 69 in c55aa79

final char firstLetter = CUIDv2.ALPHABET_ARRAY[Math.abs(Common.nextIntValue()) % CUIDv2.ALPHABET_ARRAY.length];

https://github.com/ai/nanoid?tab=readme-ov-file

random % alphabet is a popular mistake [...] [t]he distribution will not be even; there will be a lower chance for some symbols to appear compared to others.

[sdavids]

@ericelliott Maybe you could provide an authoritative assessment?

[sdavids]

I opened this issue because I considered doing a 1:1 algorithm translation in a new repo but I think it would be better to update this project instead of creating a new one.

[ericelliott]

Correct that % is not a safe method to generate uniform random values. Are the histogram and randogram tests run in this repo?

[ArnieGA]

Any updates on the issue?

[thibaultmeyer]

A fix has been merged to rework how alphabet is accessed and the entropy generation. I add a new unit test to get an histogram.

Histogram CUID v1 (1,000,000 values generated)

{
    0=50036,
    1=50153, 
    2=50277, 
    3=50222, 
    4=49676, 
    5=49867, 
    6=50294,
    7=49880, 
    8=49966, 
    9=49607, 
    10=49990, 
    11=50034, 
    12=49699, 
    13=50172, 
    14=50254, 
    15=50016, 
    16=49851, 
    17=49839, 
    18=49854, 
    19=50313
}

Histogram CUID v2 (1,000,000 values generated)

{
    0=50244,
    1=50062,
    2=49592,
    3=50009,
    4=50378,
    5=50164,
    6=50025,
    7=50197,
    8=49891,
    9=49621,
    10=50276,
    11=49488,
    12=49917,
    13=50033,
    14=50085,
    15=49897,
    16=49800,
    17=50054,
    18=50280,
    19=49987
}