1*156cd587Sjoerg /* ===-- ctzsi2.c - Implement __ctzsi2 -------------------------------------===
2*156cd587Sjoerg *
3*156cd587Sjoerg * The LLVM Compiler Infrastructure
4*156cd587Sjoerg *
5*156cd587Sjoerg * This file is dual licensed under the MIT and the University of Illinois Open
6*156cd587Sjoerg * Source Licenses. See LICENSE.TXT for details.
7*156cd587Sjoerg *
8*156cd587Sjoerg * ===----------------------------------------------------------------------===
9*156cd587Sjoerg *
10*156cd587Sjoerg * This file implements __ctzsi2 for the compiler_rt library.
11*156cd587Sjoerg *
12*156cd587Sjoerg * ===----------------------------------------------------------------------===
13*156cd587Sjoerg */
14*156cd587Sjoerg
15*156cd587Sjoerg #include "int_lib.h"
16*156cd587Sjoerg
17*156cd587Sjoerg /* Returns: the number of trailing 0-bits */
18*156cd587Sjoerg
19*156cd587Sjoerg /* Precondition: a != 0 */
20*156cd587Sjoerg
21*156cd587Sjoerg COMPILER_RT_ABI si_int
__ctzsi2(si_int a)22*156cd587Sjoerg __ctzsi2(si_int a)
23*156cd587Sjoerg {
24*156cd587Sjoerg su_int x = (su_int)a;
25*156cd587Sjoerg si_int t = ((x & 0x0000FFFF) == 0) << 4; /* if (x has no small bits) t = 16 else 0 */
26*156cd587Sjoerg x >>= t; /* x = [0 - 0xFFFF] + higher garbage bits */
27*156cd587Sjoerg su_int r = t; /* r = [0, 16] */
28*156cd587Sjoerg /* return r + ctz(x) */
29*156cd587Sjoerg t = ((x & 0x00FF) == 0) << 3;
30*156cd587Sjoerg x >>= t; /* x = [0 - 0xFF] + higher garbage bits */
31*156cd587Sjoerg r += t; /* r = [0, 8, 16, 24] */
32*156cd587Sjoerg /* return r + ctz(x) */
33*156cd587Sjoerg t = ((x & 0x0F) == 0) << 2;
34*156cd587Sjoerg x >>= t; /* x = [0 - 0xF] + higher garbage bits */
35*156cd587Sjoerg r += t; /* r = [0, 4, 8, 12, 16, 20, 24, 28] */
36*156cd587Sjoerg /* return r + ctz(x) */
37*156cd587Sjoerg t = ((x & 0x3) == 0) << 1;
38*156cd587Sjoerg x >>= t;
39*156cd587Sjoerg x &= 3; /* x = [0 - 3] */
40*156cd587Sjoerg r += t; /* r = [0 - 30] and is even */
41*156cd587Sjoerg /* return r + ctz(x) */
42*156cd587Sjoerg
43*156cd587Sjoerg /* The branch-less return statement below is equivalent
44*156cd587Sjoerg * to the following switch statement:
45*156cd587Sjoerg * switch (x)
46*156cd587Sjoerg * {
47*156cd587Sjoerg * case 0:
48*156cd587Sjoerg * return r + 2;
49*156cd587Sjoerg * case 2:
50*156cd587Sjoerg * return r + 1;
51*156cd587Sjoerg * case 1:
52*156cd587Sjoerg * case 3:
53*156cd587Sjoerg * return r;
54*156cd587Sjoerg * }
55*156cd587Sjoerg */
56*156cd587Sjoerg return r + ((2 - (x >> 1)) & -((x & 1) == 0));
57*156cd587Sjoerg }
58