5 files changed, 552 insertions, 0 deletions

diff --git a/simloop/CMakeLists.txt b/simloop/CMakeLists.txt
new file mode 100644
index 0000000..2e0114b
--- /dev/null
+++ b/simloop/CMakeLists.txt
@@ -0,0 +1,29 @@
+cmake_minimum_required(VERSION 3.5)
+
+project(simloop)
+
+set(CMAKE_C_STANDARD 23)
+set(CMAKE_C_STANDARD_REQUIRED On)
+set(CMAKE_C_EXTENSIONS Off)
+
+add_library(simloop
+  include/simloop.h
+  src/simloop.c)
+
+target_include_directories(simloop PUBLIC
+  include)
+
+target_compile_options(simloop PRIVATE -Wall -Wextra -Wpedantic)
+
+# Test
+
+add_executable(simloop_test
+  test/simloop_test.c)
+
+target_link_libraries(simloop_test
+  simloop
+  ctest)
+
+target_compile_options(simloop_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -pedantic)
+
+add_test(NAME simloop_test COMMAND simloop_test --unittest)
diff --git a/simloop/README.md b/simloop/README.md
new file mode 100644
index 0000000..f45ca05
--- /dev/null
+++ b/simloop/README.md
@@ -0,0 +1,99 @@
+# Simulation loop module
+
+Simulation loop for games and graphics applications.
+
+## Features
+
+- Client retains control flow.
+- Client-controlled time axis.
+- Updates are frame-rate capped and use a fixed time step for determinism.
+- Rendering is optionally frame-rate capped.
+- Interpolation factor for smooth animation and rendering between frames.
+
+Control flow: the client steps the loop and then checks whether the simulation
+must be updated and/or the result rendered. Time readings are external to the
+library and provided by the client.
+
+## Invariants
+
+- An initial render of the initial application state is always triggered.
+- The same frame is not re-rendered if time does not advance.
+- Animation interpolation factor in [0,1].
+
+## Handling Time Spikes
+
+Generally, the simulation's update logic should be able to keep up with the
+requested frame rate; it is the application's responsibility to ensure this.
+Specifically, the frequency with which the application loops must be higher
+than the requested update frequency, given by the update delta time.
+
+However, occasional time spikes may occur, for example when switching to the
+desktop or when pausing the application in a debugger. The library handles this
+simply by requesting an update from the application. Under the assumption that
+the loop frequency is higher than the update frequency, the simulation will
+catch up with the real-time clock.
+
+### Time Spikes in Detail
+
+When a time spike occurs, the simulation clock falls significantly behind the
+real-time clock. Ideally, the simulation should be able to recover and catch up
+to the real-time clock when this occurs.
+
+Under a variable time delta, the loop could simply update the simulation with
+a large delta that puts the simulation back into the current clock time.
+Under a fixed time delta, this isn't possible, and we seem to have the
+following choices instead:
+
+- a) Queue as many updates as necessary to bring the simulation back to the
+  current clock time (time_difference / fixed_delta).
+- b) Queue a single update.
+- c) Some middle ground between the two.
+
+The issue with (a) is that, if the simulation is never able to catch up, then
+the number of requested updates at every loop iteration diverges and the
+simulation eventually appears to freeze.
+
+(b) only works if:
+
+- clock time added per iter < desired update delta time
+
+Where:
+
+- clock time added per iter = update time + render time + vsync + etc
+- desired delta time = 1 / update frequency
+
+If the clock time added per iteration is greater or equal to the desired delta,
+then the simulation can never "catch up" and recover from the spike.
+
+The middle ground is to perform only some number of updates in each loop
+iteration N. The simulation catches up only if:
+
+- clock time added per iter < N * desired update delta time
+
+The ideal value of N depends on how many frames the application can actually
+render. For example, if the application is vsync'ed to a 240hz monitor and is
+able to render that many frames, then:
+
+- N = ceil(1/240hz / desired update delta time)
+
+Realistically, the actual frame rate will be variable. Moreover, if we queued
+as many frames as possible, then we would risk the freeze in option (a) if the
+actual update time were too large for the application to catch up. So the
+library can only guess the value of N.
+
+The library picks a small constant value of N, implementation-defined, that the
+application can override.
+
+### Example: Spike Handling with Option (A)
+
+- desired delta = 10ms (100 fps)
+- actual delta = 20ms ( 50 fps)
+
+| iter | sim time | clock time | comment                       |
+|------|----------|------------|-------------------------------|
+| 0    | 0        | 0          | initial state                 |
+| 1    | 0        | 10         | queue 1 update                |
+| 2    | 10       | 30         | queue (30-10)/10  = 2 updates |
+| 3    | 30       | 70         | queue (70-30)/10  = 4 updates |
+| 4    | 70       | 150        | queue (150-70)/10 = 8 updates |
+| ...  |
diff --git a/simloop/include/simloop.h b/simloop/include/simloop.h
new file mode 100644
index 0000000..6a83b23
--- /dev/null
+++ b/simloop/include/simloop.h
@@ -0,0 +1,40 @@
+#pragma once
+
+#include <stdint.h>
+
+typedef uint64_t simloop_time_t; ///< Time delta in nanoseconds.
+
+typedef struct SimloopArgs {
+  int update_fps;     ///< Update frame rate. Must be >0.
+  int max_render_fps; ///< Render frame rate cap. 0 to disable.
+} SimloopArgs;
+
+typedef struct SimloopOut {
+  uint64_t       frame;          ///< Frame counter.
+  simloop_time_t update_elapsed; ///< Amount of time elapsed in the simulation.
+  simloop_time_t update_dt;      ///< Delta time for simulation updates.
+  simloop_time_t throttle;      ///< Render throttle if max render fps is given.
+  double         percent_frame; ///< Percent progress between this frame and
+                                ///< the next. Used for smooth animation.
+  bool should_update;           ///< Whether the simulation should update.
+} SimloopOut;
+
+typedef struct SimloopTimeline {
+  simloop_time_t ddt;  ///< Desired delta time.
+  simloop_time_t time; ///< Time point of the last simulation step.
+} SimloopTimeline;
+
+typedef struct Simloop {
+  simloop_time_t  clock;      ///< Tracks simulation time.
+  uint64_t        frame;      ///< Frame counter, number of updates done.
+  SimloopTimeline update;     ///< Update timeline.
+  simloop_time_t  render_ddt; ///< Desired render delta time.
+} Simloop;
+
+/// Create a simulation loop.
+Simloop simloop_make(const SimloopArgs*);
+
+/// Step the simulation loop.
+///
+/// The simulation always triggers a render of the initial state of simulation.
+void simloop_update(Simloop*, simloop_time_t dt, SimloopOut*);
diff --git a/simloop/src/simloop.c b/simloop/src/simloop.c
new file mode 100644
index 0000000..4fa5f62
--- /dev/null
+++ b/simloop/src/simloop.c
@@ -0,0 +1,78 @@
+#include <simloop.h>
+
+#include <assert.h>
+
+static double min(double a, double b) { return a <= b ? a : b; }
+
+static simloop_time_t ddt_from_fps(int fps) {
+  static constexpr double NANOSECONDS = 1e9;
+  return (fps == 0) ? 0 : (simloop_time_t)(NANOSECONDS / (double)fps);
+}
+
+Simloop simloop_make(const SimloopArgs* args) {
+  assert(args);
+  assert(args->update_fps > 0);
+
+  return (Simloop){
+      .frame = 0,
+      .update =
+          (SimloopTimeline){
+                            .ddt  = ddt_from_fps(args->update_fps),
+                            .time = 0,
+                            },
+      .render_ddt = ddt_from_fps(args->max_render_fps),
+  };
+}
+
+void simloop_update(Simloop* sim, simloop_time_t dt, SimloopOut* out) {
+  assert(sim);
+  assert(out);
+
+  sim->clock += dt;
+
+  // Simulation update.
+  // If the simulation falls behind the clock, we advance by a single ddt
+  // increment per loop iteration here and give it a chance to catch up over
+  // subsequent iterations.
+  // This has the implication that percent_frame can fall out of range (>1) if
+  // we are not careful with how it is defined. See the logic below.
+  // If the delta is too large, then we simply warp the simulation to the wall
+  // clock. This avoids the appearance of the simulation playing in fast-forward
+  // as it tries to catch up. Large time spikes can typically occur at the start
+  // of the simulation when the application loads assets, compiles shaders, etc.
+  static const uint64_t max_catchup_frames = 10;
+  const simloop_time_t  delta              = sim->clock - sim->update.time;
+  const uint64_t        delta_frames       = delta / sim->update.ddt;
+  const bool            update_this_tick   = delta >= sim->update.ddt;
+  const bool            warp               = delta_frames > max_catchup_frames;
+  sim->update.time =
+      warp ? sim->clock
+           : (sim->update.time + (update_this_tick ? sim->update.ddt : 0));
+
+  // Loop-state update.
+  sim->frame += (update_this_tick ? 1 : 0);
+
+  // Interpolator for smooth animation.
+  // If the update falls behind the clock, then percent_frame can fall out of
+  // range (>1) if we are not careful. We impose that it is strictly never >1
+  // to account for this case.
+  assert(sim->update.ddt > 0);
+  assert(sim->update.time <= sim->clock);
+  out->percent_frame = min(
+      1., (double)(sim->clock - sim->update.time) / (double)sim->update.ddt);
+  assert((0. <= out->percent_frame) && (out->percent_frame <= 1.));
+
+  // Render frame rate throttle.
+  // Note that if no max render fps is given, then render_ddt is 0. The logic
+  // works for both render_ddt>0 and =0.
+  // Need to be careful with subtraction since the quantities are unsigned.
+  // Subtract an epsilon to account for delays in thread scheduling.
+  static const simloop_time_t eps = 50'000; // 50us
+  out->throttle =
+      (sim->render_ddt > (dt - eps)) ? (sim->render_ddt - eps - dt) : 0;
+
+  out->frame          = sim->frame;
+  out->update_elapsed = sim->update.time;
+  out->update_dt      = sim->update.ddt;
+  out->should_update  = update_this_tick;
+}
diff --git a/simloop/test/simloop_test.c b/simloop/test/simloop_test.c
new file mode 100644
index 0000000..bcf9d57
--- /dev/null
+++ b/simloop/test/simloop_test.c
@@ -0,0 +1,306 @@
+#include <simloop.h>
+
+#include <test.h>
+
+#include <stdint.h>
+
+// -----------------------------------------------------------------------------
+// Time.
+
+static simloop_time_t time_delta_from_sec(double seconds) {
+  static constexpr double NANOS_PER_SEC = 1e9;
+  return (simloop_time_t)(seconds * NANOS_PER_SEC);
+}
+
+// -----------------------------------------------------------------------------
+// Randomness.
+
+typedef struct {
+  uint64_t a;
+} XorShift64State;
+
+static uint64_t xorshift64(XorShift64State* state) {
+  uint64_t x = state->a;
+  x ^= x << 7;
+  x ^= x >> 9;
+  return state->a = x;
+}
+
+// -----------------------------------------------------------------------------
+// Tests.
+
+/// At time/frame 0, no update is triggered (not enough time passed).
+TEST_CASE(simloop_initial_render) {
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = 10});
+  SimloopOut simout;
+
+  simloop_update(&simloop, 0, &simout);
+
+  TEST_TRUE(!simout.should_update);
+  TEST_EQUAL(simout.frame, 0);
+}
+
+/// The simulation is not updated if time does not advance.
+/// This applies generally to any time > 0.
+TEST_CASE(simloop_render_not_retriggered) {
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = 10});
+  SimloopOut simout;
+
+  // Advance time by some amount to get past t=0.
+  simloop_update(&simloop, 1, &simout);
+
+  // Now "advance" by 0.
+  const uint64_t frame_before = simout.frame;
+  simloop_update(&simloop, 0, &simout);
+  const uint64_t frame_after = simout.frame;
+
+  TEST_TRUE(!simout.should_update);
+  TEST_EQUAL(frame_before, frame_after);
+}
+
+/// A simulation loop with no render frame cap:
+///   1. Updates based on the desired update frame rate.
+///   2. Does not throttle rendering.
+TEST_CASE(simloop_no_render_frame_cap) {
+  constexpr int        UPDATE_FPS = 10; // 100ms delta
+  const simloop_time_t UPDATE_DDT =
+      time_delta_from_sec(1.0 / (double)UPDATE_FPS);
+  const simloop_time_t STEP             = time_delta_from_sec(0.05); // 50ms
+  const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
+
+  // We need simulation time to be an exact multiple of the desired deltas for
+  // the modulo comparison below.
+  TEST_TRUE((UPDATE_DDT % STEP) == 0);
+
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
+  SimloopOut simout;
+
+  simloop_update(&simloop, 0, &simout);
+  TEST_TRUE(!simout.should_update); // Time has not advanced.
+  TEST_EQUAL(simout.throttle, 0);   // No throttling with no render frame cap.
+
+  for (simloop_time_t t = STEP; t <= SIM_DURATION_SEC; t += STEP) {
+    simloop_update(&simloop, STEP, &simout);
+    const bool expect_update = (t % UPDATE_DDT) == 0;
+    TEST_EQUAL(simout.should_update, expect_update);
+    TEST_EQUAL(simout.throttle, 0);
+  }
+}
+
+/// A simulation loop with a render frame cap:
+///   1. Updates based on the desired update frame rate.
+///   2. Throttles rendering based on the desired render frame rate.
+TEST_CASE(simloop_with_render_frame_cap) {
+  constexpr int        UPDATE_FPS = 10; // 100ms delta
+  constexpr int        RENDER_FPS = 5;  // 200ms delta
+  const simloop_time_t UPDATE_DDT =
+      time_delta_from_sec(1.0 / (double)UPDATE_FPS);
+  const simloop_time_t RENDER_DDT =
+      time_delta_from_sec(1.0 / (double)RENDER_FPS);
+  const simloop_time_t STEP             = time_delta_from_sec(0.1); // 100ms
+  const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
+
+  // We need simulation time to be an exact multiple of the desired deltas for
+  // the modulo comparisons below.
+  TEST_TRUE((UPDATE_DDT % STEP) == 0);
+
+  Simloop simloop = simloop_make(
+      &(SimloopArgs){.update_fps = UPDATE_FPS, .max_render_fps = RENDER_FPS});
+  SimloopOut simout;
+
+  simloop_update(&simloop, 0, &simout);
+  TEST_TRUE(!simout.should_update); // Time has not advanced.
+  TEST_EQUAL(simout.throttle, 0);   // No throttle since time has not advanced.
+
+  for (simloop_time_t t = STEP; t <= SIM_DURATION_SEC; t += STEP) {
+    simloop_update(&simloop, STEP, &simout);
+    TEST_EQUAL(simout.should_update, (t % UPDATE_DDT) == 0);
+    TEST_NOTEQUAL(simout.throttle, 0);
+  }
+}
+
+/// If the update falls behind the clock, then percent_frame can fall out of
+/// range (>1) if we are not careful. This tests for this condition.
+TEST_CASE(simloop_percent_frame_01_large_jump) {
+  constexpr int        UPDATE_FPS = 10; // 100ms delta
+  const simloop_time_t UPDATE_DDT =
+      time_delta_from_sec(1.0 / (double)UPDATE_FPS);
+  const simloop_time_t STEP             = time_delta_from_sec(1);
+  const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
+
+  // We need simulation time to be an exact multiple of the desired deltas for
+  // the modulo comparison below.
+  TEST_TRUE((STEP % UPDATE_DDT) == 0);
+
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
+  SimloopOut simout;
+
+  simloop_update(&simloop, 0, &simout);
+  TEST_TRUE(!simout.should_update); // Time has not advanced.
+
+  for (simloop_time_t t = STEP; t <= SIM_DURATION_SEC; t += STEP) {
+    simloop_update(&simloop, STEP, &simout);
+    TEST_TRUE(simout.should_update); // Tries to catch up to clock.
+    TEST_TRUE(0. <= simout.percent_frame);
+    TEST_TRUE(simout.percent_frame <= 1.);
+  }
+}
+
+/// One benefit of fixed over variable time deltas is determinism. Test for
+/// this by getting to t=10 by different clock time increments.
+///
+/// Note that the time increments must be able to keep up with the desired frame
+/// delta, otherwise determinism is not maintained. We can guarantee determinism
+/// at the expense of re-introducing divergence.
+/// TODO: Perhaps the API should return an update count instead of a boolean,
+///  advance simulation time per the number of updates, then leave it up to
+///  the client to decide whether to update just once or as many times as
+///  requested, depending on whether they want determinism or convergence.
+TEST_CASE(simloop_determinism) {
+  constexpr int        UPDATE_FPS     = 100; // 10ms delta
+  const simloop_time_t RANDOM_STEPS[] = {
+      time_delta_from_sec(0.007), // 7ms
+      time_delta_from_sec(0.005), // 5ms
+      time_delta_from_sec(0.003), // 3ms
+  };
+  constexpr uint64_t NUM_RANDOM_STEPS =
+      sizeof(RANDOM_STEPS) / sizeof(RANDOM_STEPS[0]);
+  const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(10);
+  constexpr float      ADD              = 0.123f;
+
+  typedef struct Simulation {
+    int   iter_count;
+    float sum;
+  } Simulation;
+
+#define UPDATE_SIMULATION(SIM) \
+  {                            \
+    SIM.sum += ADD;            \
+    SIM.iter_count++;          \
+  }
+
+  Simulation      sim[2] = {0};
+  XorShift64State xss    = (XorShift64State){12069019817132197873ULL};
+
+  // Perform two simulations with random clock-time steps.
+  for (int s = 0; s < 2; ++s) {
+    simloop_time_t dt  = 0;
+    Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
+    SimloopOut simout;
+
+    for (simloop_time_t t = 0; t <= SIM_DURATION_SEC;) {
+      simloop_update(&simloop, dt, &simout);
+
+      if (simout.should_update) {
+        UPDATE_SIMULATION(sim[s]);
+      }
+
+      // Advance time with a random step.
+      const simloop_time_t step =
+          RANDOM_STEPS[xorshift64(&xss) % NUM_RANDOM_STEPS];
+      t += step;
+      dt = step;
+    }
+  }
+
+  // Make sure the simulations have advanced by the same number of updates so
+  // that we can compare them. They may not have had the same update count
+  // depending on the clock-time steps.
+  while (sim[0].iter_count < sim[1].iter_count) {
+    UPDATE_SIMULATION(sim[0]);
+  }
+  while (sim[1].iter_count < sim[0].iter_count) {
+    UPDATE_SIMULATION(sim[1]);
+  }
+  TEST_EQUAL(sim[0].iter_count, sim[1].iter_count);
+
+  // The sums should be exactly equal if determinism holds.
+  // Check also that they are non-zero to make sure the simulation actually
+  // advanced.
+  TEST_TRUE(sim[0].sum > 0.f);
+  TEST_EQUAL(sim[0].sum, sim[1].sum);
+}
+
+/// The simulation loop attempts to catch up with the clock in the event of a
+/// time spike.
+///
+/// Catch-up is possible only if the simulation loops with a frequency higher
+/// than the requested update frequency given by the update delta time.
+///
+/// Catch-up is performed only for sufficiently small time spikes. For large
+/// time spikes, the simulation clock is warped. This test is for the small
+/// time spike case.
+static void simloop_catch_up(
+    struct test_case_metadata* metadata, int update_ddt_ms, int loop_step_ms,
+    bool expect_catchup) {
+  const int            UPDATE_FPS = 1000 / update_ddt_ms;
+  const simloop_time_t UPDATE_DDT =
+      time_delta_from_sec(1.0 / (double)UPDATE_FPS);
+  const simloop_time_t STEP =
+      time_delta_from_sec((double)loop_step_ms / 1000.0);
+  const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
+  const int            EXPECTED_TOTAL_FRAMES_WITH_CATCHUP =
+      (int)(SIM_DURATION_SEC / UPDATE_DDT);
+
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
+  SimloopOut simout;
+  int        frames = 0;
+
+  // Simulate a time spike.
+  // Advance time to t=1s. That is a lag of 1,000ms / 100ms = 10 frames.
+  // 10 frames is the maximum allowed catch-up.
+  // The simulation now has 29s to catch up.
+  simloop_time_t dt = time_delta_from_sec(1);
+  for (simloop_time_t t = dt; t <= SIM_DURATION_SEC;) {
+    simloop_update(&simloop, dt, &simout);
+
+    if (simout.should_update) {
+      frames++;
+    }
+
+    // New delta is as usual.
+    dt = STEP;
+    t += dt;
+  }
+
+  if (expect_catchup) {
+    TEST_EQUAL(frames, EXPECTED_TOTAL_FRAMES_WITH_CATCHUP);
+  } else {
+    TEST_TRUE(frames < EXPECTED_TOTAL_FRAMES_WITH_CATCHUP);
+  }
+}
+/// (Loop frequency > update frequency) => successful catch-up.
+TEST_CASE(simloop_catch_up_success) {
+  constexpr int UPDATE_DDT_MS = 100;
+  constexpr int LOOP_DDT_MS   = 10;
+  simloop_catch_up(metadata, UPDATE_DDT_MS, LOOP_DDT_MS, true);
+}
+/// (Loop frequency < update frequency) => failed catch-up.
+TEST_CASE(simloop_catch_up_failure) {
+  constexpr int UPDATE_DDT_MS = 10;
+  constexpr int LOOP_DDT_MS   = 100;
+  simloop_catch_up(metadata, UPDATE_DDT_MS, LOOP_DDT_MS, false);
+}
+
+/// This tests the large time spike case, where the simulation clock is warped
+/// to the wall clock.
+TEST_CASE(simloop_warp) {
+  const int            UPDATE_FPS = 50;
+  const simloop_time_t UPDATE_DDT =
+      time_delta_from_sec(1.0 / (double)UPDATE_FPS);
+
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
+  SimloopOut simout;
+
+  // The maximum allowed catch-up is 10 frames. Simulate a time spike larger
+  // than that.
+  const simloop_time_t TIME_SPIKE = UPDATE_DDT * 20;
+  simloop_update(&simloop, TIME_SPIKE, &simout);
+  TEST_TRUE(simout.should_update); // Warp should still request update.
+
+  // Now "advance" by 0.
+  simloop_update(&simloop, 0, &simout);
+  TEST_TRUE(!simout.should_update); // No more updates after warp.
+}
+
+int main() { return 0; }