117 lines
2.9 KiB
Markdown
117 lines
2.9 KiB
Markdown
# 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:
|
||
|
||
```c
|
||
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:
|
||
|
||
```c
|
||
// 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
|
||
|
||
```diff
|
||
--- 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);
|
||
```
|