ctzsi2.c revision 276851
150477Speter/* ===-- ctzsi2.c - Implement __ctzsi2 -------------------------------------=== 235388Smjacob * 348487Smjacob * The LLVM Compiler Infrastructure 435388Smjacob * 548487Smjacob * This file is dual licensed under the MIT and the University of Illinois Open 635388Smjacob * Source Licenses. See LICENSE.TXT for details. 735388Smjacob * 835388Smjacob * ===----------------------------------------------------------------------=== 935388Smjacob * 1035388Smjacob * This file implements __ctzsi2 for the compiler_rt library. 1135388Smjacob * 1235388Smjacob * ===----------------------------------------------------------------------=== 1335388Smjacob */ 1435388Smjacob 1535388Smjacob#include "int_lib.h" 1635388Smjacob 1735388Smjacob/* Returns: the number of trailing 0-bits */ 1835388Smjacob 1935388Smjacob/* Precondition: a != 0 */ 2035388Smjacob 2135388SmjacobCOMPILER_RT_ABI si_int 2235388Smjacob__ctzsi2(si_int a) 2335388Smjacob{ 2435388Smjacob su_int x = (su_int)a; 2535388Smjacob si_int t = ((x & 0x0000FFFF) == 0) << 4; /* if (x has no small bits) t = 16 else 0 */ 2635388Smjacob x >>= t; /* x = [0 - 0xFFFF] + higher garbage bits */ 2735388Smjacob su_int r = t; /* r = [0, 16] */ 2835388Smjacob /* return r + ctz(x) */ 2935388Smjacob t = ((x & 0x00FF) == 0) << 3; 3035388Smjacob x >>= t; /* x = [0 - 0xFF] + higher garbage bits */ 3135388Smjacob r += t; /* r = [0, 8, 16, 24] */ 3235388Smjacob /* return r + ctz(x) */ 3335388Smjacob t = ((x & 0x0F) == 0) << 2; 3435388Smjacob x >>= t; /* x = [0 - 0xF] + higher garbage bits */ 3535388Smjacob r += t; /* r = [0, 4, 8, 12, 16, 20, 24, 28] */ 3635388Smjacob /* return r + ctz(x) */ 3758100Smjacob t = ((x & 0x3) == 0) << 1; 3861773Smjacob x >>= t; 3939235Sgibbs x &= 3; /* x = [0 - 3] */ 4048487Smjacob r += t; /* r = [0 - 30] and is even */ 4139445Smjacob /* return r + ctz(x) */ 4248487Smjacob 4348487Smjacob/* The branch-less return statement below is equivalent 4448487Smjacob * to the following switch statement: 4548487Smjacob * switch (x) 4659452Smjacob * { 4762496Smjacob * case 0: 4839445Smjacob * return r + 2; 4948487Smjacob * case 2: 5048487Smjacob * return r + 1; 5148487Smjacob * case 1: 5248487Smjacob * case 3: 5362496Smjacob * return r; 5439445Smjacob * } 5548487Smjacob */ 5648487Smjacob return r + ((2 - (x >> 1)) & -((x & 1) == 0)); 5748487Smjacob} 5848487Smjacob