algebramix_doc 0.3
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes
fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold > Class Template Reference

#include <fft_blocks.hpp>

List of all members.

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

template<typename C, typename FFTER = fft_naive_transformer<C>, nat log2_outer_block_size = 9, nat log2_block_number = 7, nat log2_inner_block_size = 11, nat threshold = 12>
class mmx::fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >

Examples:

fft_test.cpp.

Definition at line 31 of file fft_blocks.hpp.

Member Typedef Documentation

typedef implementation<vector_linear,vector_naive> NVec

Definition at line 33 of file fft_blocks.hpp.

typedef FFTER::R R

Definition at line 34 of file fft_blocks.hpp.

typedef R::S S

Definition at line 36 of file fft_blocks.hpp.

typedef R::U U

Definition at line 35 of file fft_blocks.hpp.

Constructor & Destructor Documentation

fft_blocks_transformer ( nat  n) [inline]

Definition at line 44 of file fft_blocks.hpp.

                                       :
    ffter (new FFTER (n)),
    depth (ffter->depth), len (ffter->len), roots (ffter->roots) {}
~fft_blocks_transformer ( ) [inline]

Definition at line 48 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ffter.

{ delete ffter; }

Member Function Documentation

static void delocate ( C *  c1,
nat  s1,
C *  c0,
nat  s0,
nat  n 
) [inline, static]

Definition at line 51 of file fft_blocks.hpp.

References mmx::C.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft().

                                                 {
    for (nat i= 0; i < s1; i++, c0 += s0) {
      C* cc0= c0, * cc1= c1 + i;
      for (nat k= 0; k < n; k++, cc0++, cc1+= s1)
        *cc1= *cc0; } }
void dfft ( C *  c,
nat  stride,
nat  shift,
nat  steps 
) [inline]

Definition at line 159 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft().

                                                {
    dfft (c, stride, shift, steps, 0, steps); }
void dfft ( C *  c,
nat  stride,
nat  shift,
nat  steps,
nat  step1,
nat  step2 
) [inline]

Definition at line 65 of file fft_blocks.hpp.

References mmx::C, fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::delocate(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ffter, and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::relocate().

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::direct_transform().

                                                                      {
    if (steps <= max (threshold, log2_inner_block_size))
      ffter->dfft (c, stride, shift, steps, step1, step2);
    else {
      nat temp_len= default_aligned_size<C>
        ((nat) 1<<(log2_outer_block_size+log2_block_number));
      C* c0, * temp= mmx_new<C> (temp_len);
      nat step, block, blocks, todo, k_beg, k_end;

      for (step= step1;
           step < min (steps - log2_inner_block_size, step2);
           step += block) {
        block = min (min (steps - log2_inner_block_size - step, step2 - step),
                     log2_outer_block_size);
        todo  = steps - 1 - step;
        blocks= todo - block + 1;
        c0= c;
        for (nat j= 0; j < ((nat) 1<<step); j++) {
          for (k_beg= 0; k_beg < ((nat) 1<<blocks); k_beg= k_end) {
            k_end= min (((nat) 1<<blocks),
                        k_beg + ((nat) 1<< log2_block_number));
            delocate (temp, (nat) 1<<block,
                      c0 + k_beg, stride<<blocks, k_end - k_beg);
            for (nat k= 0; k < k_end - k_beg; k++)
              ffter->dfft (temp+(k<<block), 1,
                           ((shift>>todo) + j)<<(block-1), block);
            relocate (temp, (nat) 1<<block,
                      c0+k_beg, stride<<blocks, k_end - k_beg);
          }
          c0 += (stride<<(todo+1));
        }
      }
      mmx_delete<C> (temp, temp_len);
      if (step < step2) {
        c0= c;
        todo= steps - 1 - step;
        for (nat j= 0; j < ((nat) 1<<step); j++) {
          ffter->dfft (c0, stride, ((shift>>todo) + j) << todo,
                       todo+1, 0, step2-step);
          c0 += (stride<<(todo+1));
        }
      }
    }
  }
void direct_transform ( C *  c) [inline]

Definition at line 167 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::depth, and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft().

                          {
    dfft (c, 1, 0, depth); }
void ifft ( C *  c,
nat  stride,
nat  shift,
nat  steps,
nat  step1,
nat  step2 
) [inline]

Definition at line 111 of file fft_blocks.hpp.

References mmx::C, fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::delocate(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ffter, and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::relocate().

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::inverse_transform().

                                                                      {
    if (steps <= max (threshold, log2_inner_block_size))
      ffter->ifft (c, stride, shift, steps, step1, step2);
    else {
      nat temp_len= default_aligned_size<C>
        ((nat) 1<<(log2_outer_block_size+log2_block_number));
      C* c0, * temp= mmx_new<C> (temp_len);
      nat step, block, blocks, todo, k_beg, k_end;

      if (log2_inner_block_size > steps - step2) {
        step= steps - log2_inner_block_size;
        c0= c;
        todo= steps - 1 - step;
        for (nat j= 0; j < ((nat) 1<<step); j++) {
          ffter->ifft (c0, stride, ((shift>>todo) + j) <<todo,
                       todo+1, max(0, (int) step1- (int) step), step2-step);
          c0 += (stride<<(todo+1));
        }
      }
      else
        step= step2;

      while (step > step1) {
        block = min (step - step1, log2_outer_block_size);
        step -= block;
        todo  = steps - 1 - step;
        blocks= todo - block + 1;
        c0= c;
        for (nat j= 0; j < ((nat) 1<<step); j++) {
          for (k_beg= 0; k_beg < ((nat) 1<<blocks); k_beg= k_end) {
            k_end= min (((nat) 1<<blocks),
                        k_beg + ((nat) 1<< log2_block_number));
            delocate (temp, (nat) 1<<block,
                      c0 + k_beg, stride<<blocks, k_end - k_beg);
            for (nat k= 0; k < k_end - k_beg; k++)
              ffter->ifft (temp+(k<<block), 1,
                           ((shift>>todo) + j)<<(block-1), block);
            relocate (temp, (nat) 1<<block,
                      c0+k_beg, stride<<blocks, k_end - k_beg);
          }
          c0 += (stride<<(todo+1));
        }
      }
      mmx_delete<C> (temp, temp_len);
    }
  }
void ifft ( C *  c,
nat  stride,
nat  shift,
nat  steps 
) [inline]

Definition at line 163 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft().

                                                {
    ifft (c, stride, shift, steps, 0, steps); }
void inverse_transform ( C *  c,
bool  divide = true 
) [inline]

Definition at line 171 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::depth, fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft(), mmx::invert(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::len.

                                             {
    ifft (c, 1, 0, depth);
    if (divide) {
      S x= binpow (S (2), depth);
      x= invert (x);
      NVec::template vec_unary_scalar<typename R::fft_mul_sc_op> (c, x, len);
    }
  }
static void relocate ( C *  c1,
nat  s1,
C *  c0,
nat  s0,
nat  n 
) [inline, static]

Definition at line 58 of file fft_blocks.hpp.

References mmx::C.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft().

                                                 {
    for (nat i= 0; i < s1; i++, c0 += s0) {
      C* cc0= c0, * cc1= c1 + i;
      for (nat k= 0; k < n; k++, cc0++, cc1+= s1)
        *cc0= *cc1; } }

Member Data Documentation

nat depth

Definition at line 39 of file fft_blocks.hpp.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::direct_transform(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::inverse_transform().

FFTER* ffter

Definition at line 38 of file fft_blocks.hpp.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::~fft_blocks_transformer().

nat len

Definition at line 40 of file fft_blocks.hpp.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::inverse_transform().

U* roots

Definition at line 41 of file fft_blocks.hpp.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Friends Defines