diff options
Diffstat (limited to 'modules/Saturation')
| -rw-r--r-- | modules/Saturation/module.jai | 26 | ||||
| -rw-r--r-- | modules/Saturation/tests.jai | 397 |
2 files changed, 384 insertions, 39 deletions
diff --git a/modules/Saturation/module.jai b/modules/Saturation/module.jai index 74643e0..50c9b3c 100644 --- a/modules/Saturation/module.jai +++ b/modules/Saturation/module.jai @@ -1,5 +1,7 @@ // Integer saturating arighmetic (with assembly branch-free procedures for x64 - expecting signed values in two's complement). +#module_parameters(PREFER_BRANCH_FREE_CODE := false); + #import "Basic"; #import "Math"; #import "String"; @@ -37,11 +39,11 @@ INTEGER_ARITHMETIC_TYPES_CHECK :: #string DONE return true; DONE -add :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } +add :: (x: $Tx, y: $Ty, $prefer_branch_free_code := PREFER_BRANCH_FREE_CODE) -> result: $Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } { + + #if !(prefer_branch_free_code && CPU == .X64) { - #if USE_GENERIC || CPU != .X64 { - #if Tr == s8 || Tr == s16 || Tr == s32 || Tr == s64 { #if Tr == s8 { MAX :: S8_MAX; MIN :: S8_MIN; } @@ -66,7 +68,7 @@ add :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: b return x + y, false; } else { - + result: Tr = ---; saturated: bool = ---; @@ -118,10 +120,10 @@ add :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: b } } -sub :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } +sub :: (x: $Tx, y: $Ty, $prefer_branch_free_code := PREFER_BRANCH_FREE_CODE) -> result: $Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } { - #if USE_GENERIC || CPU != .X64 { + #if !(prefer_branch_free_code && CPU == .X64) { #if Tr == s8 || Tr == s16 || Tr == s32 || Tr == s64 { @@ -195,10 +197,10 @@ sub :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: b } -mul :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } +mul :: (x: $Tx, y: $Ty, $prefer_branch_free_code := PREFER_BRANCH_FREE_CODE) -> result: $Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } { - #if USE_GENERIC || CPU != .X64 { + #if !(prefer_branch_free_code && CPU == .X64) { #if Tr == s8 || Tr == s16 || Tr == s32 || Tr == s64 { @@ -286,10 +288,10 @@ mul :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, saturated: b } } -div :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, remainder: Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } +div :: (x: $Tx, y: $Ty, $prefer_branch_free_code := PREFER_BRANCH_FREE_CODE) -> result: $Tr, remainder: Tr, saturated: bool #modify { #insert INTEGER_ARITHMETIC_TYPES_CHECK; } { - #if USE_GENERIC || CPU != .X64 { + #if !(prefer_branch_free_code && CPU == .X64) { #if Tr == s8 || Tr == s16 || Tr == s32 || Tr == s64 { @@ -380,11 +382,11 @@ div :: (x: $Tx, y: $Ty, $USE_GENERIC: bool = false) -> result: $Tr, remainder: T #asm { result === a; // Pin result to register A. remainder === d; // Pin remainder to register D. - + xor result, result; // Clear result. xor remainder, remainder; // Clear remainder (required when used as dividend's high bits). xor saturated, saturated; // Clear saturated (unsigned division never saturates). - mov result, x; // Copy x value to result. + mov.SIZE result, x; // Copy x value to result. DIVIDE_PLACEHOLDER } diff --git a/modules/Saturation/tests.jai b/modules/Saturation/tests.jai index 372d66d..2a82300 100644 --- a/modules/Saturation/tests.jai +++ b/modules/Saturation/tests.jai @@ -1,5 +1,7 @@ // Tests for integer saturating arighmetic procedures. +AVOID_INFINITE_FOR_LOOP :: true; + #import "Basic"; #import "Compiler"; #import "Math"; @@ -12,36 +14,41 @@ main :: () { "#=======================#\n", "# Basic tests #\n" ); + + + test_op :: ($operation: string, x: $Tx, y: $Ty, result: $Tr, type: Type, saturated: bool, remainder: Tr = 0) -> errors_found: int #expand { + + #insert #run () -> string { + // Build test call. + builder: String_Builder; + call := ifx operation == "div" + then "t_result, t_remainder, t_saturated := %(cast(Tx)x, cast(Ty)y);" + else "t_result, t_saturated := %(cast(Tx)x, cast(Ty)y);"; + + print(*builder, call, operation); - test_op :: (operation: string, x: $Tx, y: $Ty, result: $Tr, type: Type, saturated: bool, remainder: Tr = 0) -> errors_found: int #expand { - - print_test_call :: (operation: string) -> string { - str: string = ---; - if operation != "div" { - TEST_CALL :: #string DONE - t_result, t_saturated := OP(cast(Tx)x, cast(Ty)y); - if result != t_result print("%_%(%, %) = %0%0\n", operation, type, x, y, result, ifx saturated then " : saturated"); - DONE - str = replace(TEST_CALL, "OP", operation); - } else { - TEST_CALL :: #string DONE - t_result, t_remainder, t_saturated := OP(cast(Tx)x, cast(Ty)y); - if result != t_result print("%_%(%, %) = % + %0%0\n", operation, type, x, y, result, remainder, ifx saturated then " : saturated"); - DONE - str = replace(TEST_CALL, "OP", operation); - } - return str; - } - - #insert #run print_test_call(operation); + return builder_to_string(*builder); + }(); errors := 0; - if result != t_result { errors += 1; print(" > incorrect result value: got % expected %\n", t_result, result); }; - if type != type_of(t_result) { errors += 1; print(" > incorrect result type: got % expected %\n", type_of(t_result), type); }; - if saturated != t_saturated { errors += 1; print(" > incorrect saturated flag: got % expected %\n", t_saturated, saturated); }; + log: String_Builder; + if result != t_result { errors += 1; print(*log, " > incorrect result value: got % expected %\n", t_result, result); }; + if type != type_of(t_result) { errors += 1; print(*log, " > incorrect result type: got % expected %\n", type_of(t_result), type); }; + if saturated != t_saturated { errors += 1; print(*log, " > incorrect saturated flag: got % expected %\n", t_saturated, saturated); }; #if operation == "div" { - if remainder != t_remainder { errors += 1; print(" > incorrect remainder value: got % expected %\n", t_remainder, remainder); }; + if remainder != t_remainder { errors += 1; print(*log, " > incorrect remainder value: got % expected %\n", t_remainder, remainder); }; } + + if errors > 0 { + #if operation == "div" { + print("%_%(%, %) = % + %0%0\n", operation, type, x, y, result, remainder, ifx saturated then " : saturated"); + } + else { + print("%_%(%, %) = %0%0\n", operation, type, x, y, result, ifx saturated then " : saturated"); + } + write_builder(*log); + } + return errors; } @@ -157,6 +164,342 @@ main :: () { if errors > 0 print("# Found % %!\n", errors, ifx errors == 1 then "error" else "errors"); else print(" No errors found.\n"); + + // Test generic agains branch-free alternative. + write_strings( + "#=======================#\n", + "# generic == x64 asm ? #\n" + ); + + + full_test :: ($type: Type, test: (a: type, b: type)) { + #if type == { + case u8; + min :u8 = 0; + max :u8 = U8_MAX; + + case u16; + min :u16 = 0; + max :u16 = U16_MAX; + + case s8; + min :s8 = S8_MIN; + max :s8 = S8_MAX; + + case s16; + min :s16 = S16_MIN; + max :s16 = S16_MAX; + + case; + assert(false, "This will take way too long."); + } + + #if !AVOID_INFINITE_FOR_LOOP { + for a : min..max { + for b : min..max { + test(a, b); + } + } + } + else { + a :type = min; + b :type = min; + while loop_a := true { + while loop_b := true { + test(a, b); + if b == max then break loop_b; else b += 1; + } + if a == max then break loop_a; else a += 1; + } + } + } + + partial_test :: ($type: Type, test: (a: type, b: type)) { + min, max: type; + #if type == { + case u8; + min = 0; + max = U8_MAX; + + case u16; + min = 0; + max = U16_MAX; + + case u32; + min = 0; + max = U32_MAX; + + case s8; + min = S8_MIN; + max = S8_MAX; + + case s16; + min = S16_MIN; + max = S16_MAX; + + case s32; + min = S32_MIN; + max = S32_MAX; + + case; + assert(false, "This will take way too long."); + } + + #if !AVOID_INFINITE_FOR_LOOP { + for a: min..max { + b := a; + c := max - a + min; + test(a, b); + test(a, c); + } + } + else { + a := min; + while loop := true { + b := a; + c := max - a + min; + test(a, b); + test(a, c); + if a == max then break loop; else a += 1; + } + } + } + + minimal_test :: ($type: Type, test: (a: type, b: type)) { + #if type == { + case u32; + min :u32 = 0; + mid :u32 = U32_MAX / 2; + max :u32 = U32_MAX; + range :u32 = cast(u32)U16_MAX * 2048; + + case u64; + min :u64 = 0; + mid :u64 = U64_MAX / 2; + max :u64 = U64_MAX; + range :u64 = cast(u64)U16_MAX * 2048; + + case s32; + min :s32 = S32_MIN; + mid :s32 = (S32_MIN / 2) + (S32_MAX / 2); + max :s32 = S32_MAX; + range :s32 = cast(s32)S16_MAX * 2048; + + case s64; + min :s64 = S64_MIN; + mid :s64 = (S64_MIN / 2) + (S64_MAX / 2); + max :s64 = S64_MAX; + range :s64 = cast(s64)S16_MAX * 2048; + + case; + assert(false, "Invalid type % given.", type); + } + + #if !AVOID_INFINITE_FOR_LOOP { + start, end : type; + + start = min; + end = min+range; + for a: start..end { + b := a; + c := end - a + start; + test(a, b); + test(a, c); + } + + start = mid-range; + end = mid+range; + for a: start..end { + b := a; + c := end - a + start; + test(a, b); + test(a, c); + } + + start = max-range; + end = max; + for a: start..end { + b := a; + c := end - a + start; + test(a, b); + test(a, c); + } + } + else { + start, end, a : type; + + start = min; + end = min + range; + a = start; + while loop := true { + b := a; + c := end - a + start; + test(a, b); + test(a, c); + if a == end then break loop; else a += 1; + } + + start = mid - range; + end = mid + range; + a = start; + while loop := true { + b := a; + c := end - a + start; + test(a, b); + test(a, c); + if a == end then break loop; else a += 1; + } + + start = max - range; + end = max; + a = start; + while loop := true { + b := a; + c := end - a + start; + test(a, b); + test(a, c); + if a == end then break loop; else a += 1; + } + } + } + + + // add + + ADD_TEST_TEMPLATE :: (a: $T, b: T) { + rT, sT := add(a, b, true); + rF, sF := add(a, b, false); + assert(rT == rF && sT == sF, "> add(%1, %2, true) = %3,%4 != add(%1, %2, false) = %5,%6\n", a, b, rT, sT, rF, sF); + } + + write_string("# testing add,u8 #\n"); + full_test(u8, ADD_TEST_TEMPLATE); + + write_string("# testing add,u16 #\n"); + full_test(u16, ADD_TEST_TEMPLATE); + + write_string("# testing add,u32 #\n"); + partial_test(u32, ADD_TEST_TEMPLATE); + + write_string("# testing add,u64 #\n"); + minimal_test(u64, ADD_TEST_TEMPLATE); + + write_string("# testing add,s8 #\n"); + full_test(s8, ADD_TEST_TEMPLATE); + + write_string("# testing add,s16 #\n"); + full_test(s16, ADD_TEST_TEMPLATE); + + write_string("# testing add,s32 #\n"); + partial_test(s32, ADD_TEST_TEMPLATE); + + write_string("# testing add,s64 #\n"); + minimal_test(s64, ADD_TEST_TEMPLATE); + + + // sub + + SUB_TEST_TEMPLATE :: (a: $T, b: T) { + rT, sT := sub(a, b, true); + rF, sF := sub(a, b, false); + assert(rT == rF && sT == sF, "> sub(%1, %2, true) = %3,%4 != sub(%1, %2, false) = %5,%6\n", a, b, rT, sT, rF, sF); + } + + write_string("# testing sub,u8 #\n"); + full_test(u8, SUB_TEST_TEMPLATE); + + write_string("# testing sub,u16 #\n"); + full_test(u16, SUB_TEST_TEMPLATE); + + write_string("# testing sub,u32 #\n"); + partial_test(u32, SUB_TEST_TEMPLATE); + + write_string("# testing sub,u64 #\n"); + minimal_test(u64, SUB_TEST_TEMPLATE); + + write_string("# testing sub,s8 #\n"); + full_test(s8, SUB_TEST_TEMPLATE); + + write_string("# testing sub,s16 #\n"); + full_test(s16, SUB_TEST_TEMPLATE); + + write_string("# testing sub,s32 #\n"); + partial_test(s32, SUB_TEST_TEMPLATE); + + write_string("# testing sub,s64 #\n"); + minimal_test(s64, SUB_TEST_TEMPLATE); + + + // mul + + MUL_TEST_TEMPLATE :: (a: $T, b: T) { + rT, sT := mul(a, b, true); + rF, sF := mul(a, b, false); + assert(rT == rF && sT == sF, "> mul(%1, %2, true) = %3,%4 != mul(%1, %2, false) = %5,%6\n", a, b, rT, sT, rF, sF); + } + + write_string("# testing mul,u8 #\n"); + full_test(u8, MUL_TEST_TEMPLATE); + + write_string("# testing mul,u16 #\n"); + full_test(u16, MUL_TEST_TEMPLATE); + + write_string("# testing mul,u32 #\n"); + partial_test(u32, MUL_TEST_TEMPLATE); + + write_string("# testing mul,u64 #\n"); + minimal_test(u64, MUL_TEST_TEMPLATE); + + write_string("# testing mul,s8 #\n"); + full_test(s8, MUL_TEST_TEMPLATE); + + write_string("# testing mul,s16 #\n"); + full_test(s16, MUL_TEST_TEMPLATE); + + write_string("# testing mul,s32 #\n"); + partial_test(s32, MUL_TEST_TEMPLATE); + + write_string("# testing mul,s64 #\n"); + minimal_test(s64, MUL_TEST_TEMPLATE); + + + // div + + DIV_TEST_TEMPLATE :: (a: $T, b: T) { + if b == 0 then return; + rT, remT, sT := div(a, b, true); + rF, remF, sF := div(a, b, false); + assert(rT == rF && sT == sF, "> mul(%1, %2, true) = %3,%4,%5 != mul(%1, %2, false) = %6,%7,%8\n", a, b, rT, remT, sT, rF, remF, sF); + } + + write_string("# testing div,u8 #\n"); + full_test(u8, DIV_TEST_TEMPLATE); + + write_string("# testing div,u16 #\n"); + full_test(u16, DIV_TEST_TEMPLATE); + + write_string("# testing div,u32 #\n"); + partial_test(u32, DIV_TEST_TEMPLATE); + + write_string("# testing div,u64 #\n"); + minimal_test(u64, DIV_TEST_TEMPLATE); + + write_string("# testing div,s8 #\n"); + full_test(s8, DIV_TEST_TEMPLATE); + + write_string("# testing div,s16 #\n"); + full_test(s16, DIV_TEST_TEMPLATE); + + write_string("# testing div,s32 #\n"); + partial_test(s32, DIV_TEST_TEMPLATE); + + write_string("# testing div,s64 #\n"); + minimal_test(s64, DIV_TEST_TEMPLATE); + + + write_string(" No errors found.\n"); + + write_strings( "#=======================#\n", "# Benchmarks #\n" @@ -212,11 +555,11 @@ main :: () { r_asm: type = 0; time_gen := current_time_monotonic(); - for idx: 0..DATA_SIZE-1 #insert #run replace("r_gen ^= OP(numbers_x[idx], numbers_y[idx], true);", "OP", operation); + for idx: 0..DATA_SIZE-1 #insert #run replace("r_gen ^= OP(numbers_x[idx], numbers_y[idx], false);", "OP", operation); time_gen = current_time_monotonic() - time_gen; time_asm := current_time_monotonic(); - for idx: 0..DATA_SIZE-1 #insert #run replace("r_asm ^= OP(numbers_x[idx], numbers_y[idx]);", "OP", operation); + for idx: 0..DATA_SIZE-1 #insert #run replace("r_asm ^= OP(numbers_x[idx], numbers_y[idx], true);", "OP", operation); time_asm = current_time_monotonic() - time_asm; assert(r_gen == r_asm); |