155 lines
4.4 KiB
C++
155 lines
4.4 KiB
C++
/*
|
|
* Unit test for fs-uae-0001: CWE-407 O(N) confname linear scan in inputdevice.cpp
|
|
*
|
|
* Models the defect: inputdevice_geteventid / readevent / inputdevice_uaelib
|
|
* all scan a 544-entry events[] array by strcmp on every call.
|
|
*
|
|
* The fix uses an unordered_map for O(1) lookup.
|
|
*
|
|
* This test:
|
|
* 1. Builds a synthetic events[] of N=544 entries (matching real count).
|
|
* 2. Times B=800 lookups (100 bindings * 8 sub-events each) using:
|
|
* a. Naive O(N) linear scan (defect)
|
|
* b. unordered_map O(1) lookup (fix)
|
|
* 3. Asserts ratio >= 10x speedup.
|
|
* 4. Asserts correctness: both return the same index.
|
|
*
|
|
* Compile: g++ -O2 -std=c++17 -o test_fs_uae_0001 test_fs_uae_0001.cpp
|
|
* Run: ./test_fs_uae_0001
|
|
*/
|
|
|
|
#include <algorithm>
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <string>
|
|
#include <unordered_map>
|
|
#include <vector>
|
|
|
|
/* ---- synthetic event table matching FS-UAE structure ---- */
|
|
|
|
struct inputevent {
|
|
const char *name; /* friendly name */
|
|
const char *confname; /* config file key — the lookup key */
|
|
int data;
|
|
};
|
|
|
|
static const int N_EVENTS = 544; /* matches real inputevents.def count */
|
|
|
|
/* Generate N_EVENTS entries with confname "EVENT_NNNN" */
|
|
static std::vector<std::string> g_confnames;
|
|
static std::vector<inputevent> g_events;
|
|
|
|
static void build_table(void)
|
|
{
|
|
g_confnames.reserve(N_EVENTS + 2);
|
|
g_events.reserve(N_EVENTS + 2);
|
|
|
|
/* sentinel at index 0 */
|
|
g_confnames.push_back("");
|
|
g_events.push_back({nullptr, nullptr, 0});
|
|
|
|
for (int i = 1; i <= N_EVENTS; i++) {
|
|
g_confnames.push_back("EVENT_" + std::to_string(i));
|
|
g_events.push_back({g_confnames.back().c_str(),
|
|
g_confnames.back().c_str(), i});
|
|
}
|
|
/* terminal sentinel */
|
|
g_confnames.push_back("");
|
|
g_events.push_back({nullptr, nullptr, 0});
|
|
}
|
|
|
|
/* ---- defect: O(N) linear scan ---- */
|
|
|
|
static int linear_lookup(const char *s)
|
|
{
|
|
for (int i = 1; g_events[i].name; i++) {
|
|
if (strcmp(g_events[i].confname, s) == 0)
|
|
return i;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/* ---- fix: O(1) hash map ---- */
|
|
|
|
static std::unordered_map<std::string, int> s_map;
|
|
|
|
static void build_map(void)
|
|
{
|
|
s_map.reserve(N_EVENTS * 2);
|
|
for (int i = 1; g_events[i].name; i++)
|
|
s_map[g_events[i].confname] = i;
|
|
}
|
|
|
|
static int map_lookup(const char *s)
|
|
{
|
|
auto it = s_map.find(s);
|
|
return (it != s_map.end()) ? it->second : 0;
|
|
}
|
|
|
|
/* ---- benchmark helpers ---- */
|
|
|
|
using us_t = long long;
|
|
|
|
static us_t now_us(void)
|
|
{
|
|
return std::chrono::duration_cast<std::chrono::microseconds>(
|
|
std::chrono::steady_clock::now().time_since_epoch()).count();
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
build_table();
|
|
build_map();
|
|
|
|
/* Lookups representative of 100 key bindings * 8 sub-events each.
|
|
* Half look up entries near the end (worst case for linear scan). */
|
|
static const int B = 800;
|
|
std::vector<std::string> queries;
|
|
queries.reserve(B);
|
|
for (int k = 0; k < B; k++) {
|
|
/* Alternate between middle and end entries to stress linear scan */
|
|
int idx = (k % 2 == 0)
|
|
? (N_EVENTS / 2 + k % (N_EVENTS / 2))
|
|
: (N_EVENTS - 1 - k % (N_EVENTS / 2));
|
|
if (idx < 1) idx = 1;
|
|
if (idx > N_EVENTS) idx = N_EVENTS;
|
|
queries.push_back("EVENT_" + std::to_string(idx));
|
|
}
|
|
|
|
/* --- correctness check --- */
|
|
for (int k = 0; k < B; k++) {
|
|
int r_linear = linear_lookup(queries[k].c_str());
|
|
int r_map = map_lookup(queries[k].c_str());
|
|
assert(r_linear > 0 && "linear_lookup failed");
|
|
assert(r_linear == r_map && "map result differs from linear result");
|
|
}
|
|
|
|
/* --- timing: linear --- */
|
|
volatile int sink = 0;
|
|
us_t t0 = now_us();
|
|
for (int rep = 0; rep < 1000; rep++) {
|
|
for (int k = 0; k < B; k++)
|
|
sink += linear_lookup(queries[k].c_str());
|
|
}
|
|
us_t linear_us = now_us() - t0;
|
|
|
|
/* --- timing: map --- */
|
|
us_t t1 = now_us();
|
|
for (int rep = 0; rep < 1000; rep++) {
|
|
for (int k = 0; k < B; k++)
|
|
sink += map_lookup(queries[k].c_str());
|
|
}
|
|
us_t map_us = now_us() - t1;
|
|
(void)sink;
|
|
|
|
double ratio = (map_us > 0) ? (double)linear_us / (double)map_us : 9999.0;
|
|
|
|
printf("PASS fs-uae-0001 N=%d B=%d linear=%lld us map=%lld us ratio=%.1fx\n",
|
|
N_EVENTS, B, linear_us, map_us, ratio);
|
|
|
|
assert(ratio >= 10.0 && "speedup < 10x — fix may not be applied");
|
|
|
|
return 0;
|
|
}
|