7.7.8. Convolution, Subsampling, Oversampling.
 (lsh/libidx/idx-convol.lsh)


This library contains functions for performing 1D and 2D convolutions, backconvolutions, subsampling with local averaging, and oversampling by sample replication. Each functionality is provided as a type-independent splicing macro (DMD) with names of the form midx-m1xxx and midx-m2xxx , as well as type specific functions for floats, doubles, and bytes (with names of the form idx-f1xxx , idx-d1xxx , idx-u1xxx . Two kinds of convolution functions are provided: generic 1D and 2D convolutions for any size kernel, and optimized 1D convolutions with kernels of size 2, 3, 4 and 5. The optimized versions are faster than the regular ones by about a factor of 2 through the use of loop unrolling and circular register stacks.

7.7.8.0. Fast 1D Convolutions
 (lsh/libidx/idx-convol.lsh)


a library of 1D convolutions that uses automatically generated code with unrolled loops and circular register stacks to limit memory accesses and speed up execution.

7.7.8.0.0. (midx-m1fastconvolacc in kernel out ksize type)
 (lsh/libidx/idx-convol.lsh)


ultrafast 1D convolution with accumulation of result into the output. in must be a CONTIGUOUS idx1, kernel an idx1, out a CONTIGUOUS idx1, ksize must be the size of the kernel, and type a string containing a valid C type, e.g. "float" (preferably the type of the objects in the 3 vectors). This macro is expanded at compile time into a bunch of "cinline" instructions. It unrolls loops with a circular register stack to minimize index calculations and memory access. Though this code is particularly fast on processors that have lots of floating point registers (MIPS, etc), it manages to to beat the pedestrian version by about a factor of 2 on pentiums (reaching approx 200MFLOPS per GHz for kernel of size 5). THIS CODE DOES NOT DO ANY RUN-TIME CHECK FOR ARRAY SIZE, SO BE CAREFULL.

7.7.8.0.1. (idx-f1fastconvol2acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 2 kernel (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing floats.

7.7.8.0.2. (idx-d1fastconvol2acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 2 kernel (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing doubles.

7.7.8.0.3. (idx-u1fastconvol2acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 2 kernel (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing ubytes.

7.7.8.0.4. (idx-f1fastconvol3acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 3 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing floats.

7.7.8.0.5. (idx-d1fastconvol3acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 3 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing doubles.

7.7.8.0.6. (idx-u1fastconvol3acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 3 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing ubytes.

7.7.8.0.7. (idx-f1fastconvol4acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 4 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing floats.

7.7.8.0.8. (idx-d1fastconvol4acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 4 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing doubles.

7.7.8.0.9. (idx-u1fastconvol4acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 4 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing ubytes.

7.7.8.0.10. (idx-f1fastconvol5acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 5 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing floats.

7.7.8.0.11. (idx-d1fastconvol5acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 5 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing doubles.

7.7.8.0.12. (idx-u1fastconvol5acc input kernel output)
 (lsh/libidx/idx-convol.lsh)


super-fast 1D convolution with size 5 kernel. result is ACCUMULATED in the output (with unrolled loops and optimal register assignment) input and output must be contiguous idx1, kernel must be an idx1 all containing ubytes.

7.7.8.1. Generic Convolutions
 (lsh/libidx/idx-convol.lsh)


Regular 1D and 2D convolution and backconvolutions for idx of doubles, floats, and ubytes. Each function take 3 arguments: input, kernel, output. The size of the output plus the size of the kernel minus 1 must equal to the size of the input in all dimensions (to prevent annoying boundary conditions). The backconvolution can be seen the transposed operator of the convolution.

7.7.8.1.0. (midx-m1convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


macro for 1D convolution. all arguments are idx1 (of any numerical type).

7.7.8.1.1. (idx-f1convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D convolution on idx1 of floats

7.7.8.1.2. (idx-m1convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D convolution on idx1 of floats (alias of idx-f1convol)

7.7.8.1.3. (idx-d1convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D convolution on idx1 of double

7.7.8.1.4. (idx-u1convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D convolution on idx1 of ubytes

7.7.8.1.5. (midx-m1backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


macro for 1D back convolution

7.7.8.1.6. (idx-f1backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D back convolution on floats

7.7.8.1.7. (idx-m1backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D back convolution on floats (alias of idx-f1backconvol.

7.7.8.1.8. (idx-d1backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D back convolution on doubles

7.7.8.1.9. (idx-u1backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


1D back convolution on ubytes

7.7.8.1.10. (midx-m2convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


macro for 2D convolution. all arguments are idx2.

7.7.8.1.11. (idx-f2convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution. all arguments are idx2 of floats

7.7.8.1.12. (idx-m2convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution. all arguments are idx2 of floats. (alias for idx-f2convol)

7.7.8.1.13. (idx-d2convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution. all arguments are idx2 of doubles.

7.7.8.1.14. (idx-u2convol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution. all arguments are idx2 of ubytes

7.7.8.1.15. (midx-m2convolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


macro for 2D convolution with accumulation . all arguments are idx2.

7.7.8.1.16. (idx-f2convolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution with accumulation . all arguments are idx2 of floats

7.7.8.1.17. (idx-m2convolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution with accumulation . all arguments are idx2.

7.7.8.1.18. (idx-d2convolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution with accumulation . all arguments are idx2 of double.

7.7.8.1.19. (idx-u2convolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D convolution with accumulation . all arguments are idx2 of ubyte.

7.7.8.1.20. (midx-m2backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


macro for 2D back-convolution. all arguments are idx2.

7.7.8.1.21. (idx-f2backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.1.22. (idx-m2backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats (alias for idx-f2baconvol)

7.7.8.1.23. (idx-d2backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.1.24. (idx-u2backconvol input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.1.25. (midx-m2backconvolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


macro for 2D back-convolution. all arguments are idx2.

7.7.8.1.26. (idx-f2backconvolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.1.27. (idx-m2backconvolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.1.28. (idx-d2backconvolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.1.29. (idx-u2backconvolacc input kernel output)
 (lsh/libidx/idx-convol.lsh)


2D back-convolution. all arguments are idx2 of floats.

7.7.8.2. 1D and 2D Subsampling and Oversampling
 (lsh/libidx/idx-convol.lsh)


functions that subsample 1D and 2D idx where each output sample is the average of n adjacent input samples (with no overlap). The oversmapling functions simply replicate the samples n times.

7.7.8.2.0. (midx-m1subsample input n output)
 (lsh/libidx/idx-convol.lsh)


macro for subsampling and summing of size n

7.7.8.2.1. (idx-f1subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.2. (idx-m1subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.3. (idx-d1subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.4. (idx-u1subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.5. (midx-m1oversample input n output)
 (lsh/libidx/idx-convol.lsh)


macro for oversampling of size n

7.7.8.2.6. (idx-f1oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.7. (idx-m1oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.8. (idx-d1oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.9. (idx-u1oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.10. (midx-m2subsample input n output)
 (lsh/libidx/idx-convol.lsh)


macro for subsampling and summing of size n

7.7.8.2.11. (idx-f2subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.12. (idx-m2subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.13. (idx-d2subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.14. (idx-u2subsample input n output)
 (lsh/libidx/idx-convol.lsh)


subsampling and summing of size n

7.7.8.2.15. (midx-m2oversample input n output)
 (lsh/libidx/idx-convol.lsh)


macro for oversampling of size n

7.7.8.2.16. (idx-f2oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.17. (idx-m2oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.18. (idx-d2oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n

7.7.8.2.19. (idx-u2oversample input n output)
 (lsh/libidx/idx-convol.lsh)


oversampling of size n