123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152 |
- #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
|