Commit fc59a04061
Changed files (6)
lib
std
lib/std/special/compiler_rt/addo.zig
@@ -15,7 +15,7 @@ inline fn addoXi4_generic(comptime ST: type, a: ST, b: ST, overflow: *c_int) ST
// and the sign of a+b+carry is the same as a (or equivalently b).
// Slower routine: res = ~(a ^ b) & ((sum ^ a)
// Faster routine: res = (sum ^ a) & (sum ^ b)
- // Oerflow occured, iff (res < 0)
+ // Overflow occured, iff (res < 0)
if (((sum ^ a) & (sum ^ b)) < 0)
overflow.* = 1;
return sum;
lib/std/special/compiler_rt/subo.zig
@@ -0,0 +1,38 @@
+const builtin = @import("builtin");
+
+// subo - subtract overflow
+// * return a-%b.
+// * return if a-b overflows => 1 else => 0
+// - suboXi4_generic as default
+
+inline fn suboXi4_generic(comptime ST: type, a: ST, b: ST, overflow: *c_int) ST {
+ @setRuntimeSafety(builtin.is_test);
+ overflow.* = 0;
+ var sum: ST = a -% b;
+ // Hackers Delight: section Overflow Detection, subsection Signed Add/Subtract
+ // Let sum = a -% b == a - b - carry == wraparound subtraction.
+ // Overflow in a-b-carry occurs, iff a and b have opposite signs
+ // and the sign of a-b-carry is opposite of a (or equivalently same as b).
+ // Faster routine: res = (a ^ b) & (sum ^ a)
+ // Slower routine: res = (sum^a) & ~(sum^b)
+ // Overflow occured, iff (res < 0)
+ if (((a ^ b) & (sum ^ a)) < 0)
+ overflow.* = 1;
+ return sum;
+}
+
+pub fn __subosi4(a: i32, b: i32, overflow: *c_int) callconv(.C) i32 {
+ return suboXi4_generic(i32, a, b, overflow);
+}
+pub fn __subodi4(a: i64, b: i64, overflow: *c_int) callconv(.C) i64 {
+ return suboXi4_generic(i64, a, b, overflow);
+}
+pub fn __suboti4(a: i128, b: i128, overflow: *c_int) callconv(.C) i128 {
+ return suboXi4_generic(i128, a, b, overflow);
+}
+
+test {
+ _ = @import("subosi4_test.zig");
+ _ = @import("subodi4_test.zig");
+ _ = @import("suboti4_test.zig");
+}
lib/std/special/compiler_rt/subodi4_test.zig
@@ -0,0 +1,81 @@
+const subo = @import("subo.zig");
+const std = @import("std");
+const testing = std.testing;
+const math = std.math;
+
+fn test__subodi4(a: i64, b: i64) !void {
+ var result_ov: c_int = undefined;
+ var expected_ov: c_int = undefined;
+ var result = subo.__subodi4(a, b, &result_ov);
+ var expected: i64 = simple_subodi4(a, b, &expected_ov);
+ try testing.expectEqual(expected, result);
+ try testing.expectEqual(expected_ov, result_ov);
+}
+
+// 2 cases on evaluating `a-b`:
+// 1. `a-b` may underflow, iff b>0 && a<0 and a-b < min <=> a<min+b
+// 2. `a-b` may overflow, iff b<0 && a>0 and a-b > max <=> a>max+b
+// `-b` evaluation may overflow, iff b==min, but this is handled by the hardware
+pub fn simple_subodi4(a: i64, b: i64, overflow: *c_int) i64 {
+ overflow.* = 0;
+ const min: i64 = math.minInt(i64);
+ const max: i64 = math.maxInt(i64);
+ if (((b > 0) and (a < min + b)) or
+ ((b < 0) and (a > max + b)))
+ overflow.* = 1;
+ return a -% b;
+}
+
+test "subodi3" {
+ const min: i64 = math.minInt(i64);
+ const max: i64 = math.maxInt(i64);
+ var i: i64 = 1;
+ while (i < max) : (i *|= 2) {
+ try test__subodi4(i, i);
+ try test__subodi4(-i, -i);
+ try test__subodi4(i, -i);
+ try test__subodi4(-i, i);
+ }
+
+ // edge cases
+ // 0 - 0 = 0
+ // MIN - MIN = 0
+ // MAX - MAX = 0
+ // 0 - MIN overflow
+ // 0 - MAX = MIN+1
+ // MIN - 0 = MIN
+ // MAX - 0 = MAX
+ // MIN - MAX overflow
+ // MAX - MIN overflow
+ try test__subodi4(0, 0);
+ try test__subodi4(min, min);
+ try test__subodi4(max, max);
+ try test__subodi4(0, min);
+ try test__subodi4(0, max);
+ try test__subodi4(min, 0);
+ try test__subodi4(max, 0);
+ try test__subodi4(min, max);
+ try test__subodi4(max, min);
+
+ // derived edge cases
+ // MIN+1 - MIN = 1
+ // MAX-1 - MAX = -1
+ // 1 - MIN overflow
+ // -1 - MIN = MAX
+ // -1 - MAX = MIN
+ // +1 - MAX = MIN+2
+ // MIN - 1 overflow
+ // MIN - -1 = MIN+1
+ // MAX - 1 = MAX-1
+ // MAX - -1 overflow
+ try test__subodi4(min + 1, min);
+ try test__subodi4(max - 1, max);
+ try test__subodi4(1, min);
+ try test__subodi4(-1, min);
+ try test__subodi4(-1, max);
+ try test__subodi4(1, max);
+ try test__subodi4(min, 1);
+ try test__subodi4(min, -1);
+ try test__subodi4(max, -1);
+ try test__subodi4(max, 1);
+}
lib/std/special/compiler_rt/subosi4_test.zig
@@ -0,0 +1,82 @@
+const subo = @import("subo.zig");
+const testing = @import("std").testing;
+
+fn test__subosi4(a: i32, b: i32) !void {
+ var result_ov: c_int = undefined;
+ var expected_ov: c_int = undefined;
+ var result = subo.__subosi4(a, b, &result_ov);
+ var expected: i32 = simple_subosi4(a, b, &expected_ov);
+ try testing.expectEqual(expected, result);
+ try testing.expectEqual(expected_ov, result_ov);
+}
+
+// 2 cases on evaluating `a-b`:
+// 1. `a-b` may underflow, iff b>0 && a<0 and a-b < min <=> a<min+b
+// 2. `a-b` may overflow, iff b<0 && a>0 and a-b > max <=> a>max+b
+// `-b` evaluation may overflow, iff b==min, but this is handled by the hardware
+pub fn simple_subosi4(a: i32, b: i32, overflow: *c_int) i32 {
+ overflow.* = 0;
+ const min: i32 = -2147483648;
+ const max: i32 = 2147483647;
+ if (((b > 0) and (a < min + b)) or
+ ((b < 0) and (a > max + b)))
+ overflow.* = 1;
+ return a -% b;
+}
+
+test "subosi3" {
+ // -2^31 <= i32 <= 2^31-1
+ // 2^31 = 2147483648
+ // 2^31-1 = 2147483647
+ const min: i32 = -2147483648;
+ const max: i32 = 2147483647;
+ var i: i32 = 1;
+ while (i < max) : (i *|= 2) {
+ try test__subosi4(i, i);
+ try test__subosi4(-i, -i);
+ try test__subosi4(i, -i);
+ try test__subosi4(-i, i);
+ }
+
+ // edge cases
+ // 0 - 0 = 0
+ // MIN - MIN = 0
+ // MAX - MAX = 0
+ // 0 - MIN overflow
+ // 0 - MAX = MIN+1
+ // MIN - 0 = MIN
+ // MAX - 0 = MAX
+ // MIN - MAX overflow
+ // MAX - MIN overflow
+ try test__subosi4(0, 0);
+ try test__subosi4(min, min);
+ try test__subosi4(max, max);
+ try test__subosi4(0, min);
+ try test__subosi4(0, max);
+ try test__subosi4(min, 0);
+ try test__subosi4(max, 0);
+ try test__subosi4(min, max);
+ try test__subosi4(max, min);
+
+ // derived edge cases
+ // MIN+1 - MIN = 1
+ // MAX-1 - MAX = -1
+ // 1 - MIN overflow
+ // -1 - MIN = MAX
+ // -1 - MAX = MIN
+ // +1 - MAX = MIN+2
+ // MIN - 1 overflow
+ // MIN - -1 = MIN+1
+ // MAX - 1 = MAX-1
+ // MAX - -1 overflow
+ try test__subosi4(min + 1, min);
+ try test__subosi4(max - 1, max);
+ try test__subosi4(1, min);
+ try test__subosi4(-1, min);
+ try test__subosi4(-1, max);
+ try test__subosi4(1, max);
+ try test__subosi4(min, 1);
+ try test__subosi4(min, -1);
+ try test__subosi4(max, -1);
+ try test__subosi4(max, 1);
+}
lib/std/special/compiler_rt/suboti4_test.zig
@@ -0,0 +1,81 @@
+const subo = @import("subo.zig");
+const std = @import("std");
+const testing = std.testing;
+const math = std.math;
+
+fn test__suboti4(a: i128, b: i128) !void {
+ var result_ov: c_int = undefined;
+ var expected_ov: c_int = undefined;
+ var result = subo.__suboti4(a, b, &result_ov);
+ var expected: i128 = simple_suboti4(a, b, &expected_ov);
+ try testing.expectEqual(expected, result);
+ try testing.expectEqual(expected_ov, result_ov);
+}
+
+// 2 cases on evaluating `a-b`:
+// 1. `a-b` may underflow, iff b>0 && a<0 and a-b < min <=> a<min+b
+// 2. `a-b` may overflow, iff b<0 && a>0 and a-b > max <=> a>max+b
+// `-b` evaluation may overflow, iff b==min, but this is handled by the hardware
+pub fn simple_suboti4(a: i128, b: i128, overflow: *c_int) i128 {
+ overflow.* = 0;
+ const min: i128 = math.minInt(i128);
+ const max: i128 = math.maxInt(i128);
+ if (((b > 0) and (a < min + b)) or
+ ((b < 0) and (a > max + b)))
+ overflow.* = 1;
+ return a -% b;
+}
+
+test "suboti3" {
+ const min: i128 = math.minInt(i128);
+ const max: i128 = math.maxInt(i128);
+ var i: i128 = 1;
+ while (i < max) : (i *|= 2) {
+ try test__suboti4(i, i);
+ try test__suboti4(-i, -i);
+ try test__suboti4(i, -i);
+ try test__suboti4(-i, i);
+ }
+
+ // edge cases
+ // 0 - 0 = 0
+ // MIN - MIN = 0
+ // MAX - MAX = 0
+ // 0 - MIN overflow
+ // 0 - MAX = MIN+1
+ // MIN - 0 = MIN
+ // MAX - 0 = MAX
+ // MIN - MAX overflow
+ // MAX - MIN overflow
+ try test__suboti4(0, 0);
+ try test__suboti4(min, min);
+ try test__suboti4(max, max);
+ try test__suboti4(0, min);
+ try test__suboti4(0, max);
+ try test__suboti4(min, 0);
+ try test__suboti4(max, 0);
+ try test__suboti4(min, max);
+ try test__suboti4(max, min);
+
+ // derived edge cases
+ // MIN+1 - MIN = 1
+ // MAX-1 - MAX = -1
+ // 1 - MIN overflow
+ // -1 - MIN = MAX
+ // -1 - MAX = MIN
+ // +1 - MAX = MIN+2
+ // MIN - 1 overflow
+ // MIN - -1 = MIN+1
+ // MAX - 1 = MAX-1
+ // MAX - -1 overflow
+ try test__suboti4(min + 1, min);
+ try test__suboti4(max - 1, max);
+ try test__suboti4(1, min);
+ try test__suboti4(-1, min);
+ try test__suboti4(-1, max);
+ try test__suboti4(1, max);
+ try test__suboti4(min, 1);
+ try test__suboti4(min, -1);
+ try test__suboti4(max, -1);
+ try test__suboti4(max, 1);
+}
lib/std/special/compiler_rt.zig
@@ -112,6 +112,12 @@ comptime {
@export(__addodi4, .{ .name = "__addodi4", .linkage = linkage });
const __addoti4 = @import("compiler_rt/addo.zig").__addoti4;
@export(__addoti4, .{ .name = "__addoti4", .linkage = linkage });
+ const __subosi4 = @import("compiler_rt/subo.zig").__subosi4;
+ @export(__subosi4, .{ .name = "__subosi4", .linkage = linkage });
+ const __subodi4 = @import("compiler_rt/subo.zig").__subodi4;
+ @export(__subodi4, .{ .name = "__subodi4", .linkage = linkage });
+ const __suboti4 = @import("compiler_rt/subo.zig").__suboti4;
+ @export(__suboti4, .{ .name = "__suboti4", .linkage = linkage });
const __mulosi4 = @import("compiler_rt/mulo.zig").__mulosi4;
@export(__mulosi4, .{ .name = "__mulosi4", .linkage = linkage });
const __mulodi4 = @import("compiler_rt/mulo.zig").__mulodi4;