1 files changed, 106 insertions, 88 deletions

diff --git a/mbest.c b/mbest.c
index 6216b77..9c1a6c5 100644
--- a/mbest.c
+++ b/mbest.c
@@ -27,42 +27,48 @@
 
 */
 
+#include "mbest.h"
+
 #include <assert.h>
 #include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
-#include "mbest.h"
-
 struct MBEST *mbest_create(int entries) {
-    int           i,j;
-    struct MBEST *mbest;
+  int i, j;
+  struct MBEST *mbest;
 
-    assert(entries > 0);
-    mbest = (struct MBEST *)malloc(sizeof(struct MBEST));
-    assert(mbest != NULL);
+  assert(entries > 0);
+  mbest = (struct MBEST *)malloc(sizeof(struct MBEST));
+  assert(mbest != NULL);
 
-    mbest->entries = entries;
-    mbest->list = (struct MBEST_LIST *)malloc(entries*sizeof(struct MBEST_LIST));
-    assert(mbest->list != NULL);
+  mbest->entries = entries;
+  mbest->list =
+      (struct MBEST_LIST *)malloc(entries * sizeof(struct MBEST_LIST));
+  assert(mbest->list != NULL);
 
-    for(i=0; i<mbest->entries; i++) {
-        for(j=0; j<MBEST_STAGES; j++)
-            mbest->list[i].index[j] = 0;
-        mbest->list[i].error = 1E32;
-    }
+  for (i = 0; i < mbest->entries; i++) {
+    for (j = 0; j < MBEST_STAGES; j++) mbest->list[i].index[j] = 0;
+    mbest->list[i].error = 1E32;
+  }
 
-    return mbest;
+  return mbest;
 }
 
-
 void mbest_destroy(struct MBEST *mbest) {
-    assert(mbest != NULL);
-    free(mbest->list);
-    free(mbest);
+  assert(mbest != NULL);
+  free(mbest->list);
+  free(mbest);
 }
 
+/* apply weighting to VQ for efficient VQ search */
+
+void mbest_precompute_weight(float cb[], float w[], int k, int m) {
+  for (int j = 0; j < m; j++) {
+    for (int i = 0; i < k; i++) cb[k * j + i] *= w[i];
+  }
+}
 
 /*---------------------------------------------------------------------------*\
 
@@ -75,36 +81,31 @@ void mbest_destroy(struct MBEST *mbest) {
 \*---------------------------------------------------------------------------*/
 
 void mbest_insert(struct MBEST *mbest, int index[], float error) {
-    int                i, j, found;
-    struct MBEST_LIST *list    = mbest->list;
-    int                entries = mbest->entries;
-
-    found = 0;
-    for(i=0; i<entries && !found; i++)
-        if (error < list[i].error) {
-            found = 1;
-            for(j=entries-1; j>i; j--)
-                list[j] = list[j-1];
-            for(j=0; j<MBEST_STAGES; j++)
-                list[i].index[j] = index[j];
-            list[i].error = error;
-        }
+  int i, found;
+  struct MBEST_LIST *list = mbest->list;
+  int entries = mbest->entries;
+
+  found = 0;
+  for (i = 0; i < entries && !found; i++)
+    if (error < list[i].error) {
+      found = 1;
+      memmove(&list[i + 1], &list[i],
+              sizeof(struct MBEST_LIST) * (entries - i - 1));
+      memcpy(&list[i].index[0], &index[0], sizeof(int) * MBEST_STAGES);
+      list[i].error = error;
+    }
 }
 
+void mbest_print(char title[], struct MBEST *mbest) {
+  int i, j;
 
-#ifdef MBEST_PRINT_OUT
-static void mbest_print(char title[], struct MBEST *mbest) {
-    int i,j;
-
-    fprintf(stderr, "%s\n", title);
-    for(i=0; i<mbest->entries; i++) {
-        for(j=0; j<MBEST_STAGES; j++)
-            fprintf(stderr, "  %4d ", mbest->list[i].index[j]);
-        fprintf(stderr, " %f\n", mbest->list[i].error);
-    }
+  fprintf(stderr, "%s\n", title);
+  for (i = 0; i < mbest->entries; i++) {
+    for (j = 0; j < MBEST_STAGES; j++)
+      fprintf(stderr, "  %4d ", mbest->list[i].index[j]);
+    fprintf(stderr, " %f\n", (double)mbest->list[i].error);
+  }
 }
-#endif
-
 
 /*---------------------------------------------------------------------------*\
 
@@ -115,31 +116,48 @@ static void mbest_print(char title[], struct MBEST *mbest) {
 
 \*---------------------------------------------------------------------------*/
 
-void mbest_search(
-                  const float  *cb,     /* VQ codebook to search         */
-                  float         vec[],  /* target vector                 */
-                  float         w[],    /* weighting vector              */
-                  int           k,      /* dimension of vector           */
-                  int           m,      /* number on entries in codebook */
-                  struct MBEST *mbest,  /* list of closest matches       */
-                  int           index[] /* indexes that lead us here     */
-)
-{
-   float   e;
-   int     i,j;
-   float   diff;
-
-   for(j=0; j<m; j++) {
-        e = 0.0;
-        for(i=0; i<k; i++) {
-            diff = cb[j*k+i]-vec[i];
-            e += diff*w[i]*diff*w[i];
-        }
-        index[0] = j;
-        mbest_insert(mbest, index, e);
-   }
-}
+void mbest_search(const float *cb,     /* VQ codebook to search         */
+                  float vec[],         /* target vector                 */
+                  int k,               /* dimension of vector           */
+                  int m,               /* number on entries in codebook */
+                  struct MBEST *mbest, /* list of closest matches       */
+                  int index[]          /* indexes that lead us here     */
+) {
+  int j;
+
+  /* note weighting can be applied externally by modifying cb[] and vec:
+
+    float e = 0.0;
+    for(i=0; i<k; i++)
+      e += pow(w[i]*(cb[j*k+i] - vec[i]),2.0)
+
+     |
+    \|/
+
+    for(i=0; i<k; i++)
+       e += pow(w[i]*cb[j*k+i] - w[i]*vec[i]),2.0)
+
+     |
+    \|/
 
+    for(i=0; i<k; i++)
+       e += pow(cb1[j*k+i] - vec1[i]),2.0)
+
+    where cb1[j*k+i] = w[i]*cb[j*k+i], and vec1[i] = w[i]*vec[i]
+  */
+
+  for (j = 0; j < m; j++) {
+    float e = 0.0;
+    for (int i = 0; i < k; i++) {
+      float diff = *cb++ - vec[i];
+      e += diff * diff;
+    }
+
+    index[0] = j;
+    if (e < mbest->list[mbest->entries - 1].error)
+      mbest_insert(mbest, index, e);
+  }
+}
 
 /*---------------------------------------------------------------------------*\
 
@@ -148,26 +166,26 @@ void mbest_search(
   Searches vec[] to a codebbook of vectors, and maintains a list of the mbest
   closest matches. Only searches the first NewAmp2_K Vectors
 
-  \*---------------------------------------------------------------------------*/
+\*---------------------------------------------------------------------------*/
 
-void mbest_search450(const float  *cb, float vec[], float w[], int k,int shorterK, int m, struct MBEST *mbest, int index[])
+void mbest_search450(const float *cb, float vec[], float w[], int k,
+                     int shorterK, int m, struct MBEST *mbest, int index[])
 
 {
-    float   e;
-    int     i,j;
-    float   diff;
-
-    for(j=0; j<m; j++) {
-        e = 0.0;
-        for(i=0; i<k; i++) {
-            //Only search first NEWAMP2_K Vectors
-            if(i<shorterK){
-                diff = cb[j*k+i]-vec[i];
-                e += diff*w[i] * diff*w[i];
-            }
-        }
-        index[0] = j;
-        mbest_insert(mbest, index, e);
+  float e;
+  int i, j;
+  float diff;
+
+  for (j = 0; j < m; j++) {
+    e = 0.0;
+    for (i = 0; i < k; i++) {
+      // Only search first NEWAMP2_K Vectors
+      if (i < shorterK) {
+        diff = cb[j * k + i] - vec[i];
+        e += diff * w[i] * diff * w[i];
+      }
     }
+    index[0] = j;
+    mbest_insert(mbest, index, e);
+  }
 }
-