1*0b57cec5SDimitry Andric //===-- ctzsi2.c - Implement __ctzsi2 -------------------------------------===// 2*0b57cec5SDimitry Andric // 3*0b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*0b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*0b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*0b57cec5SDimitry Andric // 7*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 8*0b57cec5SDimitry Andric // 9*0b57cec5SDimitry Andric // This file implements __ctzsi2 for the compiler_rt library. 10*0b57cec5SDimitry Andric // 11*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 12*0b57cec5SDimitry Andric 13*0b57cec5SDimitry Andric #include "int_lib.h" 14*0b57cec5SDimitry Andric 15*0b57cec5SDimitry Andric // Returns: the number of trailing 0-bits 16*0b57cec5SDimitry Andric 17*0b57cec5SDimitry Andric // Precondition: a != 0 18*0b57cec5SDimitry Andric 19*0b57cec5SDimitry Andric COMPILER_RT_ABI si_int __ctzsi2(si_int a) { 20*0b57cec5SDimitry Andric su_int x = (su_int)a; 21*0b57cec5SDimitry Andric si_int t = ((x & 0x0000FFFF) == 0) 22*0b57cec5SDimitry Andric << 4; // if (x has no small bits) t = 16 else 0 23*0b57cec5SDimitry Andric x >>= t; // x = [0 - 0xFFFF] + higher garbage bits 24*0b57cec5SDimitry Andric su_int r = t; // r = [0, 16] 25*0b57cec5SDimitry Andric // return r + ctz(x) 26*0b57cec5SDimitry Andric t = ((x & 0x00FF) == 0) << 3; 27*0b57cec5SDimitry Andric x >>= t; // x = [0 - 0xFF] + higher garbage bits 28*0b57cec5SDimitry Andric r += t; // r = [0, 8, 16, 24] 29*0b57cec5SDimitry Andric // return r + ctz(x) 30*0b57cec5SDimitry Andric t = ((x & 0x0F) == 0) << 2; 31*0b57cec5SDimitry Andric x >>= t; // x = [0 - 0xF] + higher garbage bits 32*0b57cec5SDimitry Andric r += t; // r = [0, 4, 8, 12, 16, 20, 24, 28] 33*0b57cec5SDimitry Andric // return r + ctz(x) 34*0b57cec5SDimitry Andric t = ((x & 0x3) == 0) << 1; 35*0b57cec5SDimitry Andric x >>= t; 36*0b57cec5SDimitry Andric x &= 3; // x = [0 - 3] 37*0b57cec5SDimitry Andric r += t; // r = [0 - 30] and is even 38*0b57cec5SDimitry Andric // return r + ctz(x) 39*0b57cec5SDimitry Andric 40*0b57cec5SDimitry Andric // The branch-less return statement below is equivalent 41*0b57cec5SDimitry Andric // to the following switch statement: 42*0b57cec5SDimitry Andric // switch (x) 43*0b57cec5SDimitry Andric // { 44*0b57cec5SDimitry Andric // case 0: 45*0b57cec5SDimitry Andric // return r + 2; 46*0b57cec5SDimitry Andric // case 2: 47*0b57cec5SDimitry Andric // return r + 1; 48*0b57cec5SDimitry Andric // case 1: 49*0b57cec5SDimitry Andric // case 3: 50*0b57cec5SDimitry Andric // return r; 51*0b57cec5SDimitry Andric // } 52*0b57cec5SDimitry Andric return r + ((2 - (x >> 1)) & -((x & 1) == 0)); 53*0b57cec5SDimitry Andric } 54