36#include <m4ri/m4ri_config.h>
42#if __M4RI_USE_MM_MALLOC
50#define __STDC_LIMIT_MACROS
99#define __M4RI_CONVERT_TO_INT(w) ((int)(w))
111#define __M4RI_CONVERT_TO_BIT(w) ((BIT)(w))
125#define __M4RI_CONVERT_TO_UINT64_T(w) (w)
135#define __M4RI_CONVERT_TO_WORD(i) ((word)(i))
163#define MAX(x, y) (((x) > (y)) ? (x) : (y))
174#define MIN(x, y) (((x) < (y)) ? (x) : (y))
199#define __M4RI_TWOPOW(i) ((uint64_t)1 << (i))
208#define __M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot))
217#define __M4RI_SET_BIT(w, spot) ((w) |= (m4ri_one << (spot)))
226#define __M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one)
236#define __M4RI_WRITE_BIT(w, spot, value) \
237 ((w) = (((w) & ~(m4ri_one << (spot))) | (__M4RI_CONVERT_TO_WORD(value) << (spot))))
246#define __M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot)))
272#define __M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix)
297#define __M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n)))
315#define __M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset))
324 v = ((v >> 1) & 0x5555555555555555ULL) | ((v & 0x5555555555555555ULL) << 1);
325 v = ((v >> 2) & 0x3333333333333333ULL) | ((v & 0x3333333333333333ULL) << 2);
326 v = ((v >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((v & 0x0F0F0F0F0F0F0F0FULL) << 4);
327 v = ((v >> 8) & 0x00FF00FF00FF00FFULL) | ((v & 0x00FF00FF00FF00FFULL) << 8);
328 v = ((v >> 16) & 0x0000FFFF0000FFFFULL) | ((v & 0x0000FFFF0000FFFFULL) << 16);
329 v = (v >> 32) | (v << 32);
349 switch (length - 1) {
350 case 15: to |= (from & (
m4ri_one << (Q[15] - base))) >> (Q[15] - 15 - base);
351 case 14: to |= (from & (
m4ri_one << (Q[14] - base))) >> (Q[14] - 14 - base);
352 case 13: to |= (from & (
m4ri_one << (Q[13] - base))) >> (Q[13] - 13 - base);
353 case 12: to |= (from & (
m4ri_one << (Q[12] - base))) >> (Q[12] - 12 - base);
354 case 11: to |= (from & (
m4ri_one << (Q[11] - base))) >> (Q[11] - 11 - base);
355 case 10: to |= (from & (
m4ri_one << (Q[10] - base))) >> (Q[10] - 10 - base);
356 case 9: to |= (from & (
m4ri_one << (Q[9] - base))) >> (Q[9] - 9 - base);
357 case 8: to |= (from & (
m4ri_one << (Q[8] - base))) >> (Q[8] - 8 - base);
358 case 7: to |= (from & (
m4ri_one << (Q[7] - base))) >> (Q[7] - 7 - base);
359 case 6: to |= (from & (
m4ri_one << (Q[6] - base))) >> (Q[6] - 6 - base);
360 case 5: to |= (from & (
m4ri_one << (Q[5] - base))) >> (Q[5] - 5 - base);
361 case 4: to |= (from & (
m4ri_one << (Q[4] - base))) >> (Q[4] - 4 - base);
362 case 3: to |= (from & (
m4ri_one << (Q[3] - base))) >> (Q[3] - 3 - base);
363 case 2: to |= (from & (
m4ri_one << (Q[2] - base))) >> (Q[2] - 2 - base);
364 case 1: to |= (from & (
m4ri_one << (Q[1] - base))) >> (Q[1] - 1 - base);
365 case 0: to |= (from & (
m4ri_one << (Q[0] - base))) >> (Q[0] - 0 - base);
break;
391 switch (length - 1) {
392 case 15: to |= (from & (
m4ri_one << (15))) << (Q[15] - 15 - base);
393 case 14: to |= (from & (
m4ri_one << (14))) << (Q[14] - 14 - base);
394 case 13: to |= (from & (
m4ri_one << (13))) << (Q[13] - 13 - base);
395 case 12: to |= (from & (
m4ri_one << (12))) << (Q[12] - 12 - base);
396 case 11: to |= (from & (
m4ri_one << (11))) << (Q[11] - 11 - base);
397 case 10: to |= (from & (
m4ri_one << (10))) << (Q[10] - 10 - base);
398 case 9: to |= (from & (
m4ri_one << (9))) << (Q[9] - 9 - base);
399 case 8: to |= (from & (
m4ri_one << (8))) << (Q[8] - 8 - base);
400 case 7: to |= (from & (
m4ri_one << (7))) << (Q[7] - 7 - base);
401 case 6: to |= (from & (
m4ri_one << (6))) << (Q[6] - 6 - base);
402 case 5: to |= (from & (
m4ri_one << (5))) << (Q[5] - 5 - base);
403 case 4: to |= (from & (
m4ri_one << (4))) << (Q[4] - 4 - base);
404 case 3: to |= (from & (
m4ri_one << (3))) << (Q[3] - 3 - base);
405 case 2: to |= (from & (
m4ri_one << (2))) << (Q[2] - 2 - base);
406 case 1: to |= (from & (
m4ri_one << (1))) << (Q[1] - 1 - base);
407 case 0: to |= (from & (
m4ri_one << (0))) << (Q[0] - 0 - base);
break;
421#define __M4RI_ALIGNMENT(addr, n) (((unsigned long)(addr)) % (n))
430#if defined(__GNUC__) && defined(__GNUC_MINOR__)
431#define __M4RI_GNUC_PREREQ(maj, min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
433#define __M4RI_GNUC_PREREQ(maj, min) FALSE
437#if __M4RI_GNUC_PREREQ(3, 0) || defined(M4RI_DOXYGEN)
443#define __M4RI_LIKELY(cond) __builtin_expect((cond) != 0, 1)
449#define __M4RI_UNLIKELY(cond) __builtin_expect((cond) != 0, 0)
452#define __M4RI_LIKELY(cond) (cond)
453#define __M4RI_UNLIKELY(cond) (cond)
473 return !(ib ? ((ia - 1) ^ ia) & ib : !ia);
493void m4ri_die(
const char *errormessage, ...);
514 if (rand() < RAND_MAX / 2) {
539void __attribute__((constructor))
m4ri_init(
void);
545#pragma init(m4ri_init)
556void __attribute__((destructor))
m4ri_fini(
void);
562#pragma fini(m4ri_fini)
569#if __M4RI_CPU_L3_CACHE == 0
575#undef __M4RI_CPU_L3_CACHE
576#if __M4RI_CPU_L2_CACHE
577#define __M4RI_CPU_L3_CACHE __M4RI_CPU_L2_CACHE
579#define __M4RI_CPU_L3_CACHE 4194304
583#if __M4RI_CPU_L2_CACHE == 0
588#undef __M4RI_CPU_L2_CACHE
589#define __M4RI_CPU_L2_CACHE 262144
592#if __M4RI_CPU_L1_CACHE == 0
597#undef __M4RI_CPU_L1_CACHE
598#define __M4RI_CPU_L1_CACHE 16384
616#if __M4RI_USE_MM_MALLOC
617 newthing = _mm_malloc(count * size, 64);
618#elif __M4RI_USE_POSIX_MEMALIGN
619 int error = posix_memalign(&newthing, 64, count * size);
620 if (error) newthing = NULL;
622 newthing = calloc(count, size);
625 if (newthing == NULL) {
626 m4ri_die(
"m4ri_mm_calloc: calloc returned NULL\n");
629#if __M4RI_USE_MM_MALLOC || __M4RI_USE_POSIX_MEMALIGN
630 char *b = (
char *)newthing;
631 memset(b, 0, count * size);
653#if __M4RI_USE_MM_MALLOC
654 newthing = _mm_malloc(size, alignment);
655#elif __M4RI_USE_POSIX_MEMALIGN
656 int error = posix_memalign(&newthing, alignment, size);
657 if (error) newthing = NULL;
659 newthing = malloc(size);
662 if (newthing == NULL && (size > 0)) {
663 m4ri_die(
"m4ri_mm_malloc: malloc returned NULL\n");
682#if __M4RI_USE_MM_MALLOC
683 newthing = _mm_malloc(size, 64);
684#elif __M4RI_USE_POSIX_MEMALIGN
685 int error = posix_memalign(&newthing, 64, size);
686 if (error) newthing = NULL;
688 newthing = malloc(size);
690 if (newthing == NULL && (size > 0)) {
691 m4ri_die(
"m4ri_mm_malloc: malloc returned NULL\n");
708#if __M4RI_USE_MM_MALLOC
722#define RESTRICT __restrict__
731#define __M4RI_TEMPLATE_EXPAND0(x, y) x##_##y
732#define __M4RI_TEMPLATE_EXPAND1(x, y) __M4RI_TEMPLATE_EXPAND0(x, y)
733#define __M4RI_TEMPLATE_NAME(fun) __M4RI_TEMPLATE_EXPAND1(fun, N)
int rci_t
Type of row and column indexes.
Definition misc.h:72
static word m4ri_swap_bits(word v)
swap bits in the word v
Definition misc.h:323
void m4ri_init(void)
Initialize global data structures for the M4RI library.
Definition misc.c:76
int64_t wi_t
Type of word indexes.
Definition misc.h:81
void m4ri_word_to_str(char *destination, word data, int colon)
Write a sting representing the word data to destination.
Definition misc.c:46
static void * m4ri_mm_calloc(size_t count, size_t size)
Calloc wrapper.
Definition misc.h:614
static void * m4ri_mm_malloc(size_t size)
Malloc wrapper.
Definition misc.h:680
uint64_t word
A word is the typical packed data structure to represent packed bits.
Definition misc.h:87
int BIT
Pretty for a boolean int.
Definition misc.h:64
static word const m4ri_ffff
A word with all bits set.
Definition misc.h:153
void m4ri_fini(void)
De-initialize global data structures from the M4RI library.
Definition misc.c:84
void m4ri_die(const char *errormessage,...)
Print error message and abort().
Definition misc.c:36
static int const m4ri_radix
The number of bits in a word.
Definition misc.h:141
#define __M4RI_CONVERT_TO_WORD(i)
Explicit conversion macro.
Definition misc.h:135
word m4ri_random_word()
Return uniformly randomly distributed random word.
Definition misc.c:58
static void * m4ri_mm_malloc_aligned(size_t size, size_t alignment)
Aligned malloc wrapper.
Definition misc.h:650
#define __M4RI_CONVERT_TO_UINT64_T(w)
Explicit conversion macro.
Definition misc.h:125
static BIT m4ri_coin_flip()
Return 1 or 0 uniformly randomly distributed.
Definition misc.h:513
static word m4ri_spread_bits(word const from, rci_t *const Q, int const length, int const base)
spread bits
Definition misc.h:388
static word const m4ri_one
The number one as a word.
Definition misc.h:147
static void m4ri_mm_free(void *condemned,...)
Free wrapper.
Definition misc.h:707
static int m4ri_lesser_LSB(word a, word b)
Definition misc.h:466
static word m4ri_shrink_bits(word const from, rci_t *const Q, int const length, int const base)
pack bits (inverse of m4ri_spread_bits)
Definition misc.h:346