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 int
  15 i_log2 (size_t x)
  16 {
  17   /* -1 works best for to_pow2. */
  18   if (!x)
  19     return -1;
  20
  21   /* GCC 3.4 also has this. */
  22   /* The preprocessor criteria here must match what's in pow2.h, to prevent
  23    * infinite recursion.
  24    */
  25 # if defined __GNUC__ && __GNUC__ >= 4 || defined __clang__
  26   return i_log2_fast(x);
  27 # else
  28   {
  29     unsigned bits = sizeof(x) * CHAR_BIT;
  30     size_t mask = (size_t)-1;
  31     unsigned result = bits - 1;
  32
  33     while (bits) {
  34       if (!(x & mask)) {
  35         result -= bits;
  36         x <<= bits;
  37       }
  38
  39       bits >>= 1;
  40       mask <<= bits;
  41     }
  42
  43     return result;
  44   }
  45 # endif
  46 }
  47
  48 size_t
  49 to_pow2 (size_t x)
  50 {
  51   return !x ? 1 : 1 << (i_log2(x - 1) + 1);
  52 }