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 #define __STDC_LIMIT_MACROS 00046 #include <stdint.h> 00047 00048 /* 00049 * These define entirely the word width used in the library. 00050 */ 00051 00058 typedef int BIT; 00059 00066 typedef int rci_t; 00067 00074 typedef int wi_t; 00075 00076 #ifdef M4RI_WRAPWORD 00077 // C++ wrapper class around an uint64_t, exclusively interesting for the developer(s) of M4RI. 00078 #include "wordwrapper.h" 00079 #else 00080 00085 typedef uint64_t word; 00086 00097 #define __M4RI_CONVERT_TO_INT(w) ((int)(w)) 00098 00109 #define __M4RI_CONVERT_TO_BIT(w) ((BIT)(w)) 00110 00123 #define __M4RI_CONVERT_TO_UINT64_T(w) (w) 00124 00133 #define __M4RI_CONVERT_TO_WORD(i) ((word)(i)) 00134 00135 #endif 00136 00141 static int const m4ri_radix = 64; 00142 00147 static word const m4ri_one = __M4RI_CONVERT_TO_WORD(1); 00148 00153 static word const m4ri_ffff = __M4RI_CONVERT_TO_WORD(-1); 00154 00162 #ifndef MAX 00163 #define MAX(x,y) (((x) > (y))?(x):(y)) 00164 #endif 00165 00173 #ifndef MIN 00174 #define MIN(x,y) (((x) < (y))?(x):(y)) 00175 #endif 00176 00181 #ifndef TRUE 00182 #define TRUE 1 00183 #endif 00184 00189 #ifndef FALSE 00190 #define FALSE 0 00191 #endif 00192 00199 #define __M4RI_TWOPOW(i) ((uint64_t)1 << (i)) 00200 00208 #define __M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot)) 00209 00217 #define __M4RI_SET_BIT(w, spot) ((w) |= (m4ri_one << (spot))) 00218 00226 #define __M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one) 00227 00236 #define __M4RI_WRITE_BIT(w, spot, value) ((w) = (((w) & ~(m4ri_one << (spot))) | (-__M4RI_CONVERT_TO_WORD(value) & (m4ri_one << (spot))))) 00237 00245 #define __M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot))) 00246 00271 #define __M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix) 00272 00296 #define __M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n))) 00297 00313 #define __M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset)) 00314 00321 static inline word m4ri_swap_bits(word v) { 00322 v = ((v >> 1) & 0x5555555555555555ULL) | ((v & 0x5555555555555555ULL) << 1); 00323 v = ((v >> 2) & 0x3333333333333333ULL) | ((v & 0x3333333333333333ULL) << 2); 00324 v = ((v >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((v & 0x0F0F0F0F0F0F0F0FULL) << 4); 00325 v = ((v >> 8) & 0x00FF00FF00FF00FFULL) | ((v & 0x00FF00FF00FF00FFULL) << 8); 00326 v = ((v >> 16) & 0x0000FFFF0000FFFFULL) | ((v & 0x0000FFFF0000FFFFULL) << 16); 00327 v = (v >> 32) | (v << 32); 00328 return v; 00329 } 00330 00344 static inline word m4ri_shrink_bits(word const from, rci_t* const Q, int const length, int const base) { 00345 word to = 0; 00346 switch(length-1) { 00347 case 15: to |= (from & (m4ri_one << (Q[15] - base))) >> (Q[15] - 15 - base); 00348 case 14: to |= (from & (m4ri_one << (Q[14] - base))) >> (Q[14] - 14 - base); 00349 case 13: to |= (from & (m4ri_one << (Q[13] - base))) >> (Q[13] - 13 - base); 00350 case 12: to |= (from & (m4ri_one << (Q[12] - base))) >> (Q[12] - 12 - base); 00351 case 11: to |= (from & (m4ri_one << (Q[11] - base))) >> (Q[11] - 11 - base); 00352 case 10: to |= (from & (m4ri_one << (Q[10] - base))) >> (Q[10] - 10 - base); 00353 case 9: to |= (from & (m4ri_one << (Q[ 9] - base))) >> (Q[ 9] - 9 - base); 00354 case 8: to |= (from & (m4ri_one << (Q[ 8] - base))) >> (Q[ 8] - 8 - base); 00355 case 7: to |= (from & (m4ri_one << (Q[ 7] - base))) >> (Q[ 7] - 7 - base); 00356 case 6: to |= (from & (m4ri_one << (Q[ 6] - base))) >> (Q[ 6] - 6 - base); 00357 case 5: to |= (from & (m4ri_one << (Q[ 5] - base))) >> (Q[ 5] - 5 - base); 00358 case 4: to |= (from & (m4ri_one << (Q[ 4] - base))) >> (Q[ 4] - 4 - base); 00359 case 3: to |= (from & (m4ri_one << (Q[ 3] - base))) >> (Q[ 3] - 3 - base); 00360 case 2: to |= (from & (m4ri_one << (Q[ 2] - base))) >> (Q[ 2] - 2 - base); 00361 case 1: to |= (from & (m4ri_one << (Q[ 1] - base))) >> (Q[ 1] - 1 - base); 00362 case 0: to |= (from & (m4ri_one << (Q[ 0] - base))) >> (Q[ 0] - 0 - base); 00363 break; 00364 default: 00365 abort(); 00366 } 00367 return to; 00368 } 00369 00387 static inline word m4ri_spread_bits(word const from, rci_t* const Q, int const length, int const base) { 00388 word to = 0; 00389 switch(length-1) { 00390 case 15: to |= (from & (m4ri_one << (15))) << (Q[15]-15-base); 00391 case 14: to |= (from & (m4ri_one << (14))) << (Q[14]-14-base); 00392 case 13: to |= (from & (m4ri_one << (13))) << (Q[13]-13-base); 00393 case 12: to |= (from & (m4ri_one << (12))) << (Q[12]-12-base); 00394 case 11: to |= (from & (m4ri_one << (11))) << (Q[11]-11-base); 00395 case 10: to |= (from & (m4ri_one << (10))) << (Q[10]-10-base); 00396 case 9: to |= (from & (m4ri_one << ( 9))) << (Q[ 9]- 9-base); 00397 case 8: to |= (from & (m4ri_one << ( 8))) << (Q[ 8]- 8-base); 00398 case 7: to |= (from & (m4ri_one << ( 7))) << (Q[ 7]- 7-base); 00399 case 6: to |= (from & (m4ri_one << ( 6))) << (Q[ 6]- 6-base); 00400 case 5: to |= (from & (m4ri_one << ( 5))) << (Q[ 5]- 5-base); 00401 case 4: to |= (from & (m4ri_one << ( 4))) << (Q[ 4]- 4-base); 00402 case 3: to |= (from & (m4ri_one << ( 3))) << (Q[ 3]- 3-base); 00403 case 2: to |= (from & (m4ri_one << ( 2))) << (Q[ 2]- 2-base); 00404 case 1: to |= (from & (m4ri_one << ( 1))) << (Q[ 1]- 1-base); 00405 case 0: to |= (from & (m4ri_one << ( 0))) << (Q[ 0]- 0-base); 00406 break; 00407 default: 00408 abort(); 00409 } 00410 return to; 00411 } 00412 00421 #define __M4RI_ALIGNMENT(addr, n) (((unsigned long)(addr))%(n)) 00422 00430 #if defined(__GNUC__) && defined(__GNUC_MINOR__) 00431 #define __M4RI_GNUC_PREREQ(maj, min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min)) 00432 #else 00433 #define __M4RI_GNUC_PREREQ(maj, min) FALSE 00434 #endif 00435 00436 /* __builtin_expect is in gcc 3.0, and not in 2.95. */ 00437 #if __M4RI_GNUC_PREREQ(3,0) || defined(M4RI_DOXYGEN) 00438 00443 #define __M4RI_LIKELY(cond) __builtin_expect ((cond) != 0, 1) 00444 00449 #define __M4RI_UNLIKELY(cond) __builtin_expect ((cond) != 0, 0) 00450 00451 #else 00452 #define __M4RI_LIKELY(cond) (cond) 00453 #define __M4RI_UNLIKELY(cond) (cond) 00454 #endif 00455 00466 static inline int m4ri_lesser_LSB(word a, word b) 00467 { 00468 uint64_t const ia = __M4RI_CONVERT_TO_UINT64_T(a); 00469 uint64_t const ib = __M4RI_CONVERT_TO_UINT64_T(b); 00470 /* 00471 * If a is zero then we should always return false, otherwise 00472 * if b is zero we should return true iff a has at least one bit set. 00473 */ 00474 return !(ib ? ((ia - 1) ^ ia) & ib : !ia); 00475 } 00476 00477 00478 /**** Error Handling *****/ 00479 00495 void m4ri_die(const char *errormessage, ...); 00496 00497 /**** IO *****/ 00498 00507 void m4ri_word_to_str( char *destination, word data, int colon); 00508 00515 static inline BIT m4ri_coin_flip() { 00516 if (rand() < RAND_MAX/2) { 00517 return 0; 00518 } else { 00519 return 1; 00520 } 00521 } 00522 00529 word m4ri_random_word(); 00530 00531 /***** Initialization *****/ 00532 00540 #if defined(__GNUC__) 00541 void __attribute__ ((constructor)) m4ri_init(void); 00542 #else 00543 void m4ri_init(void); 00544 #endif 00545 00546 #ifdef __SUNPRO_C 00547 #pragma init(m4ri_init) 00548 #endif 00549 00557 #if defined(__GNUC__) 00558 void __attribute__ ((destructor)) m4ri_fini(void); 00559 #else 00560 void m4ri_fini(void); 00561 #endif 00562 00563 #ifdef __SUNPRO_C 00564 #pragma fini(m4ri_fini) 00565 #endif 00566 00567 /***** Memory Management *****/ 00568 00569 #if __M4RI_CPU_L2_CACHE == 0 && !defined(M4RI_DOXYGEN) 00570 /* 00571 * Fix some standard value for L2 cache size if it couldn't be 00572 * determined by configure. 00573 */ 00574 #define __M4RI_CPU_L2_CACHE 524288 00575 #endif // __M4RI_CPU_L2_CACHE 00576 00577 #if __M4RI_CPU_L1_CACHE == 0 && !defined(M4RI_DOXYGEN) 00578 /* 00579 * Fix some standard value for L1 cache size if it couldn't be 00580 * determined by configure. 00581 */ 00582 #define __M4RI_CPU_L1_CACHE 16384 00583 #endif // __M4RI_CPU_L1_CACHE 00584 00596 static inline void *m4ri_mm_calloc(size_t count, size_t size) { 00597 void *newthing; 00598 #if __M4RI_USE_MM_MALLOC 00599 newthing = _mm_malloc(count * size, 16); 00600 #elif __M4RI_USE_POSIX_MEMALIGN 00601 int error = posix_memalign(&newthing, 16, count * size); 00602 if (error) newthing = NULL; 00603 #else 00604 newthing = calloc(count, size); 00605 #endif 00606 00607 if (newthing == NULL) { 00608 m4ri_die("m4ri_mm_calloc: calloc returned NULL\n"); 00609 return NULL; /* unreachable. */ 00610 } 00611 #if __M4RI_USE_MM_MALLOC || __M4RI_USE_POSIX_MEMALIGN 00612 char *b = (char*)newthing; 00613 memset(b, 0, count * size); 00614 #endif 00615 return newthing; 00616 } 00617 00632 static inline void *m4ri_mm_malloc_aligned(size_t size, size_t alignment) { 00633 void *newthing; 00634 00635 #if __M4RI_USE_MM_MALLOC 00636 newthing = _mm_malloc(size, alignment); 00637 #elif __M4RI_USE_POSIX_MEMALIGN 00638 int error = posix_memalign(&newthing, alignment, size); 00639 if (error) 00640 newthing = NULL; 00641 #else 00642 newthing = malloc(size); 00643 #endif 00644 00645 if (newthing==NULL && (size>0)) { 00646 m4ri_die("m4ri_mm_malloc: malloc returned NULL\n"); 00647 return NULL; /* unreachable */ 00648 } 00649 else return newthing; 00650 } 00651 00662 static inline void *m4ri_mm_malloc(size_t size) { 00663 void *newthing; 00664 #if __M4RI_USE_MM_MALLOC 00665 newthing = _mm_malloc(size, 16); 00666 #elif __M4RI_USE_POSIX_MEMALIGN 00667 int error = posix_memalign(&newthing, 16, size); 00668 if (error) newthing = NULL; 00669 #else 00670 newthing = malloc(size); 00671 #endif //__M4RI_USE_MM_MALLOC 00672 if (newthing==NULL && (size>0)) { 00673 m4ri_die("m4ri_mm_malloc: malloc returned NULL\n"); 00674 return NULL; /* unreachable */ 00675 } 00676 else return newthing; 00677 } 00678 00687 /* void m4ri_mm_free(void *condemned, ...); */ 00688 static inline void m4ri_mm_free(void *condemned, ...) { 00689 #if __M4RI_USE_MM_MALLOC 00690 _mm_free(condemned); 00691 #else 00692 free(condemned); 00693 #endif 00694 } 00695 00700 #if defined (__GNUC__) 00701 #define RESTRICT __restrict__ 00702 #else 00703 #define RESTRICT 00704 #endif 00705 00706 00707 00708 #endif // M4RI_MISC_H