The napa-fft3 Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The napa-fft3 Reference Manual

This is the napa-fft3 Reference Manual, version 0.0.1, generated automatically by Declt version 2.3 "Robert April" on Tue Jan 09 15:23:54 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Napa-FFT3: Overview

Napa-FFT3 is a complete rewrite of Napa-FFT (version 2 is an aborted experiment). The goal is still the same: to provide, via a mixture of cache-friendly algorithms and code generation, FFT routines in Common Lisp that offer performance comparable to the state of the art. In that regard, it is a success: depending on how it's used, Napa-FFT3 is, at most, around three times as slow as FFTW on small or medium inputs, and can be faster than FFTW for large inputs. The complete picture is more complicated than this; see the Performance section for details.

The goal of Napa-FFT3 isn't only to provide Discrete Fourier Transform (DFT) routines, but also (rather) to provide buildings blocks to express common operations that involve DFTs: filtering, convolutions, etc. This is what enables Napa-FFT to achieve such high performance without optimizing at the assembly level. The Easy Interface section should suffice for most developers; the Low-level Interface is described in another section, and may be of interest to some.

Napa-FFT3 also expressly supports FFTs on real data and inverse FFTs back to real data. The Real Interface section describes the facility, and is used in conjunction with the Easy Interface.

Finally, see the Installation section for installation instructions, and the Implementation section for all the gory details.

Note that Napa-FFT3 currently only supports power-of-two-sized inputs; even when/if it will gain code for arbitrary sizes, powers of two will most likely be much more efficient, both in terms of runtime and space usage.

To recapitulate:

Installation

Napa-FFT3 is a regular ASDF system defined in napa-fft3.asd. If Quicklisp is installed, it suffices to copy the Napa-FFT3 directory under ~/quicklisp/local-projects.

Once registered with ASDF, Napa-FFT3 can be loaded by executing (asdf:oos 'asdf:load-op "napa-fft3"), or, with Quicklisp, (ql:quickload "napa-fft3").

Easy Interface

The core of the "easy" interface consists of:

FFT

Syntax: fft vec &key dst size in-order scale window => vector.

Arguments and Values:

FFT computes the DFT of the first size values in vec.

First, vec is converted to a simple array of complex samples if necessary. The result is stored in dst, or a fresh array of complex doubles. dst may be the same object as vec for an in-place transform.

If window is non-nil, each value in vec is multiplied by the corresponding value in window during the transform; similarly, the values are scaled according to the value of scale.

If in-order is true, the result is then converted to be in order, which can take more than half as much time as the FFT itself.

Example:

CL-USER> (napa-fft:fft '(0 1 2 3 4 5 6 7))
#(#C(28.0d0 0.0d0) #C(-4.0d0 9.65685424949238d0) #C(-4.0d0 4.0d0)
  #C(-4.0d0 1.6568542494923806d0) #C(-4.0d0 0.0d0)
  #C(-4.0d0 -1.6568542494923806d0) #C(-4.0d0 -4.0d0)
  #C(-4.0d0 -9.65685424949238d0))

;; the same, but bit reversed
CL-USER> (napa-fft:fft '(0 1 2 3 4 5 6 7) :in-order nil)
#(#C(28.0d0 0.0d0) #C(-4.0d0 0.0d0) #C(-4.0d0 4.0d0) #C(-4.0d0 -4.0d0)
  #C(-4.0d0 9.65685424949238d0) #C(-4.0d0 -1.6568542494923806d0)
  #C(-4.0d0 1.6568542494923806d0) #C(-4.0d0 -9.65685424949238d0))

;; :scale nil is the default
CL-USER> (napa-fft:fft '(0 1 2 3) :scale nil)
#(#C(6.0d0 0.0d0) #C(-2.0d0 2.0d0) #C(-2.0d0 0.0d0) #C(-2.0d0 -2.0d0))

;; the same, but scaled by 1/4
CL-USER> (napa-fft:fft '(0 1 2 3) :scale t)
#(#C(1.5d0 0.0d0) #C(-0.5d0 0.5d0) #C(-0.5d0 0.0d0) #C(-0.5d0 -0.5d0))

;; again, scaled by 1/sqrt(4) = 1/2
CL-USER> (napa-fft:fft '(0 1 2 3 5 6 7 8) :size 4 :scale :sqrt)
#(#C(3.0d0 0.0d0) #C(-1.0d0 1.0d0) #C(-1.0d0 0.0d0) #C(-1.0d0 -1.0d0))

IFFT

Syntax: ifft vec &key dst size in-order scale window => vector.

Arguments and Values:

IFFT computes the inverse DFT of the first size Fourier coefficients in vec.

First, vec is converted to a simple array of complex samples if necessary. The result is stored in dst, or a fresh array of complex doubles. dst may be the same object as vec for an in-place transform.

If in-order is true, the result is then converted to be bit-reversed, which can take more than half as much time as the FFT itself.

If window is non-nil, each value in vec is multiplied by the corresponding value in window during the transform; similarly, the values are scaled according to scale. Note that this happens after the bit-reversal. window should thus be bit-reversed itself. Since this corresponds to a convolution, this is usually easily satisfied.

Example:

;; the defaults ensure fft and ifft are inverses
CL-USER> (napa-fft:ifft (napa-fft:fft '(0 1 2 3)))
#(#C(0.0d0 0.0d0) #C(1.0d0 0.0d0) #C(2.0d0 0.0d0) #C(3.0d0 0.0d0))

;; Skipping both bit-reversals saves a lot of time, without
;; changing the result; similarly, scaling can happen at any
;; step.
CL-USER> (napa-fft:ifft (napa-fft:fft '(0 1 2 3) :in-order nil
                                  :scale :sqrt)
                    :in-order nil
                    :scale :sqrt)
#(#C(0.0d0 0.0d0) #C(1.0d0 0.0d0) #C(2.0d0 0.0d0) #C(3.0d0 0.0d0))

;; The :window argument performs convolutions; simply make
;; sure that :in-order is nil when transforming the convolved
;; vector.  Here, the input is shifted one element to the
;; right and scaled by 1/2.
CL-USER> (napa-fft:ifft (napa-fft:fft '(0 1 2 3))
                        :window (napa-fft:fft '(0 1/2 0 0)
                                              :in-order nil))
#(#C(1.5d0 0.0d0) #C(0.0d0 0.0d0) #C(0.5d0 0.0d0) #C(1.0d0 0.0d0))

BIT-REVERSE

Syntax: bit-reverse vec &optional dst size => vector.

Arguments and values:

BIT-REVERSE permutes the first size elements in vec to bit-reversed indices, storing the result in dst if provided. vec may be the same as dst for an in-place reversal.

It should usually not be necessary to bit-reverse values explicitly, but it may still be useful to convert an in-order vector to out-of-order or vice-versa.

Example:

CL-USER> (napa-fft:bit-reverse (coerce '(0d0 1d0 2d0 3d0)
                                       'napa-fft:real-sample-array))
#(0.0d0 2.0d0 1.0d0 3.0d0)

;; bit-reverse is its own inverse.
CL-USER> (napa-fft:bit-reverse * *)
#(0.0d0 1.0d0 2.0d0 3.0d0)

WINDOWED-FFT

TODO. It's the same as Bordeaux FFT.

WINDOWED-IFFT

Real Interface

The real interface offers three functions specialized to operate on real (not complex) data:

These are convenient because the result is a vector of real values, but also offer strong performance improvements (almost halving computation times) for in-order, out-of-place, transforms, at the expense of a little precision.

RFFT

Syntax: rfft vec &key dst size scale => vector

Arguments and values:

RFFT computes the in-order DFT of the first size samples in vec.

vec is converted, if necessary, to a simple array of doubles. Its DFT is then re-expressed as a half-size DFT of complex samples, and the result is written in dst.

Example:

;; rfft should always yield the same result as fft (modulo
;; rounding)
CL-USER> (napa-fft:rfft '(0 1 2 3))
#(#C(6.0d0 0.0d0) #C(-2.0d0 2.0d0) #C(-2.0d0 0.0d0)
  #C(-1.9999999999999998d0 -2.0d0))

RIFFT

Syntax: rifft vec &key dst size scale => vector

Arguments and values:

RIFFT computes the in-order inverse DFT of the first size Fourier coefficients in vec.

vec is converted, if necessary, to a simple array of complex doubles. Its inverse DFT is then re-expressed, destructively as a half-size DFT of complex doubles. The procedure can only work correctly when the output is purely real: even if we're only interested in the real component, it will be distorted by any non-zero imaginary value.

Example:

CL-USER> (napa-fft:rifft (napa-fft:rfft '(0 1 2 3)))
#(0.0d0 1.0d0 2.0d0 3.0d0)

WINDOWED-RFFT

Same.

WINDOWED-RIFFT

...

Examples

I'm no good at this signal processing stuff; most of what I know about this comes, indirectly, from classical music training.

I'll use sox to play sound files easily, and the following function to convert float samples to s32 files:

(defun emit-raw32-file (file data &optional (max 1d0))
  (with-open-file (s file :direction :output :element-type '(signed-byte 32)
                          :if-exists :supersede)
    (write-sequence (map-into (make-array (length data)
                                          :element-type '(signed-byte 32))
                              (lambda (data)
                                (let ((x (/ (float (realpart data) 1d0)
                                            max)))
                                  (floor (* x (1- (ash 1 31))))))
                              data)
                    s)
    file))

Napa-FFT3 does a fair amount of runtime compilation and cached computations. If an operation is slow (more than one second), it was almost certainly due to a slow one-time operation; try running it again. Also, there's a lot of gratuitous consing, here. Nearly all the operations could be in-place and (nearly) non-consing without any change to the code.

Generate a single tone

The standard frequency of the middle A is 440 Hz nowadays. Sound is commonly generated, on computers, at 44100 Hz. Let's generate a signal of 64k points that, when played back at 44100 Hz, will result in an A440. The following function returns a vector with zeros everywhere except where specified in the first argument, a list designator of indices.

(defun impulse (i n &optional (value 1d0))
  (let ((vec (make-array n :element-type 'napa-fft:complex-sample
                           :initial-element (complex 0d0 0d0))))
    (dolist (i (if (listp i) i (list i)) vec)
      (setf (aref vec i) (complex (float value 1d0))))))

The DFT computes a vector such that each entry corresponds to the amount of energy in the frequency(ies) corresponding to that entry. The i th entry of an N -element Fourier-coefficient vector, with an original sampling frequency of F corresponds to a signal frequency of iF/N (+/- F/N ). So, if we want a wave at 440 Hz in in a vector of 64k played back at 44100 Hz, we have to put energy in the (440/44100)*65536 th bin.

;; create a vector with 1 only in the bin corresponding to 440 Hz,
;; convert back to the time domain, and save the double values as
;; a file of (signed-byte 32) values.
CL-USER> (emit-raw32-file "~/napa-fft3/example/a440.s32"
                          (napa-fft:ifft (impulse (round (* 440 65536)
                                                         44100)
                                                  65536)
                                         :scale nil))
"~/napa-fft3/example/foo.s32"

$ play -r44100 a440.s32 # play is a sox command; play a file of
                        # signed 32 bit samples at 44100 Hz.
                        # Should sound like an A440!

Generate a chord

We (westerners) are mostly used to a scale system based on 12 equispaced (not quite, but close enough) semi-tones. Reality tends to enforce that the scale covers a range of frequences for F to 2F. For example, while the middle A is at 440 Hz, the one in the next octave is at 880 Hz. The middle C is 9 half-tones lower than the middle A, at (* 440 (expt .5 (/ 9 12))), around 262 Hz (264 Hz in the real world). E is then 2 tones higher, at (* 262 (expt 2 (/ 4 12))) ~= 330 Hz, and G a tone and a half higher again, (* 330 (expt 2 (/ 3 12))) ~= 392 Hz.

Thus, to hear the boring middle C/E/G chord, we need energy at 262, 330 and 392 Hz; note how the energy is 1/3 at each point, so that the total comes to 1.

CL-USER> (emit-raw32-file "~/napa-fft3/example/chord.s32"
                          (napa-fft:ifft (impulse (list (round (* 262 65536)
                                                               44100)
                                                        (round (* 330 65536)
                                                               44100)
                                                        (round (* 392 65536)
                                                               44100))
                                                  65536
                                                  (/ 3d0))
                                         :scale nil))
"~/napa-fft3/example/foo.s32"

$ play -r44100 chord.s32 # you should recognize this sound

Filter frequencies out

First, let's save our time-domain chord signal:

CL-USER> (defparameter *chord* (napa-fft:ifft
                                (impulse (list (round (* 262 65536) 44100)
                                               (round (* 330 65536) 44100)
                                               (round (* 392 65536) 44100))
                                         65536
                                         (/ 3d0))
                                :scale nil))
*CHORD*

Here's a function to generate random noise and another to average two vectors:

(defun noise (n &optional (range .5d0))
  (let ((2range (* 2 range)))
    (map-into (make-array n :element-type 'napa-fft:complex-sample)
              (lambda ()
                (complex (- (random 2range) range))))))

(defun m+ (x y &optional (scale .5d0))
  (map 'napa-fft:complex-sample-array
       (lambda (x y)
         (* scale (+ x y)))
       x y))

We can noise our signal up by adding noise to the chord:

CL-USER> (defparameter *noisy-chord* (m+ *chord* (noise 65536)))
*NOISY-CHORD*

$ play -r44100 noised-chord.s32 # still recognizable, but
                                # annoying.

Let's say that we know that the only interesting stuff is in the central octave. We could zero out all the frequencies outside the 262-524 Hz range.

First, we have to convert the noisy signals in the frequency domain:

CL-USER> (defparameter *noisy-chord-freq* (napa-fft:fft *noisy-chord*))
*NOISY-CHORD-FREQ*

Then, we want to replace everything outside (round (* 262 65536) 44100) and (round (* 524 65536) 44100) with 0:

CL-USER> (defparameter *octave-chord-freq* (copy-seq *noisy-chord-freq*))
*OCTAVE-CHORD-FREQ*
CL-USER> (prog1 nil
           (fill *octave-chord-freq* (complex 0d0)
                 :end (round (* 262 65536) 44100))
           (fill *octave-chord-freq* (complex 0d0)
                 :start (1+ (round (* 524 65536) 44100))))

Now, we can convert back in the time domain and listen to the result:

CL-USER> (emit-raw32-file "~/napa-fft3/example/octave-chord.s32"
                          (napa-fft:ifft *octave-chord-freq*))

Much better.

Filter frequencies out in a real signal

Note that, as is often the case, we know that our signal is real (has no imaginary component). In this case, we can use real-only FFT/IFFT instead:

CL-USER> (defparameter *noisy-chord-freq*
           (napa-fft:rfft (map 'napa-fft:real-sample-array
                               #'realpart
                               *noisy-chord*)))
*NOISY-CHORD-FREQ*
CL-USER> (prog1 nil
           (fill *octave-chord-freq* (complex 0d0)
                 :end (round (* 262 65536) 44100))
           (fill *octave-chord-freq* (complex 0d0)
                 :start (1+ (round (* 524 65536) 44100))))
NIL
CL-USER> (emit-raw32-file "~/napa-fft3/example/octave-chord.s32"
                          (napa-fft:rifft *octave-chord-freq*))

The result is the same, but (once the routines are compiled), each FFT/IFFT is about twice as fast. Mind the fact that rifft is destructive on its input, however. It also only works when the output is purely real; any non-zero imaginary component will warp the real-valued output.

Filter frequencies out during the IFFT

We can do this directly, by filtering during the inverse FFT. Replacing most values with 0 and leaving the rest along is equivalent to multiplying by 0 or 1 (usually, we want a more gradual dampening, and the filter will also have fractional values).

CL-USER> (defun central-octave-filter (i n)
           (if (<= (round (* 262 n) 44100)
                   i
                   (round (* 524 n) 44100))
               1 0))
CENTRAL-OCTAVE-FILTER
CL-USER> (defparameter *filter*
           (napa-fft:window-vector 'central-octave-filter
                                   65536))
*FILTER*
CL-USER> (defparameter *filtered-noisy-chord-freq*
           (map 'napa-fft:complex-sample-array #'*
                *filter* *noisy-chord-freq*))
*FILTERED-NOISY-CHORD-FREQ*
CL-USER> (emit-raw32-file "~/napa-fft3/example/octave-chord2.s32"
                          (napa-fft:ifft *filtered-noisy-chord-freq*))
"~/napa-fft3/example/octave-chord.s32"

And we have the same final result. Obviously, an advantage is that we can compute the filter once, and easily apply it directly.

Another advantage is that we can bit-reverse (permute) the filter instead of bit-reversing after the FFT and before the IFFT. Again, the final result is the same, but we only bit-reverse the (cached) filter vector instead of many frequency domain vector.

CL-USER> (emit-raw32-file "~/napa-fft3/example/octave-chord3.s32"
                          (napa-fft:windowed-ifft 
                           (napa-fft:fft *noisy-chord* :in-order nil)
                           :window-fn 'central-octave-filter
                           :in-order nil))
"~/napa-fft3/example/octave-chord3.s32"

Filter low-amplitude noise out

In the previous example we already knew at what frequency the interesting signal was. That's sometimes the case (e.g. when some of us unconsciously filter out annoyingly-high-pitched voices), but somewhat uncommon.

Instead of applying a constant filter on frequencies, we can attempt to find which frequencies dominate (have a high energy), and eliminate the rest.

Filter by strength

The easiest way is to find the frequency with the most energy, and clamp out everything that's below a fixed fraction (e.g. 1%) of that.

(defun amplitude-clamp-fraction (vector fraction)
  (let ((limit (* (reduce #'max vector :key #'abs)
                  fraction)))
    (map 'napa-fft:complex-sample-array
         (lambda (x)
           (if (< (abs x) limit)
               (complex 0d0)
               x))
         vector)))

This function performs the same operation, regardless of the order in which its data is permuted. We can thus use out-of-order FFTs and IFFTs here as well.

CL-USER> (emit-raw32-file "~/napa-fft3/example/octave-chord4.s32"
                          (napa-fft:ifft
                           (amplitude-clamp-fraction
                            (napa-fft:fft *noisy-chord* :in-order nil)
                            1d-2)
                           :in-order nil))
"~/napa-fft3/example/octave-chord4.s32"

When frequencies below 1% of the max energy are zeroed out, the amount of noise is significantly reduced, but there's still an annoying ringing. Increasing the limit to 2% improves matters a lot; however, if we set too high a limit, we'll start to filter out interesting, if somewhat weak, sounds.

Filter by count

We could also know ahead of time that there are only a few (e.g. 3) interesting frequencies in the signal. In that case, we can find the k frequencies with the most energy, and remove everything else:

(defun amplitude-clamp-k (vector k)
  (let* ((n      (length vector))
         (values (make-array n)))
    (dotimes (i n)
      (setf (aref values i) (cons (abs (aref vector i)) i)))
    ;; this would be a heap or a quickselect if I cared
    (sort values #'> :key #'car)
    (let ((result (make-array n
                              :element-type 'napa-fft:complex-sample
                              :initial-element (complex 0d0))))
      (loop repeat k
            for (nil . i) across values
            do (setf (aref result i) (aref vector i))
            finally (return result)))))

Again, the input may be permuted without changing the result, so we can stick to out-of-order transforms:

CL-USER> (emit-raw32-file "~/napa-fft3/example/octave-chord5.s32"
                          (napa-fft:ifft
                           (amplitude-clamp-k
                            (napa-fft:fft *noisy-chord* :in-order nil)
                            3) ; we're cheating here (:
                           :in-order nil))
"~/napa-fft3/example/octave-chord5.s32"

Windowing chunks of long signals

Let's filter Justin Bieber out of one of his songs. That's actually a very difficult task, especially for example code: voices tend to have rich harmonics, and span a wide range of frequencies. What we can do is filter every frequency higher than a certain limit.

First, I use sox to convert the input (in wave format) to mono s32:

$ sox never.wav -r 44100 -c 1 never.s32

I can now read the first minute and convert it to doubles:

(defun read-raw32-file (file &optional n (max 1d0))
  (with-open-file (s file :element-type '(signed-byte 32))
    (let* ((n   (or n
                    (file-length s)))
           (seq (make-array n :element-type '(signed-byte 32))))
      (read-sequence seq s)
      (let ((scale (expt (* 2d0 max) -31)))
        (declare (type double-float scale))
        (map 'napa-fft:real-sample-array
             (lambda (x)
               (* x scale))
             seq)))))

CL-USER> (defparameter *never* (read-raw32-file "~/napa-fft3/example/never.s32"
                                                (* 44100 60)))
*NEVER*

We could just transform the whole 60 seconds at once, and revert it, but that'd be a lot of work. Instead, we'll chunk it into short periods, say one tenth of a second, and filter each chunk separately. We'll simplify things and use chunks of 4096 samples (slightly less than 4410 samples).

Some fiddling around lets us discover than Bieber seems to sing around 260 Hz and higher, so we'll cut off frequencies from 260 Hz and up.

CL-USER> (defparameter *jb-filter*
           (napa-fft:window-vector (lambda (i n)
                                     (if (< i (round (* 260 n) 44100))
                                         1 0))
                                   4096))
*JB-FILTER*

The following function will apply the same filter to each chunk of samples.

(defun filter-chunks (vector filter)
  (declare (type napa-fft:real-sample-array vector filter))
  (let* ((destination (make-array (length vector)
                                  :element-type 'napa-fft:complex-sample))
         (chunk-size  (length filter))
         (chunk       (make-array chunk-size
                                  :element-type 'napa-fft:complex-sample))
         (filter      (napa-fft:bit-reverse filter)))
    (declare (optimize speed))
    (loop for i below (length vector) by chunk-size
          for end = (min (length vector) (+ i chunk-size))
          do (fill chunk (complex 0d0))
             (replace chunk vector :start2 i :end2 end)
             (napa-fft:fft chunk :dst chunk :in-order nil)
             (napa-fft:ifft chunk
                            :dst chunk :in-order nil
                            :window filter)
             (replace destination chunk :start1 i :end2 end)
          finally (return destination))))

We can then directly filter all the high frequencies in *never*.

CL-USER> (emit-raw32-file "~/napa-fft3/example/never-prime.s32"
                          (filter-chunks *never* *jb-filter*))
"~/napa-fft3/example/never-prime.s32"

The filtering process loses a lot of volume. We can recover that by scaling the output so that its 2-norm is the same. There's also an annoying noise: that's an artefact of the way we cut our signal up and pretend each chunk is periodic. The latter problem is what the windowing support attempts to address.

Instead of filtering each chunk independently, we'll use a triangular window, and overlap the chunks so that each sample is processed exactly twice. The triangular window ensures that the two weights assigned to each sample adds to 1. windowed-fft takes care of applying the triangular window to the input, and a scaling factor is applied so that the energy in the output is half that in the input. The result of the thunks are then added together, with the same overlap as the input. filter-chunks becomes:

(defun filter-chunks (vector filter)
  (declare (type napa-fft:real-sample-array vector filter))
  (let* ((destination (make-array (length vector)
                                  :element-type 'napa-fft:complex-sample
                                  :initial-element (complex 0d0)))
         (chunk-size  (length filter))
         (half-size   (truncate chunk-size 2))
         (chunk       (make-array chunk-size
                                  :element-type 'napa-fft:complex-sample))
         (filter      (napa-fft:bit-reverse filter)))
    (declare (optimize speed))
    (loop for i below (length vector) by half-size
          for end = (min (length vector) (+ i chunk-size))
          do (fill chunk (complex 0d0))
             (loop for dst upfrom 0
                   for src from i below end
                   do (setf (aref chunk dst) (complex (aref vector src))))
             (let ((old-energy (energy chunk)))
               (napa-fft:windowed-fft chunk half-size
                                      chunk-size
                                      :window-fn 'napa-fft:triangle
                                      :dst chunk :in-order nil)
               (napa-fft:ifft chunk
                              :dst chunk :in-order nil
                              :window filter)
               (let* ((new-energy (energy chunk))
                      (scale      (* .5d0 (sqrt (/ old-energy
                                                   new-energy)))))
                 (declare (type double-float scale))
                 (loop for src upfrom 0
                     for dst from i below end
                     do (incf (aref destination dst)
                              (* scale (aref chunk src))))))
      finally (return destination))))

When I play that back, I only hear high quality percussions and little to no artefacts.

Multiplying integers or polynomials via a convolution

So far, we've been using point-wise multiplication in the frequency domain to filter frequencies out. We can also see it as a nice way to execute convolutions. We can use this to implement fast multiplication of polynomials or of integers, with the right encoding. However, please don't use it for bignum multiplications without checking the precision of the transforms.

Let's multiply 1005 by 1234. 1005 is 1*10^3 + 0*10^2 + 0*10^1 + 5*10^0, which we can encode, as a vector: #(1 0 0 5 0 0 0 0) (note the padding at the end), and similarly for 1234. Again, filtering is oblivious to any permutation (as long as the windowing vector is bit-reversed), so we can do everything out of order.

CL-USER> (napa-fft:fft #(1 0 0 5 0 0 0 0) :in-order nil)
#(#C(6.0d0 0.0d0) #C(-4.0d0 0.0d0) #C(1.0d0 5.0d0) #C(1.0d0 -5.0d0)
  #C(-2.5355339059327378d0 -3.5355339059327378d0)
  #C(4.535533905932738d0 3.5355339059327378d0)
  #C(4.535533905932738d0 -3.5355339059327378d0)
  #C(-2.5355339059327378d0 3.5355339059327378d0))
CL-USER> (napa-fft:fft #(1 2 3 4 0 0 0 0) :in-order nil)
#(#C(10.0d0 0.0d0) #C(-2.0d0 0.0d0) #C(-2.0d0 2.0d0) #C(-2.0d0 -2.0d0)
  #C(-0.41421356237309515d0 -7.242640687119286d0)
  #C(2.414213562373095d0 1.2426406871192857d0)
  #C(2.414213562373095d0 -1.2426406871192857d0)
  #C(-0.41421356237309515d0 7.242640687119286d0))
CL-USER> (napa-fft:ifft * :window ** :in-order nil)
#(#C(0.9999999999999982d0 0.0d0) #C(1.9999999999999991d0 0.0d0)
  #C(3.0d0 0.0d0) #C(9.0d0 0.0d0) #C(10.000000000000002d0 0.0d0)
  #C(15.0d0 0.0d0) #C(20.0d0 0.0d0) #C(-8.881784197001252d-16 0.0d0))

If we remove the imaginary portions (which are all 0) and round some numerical errors away, we find #(1 2 3 9 10 15 20 0), this time with only one element of padding; this value represents 1*10^6 + 2*10^5 + 3*10^4 + 9*10^3 + 10*10^2, etc. If we take care of the carries, we find 1240170, which is indeed 1005 * 1234.

Of course, we can also exploit the fact that the input and output are all reals to use rfft and rifft. We can do even better with %2rfft, which performs 2 real fft at the same time. However, if we do that, we have to use in-order transforms and perform the element-wise multiplication ourselves. It's a trade off, and even when we're only concerned with computation times, the right answer depends on a lot of variables.

;; the results are returned one after the other in a single
;; vector of complex doubles
CL-USER> (napa-fft:%2rfft '(1 0 0 5 0 0 0 0)
                          '(1 2 3 4 0 0 0 0))
#(#C(6.0d0 0.0d0) #C(-2.5355339059327378d0 -3.5355339059327378d0)
  #C(1.0d0 5.0d0) #C(4.535533905932738d0 -3.535533905932738d0)
  ...)
  
CL-USER> (let ((x (subseq * 0 8))
               (y (subseq * 8)))
           (napa-fft:rifft (map-into x #'* x y)))
#(0.9999999999999991d0 2.0d0 2.9999999999999964d0 9.0d0 10.0d0 15.0d0
  20.000000000000004d0 -8.881784197001252d-16)

Low-level Interface

These functions directly expose the runtime code generator to let you avoid all the argument-list parsing overhead in the regular interface, and hoist the lookups outside performance-critical code. All the generators are memoised in specials, but accesses are protected by mutexes (and are atomic on SBCL anyway), so there should not be any threading issue.

The low-level interface consists of the three following generators; they don't offer any functionality absent from the easy interface, but make it possible to dispatch once and subsequently call the right function directly.

The previous three generators actually depend on these memoised generators, which allow even lower-level accesses.

The functions returned by these generators perform virtually no error checking; make sure to use them correctly.

GET-FFT

Syntax: get-fft size &key forward scale in-order => fft-function.

Arguments and Values:

GET-FFT returns a function that computes the DFT of the first size elements of its single argument. That argument must be a complex-sample-array, and will be transformed in-place.

Example:

CL-USER> (let ((fft (napa-fft:get-fft 8))
               (data (make-array 8 :element-type 'napa-fft:complex-sample
                                   :initial-element (complex 1d0 0d0))))
           ;; data transformed in-place
           (funcall fft data))
#(#C(8.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
  #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0))

GET-WINDOWED-FFT

Syntax: get-windowed-fft size window-type &key forward scale in-order => fft-function

Arguments and Values:

GET-WINDOWED-FFT returns a function that computes the DFT of the first size elements of its first argument. Conceptually, this first argument is first multiplied element-wise by the second argument (the window); in practice, this is executed as part of the FFT.

For inverse FFTs, the multiplication happens after the bit-reversal; the window should thus itself be bit-reversed.

GET-REVERSE

Syntax: get-reverse n &optional eltype => reversal-function

Arguments and Values:

GET-REVERSE returns a function that perform an in-place bit-reversal of the first size elements of its single argument.

%ENSURE-FFT

Syntax: %ensure-fft direction scaling windowing n => fft-function

Arguments and Values:

%ENSURE-FFT is similar to GET-FFT or GET-WINDOWED-FFT, except that the start indices may be specified.

%ENSURE-TWIDDLES

Syntax: %ensure-twiddles n forwardp => twiddle-vector

Argument and Values:

%ENSURE-TWIDDLES computes and caches vectors that should be passed as the last argument of the function returned by %ENSURE-FFT. The structure of the vectors is such that a vector appropriate for a transform of size n is also appropriate for all smaller sizes (with the same direction).

%ENSURE-REVERSE

Syntax %ensure-reverse n &optional eltype => reversal-function

Argument and Values:

%ENSURE-REVERSE is exactly like GET-REVERSE, but allows the user to specify the starting index of the vector to bit-reverse.

Implementation

Napa-FFT3 is based on a split-radix, out-of-order and in-place variant of the Cooley-Tukey FFT algorithm. Split-radix is relatively simple, and achieve operation counts very close (within a couple percents) to the minimum known so far. Doing it out of order simplifies the transform code a lot; this way, all the accesses are naturally in-place and follow a streaming order, at each level of the recursion. Better: by executing the recursion depth-first rather than breadth-first, the code exploits caches implicitly. Finally, an in-place transform can hope to fit nearly twice as large inputs in cache as an out-of-place one, as there is no auxiliary output vector. All in all, it looks like a good choice of algorithm: close enough to the theoretical optimum, interesting performance properties, and not too complex to implement.

Many operations are as easily expressed on bit-reversed as on natural-order frequency-domain values (e.g. convolutions, or filtering noise out). That's not always the case, unfortunately, so Napa-FFT also implements a bit-reversal pass.

In the past, this was often slow enough to make it vastly preferable to instead implement an in-order (autosorting) FFT: the slow, bandwidth-bound, bit-reversal is merged with the more arithmetic-heavy FFT, hopefully resulting in faster code than executing each serially. However, as [Karp] points out, this seems to be better explained by bad code than anything else. [Karter and Gatlin] build on that and describe an algorithm designed to exploit memory caches, ensuring at most two misses per cache line of data; this is enough to obtain much better performance (or comparable) than all the algorithms reviewed in [Karp] across a range of nearly-contemporary machines. In a later paper, [Zhang and Zhang], note that we can exploit the high associativity in certain caches to simplify the code a lot, or improve on its performance. Their algorithms are somewhat complicated by explicit blocking loops; a clever recursion suffices to obtain access patterns appropriate for nearly all block sizes.

Split-radix FFT

The split-radix algorithm has a very short recursive definition; practically however, we want larger base cases than the strict minimum. Rather than depending on hand-written specialised base cases, Napa-FFT3 includes a specialised compiler that turns the execution trace for a given FFT into straight-line code. This way, we maintain the near-optimal operation count, especially since the code to multiply by twiddle factors can be optimised for "nice" constants (e.g. 1, i or sqrt(i)). The specialised compiler takes care of spilling values to the data vector according to Belady's algorithm. This will tend to perform a lot better than general-purpose spilling logic (e.g. SBCL's coloring-based algorithm), and spilled values are stored at correctly-aligned addresses, following a cache-friendly layout.

This, along with specialised recursive steps for each size, gives us high-performance out-of-order transforms. Much of the complexity in FFTs comes from ensuring the data are in natural order; it's not surprising that simple code can achieve runtimes comparable or lower than sophisticated code like FFTW once that constraint is relaxed.

The base cases are nevertheless incredibly naive, compared to FFTW's codelets. For tiny transforms, Napa-FFT is clearly not in the same league; however, as cache effects gain importance, the higher-level design choices pay off, and out-of-order Napa-FFT closes the gap with FFTW. In fact, it is even slightly faster for very large transforms.

Bit reversal

More surprising might be the fact that quick bit-reversals are now so easy to design. Much of the runtime in Napa-FFT2 was caused by the transposition steps. At first sight, a bit-reversal is even more complicated. However, bit-reversals have the nice property that they only consist of swaps: they can be easily be executed in-place, by swapping each element with its destination. In contrast, this is only true for transpose of square matrices (FFT sizes that are even powers of two).

Historically, on cache-ful computers, the issue with bit-reversal has been one of aliasing in low-associativity caches: the swap pattern involves addresses that tend to be mapped to the same cache lines. The workarounds involve some sort of software buffering, either in registers or in an auxiliary array, to supplement the caches.

Nowadays, however, computer architects have more transistors than they know what to do with, so caches are large and have high associativity (at least 4-way at the L2 or L3 level on both AMD and Intel chips). Since we're mostly conerned with bit-reversing complex-sample-vectors, each element is a pair of double-floats, and only 4 fit in each cache line. In this case, as [Zhang and Zhang 99] point out, the associativity is high enough not to necessitate any software buffering!

The novel part seems to be the traversal order. [Zhang and Zhang 99] point out that blocking helps with locality, and a few older work [Elster, Rutkowska] have described how bit-reversal swaps could be generated recursively. The blocking described in [Zhang and Zhang 99] is very much cache-aware, and must be explicitly structured to take advantage of cache levels and TLBs. It seems that all the recursively-generated swaps generate indices to swap from the outside in; that is, the leaf of the recursion have all the bits fixed except for the middle ones. If we wish to enhance locality, we should fix the middle bit first, and, at the leaves, have the outermost (i.e. most significant, but also least significant) bits vary. This way, we implicitly get blocking for any cache line size (given sufficient associativity), but also for fully-associative TLBs.

Another way to see this is that each swap tends to be between vastly different indices (bit reversal is bad for locality). One classic way to deal with this is to sort the swaps in Z-order, by interleaving bits from each swapped index. Unfortunately, with bit reversal, this is equivalent to recursing from the outside. Instead, we can sort the least significant half of the indices in Z-order, and that will make the outermost bit vary between adjacent swaps.

Obviously, determining this ordering at runtime is a lot of work. Instead, specialised leaf routines that handle changing, e.g., the top and bottom -most three bits (in the right traversal order), are called with the middle bits found in a pre-sorted vector.

On my workstation, this results in .3 cache miss/element (for complex double floats), which is only a bit more than the compulsory .25 miss/element. Surprisingly, while there are a lot ofTLB misses (at the first level, I suppose), eliminating them by switching to huge pages doesn't really improve runtimes. I'm currently thinking that's because the traversal order is actually tuned for the last level TLB, which is fully-associative. In the end, the net effect is that bit reversal of large vectors hits around 60 % of my workstation's out-of-cache streaming bandwidth (as measured by STREAM's copy loop). It's not instantaneous, but not an insurmountable handicap either.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 napa-fft3

Author

Paul Khuong

License

3-clause BSD

Description

Fast Fourier Transforms via generated split-radix

Version

0.0.1

Source

napa-fft3.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 napa-fft3.asd

Location

napa-fft3.asd

Systems

napa-fft3 (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 napa-fft3/package.lisp

Parent

napa-fft3 (system)

Location

package.lisp

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 napa-fft3/support.lisp

Dependency

package.lisp (file)

Parent

napa-fft3 (system)

Location

support.lisp

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.4 napa-fft3/bblock.lisp

Dependency

support.lisp (file)

Parent

napa-fft3 (system)

Location

bblock.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.5 napa-fft3/gen-support.lisp

Dependency

bblock.lisp (file)

Parent

napa-fft3 (system)

Location

gen-support.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.6 napa-fft3/forward.lisp

Dependency

gen-support.lisp (file)

Parent

napa-fft3 (system)

Location

forward.lisp

Exported Definitions

gen-dif (function)

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.7 napa-fft3/inverse.lisp

Dependency

forward.lisp (file)

Parent

napa-fft3 (system)

Location

inverse.lisp

Exported Definitions

gen-dit (function)

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.8 napa-fft3/bit-reversal.lisp

Dependency

inverse.lisp (file)

Parent

napa-fft3 (system)

Location

bit-reversal.lisp

Exported Definitions

gen-bit-reversal (function)

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.9 napa-fft3/interface.lisp

Dependency

bit-reversal.lisp (file)

Parent

napa-fft3 (system)

Location

interface.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.10 napa-fft3/easy-interface.lisp

Dependency

interface.lisp (file)

Parent

napa-fft3 (system)

Location

easy-interface.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.11 napa-fft3/windowing.lisp

Dependency

easy-interface.lisp (file)

Parent

napa-fft3 (system)

Location

windowing.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.12 napa-fft3/real.lisp

Dependency

windowing.lisp (file)

Parent

napa-fft3 (system)

Location

real.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.13 napa-fft3/test-support.lisp

Dependency

real.lisp (file)

Parent

napa-fft3 (system)

Location

test-support.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.14 napa-fft3/tests.lisp

Dependency

test-support.lisp (file)

Parent

napa-fft3 (system)

Location

tests.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.15 napa-fft3/ergun-test.lisp

Dependency

tests.lisp (file)

Parent

napa-fft3 (system)

Location

ergun-test.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 napa-fft.tests

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

4.2 napa-fft.impl

Source

package.lisp (file)

Use List
Internal Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

4.3 napa-fft.gen

Source

package.lisp (file)

Use List
Used By List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

4.4 napa-fft.support

Source

package.lisp (file)

Use List
Used By List
Exported Definitions

Previous: , Up: Packages   [Contents][Index]

4.5 napa-fft

Source

package.lisp (file)

Used By List
Exported Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Constants

Constant: +twiddle-offset+
Package

napa-fft.support

Source

support.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Special variables

Special Variable: *fancy-in-order*
Package

napa-fft.tests

Source

tests.lisp (file)

Special Variable: *optimization-policy*
Package

napa-fft.support

Source

support.lisp (file)

Special Variable: *rfft-twiddles*
Package

napa-fft

Source

real.lisp (file)

Special Variable: *rifft-twiddles*
Package

napa-fft

Source

real.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Functions

Function: %2rfft V1 V2 &key DST SIZE SCALE
Package

napa-fft

Source

real.lisp (file)

Function: %ensure-fft DIRECTION SCALING WINDOWING N
Package

napa-fft

Source

interface.lisp (file)

Function: %ensure-reverse N &optional ELTYPE
Package

napa-fft

Source

interface.lisp (file)

Function: %ensure-twiddles N FORWARDP
Package

napa-fft

Source

interface.lisp (file)

Function: bartlett I N
Package

napa-fft

Source

windowing.lisp (file)

Function: bit-reverse VEC &optional DST SIZE
Package

napa-fft

Source

easy-interface.lisp (file)

Function: bit-reverse-integer X WIDTH
Package

napa-fft.support

Source

support.lisp (file)

Function: blackman I N
Package

napa-fft

Source

windowing.lisp (file)

Function: blackman* ALPHA I N
Package

napa-fft

Source

windowing.lisp (file)

Function: blackman-harris I N
Package

napa-fft

Source

windowing.lisp (file)

Function: complex-samplify VEC &optional SIZE
Package

napa-fft.support

Source

support.lisp (file)

Function: cosine-series I N A0 A1 A2 A3
Package

napa-fft

Source

windowing.lisp (file)

Function: fft VEC &key DST SIZE IN-ORDER SCALE WINDOW
Package

napa-fft

Source

easy-interface.lisp (file)

Function: forward-test SIZE &key PROB MAKER (BIT-REVERSED *BIT-REVERSED*)
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: gauss* SIGMA I N
Package

napa-fft

Source

windowing.lisp (file)

Function: gaussian SIGMA
Package

napa-fft

Source

windowing.lisp (file)

Function: gaussian*bartlett^x SIGMA TRIANGLE-EXPONENT
Package

napa-fft

Source

windowing.lisp (file)

Function: gen-bit-reversal N
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: gen-dif N &key SCALE WINDOW
Package

napa-fft.gen

Source

forward.lisp (file)

Function: gen-dit N &key SCALE WINDOW
Package

napa-fft.gen

Source

inverse.lisp (file)

Function: get-fancy-fwd N SCALE
Package

napa-fft.tests

Source

tests.lisp (file)

Function: get-fancy-inv N SCALE
Package

napa-fft.tests

Source

tests.lisp (file)

Function: get-fancy-windowed-fwd N WINDOW
Package

napa-fft.tests

Source

tests.lisp (file)

Function: get-fancy-windowed-inv N WINDOW
Package

napa-fft.tests

Source

tests.lisp (file)

Function: get-fft SIZE &key FORWARD SCALE IN-ORDER
Package

napa-fft

Source

interface.lisp (file)

Function: get-reverse N &optional ELTYPE
Package

napa-fft

Source

interface.lisp (file)

Function: get-windowed-fft SIZE WINDOW-TYPE &key FORWARD SCALE IN-ORDER
Package

napa-fft

Source

interface.lisp (file)

Function: hann I N
Package

napa-fft

Source

windowing.lisp (file)

Function: ifft VEC &key DST SIZE IN-ORDER SCALE WINDOW
Package

napa-fft

Source

easy-interface.lisp (file)

Function: lb N
Package

napa-fft.support

Source

support.lisp (file)

Function: make-scaled-fwd N SCALE
Package

napa-fft.tests

Source

tests.lisp (file)

Function: make-scaled-inv N SCALE
Package

napa-fft.tests

Source

tests.lisp (file)

Function: make-twiddle N &optional DIR
Package

napa-fft.support

Source

support.lisp (file)

Function: make-windowed-fwd N WINDOW
Package

napa-fft.tests

Source

tests.lisp (file)

Function: make-windowed-inv N WINDOW
Package

napa-fft.tests

Source

tests.lisp (file)

Function: power-of-two-p X
Package

napa-fft.support

Source

support.lisp (file)

Function: real-samplify VEC &optional SIZE
Package

napa-fft.support

Source

support.lisp (file)

Function: rectangular I N
Package

napa-fft

Source

windowing.lisp (file)

Function: rfft VEC &key DST SIZE SCALE
Package

napa-fft

Source

real.lisp (file)

Function: rifft VEC &key DST SIZE SCALE
Package

napa-fft

Source

real.lisp (file)

Function: run-forward-tests MAX-SIZE &optional FANCY *FANCY-IN-ORDER*
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: run-offsets MAX
Package

napa-fft.tests

Source

tests.lisp (file)

Function: run-pairs MAX &key FWD INV
Package

napa-fft.tests

Source

tests.lisp (file)

Function: run-windows MAX &key FWD-MAKER INV-MAKER &aux WINDOW
Package

napa-fft.tests

Source

tests.lisp (file)

Function: test-offset N
Package

napa-fft.tests

Source

tests.lisp (file)

Function: test-pairs N &key FWD-SCALE FWD INV
Package

napa-fft.tests

Source

tests.lisp (file)

Function: test-window N &key WINDOW WINDOW-FWD WINDOW-INV FWD INV
Package

napa-fft.tests

Source

tests.lisp (file)

Function: triangle I N
Package

napa-fft

Source

windowing.lisp (file)

Function: window-vector FUNCTION N &key BIT-REVERSE
Package

napa-fft

Source

windowing.lisp (file)

Function: windowed-fft SIGNAL-VECTOR CENTER LENGTH &key WINDOW-FN DST IN-ORDER SCALE

Perform an FFT on the window of a signal, centered on the given index, multiplied by a window generated by the chosen window function

Package

napa-fft

Source

windowing.lisp (file)

Function: windowed-ifft SIGNAL-VECTOR &key WINDOW-FN SIZE DST IN-ORDER SCALE
Package

napa-fft

Source

windowing.lisp (file)

Function: windowed-rfft SIGNAL-VECTOR CENTER LENGTH &key WINDOW-FN DST SCALE
Package

napa-fft

Source

real.lisp (file)

Function: windowed-rifft VEC &key WINDOW-FN DST SIZE SCALE
Package

napa-fft

Source

real.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.4 Types

Type: complex-sample ()
Package

napa-fft

Source

support.lisp (file)

Type: complex-sample-array &optional SIZE
Package

napa-fft

Source

support.lisp (file)

Type: direction ()
Package

napa-fft

Source

interface.lisp (file)

Type: half-index ()
Package

napa-fft.support

Source

support.lisp (file)

Type: half-size ()
Package

napa-fft.support

Source

support.lisp (file)

Type: index ()
Package

napa-fft.support

Source

support.lisp (file)

Type: real-sample ()
Package

napa-fft

Source

support.lisp (file)

Type: real-sample-array &optional SIZE
Package

napa-fft

Source

support.lisp (file)

Type: scaling ()
Package

napa-fft

Source

interface.lisp (file)

Type: size ()
Package

napa-fft.support

Source

support.lisp (file)

Type: windowing ()
Package

napa-fft

Source

interface.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: *bit-reverse-lock*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *bit-reversed*
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Special Variable: *bit-reverses*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *default-abs-tol*
Package

napa-fft.tests

Source

test-support.lisp (file)

Special Variable: *double-bit-reverses*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *fft-lock*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *ffts*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *forward-twiddle*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *fwd-base-case*
Package

napa-fft.gen

Source

forward.lisp (file)

Special Variable: *inv-base-case*
Package

napa-fft.gen

Source

inverse.lisp (file)

Special Variable: *inverse-twiddle*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *max-small-bit-reverse*
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Special Variable: *ops*
Package

napa-fft.gen

Source

bblock.lisp (file)

Special Variable: *outer-width*
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Special Variable: *swap-block-size*
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Special Variable: *twiddle-lock*
Package

napa-fft.impl

Source

interface.lisp (file)

Special Variable: *vector*
Package

napa-fft.gen

Source

bblock.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Symbol macros

Symbol Macro: %blocking-factor%
Package

napa-fft.gen

Source

gen-support.lisp (file)

Expansion

4

Symbol Macro: %unroll-count%
Package

napa-fft.gen

Source

gen-support.lisp (file)

Expansion

8


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Macros

Macro: bblock (&rest BINDINGS) &body BODY
Package

napa-fft.gen

Source

bblock.lisp (file)

Macro: define-inline-function NAME (&rest ARGS) &body BODY
Package

napa-fft.gen

Source

gen-support.lisp (file)

Macro: for (COUNT &rest BINDINGS) &body BODY
Package

napa-fft.gen

Source

gen-support.lisp (file)

Macro: op (&rest TYPES) BODY &rest ARGS
Package

napa-fft.gen

Source

bblock.lisp (file)

Macro: with-scale (SCALE) &body BODY
Package

napa-fft.impl

Source

real.lisp (file)

Macro: with-vector (N &key TYPE MAXLIVE) &body BODY
Package

napa-fft.gen

Source

bblock.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Compiler macros

Compiler Macro: %scale &rest ARG-FORMS
Package

napa-fft.gen

Source

gen-support.lisp (file)

Compiler Macro: %window &rest ARG-FORMS
Package

napa-fft.gen

Source

gen-support.lisp (file)

Compiler Macro: mul+/-sqrt+i &rest ARG-FORMS
Package

napa-fft.gen

Source

gen-support.lisp (file)

Compiler Macro: mul+/-sqrt-i &rest ARG-FORMS
Package

napa-fft.gen

Source

gen-support.lisp (file)

Compiler Macro: mul+i &rest ARG-FORMS
Package

napa-fft.gen

Source

gen-support.lisp (file)

Compiler Macro: mul-i &rest ARG-FORMS
Package

napa-fft.gen

Source

gen-support.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.5 Functions

Function: %%op RESULT-TYPES BODY ARGS
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: %bit-reverse-complex VEC DST SIZE
Package

napa-fft.impl

Source

easy-interface.lisp (file)

Function: %bit-reverse-double VEC DST SIZE
Package

napa-fft.impl

Source

easy-interface.lisp (file)

Function: %dif VEC START N TWIDDLE
Package

napa-fft.gen

Source

forward.lisp (file)

Function: %dit VEC START N TWIDDLE
Package

napa-fft.gen

Source

inverse.lisp (file)

Function: %forward-test-1 SIZE REPEAT FUNCTION
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: %forward-test-2 SIZE REPEAT FUNCTION
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: %forward-test-3 SIZE OUTER-REPEAT INNER-REPEAT FUNCTION
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: %gen-flat-dif N SCALE WINDOW
Package

napa-fft.gen

Source

forward.lisp (file)

Function: %gen-flat-dit N SCALE WINDOW
Package

napa-fft.gen

Source

inverse.lisp (file)

Function: %get-radix-2-twiddle N DIRECTION
Package

napa-fft.impl

Source

real.lisp (file)

Function: %make-op &key (BODY BODY) (ARGS ARGS) (DEPS DEPS) (WRITES WRITES)
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: %make-vval &key (NAME NAME) (TYPE TYPE) (SPILLS SPILLS) (DESTS DESTS) (STATUS STATUS) (READS READS)
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: %op RESULT-TYPES BODY ARGS
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: %scale X SCALE
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: %window X WINDOW I
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: @ I
Function: (setf @) VALUE I
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: annotate-uses OPS
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: apply-window-inv VEC WINDOW
Package

napa-fft.tests

Source

tests.lisp (file)

Function: butterfly I J
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: check-eqv A B &optional NAME
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: clip-in-window X START END
Package

napa-fft.impl

Source

windowing.lisp (file)

Function: copy-load-op INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: copy-op INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: copy-or-replace SRC DST
Package

napa-fft.impl

Source

easy-interface.lisp (file)

Function: copy-store-op INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: copy-vval INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: delta X Y
Package

napa-fft.tests

Source

tests.lisp (file)

Function: emit-bblock BINDINGS BODY
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: emit-code OPS BODY
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: emit-small-bit-reverse N &aux WIDTH
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: emit-swaps PAIRS BUILDER1 &optional BUILDER2
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: emit-swaps-same PAIRS BUILDER
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: emit-unrolled-for COUNT BINDINGS BODY
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: extract-centered-window VECTOR CENTER SIZE &optional ELEMENT-TYPE

Extract a subsequence of SIZE from VECTOR, centered on CENTER and padding with zeros beyond the edges of the vector.

Package

napa-fft.impl

Source

windowing.lisp (file)

Function: extract-centered-window-into VECTOR CENTER SIZE DESTINATION

Extract a subsequence of SIZE from VECTOR, centered on OFFSET and padding with zeros beyond the boundaries of the vector, storing it to DESTINATION.

Package

napa-fft.impl

Source

windowing.lisp (file)

Function: extract-window VECTOR START LENGTH &optional ELEMENT-TYPE
Package

napa-fft.impl

Source

windowing.lisp (file)

Function: extract-window-into VECTOR START LENGTH DESTINATION

Copy an extent of VECTOR to DESTINATION. Outside of its legal array indices, VECTOR is considered to be zero.

Package

napa-fft.impl

Source

windowing.lisp (file)

Function: fft-swizzled-reals VEC SCALE
Package

napa-fft.impl

Source

real.lisp (file)

Function: find-index DIRECTION SCALING WINDOWING
Package

napa-fft.impl

Source

interface.lisp (file)

Function: gen-flat-dif N &key SCALE WINDOW
Package

napa-fft.gen

Source

forward.lisp (file)

Function: gen-flat-dit N &key SCALE WINDOW
Package

napa-fft.gen

Source

inverse.lisp (file)

Function: generate-fft DIRECTION SCALING WINDOWING N
Package

napa-fft.impl

Source

interface.lisp (file)

Function: generate-large-reversal OUTER INNER
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: generate-leaf-reverse OUTER INNER
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: generate-leaf-reverse-swap OUTER INNER
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: generate-outward-seq SEED MOST LEAST
Package

napa-fft.gen

Source

bit-reversal.lisp (file)

Function: get-radix-2-twiddle N DIRECTION
Package

napa-fft.impl

Source

real.lisp (file)

Function: get-window-type WINDOW
Package

napa-fft.impl

Source

easy-interface.lisp (file)

Function: impulse I N
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: initialize-vector TYPE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: insert-spill OPS INITIAL-VECTOR FINAL-VECTOR MAXLIVE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: iota N
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: load-op-idx INSTANCE
Function: (setf load-op-idx) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: load-op-p OBJECT
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: load-op-var INSTANCE
Function: (setf load-op-var) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: m* X Y &optional DST
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: m+ X Y &optional DST
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: m- X Y &optional DST
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: m= X Y &optional TOL
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: make-dummy-window N
Package

napa-fft.tests

Source

tests.lisp (file)

Function: make-forward-fun SIZE
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: make-load-op &key (VAR VAR) (IDX IDX)
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: make-store-op &key (VAR VAR) (IDX IDX)
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: make-vector N
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: mul+/-sqrt+i X SCALE
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: mul+/-sqrt-i X SCALE
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: mul+i X
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: mul-i X
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: mul-root X ROOT &optional DEFAULT
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: note-writes ()
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: op-args INSTANCE
Function: (setf op-args) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: op-body INSTANCE
Function: (setf op-body) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: op-deps INSTANCE
Function: (setf op-deps) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: op-p OBJECT
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: op-writes INSTANCE
Function: (setf op-writes) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: random-vector N &optional DST
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: rol VEC &optional DST
Package

napa-fft.tests

Source

ergun-test.lisp (file)

Function: rotate I K ROOT
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: scale I SCALE WINDOW &optional WINDOW-I
Package

napa-fft.gen

Source

gen-support.lisp (file)

Function: slow-bit-reverse ARRAY
Package

napa-fft.tests

Source

test-support.lisp (file)

Function: store-op-idx INSTANCE
Function: (setf store-op-idx) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: store-op-p OBJECT
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: store-op-var INSTANCE
Function: (setf store-op-var) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: swap X
Package

napa-fft.impl

Source

real.lisp (file)

Function: vval TYPE &key STEM
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-dests INSTANCE
Function: (setf vval-dests) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-name INSTANCE
Function: (setf vval-name) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-p OBJECT
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-reads INSTANCE
Function: (setf vval-reads) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-spills INSTANCE
Function: (setf vval-spills) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-status INSTANCE
Function: (setf vval-status) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: vval-type INSTANCE
Function: (setf vval-type) VALUE INSTANCE
Package

napa-fft.gen

Source

bblock.lisp (file)

Function: z-order-words PAIRS &optional MASK
Package

napa-fft.gen

Source

bit-reversal.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.6 Structures

Structure: load-op ()
Package

napa-fft.gen

Source

bblock.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: var
Readers

load-op-var (function)

Writers

(setf load-op-var) (function)

Slot: idx
Readers

load-op-idx (function)

Writers

(setf load-op-idx) (function)

Structure: op ()
Package

napa-fft.gen

Source

bblock.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: body
Readers

op-body (function)

Writers

(setf op-body) (function)

Slot: args
Readers

op-args (function)

Writers

(setf op-args) (function)

Slot: deps
Readers

op-deps (function)

Writers

(setf op-deps) (function)

Slot: writes
Readers

op-writes (function)

Writers

(setf op-writes) (function)

Structure: store-op ()
Package

napa-fft.gen

Source

bblock.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: var
Readers

store-op-var (function)

Writers

(setf store-op-var) (function)

Slot: idx
Readers

store-op-idx (function)

Writers

(setf store-op-idx) (function)

Structure: vval ()
Package

napa-fft.gen

Source

bblock.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: name
Readers

vval-name (function)

Writers

(setf vval-name) (function)

Slot: type
Readers

vval-type (function)

Writers

(setf vval-type) (function)

Slot: spills
Readers

vval-spills (function)

Writers

(setf vval-spills) (function)

Slot: dests
Readers

vval-dests (function)

Writers

(setf vval-dests) (function)

Slot: status
Readers

vval-status (function)

Writers

(setf vval-status) (function)

Slot: reads
Readers

vval-reads (function)

Writers

(setf vval-reads) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   N  
Index Entry  Section

F
File, Lisp, napa-fft3.asd: The napa-fft3<dot>asd file
File, Lisp, napa-fft3/bblock.lisp: The napa-fft3/bblock<dot>lisp file
File, Lisp, napa-fft3/bit-reversal.lisp: The napa-fft3/bit-reversal<dot>lisp file
File, Lisp, napa-fft3/easy-interface.lisp: The napa-fft3/easy-interface<dot>lisp file
File, Lisp, napa-fft3/ergun-test.lisp: The napa-fft3/ergun-test<dot>lisp file
File, Lisp, napa-fft3/forward.lisp: The napa-fft3/forward<dot>lisp file
File, Lisp, napa-fft3/gen-support.lisp: The napa-fft3/gen-support<dot>lisp file
File, Lisp, napa-fft3/interface.lisp: The napa-fft3/interface<dot>lisp file
File, Lisp, napa-fft3/inverse.lisp: The napa-fft3/inverse<dot>lisp file
File, Lisp, napa-fft3/package.lisp: The napa-fft3/package<dot>lisp file
File, Lisp, napa-fft3/real.lisp: The napa-fft3/real<dot>lisp file
File, Lisp, napa-fft3/support.lisp: The napa-fft3/support<dot>lisp file
File, Lisp, napa-fft3/test-support.lisp: The napa-fft3/test-support<dot>lisp file
File, Lisp, napa-fft3/tests.lisp: The napa-fft3/tests<dot>lisp file
File, Lisp, napa-fft3/windowing.lisp: The napa-fft3/windowing<dot>lisp file

L
Lisp File, napa-fft3.asd: The napa-fft3<dot>asd file
Lisp File, napa-fft3/bblock.lisp: The napa-fft3/bblock<dot>lisp file
Lisp File, napa-fft3/bit-reversal.lisp: The napa-fft3/bit-reversal<dot>lisp file
Lisp File, napa-fft3/easy-interface.lisp: The napa-fft3/easy-interface<dot>lisp file
Lisp File, napa-fft3/ergun-test.lisp: The napa-fft3/ergun-test<dot>lisp file
Lisp File, napa-fft3/forward.lisp: The napa-fft3/forward<dot>lisp file
Lisp File, napa-fft3/gen-support.lisp: The napa-fft3/gen-support<dot>lisp file
Lisp File, napa-fft3/interface.lisp: The napa-fft3/interface<dot>lisp file
Lisp File, napa-fft3/inverse.lisp: The napa-fft3/inverse<dot>lisp file
Lisp File, napa-fft3/package.lisp: The napa-fft3/package<dot>lisp file
Lisp File, napa-fft3/real.lisp: The napa-fft3/real<dot>lisp file
Lisp File, napa-fft3/support.lisp: The napa-fft3/support<dot>lisp file
Lisp File, napa-fft3/test-support.lisp: The napa-fft3/test-support<dot>lisp file
Lisp File, napa-fft3/tests.lisp: The napa-fft3/tests<dot>lisp file
Lisp File, napa-fft3/windowing.lisp: The napa-fft3/windowing<dot>lisp file

N
napa-fft3.asd: The napa-fft3<dot>asd file
napa-fft3/bblock.lisp: The napa-fft3/bblock<dot>lisp file
napa-fft3/bit-reversal.lisp: The napa-fft3/bit-reversal<dot>lisp file
napa-fft3/easy-interface.lisp: The napa-fft3/easy-interface<dot>lisp file
napa-fft3/ergun-test.lisp: The napa-fft3/ergun-test<dot>lisp file
napa-fft3/forward.lisp: The napa-fft3/forward<dot>lisp file
napa-fft3/gen-support.lisp: The napa-fft3/gen-support<dot>lisp file
napa-fft3/interface.lisp: The napa-fft3/interface<dot>lisp file
napa-fft3/inverse.lisp: The napa-fft3/inverse<dot>lisp file
napa-fft3/package.lisp: The napa-fft3/package<dot>lisp file
napa-fft3/real.lisp: The napa-fft3/real<dot>lisp file
napa-fft3/support.lisp: The napa-fft3/support<dot>lisp file
napa-fft3/test-support.lisp: The napa-fft3/test-support<dot>lisp file
napa-fft3/tests.lisp: The napa-fft3/tests<dot>lisp file
napa-fft3/windowing.lisp: The napa-fft3/windowing<dot>lisp file

Jump to:   F   L   N  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (   @  
A   B   C   D   E   F   G   H   I   L   M   N   O   P   R   S   T   V   W   Z  
Index Entry  Section

%
%%op: Internal functions
%2rfft: Exported functions
%bit-reverse-complex: Internal functions
%bit-reverse-double: Internal functions
%dif: Internal functions
%dit: Internal functions
%ensure-fft: Exported functions
%ensure-reverse: Exported functions
%ensure-twiddles: Exported functions
%forward-test-1: Internal functions
%forward-test-2: Internal functions
%forward-test-3: Internal functions
%gen-flat-dif: Internal functions
%gen-flat-dit: Internal functions
%get-radix-2-twiddle: Internal functions
%make-op: Internal functions
%make-vval: Internal functions
%op: Internal functions
%scale: Internal compiler macros
%scale: Internal functions
%window: Internal compiler macros
%window: Internal functions

(
(setf @): Internal functions
(setf load-op-idx): Internal functions
(setf load-op-var): Internal functions
(setf op-args): Internal functions
(setf op-body): Internal functions
(setf op-deps): Internal functions
(setf op-writes): Internal functions
(setf store-op-idx): Internal functions
(setf store-op-var): Internal functions
(setf vval-dests): Internal functions
(setf vval-name): Internal functions
(setf vval-reads): Internal functions
(setf vval-spills): Internal functions
(setf vval-status): Internal functions
(setf vval-type): Internal functions

@
@: Internal functions

A
annotate-uses: Internal functions
apply-window-inv: Internal functions

B
bartlett: Exported functions
bblock: Internal macros
bit-reverse: Exported functions
bit-reverse-integer: Exported functions
blackman: Exported functions
blackman*: Exported functions
blackman-harris: Exported functions
butterfly: Internal functions

C
check-eqv: Internal functions
clip-in-window: Internal functions
Compiler Macro, %scale: Internal compiler macros
Compiler Macro, %window: Internal compiler macros
Compiler Macro, mul+/-sqrt+i: Internal compiler macros
Compiler Macro, mul+/-sqrt-i: Internal compiler macros
Compiler Macro, mul+i: Internal compiler macros
Compiler Macro, mul-i: Internal compiler macros
complex-samplify: Exported functions
copy-load-op: Internal functions
copy-op: Internal functions
copy-or-replace: Internal functions
copy-store-op: Internal functions
copy-vval: Internal functions
cosine-series: Exported functions

D
define-inline-function: Internal macros
delta: Internal functions

E
emit-bblock: Internal functions
emit-code: Internal functions
emit-small-bit-reverse: Internal functions
emit-swaps: Internal functions
emit-swaps-same: Internal functions
emit-unrolled-for: Internal functions
extract-centered-window: Internal functions
extract-centered-window-into: Internal functions
extract-window: Internal functions
extract-window-into: Internal functions

F
fft: Exported functions
fft-swizzled-reals: Internal functions
find-index: Internal functions
for: Internal macros
forward-test: Exported functions
Function, %%op: Internal functions
Function, %2rfft: Exported functions
Function, %bit-reverse-complex: Internal functions
Function, %bit-reverse-double: Internal functions
Function, %dif: Internal functions
Function, %dit: Internal functions
Function, %ensure-fft: Exported functions
Function, %ensure-reverse: Exported functions
Function, %ensure-twiddles: Exported functions
Function, %forward-test-1: Internal functions
Function, %forward-test-2: Internal functions
Function, %forward-test-3: Internal functions
Function, %gen-flat-dif: Internal functions
Function, %gen-flat-dit: Internal functions
Function, %get-radix-2-twiddle: Internal functions
Function, %make-op: Internal functions
Function, %make-vval: Internal functions
Function, %op: Internal functions
Function, %scale: Internal functions
Function, %window: Internal functions
Function, (setf @): Internal functions
Function, (setf load-op-idx): Internal functions
Function, (setf load-op-var): Internal functions
Function, (setf op-args): Internal functions
Function, (setf op-body): Internal functions
Function, (setf op-deps): Internal functions
Function, (setf op-writes): Internal functions
Function, (setf store-op-idx): Internal functions
Function, (setf store-op-var): Internal functions
Function, (setf vval-dests): Internal functions
Function, (setf vval-name): Internal functions
Function, (setf vval-reads): Internal functions
Function, (setf vval-spills): Internal functions
Function, (setf vval-status): Internal functions
Function, (setf vval-type): Internal functions
Function, @: Internal functions
Function, annotate-uses: Internal functions
Function, apply-window-inv: Internal functions
Function, bartlett: Exported functions
Function, bit-reverse: Exported functions
Function, bit-reverse-integer: Exported functions
Function, blackman: Exported functions
Function, blackman*: Exported functions
Function, blackman-harris: Exported functions
Function, butterfly: Internal functions
Function, check-eqv: Internal functions
Function, clip-in-window: Internal functions
Function, complex-samplify: Exported functions
Function, copy-load-op: Internal functions
Function, copy-op: Internal functions
Function, copy-or-replace: Internal functions
Function, copy-store-op: Internal functions
Function, copy-vval: Internal functions
Function, cosine-series: Exported functions
Function, delta: Internal functions
Function, emit-bblock: Internal functions
Function, emit-code: Internal functions
Function, emit-small-bit-reverse: Internal functions
Function, emit-swaps: Internal functions
Function, emit-swaps-same: Internal functions
Function, emit-unrolled-for: Internal functions
Function, extract-centered-window: Internal functions
Function, extract-centered-window-into: Internal functions
Function, extract-window: Internal functions
Function, extract-window-into: Internal functions
Function, fft: Exported functions
Function, fft-swizzled-reals: Internal functions
Function, find-index: Internal functions
Function, forward-test: Exported functions
Function, gauss*: Exported functions
Function, gaussian: Exported functions
Function, gaussian*bartlett^x: Exported functions
Function, gen-bit-reversal: Exported functions
Function, gen-dif: Exported functions
Function, gen-dit: Exported functions
Function, gen-flat-dif: Internal functions
Function, gen-flat-dit: Internal functions
Function, generate-fft: Internal functions
Function, generate-large-reversal: Internal functions
Function, generate-leaf-reverse: Internal functions
Function, generate-leaf-reverse-swap: Internal functions
Function, generate-outward-seq: Internal functions
Function, get-fancy-fwd: Exported functions
Function, get-fancy-inv: Exported functions
Function, get-fancy-windowed-fwd: Exported functions
Function, get-fancy-windowed-inv: Exported functions
Function, get-fft: Exported functions
Function, get-radix-2-twiddle: Internal functions
Function, get-reverse: Exported functions
Function, get-window-type: Internal functions
Function, get-windowed-fft: Exported functions
Function, hann: Exported functions
Function, ifft: Exported functions
Function, impulse: Internal functions
Function, initialize-vector: Internal functions
Function, insert-spill: Internal functions
Function, iota: Internal functions
Function, lb: Exported functions
Function, load-op-idx: Internal functions
Function, load-op-p: Internal functions
Function, load-op-var: Internal functions
Function, m*: Internal functions
Function, m+: Internal functions
Function, m-: Internal functions
Function, m=: Internal functions
Function, make-dummy-window: Internal functions
Function, make-forward-fun: Internal functions
Function, make-load-op: Internal functions
Function, make-scaled-fwd: Exported functions
Function, make-scaled-inv: Exported functions
Function, make-store-op: Internal functions
Function, make-twiddle: Exported functions
Function, make-vector: Internal functions
Function, make-windowed-fwd: Exported functions
Function, make-windowed-inv: Exported functions
Function, mul+/-sqrt+i: Internal functions
Function, mul+/-sqrt-i: Internal functions
Function, mul+i: Internal functions
Function, mul-i: Internal functions
Function, mul-root: Internal functions
Function, note-writes: Internal functions
Function, op-args: Internal functions
Function, op-body: Internal functions
Function, op-deps: Internal functions
Function, op-p: Internal functions
Function, op-writes: Internal functions
Function, power-of-two-p: Exported functions
Function, random-vector: Internal functions
Function, real-samplify: Exported functions
Function, rectangular: Exported functions
Function, rfft: Exported functions
Function, rifft: Exported functions
Function, rol: Internal functions
Function, rotate: Internal functions
Function, run-forward-tests: Exported functions
Function, run-offsets: Exported functions
Function, run-pairs: Exported functions
Function, run-windows: Exported functions
Function, scale: Internal functions
Function, slow-bit-reverse: Internal functions
Function, store-op-idx: Internal functions
Function, store-op-p: Internal functions
Function, store-op-var: Internal functions
Function, swap: Internal functions
Function, test-offset: Exported functions
Function, test-pairs: Exported functions
Function, test-window: Exported functions
Function, triangle: Exported functions
Function, vval: Internal functions
Function, vval-dests: Internal functions
Function, vval-name: Internal functions
Function, vval-p: Internal functions
Function, vval-reads: Internal functions
Function, vval-spills: Internal functions
Function, vval-status: Internal functions
Function, vval-type: Internal functions
Function, window-vector: Exported functions
Function, windowed-fft: Exported functions
Function, windowed-ifft: Exported functions
Function, windowed-rfft: Exported functions
Function, windowed-rifft: Exported functions
Function, z-order-words: Internal functions

G
gauss*: Exported functions
gaussian: Exported functions
gaussian*bartlett^x: Exported functions
gen-bit-reversal: Exported functions
gen-dif: Exported functions
gen-dit: Exported functions
gen-flat-dif: Internal functions
gen-flat-dit: Internal functions
generate-fft: Internal functions
generate-large-reversal: Internal functions
generate-leaf-reverse: Internal functions
generate-leaf-reverse-swap: Internal functions
generate-outward-seq: Internal functions
get-fancy-fwd: Exported functions
get-fancy-inv: Exported functions
get-fancy-windowed-fwd: Exported functions
get-fancy-windowed-inv: Exported functions
get-fft: Exported functions
get-radix-2-twiddle: Internal functions
get-reverse: Exported functions
get-window-type: Internal functions
get-windowed-fft: Exported functions

H
hann: Exported functions

I
ifft: Exported functions
impulse: Internal functions
initialize-vector: Internal functions
insert-spill: Internal functions
iota: Internal functions

L
lb: Exported functions
load-op-idx: Internal functions
load-op-p: Internal functions
load-op-var: Internal functions

M
m*: Internal functions
m+: Internal functions
m-: Internal functions
m=: Internal functions
Macro, bblock: Internal macros
Macro, define-inline-function: Internal macros
Macro, for: Internal macros
Macro, op: Internal macros
Macro, with-scale: Internal macros
Macro, with-vector: Internal macros
make-dummy-window: Internal functions
make-forward-fun: Internal functions
make-load-op: Internal functions
make-scaled-fwd: Exported functions
make-scaled-inv: Exported functions
make-store-op: Internal functions
make-twiddle: Exported functions
make-vector: Internal functions
make-windowed-fwd: Exported functions
make-windowed-inv: Exported functions
mul+/-sqrt+i: Internal compiler macros
mul+/-sqrt+i: Internal functions
mul+/-sqrt-i: Internal compiler macros
mul+/-sqrt-i: Internal functions
mul+i: Internal compiler macros
mul+i: Internal functions
mul-i: Internal compiler macros
mul-i: Internal functions
mul-root: Internal functions

N
note-writes: Internal functions

O
op: Internal macros
op-args: Internal functions
op-body: Internal functions
op-deps: Internal functions
op-p: Internal functions
op-writes: Internal functions

P
power-of-two-p: Exported functions

R
random-vector: Internal functions
real-samplify: Exported functions
rectangular: Exported functions
rfft: Exported functions
rifft: Exported functions
rol: Internal functions
rotate: Internal functions
run-forward-tests: Exported functions
run-offsets: Exported functions
run-pairs: Exported functions
run-windows: Exported functions

S
scale: Internal functions
slow-bit-reverse: Internal functions
store-op-idx: Internal functions
store-op-p: Internal functions
store-op-var: Internal functions
swap: Internal functions

T
test-offset: Exported functions
test-pairs: Exported functions
test-window: Exported functions
triangle: Exported functions

V
vval: Internal functions
vval-dests: Internal functions
vval-name: Internal functions
vval-p: Internal functions
vval-reads: Internal functions
vval-spills: Internal functions
vval-status: Internal functions
vval-type: Internal functions

W
window-vector: Exported functions
windowed-fft: Exported functions
windowed-ifft: Exported functions
windowed-rfft: Exported functions
windowed-rifft: Exported functions
with-scale: Internal macros
with-vector: Internal macros

Z
z-order-words: Internal functions

Jump to:   %   (   @  
A   B   C   D   E   F   G   H   I   L   M   N   O   P   R   S   T   V   W   Z  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   %   *   +  
A   B   C   D   I   N   R   S   T   V   W  
Index Entry  Section

%
%blocking-factor%: Internal symbol macros
%unroll-count%: Internal symbol macros

*
*bit-reverse-lock*: Internal special variables
*bit-reversed*: Internal special variables
*bit-reverses*: Internal special variables
*default-abs-tol*: Internal special variables
*double-bit-reverses*: Internal special variables
*fancy-in-order*: Exported special variables
*fft-lock*: Internal special variables
*ffts*: Internal special variables
*forward-twiddle*: Internal special variables
*fwd-base-case*: Internal special variables
*inv-base-case*: Internal special variables
*inverse-twiddle*: Internal special variables
*max-small-bit-reverse*: Internal special variables
*ops*: Internal special variables
*optimization-policy*: Exported special variables
*outer-width*: Internal special variables
*rfft-twiddles*: Exported special variables
*rifft-twiddles*: Exported special variables
*swap-block-size*: Internal special variables
*twiddle-lock*: Internal special variables
*vector*: Internal special variables

+
+twiddle-offset+: Exported constants

A
args: Internal structures

B
body: Internal structures

C
Constant, +twiddle-offset+: Exported constants

D
deps: Internal structures
dests: Internal structures

I
idx: Internal structures
idx: Internal structures

N
name: Internal structures

R
reads: Internal structures

S
Slot, args: Internal structures
Slot, body: Internal structures
Slot, deps: Internal structures
Slot, dests: Internal structures
Slot, idx: Internal structures
Slot, idx: Internal structures
Slot, name: Internal structures
Slot, reads: Internal structures
Slot, spills: Internal structures
Slot, status: Internal structures
Slot, type: Internal structures
Slot, var: Internal structures
Slot, var: Internal structures
Slot, writes: Internal structures
Special Variable, *bit-reverse-lock*: Internal special variables
Special Variable, *bit-reversed*: Internal special variables
Special Variable, *bit-reverses*: Internal special variables
Special Variable, *default-abs-tol*: Internal special variables
Special Variable, *double-bit-reverses*: Internal special variables
Special Variable, *fancy-in-order*: Exported special variables
Special Variable, *fft-lock*: Internal special variables
Special Variable, *ffts*: Internal special variables
Special Variable, *forward-twiddle*: Internal special variables
Special Variable, *fwd-base-case*: Internal special variables
Special Variable, *inv-base-case*: Internal special variables
Special Variable, *inverse-twiddle*: Internal special variables
Special Variable, *max-small-bit-reverse*: Internal special variables
Special Variable, *ops*: Internal special variables
Special Variable, *optimization-policy*: Exported special variables
Special Variable, *outer-width*: Internal special variables
Special Variable, *rfft-twiddles*: Exported special variables
Special Variable, *rifft-twiddles*: Exported special variables
Special Variable, *swap-block-size*: Internal special variables
Special Variable, *twiddle-lock*: Internal special variables
Special Variable, *vector*: Internal special variables
spills: Internal structures
status: Internal structures
Symbol Macro, %blocking-factor%: Internal symbol macros
Symbol Macro, %unroll-count%: Internal symbol macros

T
type: Internal structures

V
var: Internal structures
var: Internal structures

W
writes: Internal structures

Jump to:   %   *   +  
A   B   C   D   I   N   R   S   T   V   W  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   D   H   I   L   N   O   P   R   S   T   V   W  
Index Entry  Section

C
complex-sample: Exported types
complex-sample-array: Exported types

D
direction: Exported types

H
half-index: Exported types
half-size: Exported types

I
index: Exported types

L
load-op: Internal structures

N
napa-fft: The napa-fft package
napa-fft.gen: The napa-fft<dot>gen package
napa-fft.impl: The napa-fft<dot>impl package
napa-fft.support: The napa-fft<dot>support package
napa-fft.tests: The napa-fft<dot>tests package
napa-fft3: The napa-fft3 system

O
op: Internal structures

P
Package, napa-fft: The napa-fft package
Package, napa-fft.gen: The napa-fft<dot>gen package
Package, napa-fft.impl: The napa-fft<dot>impl package
Package, napa-fft.support: The napa-fft<dot>support package
Package, napa-fft.tests: The napa-fft<dot>tests package

R
real-sample: Exported types
real-sample-array: Exported types

S
scaling: Exported types
size: Exported types
store-op: Internal structures
Structure, load-op: Internal structures
Structure, op: Internal structures
Structure, store-op: Internal structures
Structure, vval: Internal structures
System, napa-fft3: The napa-fft3 system

T
Type, complex-sample: Exported types
Type, complex-sample-array: Exported types
Type, direction: Exported types
Type, half-index: Exported types
Type, half-size: Exported types
Type, index: Exported types
Type, real-sample: Exported types
Type, real-sample-array: Exported types
Type, scaling: Exported types
Type, size: Exported types
Type, windowing: Exported types

V
vval: Internal structures

W
windowing: Exported types

Jump to:   C   D   H   I   L   N   O   P   R   S   T   V   W