git.hungrycats.org Git - xscreensaver/blob - utils/pow2.c

   1 /* pow2, Copyright (c) 2016 Dave Odell <dmo2118@gmail.com>
   2  *
   3  * Permission to use, copy, modify, distribute, and sell this software and its
   4  * documentation for any purpose is hereby granted without fee, provided that
   5  * the above copyright notice appear in all copies and that both that
   6  * copyright notice and this permission notice appear in supporting
   7  * documentation.  No representations are made about the suitability of this
   8  * software for any purpose.  It is provided "as is" without express or
   9  * implied warranty.
  10  */
  11
  12 #include "pow2.h"
  13
  14 #include <limits.h>
  15
  16 int
  17 i_log2 (size_t x)
  18 {
  19   /* -1 works best for to_pow2. */
  20   if (!x)
  21     return -1;
  22
  23   /* GCC 3.4 also has this. */
  24 # if defined __GNUC__ && __GNUC__ >= 4 || defined __clang__
  25   return sizeof(long) * CHAR_BIT - __builtin_clzl(x) - 1;
  26 # else
  27   {
  28     unsigned bits = sizeof(x) * CHAR_BIT;
  29     size_t mask = (size_t)-1;
  30     unsigned result = bits - 1;
  31
  32     while (bits) {
  33       if (!(x & mask)) {
  34         result -= bits;
  35         x <<= bits;
  36       }
  37
  38       bits >>= 1;
  39       mask <<= bits;
  40     }
  41
  42     return result;
  43   }
  44 # endif
  45 }
  46
  47 size_t
  48 to_pow2 (size_t x)
  49 {
  50   return !x ? 1 : 1 << (i_log2(x - 1) + 1);
  51 }