| #include <stdio.h> |
| #include <stdlib.h> |
| |
| // Simple REM test case. Tests some basic properties of remainder |
| // operation. |
| |
| // All macros must evaluate to true. x,y can be signed/unsigned, m |
| // should be unsigned. |
| |
| // Returns true if multiplication will overflow. |
| #define MultOverflow(x,y) ((((x) * (y)) / (y)) != (x)) |
| |
| // x == y => (x mod m) == (y mod m) |
| #define CongruenceTest(x,y,m) \ |
| (((x) != (y)) || (((x) % (m)) == ((y) % (m)))) |
| |
| |
| /****************************************************************** |
| * These three tests can be done only for unsigned case because they |
| * contain add/sub. If you're eager to get this working with signed |
| * numbers, take care of overflows. |
| ******************************************************************/ |
| |
| // Return true if add/sub will cause overflow. |
| #define UnsignedAddOverflow(x,y) (((x) + (y)) < (x)) |
| #define UnsignedSubUnderflow(x,y) (((x) - (y)) > (x)) |
| |
| // ((x % m) + (y % m)) % m = (x + y) % m |
| #define AdditionOfCongruences(x,y,m) \ |
| (UnsignedAddOverflow((x)%(m),(y)%(m)) || \ |
| UnsignedAddOverflow((x),(y)) || \ |
| (((((x) % (m)) + ((y) % (m))) % m) == (((x) + (y)) % (m)))) |
| |
| // ((x % m) == ((y + z) % m)) == (((x - z) % m) == (y % m)) |
| #define SimpleCongruenceEquation(x,y,z,m) \ |
| (UnsignedAddOverflow((y),(z)) || \ |
| UnsignedSubUnderflow((x),(z)) || \ |
| ((((x) % (m)) == (((y) + (z)) % (m))) % m) == \ |
| ((((x) - (z)) % (m)) == ((y) % (m)))) |
| |
| // If y*m does not overflow: (x % m) == (x + y*m) % m |
| #define AdditionOfMultipleOfModIsNOP(x,y,m) \ |
| (MultOverflow(y,m) || \ |
| UnsignedAddOverflow((x),(y)*(m)) || \ |
| (((x) % (m)) == (((x) + ((y)*(m))) % (m)))) |
| |
| /******************************************************************/ |
| |
| // Greatest common divisor |
| long gcd(long a, long b) { |
| long c; |
| while(1) { |
| c = a % b; |
| if(c == 0) return b; |
| a = b; |
| b = c; |
| } |
| } |
| |
| // If gcd(z,m)==1: ((x == y) % m) == ((x / z == y / z) % m). This holds |
| // only if both sides are actually divisble by z. |
| #define BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x,y,z,m) \ |
| ((gcd((z),(m)) != 1) || ((z) == 0) || \ |
| (gcd((x),(z)) != (z)) || ((gcd((y),(z)) != (z))) || \ |
| (((x) % (m)) == ((y) % (m))) == (((((x) / (z)) % m) == (((y) / (z))) % m))) |
| |
| // If z divides x,y,m: ((x % m) == (y % m)) == (((x/z) % (m/z)) == ((y/z) % (m/z))) |
| #define DivideBothSidesAndModulus(x,y,z,m) \ |
| (((z) == 0) || (gcd((x),(z)) != (z)) || \ |
| (gcd((y),(z)) != (z)) || \ |
| (gcd((m),(z)) != (z)) || \ |
| (((x)%(m)) == ((y)%(m))) == \ |
| ((((x)/(z)) % ((m)/(z))) == (((y)/(z)) % ((m)/(z))))) |
| |
| // If z divides m, than: ((x % m) == (y % m)) == ((x % z) == (y % z)) |
| // z should be unsigned. |
| #define SubModulusTest(x,y,z,m) \ |
| (((z) == 0) || (gcd((m),(z)) != (z)) || \ |
| ((((x)%(m)) == ((y)%(m))) == (((x)%(z)) == ((y)%(z))))) |
| |
| // Runs the test c under number t. |
| #define test(t,c) \ |
| if (!c) { \ |
| printf("Test #%u, failed in iteration #: %u\n", t, idx); \ |
| printf("Failing test vector:\n"); \ |
| printf("m=%u, x_u=%u, y_u=%u, z_u=%u, x_s=%d, y_s=%d, z_s=%d\n", \ |
| m, x_u, y_u, z_u, x_s, y_s, z_s); \ |
| return 1; \ |
| } |
| |
| // The higher the number the better the testing. |
| #define ITERATIONS 100 |
| |
| int main(int argc, char **argv) { |
| // Since the test vectors are printed out anyways, I suggest leaving |
| // the test nondeterministic. Many people run tests on various |
| // machines, so REM-related code will be covered with a much better |
| // coverage... If you really don't like the idea of having better |
| // coverage, uncomment the following line: |
| |
| //srand(0xA392049F); |
| |
| unsigned idx = 0; |
| for (; idx < ITERATIONS; ++idx) { |
| unsigned m = (unsigned)rand(); |
| |
| if (m == 0) { // Repeat again |
| idx--; continue; |
| } |
| |
| unsigned x_u = (unsigned)rand(); |
| unsigned y_u = (unsigned)rand(); |
| unsigned z_u = (unsigned)rand(); |
| |
| int x_s = (rand() % 2) ? rand() : -rand(); |
| int y_s = (rand() % 2) ? rand() : -rand(); |
| int z_s = (rand() % 2) ? rand() : -rand(); |
| |
| test(1, CongruenceTest(x_s, y_s, m)); |
| test(2, CongruenceTest(x_s, y_u, m)); |
| test(3, CongruenceTest(x_u, y_s, m)); |
| test(4, CongruenceTest(x_u, y_u, m)); |
| |
| test(5, AdditionOfCongruences(x_u, y_u, m)); |
| |
| test(6, SimpleCongruenceEquation(x_u, y_u, z_u, m)); |
| |
| test(7, AdditionOfMultipleOfModIsNOP(x_u, y_u, m)); |
| |
| test(8, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_s, y_s, z_s, m)); |
| test(9, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_s, y_s, z_u, m)); |
| test(10, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_s, y_u, z_s, m)); |
| test(11, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_s, y_u, z_u, m)); |
| test(12, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_u, y_s, z_s, m)); |
| test(13, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_u, y_s, z_u, m)); |
| test(14, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_u, y_u, z_s, m)); |
| test(15, BothSidesCanBeDividedWithDivisorMutuallyPrimeWithMod(x_u, y_u, z_u, m)); |
| |
| test(16, DivideBothSidesAndModulus(x_s, y_s, z_s, m)); |
| test(17, DivideBothSidesAndModulus(x_s, y_s, z_u, m)); |
| test(18, DivideBothSidesAndModulus(x_s, y_u, z_s, m)); |
| test(19, DivideBothSidesAndModulus(x_s, y_u, z_u, m)); |
| test(20, DivideBothSidesAndModulus(x_u, y_s, z_s, m)); |
| test(21, DivideBothSidesAndModulus(x_u, y_s, z_u, m)); |
| test(22, DivideBothSidesAndModulus(x_u, y_u, z_s, m)); |
| test(23, DivideBothSidesAndModulus(x_u, y_u, z_u, m)); |
| |
| test(25, SubModulusTest(x_s, y_s, z_u, m)); |
| test(27, SubModulusTest(x_s, y_u, z_u, m)); |
| test(29, SubModulusTest(x_u, y_s, z_u, m)); |
| test(31, SubModulusTest(x_u, y_u, z_u, m)); |
| } |
| printf("\n *** REM test done! ***\n"); |
| return 0; |
| } |