1 /* Karatsuba convolution
3 * Copyright (C) 1999 Ralph Loader <suckfish@ihug.co.nz>
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
24 /* The algorithm is based on the following. For the convolution of a pair
25 * of pairs, (a,b) * (c,d) = (0, a.c, a.d+b.c, b.d), we can reduce the four
26 * multiplications to three, by the formulae a.d+b.c = (a+b).(c+d) - a.c -
27 * b.d. A similar relation enables us to compute a 2n by 2n convolution
28 * using 3 n by n convolutions, and thus a 2^n by 2^n convolution using 3^n
29 * multiplications (as opposed to the 4^n that the quadratic algorithm
32 /* For large n, this is slower than the O(n log n) that the FFT method
33 * takes, but we avoid using complex numbers, and we only have to compute
34 * one convolution, as opposed to 3 FFTs. We have good locality-of-
35 * reference as well, which will help on CPUs with tiny caches. */
37 /* E.g., for a 512 x 512 convolution, the FFT method takes 55 * 512 = 28160
38 * (real) multiplications, as opposed to 3^9 = 19683 for the Karatsuba
39 * algorithm. We actually want 257 outputs of a 256 x 512 convolution;
40 * that doesn't appear to give an easy advantage for the FFT algorithm, but
41 * for the Karatsuba algorithm, it's easy to use two 256 x 256
42 * convolutions, taking 2 x 3^8 = 12312 multiplications. [This difference
43 * is that the FFT method "wraps" the arrays, doing a 2^n x 2^n -> 2^n,
44 * while the Karatsuba algorithm pads with zeros, doing 2^n x 2^n -> 2.2^n
47 /* There's a big lie above, actually... for a 4x4 convolution, it's quicker
48 * to do it using 16 multiplications than the more complex Karatsuba
49 * algorithm... So the recursion bottoms out at 4x4s. This increases the
50 * number of multiplications by a factor of 16/9, but reduces the overheads
53 /* The convolution algorithm is implemented as a stack machine. We have a
54 * stack of commands, each in one of the forms "do a 2^n x 2^n
55 * convolution", or "combine these three length 2^n outputs into one
65 typedef union stack_entry_s
69 const double *left, *right;
79 #define STACK_SIZE (CONVOLVE_DEPTH * 3)
81 struct _struct_convolve_state
83 double left[CONVOLVE_BIG];
84 double right[CONVOLVE_SMALL * 3];
85 double scratch[CONVOLVE_SMALL * 3];
86 stack_entry stack[STACK_SIZE];
90 * Initialisation routine - sets up tables and space to work in.
91 * Returns a pointer to internal state, to be used when performing calls.
92 * On error, returns NULL.
93 * The pointer should be freed when it is finished with, by convolve_close().
98 return (convolve_state *) malloc (sizeof (convolve_state));
102 * Free the state allocated with convolve_init().
105 convolve_close (convolve_state * state)
112 convolve_4 (double *out, const double *left, const double *right)
113 /* This does a 4x4 -> 7 convolution. For what it's worth, the slightly odd
114 * ordering gives about a 1% speed up on my Pentium II. */
116 double l0, l1, l2, l3, r0, r1, r2, r3;
125 a = (l0 * r1) + (l1 * r0);
129 a = (l0 * r2) + (l1 * r1) + (l2 * r0);
134 out[3] = (l0 * r3) + (l1 * r2) + (l2 * r1) + (l3 * r0);
135 out[4] = (l1 * r3) + (l2 * r2) + (l3 * r1);
136 out[5] = (l2 * r3) + (l3 * r2);
141 convolve_run (stack_entry * top, unsigned size, double *scratch)
142 /* Interpret a stack of commands. The stack starts with two entries; the
143 * convolution to do, and an illegal entry used to mark the stack top. The
144 * size is the number of entries in each input, and must be a power of 2,
145 * and at least 8. It is OK to have out equal to left and/or right.
146 * scratch must have length 3*size. The number of stack entries needed is
147 * 3n-4 where size=2^n. */
154 /* When we get here, the stack top is always a convolve,
155 * with size > 4. So we will split it. We repeatedly split
156 * the top entry until we get to size = 4. */
159 right = top->v.right;
164 double *s_left, *s_right;
167 /* Halve the size. */
170 /* Allocate the scratch areas. */
171 s_left = scratch + size * 3;
172 /* s_right is a length 2*size buffer also used for
173 * intermediate output. */
174 s_right = scratch + size * 4;
176 /* Create the intermediate factors. */
177 for (i = 0; i < size; i++) {
178 double l = left[i] + left[i + size];
179 double r = right[i] + right[i + size];
181 s_left[i + size] = r;
185 /* Push the combine entry onto the stack. */
188 top[2].b.null = NULL;
190 /* Push the low entry onto the stack. This must be
191 * the last of the three sub-convolutions, because
192 * it may overwrite the arguments. */
193 top[1].v.left = left;
194 top[1].v.right = right;
197 /* Push the mid entry onto the stack. */
198 top[0].v.left = s_left;
199 top[0].v.right = s_right;
200 top[0].v.out = s_right;
202 /* Leave the high entry in variables. */
209 /* When we get here, the stack top is a group of 3
210 * convolves, with size = 4, followed by some combines. */
211 convolve_4 (out, left, right);
212 convolve_4 (top[0].v.out, top[0].v.left, top[0].v.right);
213 convolve_4 (top[1].v.out, top[1].v.left, top[1].v.right);
216 /* Now process combines. */
218 /* b.main is the output buffer, mid is the middle
219 * part which needs to be adjusted in place, and
220 * then folded back into the output. We do this in
221 * a slightly strange way, so as to avoid having
223 double *out = top->b.main;
224 double *mid = scratch + size * 4;
228 out[size * 2 - 1] = 0;
229 for (i = 0; i < size - 1; i++) {
233 lo = mid[0] - (out[0] + out[2 * size]) + out[size];
234 hi = mid[size] - (out[size] + out[3 * size]) + out[2 * size];
241 } while (top->b.null == NULL);
242 } while (top->b.main != NULL);
246 convolve_match (const int *lastchoice,
247 const short *input, convolve_state * state)
248 /* lastchoice is a 256 sized array. input is a 512 array. We find the
249 * contiguous length 256 sub-array of input that best matches lastchoice.
250 * A measure of how good a sub-array is compared with the lastchoice is
251 * given by the sum of the products of each pair of entries. We maximise
252 * that, by taking an appropriate convolution, and then finding the maximum
253 * entry in the convolutions. state is a (non-NULL) pointer returned by
260 double *left = state->left;
261 double *right = state->right;
262 double *scratch = state->scratch;
263 stack_entry *top = state->stack + STACK_SIZE - 1;
266 for (i = 0; i < 512; i++)
270 for (i = 0; i < 256; i++) {
271 double a = lastchoice[255 - i];
277 /* We adjust the smaller of the two input arrays to have average
278 * value 0. This makes the eventual result insensitive to both
279 * constant offsets and positive multipliers of the inputs. */
281 for (i = 0; i < 256; i++)
283 /* End-of-stack marker. */
284 #if 0 /* The following line produces a CRASH, need to figure out why?!! */
285 top[1].b.null = scratch;
287 top[1].b.main = NULL;
288 /* The low 256x256, of which we want the high 256 outputs. */
290 top->v.right = right;
291 top->v.out = right + 256;
292 convolve_run (top, 256, scratch);
294 /* The high 256x256, of which we want the low 256 outputs. */
295 top->v.left = left + 256;
296 top->v.right = right;
298 convolve_run (top, 256, scratch);
300 /* Now find the best position amoungs this. Apart from the first
301 * and last, the required convolution outputs are formed by adding
302 * outputs from the two convolutions above. */
306 for (i = 0; i < 256; i++) {
307 double a = right[i] + right[i + 512];
318 /* This is some debugging code... */
322 for (i = 0; i < 256; i++)
323 best += ((double) input[i + p]) * ((double) lastchoice[i] - avg);
325 for (i = 0; i < 257; i++) {
329 for (j = 0; j < 256; j++)
330 tot += ((double) input[i + j]) * ((double) lastchoice[j] - avg);
333 if (tot != left[i + 255])