wilf-oar/src/semigroup.hpp

#ifndef SEMIGROUP_HPP
#define SEMIGROUP_HPP


#include <cstring>
#include <cstdint>
#include <cassert>
#include <immintrin.h>
#include <fstream>

#include "config.hpp"
#include "simd.hpp"

union v8x8{
  uint64_t v64;
  uint32_t v32[2];
  uint8_t v8[8];
};
  static const size_t m1_32=((1UL<<32)-1);
class Semigroup{
public:
  static const size_t _size=3*(g_max-1);
  static const size_t navx=((_size+31)/32);
  static const size_t nin=((_size+63)/64);
  static const size_t size=navx*32;

  union{
    __m256i avx[navx];
    uint8_t delta[size];
  };
  union{
    uint64_t in64[nin];
    uint32_t in32[2*nin];
  };    
  size_t c,m,g,e,e_left,left;

  Semigroup();
  void init_N();
  void copy_delta(const Semigroup& S);
  void copy_in(const Semigroup& S);
  
  void son(const Semigroup& S,size_t x,size_t pos);
  void display() const;
  void copy(const Semigroup& S);
  ~Semigroup();
  void to_file(string filename) const;
  void from_file(string filename);
};

class SonIterator{
public:
  const Semigroup *S;
  size_t  mask;   // movemask_epi8 returns a 32 bits values
  size_t iblock, gen, bound;
public:
  SonIterator(const Semigroup *S);
  bool move_next();
  uint8_t count();
  inline size_t get_gen() const {return gen;};
};

inline SonIterator::SonIterator(const Semigroup* _S)
  : S(_S), bound(min(Semigroup::navx-1,(_S->c+_S->m+31) >> 5)){
  iblock = S->c >> 5;
  size_t imask = (S->c&0x1F);
  __m256i a=S->avx[iblock];
  __m256i b=mask32[imask];
  __m256i block = _mm256_and_si256(a,b);
  mask  =  _mm256_movemask_epi8(_mm256_cmpeq_epi8(block,avx1))&m1_32;
  gen = (iblock << 5) - 1;
};

inline bool
SonIterator::move_next(){
  while (not mask){
    iblock++;
    if (iblock > bound) return false;
    gen = (iblock << 5) - 1;
    mask  = _mm256_movemask_epi8(_mm256_cmpeq_epi8(S->avx[iblock],avx1))&m1_32;
  }
  //unsigned char shift = __bsfq (mask) +1;
   uint64_t shift;
  asm("bsfq %1,%0" : "=r" (shift)  :"r" (mask));
  ++shift;

  gen += shift;
  mask >>= shift;
  return true;
};

inline
Semigroup::Semigroup(){
 
  
}

#define copy_delta_unroll(i) case (i): \
  avx[(i-1)]=S.avx[(i-1)];

inline void 
Semigroup::copy_delta(const Semigroup& S){
  switch(navx){
    copy_delta_unroll(16);
    copy_delta_unroll(15);
    copy_delta_unroll(14);
    copy_delta_unroll(13);
    copy_delta_unroll(12);
    copy_delta_unroll(11);
    copy_delta_unroll(10);
    copy_delta_unroll(9);
    copy_delta_unroll(8);
    copy_delta_unroll(7);
    copy_delta_unroll(6);
    copy_delta_unroll(5);
    copy_delta_unroll(4);
    copy_delta_unroll(3);
    copy_delta_unroll(2);
  case 1:
    avx[0]=S.avx[0];
    break;
  default:
    assert(false);
  };
}

#define copy_in_unroll(i) case (i): \
  in64[(i-1)]=S.in64[(i-1)];

inline void 
Semigroup::copy_in(const Semigroup& S){
  switch(nin){
    copy_in_unroll(8);
    copy_in_unroll(7);
    copy_in_unroll(6);
    copy_in_unroll(5);
    copy_in_unroll(4);
    copy_in_unroll(3);
    copy_in_unroll(2);
  case 1:
    in64[0]=S.in64[0];
    break;
  default:
    assert(false);
    break;
  };
}

inline
Semigroup::~Semigroup(){
}

#endif