compiler_rt: add __absvsi2, __absvdi2, __absvti2

- abs can only overflow, if a == MIN
- comparing the sign change from wrapping addition is branchless
- tests: MIN, MIN+1,..MIN+4, -42, -7, -1, 0, 1, 7..

See #1290

6 files changed, 133 insertions, 1 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4150f8b2ef..12df765268 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -444,6 +444,7 @@ set(ZIG_STAGE2_SOURCES
     "${CMAKE_SOURCE_DIR}/lib/std/rand.zig"
     "${CMAKE_SOURCE_DIR}/lib/std/sort.zig"
     "${CMAKE_SOURCE_DIR}/lib/std/special/compiler_rt.zig"
+    "${CMAKE_SOURCE_DIR}/lib/std/special/compiler_rt/absv.zig"
     "${CMAKE_SOURCE_DIR}/lib/std/special/compiler_rt/addXf3.zig"
     "${CMAKE_SOURCE_DIR}/lib/std/special/compiler_rt/atomics.zig"
     "${CMAKE_SOURCE_DIR}/lib/std/special/compiler_rt/bswap.zig"
diff --git a/lib/std/special/compiler_rt.zig b/lib/std/special/compiler_rt.zig
index c8cb00ee3e..6d2f76bf3c 100644
--- a/lib/std/special/compiler_rt.zig
+++ b/lib/std/special/compiler_rt.zig
@@ -416,7 +416,13 @@ comptime {
         const __udivmodsi4 = @import("compiler_rt/int.zig").__udivmodsi4;
         @export(__udivmodsi4, .{ .name = "__udivmodsi4", .linkage = linkage });
 
-        // missing: Integral arithmetic with trapping overflow
+        // Integral arithmetic with trapping overflow
+        const __absvsi2 = @import("compiler_rt/absv.zig").__absvsi2;
+        @export(__absvsi2, .{ .name = "__absvsi2", .linkage = linkage });
+        const __absvdi2 = @import("compiler_rt/absv.zig").__absvdi2;
+        @export(__absvdi2, .{ .name = "__absvdi2", .linkage = linkage });
+        const __absvti2 = @import("compiler_rt/absv.zig").__absvti2;
+        @export(__absvti2, .{ .name = "__absvti2", .linkage = linkage });
 
         // missing: Integral arithmetic which returns if overflow
 
diff --git a/lib/std/special/compiler_rt/absv.zig b/lib/std/special/compiler_rt/absv.zig
new file mode 100644
index 0000000000..5c46d028a9
--- /dev/null
+++ b/lib/std/special/compiler_rt/absv.zig
@@ -0,0 +1,35 @@
+// absv - absolute oVerflow
+// * @panic, if value can not be represented
+// - absvXi4_generic for unoptimized version
+
+fn absvXi_generic(comptime ST: type) fn (a: ST) callconv(.C) ST {
+    return struct {
+        fn f(a: ST) callconv(.C) ST {
+            const UT = switch (ST) {
+                i32 => u32,
+                i64 => u64,
+                i128 => u128,
+                else => unreachable,
+            };
+            // taken from  Bit Twiddling Hacks
+            // compute the integer absolute value (abs) without branching
+            var x: ST = a;
+            const N: UT = @bitSizeOf(ST);
+            const sign: ST = a >> N - 1;
+            x +%= sign;
+            x ^= sign;
+            if (x < 0)
+                @panic("compiler_rt absv: overflow");
+            return x;
+        }
+    }.f;
+}
+pub const __absvsi2 = absvXi_generic(i32);
+pub const __absvdi2 = absvXi_generic(i64);
+pub const __absvti2 = absvXi_generic(i128);
+
+test {
+    _ = @import("absvsi2_test.zig");
+    _ = @import("absvdi2_test.zig");
+    _ = @import("absvti2_test.zig");
+}
diff --git a/lib/std/special/compiler_rt/absvdi2_test.zig b/lib/std/special/compiler_rt/absvdi2_test.zig
new file mode 100644
index 0000000000..4aa73513ee
--- /dev/null
+++ b/lib/std/special/compiler_rt/absvdi2_test.zig
@@ -0,0 +1,30 @@
+const absv = @import("absv.zig");
+const testing = @import("std").testing;
+
+fn test__absvdi2(a: i64, expected: i64) !void {
+    var result = absv.__absvdi2(a);
+    try testing.expectEqual(expected, result);
+}
+
+test "absvdi2" {
+    // -2^63 <= i64 <= 2^63-1
+    // 2^63 = 9223372036854775808
+    // 2^63-1 = 9223372036854775807
+    // TODO write panic handler for testing panics
+    //try test__absvdi2(-9223372036854775808, -5); // tested with return -5; and panic
+    try test__absvdi2(-9223372036854775807, 9223372036854775807);
+    try test__absvdi2(-9223372036854775806, 9223372036854775806);
+    try test__absvdi2(-9223372036854775805, 9223372036854775805);
+    try test__absvdi2(-9223372036854775804, 9223372036854775804);
+    try test__absvdi2(-42, 42);
+    try test__absvdi2(-7, 7);
+    try test__absvdi2(-1, 1);
+    try test__absvdi2(0, 0);
+    try test__absvdi2(1, 1);
+    try test__absvdi2(7, 7);
+    try test__absvdi2(42, 42);
+    try test__absvdi2(9223372036854775804, 9223372036854775804);
+    try test__absvdi2(9223372036854775805, 9223372036854775805);
+    try test__absvdi2(9223372036854775806, 9223372036854775806);
+    try test__absvdi2(9223372036854775807, 9223372036854775807);
+}
diff --git a/lib/std/special/compiler_rt/absvsi2_test.zig b/lib/std/special/compiler_rt/absvsi2_test.zig
new file mode 100644
index 0000000000..2cc3dbf991
--- /dev/null
+++ b/lib/std/special/compiler_rt/absvsi2_test.zig
@@ -0,0 +1,30 @@
+const absv = @import("absv.zig");
+const testing = @import("std").testing;
+
+fn test__absvsi2(a: i32, expected: i32) !void {
+    var result = absv.__absvsi2(a);
+    try testing.expectEqual(expected, result);
+}
+
+test "absvsi2" {
+    // -2^31 <= i32 <= 2^31-1
+    // 2^31 = 2147483648
+    // 2^31-1 = 2147483647
+    // TODO write panic handler for testing panics
+    //try test__absvsi2(-2147483648, -5);  // tested with return -5; and panic
+    try test__absvsi2(-2147483647, 2147483647);
+    try test__absvsi2(-2147483646, 2147483646);
+    try test__absvsi2(-2147483645, 2147483645);
+    try test__absvsi2(-2147483644, 2147483644);
+    try test__absvsi2(-42, 42);
+    try test__absvsi2(-7, 7);
+    try test__absvsi2(-1, 1);
+    try test__absvsi2(0, 0);
+    try test__absvsi2(1, 1);
+    try test__absvsi2(7, 7);
+    try test__absvsi2(42, 42);
+    try test__absvsi2(2147483644, 2147483644);
+    try test__absvsi2(2147483645, 2147483645);
+    try test__absvsi2(2147483646, 2147483646);
+    try test__absvsi2(2147483647, 2147483647);
+}
diff --git a/lib/std/special/compiler_rt/absvti2_test.zig b/lib/std/special/compiler_rt/absvti2_test.zig
new file mode 100644
index 0000000000..5b4deb3640
--- /dev/null
+++ b/lib/std/special/compiler_rt/absvti2_test.zig
@@ -0,0 +1,30 @@
+const absv = @import("absv.zig");
+const testing = @import("std").testing;
+
+fn test__absvti2(a: i128, expected: i128) !void {
+    var result = absv.__absvti2(a);
+    try testing.expectEqual(expected, result);
+}
+
+test "absvti2" {
+    // -2^127 <= i128 <= 2^127-1
+    // 2^127 = 170141183460469231731687303715884105728
+    // 2^127+1 = 170141183460469231731687303715884105727
+    // TODO write panic handler for testing panics
+    //try test__absvti2(-170141183460469231731687303715884105728, -5); // tested with return -5; and panic
+    try test__absvti2(-170141183460469231731687303715884105727, 170141183460469231731687303715884105727);
+    try test__absvti2(-170141183460469231731687303715884105726, 170141183460469231731687303715884105726);
+    try test__absvti2(-170141183460469231731687303715884105725, 170141183460469231731687303715884105725);
+    try test__absvti2(-170141183460469231731687303715884105724, 170141183460469231731687303715884105724);
+    try test__absvti2(-42, 42);
+    try test__absvti2(-7, 7);
+    try test__absvti2(-1, 1);
+    try test__absvti2(0, 0);
+    try test__absvti2(1, 1);
+    try test__absvti2(7, 7);
+    try test__absvti2(42, 42);
+    try test__absvti2(170141183460469231731687303715884105724, 170141183460469231731687303715884105724);
+    try test__absvti2(170141183460469231731687303715884105725, 170141183460469231731687303715884105725);
+    try test__absvti2(170141183460469231731687303715884105726, 170141183460469231731687303715884105726);
+    try test__absvti2(170141183460469231731687303715884105727, 170141183460469231731687303715884105727);
+}