wsutil/bits_ctz.h

   1 /*
   2  * bitz_ctz.h
   3  *
   4  * Wireshark - Network traffic analyzer
   5  * By Gerald Combs <gerald@wireshark.org>
   6  * Copyright 1998 Gerald Combs
   7  *
   8  * This program is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License
  10  * as published by the Free Software Foundation; either version 2
  11  * of the License, or (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  21  */
  22
  23 #ifndef __WSUTIL_BITS_CTZ_H__
  24 #define __WSUTIL_BITS_CTZ_H__
  25
  26 #include <glib.h>
  27
  28 /* ws_ctz == trailing zeros == position of lowest set bit [0..63] */
  29 /* ws_ilog2 == position of highest set bit == 63 - leading zeros [0..63] */
  30
  31 /* The return value of both ws_ctz and ws_ilog2 is undefined for x == 0 */
  32
  33 #if defined(__GNUC__) && ((__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
  34
  35 static inline int
  36 ws_ctz(guint64 x)
  37 {
  38         return __builtin_ctzll(x);
  39 }
  40
  41 static inline int
  42 ws_ilog2(guint64 x)
  43 {
  44         return 63 - __builtin_clzll(x);
  45 }
  46
  47 #else
  48
  49 static inline int
  50 __ws_ctz32(guint32 x)
  51 {
  52         /* From http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup */
  53         static const guint8 table[32] = {
  54                 0,   1, 28,  2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17,  4, 8,
  55                 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18,  6, 11,  5, 10, 9
  56         };
  57
  58         return table[((guint32)((x & -(gint32)x) * 0x077CB531U)) >> 27];
  59 }
  60
  61 static inline int
  62 ws_ctz(guint64 x)
  63 {
  64         guint32 hi = x >> 32;
  65         guint32 lo = (guint32) x;
  66
  67         if (lo == 0)
  68                 return 32 + __ws_ctz32(hi);
  69         else
  70                 return __ws_ctz32(lo);
  71 }
  72
  73 static inline int
  74 __ws_ilog2_32(guint32 x)
  75 {
  76         /* From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn */
  77         static const guint8 table[32] = {
  78                 0,  9,  1, 10, 13, 21,  2, 29, 11, 14, 16, 18, 22, 25,  3, 30,
  79                 8, 12, 20, 28, 15, 17, 24,  7, 19, 27, 23,  6, 26,  5,  4, 31
  80         };
  81
  82         x |= x >> 1;
  83         x |= x >> 2;
  84         x |= x >> 4;
  85         x |= x >> 8;
  86         x |= x >> 16;
  87
  88         return table[((guint32)(x * 0x07C4ACDDU)) >> 27];
  89 }
  90
  91 static inline int
  92 ws_ilog2(guint64 x)
  93 {
  94         guint32 hi = x >> 32;
  95         guint32 lo = (guint32) x;
  96
  97         if (hi == 0)
  98                 return __ws_ilog2_32(lo);
  99         else
 100                 return 32 + __ws_ilog2_32(hi);
 101 }
 102
 103 #endif
 104
 105 #endif /* __WSUTIL_BITS_CTZ_H__ */