misc.h

Go to the documentation of this file.

#ifndef M4RI_MISC_H
#define M4RI_MISC_H

/*******************************************************************
*
*                 M4RI: Linear Algebra over GF(2)
*
*    Copyright (C) 2007, 2008 Gregory Bard <bard@fordham.edu>
*    Copyright (C) 2008 Martin Albrecht <M.R.Albrecht@rhul.ac.uk>
*    Copyright (C) 2011 Carlo Wood <carlo@alinoe.com>
*
*  Distributed under the terms of the GNU General Public License (GPL)
*  version 2 or higher.
*
*    This code is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
*    General Public License for more details.
*
*  The full text of the GPL is available at:
*
*                  http://www.gnu.org/licenses/
*
********************************************************************/

#include <m4ri/m4ri_config.h>

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#if __M4RI_USE_MM_MALLOC
#include <mm_malloc.h>
#endif

#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define __STDC_LIMIT_MACROS
#include <stdint.h>

/*
 * These define entirely the word width used in the library.
 */

typedef int BIT;

typedef int rci_t;

typedef int wi_t;


typedef uint64_t word;

#define __M4RI_CONVERT_TO_INT(w) ((int)(w))

#define __M4RI_CONVERT_TO_BIT(w) ((BIT)(w))

#define __M4RI_CONVERT_TO_UINT64_T(w) (w)

#define __M4RI_CONVERT_TO_WORD(i) ((word)(i))

static int const m4ri_radix = 64;

static word const m4ri_one = __M4RI_CONVERT_TO_WORD(1);

static word const m4ri_ffff = __M4RI_CONVERT_TO_WORD(-1);

#ifndef MAX
#define MAX(x,y) (((x) > (y))?(x):(y))
#endif

#ifndef MIN
#define MIN(x,y) (((x) < (y))?(x):(y))
#endif

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

#define __M4RI_TWOPOW(i) ((uint64_t)1 << (i))

#define __M4RI_CLR_BIT(w, spot) ((w) &= ~(m4ri_one << (spot))

#define __M4RI_SET_BIT(w, spot) ((w) |= (m4ri_one << (spot)))

#define __M4RI_GET_BIT(w, spot) __M4RI_CONVERT_TO_BIT(((w) >> (spot)) & m4ri_one)

#define __M4RI_WRITE_BIT(w, spot, value) ((w) = (((w) & ~(m4ri_one << (spot))) | (-__M4RI_CONVERT_TO_WORD(value) & (m4ri_one << (spot)))))

#define __M4RI_FLIP_BIT(w, spot) ((w) ^= (m4ri_one << (spot)))

#define __M4RI_LEFT_BITMASK(n) (m4ri_ffff >> (m4ri_radix - (n)) % m4ri_radix)

#define __M4RI_RIGHT_BITMASK(n) (m4ri_ffff << (m4ri_radix - (n)))

#define __M4RI_MIDDLE_BITMASK(n, offset) (__M4RI_LEFT_BITMASK(n) << (offset))

static inline word m4ri_swap_bits(word v) {
  v = ((v >>  1) & 0x5555555555555555ULL) | ((v & 0x5555555555555555ULL) << 1);
  v = ((v >>  2) & 0x3333333333333333ULL) | ((v & 0x3333333333333333ULL) << 2);
  v = ((v >>  4) & 0x0F0F0F0F0F0F0F0FULL) | ((v & 0x0F0F0F0F0F0F0F0FULL) << 4);
  v = ((v >>  8) & 0x00FF00FF00FF00FFULL) | ((v & 0x00FF00FF00FF00FFULL) << 8);
  v = ((v >> 16) & 0x0000FFFF0000FFFFULL) | ((v & 0x0000FFFF0000FFFFULL) << 16);
  v =  (v >> 32)                          |  (v                          << 32);
  return v;
}

static inline word m4ri_shrink_bits(word const from, rci_t* const Q, int const length, int const base) {
  word to = 0;
  switch(length-1) {
  case 15: to |= (from & (m4ri_one << (Q[15] - base))) >> (Q[15] - 15 - base);
  case 14: to |= (from & (m4ri_one << (Q[14] - base))) >> (Q[14] - 14 - base);
  case 13: to |= (from & (m4ri_one << (Q[13] - base))) >> (Q[13] - 13 - base);
  case 12: to |= (from & (m4ri_one << (Q[12] - base))) >> (Q[12] - 12 - base);
  case 11: to |= (from & (m4ri_one << (Q[11] - base))) >> (Q[11] - 11 - base);
  case 10: to |= (from & (m4ri_one << (Q[10] - base))) >> (Q[10] - 10 - base);
  case  9: to |= (from & (m4ri_one << (Q[ 9] - base))) >> (Q[ 9] -  9 - base);
  case  8: to |= (from & (m4ri_one << (Q[ 8] - base))) >> (Q[ 8] -  8 - base);
  case  7: to |= (from & (m4ri_one << (Q[ 7] - base))) >> (Q[ 7] -  7 - base);
  case  6: to |= (from & (m4ri_one << (Q[ 6] - base))) >> (Q[ 6] -  6 - base);
  case  5: to |= (from & (m4ri_one << (Q[ 5] - base))) >> (Q[ 5] -  5 - base);
  case  4: to |= (from & (m4ri_one << (Q[ 4] - base))) >> (Q[ 4] -  4 - base);
  case  3: to |= (from & (m4ri_one << (Q[ 3] - base))) >> (Q[ 3] -  3 - base);
  case  2: to |= (from & (m4ri_one << (Q[ 2] - base))) >> (Q[ 2] -  2 - base); 
  case  1: to |= (from & (m4ri_one << (Q[ 1] - base))) >> (Q[ 1] -  1 - base);
  case  0: to |= (from & (m4ri_one << (Q[ 0] - base))) >> (Q[ 0] -  0 - base);
    break;
  default:
    abort();
  }
  return to;
}

static inline word m4ri_spread_bits(word const from, rci_t* const Q, int const length, int const base) {
  word to = 0;
  switch(length-1) {
  case 15: to |= (from & (m4ri_one << (15))) << (Q[15]-15-base);
  case 14: to |= (from & (m4ri_one << (14))) << (Q[14]-14-base);
  case 13: to |= (from & (m4ri_one << (13))) << (Q[13]-13-base);
  case 12: to |= (from & (m4ri_one << (12))) << (Q[12]-12-base);
  case 11: to |= (from & (m4ri_one << (11))) << (Q[11]-11-base);
  case 10: to |= (from & (m4ri_one << (10))) << (Q[10]-10-base);
  case  9: to |= (from & (m4ri_one << ( 9))) << (Q[ 9]- 9-base);
  case  8: to |= (from & (m4ri_one << ( 8))) << (Q[ 8]- 8-base);
  case  7: to |= (from & (m4ri_one << ( 7))) << (Q[ 7]- 7-base);
  case  6: to |= (from & (m4ri_one << ( 6))) << (Q[ 6]- 6-base);
  case  5: to |= (from & (m4ri_one << ( 5))) << (Q[ 5]- 5-base);
  case  4: to |= (from & (m4ri_one << ( 4))) << (Q[ 4]- 4-base);
  case  3: to |= (from & (m4ri_one << ( 3))) << (Q[ 3]- 3-base);
  case  2: to |= (from & (m4ri_one << ( 2))) << (Q[ 2]- 2-base);
  case  1: to |= (from & (m4ri_one << ( 1))) << (Q[ 1]- 1-base);
  case  0: to |= (from & (m4ri_one << ( 0))) << (Q[ 0]- 0-base);
    break;
  default:
    abort();
  }
  return to;
}

#define __M4RI_ALIGNMENT(addr, n) (((unsigned long)(addr))%(n))

#if defined(__GNUC__) && defined(__GNUC_MINOR__)
#define __M4RI_GNUC_PREREQ(maj, min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
#else
#define __M4RI_GNUC_PREREQ(maj, min) FALSE
#endif

/* __builtin_expect is in gcc 3.0, and not in 2.95. */
#if __M4RI_GNUC_PREREQ(3,0) || defined(M4RI_DOXYGEN)

#define __M4RI_LIKELY(cond)    __builtin_expect ((cond) != 0, 1)

#define __M4RI_UNLIKELY(cond)  __builtin_expect ((cond) != 0, 0)

#else
#define __M4RI_LIKELY(cond)    (cond)
#define __M4RI_UNLIKELY(cond)  (cond)
#endif

static inline int m4ri_lesser_LSB(word a, word b)
{
  uint64_t const ia = __M4RI_CONVERT_TO_UINT64_T(a);
  uint64_t const ib = __M4RI_CONVERT_TO_UINT64_T(b);
  /*
   * If a is zero then we should always return false, otherwise
   * if b is zero we should return true iff a has at least one bit set.
   */
  return !(ib ? ((ia - 1) ^ ia) & ib : !ia);
}


/**** Error Handling *****/

void m4ri_die(const char *errormessage, ...);

/**** IO *****/

void m4ri_word_to_str( char *destination, word data, int colon);

static inline BIT m4ri_coin_flip() {
  if (rand() < RAND_MAX/2) {
    return 0;
  }  else {
    return 1;
  }
}

word m4ri_random_word();

/***** Initialization *****/

#if defined(__GNUC__)
void __attribute__ ((constructor)) m4ri_init(void);
#else
void m4ri_init(void);
#endif

#ifdef __SUNPRO_C
#pragma init(m4ri_init)
#endif

#if defined(__GNUC__)
void __attribute__ ((destructor)) m4ri_fini(void);
#else
void m4ri_fini(void);
#endif

#ifdef __SUNPRO_C
#pragma fini(m4ri_fini)
#endif

/***** Memory Management *****/


#if __M4RI_CPU_L3_CACHE == 0
/*
 * Fix some standard value for L3 cache size if it couldn't be
 * determined by configure.
 */

#undef __M4RI_CPU_L3_CACHE
#if __M4RI_CPU_L2_CACHE
#define __M4RI_CPU_L3_CACHE __M4RI_CPU_L2_CACHE
#else
#define __M4RI_CPU_L3_CACHE 4194304
#endif // __M4RI_CPU_L2_CACHE
#endif // __M4RI_CPU_L3_CACHE

#if __M4RI_CPU_L2_CACHE == 0
/*
 * Fix some standard value for L2 cache size if it couldn't be
 * determined by configure.
 */
#undef __M4RI_CPU_L2_CACHE
#define __M4RI_CPU_L2_CACHE 262144
#endif // __M4RI_CPU_L2_CACHE


#if __M4RI_CPU_L1_CACHE == 0
/*
 * Fix some standard value for L1 cache size if it couldn't be
 * determined by configure.
 */
#undef __M4RI_CPU_L1_CACHE
#define __M4RI_CPU_L1_CACHE 16384
#endif // __M4RI_CPU_L1_CACHE


static inline void *m4ri_mm_calloc(size_t count, size_t size) {
  void *newthing;
#if __M4RI_USE_MM_MALLOC
  newthing = _mm_malloc(count * size, 64);
#elif __M4RI_USE_POSIX_MEMALIGN
  int error = posix_memalign(&newthing, 64, count * size);
  if (error) newthing = NULL;
#else
  newthing = calloc(count, size);
#endif

  if (newthing == NULL) {
    m4ri_die("m4ri_mm_calloc: calloc returned NULL\n");
    return NULL; /* unreachable. */
  }
#if __M4RI_USE_MM_MALLOC || __M4RI_USE_POSIX_MEMALIGN
  char *b = (char*)newthing;
  memset(b, 0, count * size);
#endif
  return newthing;
}

static inline void *m4ri_mm_malloc_aligned(size_t size, size_t alignment) {
  void *newthing;

#if __M4RI_USE_MM_MALLOC
  newthing = _mm_malloc(size, alignment);
#elif __M4RI_USE_POSIX_MEMALIGN
  int error = posix_memalign(&newthing, alignment, size);
  if (error)
    newthing = NULL;
#else
  newthing = malloc(size);
#endif

 if (newthing==NULL && (size>0)) {
   m4ri_die("m4ri_mm_malloc: malloc returned NULL\n");
   return NULL; /* unreachable */
 }
 else return newthing;
}

static inline void *m4ri_mm_malloc(size_t size) {
  void *newthing;
#if __M4RI_USE_MM_MALLOC
    newthing = _mm_malloc(size, 64);
#elif __M4RI_USE_POSIX_MEMALIGN
    int error = posix_memalign(&newthing, 64, size);
    if (error) newthing = NULL;
#else
    newthing = malloc(size);
#endif //__M4RI_USE_MM_MALLOC
  if (newthing==NULL && (size>0)) {
    m4ri_die("m4ri_mm_malloc: malloc returned NULL\n");
    return NULL; /* unreachable */
  }
  else return newthing;
}


/* void m4ri_mm_free(void *condemned, ...); */
static inline void m4ri_mm_free(void *condemned, ...) { 
#if __M4RI_USE_MM_MALLOC
    _mm_free(condemned);
#else
    free(condemned);
#endif
}


/*
 * MSVC does not understand the restrict keyword 
 */

#if defined (__GNUC__)
#define RESTRICT __restrict__
#else
#define RESTRICT
#endif



/*
 * Macros for template expansion.
 */

#define __M4RI_TEMPLATE_EXPAND0(x,y) x ## _ ## y
#define __M4RI_TEMPLATE_EXPAND1(x,y) __M4RI_TEMPLATE_EXPAND0(x,y)
#define __M4RI_TEMPLATE_NAME(fun) __M4RI_TEMPLATE_EXPAND1(fun, N)


#endif // M4RI_MISC_H