gcc/hwint.c

   1 /* Operations on HOST_WIDE_INT.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24
  25 #if GCC_VERSION < 3004
  26
  27 /* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2 and exact_log2
  28    are defined as inline functions in hwint.h if GCC_VERSION >= 3004.
  29    The definitions here are used for older versions of GCC and non-GCC
  30    bootstrap compilers.  */
  31
  32 /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
  33    If X is 0, return -1.  */
  34
  35 int
  36 floor_log2 (unsigned HOST_WIDE_INT x)
  37 {
  38   int t = 0;
  39
  40   if (x == 0)
  41     return -1;
  42
  43   if (HOST_BITS_PER_WIDE_INT > 64)
  44     if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64))
  45       t += 64;
  46   if (HOST_BITS_PER_WIDE_INT > 32)
  47     if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32))
  48       t += 32;
  49   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16))
  50     t += 16;
  51   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8))
  52     t += 8;
  53   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4))
  54     t += 4;
  55   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2))
  56     t += 2;
  57   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1))
  58     t += 1;
  59
  60   return t;
  61 }
  62
  63 /* Return the logarithm of X, base 2, considering X unsigned,
  64    if X is a power of 2.  Otherwise, returns -1.  */
  65
  66 int
  67 exact_log2 (unsigned HOST_WIDE_INT x)
  68 {
  69   if (x != (x & -x))
  70     return -1;
  71   return floor_log2 (x);
  72 }
  73
  74 /* Given X, an unsigned number, return the number of least significant bits
  75    that are zero.  When X == 0, the result is the word size.  */
  76
  77 int
  78 ctz_hwi (unsigned HOST_WIDE_INT x)
  79 {
  80   return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT;
  81 }
  82
  83 /* Similarly for most significant bits.  */
  84
  85 int
  86 clz_hwi (unsigned HOST_WIDE_INT x)
  87 {
  88   return HOST_BITS_PER_WIDE_INT - 1 - floor_log2(x);
  89 }
  90
  91 /* Similar to ctz_hwi, except that the least significant bit is numbered
  92    starting from 1, and X == 0 yields 0.  */
  93
  94 int
  95 ffs_hwi (unsigned HOST_WIDE_INT x)
  96 {
  97   return 1 + floor_log2 (x & -x);
  98 }
  99
 100 #endif /* GCC_VERSION < 3004 */