Skip to content

Instantly share code, notes, and snippets.

@evdenis evdenis/memweight.c
Last active Sep 13, 2019

Embed
What would you like to do?
Memweight
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.