1const builtin = @import("builtin");
2const std = @import("std");
3const compiler_rt = @import("../compiler_rt.zig");
4const symbol = compiler_rt.symbol;
5
6comptime {
7 symbol(&__clzsi2, "__clzsi2");
8 symbol(&__clzdi2, "__clzdi2");
9 symbol(&__clzti2, "__clzti2");
10 symbol(&__ctzsi2, "__ctzsi2");
11 symbol(&__ctzdi2, "__ctzdi2");
12 symbol(&__ctzti2, "__ctzti2");
13 symbol(&__ffssi2, "__ffssi2");
14 symbol(&__ffsdi2, "__ffsdi2");
15 symbol(&__ffsti2, "__ffsti2");
16}
17
18// clz - count leading zeroes
19// - clzXi2 for unoptimized little and big endian
20// - __clzsi2_thumb1: assume a != 0
21// - __clzsi2_arm32: assume a != 0
22
23// ctz - count trailing zeroes
24// - ctzXi2 for unoptimized little and big endian
25
26// ffs - find first set
27// * ffs = (a == 0) => 0, (a != 0) => ctz + 1
28// * dont pay for `if (x == 0) return shift;` inside ctz
29// - ffsXi2 for unoptimized little and big endian
30
31inline fn clzXi2(comptime T: type, a: T) i32 {
32 var x = switch (@bitSizeOf(T)) {
33 32 => @as(u32, @bitCast(a)),
34 64 => @as(u64, @bitCast(a)),
35 128 => @as(u128, @bitCast(a)),
36 else => unreachable,
37 };
38 var n: T = @bitSizeOf(T);
39 // Count first bit set using binary search, from Hacker's Delight
40 var y: @TypeOf(x) = 0;
41 comptime var shift: u8 = @bitSizeOf(T);
42 inline while (shift > 0) {
43 shift = shift >> 1;
44 y = x >> shift;
45 if (y != 0) {
46 n = n - shift;
47 x = y;
48 }
49 }
50 return @intCast(n - @as(T, @bitCast(x)));
51}
52
53fn __clzsi2_thumb1() callconv(.naked) void {
54 @setRuntimeSafety(false);
55
56 // Similar to the generic version with the last two rounds replaced by a LUT
57 asm volatile (
58 \\ movs r1, #32
59 \\ lsrs r2, r0, #16
60 \\ beq 1f
61 \\ subs r1, #16
62 \\ movs r0, r2
63 \\ 1:
64 \\ lsrs r2, r0, #8
65 \\ beq 1f
66 \\ subs r1, #8
67 \\ movs r0, r2
68 \\ 1:
69 \\ lsrs r2, r0, #4
70 \\ beq 1f
71 \\ subs r1, #4
72 \\ movs r0, r2
73 \\ 1:
74 \\ adr r3, .lut
75 \\ ldrb r0, [r3, r0]
76 \\ subs r0, r1, r0
77 \\ bx lr
78 \\ .p2align 2
79 \\ // Number of bits set in the 0-15 range
80 \\ .lut:
81 \\ .byte 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4
82 );
83
84 unreachable;
85}
86
87fn __clzsi2_arm32() callconv(.naked) void {
88 @setRuntimeSafety(false);
89
90 asm volatile (
91 \\ // Assumption: n != 0
92 \\ // r0: n
93 \\ // r1: count of leading zeros in n + 1
94 \\ // r2: scratch register for shifted r0
95 \\ mov r1, #1
96 \\
97 \\ // Basic block:
98 \\ // if ((r0 >> SHIFT) == 0)
99 \\ // r1 += SHIFT;
100 \\ // else
101 \\ // r0 >>= SHIFT;
102 \\ // for descending powers of two as SHIFT.
103 \\ lsrs r2, r0, #16
104 \\ movne r0, r2
105 \\ addeq r1, #16
106 \\
107 \\ lsrs r2, r0, #8
108 \\ movne r0, r2
109 \\ addeq r1, #8
110 \\
111 \\ lsrs r2, r0, #4
112 \\ movne r0, r2
113 \\ addeq r1, #4
114 \\
115 \\ lsrs r2, r0, #2
116 \\ movne r0, r2
117 \\ addeq r1, #2
118 \\
119 \\ // The basic block invariants at this point are (r0 >> 2) == 0 and
120 \\ // r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1.
121 \\ //
122 \\ // r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1)f
123 \\ // ---+----------------+----------------+------------+--------------
124 \\ // 1 | 1 | 0 | 0 | 1
125 \\ // 2 | 0 | 1 | -1 | 0
126 \\ // 3 | 0 | 1 | -1 | 0
127 \\ //
128 \\ // The r1's initial value of 1 compensates for the 1 here.
129 \\ sub r0, r1, r0, lsr #1
130 \\ bx lr
131 );
132
133 unreachable;
134}
135
136fn clzsi2_generic(a: i32) callconv(.c) i32 {
137 return clzXi2(i32, a);
138}
139
140pub const __clzsi2 = switch (builtin.cpu.arch) {
141 .arm, .armeb, .thumb, .thumbeb => impl: {
142 const use_thumb1 =
143 (builtin.cpu.arch.isThumb() or builtin.cpu.has(.arm, .noarm)) and !builtin.cpu.has(.arm, .thumb2);
144
145 if (use_thumb1) {
146 break :impl __clzsi2_thumb1;
147 }
148 // From here on we're either targeting Thumb2 or ARM.
149 else if (!builtin.cpu.arch.isThumb()) {
150 break :impl __clzsi2_arm32;
151 }
152 // Use the generic implementation otherwise.
153 else break :impl clzsi2_generic;
154 },
155 else => clzsi2_generic,
156};
157
158pub fn __clzdi2(a: i64) callconv(.c) i32 {
159 return clzXi2(i64, a);
160}
161
162pub fn __clzti2(a: i128) callconv(.c) i32 {
163 return clzXi2(i128, a);
164}
165
166inline fn ctzXi2(comptime T: type, a: T) i32 {
167 var x = switch (@bitSizeOf(T)) {
168 32 => @as(u32, @bitCast(a)),
169 64 => @as(u64, @bitCast(a)),
170 128 => @as(u128, @bitCast(a)),
171 else => unreachable,
172 };
173 var n: T = 1;
174 // Number of trailing zeroes as binary search, from Hacker's Delight
175 var mask: @TypeOf(x) = std.math.maxInt(@TypeOf(x));
176 comptime var shift = @bitSizeOf(T);
177 if (x == 0) return shift;
178 inline while (shift > 1) {
179 shift = shift >> 1;
180 mask = mask >> shift;
181 if ((x & mask) == 0) {
182 n = n + shift;
183 x = x >> shift;
184 }
185 }
186 return @intCast(n - @as(T, @bitCast((x & 1))));
187}
188
189pub fn __ctzsi2(a: i32) callconv(.c) i32 {
190 return ctzXi2(i32, a);
191}
192
193pub fn __ctzdi2(a: i64) callconv(.c) i32 {
194 return ctzXi2(i64, a);
195}
196
197pub fn __ctzti2(a: i128) callconv(.c) i32 {
198 return ctzXi2(i128, a);
199}
200
201inline fn ffsXi2(comptime T: type, a: T) i32 {
202 var x: @Int(.unsigned, @typeInfo(T).int.bits) = @bitCast(a);
203 var n: T = 1;
204 // adapted from Number of trailing zeroes (see ctzXi2)
205 var mask: @TypeOf(x) = std.math.maxInt(@TypeOf(x));
206 comptime var shift = @bitSizeOf(T);
207 // In contrast to ctz return 0
208 if (x == 0) return 0;
209 inline while (shift > 1) {
210 shift = shift >> 1;
211 mask = mask >> shift;
212 if ((x & mask) == 0) {
213 n = n + shift;
214 x = x >> shift;
215 }
216 }
217 // return ctz + 1
218 return @as(i32, @intCast(n - @as(T, @bitCast((x & 1))))) + 1;
219}
220
221pub fn __ffssi2(a: i32) callconv(.c) i32 {
222 return ffsXi2(i32, a);
223}
224
225pub fn __ffsdi2(a: i64) callconv(.c) i32 {
226 return ffsXi2(i64, a);
227}
228
229pub fn __ffsti2(a: i128) callconv(.c) i32 {
230 return ffsXi2(i128, a);
231}
232
233test {
234 _ = @import("clzsi2_test.zig");
235 _ = @import("clzdi2_test.zig");
236 _ = @import("clzti2_test.zig");
237
238 _ = @import("ctzsi2_test.zig");
239 _ = @import("ctzdi2_test.zig");
240 _ = @import("ctzti2_test.zig");
241
242 _ = @import("ffssi2_test.zig");
243 _ = @import("ffsdi2_test.zig");
244 _ = @import("ffsti2_test.zig");
245}