10b57cec5SDimitry Andric //===-- ctzsi2.c - Implement __ctzsi2 -------------------------------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements __ctzsi2 for the compiler_rt library. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric #include "int_lib.h" 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric // Returns: the number of trailing 0-bits 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric // Precondition: a != 0 180b57cec5SDimitry Andric 19*5ffd83dbSDimitry Andric COMPILER_RT_ABI int __ctzsi2(si_int a) { 200b57cec5SDimitry Andric su_int x = (su_int)a; 210b57cec5SDimitry Andric si_int t = ((x & 0x0000FFFF) == 0) 220b57cec5SDimitry Andric << 4; // if (x has no small bits) t = 16 else 0 230b57cec5SDimitry Andric x >>= t; // x = [0 - 0xFFFF] + higher garbage bits 240b57cec5SDimitry Andric su_int r = t; // r = [0, 16] 250b57cec5SDimitry Andric // return r + ctz(x) 260b57cec5SDimitry Andric t = ((x & 0x00FF) == 0) << 3; 270b57cec5SDimitry Andric x >>= t; // x = [0 - 0xFF] + higher garbage bits 280b57cec5SDimitry Andric r += t; // r = [0, 8, 16, 24] 290b57cec5SDimitry Andric // return r + ctz(x) 300b57cec5SDimitry Andric t = ((x & 0x0F) == 0) << 2; 310b57cec5SDimitry Andric x >>= t; // x = [0 - 0xF] + higher garbage bits 320b57cec5SDimitry Andric r += t; // r = [0, 4, 8, 12, 16, 20, 24, 28] 330b57cec5SDimitry Andric // return r + ctz(x) 340b57cec5SDimitry Andric t = ((x & 0x3) == 0) << 1; 350b57cec5SDimitry Andric x >>= t; 360b57cec5SDimitry Andric x &= 3; // x = [0 - 3] 370b57cec5SDimitry Andric r += t; // r = [0 - 30] and is even 380b57cec5SDimitry Andric // return r + ctz(x) 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric // The branch-less return statement below is equivalent 410b57cec5SDimitry Andric // to the following switch statement: 420b57cec5SDimitry Andric // switch (x) 430b57cec5SDimitry Andric // { 440b57cec5SDimitry Andric // case 0: 450b57cec5SDimitry Andric // return r + 2; 460b57cec5SDimitry Andric // case 2: 470b57cec5SDimitry Andric // return r + 1; 480b57cec5SDimitry Andric // case 1: 490b57cec5SDimitry Andric // case 3: 500b57cec5SDimitry Andric // return r; 510b57cec5SDimitry Andric // } 520b57cec5SDimitry Andric return r + ((2 - (x >> 1)) & -((x & 1) == 0)); 530b57cec5SDimitry Andric } 54