M4RI 1.0.1
|
00001 00010 #ifndef MISC_H 00011 #define MISC_H 00012 /******************************************************************* 00013 * 00014 * M4RI: Linear Algebra over GF(2) 00015 * 00016 * Copyright (C) 2007, 2008 Gregory Bard <bard@fordham.edu> 00017 * Copyright (C) 2008 Martin Albrecht <M.R.Albrecht@rhul.ac.uk> 00018 * 00019 * Distributed under the terms of the GNU General Public License (GPL) 00020 * version 2 or higher. 00021 * 00022 * This code is distributed in the hope that it will be useful, 00023 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00024 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00025 * General Public License for more details. 00026 * 00027 * The full text of the GPL is available at: 00028 * 00029 * http://www.gnu.org/licenses/ 00030 * 00031 ********************************************************************/ 00032 00033 #ifndef HAVE_SSE2 00034 #undef HAVE_MM_MALLOC 00035 #endif 00036 00037 #ifdef HAVE_MM_MALLOC 00038 #include <mm_malloc.h> 00039 #endif 00040 00041 #include <stdlib.h> 00042 #include <assert.h> 00043 #include <string.h> 00044 00045 /* 00046 * These define entirely the word width used in the library. 00047 */ 00048 00054 typedef unsigned long long word; 00055 00060 #define RADIX (sizeof(word)<<3) 00061 00066 #define ONE ((word)1) 00067 00068 00073 #define FFFF ((word)0xffffffffffffffffull) 00074 00082 #ifndef MAX 00083 #define MAX(x,y) (((x) > (y))?(x):(y)) 00084 #endif 00085 00093 #ifndef MIN 00094 #define MIN(x,y) (((x) < (y))?(x):(y)) 00095 #endif 00096 00104 #define DIV_CEIL(x,y) (((x)%(y))?(x)/(y)+1:(x)/(y)) 00105 00110 #define TRUE 1 00111 00116 #define FALSE 0 00117 00124 #define TWOPOW(i) (ONE<<(i)) 00125 00130 typedef unsigned char BIT; 00131 00139 #define CLR_BIT(w, spot) ((w) &= ~(ONE<<(RADIX - (spot) - 1))) 00140 00148 #define SET_BIT(w, spot) ((w) |= (ONE<<(RADIX - (spot) - 1))) 00149 00157 #define GET_BIT(w, spot) (((w) & (ONE<<(RADIX - (spot) - 1))) >> (RADIX - (spot) - 1)) 00158 00167 #define WRITE_BIT(w, spot, value) ((w) = (((w) &~(ONE<<(RADIX - (spot) - 1))) | (((word)(value))<<(RADIX - (spot) - 1)))) 00168 00176 #define FLIP_BIT(w, spot) ((w) ^= (ONE<<(RADIX - (spot) - 1))) 00177 00185 #define LEFTMOST_BITS(w, n) ((w) & ~((ONE<<(RADIX-(n)))-1))>>(RADIX-(n)) 00186 00194 #define RIGHTMOST_BITS(w, n) (((w)<<(RADIX-(n)-1))>>(RADIX-(n)-1)) 00195 00203 #define LEFT_BITMASK(n) (~((ONE << ((RADIX - (n % RADIX))%RADIX) ) - 1)) 00204 00214 #define RIGHT_BITMASK(n) (FFFF>>( (RADIX - (n%RADIX))%RADIX )) 00215 00223 #define BITMASK(n) (ONE<<(RADIX-((n)%RADIX)-1)) 00224 00225 00234 #define ALIGNMENT(addr, n) (((unsigned long)(addr))%(n)) 00235 00242 static inline int leftmost_bit(word a) { 00243 int r = 0; 00244 if(a>>32) 00245 r+=32, a>>=32; 00246 if(a>>16) 00247 r+=16, a>>=16; 00248 if(a>>8) 00249 r+=8, a>>=8; 00250 if(a>>4) 00251 r+=4, a>>=4; 00252 if(a>>2) 00253 r+=2, a>>=2; 00254 if(a>>1) 00255 r+=1, a>>=1; 00256 if(a) 00257 r+=1, a>>=1; 00258 return r; 00259 } 00260 00261 00262 00263 /**** Error Handling *****/ 00264 00280 void m4ri_die(const char *errormessage, ...); 00281 00282 /**** IO *****/ 00283 00292 void m4ri_word_to_str( char *destination, word data, int colon); 00293 00300 //BIT m4ri_coin_flip(void); 00301 static inline BIT m4ri_coin_flip() { 00302 if (rand() < RAND_MAX/2) { 00303 return 0; 00304 } else { 00305 return 1; 00306 } 00307 } 00308 00315 word m4ri_random_word(); 00316 00317 /***** Initialization *****/ 00318 00326 #if defined(__GNUC__) 00327 void __attribute__ ((constructor)) m4ri_init(void); 00328 #else 00329 void m4ri_init(void); 00330 #endif 00331 00332 #ifdef __SUNPRO_C 00333 #pragma init(m4ri_init) 00334 #endif 00335 00343 #if defined(__GNUC__) 00344 void __attribute__ ((destructor)) m4ri_fini(void); 00345 #else 00346 void m4ri_fini(void); 00347 #endif 00348 00349 #ifdef __SUNPRO_C 00350 #pragma fini(m4ri_fini) 00351 #endif 00352 00353 /***** Memory Management *****/ 00354 00355 #if CPU_L2_CACHE == 0 00356 00360 #define CPU_L2_CACHE 524288 00361 #endif //CPU_L2_CACHE 00362 00363 #if CPU_L1_CACHE == 0 00364 00368 #define CPU_L1_CACHE 16384 00369 #endif //CPU_L1_CACHE 00370 00380 /* void *m4ri_mm_calloc( int count, int size ); */ 00381 static inline void *m4ri_mm_calloc( int count, int size ) { 00382 void *newthing; 00383 #ifdef HAVE_OPENMP 00384 #pragma omp critical 00385 { 00386 #endif 00387 00388 #ifdef HAVE_MM_MALLOC 00389 newthing = _mm_malloc(count*size, 16); 00390 #else 00391 newthing = calloc(count, size); 00392 #endif 00393 00394 #ifdef HAVE_OPENMP 00395 } 00396 #endif 00397 00398 if (newthing==NULL) { 00399 m4ri_die("m4ri_mm_calloc: calloc returned NULL\n"); 00400 return NULL; /* unreachable. */ 00401 } 00402 #ifdef HAVE_MM_MALLOC 00403 char *b = (char*)newthing; 00404 memset(b, 0, count*size); 00405 #endif 00406 return newthing; 00407 } 00408 00417 /* void *m4ri_mm_malloc( int size ); */ 00418 static inline void *m4ri_mm_malloc( int size ) { 00419 void *newthing; 00420 #ifdef HAVE_OPENMP 00421 #pragma omp critical 00422 { 00423 #endif 00424 00425 #ifdef HAVE_MM_MALLOC 00426 newthing = _mm_malloc(size, 16); 00427 #else 00428 newthing = malloc( size ); 00429 #endif 00430 #ifdef HAVE_OPENMP 00431 } 00432 #endif 00433 if (newthing==NULL && (size>0)) { 00434 m4ri_die("m4ri_mm_malloc: malloc returned NULL\n"); 00435 return NULL; /* unreachable */ 00436 } 00437 else return newthing; 00438 } 00439 00440 00449 /* void m4ri_mm_free(void *condemned, ...); */ 00450 static inline void m4ri_mm_free(void *condemned, ...) { 00451 #ifdef HAVE_MM_MALLOC 00452 _mm_free(condemned); 00453 #else 00454 free(condemned); 00455 #endif 00456 } 00457 00462 #define MM_MAX_MALLOC ((1ULL)<<30) 00463 00467 #define ENABLE_MMC 00468 00469 00474 #define M4RI_MMC_NBLOCKS 16 00475 00480 #define M4RI_MMC_THRESHOLD CPU_L2_CACHE 00481 00487 typedef struct _mm_block { 00491 size_t size; 00492 00496 void *data; 00497 00498 } mmb_t; 00499 00504 extern mmb_t m4ri_mmc_cache[M4RI_MMC_NBLOCKS]; 00505 00512 static inline mmb_t *m4ri_mmc_handle(void) { 00513 return m4ri_mmc_cache; 00514 } 00515 00522 static inline void *m4ri_mmc_malloc(size_t size) { 00523 00524 #ifdef ENABLE_MMC 00525 void *ret = NULL; 00526 #endif 00527 00528 #ifdef HAVE_OPENMP 00529 #pragma omp critical 00530 { 00531 #endif 00532 00533 #ifdef ENABLE_MMC 00534 mmb_t *mm = m4ri_mmc_handle(); 00535 if (size <= M4RI_MMC_THRESHOLD) { 00536 size_t i; 00537 for (i=0; i<M4RI_MMC_NBLOCKS; i++) { 00538 if(mm[i].size == size) { 00539 ret = mm[i].data; 00540 mm[i].data = NULL; 00541 mm[i].size = 0; 00542 break; 00543 } 00544 } 00545 } 00546 #endif //ENABLE_MMC 00547 00548 #ifdef HAVE_OPENMP 00549 } 00550 #endif 00551 00552 #ifdef ENABLE_MMC 00553 if (ret) 00554 return ret; 00555 else 00556 return m4ri_mm_malloc(size); 00557 #else 00558 return m4ri_mm_malloc(size); 00559 #endif 00560 } 00561 00571 static inline void *m4ri_mmc_calloc(size_t size, size_t count) { 00572 void *ret = m4ri_mmc_malloc(size*count); 00573 memset((char*)ret, 0, count*size); 00574 return ret; 00575 } 00576 00586 static inline void m4ri_mmc_free(void *condemned, size_t size) { 00587 #ifdef HAVE_OPENMP 00588 #pragma omp critical 00589 { 00590 #endif 00591 #ifdef ENABLE_MMC 00592 static size_t j = 0; 00593 mmb_t *mm = m4ri_mmc_handle(); 00594 if (size < M4RI_MMC_THRESHOLD) { 00595 size_t i; 00596 for(i=0; i<M4RI_MMC_NBLOCKS; i++) { 00597 if(mm[i].size == 0) { 00598 mm[i].size = size; 00599 mm[i].data = condemned; 00600 break; 00601 } 00602 } 00603 if (i == M4RI_MMC_NBLOCKS) { 00604 m4ri_mm_free(mm[j].data); 00605 mm[j].size = size; 00606 mm[j].data = condemned; 00607 j = (j+1) % M4RI_MMC_NBLOCKS; 00608 } 00609 } else { 00610 m4ri_mm_free(condemned); 00611 } 00612 #else 00613 m4ri_mm_free(condemned); 00614 #endif //ENABLE_MMC 00615 #ifdef HAVE_OPENMP 00616 } 00617 #endif 00618 } 00619 00629 static inline void m4ri_mmc_cleanup(void) { 00630 #ifdef HAVE_OPENMP 00631 #pragma omp critical 00632 { 00633 #endif 00634 mmb_t *mm = m4ri_mmc_handle(); 00635 size_t i; 00636 for(i=0; i < M4RI_MMC_NBLOCKS; i++) { 00637 if (mm[i].size) 00638 m4ri_mm_free(mm[i].data); 00639 mm[i].size = 0; 00640 } 00641 #ifdef HAVE_OPENMP 00642 } 00643 #endif 00644 } 00645 00646 #endif //MISC_H