Memweight

memweight.c

#include <assert.h>

#define BITS_PER_BYTE 8
#define BITS_PER_LONG 64

#define INT_MAX ((int)(~0U >> 1))

#define UINT_MAX (~0U)

#define __const_hweight8(w) ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))
#define __const_hweight16(w) (__const_hweight8(w) + __const_hweight8((w) >> 8 ))
#define __const_hweight32(w) (__const_hweight16(w) + __const_hweight16((w) >> 16))
#define __const_hweight64(w) (__const_hweight32(w) + __const_hweight32((w) >> 32))

#define hweight32(w) (__builtin_constant_p(w) ? __const_hweight32(w) : __arch_hweight32(w))
#define hweight64(w) (__builtin_constant_p(w) ? __const_hweight64(w) : __arch_hweight64(w))

#define __stringify_1(x...) #x

#define annotate_unreachable()

#define barrier_before_unreachable() asm volatile("")

#define unlikely(x) __builtin_expect(!!(x), 0)

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))

#define __stringify(x...) __stringify_1(x)

#define hweight8(w) (__builtin_constant_p(w) ? __const_hweight8(w) : __arch_hweight8(w))

#define unreachable() do { annotate_unreachable(); barrier_before_unreachable(); __builtin_unreachable(); } while (0)

#define BUG() do { unreachable(); } while (0)

#define BUG_ON(condition) do { if (unlikely(condition)) BUG(); } while (0)

#define __always_inline inline __attribute__((__always_inline__))

#define small_const_nbits(nbits) (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

#define REG_IN "D"
#define REG_OUT "a"
#define X86_FEATURE_POPCNT ( 4*32+23) /* POPCNT instruction */

#define alt_end_marker "663"

#define alt_slen "662b-661b"

#define b_replacement(num) "664"#num

#define e_replacement(num) "665"#num

#define ALTINSTR_REPLACEMENT(newinstr,feature,num) /* replacement */ "# ALT: replacement " #num "\n" b_replacement(num)":\n\t" newinstr "\n" e_replacement(num) ":\n"

#define alt_pad_len alt_end_marker"b-662b"

#define alt_rlen(num) e_replacement(num)"f-"b_replacement(num)"f"

#define alt_total_slen alt_end_marker"b-661b"

#define ALTINSTR_ENTRY(feature,num) " .long 661b - .\n" /* label           */ " .long " b_replacement(num)"f - .\n" /* new instruction */ " .word " __stringify(feature) "\n" /* feature bit     */ " .byte " alt_total_slen "\n" /* source len      */ " .byte " alt_rlen(num) "\n" /* replacement len */ " .byte " alt_pad_len "\n" /* pad len */

#define OLDINSTR(oldinstr,num) "# ALT: oldnstr\n" "661:\n\t" oldinstr "\n662:\n" "# ALT: padding\n" ".skip -(((" alt_rlen(num) ")-(" alt_slen ")) > 0) * " "((" alt_rlen(num) ")-(" alt_slen ")),0x90\n" alt_end_marker ":\n"

#define ALTERNATIVE(oldinstr,newinstr,feature) OLDINSTR(oldinstr, 1) ".pushsection .altinstructions,\"a\"\n" ALTINSTR_ENTRY(feature, 1) ".popsection\n" ".pushsection .altinstr_replacement, \"ax\"\n" ALTINSTR_REPLACEMENT(newinstr, feature, 1) ".popsection\n"

typedef _Bool bool;

typedef unsigned long long __u64;

typedef long __kernel_long_t;

typedef unsigned long __kernel_ulong_t;

typedef __kernel_ulong_t __kernel_size_t;

typedef __kernel_long_t __kernel_ssize_t;

typedef __kernel_size_t size_t;

typedef __kernel_ssize_t ssize_t;

unsigned int __sw_hweight32(unsigned int w)
{
	unsigned int res = w - ((w >> 1) & 0x55555555);
	res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
	res = (res + (res >> 4)) & 0x0F0F0F0F;
	res = res + (res >> 8);
	return (res + (res >> 16)) & 0x000000FF;
}

unsigned int __sw_hweight16(unsigned int w)
{
	unsigned int res = w - ((w >> 1) & 0x5555);
	res = (res & 0x3333) + ((res >> 2) & 0x3333);
	res = (res + (res >> 4)) & 0x0F0F;
	return (res + (res >> 8)) & 0x00FF;
}

unsigned int __sw_hweight8(unsigned int w)
{
	unsigned int res = w - ((w >> 1) & 0x55);
	res = (res & 0x33) + ((res >> 2) & 0x33);
	return (res + (res >> 4)) & 0x0F;
}

unsigned long __sw_hweight64(__u64 w)
{
	__u64 res = w - ((w >> 1) & 0x5555555555555555ul);
	res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
	res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
	res = res + (res >> 8);
	res = res + (res >> 16);
	return (res + (res >> 32)) & 0x00000000000000FFul;
}

static __always_inline unsigned int __arch_hweight32(unsigned int w)
{
	unsigned int res;

	asm (ALTERNATIVE("call __sw_hweight32", "popcntl %1, %0", X86_FEATURE_POPCNT)
			 : "="REG_OUT (res)
			 : REG_IN (w));

	return res;
}

static __always_inline unsigned long __arch_hweight64(__u64 w)
{
	unsigned long res;

	asm (ALTERNATIVE("call __sw_hweight64", "popcntq %1, %0", X86_FEATURE_POPCNT)
			 : "="REG_OUT (res)
			 : REG_IN (w));

	return res;
}

static inline unsigned int __arch_hweight8(unsigned int w)
{
	return __arch_hweight32(w & 0xff);
}

static __always_inline unsigned long hweight_long(unsigned long w)
{
	return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
}

int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
{
	unsigned int k, lim = bits/BITS_PER_LONG;
	int w = 0;

	for (k = 0; k < lim; k++)
		w += hweight_long(bitmap[k]);

	if (bits % BITS_PER_LONG)
		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));

	return w;
}

static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
{
	if (small_const_nbits(nbits))
		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
	return __bitmap_weight(src, nbits);
}

/**
 * memweight - count the total number of bits set in memory area
 * @ptr: pointer to the start of the area
 * @bytes: the size of the area
 */
size_t memweight(const void *ptr, size_t bytes)
{
	size_t ret = 0;
	size_t longs;
	const unsigned char *bitmap = ptr;

	for (; bytes > 0 && ((unsigned long)bitmap) % sizeof(long);
			bytes--, bitmap++)
		ret += hweight8(*bitmap);

	longs = bytes / sizeof(long);
	if (longs) {
		BUG_ON(longs >= INT_MAX / BITS_PER_LONG);
		ret += bitmap_weight((unsigned long *)bitmap,
				longs * BITS_PER_LONG);
		bytes -= longs * sizeof(long);
		bitmap += longs * sizeof(long);
	}
	/*
	 * The reason that this last loop is distinct from the preceding
	 * bitmap_weight() call is to compute 1-bits in the last region smaller
	 * than sizeof(long) properly on big-endian systems.
	 */
	for (; bytes > 0; bytes--, bitmap++)
		ret += hweight8(*bitmap);

	return ret;
}

size_t new_memweight(const void *ptr, size_t bytes)
{
	BUG_ON(bytes >= UINT_MAX / BITS_PER_BYTE);
	return bitmap_weight(ptr, bytes * BITS_PER_BYTE);
}

// clang -fsanitize=fuzzer memweight.c
int LLVMFuzzerTestOneInput(const void *data,
                           size_t size)
{
	assert(memweight(data, size) == new_memweight(data, size));
	return 0;
}