+/*********************************************************************************/
+
+struct vectors_node {
+ oid_t oid;
+ u32 temp;
+ struct image_vector vec;
+};
+
+static uns vectors_count;
+static struct vectors_node *vectors;
+
+static void
+vectors_read(void)
+{
+ log(L_DEBUG, "Reading signature vectors");
+ struct fastbuf *fb = index_bopen("image-sig", O_RDONLY);
+ vectors_count = bgetl(fb);
+ if (vectors_count)
+ {
+ vectors = xmalloc(vectors_count * sizeof(struct vectors_node));
+ for (uns i = 0; i < vectors_count; i++)
+ {
+ bread(fb, &vectors[i].oid, sizeof(oid_t));
+ bread(fb, &vectors[i].vec, sizeof(struct image_vector));
+ bskip(fb, bgetc(fb) * sizeof(struct image_region));
+ }
+ }
+ bclose(fb);
+}
+
+static void
+vectors_cleanup(void)
+{
+ log(L_DEBUG, "Freeing signature vectors");
+ if (vectors_count)
+ xfree(vectors);
+}
+
+/*********************************************************************************/
+
+static u64 random_clusters_max_size = 500000;
+static uns random_clusters_max_count = 1000;
+
+#define RANDOM_CLUSTERS_SIZE 0x7fffffff
+#define RANDOM_CLUSTERS_LAST 0x80000000
+
+static struct random_clusters_node {
+ struct vectors_node *node;
+ s32 dot_prod;
+} *random_clusters_temp;
+static uns random_clusters_count;
+
+#define ASORT_PREFIX(x) random_clusters_##x
+#define ASORT_KEY_TYPE s32
+#define ASORT_ELT(i) start[i].dot_prod
+#define ASORT_SWAP(i,j) do { struct random_clusters_node _s = start[i]; start[i] = start[j]; start[j] = _s; } while(0)
+#define ASORT_EXTRA_ARGS , struct random_clusters_node *start
+#include "lib/arraysort.h"
+
+static void
+random_clusters_init(void)
+{
+ if (!vectors_count)
+ return;
+ log(L_INFO, "Initializing random clusters generator");
+ random_clusters_temp = xmalloc(vectors_count * sizeof(struct random_clusters_node));
+ for (uns i = 0; i < vectors_count; i++)
+ random_clusters_temp[i].node = vectors + i;
+}
+
+static void
+random_clusters_build(void)
+{
+ random_clusters_count = 0;
+ if (!vectors_count)
+ return;
+
+ log(L_INFO, "Generating random clusters for duplicates comparision");
+
+ for (uns i = 0; i < vectors_count; i++)
+ vectors[i].temp &= RANDOM_CLUSTERS_SIZE;
+
+ /* Initialize recursion */
+ struct stk {
+ uns count;
+ struct random_clusters_node *start;
+ } stk_top[64], *stk = stk_top + 1;
+ stk->start = random_clusters_temp;
+ stk->count = vectors_count;
+
+ /* Main loop */
+ while (stk != stk_top)
+ {
+ /* Split conditions */
+ uns split;
+ if (stk->count < 2)
+ split = 0;
+ else if (stk->count > random_clusters_max_count)
+ split = 1;
+ else
+ {
+ s64 size = random_clusters_max_size;
+ for (uns i = 0; i < stk->count && size >= 0; i++)
+ size -= stk->start[i].node->temp;
+ split = size < 0;
+ }
+
+ /* BSP leaf node */
+ if (!split)
+ {
+ stk->start[stk->count - 1].node->temp |= RANDOM_CLUSTERS_LAST;
+ random_clusters_count++;
+ stk--;
+ }
+
+ /* BSP internal node */
+ else
+ {
+ /* Generate random normal vector of the splitting plane */
+ int normal[IMAGE_VEC_K];
+ for (uns i = 0; i < IMAGE_VEC_K; i++)
+ normal[i] = random_max(0x20001) - 0x10000;
+
+ /* Compute dot produts */
+ for (uns i = 0; i < stk->count; i++)
+ {
+ stk->start[i].dot_prod = 0;
+ for (uns j = 0; j < IMAGE_VEC_K; j++)
+ stk->start[i].dot_prod += normal[j] * stk->start[i].node->vec.f[j];
+ }
+
+ /* Sort... could be faster, because we only need the median */
+ random_clusters_sort(stk->count, stk->start);
+
+ /* Split in the middle */
+ stk[1].count = stk[0].count >> 1;
+ stk[0].count -= stk[1].count;
+ stk[1].start = stk[0].start;
+ stk[0].start += stk[1].count;
+ stk++;
+ }
+ }
+ log(L_INFO, "Generated %u clusters", random_clusters_count);
+}
+
+static void
+random_clusters_cleanup(void)
+{
+ if (vectors_count)
+ xfree(random_clusters_temp);
+}
+
+/*********************************************************************************/
+
+// FIXME: use vectors_read()... duplicate code
+