M4RI  1.0.1
misc.h
Go to the documentation of this file.
1 
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_config.h"
37 
38 #if __M4RI_USE_MM_MALLOC
39 #include <mm_malloc.h>
40 #endif
41 
42 #include <stdlib.h>
43 #include <assert.h>
44 #include <string.h>
45 #define __STDC_LIMIT_MACROS
46 #include <stdint.h>
47 
48 /*
49  * These define entirely the word width used in the library.
50  */
51 
58 typedef int BIT;
59 
66 typedef int rci_t;
67 
74 typedef int wi_t;
75 
76 #ifdef M4RI_WRAPWORD
77 // C++ wrapper class around an uint64_t, exclusively interesting for the developer(s) of M4RI.
78 #include "wordwrapper.h"
79 #else
80 
85 typedef uint64_t word;
86 
97 #define __M4RI_CONVERT_TO_INT(w) ((int)(w))
98 
109 #define __M4RI_CONVERT_TO_BIT(w) ((BIT)(w))
110 
123 #define __M4RI_CONVERT_TO_UINT64_T(w) (w)
124 
133 #define __M4RI_CONVERT_TO_WORD(i) ((word)(i))
134 
135 #endif
136 
141 static int const m4ri_radix = 64;
142 
148 
154 
162 #ifndef MAX
163 #define MAX(x,y) (((x) > (y))?(x):(y))
164 #endif
165 
173 #ifndef MIN
174 #define MIN(x,y) (((x) < (y))?(x):(y))
175 #endif
176 
181 #ifndef TRUE
182 #define TRUE 1
183 #endif
184 
189 #ifndef FALSE
190 #define FALSE 0
191 #endif
192 
199 #define __M4RI_TWOPOW(i) ((uint64_t)1 << (i))
200 
208 #define __M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot))
209 
217 #define __M4RI_SET_BIT(w, spot) ((w) |= (m4ri_one << (spot)))
218 
226 #define __M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one)
227 
236 #define __M4RI_WRITE_BIT(w, spot, value) ((w) = (((w) & ~(m4ri_one << (spot))) | (-__M4RI_CONVERT_TO_WORD(value) & (m4ri_one << (spot)))))
237 
245 #define __M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot)))
246 
271 #define __M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix)
272 
296 #define __M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n)))
297 
313 #define __M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset))
314 
321 static 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 
344 static 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 
387 static 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 
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 
443 #define __M4RI_LIKELY(cond) __builtin_expect ((cond) != 0, 1)
444 
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 
466 static 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 
495 void m4ri_die(const char *errormessage, ...);
496 
497 /**** IO *****/
498 
507 void m4ri_word_to_str( char *destination, word data, int colon);
508 
515 static inline BIT m4ri_coin_flip() {
516  if (rand() < RAND_MAX/2) {
517  return 0;
518  } else {
519  return 1;
520  }
521 }
522 
529 word m4ri_random_word();
530 
531 /***** Initialization *****/
532 
540 #if defined(__GNUC__)
541 void __attribute__ ((constructor)) m4ri_init(void);
542 #else
543 void m4ri_init(void);
544 #endif
545 
546 #ifdef __SUNPRO_C
547 #pragma init(m4ri_init)
548 #endif
549 
557 #if defined(__GNUC__)
558 void __attribute__ ((destructor)) m4ri_fini(void);
559 #else
560 void m4ri_fini(void);
561 #endif
562 
563 #ifdef __SUNPRO_C
564 #pragma fini(m4ri_fini)
565 #endif
566 
567 /***** Memory Management *****/
568 
569 #if __M4RI_CPU_L2_CACHE == 0 && !defined(M4RI_DOXYGEN)
570 /*
571  * Fix some standard value for L2 cache size if it couldn't be
572  * determined by configure.
573  */
574 #define __M4RI_CPU_L2_CACHE 524288
575 #endif // __M4RI_CPU_L2_CACHE
576 
577 #if __M4RI_CPU_L1_CACHE == 0 && !defined(M4RI_DOXYGEN)
578 /*
579  * Fix some standard value for L1 cache size if it couldn't be
580  * determined by configure.
581  */
582 #define __M4RI_CPU_L1_CACHE 16384
583 #endif // __M4RI_CPU_L1_CACHE
584 
596 static inline void *m4ri_mm_calloc(size_t count, size_t size) {
597  void *newthing;
598 #if __M4RI_USE_MM_MALLOC
599  newthing = _mm_malloc(count * size, 16);
600 #elif __M4RI_USE_POSIX_MEMALIGN
601  int error = posix_memalign(&newthing, 16, count * size);
602  if (error) newthing = NULL;
603 #else
604  newthing = calloc(count, size);
605 #endif
606 
607  if (newthing == NULL) {
608  m4ri_die("m4ri_mm_calloc: calloc returned NULL\n");
609  return NULL; /* unreachable. */
610  }
611 #if __M4RI_USE_MM_MALLOC || __M4RI_USE_POSIX_MEMALIGN
612  char *b = (char*)newthing;
613  memset(b, 0, count * size);
614 #endif
615  return newthing;
616 }
617 
632 static inline void *m4ri_mm_malloc_aligned(size_t size, size_t alignment) {
633  void *newthing;
634 
635 #if __M4RI_USE_MM_MALLOC
636  newthing = _mm_malloc(size, alignment);
637 #elif __M4RI_USE_POSIX_MEMALIGN
638  int error = posix_memalign(&newthing, alignment, size);
639  if (error)
640  newthing = NULL;
641 #else
642  newthing = malloc(size);
643 #endif
644 
645  if (newthing==NULL && (size>0)) {
646  m4ri_die("m4ri_mm_malloc: malloc returned NULL\n");
647  return NULL; /* unreachable */
648  }
649  else return newthing;
650 }
651 
662 static inline void *m4ri_mm_malloc(size_t size) {
663  void *newthing;
664 #if __M4RI_USE_MM_MALLOC
665  newthing = _mm_malloc(size, 16);
666 #elif __M4RI_USE_POSIX_MEMALIGN
667  int error = posix_memalign(&newthing, 16, size);
668  if (error) newthing = NULL;
669 #else
670  newthing = malloc(size);
671 #endif //__M4RI_USE_MM_MALLOC
672  if (newthing==NULL && (size>0)) {
673  m4ri_die("m4ri_mm_malloc: malloc returned NULL\n");
674  return NULL; /* unreachable */
675  }
676  else return newthing;
677 }
678 
687 /* void m4ri_mm_free(void *condemned, ...); */
688 static inline void m4ri_mm_free(void *condemned, ...) {
689 #if __M4RI_USE_MM_MALLOC
690  _mm_free(condemned);
691 #else
692  free(condemned);
693 #endif
694 }
695 
700 #if defined (__GNUC__)
701 #define RESTRICT __restrict__
702 #else
703 #define RESTRICT
704 #endif
705 
706 
707 
708 #endif // M4RI_MISC_H