M4RI 1.0.1
misc.h
Go to the documentation of this file.
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