java-topology/defects/raylib/patch/raylib-0002-random-sequence-hashset-dedup.md

UNDF: UNDF-2026-000000522

raylib-0002: LoadRandomSequence O(n²) dedup — CWE-407

Severity: MEDIUM File: src/rcore.c Function: LoadRandomSequence() Lines: ~1788–1803

Description

LoadRandomSequence() generates a sequence of count unique random integers in [min, max]. The fallback path (when SUPPORT_RPRAND_GENERATOR is not defined) uses a classic rejection-sampling loop with a nested linear scan:

for (int i = 0; i < (int)count;)
{
    value = GetRandomValue(min, max);
    dupValue = false;

    for (int j = 0; j < i; j++)      // O(i) per attempt — CWE-407
    {
        if (values[j] == value)
        {
            dupValue = true;
            break;
        }
    }

    if (!dupValue) { values[i] = value; i++; }
}

Total inner iterations: O(n²/2) expected. At n=1000 this is ~500 000 comparisons. At n=10 000 this is ~50 000 000 comparisons.

Fix

Replace the values[] linear scan with a bool seen[] bitmap (range is bounded by [min, max]) for O(1) membership:

// FIX raylib-0002: O(1) membership via boolean seen-array — CWE-407
int range = abs(max - min) + 1;
bool *seen = (bool *)RL_CALLOC(range, sizeof(bool));

for (int i = 0; i < (int)count;)
{
    value = GetRandomValue(min, max);
    int idx = value - min;
    if (!seen[idx])               // O(1)
    {
        seen[idx] = true;
        values[i] = value;
        i++;
    }
}
RL_FREE(seen);

Complexity: O(n) expected (geometric distribution, not O(n²)).

Speedup

n	Before (inner iters)	After (O(1) checks)	Ratio
100	~2 500	~100	~25×
1 000	~250 000	~1 000	~250×
10 000	~25 000 000	~10 000	~2500×

Patch

--- a/src/rcore.c
+++ b/src/rcore.c
@@ -1788,19 +1788,24 @@ int *LoadRandomSequence(unsigned int count, int min, int max)
     values = (int *)RL_CALLOC(count, sizeof(int));

-    int value = 0;
-    bool dupValue = false;
-
-    for (int i = 0; i < (int)count;)
-    {
-        value = GetRandomValue(min, max);
-        dupValue = false;
-
-        for (int j = 0; j < i; j++)
-        {
-            if (values[j] == value)
-            {
-                dupValue = true;
-                break;
-            }
-        }
-
-        if (!dupValue)
-        {
-            values[i] = value;
-            i++;
-        }
-    }
+    // FIX raylib-0002: replace O(n) inner scan with O(1) boolean bitmap — CWE-407
+    int range = abs(max - min) + 1;
+    bool *seen = (bool *)RL_CALLOC(range, sizeof(bool));
+    for (int i = 0; i < (int)count;)
+    {
+        int value = GetRandomValue(min, max);
+        int idx = value - min;
+        if (!seen[idx])
+        {
+            seen[idx] = true;
+            values[i] = value;
+            i++;
+        }
+    }
+    RL_FREE(seen);