M4RI
1.0.1
|
00001 00011 #ifndef M4RI_MISC_H 00012 #define M4RI_MISC_H 00013 00014 /******************************************************************* 00015 * 00016 * M4RI: Linear Algebra over GF(2) 00017 * 00018 * Copyright (C) 2007, 2008 Gregory Bard <bard@fordham.edu> 00019 * Copyright (C) 2008 Martin Albrecht <M.R.Albrecht@rhul.ac.uk> 00020 * Copyright (C) 2011 Carlo Wood <carlo@alinoe.com> 00021 * 00022 * Distributed under the terms of the GNU General Public License (GPL) 00023 * version 2 or higher. 00024 * 00025 * This code is distributed in the hope that it will be useful, 00026 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00027 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00028 * General Public License for more details. 00029 * 00030 * The full text of the GPL is available at: 00031 * 00032 * http://www.gnu.org/licenses/ 00033 * 00034 ********************************************************************/ 00035 00036 #include "m4ri_config.h" 00037 00038 #if __M4RI_USE_MM_MALLOC 00039 #include <mm_malloc.h> 00040 #endif 00041 00042 #include <stdlib.h> 00043 #include <assert.h> 00044 #include <string.h> 00045 #include <stdint.h> 00046 00047 /* 00048 * These define entirely the word width used in the library. 00049 */ 00050 00057 typedef int BIT; 00058 00065 typedef int rci_t; 00066 00073 typedef int wi_t; 00074 00075 #ifdef M4RI_WRAPWORD 00076 // C++ wrapper class around an uint64_t, exclusively interesting for the developer(s) of M4RI. 00077 #include "wordwrapper.h" 00078 #else 00079 00084 typedef uint64_t word; 00085 00096 #define __M4RI_CONVERT_TO_INT(w) ((int)(w)) 00097 00108 #define __M4RI_CONVERT_TO_BIT(w) ((BIT)(w)) 00109 00122 #define __M4RI_CONVERT_TO_UINT64_T(w) (w) 00123 00132 #define __M4RI_CONVERT_TO_WORD(i) ((word)(i)) 00133 00134 #endif 00135 00140 static int const m4ri_radix = 64; 00141 00146 static word const m4ri_one = __M4RI_CONVERT_TO_WORD(1); 00147 00152 static word const m4ri_ffff = __M4RI_CONVERT_TO_WORD(-1); 00153 00161 #ifndef MAX 00162 #define MAX(x,y) (((x) > (y))?(x):(y)) 00163 #endif 00164 00172 #ifndef MIN 00173 #define MIN(x,y) (((x) < (y))?(x):(y)) 00174 #endif 00175 00180 #ifndef TRUE 00181 #define TRUE 1 00182 #endif 00183 00188 #ifndef FALSE 00189 #define FALSE 0 00190 #endif 00191 00198 #define __M4RI_TWOPOW(i) ((uint64_t)1 << (i)) 00199 00207 #define __M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot)) 00208 00216 #define __M4RI_SET_BIT(w, spot) ((w) |= (m4ri_one << (spot))) 00217 00225 #define __M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one) 00226 00235 #define __M4RI_WRITE_BIT(w, spot, value) ((w) = (((w) & ~(m4ri_one << (spot))) | (-__M4RI_CONVERT_TO_WORD(value) & (m4ri_one << (spot))))) 00236 00244 #define __M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot))) 00245 00270 #define __M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix) 00271 00295 #define __M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n))) 00296 00312 #define __M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset)) 00313 00320 static inline word m4ri_swap_bits(word v) { 00321 v = ((v >> 1) & 0x5555555555555555ULL) | ((v & 0x5555555555555555ULL) << 1); 00322 v = ((v >> 2) & 0x3333333333333333ULL) | ((v & 0x3333333333333333ULL) << 2); 00323 v = ((v >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((v & 0x0F0F0F0F0F0F0F0FULL) << 4); 00324 v = ((v >> 8) & 0x00FF00FF00FF00FFULL) | ((v & 0x00FF00FF00FF00FFULL) << 8); 00325 v = ((v >> 16) & 0x0000FFFF0000FFFFULL) | ((v & 0x0000FFFF0000FFFFULL) << 16); 00326 v = (v >> 32) | (v << 32); 00327 return v; 00328 } 00329 00343 static inline word m4ri_shrink_bits(word const from, rci_t* const Q, int const length, int const base) { 00344 word to = 0; 00345 switch(length-1) { 00346 case 15: to |= (from & (m4ri_one << (Q[15] - base))) >> (Q[15] - 15 - base); 00347 case 14: to |= (from & (m4ri_one << (Q[14] - base))) >> (Q[14] - 14 - base); 00348 case 13: to |= (from & (m4ri_one << (Q[13] - base))) >> (Q[13] - 13 - base); 00349 case 12: to |= (from & (m4ri_one << (Q[12] - base))) >> (Q[12] - 12 - base); 00350 case 11: to |= (from & (m4ri_one << (Q[11] - base))) >> (Q[11] - 11 - base); 00351 case 10: to |= (from & (m4ri_one << (Q[10] - base))) >> (Q[10] - 10 - base); 00352 case 9: to |= (from & (m4ri_one << (Q[ 9] - base))) >> (Q[ 9] - 9 - base); 00353 case 8: to |= (from & (m4ri_one << (Q[ 8] - base))) >> (Q[ 8] - 8 - base); 00354 case 7: to |= (from & (m4ri_one << (Q[ 7] - base))) >> (Q[ 7] - 7 - base); 00355 case 6: to |= (from & (m4ri_one << (Q[ 6] - base))) >> (Q[ 6] - 6 - base); 00356 case 5: to |= (from & (m4ri_one << (Q[ 5] - base))) >> (Q[ 5] - 5 - base); 00357 case 4: to |= (from & (m4ri_one << (Q[ 4] - base))) >> (Q[ 4] - 4 - base); 00358 case 3: to |= (from & (m4ri_one << (Q[ 3] - base))) >> (Q[ 3] - 3 - base); 00359 case 2: to |= (from & (m4ri_one << (Q[ 2] - base))) >> (Q[ 2] - 2 - base); 00360 case 1: to |= (from & (m4ri_one << (Q[ 1] - base))) >> (Q[ 1] - 1 - base); 00361 case 0: to |= (from & (m4ri_one << (Q[ 0] - base))) >> (Q[ 0] - 0 - base); 00362 break; 00363 default: 00364 exit(-1); 00365 } 00366 return to; 00367 } 00368 00386 static inline word m4ri_spread_bits(word const from, rci_t* const Q, int const length, int const base) { 00387 word to = 0; 00388 switch(length-1) { 00389 case 15: to |= (from & (m4ri_one << (15))) << (Q[15]-15-base); 00390 case 14: to |= (from & (m4ri_one << (14))) << (Q[14]-14-base); 00391 case 13: to |= (from & (m4ri_one << (13))) << (Q[13]-13-base); 00392 case 12: to |= (from & (m4ri_one << (12))) << (Q[12]-12-base); 00393 case 11: to |= (from & (m4ri_one << (11))) << (Q[11]-11-base); 00394 case 10: to |= (from & (m4ri_one << (10))) << (Q[10]-10-base); 00395 case 9: to |= (from & (m4ri_one << ( 9))) << (Q[ 9]- 9-base); 00396 case 8: to |= (from & (m4ri_one << ( 8))) << (Q[ 8]- 8-base); 00397 case 7: to |= (from & (m4ri_one << ( 7))) << (Q[ 7]- 7-base); 00398 case 6: to |= (from & (m4ri_one << ( 6))) << (Q[ 6]- 6-base); 00399 case 5: to |= (from & (m4ri_one << ( 5))) << (Q[ 5]- 5-base); 00400 case 4: to |= (from & (m4ri_one << ( 4))) << (Q[ 4]- 4-base); 00401 case 3: to |= (from & (m4ri_one << ( 3))) << (Q[ 3]- 3-base); 00402 case 2: to |= (from & (m4ri_one << ( 2))) << (Q[ 2]- 2-base); 00403 case 1: to |= (from & (m4ri_one << ( 1))) << (Q[ 1]- 1-base); 00404 case 0: to |= (from & (m4ri_one << ( 0))) << (Q[ 0]- 0-base); 00405 break; 00406 default: 00407 exit(-1); 00408 } 00409 return to; 00410 } 00411 00420 #define __M4RI_ALIGNMENT(addr, n) (((unsigned long)(addr))%(n)) 00421 00429 #if defined(__GNUC__) && defined(__GNUC_MINOR__) 00430 #define __M4RI_GNUC_PREREQ(maj, min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min)) 00431 #else 00432 #define __M4RI_GNUC_PREREQ(maj, min) FALSE 00433 #endif 00434 00435 /* __builtin_expect is in gcc 3.0, and not in 2.95. */ 00436 #if __M4RI_GNUC_PREREQ(3,0) || defined(M4RI_DOXYGEN) 00437 00442 #define __M4RI_LIKELY(cond) __builtin_expect ((cond) != 0, 1) 00443 00448 #define __M4RI_UNLIKELY(cond) __builtin_expect ((cond) != 0, 0) 00449 00450 #else 00451 #define __M4RI_LIKELY(cond) (cond) 00452 #define __M4RI_UNLIKELY(cond) (cond) 00453 #endif 00454 00465 static inline int m4ri_lesser_LSB(word a, word b) 00466 { 00467 uint64_t const ia = __M4RI_CONVERT_TO_UINT64_T(a); 00468 uint64_t const ib = __M4RI_CONVERT_TO_UINT64_T(b); 00469 /* 00470 * If a is zero then we should always return false, otherwise 00471 * if b is zero we should return true iff a has at least one bit set. 00472 */ 00473 return !(ib ? ((ia - 1) ^ ia) & ib : !ia); 00474 } 00475 00476 00477 /**** Error Handling *****/ 00478 00494 void m4ri_die(const char *errormessage, ...); 00495 00496 /**** IO *****/ 00497 00506 void m4ri_word_to_str( char *destination, word data, int colon); 00507 00514 static inline BIT m4ri_coin_flip() { 00515 if (rand() < RAND_MAX/2) { 00516 return 0; 00517 } else { 00518 return 1; 00519 } 00520 } 00521 00528 word m4ri_random_word(); 00529 00530 /***** Initialization *****/ 00531 00539 #if defined(__GNUC__) 00540 void __attribute__ ((constructor)) m4ri_init(void); 00541 #else 00542 void m4ri_init(void); 00543 #endif 00544 00545 #ifdef __SUNPRO_C 00546 #pragma init(m4ri_init) 00547 #endif 00548 00556 #if defined(__GNUC__) 00557 void __attribute__ ((destructor)) m4ri_fini(void); 00558 #else 00559 void m4ri_fini(void); 00560 #endif 00561 00562 #ifdef __SUNPRO_C 00563 #pragma fini(m4ri_fini) 00564 #endif 00565 00566 /***** Memory Management *****/ 00567 00568 #if __M4RI_CPU_L2_CACHE == 0 && !defined(M4RI_DOXYGEN) 00569 /* 00570 * Fix some standard value for L2 cache size if it couldn't be 00571 * determined by configure. 00572 */ 00573 #define __M4RI_CPU_L2_CACHE 524288 00574 #endif // __M4RI_CPU_L2_CACHE 00575 00576 #if __M4RI_CPU_L1_CACHE == 0 && !defined(M4RI_DOXYGEN) 00577 /* 00578 * Fix some standard value for L1 cache size if it couldn't be 00579 * determined by configure. 00580 */ 00581 #define __M4RI_CPU_L1_CACHE 16384 00582 #endif // __M4RI_CPU_L1_CACHE 00583 00595 static inline void *m4ri_mm_calloc(size_t count, size_t size) { 00596 void *newthing; 00597 #if __M4RI_HAVE_OPENMP 00598 #pragma omp critical 00599 { 00600 #endif 00601 00602 #if __M4RI_USE_MM_MALLOC 00603 newthing = _mm_malloc(count * size, 16); 00604 #elif __M4RI_USE_POSIX_MEMALIGN 00605 int error = posix_memalign(&newthing, 16, count * size); 00606 if (error) newthing = NULL; 00607 #else 00608 newthing = calloc(count, size); 00609 #endif 00610 00611 #if __M4RI_HAVE_OPENMP 00612 } 00613 #endif 00614 00615 if (newthing==NULL) { 00616 m4ri_die("m4ri_mm_calloc: calloc returned NULL\n"); 00617 return NULL; /* unreachable. */ 00618 } 00619 #if __M4RI_USE_MM_MALLOC || __M4RI_USE_POSIX_MEMALIGN 00620 char *b = (char*)newthing; 00621 memset(b, 0, count * size); 00622 #endif 00623 return newthing; 00624 } 00625 00636 static inline void *m4ri_mm_malloc(size_t size) { 00637 void *newthing; 00638 #if __M4RI_HAVE_OPENMP 00639 #pragma omp critical 00640 { 00641 #endif 00642 00643 #if __M4RI_USE_MM_MALLOC 00644 newthing = _mm_malloc(size, 16); 00645 #elif __M4RI_USE_POSIX_MEMALIGN 00646 int error = posix_memalign(&newthing, 16, size); 00647 if (error) newthing = NULL; 00648 #else 00649 newthing = malloc( size ); 00650 #endif 00651 #if __M4RI_HAVE_OPENMP 00652 } 00653 #endif 00654 if (newthing==NULL && (size>0)) { 00655 m4ri_die("m4ri_mm_malloc: malloc returned NULL\n"); 00656 return NULL; /* unreachable */ 00657 } 00658 else return newthing; 00659 } 00660 00669 /* void m4ri_mm_free(void *condemned, ...); */ 00670 static inline void m4ri_mm_free(void *condemned, ...) { 00671 #if __M4RI_USE_MM_MALLOC 00672 _mm_free(condemned); 00673 #else 00674 free(condemned); 00675 #endif 00676 } 00677 00682 #if defined (__GNUC__) 00683 #define RESTRICT __restrict__ 00684 #else 00685 #define RESTRICT 00686 #endif 00687 00688 00689 00690 #endif // M4RI_MISC_H