Project

General

Profile

Feature #8748 ยป popcount.patch

akr (Akira Tanaka), 08/07/2013 09:51 PM

View differences:

configure.in (working copy)
RUBY_CHECK_BUILTIN_FUNC(__builtin_clz, [__builtin_clz(0)])
RUBY_CHECK_BUILTIN_FUNC(__builtin_clzl, [__builtin_clzl(0)])
RUBY_CHECK_BUILTIN_FUNC(__builtin_clzll, [__builtin_clzll(0)])
RUBY_CHECK_BUILTIN_FUNC(__builtin_popcount, [__builtin_popcount(0)])
RUBY_CHECK_BUILTIN_FUNC(__builtin_popcountl, [__builtin_popcountl(0)])
RUBY_CHECK_BUILTIN_FUNC(__builtin_popcountll, [__builtin_popcountll(0)])
# Some platform need -lrt for clock_gettime, but the other don't.
if test x"$ac_cv_func_clock_gettime" != xyes; then
numeric.c (working copy)
/*
* call-seq:
* int.popcount -> integer
*
* Returns the number of one bits in the absolute number of +int+.
*
* 0.popcount #=> 0
* 0b1010.popcount #=> 2
* (-0b1011).popcount #=> 3
*/
static VALUE
fix_popcount(VALUE num)
{
long i = FIX2LONG(num);
if (i < 0)
i = -i;
return LONG2FIX(popcount_long((unsigned long)i));
}
/*
* call-seq:
* int.next -> integer
* int.succ -> integer
*
......
rb_define_method(rb_cFixnum, "odd?", fix_odd_p, 0);
rb_define_method(rb_cFixnum, "even?", fix_even_p, 0);
rb_define_method(rb_cFixnum, "succ", fix_succ, 0);
rb_define_method(rb_cFixnum, "popcount", fix_popcount, 0);
rb_cFloat = rb_define_class("Float", rb_cNumeric);
bignum.c (working copy)
}
/*
* call-seq:
* int.popcount -> integer
*
* Returns the number of one bits in the absolute number of +int+.
*
* (2**100).popcount #=> 1
* (2**100-1).popcount #=> 100
* (-2**100).popcount #=> 1
* (10**100).popcount #=> 105
* (257**257).popcount #=> 999
*/
static VALUE
rb_big_popcount(VALUE num)
{
long n = RBIGNUM_LEN(num);
BDIGIT *ds = BDIGITS(num);
VALUE result = LONG2FIX(0);
long r = 0;
int pop;
while (0 < n) {
n--;
#if SIZEOF_BDIGITS <= SIZEOF_INT
pop = popcount_int((unsigned int)ds[n]);
#elif SIZEOF_BDIGITS <= SIZEOF_LONG
pop = popcount_long((unsigned long)ds[n]);
#elif defined(HAVE_LONG_LONG) && SIZEOF_BDIGITS <= SIZEOF_LONG_LONG
pop = popcount_long_long((unsigned LONG_LONG)ds[n]);
#else
# error too big BDIGIT type.
#endif
r += pop;
if (FIXNUM_MAX < r) {
if (result == LONG2FIX(0))
result = rb_uint2big(r);
else
result = bigadd_int(result, r);
}
}
if (r != 0) {
if (result == LONG2FIX(0))
result = LONG2NUM(r);
else
result = bigadd_int(result, r);
}
return result;
}
/*
* Bignum objects hold integers outside the range of
* Fixnum. Bignum objects are created
* automatically when integer calculations would otherwise overflow a
......
rb_define_method(rb_cBignum, "size", rb_big_size, 0);
rb_define_method(rb_cBignum, "odd?", rb_big_odd_p, 0);
rb_define_method(rb_cBignum, "even?", rb_big_even_p, 0);
rb_define_method(rb_cBignum, "popcount", rb_big_popcount, 0);
power_cache_init();
}
internal.h (working copy)
# endif
#endif
#define MASK_8x2(mask) (((mask) << 8) | (mask))
#define MASK_8x4(mask) ((MASK_8x2(mask) << 16) | MASK_8x2(mask))
#define MASK_8x8(mask) ((MASK_8x4(mask) << 32) | MASK_8x4(mask))
#define MASK_8x16(mask) ((MASK_8x8(mask) << 64) | MASK_8x8(mask))
#if SIZEOF_INT * CHAR_BIT <= 16
# define MASK_INT(byte) MASK_8x2((unsigned int)(byte))
#elif SIZEOF_INT * CHAR_BIT <= 32
# define MASK_INT(byte) MASK_8x4((unsigned int)(byte))
#elif SIZEOF_INT * CHAR_BIT <= 64
# define MASK_INT(byte) MASK_8x8((unsigned int)(byte))
#elif SIZEOF_INT * CHAR_BIT <= 128
# define MASK_INT(byte) MASK_8x16((unsigned int)(byte))
#else
# error too big integer type
#endif
#if SIZEOF_LONG * CHAR_BIT <= 16
# define MASK_LONG(byte) MASK_8x2((unsigned long)(byte))
#elif SIZEOF_LONG * CHAR_BIT <= 32
# define MASK_LONG(byte) MASK_8x4((unsigned long)(byte))
#elif SIZEOF_LONG * CHAR_BIT <= 64
# define MASK_LONG(byte) MASK_8x8((unsigned long)(byte))
#elif SIZEOF_LONG * CHAR_BIT <= 128
# define MASK_LONG(byte) MASK_8x16((unsigned long)(byte))
#else
# error too big integer type
#endif
#ifdef HAVE_LONG_LONG
# if SIZEOF_LONG_LONG * CHAR_BIT <= 16
# define MASK_LONG_LONG(byte) MASK_8x2((unsigned LONG_LONG)(byte))
# elif SIZEOF_LONG_LONG * CHAR_BIT <= 32
# define MASK_LONG_LONG(byte) MASK_8x4((unsigned LONG_LONG)(byte))
# elif SIZEOF_LONG_LONG * CHAR_BIT <= 64
# define MASK_LONG_LONG(byte) MASK_8x8((unsigned LONG_LONG)(byte))
# elif SIZEOF_LONG_LONG * CHAR_BIT <= 128
# define MASK_LONG_LONG(byte) MASK_8x16((unsigned LONG_LONG)(byte))
# else
# error too big integer type
# endif
#endif
#if defined(HAVE_BUILTIN___BUILTIN_POPCOUNT)
# define popcount_int(x) __builtin_popcount(x)
#else
static inline int
popcount_int(unsigned int x)
{
x -= (x >> 1) & MASK_INT(0x55);
x = ((x >> 2) & MASK_INT(0x33)) + (x & MASK_INT(0x33));
x = ((x >> 4) + x) & MASK_INT(0x0f);
x += (x >> 8);
x += (x >> 16);
#if 32 < SIZEOF_INT * CHAR_BIT
x += (x >> 32);
#endif
#if 64 < SIZEOF_INT * CHAR_BIT
x += (x >> 64);
#endif
#if 128 < SIZEOF_INT * CHAR_BIT
# error too big integer type
#endif
return (int)(x & 0xff);
}
#endif
#if defined(HAVE_BUILTIN___BUILTIN_POPCOUNTL)
# define popcount_long(x) __builtin_popcountl(x)
#else
static inline int
popcount_long(unsigned long x)
{
x -= (x >> 1) & MASK_LONG(0x55);
x = ((x >> 2) & MASK_LONG(0x33)) + (x & MASK_LONG(0x33));
x = ((x >> 4) + x) & MASK_LONG(0x0f);
x += (x >> 8);
x += (x >> 16);
#if 32 < SIZEOF_LONG * CHAR_BIT
x += (x >> 32);
#endif
#if 64 < SIZEOF_LONG * CHAR_BIT
x += (x >> 64);
#endif
#if 128 < SIZEOF_LONG * CHAR_BIT
# error too big integer type
#endif
return (int)(x & 0xff);
}
#endif
#ifdef HAVE_LONG_LONG
# if defined(HAVE_BUILTIN___BUILTIN_POPCOUNTLL)
# define popcount_long_long(x) __builtin_popcountll(x)
# else
static inline int
popcount_long_long(unsigned LONG_LONG x)
{
x -= (x >> 1) & MASK_LONG_LONG(0x55);
x = ((x >> 2) & MASK_LONG_LONG(0x33)) + (x & MASK_LONG_LONG(0x33));
x = ((x >> 4) + x) & MASK_LONG_LONG(0x0f);
x += (x >> 8);
x += (x >> 16);
#if 32 < SIZEOF_LONG_LONG * CHAR_BIT
x += (x >> 32);
#endif
#if 64 < SIZEOF_LONG_LONG * CHAR_BIT
x += (x >> 64);
#endif
#if 128 < SIZEOF_LONG_LONG * CHAR_BIT
# error too big integer type
#endif
return (int)(x & 0xff);
}
# endif
#endif
struct rb_deprecated_classext_struct {
char conflict[sizeof(VALUE) * 3];
};
test/ruby/test_integer.rb (working copy)
end
assert_equal(3 ^ 10, 3 ^ obj)
end
def test_popcount
assert_equal(1, -1.popcount)
assert_equal(0, 0.popcount)
assert_equal(1, 1.popcount)
-100.upto(100) {|n|
assert_equal(n.abs.to_s(2).count("1"), n.popcount)
}
0.upto(100) {|k|
n = 3**k
assert_equal(n.abs.to_s(2).count("1"), n.popcount)
n = -n
assert_equal(n.abs.to_s(2).count("1"), n.popcount)
}
end
end
    (1-1/1)