Help us shape the future of Go! Take the 2026 Go Developer Survey

kernels

package
v0.28.6 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 27, 2026 License: BSD-3-Clause Imports: 1 Imported by: 0

Documentation

Overview

Package kernels holds the inner loops of the FFT — the bit-reversal permutation and the radix-2 butterfly stages — isolated from the public API.

Today these are portable scalar pure-Go implementations. They are kept in their own package so that SIMD variants generated by go-asmgen across the six 64-bit Go targets (amd64, arm64, riscv64, loong64, ppc64le, s390x) can be substituted later behind the same function signatures without touching the public fft package.

Index

Constants

View Source 
const ZnThreePassMax = 512

ZnThreePassMax is the longest transform ZnThreePass runs: znThreePassAVX2's frame holds two buffers of that many points (znThreePassMax in gen.go).

View Source 
const ZnTwoPassMax = 256

ZnTwoPassMax is the longest transform ZnTwoPass runs: znTwoPassAVX2's frame holds that many complex128 points (znTwoPassMax in gen.go).

Variables

View Source 
var (
	UseStockhamAVX2   = useAVX2
	UseStockhamAVX512 = supportsAVX512F()
)

UseStockhamAVX2 and UseStockhamAVX512 report whether StockhamPass may take the AVX2 and the AVX-512 kernels. They are variables so the tests can run every narrower path on a machine that has the wider one.

View Source 
var ClCompSplit256 = true

ClCompSplit256 lets the composites take the 256-bit split layout on a CPU where the 512-bit one serves the powers of two (Round 31, Cascade Lake). The 512-bit kernels run powers of two only, so the composites ran their radix-4 and radix-8 passes interleaved there. With Round 29's composite rule, every n = 2^e·3^a·5^b up to 16384 (e >= 1, a+b >= 1), five rotated rounds: the rule interleaved ran 1.086× as fast as Round 24's (geometric mean) with six lengths below 0.98, and split 1.093× with none below 0.984. Above 16384 (fifteen lengths to 10^6, seven rounds) the layout did not pay (0.916–1.011), so clCompSplitMax bounds it. A variable so the tests can turn it off.

View Source 
var IntelCPU = isGenuineIntel()

IntelCPU reports whether CPUID names the vendor GenuineIntel. It only tunes the fft package's radix rule (route_amd64.go), which was measured to differ between Intel and AMD; no result depends on it. A hypervisor reporting its own vendor string reads as false, which keeps the default rule.

View Source 
var R32Cos = [9]float64{
	1,
	0.98078528040323044912618223613423903697393373089333,
	0.92387953251128675612818318939678828682241662586364,
	0.83146961230254523707878837761790575673856081757400,
	0.70710678118654752440084436210484903928483593768847,
	0.55557023301960222474283081394853287437493719075480,
	0.38268343236508977172845998403039886676134456248563,
	0.19509032201612826784828486847702224092769161775195,
	0,
}

R32Cos[k] is cos(kπ/16), k = 0 .. 8.

View Source 
var UntangleWideMax, RetangleWideMax = 1 << 16, 1 << 14

UntangleWideMax and RetangleWideMax are the longest half-lengths m whose Untangle and Retangle take the 512-bit kernel (clUntangleWide). Variables so the tests can move them. Round 31 stopped both at m = 16384 because IRFFT did not gain beyond it; the forward one does (Round 35, Cascade Lake, one process, fifteen rotated rounds, time bounded at 16384 ÷ time unbounded): RFFT 65536 (m = 32768) 1.058, every round 1.050–1.076; RFFT 131072 1.033 (1.011–1.108); RFFT 2^20 1.012 (0.922–1.069), within its noise; IRFFT 0.99–1.01 at all three. So Untangle runs at 512 bits to m = 65536, Retangle to 16384.

View Source 
var UseFMA = useAVX2 && supportsFMA()

UseFMA reports whether the CPU runs the FMA kernels: AVX2, which every FMA kernel also uses, and FMA3, a CPUID bit of its own that a hypervisor can mask apart from AVX2 (supportsFMA, go-asmgen's probe, which also checks that the OS saves YMM state). The fft package reads it when it builds a plan; a variable so that its tests can build the default plan on a machine with FMA. Setting it on a CPU without FMA3 makes the FMA kernels fault.

View Source 
var UseStockham32 = useAVX2

UseStockham32 reports whether StockhamPass32 may take the AVX2 kernels; a variable so the tests can compare them with the Go passes.

View Source 
var UseStockhamBatch32 = useAVX2

UseStockhamBatch32 reports whether StockhamBatchPass32 takes the AVX2 kernels (genF32rBatchAVX2); a variable so the tests can compare them with the Go batched pass.

View Source 
var UseStockhamBatchAVX2 = useAVX2

UseStockhamBatchAVX2 reports whether StockhamBatchPass takes the AVX2 kernels; a variable so the tests can compare them with the Go pass.

View Source 
var UseStockhamSplit = splitDefault(useAVX2, supportsAVX512F())

UseStockhamSplit reports whether plans built from now on keep their data split between passes (StockhamSplitModes); splitDefault decides. A variable so the tests can turn it on and off; a plan keeps the layout it was built with, and its passes all fall back to Go, interleaved, when UseStockhamAVX2 is off.

View Source 
var UseStockhamSplit512 = intelSplit512Default(useAVX2, supportsAVX512F(), IntelCPU)

UseStockhamSplit512 reports whether plans built from now on keep the data of a power of two split at 512 bits between passes, instead of the 256-bit layout (UseStockhamSplit) or none; intelSplit512Default decides. A variable so the tests can turn it on and off; it takes effect only where the CPU runs AVX-512 (intelHasAVX512).

View Source 
var UseUntangle32 = useAVX2

UseUntangle32 reports whether Untangle32 and Retangle32 take the AVX2 kernels; a variable so the tests can compare them with the Go loops.

View Source 
var UseUntangleAVX2 = useAVX2

UseUntangleAVX2 reports whether Untangle takes the AVX2 kernel; a variable so the tests can compare it with the scalar loop on an AVX2 machine.

View Source 
var UseUntangleAVX512 = untangle512Default(useAVX2, supportsAVX512F(), IntelCPU)

UseUntangleAVX512 reports whether Untangle and Retangle run four bins per step on the 512-bit kernels (Round 31), the AVX2 kernel taking a pair left over; untangle512Default decides. A variable so the tests can compare the two widths on an AVX-512 machine.

View Source 
var ZmCMulOn = !IntelCPU

ZmCMulOn lets CMulTo run zmCMulAVX2: on where the CPU is not Intel's, the only vendor Round 36 measured it on (Zen 3). Its results are the Go loop's bits either way. A variable so the tests can take both routes on any machine.

View Source 
var ZmSplitOdd = !IntelCPU

ZmSplitOdd lets splitModes put radix-3 and radix-5 passes in a split run (Round 36, measured on Zen 3 only): on where the CPU is not Intel's. A variable so the tests can take both routes on any machine; a plan keeps the modes it was built with, and the kernels run either way.

Functions

func BitReverse 

func BitReverse(x []complex128)

BitReverse permutes x in place into bit-reversal order, the prerequisite ordering for the iterative radix-2 transform. len(x) must be a power of two.

func CMul 

func CMul(a, b []complex128)

CMul computes the elementwise complex product a[i] *= b[i] over the first min(len(a), len(b)) elements, in place in a. Bluestein's pointwise spectral product called it until Round 36, which moved Bluestein's three products to CMulTo (cmulto.go) and its four-point AVX2 kernel on amd64; it remains the stable seam behind which these per-architecture SIMD kernels are validated.

Today CMul routes to the portable scalar oracle CMulScalar. Each supported architecture also ships a generated SIMD kernel (cmulSIMD, from cmul_<arch>.s) that the per-arch CI execution jobs assert is bit-identical to CMulScalar — but the kernel is NOT installed on the hot path, because the Go compiler's scalar loop (gc does not vectorize; on arm64 it emits FMULD/ FMADDD/FMSUBD) matches or beats it at the widths Bluestein uses (measured: ~3x faster than the de-interleaving NEON kernel on arm64; see docs/plan-fft.md). Routing the hot path through a kernel we have measured to be slower would be a regression, so the scalar default stands until a kernel is measured to win. The SIMD work remains a validated, per-arch-tested artifact and the reference for future widening.

Coverage policy. The portable scalar core (this file, cmul.go, kernels.go) is held to 100% statement coverage under the pure-Go gate. The generated assembly carries no Go statements; the per-arch cmulSIMD wrappers are reached only on their own architecture and are exercised by that architecture's native/qemu execution job (which runs the SIMD==scalar assertion), not by the single-run gate. Nothing is excluded from the gate that is not exercised by a per-arch job, and the gate is never lowered.

func CMulScalar 

func CMulScalar(a, b []complex128)

CMulScalar computes the elementwise (Hadamard) complex product a[i] *= b[i] over the first min(len(a), len(b)) elements, in place in a. It is the portable pure-Go correctness oracle for the pointwise complex multiply used by Bluestein's convolution, and the fallback when no SIMD kernel is selected for the running CPU.

The complex product of (ar + ai·i) and (br + bi·i) is 

(ar·br − ai·bi) + (ar·bi + ai·br)·i.

Keeping this in its own function lets the SIMD variants (cmul_<arch>.s, generated by go-asmgen) drop in behind CMul with bit-identical results.

//go:noinline pins a single compiled body for the oracle so that every caller — the dispatched CMul, the per-arch cmulSIMD fallback, and the test's reference computation — observes the SAME floating-point form. Without it the gc compiler may fuse ar*br-ai*bi into an FMA at one call site but not another (FMA is baseline on arm64 and the other non-amd64 targets), making the scalar==scalar comparison diverge by 1 ULP purely from inlining. amd64's SSE2 kernel matches because GOAMD64=v1 does not fuse, the same form this body compiles to there.

func CMulTo added in v0.26.0 

func CMulTo(dst, a, b []complex128)

CMulTo writes dst[i] = a[i]·b[i] for every i < len(dst), Go's complex product, and panics before writing anything if a or b is shorter than dst. dst may be a (in place); it must not otherwise overlap a or b. On amd64 with AVX2, where ZmCMulOn (not Intel) says so, the points four at a time run on zmCMulAVX2 (zmcmul_amd64.s, Round 36), whose products, sums and differences are the GOAMD64=v1 scalar loop's, bit for bit; the rest, and every other CPU, run the scalar loop below. Bluestein's chirp and spectral products call it.

func IsPowerOfTwo 

func IsPowerOfTwo(n int) bool

IsPowerOfTwo reports whether n is a positive power of two.

func R32Trig added in v0.28.0 

func R32Trig(e int) (c, s float64)

R32Trig returns cos θ and sin θ, θ = 2π·e/32, for 0 <= e < 24, from R32Cos by the exact symmetries: the internal twiddle W32^e is cos θ + s·i·sin θ (s = −1 forward, +1 inverse).

func Radix2 

func Radix2(x []complex128, inverse bool)

Radix2 performs an in-place iterative radix-2 Cooley–Tukey transform on x, which must already be in bit-reversal order and have a power-of-two length. When inverse is true it uses the conjugate twiddle factors; the caller is responsible for the 1/N normalization.

func Radix2Stage 

func Radix2Stage(a []complex128, n, span int, tw []complex128)

Radix2Stage runs one radix-2 DIT pass: see Radix2StageScalar.

func Radix2StageScalar 

func Radix2StageScalar(a []complex128, n, span int, tw []complex128)

Radix2StageScalar runs one radix-2 decimation-in-time pass in place over a (length n). span is the sub-transform length entering the stage; groups of 2·span are combined. tw is the span-long twiddle plane (tw[k]=W_{2·span}^k). For each group base and each k in [0,span): 

t            = a[base+span+k] * tw[k]
a[base+k]    = a[base+k] + t
a[base+span+k] = a[base+k]_old - t

It is the portable correctness oracle and the fallback when no SIMD kernel is selected. //go:noinline pins one compiled body so every caller observes the same floating-point form (the same reason CMulScalar is noinline).

func Radix4Stage 

func Radix4Stage(a []complex128, n, span int, w1, w2, w3 []complex128, inverse bool)

Radix4Stage runs one radix-4 DIT pass: see Radix4StageScalar.

func Radix4StageScalar 

func Radix4StageScalar(a []complex128, n, span int, w1, w2, w3 []complex128, inverse bool)

Radix4StageScalar runs one radix-4 decimation-in-time pass in place over a (length n). span is the sub-transform length entering the stage; groups of 4·span are combined. w1,w2,w3 are the three span-long twiddle planes (w1[k]=W^k, w2[k]=W^{2k}, w3[k]=W^{3k}). inverse selects the rotation (×−i forward, ×+i inverse). For each group base and each k in [0,span): 

m1 = a[i1+k]*w1[k], m2 = a[i2+k]*w2[k], m3 = a[i3+k]*w3[k]   (i1=base+span …)
t0 = a[i0+k]+m2, t1 = a[i0+k]-m2, t2 = m1+m3, t3 = rot∓i(m1-m3)
a[i0+k]=t0+t2, a[i1+k]=t1+t3, a[i2+k]=t0-t2, a[i3+k]=t1-t3

func Retangle 

func Retangle(z, x, tw []complex128, m int, h float64) int

Retangle runs the real-FFT inverse untangle for k = 1 .. 2·⌊half/2⌋ (half = (m-1)/2) on the AVX2 kernel (or the 512-bit one, as Untangle), writing z from the complete half spectrum x scaled by h = 0.5·scale, and returns the last k it produced, or 0 when it did nothing (UseUntangleAVX2 gates it too). z holds at least m entries, x m+1 and tw 2·pairs+2.

func Retangle32 added in v0.16.0 

func Retangle32(z, x, tw []complex64, m int, h float32) int

Retangle32 runs the inverse untangle for k = 1 .. 4·quads on the SIMD kernel, writing z (and its mirrors z[m-k]) from the complete half spectrum x scaled by h, and returns the last k it produced, or 0 when it did nothing. z holds at least m entries, x m+1 and tw 4·quads+1.

func StockhamBatchKernels added in v0.8.0 

func StockhamBatchKernels() bool

StockhamBatchKernels reports whether StockhamBatchPass has kernels on this machine (AVX2), which is when the fft package runs a non-contiguous axis as batched passes instead of gathering its lines.

func StockhamBatchKernels32 added in v0.16.0 

func StockhamBatchKernels32() bool

StockhamBatchKernels32 reports whether StockhamBatchPass32 has kernels on this machine (AVX2), which is when the fft package runs a non-contiguous float32 axis as batched passes instead of gathering its lines.

func StockhamBatchPass added in v0.8.0 

func StockhamBatchPass(r, ido, l1 int, cc, ch, tw []complex128, w, sIn, sOut int, inverse bool) bool

StockhamBatchPass runs one Stockham pass of radix r over a batch of w transforms laid out side by side, and reports true, or reports false (and does nothing) when no kernel can: no AVX2, or a radix without a kernel. Point p of the batch is the w values cc[p·sIn : p·sIn+w] on input and ch[p·sOut : p·sOut+w] on output (sIn, sOut >= w), so a pass reads or writes a strip of an N-D array in place. tw is StockhamBatchTwiddles' table for the direction (unused when ido == 1). The arithmetic is the scalar pass's, operation for operation, on every value of the batch.

func StockhamBatchPass32 added in v0.16.0 

func StockhamBatchPass32(r, ido, l1 int, cc, ch, tw []complex64, w, sIn, sOut int, inverse bool) bool

StockhamBatchPass32 runs one float32 Stockham pass of radix r over a batch of w transforms laid out side by side (Round 25), and reports true, or reports false (and does nothing) when no kernel can: no AVX2 on amd64, or a radix without a kernel. Point p of the batch is the w values cc[p·sIn : p·sIn+w] on input and ch[p·sOut : p·sOut+w] on output (sIn, sOut >= w), so a pass reads or writes a strip of an N-D array in place. tw is the fft package's batched twiddle table for the direction: for i = 1 .. ido-1, the r-1 twiddles of point i (unused when ido == 1). Every value of the batch gets the arithmetic of the 1-D float32 kernels (StockhamPass32), which is the Go pass's. It panics on a layout its bound checks cannot vouch for, before any kernel runs.

func StockhamBatchPassFMA added in v0.28.0 

func StockhamBatchPassFMA(r, ido, l1 int, cc, ch, tw []complex128, w, sIn, sOut int, inverse bool) bool

StockhamBatchPassFMA is StockhamBatchPass for a pass of an FMA plan: the FMA twins of the batched kernels, which fuse radix 8's √2/2 products in the final pass too.

func StockhamLastRun added in v0.12.0 

func StockhamLastRun(r int, cc, ch []complex128, os, runs, run, gap int, inverse, wide bool) bool

StockhamLastRun runs the final pass (ido == 1) of radix r over runs·run blocks of r points read one after the other from cc, and reports true, or reports false (and does nothing) when no kernel can: no AVX2, a radix other than 2, 4 or 8, or run not a positive multiple of 4. Output j of block q·run + c (c < run) goes to ch[q·gap + c + j·os]: the outputs land in runs of run consecutive points, gap apart, instead of one contiguous stream per j. The arithmetic is StockhamPass's final pass, operation for operation; wide allows the AVX-512 kernel as it does there.

func StockhamLastRunFMA added in v0.28.0 

func StockhamLastRunFMA(r int, cc, ch []complex128, os, runs, run, gap int, inverse, wide bool) bool

StockhamLastRunFMA is StockhamLastRun for the final pass of an FMA plan: the FMA twin of the kernel for radix 8, the default kernel otherwise.

func StockhamPass 

func StockhamPass(r, ido, l1 int, cc, ch, tw []complex128, inverse, wide bool) bool

StockhamPass runs one Stockham pass of radix r on the widest SIMD kernel that can run it and reports true, or reports false (and does nothing) when none can: no AVX2, or a radix without a kernel. cc holds r·ido·l1 inputs, ch receives as many outputs, and tw is the pass's twiddle table extended to i = 0 ((r-1) blocks of ido entries; unused by the final pass, ido == 1).

wide allows the AVX-512 kernels. The caller sets it for a transform whose length is a power of two and for nothing else: on Cascade Lake, AVX-512 sped powers of two up 1.16–1.49× (256–4096) but left composites at 0.88–1.04×, whether every pass or only the radix-2/4/8 passes went to 512 bits (the latter was worse, 0.83–0.94×); a transform that mixes widths, or runs radix-3/5/7 passes at 512 bits, pays for the core's 512-bit frequency license without enough work to amortize it. (2026-10-01)

func StockhamPass32 added in v0.13.0 

func StockhamPass32(r, ido, l1 int, cc, ch, tw []complex64, inverse bool) bool

StockhamPass32 runs one float32 Stockham pass of radix r on an AVX2 kernel and reports true, or reports false (and does nothing) when none can: no AVX2, or a radix without a kernel. cc holds r·ido·l1 inputs, ch receives as many outputs, and tw is StockhamTwiddles32's table for the direction (unused by the final pass, ido == 1). It panics when ido or l1 is below 1 or a slice is shorter than the pass reads or writes: the kernels trust these lengths.

func StockhamPassFMA added in v0.28.0 

func StockhamPassFMA(r, ido, l1 int, cc, ch, tw []complex128, inverse, wide bool) bool

StockhamPassFMA is StockhamPass for a pass of an FMA plan. A final pass (ido == 1) has no twiddles: it runs the FMA twin of its kernel where the butterfly has a product to fuse (stockhamLastFMAKernel), the default kernel otherwise.

func StockhamPassLayout added in v0.11.0 

func StockhamPassLayout(mode uint8, r, ido, l1 int, cc, ch, tw []complex128, inverse, wide bool) bool

StockhamPassLayout is StockhamPass with the pass's layout mode from StockhamSplitModes; mode 0 is StockhamPass itself. It reports false, as StockhamPass does, when the AVX2 kernels are off: every pass of a transform then runs in Go, interleaved. A mode the pass cannot run (an ido that is not a positive multiple of four, a radix without a split kernel, an unknown mode, l1 < 1) panics before any kernel runs: the kernels walk whole four-point groups and trust the layout.

func StockhamPassLayoutFMA added in v0.28.0 

func StockhamPassLayoutFMA(mode uint8, r, ido, l1 int, cc, ch, tw []complex128, inverse, wide bool) bool

StockhamPassLayoutFMA is StockhamPassLayout for a pass of an FMA plan.

func StockhamSplitModes added in v0.11.0 

func StockhamSplitModes(r, ido, l1 []int) []uint8

StockhamSplitModes returns, for the passes of one transform (pass k of radix r[k], ido[k], l1[k]), the layout mode of each: splitModes when UseStockhamSplit is on, all zeros (interleaved throughout) otherwise. Where the 512-bit layout runs, a power of two takes it (intelSplitModes512) and a composite of at most clCompSplitMax points the 256-bit one when ClCompSplit256 is on.

func StockhamSplitTwiddles added in v0.14.0 

func StockhamSplitTwiddles(r, ido, l1 int, root []complex128) (fwd, conj []complex128)

StockhamSplitTwiddles is StockhamTwiddles for a split pass: per group of four points i0 .. i0+3 and per j = 1 .. r-1, the real parts of twiddle j in the block order (i0, i0+2, i0+1, i0+3), then the imaginary parts, 64 bytes that the kernel loads as two registers. It is stored as complex128 for the plan's sake, two float64s per element, (r-1)·ido elements as interleaved.

func StockhamSplitTwiddlesFor added in v0.22.0 

func StockhamSplitTwiddlesFor(mode uint8, r, ido, l1 int, root []complex128) (fwd, conj []complex128)

StockhamSplitTwiddlesFor is StockhamSplitTwiddles for a pass of the given split mode: the 512-bit layout's twiddles for its modes, the 256-bit layout's for the others. Where the 512-bit layout runs, the composites take the 256-bit one (ClCompSplit256), so the mode, not the machine, says which.

func StockhamStrided added in v0.12.0 

func StockhamStrided(r int, cc, ch, tw []complex128, cnt, nb, sin, bin, sout, bout, btw int, first0, firstRest, inverse, wide bool) bool

StockhamStrided runs part of a Stockham pass of radix r (ido >= 4) with every stride given, and reports true, or reports false (and does nothing) when no kernel can: no AVX2, a radix other than 4 or 8, or cnt not a positive multiple of 4. It runs nb blocks of cnt points: point i of block b reads its inputs cc[b·bin + i + m·sin] (m < r), applies the pass's butterfly, multiplies output j >= 1 by its twiddle and writes ch[b·bout + i + j·sout]. tw is the pass's table (StockhamTwiddles) from the group of the block's first point on, and block b's twiddles start btw entries after block b-1's. first0 and firstRest say whether the first point of block 0, and of the other blocks, is the pass's point i = 0, which is not multiplied (the plain pass keeps it exact the same way). The arithmetic is StockhamPass's, operation for operation.

func StockhamStridedFMA added in v0.28.0 

func StockhamStridedFMA(r int, cc, ch, tw []complex128, cnt, nb, sin, bin, sout, bout, btw int, first0, firstRest, inverse, wide bool) bool

StockhamStridedFMA is StockhamStrided for a pass of an FMA plan.

func StockhamTwiddles 

func StockhamTwiddles(r, ido, l1 int, root []complex128) (fwd, conj []complex128)

StockhamTwiddles builds, for a pass of radix r with l1 earlier points and ido remaining ones, the twiddle table the kernels read, in forward and conjugate form: root is the size-n root table (root[k] = exp(-2πi·k/n)) and twiddle j of point i is root[(j·l1·i) mod n], i = 0..ido-1, j = 1..r-1. It returns nils when no kernel will run that pass.

The table is laid out group by group, in the order every kernel walks the points (twGroups): groups of four, then one of two and one of one for ido mod 4. A group of g points starting at i0 stores twiddle 1 of points i0 .. i0+g-1, then twiddle 2 of the same points, and so on. A pass so reads its twiddles as one sequential stream. Laid out as r-1 runs of ido entries, a radix-8 pass read seven streams beside its eight inputs and eight outputs; grouped, radix-8 transforms ran 1.22–1.53× faster on Zen 3 from 2048 points on, radix-4 ones up to 1.21×, and 1.02–1.07× on Cascade Lake (2026-10-04, see BENCHMARKS.md).

func StockhamTwiddles32 added in v0.13.0 

func StockhamTwiddles32(r, ido, l1 int, root []complex128) (fwd, conj []complex64)

StockhamTwiddles32 builds, for a float32 pass of radix r with l1 earlier points and ido remaining ones, the twiddle table the kernels read, in forward and conjugate form, each entry root[(j·l1·i) mod n] rounded once to complex64 (i = 0..ido-1, j = 1..r-1), or returns nils when no kernel runs the pass. The layout is StockhamTwiddles' (twGroups): groups of four points, one register each, then a group of two and one of one for ido mod 4, each group storing its r-1 twiddle runs back to back.

func Untangle 

func Untangle(dst, z, tw []complex128, m int) int

Untangle runs the real-FFT untangle for bins k = 1 .. 2·⌊half/2⌋ (half = (m-1)/2) on the AVX2 kernel (four bins per step on the 512-bit one where UseUntangleAVX512 says) and returns the last bin it produced, or 0 when it did nothing; the caller finishes the remaining bins, and the DC, Nyquist and middle bins, in Go. dst has m+1 entries, z at least m and tw 2·pairs+2 (the kernel reads the twiddles' imaginary parts at tw+8). dst may be z: each pair is read before it is written, and no two pairs overlap.

func Untangle32 added in v0.16.0 

func Untangle32(dst, z, tw []complex64, m int) int

Untangle32 runs the float32 real-FFT untangle for bins k = 1 .. 4·quads (and their mirrors m-k), quads = ⌊(m-1)/2/4⌋, on the SIMD kernel and returns the last bin it produced, or 0 when it did nothing; the caller finishes the remaining bins, and the DC, Nyquist and middle bins, in Go. dst holds at least m+1 entries, z m and tw 4·quads+1: the bound checks below panic before the kernel runs when one is shorter.

func UntangleTable added in v0.24.0 

func UntangleTable(tw []complex128, m int) []complex128

UntangleTable returns the table Untangle and Retangle read: tw itself, the twiddles as they lie (the AVX2 kernels permute them).

Types

type ZnPlan added in v0.23.0 

type ZnPlan struct {
	// contains filtered or unexported fields
}

ZnPlan is a Stockham transform of two or three passes bound to the kernels and twiddle tables that run it with the buffers between its passes in a kernel's own stack frame (znTwoPassAVX2, znThreePassAVX2): no scratch buffer from the caller, and no selection left for each call. ZnPlanFor builds it.

func ZnPlanFor added in v0.23.0 

func ZnPlanFor(r []int, mode []uint8, tw0, tw0c, tw1, tw1c []complex128) *ZnPlan

ZnPlanFor returns the ZnPlan of the passes of radices r (two or three) and layout modes mode (one per pass, the last 0), whose first two passes take the twiddle tables tw0 and tw1 (forward) and tw0c and tw1c (conjugate) as StockhamTwiddles or StockhamSplitTwiddlesFor build them (tw1 unused for two passes), or nil when the kernels cannot run it: the AVX2 kernels off, more points than ZnTwoPassMax or ZnThreePassMax, a radix without a kernel, a table too short, or layouts that do not chain (pass 0 reads interleaved data, each pass reads the layout the one before writes, the pass before the final one writes interleaved data). It is ZnPlanForWide without the AVX-512 kernels.

Run calls the kernels StockhamPassLayout and StockhamPass would call, with the same arguments, so the result is the same bits.

func ZnPlanForWide added in v0.25.0 

func ZnPlanForWide(r []int, mode []uint8, tw0, tw0c, tw1, tw1c []complex128, wide bool) *ZnPlan

ZnPlanForWide is ZnPlanFor for a transform whose passes StockhamPass runs with wide (Round 35, Cascade Lake): its 512-bit split passes (the modes of intelSplitModes512) and an AVX-512 final pass run in the frame too. An interleaved pass other than the last that StockhamPass would run at 512 bits has no entry point: such a plan gets nil.

func ZnPlanForWideFMA added in v0.28.0 

func ZnPlanForWideFMA(r []int, mode []uint8, tw0, tw0c, tw1, tw1c []complex128, wide bool, fma []bool) *ZnPlan

ZnPlanForWideFMA is ZnPlanForWide for the passes of an FMA plan (Round 41): pass i runs the FMA twin of the kernel ZnPlanForWide binds (the one StockhamPassLayoutFMA or StockhamPassFMA runs) where fma[i] is set, the default kernel where it is not (Round 42: an FMA plan fuses only the passes where that pays). fma has one entry per pass.

func (*ZnPlan) Run added in v0.23.0 

func (z *ZnPlan) Run(cc, ch []complex128, inverse bool) bool

Run transforms cc into ch (they may be the same slice) and reports true, or reports false (and does nothing) when the kernels it was built with have been turned off since: the AVX2 ones, or the AVX-512 final pass's.

func (*ZnPlan) Wide added in v0.25.0 

func (z *ZnPlan) Wide() bool

Wide reports whether the plan's final pass runs an AVX-512 kernel.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.