Skip to content

Instantly share code, notes, and snippets.

@imaami

imaami/popcnt.h

Last active September 16, 2024 19:51
Show Gist options
  • Save imaami/2c0c9e41eabea886460735d5fc9f5882 to your computer and use it in GitHub Desktop.
Save imaami/2c0c9e41eabea886460735d5fc9f5882 to your computer and use it in GitHub Desktop.
Download ZIP
Generic popcount
Raw
popcnt.h
/** @file popcnt.h
*/
#ifndef POPCNT_H_
#define POPCNT_H_
#include <limits.h>
#include <stdint.h>
#undef define_popcnt
#undef popcnt16_impl
#undef popcnt32_impl
#undef popcnt64_impl
#undef popcnt_compat
#undef popcnt_inline
#ifdef _MSC_VER
# define popcnt_inline __forceinline
# define popcnt16_impl return __popcnt16
# define popcnt32_impl return __popcnt
# define popcnt64_impl return __popcnt64
# ifndef typeof
# define typeof __typeof__
# endif
# ifdef _M_IX86
# define __popcnt64(x) \
(__popcnt((uint32_t)(x >> 32U)) + \
__popcnt((uint32_t)(x & ~(uint32_t)0)))
# endif
# define popcnt_pre_pragma _Pragma("warning(push)") \
_Pragma("warning(disable: 4116)")
# define popcnt_post_pragma _Pragma("warning(pop)")
#else
# define popcnt_inline inline __attribute__((always_inline,const))
# ifndef __has_builtin
# define __has_builtin(x) 0
# endif
# if __has_builtin(__builtin_popcount) && (UINT_MAX == UINT32_MAX)
# define popcnt16_impl return (uint16_t)__builtin_popcount
# define popcnt32_impl return (uint32_t)__builtin_popcount
# endif
# if !defined(popcnt32_impl) && \
__has_builtin(__builtin_popcountl) && (ULONG_MAX == UINT32_MAX)
# define popcnt16_impl return (uint16_t)__builtin_popcountl
# define popcnt32_impl return (uint32_t)__builtin_popcountl
# endif
# if __has_builtin(__builtin_popcountl) && (ULONG_MAX == UINT64_MAX)
# define popcnt64_impl return (uint64_t)__builtin_popcountl
# endif
# if !defined(popcnt64_impl) && \
__has_builtin(__builtin_popcountll) && (ULLONG_MAX == UINT64_MAX)
# define popcnt64_impl return (uint64_t)__builtin_popcountll
# endif
# if __has_builtin(__builtin_popcountg)
# if !defined(popcnt16_impl)
# define popcnt16_impl return (uint16_t)__builtin_popcountg
# endif
# if !defined(popcnt32_impl)
# define popcnt32_impl return (uint32_t)__builtin_popcountg
# endif
# if !defined(popcnt64_impl)
# define popcnt64_impl return (uint64_t)__builtin_popcountg
# endif
# endif
#endif
#define define_popcnt(b, ...) popcnt_inline \
static uint##b##_t popcnt##b(uint##b##_t val) \
{ __VA_ARGS__(val); } _Static_assert(b>0, #b)
#define popcnt_compat(x) typeof(_Generic( \
(char(*)[2 - (sizeof(x) > 4U)])0 \
,char(*)[1]: (uint64_t)0 \
,char(*)[2]: (uint32_t)0)) y = (x); \
y -= (typeof(y))-1/3 & (y >> 1U); \
y = ((typeof(y))-1/5 & (y >> 2U)) \
+ ((typeof(y))-1/5 & y); \
return ((typeof(y))-1/ 17 & ((y >> 4U) + y)) \
* ((typeof(y))-1/255) >> (sizeof y - 1U) \
* CHAR_BIT
#ifndef popcnt16_impl
# define popcnt16_impl popcnt_compat
#endif
#ifndef popcnt32_impl
# define popcnt32_impl popcnt_compat
#endif
#ifndef popcnt64_impl
# define popcnt64_impl popcnt_compat
#endif
#ifndef popcnt_pre_pragma
# define popcnt_pre_pragma
#endif
#ifndef popcnt_post_pragma
# define popcnt_post_pragma
#endif
define_popcnt(16, popcnt16_impl);
define_popcnt(32, popcnt32_impl);
define_popcnt(64, popcnt64_impl);
#undef define_popcnt
#undef popcnt16_impl
#undef popcnt32_impl
#undef popcnt64_impl
#undef popcnt_compat
#undef popcnt_inline
#if defined(_MSC_VER) && defined(_M_IX86)
# undef __popcnt64
#endif
#define popcnt(x) popcnt_pre_pragma _Generic((x), \
typeof(_Generic((char)0, \
signed char: (struct{int i;}){0}, \
unsigned char: (struct{int i;}){0}, \
default: (char)0)): popcnt16, \
signed char: popcnt16, short: popcnt16, \
unsigned char: popcnt16, int: popcnt32, \
unsigned short: popcnt16, unsigned: popcnt32, \
long long: popcnt64, unsigned long: _Generic( \
&(int[sizeof 1UL]){0}, \
int(*)[sizeof(uint32_t)]: popcnt32, \
int(*)[sizeof(uint64_t)]: popcnt64), \
unsigned long long: popcnt64, long: _Generic( \
&(int[sizeof 1L]){0}, \
int(*)[sizeof(int32_t)]: popcnt32, \
int(*)[sizeof(int64_t)]: popcnt64)) \
(_Generic((x), default: (x), \
long long: (unsigned long long)(x), \
signed char: (unsigned char)(x), \
short: (unsigned short)(x), \
typeof(_Generic((char)0, \
signed char: \
(struct{int i;}){0}, \
unsigned char: \
(struct{int i;}){0}, \
default: (char)0)): \
(unsigned char)(x), \
long: (unsigned long)(x), \
int: (unsigned)(x))) popcnt_post_pragma
#endif /* POPCNT_H_ */
Raw
test-popcnt.c
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "popcnt.h"
int
main (int c,
char **v)
{
for (int i = 1; i < c; ++i) {
unsigned long long n = 0;
int e = v[i] && v[i][0] ? 0 : EINVAL;
if (!e) {
errno = 0;
char *ep = v[i];
n = (typeof(n))strtoll(v[i], &ep, 0);
e = errno;
if (e == ERANGE) {
errno = 0;
ep = v[i];
n = strtoull(v[i], &ep, 0);
e = errno;
}
if (!e && *ep)
e = EINVAL;
}
if (e) {
(void)fprintf(stderr, "%s: \"%s\"\n",
strerror(e), v[i]);
continue;
}
#define fmt(T) "%3zu " #T "\n"
#define run(T) , (size_t)popcnt((T)n)
#define test_types(T) T(char ) \
T(signed char ) T(unsigned char ) \
T(signed short ) T(unsigned short ) \
T(signed int ) T(unsigned int ) \
T(signed long ) T(unsigned long ) \
T(signed long long) T(unsigned long long)
(void)printf(test_types(fmt) " \033[1m"
"\033[38;5;99m0x"
"\033[94m%08llx\033[96m%04llx"
"\033[92m%02llx\033[93m%02llx"
"\033[m\n" test_types(run)
, n >> 32U
, n >> 16U & 0xffffU
, n >> 8U & 0x00ffU
, n & 0x00ffU);
#undef test_types
#undef run
#undef fmt
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment