*
* Copyright (C) 1999 Ralph Loader <suckfish@ihug.co.nz>
*
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
*
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
*
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ *
+ * Note: 7th December 2004: This file used to be licensed under the GPL,
+ * but we got permission from Ralp Loader to relicense it to LGPL.
*
* $Id$
*
{
const double *left, *right;
double *out;
- } v;
+ }
+ v;
struct
{
double *main, *null;
- } b;
-
-} stack_entry;
+ }
+ b;
-#define STACK_SIZE (CONVOLVE_DEPTH * 3)
+}
+stack_entry;
struct _struct_convolve_state
{
- double left[CONVOLVE_BIG];
- double right[CONVOLVE_SMALL * 3];
- double scratch[CONVOLVE_SMALL * 3];
- stack_entry stack[STACK_SIZE];
+ int depth, small, big, stack_size;
+ double *left;
+ double *right;
+ double *scratch;
+ stack_entry *stack;
};
/*
* The pointer should be freed when it is finished with, by convolve_close().
*/
convolve_state *
-convolve_init (void)
+convolve_init (int depth)
{
- return (convolve_state *) malloc (sizeof (convolve_state));
+ convolve_state *state;
+
+ state = malloc (sizeof (convolve_state));
+ state->depth = depth;
+ state->small = (1 << depth);
+ state->big = (2 << depth);
+ state->stack_size = depth * 3;
+ state->left = calloc (state->big, sizeof (double));
+ state->right = calloc (state->small * 3, sizeof (double));
+ state->scratch = calloc (state->small * 3, sizeof (double));
+ state->stack = calloc (state->stack_size + 1, sizeof (stack_entry));
+ return state;
}
/*
void
convolve_close (convolve_state * state)
{
- if (state)
- free (state);
+ free (state->left);
+ free (state->right);
+ free (state->scratch);
+ free (state->stack);
+ free (state);
}
static void
/* Create the intermediate factors. */
for (i = 0; i < size; i++) {
- double l = left[i] + left[i + size];
- double r = right[i] + right[i + size];
+ double l = left[i] + left[i + size];
+ double r = right[i] + right[i + size];
- s_left[i + size] = r;
- s_left[i] = l;
+ s_left[i + size] = r;
+ s_left[i] = l;
}
/* Push the combine entry onto the stack. */
top++;
out[size * 2 - 1] = 0;
for (i = 0; i < size - 1; i++) {
- double lo;
- double hi;
-
- lo = mid[0] - (out[0] + out[2 * size]) + out[size];
- hi = mid[size] - (out[size] + out[3 * size]) + out[2 * size];
- out[size] = lo;
- out[2 * size] = hi;
- out++;
- mid++;
+ double lo;
+ double hi;
+
+ lo = mid[0] - (out[0] + out[2 * size]) + out[size];
+ hi = mid[size] - (out[size] + out[3 * size]) + out[2 * size];
+ out[size] = lo;
+ out[2 * size] = hi;
+ out++;
+ mid++;
}
size <<= 1;
} while (top->b.null == NULL);
} while (top->b.main != NULL);
}
-int
-convolve_match (const int *lastchoice,
- const short *input, convolve_state * state)
-/* lastchoice is a 256 sized array. input is a 512 array. We find the
- * contiguous length 256 sub-array of input that best matches lastchoice.
- * A measure of how good a sub-array is compared with the lastchoice is
- * given by the sum of the products of each pair of entries. We maximise
+/*
+ * convolve_match:
+ * @lastchoice: an array of size SMALL.
+ * @input: an array of size BIG (2*SMALL)
+ * @state: a (non-NULL) pointer returned by convolve_init.
+ *
+ * We find the contiguous SMALL-size sub-array of input that best matches
+ * lastchoice. A measure of how good a sub-array is compared with the lastchoice
+ * is given by the sum of the products of each pair of entries. We maximise
* that, by taking an appropriate convolution, and then finding the maximum
- * entry in the convolutions. state is a (non-NULL) pointer returned by
- * convolve_init. */
+ * entry in the convolutions.
+ *
+ * Return: the position of the best match
+ */
+int
+convolve_match (const int *lastchoice, const short *input,
+ convolve_state * state)
{
- double avg;
+ double avg = 0;
double best;
int p = 0;
int i;
double *left = state->left;
double *right = state->right;
double *scratch = state->scratch;
- stack_entry *top = state->stack + STACK_SIZE - 1;
+ stack_entry *top = state->stack + (state->stack_size - 1);
-#if 1
- for (i = 0; i < 512; i++)
+ for (i = 0; i < state->big; i++)
left[i] = input[i];
- avg = 0;
- for (i = 0; i < 256; i++) {
- double a = lastchoice[255 - i];
+ for (i = 0; i < state->small; i++) {
+ double a = lastchoice[(state->small - 1) - i];
right[i] = a;
avg += a;
}
-#endif
+
/* We adjust the smaller of the two input arrays to have average
* value 0. This makes the eventual result insensitive to both
* constant offsets and positive multipliers of the inputs. */
- avg /= 256;
- for (i = 0; i < 256; i++)
+ avg /= state->small;
+ for (i = 0; i < state->small; i++)
right[i] -= avg;
/* End-of-stack marker. */
-#if 0 /* The following line produces a CRASH, need to figure out why?!! */
top[1].b.null = scratch;
-#endif
top[1].b.main = NULL;
- /* The low 256x256, of which we want the high 256 outputs. */
+ /* The low (small x small) part, of which we want the high outputs. */
top->v.left = left;
top->v.right = right;
- top->v.out = right + 256;
- convolve_run (top, 256, scratch);
+ top->v.out = right + state->small;
+ convolve_run (top, state->small, scratch);
- /* The high 256x256, of which we want the low 256 outputs. */
- top->v.left = left + 256;
+ /* The high (small x small) part, of which we want the low outputs. */
+ top->v.left = left + state->small;
top->v.right = right;
top->v.out = right;
- convolve_run (top, 256, scratch);
+ convolve_run (top, state->small, scratch);
/* Now find the best position amoungs this. Apart from the first
* and last, the required convolution outputs are formed by adding
* outputs from the two convolutions above. */
- best = right[511];
- right[767] = 0;
+ best = right[state->big - 1];
+ right[state->big + state->small - 1] = 0;
p = -1;
- for (i = 0; i < 256; i++) {
- double a = right[i] + right[i + 512];
+ for (i = 0; i < state->small; i++) {
+ double a = right[i] + right[i + state->big];
if (a > best) {
best = a;
#if 0
{
/* This is some debugging code... */
- int bad = 0;
-
best = 0;
- for (i = 0; i < 256; i++)
+ for (i = 0; i < state->small; i++)
best += ((double) input[i + p]) * ((double) lastchoice[i] - avg);
- for (i = 0; i < 257; i++) {
+ for (i = 0; i <= state->small; i++) {
double tot = 0;
unsigned int j;
- for (j = 0; j < 256; j++)
- tot += ((double) input[i + j]) * ((double) lastchoice[j] - avg);
+ for (j = 0; j < state->small; j++)
+ tot += ((double) input[i + j]) * ((double) lastchoice[j] - avg);
if (tot > best)
- printf ("(%i)", i);
- if (tot != left[i + 255])
- printf ("!");
+ printf ("(%i)", i);
+ if (tot != left[i + (state->small - 1)])
+ printf ("!");
}
printf ("%i\n", p);
projects / platform / upstream / gst-plugins-good.git / blobdiff