M4RI 20200125
misc.h
Go to the documentation of this file.
1
10
11#ifndef M4RI_MISC_H
12#define M4RI_MISC_H
13
14/*******************************************************************
15*
16* M4RI: Linear Algebra over GF(2)
17*
18* Copyright (C) 2007, 2008 Gregory Bard <bard@fordham.edu>
19* Copyright (C) 2008 Martin Albrecht <M.R.Albrecht@rhul.ac.uk>
20* Copyright (C) 2011 Carlo Wood <carlo@alinoe.com>
21*
22* Distributed under the terms of the GNU General Public License (GPL)
23* version 2 or higher.
24*
25* This code is distributed in the hope that it will be useful,
26* but WITHOUT ANY WARRANTY; without even the implied warranty of
27* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
28* General Public License for more details.
29*
30* The full text of the GPL is available at:
31*
32* http://www.gnu.org/licenses/
33*
34********************************************************************/
35
36#include <m4ri/m4ri_config.h>
37
38#ifdef HAVE_CONFIG_H
39#include "config.h"
40#endif
41
42#if __M4RI_USE_MM_MALLOC
43#include <mm_malloc.h>
44#endif
45
46#include <stdlib.h>
47#include <assert.h>
48#include <string.h>
50#define __STDC_LIMIT_MACROS
52#include <stdint.h>
53
54/*
55 * These define entirely the word width used in the library.
56 */
57
63
64typedef int BIT;
65
71
72typedef int rci_t;
73
79
80typedef int wi_t;
81
82
86
87typedef uint64_t word;
88
98
99#define __M4RI_CONVERT_TO_INT(w) ((int)(w))
100
110
111#define __M4RI_CONVERT_TO_BIT(w) ((BIT)(w))
112
124
125#define __M4RI_CONVERT_TO_UINT64_T(w) (w)
126
134
135#define __M4RI_CONVERT_TO_WORD(i) ((word)(i))
136
140
141static int const m4ri_radix = 64;
142
146
148
152
154
161
162#ifndef MAX
163#define MAX(x,y) (((x) > (y))?(x):(y))
164#endif
165
172
173#ifndef MIN
174#define MIN(x,y) (((x) < (y))?(x):(y))
175#endif
176
180
181#ifndef TRUE
182#define TRUE 1
183#endif
184
188
189#ifndef FALSE
190#define FALSE 0
191#endif
192
198
199#define __M4RI_TWOPOW(i) ((uint64_t)1 << (i))
200
207
208#define __M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot))
209
216
217#define __M4RI_SET_BIT(w, spot) ((w) |= (m4ri_one << (spot)))
218
225
226#define __M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one)
227
235
236#define __M4RI_WRITE_BIT(w, spot, value) ((w) = (((w) & ~(m4ri_one << (spot))) | (__M4RI_CONVERT_TO_WORD(value) << (spot))))
237
244
245#define __M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot)))
246
270
271#define __M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix)
272
295
296#define __M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n)))
297
312
313#define __M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset))
314
320
321static inline word m4ri_swap_bits(word v) {
322 v = ((v >> 1) & 0x5555555555555555ULL) | ((v & 0x5555555555555555ULL) << 1);
323 v = ((v >> 2) & 0x3333333333333333ULL) | ((v & 0x3333333333333333ULL) << 2);
324 v = ((v >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((v & 0x0F0F0F0F0F0F0F0FULL) << 4);
325 v = ((v >> 8) & 0x00FF00FF00FF00FFULL) | ((v & 0x00FF00FF00FF00FFULL) << 8);
326 v = ((v >> 16) & 0x0000FFFF0000FFFFULL) | ((v & 0x0000FFFF0000FFFFULL) << 16);
327 v = (v >> 32) | (v << 32);
328 return v;
329}
330
343
344static inline word m4ri_shrink_bits(word const from, rci_t* const Q, int const length, int const base) {
345 word to = 0;
346 switch(length-1) {
347 case 15: to |= (from & (m4ri_one << (Q[15] - base))) >> (Q[15] - 15 - base);
348 case 14: to |= (from & (m4ri_one << (Q[14] - base))) >> (Q[14] - 14 - base);
349 case 13: to |= (from & (m4ri_one << (Q[13] - base))) >> (Q[13] - 13 - base);
350 case 12: to |= (from & (m4ri_one << (Q[12] - base))) >> (Q[12] - 12 - base);
351 case 11: to |= (from & (m4ri_one << (Q[11] - base))) >> (Q[11] - 11 - base);
352 case 10: to |= (from & (m4ri_one << (Q[10] - base))) >> (Q[10] - 10 - base);
353 case 9: to |= (from & (m4ri_one << (Q[ 9] - base))) >> (Q[ 9] - 9 - base);
354 case 8: to |= (from & (m4ri_one << (Q[ 8] - base))) >> (Q[ 8] - 8 - base);
355 case 7: to |= (from & (m4ri_one << (Q[ 7] - base))) >> (Q[ 7] - 7 - base);
356 case 6: to |= (from & (m4ri_one << (Q[ 6] - base))) >> (Q[ 6] - 6 - base);
357 case 5: to |= (from & (m4ri_one << (Q[ 5] - base))) >> (Q[ 5] - 5 - base);
358 case 4: to |= (from & (m4ri_one << (Q[ 4] - base))) >> (Q[ 4] - 4 - base);
359 case 3: to |= (from & (m4ri_one << (Q[ 3] - base))) >> (Q[ 3] - 3 - base);
360 case 2: to |= (from & (m4ri_one << (Q[ 2] - base))) >> (Q[ 2] - 2 - base);
361 case 1: to |= (from & (m4ri_one << (Q[ 1] - base))) >> (Q[ 1] - 1 - base);
362 case 0: to |= (from & (m4ri_one << (Q[ 0] - base))) >> (Q[ 0] - 0 - base);
363 break;
364 default:
365 abort();
366 }
367 return to;
368}
369
386
387static inline word m4ri_spread_bits(word const from, rci_t* const Q, int const length, int const base) {
388 word to = 0;
389 switch(length-1) {
390 case 15: to |= (from & (m4ri_one << (15))) << (Q[15]-15-base);
391 case 14: to |= (from & (m4ri_one << (14))) << (Q[14]-14-base);
392 case 13: to |= (from & (m4ri_one << (13))) << (Q[13]-13-base);
393 case 12: to |= (from & (m4ri_one << (12))) << (Q[12]-12-base);
394 case 11: to |= (from & (m4ri_one << (11))) << (Q[11]-11-base);
395 case 10: to |= (from & (m4ri_one << (10))) << (Q[10]-10-base);
396 case 9: to |= (from & (m4ri_one << ( 9))) << (Q[ 9]- 9-base);
397 case 8: to |= (from & (m4ri_one << ( 8))) << (Q[ 8]- 8-base);
398 case 7: to |= (from & (m4ri_one << ( 7))) << (Q[ 7]- 7-base);
399 case 6: to |= (from & (m4ri_one << ( 6))) << (Q[ 6]- 6-base);
400 case 5: to |= (from & (m4ri_one << ( 5))) << (Q[ 5]- 5-base);
401 case 4: to |= (from & (m4ri_one << ( 4))) << (Q[ 4]- 4-base);
402 case 3: to |= (from & (m4ri_one << ( 3))) << (Q[ 3]- 3-base);
403 case 2: to |= (from & (m4ri_one << ( 2))) << (Q[ 2]- 2-base);
404 case 1: to |= (from & (m4ri_one << ( 1))) << (Q[ 1]- 1-base);
405 case 0: to |= (from & (m4ri_one << ( 0))) << (Q[ 0]- 0-base);
406 break;
407 default:
408 abort();
409 }
410 return to;
411}
412
420
421#define __M4RI_ALIGNMENT(addr, n) (((unsigned long)(addr))%(n))
422
430#if defined(__GNUC__) && defined(__GNUC_MINOR__)
431#define __M4RI_GNUC_PREREQ(maj, min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
432#else
433#define __M4RI_GNUC_PREREQ(maj, min) FALSE
434#endif
435
436/* __builtin_expect is in gcc 3.0, and not in 2.95. */
437#if __M4RI_GNUC_PREREQ(3,0) || defined(M4RI_DOXYGEN)
438
442
443#define __M4RI_LIKELY(cond) __builtin_expect ((cond) != 0, 1)
444
448
449#define __M4RI_UNLIKELY(cond) __builtin_expect ((cond) != 0, 0)
450
451#else
452#define __M4RI_LIKELY(cond) (cond)
453#define __M4RI_UNLIKELY(cond) (cond)
454#endif
455
465
466static inline int m4ri_lesser_LSB(word a, word b)
467{
468 uint64_t const ia = __M4RI_CONVERT_TO_UINT64_T(a);
469 uint64_t const ib = __M4RI_CONVERT_TO_UINT64_T(b);
470 /*
471 * If a is zero then we should always return false, otherwise
472 * if b is zero we should return true iff a has at least one bit set.
473 */
474 return !(ib ? ((ia - 1) ^ ia) & ib : !ia);
475}
476
477
478/**** Error Handling *****/
479
494
495void m4ri_die(const char *errormessage, ...);
496
497/**** IO *****/
498
507void m4ri_word_to_str( char *destination, word data, int colon);
508
514
515static inline BIT m4ri_coin_flip() {
516 if (rand() < RAND_MAX/2) {
517 return 0;
518 } else {
519 return 1;
520 }
521}
522
528
530
531/***** Initialization *****/
532
539
540#if defined(__GNUC__)
541void __attribute__ ((constructor)) m4ri_init(void);
542#else
543void m4ri_init(void);
544#endif
545
546#ifdef __SUNPRO_C
547#pragma init(m4ri_init)
548#endif
549
556
557#if defined(__GNUC__)
558void __attribute__ ((destructor)) m4ri_fini(void);
559#else
560void m4ri_fini(void);
561#endif
562
563#ifdef __SUNPRO_C
564#pragma fini(m4ri_fini)
565#endif
566
567/***** Memory Management *****/
568
570
571#if __M4RI_CPU_L3_CACHE == 0
572/*
573 * Fix some standard value for L3 cache size if it couldn't be
574 * determined by configure.
575 */
576
577#undef __M4RI_CPU_L3_CACHE
578#if __M4RI_CPU_L2_CACHE
579#define __M4RI_CPU_L3_CACHE __M4RI_CPU_L2_CACHE
580#else
581#define __M4RI_CPU_L3_CACHE 4194304
582#endif // __M4RI_CPU_L2_CACHE
583#endif // __M4RI_CPU_L3_CACHE
584
585#if __M4RI_CPU_L2_CACHE == 0
586/*
587 * Fix some standard value for L2 cache size if it couldn't be
588 * determined by configure.
589 */
590#undef __M4RI_CPU_L2_CACHE
591#define __M4RI_CPU_L2_CACHE 262144
592#endif // __M4RI_CPU_L2_CACHE
593
594
595#if __M4RI_CPU_L1_CACHE == 0
596/*
597 * Fix some standard value for L1 cache size if it couldn't be
598 * determined by configure.
599 */
600#undef __M4RI_CPU_L1_CACHE
601#define __M4RI_CPU_L1_CACHE 16384
602#endif // __M4RI_CPU_L1_CACHE
603
605
616
617static inline void *m4ri_mm_calloc(size_t count, size_t size) {
618 void *newthing;
619#if __M4RI_USE_MM_MALLOC
620 newthing = _mm_malloc(count * size, 64);
621#elif __M4RI_USE_POSIX_MEMALIGN
622 int error = posix_memalign(&newthing, 64, count * size);
623 if (error) newthing = NULL;
624#else
625 newthing = calloc(count, size);
626#endif
627
628 if (newthing == NULL) {
629 m4ri_die("m4ri_mm_calloc: calloc returned NULL\n");
630 return NULL; /* unreachable. */
631 }
632#if __M4RI_USE_MM_MALLOC || __M4RI_USE_POSIX_MEMALIGN
633 char *b = (char*)newthing;
634 memset(b, 0, count * size);
635#endif
636 return newthing;
637}
638
652
653static inline void *m4ri_mm_malloc_aligned(size_t size, size_t alignment) {
654 void *newthing;
655
656#if __M4RI_USE_MM_MALLOC
657 newthing = _mm_malloc(size, alignment);
658#elif __M4RI_USE_POSIX_MEMALIGN
659 int error = posix_memalign(&newthing, alignment, size);
660 if (error)
661 newthing = NULL;
662#else
663 newthing = malloc(size);
664#endif
665
666 if (newthing==NULL && (size>0)) {
667 m4ri_die("m4ri_mm_malloc: malloc returned NULL\n");
668 return NULL; /* unreachable */
669 }
670 else { return newthing; }
671}
672
682
683static inline void *m4ri_mm_malloc(size_t size) {
684 void *newthing;
685#if __M4RI_USE_MM_MALLOC
686 newthing = _mm_malloc(size, 64);
687#elif __M4RI_USE_POSIX_MEMALIGN
688 int error = posix_memalign(&newthing, 64, size);
689 if (error) newthing = NULL;
690#else
691 newthing = malloc(size);
692#endif //__M4RI_USE_MM_MALLOC
693 if (newthing==NULL && (size>0)) {
694 m4ri_die("m4ri_mm_malloc: malloc returned NULL\n");
695 return NULL; /* unreachable */
696 }
697 else { return newthing; }
698}
699
700
708
709/* void m4ri_mm_free(void *condemned, ...); */
710static inline void m4ri_mm_free(void *condemned, ...) {
711#if __M4RI_USE_MM_MALLOC
712 _mm_free(condemned);
713#else
714 free(condemned);
715#endif
716}
717
719
720/*
721 * MSVC does not understand the restrict keyword
722 */
723
724#if defined (__GNUC__)
725#define RESTRICT __restrict__
726#else
727#define RESTRICT
728#endif
729
730
731
732/*
733 * Macros for template expansion.
734 */
735
736#define __M4RI_TEMPLATE_EXPAND0(x,y) x ## _ ## y
737#define __M4RI_TEMPLATE_EXPAND1(x,y) __M4RI_TEMPLATE_EXPAND0(x,y)
738#define __M4RI_TEMPLATE_NAME(fun) __M4RI_TEMPLATE_EXPAND1(fun, N)
739
741
742#endif // M4RI_MISC_H
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:321
void m4ri_init(void)
Initialize global data structures for the M4RI library.
Definition misc.c:78
void m4ri_word_to_str(char *destination, word data, int colon)
Write a sting representing the word data to destination.
Definition misc.c:45
static void * m4ri_mm_calloc(size_t count, size_t size)
Calloc wrapper.
Definition misc.h:617
static void * m4ri_mm_malloc(size_t size)
Malloc wrapper.
Definition misc.h:683
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:86
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
int wi_t
Type of word indexes.
Definition misc.h:80
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:653
#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:515
static word m4ri_spread_bits(word const from, rci_t *const Q, int const length, int const base)
spread bits
Definition misc.h:387
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:710
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:344