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