Skip to content

Instantly share code, notes, and snippets.

@DavidEGrayson

DavidEGrayson/range_checker_test.c

Created October 31, 2025 15:04
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save DavidEGrayson/467e9b32ba62f53947bcce8011d8881b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save DavidEGrayson/467e9b32ba62f53947bcce8011d8881b to your computer and use it in GitHub Desktop.
Download ZIP
Code and test suite for a C function that checks evaluates the possibility of picking an offset 'd' between 'd_min' and 'd_max' such that a + d = b where all we know about a and be are a range of possible values they might have.
Raw
range_checker_test.c
#include <stdio.h>
#include <stdint.h>
#define XLEN 4
typedef uint8_t TSize;
_Static_assert(sizeof(TSize) * 8 >= XLEN);
const TSize mask = (1 << XLEN) - 1;
#define M(x) ((x) & mask)
#define OUT_OF_RANGE -1
#define MAYBE_IN_RANGE 0
#define IN_RANGE 1
// This function evaluates the possibility of picking an offset 'd'
// between 'd_min' and 'd_max' such that a + d = b, where a and b are
// addresses in the program which will be determined later, and for now
// all we know is that a is between 'a_min' and 'a_max', and b is between
// 'b_min' and 'b_max'. Returns OUT_OF_RANGE, MAYBE_IN_RANGE, or IN_RANGE.
// Note that "between X and Y" means that it is in the sequence
// X, X+1, ... Y, which includes Y and which might wrap around.
// Note that every value in sight is in the integers modulo (1 << XLEN), so
// addition is defined to be addition modulo (1 << XLEN) and can overflow.
static int check_range(TSize a_min, TSize a_max, TSize d_min, TSize d_max,
TSize b_min, TSize b_max)
{
#ifdef ZOOM
printf("entry: %u,%u, %u,%u, %u,%u\n", a_min, a_max, d_min, d_max, b_min, b_max);
#endif
// Since the equation is 'a + d = b', we can add a constant to 'a' and subtract it
// from 'd' without changing the answer. Let's set the constant equal to d_min,
// so that d_min becomes 0 and we can ignore it for the rest of the function.
a_min = M(a_min + d_min);
a_max = M(a_max + d_min);
d_max = M(d_max - d_min);
d_min = 0;
if (d_max == M(-1))
{
// Any point can reach any other point.
return IN_RANGE;
}
#ifdef ZOOM
printf("1: %u,%u, %u,%u, %u,%u\n", a_min, a_max, d_min, d_max, b_min, b_max);
#endif
// We can also subtract a constant from 'a' and 'b' without changing the answer.
// Let's do that with a_max so that a_max becomes 0 (for now).
a_min = M(a_min - a_max);
b_min = M(b_min - a_max);
b_max = M(b_max - a_max);
a_max = 0;
#ifdef ZOOM
printf("2: %u,%u, %u,%u, %u,%u\n", a_min, a_max, d_min, d_max, b_min, b_max);
#endif
// We want to find the set of values reachable from all 'a'.
// The set of numbers reachable from a_max is 0...d_max.
// For the next lowest possible value of a (if there is one), the set of numbers reachable
// from it only extends up to d_max - 1, so when we intersect that with the first set, the
// result is to move the upper bound down by one.
// Going on like this, we see that we have to shrink the upper bound of that set -a_min times
// to get the full intersection of all the sets. (That's how many iterations it takes
// for the lower bound of the set to go from 0 == a_max down to a_min.)
// For a_min, the upper end of its reachable set is a_min + d_max.
// (Note that the lower end of this set might intersect the upper end of the original set,
// so we can't just phrase this as a problem of two intersecting sets.)
// The intersection of all those sets is empty if and only if there was underflow while we walked
// from d_max to a_min + d_max, which is equivalent to a_min + d_max > d_max.
TSize upper = M(a_min + d_max);
if (upper <= d_max)
{
// The range of numbers that are reachable from any possible value of a
// is precisely 0...upper.
if (b_min <= b_max && b_max <= upper)
{
// Every possible b value is within that range.
return IN_RANGE;
}
}
// Rebase it so a_min becomes 0.
a_max = M(a_max - a_min);
b_min = M(b_min - a_min);
b_max = M(b_max - a_min);
a_min = 0;
#ifdef ZOOM
printf("3: %u,%u, %u,%u, %u,%u\n", a_min, a_max, d_min, d_max, b_min, b_max);
#endif
// The set of values possibly reachable by some value of 'a' is the union of
// 1. 0...a_max (which are reachable from the 'a' equal to said value), and
// 2. a_max...(a_max+d_max) (which are reachable from a_max).
upper = M(a_max + d_max);
if (upper < a_max)
{
// There is an overflow in a_max+d_max, so every number is reachable by some a.
return MAYBE_IN_RANGE;
}
else
{
// The numbers that are reachable by some 'a' are precisely 0...(a_max+d_max).
// So we just have to see if that intersects with b_min...b_max.
if (b_min <= upper || b_max < b_min)
{
// The range of possible b values intersects, so maybe it is in range.
return MAYBE_IN_RANGE;
}
}
return OUT_OF_RANGE;
}
static int check_range_brute(TSize a_min, TSize a_max, TSize d_min, TSize d_max,
TSize b_min, TSize b_max)
{
bool sometimes_in_range = false;
bool sometimes_out_of_range = false;
TSize a = a_min;
while (1)
{
TSize b = b_min;
while (1)
{
TSize diff = M(b - a);
if (d_min <= d_max)
{
if (d_min <= diff && diff <= d_max)
{
sometimes_in_range = true;
}
else
{
sometimes_out_of_range = true;
}
}
else
{
if (diff <= d_max || d_min <= diff)
{
sometimes_in_range = true;
}
else
{
sometimes_out_of_range = true;
}
}
if (b == b_max) { break; }
b = M(b + 1);
}
if (a == a_max) { break; }
a = M(a + 1);
}
return sometimes_in_range - sometimes_out_of_range;
}
int main()
{
#ifdef ZOOM
printf("result = %d\n", check_range(4,6,6,6,6,6));
printf("brute = %d\n", check_range_brute(4,6,6,6,6,6));
return 0;
#endif
const uint64_t tc_mask = (1 << (6 * XLEN)) - 1;
uint64_t test_case = 0;
size_t test_count = 0;
while (1)
{
uint64_t c = test_case;
TSize
a_min = M(c >> (0 * XLEN)),
a_max = M(c >> (1 * XLEN)),
d_min = M(c >> (2 * XLEN)),
d_max = M(c >> (3 * XLEN)),
b_min = M(c >> (4 * XLEN)),
b_max = M(c >> (5 * XLEN));
int result = check_range(a_min, a_max, d_min, d_max, b_min, b_max);
int result_brute = check_range_brute(a_min, a_max, d_min, d_max, b_min, b_max);
if (result != result_brute)
{
printf("ERROR! %u,%u,%u,%u,%u,%u: expected %d, got %d\n",
a_min, a_max, d_min, d_max, b_min, b_max, result_brute, result);
}
test_count++;
test_case += 0x807E2889D833FB69; // random odd number
if ((test_case & tc_mask) == 0)
{
break;
}
}
printf("test cases: %zu\n", test_count);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment