1const builtin = @import("builtin");
2const endian = builtin.cpu.arch.endian();
3
4const std = @import("std");
5const shr = std.math.shr;
6const shl = std.math.shl;
7
8const compiler_rt = @import("../compiler_rt.zig");
9const symbol = compiler_rt.symbol;
10
11const max_limbs = @divCeil(65535, 32); // max supported type is u65535
12
13comptime {
14 symbol(&__udivei4, "__udivei4");
15 symbol(&__umodei4, "__umodei4");
16 symbol(&__udivei5, "__udivei5");
17 symbol(&__umodei5, "__umodei5");
18}
19
20/// Get the value of a limb.
21inline fn limb(x: []const u32, i: usize) u32 {
22 return if (endian == .little) x[i] else x[x.len - 1 - i];
23}
24
25/// Change the value of a limb.
26inline fn limb_set(x: []u32, i: usize, v: u32) void {
27 if (endian == .little) {
28 x[i] = v;
29 } else {
30 x[x.len - 1 - i] = v;
31 }
32}
33
34/// Uses Knuth's Algorithm D, 4.3.1, p. 272.
35pub fn divmod(q: ?[]u32, r: ?[]u32, u: []const u32, v: []const u32) !void {
36 if (q) |q_| @memset(q_[0..], 0);
37 if (r) |r_| @memset(r_[0..], 0);
38
39 if (u.len == 0 or v.len == 0) return error.DivisionByZero;
40
41 var m = u.len - 1;
42 var n = v.len - 1;
43 while (limb(u, m) == 0) : (m -= 1) {
44 if (m == 0) return;
45 }
46 while (limb(v, n) == 0) : (n -= 1) {
47 if (n == 0) return error.DivisionByZero;
48 }
49
50 if (n > m) {
51 if (r) |r_| @memcpy(r_[0..u.len], u);
52 return;
53 }
54
55 const s = @clz(limb(v, n));
56
57 var vn: [max_limbs]u32 = undefined;
58 var i = n;
59 while (i > 0) : (i -= 1) {
60 limb_set(&vn, i, shl(u32, limb(v, i), s) | shr(u32, limb(v, i - 1), 32 - s));
61 }
62 limb_set(&vn, 0, shl(u32, limb(v, 0), s));
63
64 var un: [max_limbs + 1]u32 = undefined;
65 limb_set(&un, m + 1, shr(u32, limb(u, m), 32 - s));
66 i = m;
67 while (i > 0) : (i -= 1) {
68 limb_set(&un, i, shl(u32, limb(u, i), s) | shr(u32, limb(u, i - 1), 32 - s));
69 }
70 limb_set(&un, 0, shl(u32, limb(u, 0), s));
71
72 var j = m - n;
73 while (true) : (j -= 1) {
74 const uu = (@as(u64, limb(&un, j + n + 1)) << 32) + limb(&un, j + n);
75 var qhat = uu / limb(&vn, n);
76 var rhat = uu % limb(&vn, n);
77
78 while (true) {
79 if (qhat >= (1 << 32) or (n > 0 and qhat * limb(&vn, n - 1) > (rhat << 32) + limb(&un, j + n - 1))) {
80 qhat -= 1;
81 rhat += limb(&vn, n);
82 if (rhat < (1 << 32)) continue;
83 }
84 break;
85 }
86 var carry: i64 = 0;
87 i = 0;
88 while (i <= n) : (i += 1) {
89 const p = qhat * limb(&vn, i);
90 const t = limb(&un, i + j) - carry - @as(u32, @truncate(p));
91 limb_set(&un, i + j, @as(u32, @truncate(@as(u64, @bitCast(t)))));
92 carry = @as(i64, @intCast(p >> 32)) - @as(i64, @intCast(t >> 32));
93 }
94 const t = limb(&un, j + n + 1) -% carry;
95 limb_set(&un, j + n + 1, @as(u32, @truncate(@as(u64, @bitCast(t)))));
96 if (q) |q_| limb_set(q_, j, @as(u32, @truncate(qhat)));
97 if (t < 0) {
98 if (q) |q_| limb_set(q_, j, limb(q_, j) - 1);
99 var carry2: u64 = 0;
100 i = 0;
101 while (i <= n) : (i += 1) {
102 const t2 = @as(u64, limb(&un, i + j)) + @as(u64, limb(&vn, i)) + carry2;
103 limb_set(&un, i + j, @as(u32, @truncate(t2)));
104 carry2 = t2 >> 32;
105 }
106 limb_set(&un, j + n + 1, @as(u32, @truncate(limb(&un, j + n + 1) + carry2)));
107 }
108 if (j == 0) break;
109 }
110 if (r) |r_| {
111 i = 0;
112 while (i <= n) : (i += 1) {
113 limb_set(r_, i, shr(u32, limb(&un, i), s) | shl(u32, limb(&un, i + 1), 32 - s));
114 }
115 limb_set(r_, n, shr(u32, limb(&un, n), s));
116 }
117}
118
119pub fn __udivei4(q_p: [*]u8, u_p: [*]const u8, v_p: [*]const u8, bits: usize) callconv(.c) void {
120 @setRuntimeSafety(compiler_rt.test_safety);
121 const byte_size = std.zig.target.intByteSize(&builtin.target, @intCast(bits));
122 const q: []u32 = @ptrCast(@alignCast(q_p[0..byte_size]));
123 const u: []const u32 = @ptrCast(@alignCast(u_p[0..byte_size]));
124 const v: []const u32 = @ptrCast(@alignCast(v_p[0..byte_size]));
125 @call(.always_inline, divmod, .{ q, null, u, v }) catch unreachable;
126}
127
128pub fn __umodei4(r_p: [*]u8, u_p: [*]const u8, v_p: [*]const u8, bits: usize) callconv(.c) void {
129 @setRuntimeSafety(compiler_rt.test_safety);
130 const byte_size = std.zig.target.intByteSize(&builtin.target, @intCast(bits));
131 const r: []u32 = @ptrCast(@alignCast(r_p[0..byte_size]));
132 const u: []const u32 = @ptrCast(@alignCast(u_p[0..byte_size]));
133 const v: []const u32 = @ptrCast(@alignCast(v_p[0..byte_size]));
134 @call(.always_inline, divmod, .{ null, r, u, v }) catch unreachable;
135}
136
137pub fn __udivei5(q_p: [*]u8, u_p: [*]const u8, v_p: [*]const u8, t_p: [*]u8, bits: usize) callconv(.c) void {
138 @setRuntimeSafety(compiler_rt.test_safety);
139 const byte_size = std.zig.target.intByteSize(&builtin.target, @intCast(bits));
140 const q: []u32 = @ptrCast(@alignCast(q_p[0..byte_size]));
141 const u: []const u32 = @ptrCast(@alignCast(u_p[0..byte_size]));
142 const v: []const u32 = @ptrCast(@alignCast(v_p[0..byte_size]));
143 const tu: []u32 = @ptrCast(@alignCast(t_p[0..byte_size]));
144 _ = tu;
145 const tv: []u32 = @ptrCast(@alignCast(t_p[byte_size..][0..byte_size]));
146 _ = tv;
147 @call(.always_inline, divmod, .{ q, null, u, v }) catch unreachable;
148}
149
150pub fn __umodei5(r_p: [*]u8, u_p: [*]const u8, v_p: [*]const u8, t_p: [*]u8, bits: usize) callconv(.c) void {
151 @setRuntimeSafety(compiler_rt.test_safety);
152 const byte_size = std.zig.target.intByteSize(&builtin.target, @intCast(bits));
153 const r: []u32 = @ptrCast(@alignCast(r_p[0..byte_size]));
154 const u: []const u32 = @ptrCast(@alignCast(u_p[0..byte_size]));
155 const v: []const u32 = @ptrCast(@alignCast(v_p[0..byte_size]));
156 const tu: []u32 = @ptrCast(@alignCast(t_p[0..byte_size]));
157 _ = tu;
158 const tv: []u32 = @ptrCast(@alignCast(t_p[byte_size..][0..byte_size]));
159 _ = tv;
160 @call(.always_inline, divmod, .{ null, r, u, v }) catch unreachable;
161}
162
163test "__udivei4/__umodei4" {
164 if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
165 if (builtin.zig_backend == .stage2_c) return error.SkipZigTest;
166 if (builtin.zig_backend == .stage2_wasm) return error.SkipZigTest;
167
168 const RndGen = std.Random.DefaultPrng;
169 var rnd = RndGen.init(42);
170 var i: usize = 10000;
171 while (i > 0) : (i -= 1) {
172 const u = rnd.random().int(u1000);
173 const v = 1 + rnd.random().int(u1200);
174 const q = u / v;
175 const r = u % v;
176 const z = q * v + r;
177 try std.testing.expect(z == u);
178 }
179}