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