russell@unturf.com
0d33225dcc
sdl-0001: SDL_gamepad.c SDL_PrivateAddMappingForGUID — O(M) tail walk of s_pSupportedGamepads linked list on every mapping insert → O(M²) bulk load. SDL_GameControllerDB ships >30 000 entries; fix: tail pointer s_pLastSupportedGamepad. box2d-0001: broad_phase.c b2UnBufferMove — linear scan through moveArray to find proxy key on destroy (acknowledged by code comment) → O(N²) on bulk destroy. Fix: index map (proxyKey → slot) for O(1) swap-remove.
105 lines
3.8 KiB
Java
105 lines
3.8 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* SdlTest — sdl-0001
|
||
*
|
||
* Proves CWE-407 in SDL3 SDL_gamepad.c:
|
||
* sdl-0001: SDL_PrivateAddMappingForGUID — tail walk of s_pSupportedGamepads
|
||
* linked list on every insert → O(M²) for M mappings loaded.
|
||
* The SDL_GameControllerDB community database has >30 000 entries.
|
||
*
|
||
* Run: javac -d . SdlTest.java && java -ea unit.SdlTest
|
||
*/
|
||
public class SdlTest {
|
||
|
||
// ── sdl-0001: tail walk on singly-linked list ───────────────────────────
|
||
|
||
/** SLOW: simulate s_pSupportedGamepads — walk to tail on every insert (O(M²)) */
|
||
static long mappingLoadSlow(int mappingCount) {
|
||
// Linked list node: just an index acting as the mapping
|
||
int[] next = new int[mappingCount + 1]; // next[i] = next node, -1 = none
|
||
Arrays.fill(next, -1);
|
||
int head = -1;
|
||
long ops = 0;
|
||
|
||
for (int i = 0; i < mappingCount; i++) {
|
||
// Dedup scan: O(M) walk — SDL_PrivateGetGamepadMappingForGUID
|
||
int cur = head;
|
||
boolean found = false;
|
||
while (cur != -1) {
|
||
ops++;
|
||
if (cur == i) { found = true; break; }
|
||
cur = next[cur];
|
||
}
|
||
if (found) continue;
|
||
|
||
// Tail walk to append: O(M) — SDL_PrivateAddMappingForGUID lines 2213-2217
|
||
if (head == -1) {
|
||
head = i;
|
||
} else {
|
||
int prev = head;
|
||
while (next[prev] != -1) {
|
||
ops++;
|
||
prev = next[prev];
|
||
}
|
||
next[prev] = i;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** FAST: tail pointer + hash-map dedup → O(M) total */
|
||
static long mappingLoadFast(int mappingCount) {
|
||
Set<Integer> seen = new HashSet<>();
|
||
int tail = -1; // tail pointer — s_pLastSupportedGamepad
|
||
long ops = 0;
|
||
|
||
for (int i = 0; i < mappingCount; i++) {
|
||
ops++; // O(1) hash lookup for dedup
|
||
if (seen.add(i)) {
|
||
// O(1) tail-pointer append
|
||
tail = i;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testSdl0001() {
|
||
System.out.println("=== sdl-0001: gamepad mapping bulk load tail walk ===");
|
||
|
||
// Small test — correctness
|
||
int[] sizes = {100, 500, 1000, 5000, 10000};
|
||
for (int M : sizes) {
|
||
long slow = mappingLoadSlow(M);
|
||
long fast = mappingLoadFast(M);
|
||
double ratio = (double) slow / fast;
|
||
System.out.printf(" M=%6d slow_ops=%12d fast_ops=%8d ratio=%.1fx%n",
|
||
M, slow, fast, ratio);
|
||
}
|
||
|
||
// Regression: at M=1000 slow should be >> 2x fast
|
||
long slow1000 = mappingLoadSlow(1000);
|
||
long fast1000 = mappingLoadFast(1000);
|
||
double ratio1000 = (double) slow1000 / fast1000;
|
||
assert ratio1000 > 50.0 :
|
||
"sdl-0001 FAIL: expected slow/fast ratio > 50x at M=1000, got " + ratio1000;
|
||
System.out.println(" [PASS] sdl-0001: ratio=" + String.format("%.1f", ratio1000) + "x at M=1000");
|
||
|
||
// Verify O(M²) vs O(M) growth: ratio at M=5000 should be >> ratio at M=1000
|
||
long slow5000 = mappingLoadSlow(5000);
|
||
long fast5000 = mappingLoadFast(5000);
|
||
double ratio5000 = (double) slow5000 / fast5000;
|
||
assert ratio5000 > ratio1000 * 3 :
|
||
"sdl-0001 FAIL: O(M²) growth expected; ratio5000=" + ratio5000 + " ratio1000=" + ratio1000;
|
||
System.out.println(" [PASS] sdl-0001: O(M²) growth confirmed (ratio5000=" +
|
||
String.format("%.1f", ratio5000) + "x > 3×ratio1000=" +
|
||
String.format("%.1f", ratio1000) + "x)");
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
testSdl0001();
|
||
System.out.println("\nAll SDL tests PASS.");
|
||
}
|
||
}
|