1const builtin = @import("builtin");
2
3const std = @import("std");
4const assert = std.debug.assert;
5const div_t = std.c.div_t;
6const ldiv_t = std.c.ldiv_t;
7const lldiv_t = std.c.lldiv_t;
8
9const symbol = @import("../c.zig").symbol;
10
11comptime {
12 _ = @import("stdlib/rand.zig");
13 _ = @import("stdlib/drand48.zig");
14
15 if (builtin.target.isMuslLibC() or builtin.target.isWasiLibC()) {
16 // Functions specific to musl and wasi-libc.
17 symbol(&abs, "abs");
18 symbol(&labs, "labs");
19 symbol(&llabs, "llabs");
20
21 symbol(&div, "div");
22 symbol(&ldiv, "ldiv");
23 symbol(&lldiv, "lldiv");
24
25 symbol(&atoi, "atoi");
26 symbol(&atol, "atol");
27 symbol(&atoll, "atoll");
28
29 symbol(&strtol, "strtol");
30 symbol(&strtoll, "strtoll");
31 symbol(&strtoul, "strtoul");
32 symbol(&strtoull, "strtoull");
33 symbol(&strtoimax, "strtoimax");
34 symbol(&strtoumax, "strtoumax");
35
36 symbol(&strtol, "__strtol_internal");
37 symbol(&strtoll, "__strtoll_internal");
38 symbol(&strtoul, "__strtoul_internal");
39 symbol(&strtoull, "__strtoull_internal");
40 symbol(&strtoimax, "__strtoimax_internal");
41 symbol(&strtoumax, "__strtoumax_internal");
42
43 symbol(&qsort_r, "qsort_r");
44 symbol(&qsort, "qsort");
45
46 symbol(&bsearch, "bsearch");
47 }
48}
49
50fn abs(a: c_int) callconv(.c) c_int {
51 return @intCast(@abs(a));
52}
53
54fn labs(a: c_long) callconv(.c) c_long {
55 return @intCast(@abs(a));
56}
57
58fn llabs(a: c_longlong) callconv(.c) c_longlong {
59 return @intCast(@abs(a));
60}
61
62fn div(a: c_int, b: c_int) callconv(.c) div_t {
63 return .{
64 .quot = @divTrunc(a, b),
65 .rem = @rem(a, b),
66 };
67}
68
69fn ldiv(a: c_long, b: c_long) callconv(.c) ldiv_t {
70 return .{
71 .quot = @divTrunc(a, b),
72 .rem = @rem(a, b),
73 };
74}
75
76fn lldiv(a: c_longlong, b: c_longlong) callconv(.c) lldiv_t {
77 return .{
78 .quot = @divTrunc(a, b),
79 .rem = @rem(a, b),
80 };
81}
82
83fn atoi(str: [*:0]const c_char) callconv(.c) c_int {
84 return asciiToInteger(c_int, @ptrCast(str));
85}
86
87fn atol(str: [*:0]const c_char) callconv(.c) c_long {
88 return asciiToInteger(c_long, @ptrCast(str));
89}
90
91fn atoll(str: [*:0]const c_char) callconv(.c) c_longlong {
92 return asciiToInteger(c_longlong, @ptrCast(str));
93}
94
95fn asciiToInteger(comptime T: type, buf: [*:0]const u8) T {
96 comptime assert(std.math.isPowerOfTwo(@bitSizeOf(T)));
97
98 var current = buf;
99 while (std.ascii.isWhitespace(current[0])) : (current += 1) {}
100
101 // The behaviour *is* undefined if the result cannot be represented
102 // but as they are usually called with untrusted input we can just handle overflow gracefully.
103 if (current[0] == '-') return parseDigitsWithSignGenericCharacter(T, u8, current + 1, null, 10, .neg) catch std.math.minInt(T);
104 if (current[0] == '+') current += 1;
105 return parseDigitsWithSignGenericCharacter(T, u8, current, null, 10, .pos) catch std.math.maxInt(T);
106}
107
108fn strtol(noalias str: [*:0]const c_char, noalias str_end: ?*[*:0]const c_char, base: c_int) callconv(.c) c_long {
109 return stringToInteger(c_long, @ptrCast(str), if (str_end) |end| @ptrCast(end) else null, base);
110}
111
112fn strtoll(noalias str: [*:0]const c_char, noalias str_end: ?*[*:0]const c_char, base: c_int) callconv(.c) c_longlong {
113 return stringToInteger(c_longlong, @ptrCast(str), if (str_end) |end| @ptrCast(end) else null, base);
114}
115
116fn strtoul(noalias str: [*:0]const c_char, noalias str_end: ?*[*:0]const c_char, base: c_int) callconv(.c) c_ulong {
117 return stringToInteger(c_ulong, @ptrCast(str), if (str_end) |end| @ptrCast(end) else null, base);
118}
119
120fn strtoull(noalias str: [*:0]const c_char, noalias str_end: ?*[*:0]const c_char, base: c_int) callconv(.c) c_ulonglong {
121 return stringToInteger(c_ulonglong, @ptrCast(str), if (str_end) |end| @ptrCast(end) else null, base);
122}
123
124// XXX: These belong in inttypes.zig but we'd have to make stringToInteger pub or move it somewhere else.
125fn strtoimax(noalias str: [*:0]const c_char, noalias str_end: ?*[*:0]const c_char, base: c_int) callconv(.c) std.c.intmax_t {
126 return stringToInteger(std.c.intmax_t, @ptrCast(str), if (str_end) |end| @ptrCast(end) else null, base);
127}
128
129fn strtoumax(noalias str: [*:0]const c_char, noalias str_end: ?*[*:0]const c_char, base: c_int) callconv(.c) std.c.uintmax_t {
130 return stringToInteger(std.c.uintmax_t, @ptrCast(str), if (str_end) |end| @ptrCast(end) else null, base);
131}
132
133fn stringToInteger(comptime T: type, noalias buf: [*:0]const u8, noalias maybe_end: ?*[*:0]const u8, base: c_int) T {
134 comptime assert(std.math.isPowerOfTwo(@bitSizeOf(T)));
135
136 if (base < 0 or base == 1 or base > 36) {
137 if (maybe_end) |end| {
138 end.* = buf;
139 }
140
141 std.c._errno().* = @backingInt(std.c.E.INVAL);
142 return 0;
143 }
144
145 var current = buf;
146 while (std.ascii.isWhitespace(current[0])) : (current += 1) {}
147
148 const negative: bool = switch (current[0]) {
149 '-' => blk: {
150 current += 1;
151 break :blk true;
152 },
153 '+' => blk: {
154 current += 1;
155 break :blk false;
156 },
157 else => false,
158 };
159
160 // The prefix is allowed iff base == 0 or base == base of the prefix
161 const real_base: u6, const digits = blk: {
162 if (current[0] == '0') {
163 if ((base == 0 or base == 16) and std.ascii.toLower(current[1]) == 'x' and std.ascii.isHex(current[2])) {
164 break :blk .{ 16, current[2..] };
165 } else if (base == 0) {
166 break :blk .{ 8, current };
167 } else {
168 break :blk .{
169 switch (base) {
170 0 => 10,
171 else => @intCast(base),
172 },
173 current,
174 };
175 }
176 } else {
177 const real_base: u6 = switch (base) {
178 0 => 10,
179 else => @intCast(base),
180 };
181
182 _ = std.fmt.charToDigit(current[0], real_base) catch {
183 // No digits to parse. Setting errno to .INVAL is optional in this case.
184 if (maybe_end) |end| {
185 end.* = buf;
186 }
187 return 0;
188 };
189 break :blk .{ real_base, current };
190 }
191 };
192
193 if (@typeInfo(T).int.signedness == .unsigned) {
194 const result = parseDigitsWithSignGenericCharacter(T, u8, digits, maybe_end, real_base, .pos) catch {
195 std.c._errno().* = @backingInt(std.c.E.RANGE);
196 return std.math.maxInt(T);
197 };
198
199 return if (negative) -%result else result;
200 }
201
202 if (negative) return parseDigitsWithSignGenericCharacter(T, u8, digits, maybe_end, real_base, .neg) catch blk: {
203 std.c._errno().* = @backingInt(std.c.E.RANGE);
204 break :blk std.math.minInt(T);
205 };
206
207 return parseDigitsWithSignGenericCharacter(T, u8, digits, maybe_end, real_base, .pos) catch blk: {
208 std.c._errno().* = @backingInt(std.c.E.RANGE);
209 break :blk std.math.maxInt(T);
210 };
211}
212
213fn parseDigitsWithSignGenericCharacter(
214 comptime T: type,
215 comptime Char: type,
216 noalias buf: [*:0]const Char,
217 noalias maybe_end: ?*[*:0]const Char,
218 base: u6,
219 comptime sign: enum { pos, neg },
220) error{Overflow}!T {
221 assert(base >= 2 and base <= 36);
222
223 var current = buf;
224 defer if (maybe_end) |end| {
225 end.* = current;
226 };
227
228 const add = switch (sign) {
229 .pos => std.math.add,
230 .neg => std.math.sub,
231 };
232
233 var value: T = 0;
234 while (true) {
235 const c: u8 = std.math.cast(u8, current[0]) orelse break;
236
237 const digit: u6 = @intCast(std.fmt.charToDigit(c, base) catch break);
238 defer current += 1;
239
240 value = try std.math.mul(T, value, base);
241 value = try add(T, value, digit);
242 }
243
244 return value;
245}
246
247// NOTE: Despite its name, `qsort` doesn't have to use quicksort or make any complexity or stability guarantee.
248fn qsort_r(base: *anyopaque, n: usize, size: usize, compare: *const fn (a: *const anyopaque, b: *const anyopaque, arg: ?*anyopaque) callconv(.c) c_int, arg: ?*anyopaque) callconv(.c) void {
249 const Context = struct {
250 base: [*]u8,
251 size: usize,
252 compare: *const fn (a: *const anyopaque, b: *const anyopaque, arg: ?*anyopaque) callconv(.c) c_int,
253 arg: ?*anyopaque,
254
255 pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
256 return ctx.compare(&ctx.base[a * ctx.size], &ctx.base[b * ctx.size], ctx.arg) < 0;
257 }
258
259 pub fn swap(ctx: @This(), a: usize, b: usize) void {
260 const a_bytes: []u8 = ctx.base[a * ctx.size ..][0..ctx.size];
261 const b_bytes: []u8 = ctx.base[b * ctx.size ..][0..ctx.size];
262
263 for (a_bytes, b_bytes) |*ab, *bb| {
264 const tmp = ab.*;
265 ab.* = bb.*;
266 bb.* = tmp;
267 }
268 }
269 };
270
271 std.mem.sortUnstableContext(0, n, Context{
272 .base = @ptrCast(base),
273 .size = size,
274 .compare = compare,
275 .arg = arg,
276 });
277}
278
279fn qsort(base: *anyopaque, n: usize, size: usize, compare: *const fn (a: *const anyopaque, b: *const anyopaque) callconv(.c) c_int) callconv(.c) void {
280 return qsort_r(base, n, size, (struct {
281 fn wrap(a: *const anyopaque, b: *const anyopaque, arg: ?*anyopaque) callconv(.c) c_int {
282 const cmp: *const fn (a: *const anyopaque, b: *const anyopaque) callconv(.c) c_int = @ptrCast(@alignCast(arg.?));
283 return cmp(a, b);
284 }
285 }).wrap, @constCast(compare));
286}
287
288// NOTE: Despite its name, `bsearch` doesn't need to be implemented using binary search or make any complexity guarantee.
289fn bsearch(key: *const anyopaque, base: *const anyopaque, n: usize, size: usize, compare: *const fn (a: *const anyopaque, b: *const anyopaque) callconv(.c) c_int) callconv(.c) ?*anyopaque {
290 const base_bytes: [*]const u8 = @ptrCast(base);
291 var low: usize = 0;
292 var high: usize = n;
293
294 while (low < high) {
295 // Avoid overflowing in the midpoint calculation
296 const mid = low + (high - low) / 2;
297 const elem = &base_bytes[mid * size];
298
299 switch (std.math.order(compare(key, elem), 0)) {
300 .eq => return @constCast(elem),
301 .gt => low = mid + 1,
302 .lt => high = mid,
303 }
304 }
305 return null;
306}