#include <fft_threads.hpp>

Classes

struct inner_fft_task_rep
struct outer_fft_task_rep

Public Types

typedef implementation
< vector_linear,
vector_threads< vector_naive > > Vec
typedef FFTER::R R
typedef R::U U
typedef R::S S

Public Member Functions

fft_threads_transformer (nat n)
~fft_threads_transformer ()
void fft (bool direct, C *c, nat stride, nat shift, nat steps)
void dfft (C *c, nat stride, nat shift, nat steps)
void ifft (C *c, nat stride, nat shift, nat steps)
void dfft (C *c, nat stride, nat shift, nat steps, nat step1, nat step2)
void ifft (C *c, nat stride, nat shift, nat steps, nat step1, nat step2)
void direct_transform (C *c)
void inverse_transform (C *c, bool divide=true)

Static Public Member Functions

static void copy (C *d, nat drs, nat dcs, C *s, nat srs, nat scs, nat r, nat c)

Public Attributes

FFTER * ffter
nat depth
nat len
U * roots

Static Public Attributes

static const nat min_reps = 16

Detailed Description

template<typename C, typename FFTER = fft_blocks_transformer<C, fft_naive_transformer<C>, 8, 6, 10>, nat thr = 14>
class mmx::fft_threads_transformer< C, FFTER, thr >

Examples:: fft_test.cpp.

Definition at line 30 of file fft_threads.hpp.

Member Typedef Documentation

typedef FFTER::R R

Definition at line 33 of file fft_threads.hpp.

typedef R::S S

Definition at line 35 of file fft_threads.hpp.

typedef R::U U

Definition at line 34 of file fft_threads.hpp.

typedef implementation<vector_linear,vector_threads<vector_naive> > Vec

Definition at line 32 of file fft_threads.hpp.

Constructor & Destructor Documentation

fft_threads_transformer ( nat n ) [inline]

Definition at line 44 of file fft_threads.hpp.

                                        :
    ffter (new FFTER (n)),
    depth (ffter->depth), len (ffter->len), roots (ffter->roots) {}

~fft_threads_transformer ( ) [inline]

Definition at line 47 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::ffter.

{ delete ffter; }

Member Function Documentation

static void copy	(	C *	d,
		nat	drs,
		nat	dcs,
		C *	s,
		nat	srs,
		nat	scs,
		nat	r,
		nat	c
	)		`[inline, static]`

Definition at line 50 of file fft_threads.hpp.

References mmx::C.

Referenced by fft_threads_transformer< C, FFTER, thr >::outer_fft_task_rep::execute().

                                                                      {
    for (nat j=0; j<c; j++, d+=dcs, s+=scs) {
      C* dd= d; C* ss= s;
      for (nat i=0; i<r; i++, dd+=drs, ss+=srs)
        *dd= *ss;
    }
  }

void dfft	(	C *	c,
		nat	stride,
		nat	shift,
		nat	steps,
		nat	step1,
		nat	step2
	)		`[inline]`

Definition at line 179 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::fft(), and fft_threads_transformer< C, FFTER, thr >::ffter.

                                                                      {
    if (step1 == 0 && step2 == steps && steps > thr)
      fft (true, c, stride, shift, steps);
    else ffter->dfft (c, stride, shift, steps, step1, step2);
  }

void dfft	(	C *	c,
		nat	stride,
		nat	shift,
		nat	steps
	)		`[inline]`

Definition at line 167 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::fft(), and fft_threads_transformer< C, FFTER, thr >::ffter.

Referenced by fft_threads_transformer< C, FFTER, thr >::direct_transform().

                                                {
    if (steps <= thr) ffter->dfft (c, stride, shift, steps);
    else fft (true, c, stride, shift, steps);
  }

void direct_transform ( C * c ) [inline]

Definition at line 193 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::depth, and fft_threads_transformer< C, FFTER, thr >::dfft().

                          {
    dfft (c, 1, 0, depth); }

void fft	(	bool	direct,
		C *	c,
		nat	stride,
		nat	shift,
		nat	steps
	)		`[inline]`

Definition at line 118 of file fft_threads.hpp.

References mmx::C, fft_threads_transformer< C, FFTER, thr >::ffter, and fft_threads_transformer< C, FFTER, thr >::min_reps.

Referenced by fft_threads_transformer< C, FFTER, thr >::dfft(), and fft_threads_transformer< C, FFTER, thr >::ifft().

                                                            {
    if (steps <= thr) {
      if (direct) ffter->dfft (c, stride, shift, steps);
      else ffter->ifft (c, stride, shift, steps);
    }
    else {
      nat half1= min(log_2 (threads_number), steps);
      nat half2= steps - half1;

      for (nat stage=0; stage<2; stage++) {
        if ((stage == 0) ^ (!direct)) {
          //C*  cc1  = c;
          //for (nat i=0; i<((nat) 1<<half2); i++, cc1 += stride)
          //  ffter->fft (direct, cc1, stride << half2,
          //              shift >> half2, half1);

          nat nt = threads_number;
          nat bsz= (min_reps << half1);
          C* buf= mmx_new<C> (nt * bsz);
          task tasks[nt];
          for (nat i=0; i<nt; i++) {
            nat tot= 1 << half2;
            nat sta= min_reps * ((  i   * tot) / (min_reps * nt));
            nat end= min_reps * (((i+1) * tot) / (min_reps * nt));
            tasks[i]= new outer_fft_task_rep
              (ffter, direct, buf + i*bsz, end-sta, tot,
               c + sta*stride, stride, shift >> half2, half1);
          }
          threads_execute (tasks, nt);
          mmx_delete<C> (buf, nt * bsz);

        }
        else {
          //C* cc2= c;
          //for (nat i=0; i<((nat) 1<<half1); i++, cc2 += (stride << half2))
          //  ffter->fft (direct, cc2, stride,
          //              shift + ((i << half2) >> 1), half2);
          nat nt= threads_number;
          task tasks[nt];
          for (nat i=0; i<nt; i++)
            tasks[i]= new inner_fft_task_rep
              (ffter, direct, i, nt, 1 << half1, c, stride, shift, half2);
          threads_execute (tasks, nt);
        }
      }
    }
  }

void ifft	(	C *	c,
		nat	stride,
		nat	shift,
		nat	steps
	)		`[inline]`

Definition at line 173 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::fft(), and fft_threads_transformer< C, FFTER, thr >::ffter.

Referenced by fft_threads_transformer< C, FFTER, thr >::inverse_transform().

                                                {
    if (steps <= thr) ffter->ifft (c, stride, shift, steps);
    else fft (false, c, stride, shift, steps);
  }

void ifft	(	C *	c,
		nat	stride,
		nat	shift,
		nat	steps,
		nat	step1,
		nat	step2
	)		`[inline]`

Definition at line 186 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::fft(), and fft_threads_transformer< C, FFTER, thr >::ffter.

                                                                      {
    if (step1 == 0 && step2 == steps && steps > thr)
      fft (false, c, stride, shift, steps);
    else ffter->ifft (c, stride, shift, steps, step1, step2);
  }

void inverse_transform	(	C *	c,
		bool	divide = `true`
	)		`[inline]`

Definition at line 197 of file fft_threads.hpp.

References fft_threads_transformer< C, FFTER, thr >::depth, fft_threads_transformer< C, FFTER, thr >::ifft(), mmx::invert(), and fft_threads_transformer< C, FFTER, thr >::len.

                                             {
    ifft (c, 1, 0, depth);
    if (divide) {
      S x= binpow (S (2), depth);
      x= invert (x);
      Vec::template vec_unary_scalar<typename R::fft_mul_sc_op> (c, x, len);
    }
  }