images/image-idx.c

   1 // FIXME: this file is full of experiments... will be completely different in final version
   2
   3 #undef LOCAL_DEBUG
   4
   5 #include "sherlock/sherlock.h"
   6 #include "lib/mempool.h"
   7 #include "lib/conf.h"
   8 #include "lib/getopt.h"
   9 #include "lib/fastbuf.h"
  10 #include "lib/chartype.h"
  11 #include "sherlock/object.h"
  12 #include "lib/url.h"
  13 #include "lib/unicode.h"
  14 #include "sherlock/lizard-fb.h"
  15 #include "sherlock/tagged-text.h"
  16 #include "charset/charconv.h"
  17 #include "charset/unicat.h"
  18 #include "charset/fb-charconv.h"
  19 #include "indexer/indexer.h"
  20 #include "indexer/lexicon.h"
  21 #include "indexer/params.h"
  22 #include "utils/dumpconfig.h"
  23 #include "lang/lang.h"
  24 #include "lib/base224.h"
  25 #include "lib/bbuf.h"
  26 #include "lib/clists.h"
  27
  28 #include "images/images.h"
  29 #include "images/image-obj.h"
  30 #include "images/image-sig.h"
  31 #include "images/dup-cmp.h"
  32 #include "images/kd-tree.h"
  33 #include "images/color.h"
  34
  35 #include <stdlib.h>
  36 #include <fcntl.h>
  37 #include <string.h>
  38
  39 static struct fastbuf *fb_cards;
  40 static struct fastbuf *fb_card_attrs;
  41 static struct buck2obj_buf *buck2obj;
  42
  43 /* This should happen in gatherer or scanner */
  44 static void
  45 generate_signatures(uns limit)
  46 {
  47   fb_cards = index_bopen("cards", O_RDONLY);
  48   fb_card_attrs = index_bopen("card-attrs", O_RDONLY);
  49   struct fastbuf *fb_signatures = index_bopen("image-sig", O_CREAT | O_WRONLY | O_TRUNC);
  50   struct card_attr ca;
  51   struct image_signature sig;
  52   struct mempool *pool = mp_new(1 << 16);
  53   struct buck2obj_buf *bob = buck2obj_alloc();
  54   uns count = 0;
  55
  56   if (limit == ~0U)
  57     log(L_INFO, "Generating image signatures");
  58   else
  59     log(L_INFO, "Generating at most %d image signatures", limit);
  60   bputl(fb_signatures, 0);
  61   imo_decompress_thumbnails_init();
  62
  63   for (oid_t oid = 0; bread(fb_card_attrs, &ca, sizeof(ca)); oid++)
  64     if ((uns)((ca.type_flags >> 4) - 8) < 4)
  65       {
  66         bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT);
  67         uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
  68         uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
  69         mp_flush(pool);
  70         struct odes *obj = obj_read_bucket(bob, pool, buck_type, buck_len, fb_cards, NULL);
  71         struct oattr *attr;
  72         if (!obj)
  73           die("Failed to read card");
  74         if (attr = obj_find_attr(obj, 'N'))
  75           {
  76 #ifdef LOCAL_DEBUG
  77             byte *url = obj_find_aval(obj_find_attr(obj, 'U' + OBJ_ATTR_SON)->son, 'U');
  78             DBG("Reading oid=%d url=%s", oid, url);
  79 #endif
  80             struct image_obj imo;
  81             imo_init(&imo, pool, obj);
  82             if (imo_decompress_thumbnail(&imo))
  83               {
  84                 if (compute_image_signature(&imo.thumb, &sig))
  85                   {
  86                     bwrite(fb_signatures, &oid, sizeof(oid));
  87                     bwrite(fb_signatures, &sig.vec, sizeof(struct image_vector));
  88                     bputc(fb_signatures, sig.len);
  89                     if (sig.len)
  90                       bwrite(fb_signatures, sig.reg, sig.len * sizeof(struct image_region));
  91                     count++;
  92                     if (count % 10000 == 0)
  93                       log(L_DEBUG, "... passed %d images", count);
  94                     if (count >= limit)
  95                       break;
  96                   }
  97                 else
  98                   DBG("Cannot create signature");
  99               }
 100             else
 101               DBG("Cannot decompress thumbnail");
 102           }
 103       }
 104   brewind(fb_signatures);
 105   bputl(fb_signatures, count);
 106   DBG("%d signatures written", count);
 107
 108   imo_decompress_thumbnails_done();
 109   buck2obj_free(bob);
 110   mp_delete(pool);
 111   bclose(fb_cards);
 112   bclose(fb_card_attrs);
 113   bclose(fb_signatures);
 114 }
 115
 116 /*********************************************************************************/
 117
 118 struct vectors_node {
 119   oid_t oid;
 120   u32 temp;
 121   struct image_vector vec;
 122 };
 123
 124 static uns vectors_count;
 125 static struct vectors_node *vectors;
 126
 127 static void
 128 vectors_read(void)
 129 {
 130   log(L_DEBUG, "Reading signature vectors");
 131   struct fastbuf *fb = index_bopen("image-sig", O_RDONLY);
 132   vectors_count = bgetl(fb);
 133   if (vectors_count)
 134     {
 135       vectors = xmalloc(vectors_count * sizeof(struct vectors_node));
 136       for (uns i = 0; i < vectors_count; i++)
 137         {
 138           bread(fb, &vectors[i].oid, sizeof(oid_t));
 139           bread(fb, &vectors[i].vec, sizeof(struct image_vector));
 140           bskip(fb, bgetc(fb) * sizeof(struct image_region));
 141         }
 142     }
 143   bclose(fb);
 144 }
 145
 146 static void
 147 vectors_cleanup(void)
 148 {
 149   log(L_DEBUG, "Freeing signature vectors");
 150   if (vectors_count)
 151     xfree(vectors);
 152 }
 153
 154 /*********************************************************************************/
 155
 156 static u64 random_clusters_max_size = 500000;
 157 static uns random_clusters_max_count = 1000;
 158
 159 #define RANDOM_CLUSTERS_SIZE    0x7fffffff
 160 #define RANDOM_CLUSTERS_LAST    0x80000000
 161
 162 static struct random_clusters_node {
 163   struct vectors_node *node;
 164   s32 dot_prod;
 165 } *random_clusters_temp;
 166 static uns random_clusters_count;
 167
 168 #define ASORT_PREFIX(x) random_clusters_##x
 169 #define ASORT_KEY_TYPE s32
 170 #define ASORT_ELT(i) start[i].dot_prod
 171 #define ASORT_SWAP(i,j) do { struct random_clusters_node _s = start[i]; start[i] = start[j]; start[j] = _s; } while(0)
 172 #define ASORT_EXTRA_ARGS , struct random_clusters_node *start
 173 #include "lib/arraysort.h"
 174
 175 static void
 176 random_clusters_init(void)
 177 {
 178   if (!vectors_count)
 179     return;
 180   log(L_INFO, "Initializing random clusters generator");
 181   random_clusters_temp = xmalloc(vectors_count * sizeof(struct random_clusters_node));
 182   for (uns i = 0; i < vectors_count; i++)
 183     random_clusters_temp[i].node = vectors + i;
 184 }
 185
 186 static void
 187 random_clusters_build(void)
 188 {
 189   random_clusters_count = 0;
 190   if (!vectors_count)
 191     return;
 192
 193   log(L_INFO, "Generating random clusters for duplicates comparision");
 194
 195   for (uns i = 0; i < vectors_count; i++)
 196     vectors[i].temp &= RANDOM_CLUSTERS_SIZE;
 197
 198   /* Initialize recursion */
 199   struct stk {
 200     uns count;
 201     struct random_clusters_node *start;
 202   } stk_top[64], *stk = stk_top + 1;
 203   stk->start = random_clusters_temp;
 204   stk->count = vectors_count;
 205
 206   /* Main loop */
 207   while (stk != stk_top)
 208     {
 209       /* Split conditions */
 210       uns split;
 211       if (stk->count < 2)
 212         split = 0;
 213       else if (stk->count > random_clusters_max_count)
 214         split = 1;
 215       else
 216         {
 217           s64 size = random_clusters_max_size;
 218           for (uns i = 0; i < stk->count && size >= 0; i++)
 219             size -= stk->start[i].node->temp;
 220           split = size < 0;
 221         }
 222
 223       /* BSP leaf node */
 224       if (!split)
 225         {
 226           stk->start[stk->count - 1].node->temp |= RANDOM_CLUSTERS_LAST;
 227           random_clusters_count++;
 228           stk--;
 229         }
 230
 231       /* BSP internal node */
 232       else
 233         {
 234           /* Generate random normal vector of the splitting plane */
 235           int normal[IMAGE_VEC_K];
 236           for (uns i = 0; i < IMAGE_VEC_K; i++)
 237             normal[i] = random_max(0x20001) - 0x10000;
 238
 239           /* Compute dot produts */
 240           for (uns i = 0; i < stk->count; i++)
 241             {
 242               stk->start[i].dot_prod = 0;
 243               for (uns j = 0; j < IMAGE_VEC_K; j++)
 244                 stk->start[i].dot_prod += normal[j] * stk->start[i].node->vec.f[j];
 245             }
 246
 247           /* Sort... could be faster, because we only need the median */
 248           random_clusters_sort(stk->count, stk->start);
 249
 250           /* Split in the middle */
 251           stk[1].count = stk[0].count >> 1;
 252           stk[0].count -= stk[1].count;
 253           stk[1].start = stk[0].start;
 254           stk[0].start += stk[1].count;
 255           stk++;
 256         }
 257     }
 258   log(L_INFO, "Generated %u clusters", random_clusters_count);
 259 }
 260
 261 static void
 262 random_clusters_cleanup(void)
 263 {
 264   if (vectors_count)
 265     xfree(random_clusters_temp);
 266 }
 267
 268 /*********************************************************************************/
 269
 270 // FIXME: use vectors_read()... duplicate code
 271
 272 struct signature_record {
 273   oid_t oid;
 274   struct image_vector vec;
 275 };
 276
 277 #define ASORT_PREFIX(x) build_search_tree_##x
 278 #define ASORT_KEY_TYPE struct signature_record *
 279 #define ASORT_ELT(i) rec[i]
 280 #define ASORT_LT(x,y) x->vec.f[dim] < y->vec.f[dim]
 281 #define ASORT_EXTRA_ARGS , uns dim, struct signature_record **rec
 282 #include "lib/arraysort.h"
 283
 284 #if 0
 285 #define DBG_KD(x...) DBG(x)
 286 #else
 287 #define DBG_KD(x...) do{}while(0)
 288 #endif
 289
 290 static struct image_tree tree;
 291 static struct signature_record *records;
 292 static struct signature_record **precords;
 293
 294 static void
 295 build_kd_tree(void)
 296 {
 297   log(L_INFO, "Building KD-tree");
 298
 299   struct fastbuf *fb_signatures = index_bopen("image-sig", O_RDONLY);
 300   tree.count = bgetl(fb_signatures);
 301   ASSERT(tree.count < 0x80000000);
 302   if (!tree.count)
 303     {
 304       /* FIXME */
 305       bclose(fb_signatures);
 306       die("There are no signatures");
 307     }
 308   else
 309     {
 310       DBG("Reading %d signatures", tree.count);
 311       records = xmalloc(tree.count * sizeof(struct signature_record));
 312       precords = xmalloc(tree.count * sizeof(void *));
 313       for (uns i = 0; i < tree.count; i++)
 314         {
 315           bread(fb_signatures, &records[i].oid, sizeof(oid_t));
 316           bread(fb_signatures, &records[i].vec, sizeof(struct image_vector));
 317           uns len = bgetc(fb_signatures);
 318           bskip(fb_signatures, len * sizeof(struct image_region));
 319           precords[i] = records + i;
 320           if (likely(i))
 321             for (uns j = 0; j < IMAGE_VEC_K; j++)
 322               {
 323                 tree.bbox.vec[0].f[j] = MIN(tree.bbox.vec[0].f[j], records[i].vec.f[j]);
 324                 tree.bbox.vec[1].f[j] = MAX(tree.bbox.vec[1].f[j], records[i].vec.f[j]);
 325               }
 326           else
 327             tree.bbox.vec[0] = tree.bbox.vec[1] = records[0].vec;
 328         }
 329       bclose(fb_signatures);
 330
 331       for (tree.depth = 1; (uns)(2 << tree.depth) < tree.count; tree.depth++);
 332       DBG("depth=%d nodes=%d bbox=[(%s), (%s)]", tree.depth, 1 << tree.depth,
 333           stk_print_image_vector(tree.bbox.vec + 0), stk_print_image_vector(tree.bbox.vec + 1));
 334       uns leaves_index = 1 << (tree.depth - 1);
 335       tree.nodes = xmalloc_zero((1 << tree.depth) * sizeof(struct image_node));
 336       tree.leaves = xmalloc_zero(tree.count * sizeof(struct image_leaf));
 337
 338       /* Initialize recursion */
 339       struct stk {
 340         struct image_bbox bbox;
 341         uns index, count;
 342         struct signature_record **start;
 343       } stk_top[32], *stk = stk_top + 1;
 344       stk->index = 1;
 345       stk->start = precords;
 346       stk->count = tree.count;
 347       stk->bbox.vec[0] = tree.bbox.vec[0];
 348       for (uns i = 0; i < IMAGE_VEC_K; i++)
 349         stk->bbox.vec[1].f[i] = tree.bbox.vec[1].f[i] - tree.bbox.vec[0].f[i];
 350       uns entry_index = 0;
 351
 352       /* Main loop */
 353       while (stk != stk_top)
 354         {
 355           DBG_KD("Main loop... depth=%d index=%d count=%d, start=%d, min=%s dif=%s",
 356               stk - stk_top, stk->index, stk->count, stk->start - precords,
 357               stk_print_image_vector(stk->bbox.vec + 0), stk_print_image_vector(stk->bbox.vec + 1));
 358           ASSERT(stk->count);
 359
 360           /* Create leaf node */
 361           if (stk->index >= leaves_index || stk->count < 2)
 362             {
 363               tree.nodes[stk->index].val = IMAGE_NODE_LEAF | entry_index;
 364               for (; stk->count--; stk->start++)
 365                 {
 366                   struct image_leaf *leaf = &tree.leaves[entry_index++];
 367                   struct signature_record *record = *stk->start;
 368                   leaf->oid = record->oid;
 369                   leaf->flags = 0;
 370                   for (uns i = IMAGE_VEC_K; i--; )
 371                     {
 372                       uns bits = IMAGE_LEAF_BITS(i);
 373                       leaf->flags <<= bits;
 374                       if (stk->bbox.vec[1].f[i])
 375                         {
 376                           uns value =
 377                             (record->vec.f[i] - stk->bbox.vec[0].f[i]) *
 378                             ((1 << bits) - 1) / stk->bbox.vec[1].f[i];
 379                           ASSERT(value < (uns)(1 << bits));
 380                           leaf->flags |= value;
 381                         }
 382                     }
 383                   if (!stk->count)
 384                     leaf->flags |= IMAGE_LEAF_LAST;
 385                   DBG_KD("Creating leaf node; oid=%d vec=(%s) flags=0x%08x",
 386                       leaf->oid, stk_print_image_vector(&record->vec), leaf->flags);
 387                 }
 388               stk--;
 389             }
 390
 391           /* Create internal node */
 392           else
 393             {
 394               /* Select dimension to splis */
 395               uns dim = 0;
 396               for (uns i = 1; i < IMAGE_VEC_K; i++)
 397                 if (stk->bbox.vec[1].f[i] > stk->bbox.vec[1].f[dim])
 398                   dim = i;
 399
 400               /* Sort... FIXME: we only need the median */
 401               build_search_tree_sort(stk->count, dim, stk->start);
 402
 403               /* Split in the middle */
 404               uns index = stk->index;
 405               stk[1].index = stk[0].index * 2;
 406               stk[0].index = stk[1].index + 1;
 407               stk[1].count = stk[0].count >> 1;
 408               stk[0].count -= stk[1].count;
 409               stk[1].start = stk[0].start;
 410               stk[0].start += stk[1].count;
 411
 412               /* Choose split value */
 413               uns lval = stk->start[-1]->vec.f[dim];
 414               uns rval = stk->start[0]->vec.f[dim];
 415               uns pivot = stk->bbox.vec[0].f[dim] + (stk->bbox.vec[1].f[dim] >> 1);
 416               if (pivot <= lval)
 417                 pivot = lval;
 418               else if (pivot >= rval)
 419                 pivot = rval;
 420
 421               DBG_KD("Created internal node; dim=%d pivot=%d", dim, pivot);
 422
 423               /* Split the box */
 424               stk[1].bbox = stk[0].bbox;
 425               stk[1].bbox.vec[1].f[dim] = pivot - stk[0].bbox.vec[0].f[dim];
 426               stk[0].bbox.vec[0].f[dim] += stk[1].bbox.vec[1].f[dim];
 427               stk[0].bbox.vec[1].f[dim] -= stk[1].bbox.vec[1].f[dim];
 428
 429               /* Fill the node structure */
 430               tree.nodes[index].val = dim + (pivot << 8);
 431               stk++;
 432             }
 433         }
 434
 435       DBG("Tree constructed, saving...");
 436
 437       struct fastbuf *fb_tree = index_bopen("image-tree", O_CREAT | O_WRONLY | O_TRUNC);
 438       bputl(fb_tree, tree.count);
 439       bputl(fb_tree, tree.depth);
 440       bwrite(fb_tree, &tree.bbox, sizeof(struct image_bbox));
 441       bwrite(fb_tree, tree.nodes + 1, ((1 << tree.depth) - 1) * sizeof(struct image_node));
 442       bwrite(fb_tree, tree.leaves, tree.count * sizeof(struct image_leaf));
 443       bclose(fb_tree);
 444
 445       //xfree(tree.leaves);
 446       //xfree(tree.nodes);
 447       //xfree(precords);
 448       //xfree(records);
 449     }
 450 }
 451
 452 /*********************************************************************************/
 453
 454 struct pass1_hilbert {
 455   u32 index;
 456   struct image_vector vec;
 457 };
 458
 459 struct pass1_node {
 460   cnode lru_node;
 461   cnode buf_node;
 462   uns buf_size;
 463   byte *buf;
 464   oid_t oid;
 465   byte *url;
 466   struct image_data image;
 467   struct image_dup dup;
 468 };
 469
 470 static uns pass1_buf_size = 400 << 20;
 471 static uns pass1_max_count = 100000;
 472 static uns pass1_search_dist = 40;
 473 static uns pass1_search_count = 500;
 474
 475 static struct mempool *pass1_pool;
 476 static struct pass1_hilbert *pass1_hilbert_list;
 477 static byte *pass1_buf_start;
 478 static byte *pass1_buf_pos;
 479 static uns pass1_buf_free;
 480 static uns pass1_buf_used;
 481 static clist pass1_buf_list;
 482 static clist pass1_lru_list;
 483 static u64 pass1_lookups;
 484 static u64 pass1_reads;
 485 static u64 pass1_pairs;
 486 static u64 pass1_dups;
 487 static u64 pass1_shrinks;
 488 static u64 pass1_alloc_sum;
 489
 490 #define HILBERT_PREFIX(x) pass1_hilbert_##x
 491 #define HILBERT_TYPE byte
 492 #define HILBERT_ORDER 8
 493 #define HILBERT_DIM IMAGE_VEC_K
 494 #define HILBERT_WANT_ENCODE
 495 #include "images/hilbert.h"
 496
 497 #define ASORT_PREFIX(x) pass1_hilbert_sort_##x
 498 #define ASORT_KEY_TYPE struct image_vector *
 499 #define ASORT_ELT(i) (&pass1_hilbert_list[i].vec)
 500 #define ASORT_LT(x,y) (memcmp(x, y, sizeof(*x)) < 0)
 501 #define ASORT_SWAP(i,j) do { struct pass1_hilbert _s;           \
 502                 _s = pass1_hilbert_list[i];                     \
 503                 pass1_hilbert_list[i] = pass1_hilbert_list[j];  \
 504                 pass1_hilbert_list[j] = _s; } while(0)
 505 #include "lib/arraysort.h"
 506
 507 static void
 508 pass1_hilbert_sort(void)
 509 {
 510   DBG("Computing positions on the Hilbert curve");
 511   pass1_hilbert_list = xmalloc(tree.count * sizeof(struct pass1_hilbert));
 512   for (uns i = 0; i < tree.count; i++)
 513     {
 514       struct pass1_hilbert *h = pass1_hilbert_list + i;
 515       h->index = i;
 516       byte vec[IMAGE_VEC_K];
 517       pass1_hilbert_encode(vec, precords[i]->vec.f);
 518       for (uns j = 0; j < IMAGE_VEC_K; j++)
 519         h->vec.f[j] = vec[IMAGE_VEC_K - 1 - j];
 520     }
 521   DBG("Sorting signatures in order of incresing parameters on the Hilbert curve");
 522   pass1_hilbert_sort_sort(tree.count);
 523 #if 0
 524   for (uns i = 0; i < tree.count; i++)
 525     {
 526       if (i)
 527         {
 528           byte *v1 = precords[pass1_hilbert_list[i - 1].index]->vec.f;
 529           byte *v2 = precords[pass1_hilbert_list[i].index]->vec.f;
 530 #define SQR(x) ((x)*(x))
 531            uns dist = 0;
 532           for (uns j = 0; j < 6; j++)
 533             dist += SQR(v1[j] - v2[j]);
 534           DBG("dist %d", dist);
 535         }
 536       DBG("index %d", pass1_hilbert_list[i].index);
 537     }
 538 #endif
 539 }
 540
 541 static void
 542 pass1_hilbert_cleanup(void)
 543 {
 544   xfree(pass1_hilbert_list);
 545 }
 546
 547 #define HASH_PREFIX(x) pass1_hash_##x
 548 #define HASH_NODE struct pass1_node
 549 #define HASH_KEY_ATOMIC oid
 550 #define HASH_WANT_CLEANUP
 551 #define HASH_WANT_FIND
 552 #define HASH_WANT_NEW
 553 #define HASH_WANT_REMOVE
 554 #include "lib/hashtable.h"
 555
 556 static inline void
 557 pass1_buf_init(void)
 558 {
 559   //DBG("pass1_buf_init()");
 560   pass1_buf_free = pass1_buf_size;
 561   pass1_buf_start = pass1_buf_pos = xmalloc(pass1_buf_size);
 562   pass1_buf_used = 0;
 563 }
 564
 565 static inline void
 566 pass1_buf_cleanup(void)
 567 {
 568   //DBG("pass1_buf_cleanup()");
 569   xfree(pass1_buf_start);
 570 }
 571
 572 static void
 573 pass1_node_free(struct pass1_node *node)
 574 {
 575   //DBG("pass1_node_free(%d)", (uns)node->oid);
 576   if (node->buf_size)
 577     {
 578       pass1_buf_used -= node->buf_size;
 579       clist_remove(&node->buf_node);
 580     }
 581   clist_remove(&node->lru_node);
 582   pass1_hash_remove(node);
 583 }
 584
 585 static inline void
 586 pass1_node_free_lru(void)
 587 {
 588   ASSERT(!clist_empty(&pass1_lru_list));
 589   pass1_node_free(SKIP_BACK(struct pass1_node, lru_node, clist_head(&pass1_lru_list)));
 590 }
 591
 592 static inline void
 593 pass1_node_after_move(struct pass1_node *node, addr_int_t move)
 594 {
 595   //DBG("pass1_node_after_mode(%d, %d)", (uns)node->oid, (uns)move);
 596   /* adjust internal pointers */
 597 #define MOVE(x) x = (byte *)(x) - move
 598   MOVE(node->url);
 599   MOVE(node->image.pixels);
 600   MOVE(node->dup.buf);
 601 #undef MOVE
 602 }
 603
 604 static inline void
 605 pass1_buf_shrink(void)
 606 {
 607   DBG("pass1_buf_shrink()");
 608   pass1_shrinks++;
 609   pass1_buf_free = pass1_buf_size;
 610   pass1_buf_pos = pass1_buf_start;
 611   CLIST_FOR_EACH(void *, p, pass1_buf_list)
 612     {
 613       struct pass1_node *node = SKIP_BACK(struct pass1_node, buf_node, p);
 614       if (node->buf != pass1_buf_pos)
 615         {
 616           memmove(pass1_buf_pos, node->buf, node->buf_size);
 617           pass1_node_after_move(node, node->buf - pass1_buf_pos);
 618           node->buf = pass1_buf_pos;
 619         }
 620       pass1_buf_pos += node->buf_size;
 621       pass1_buf_free -= node->buf_size;
 622     }
 623 }
 624
 625 static void *
 626 pass1_buf_alloc(uns size)
 627 {
 628   //DBG("pass1_buf_alloc(%d)", size);
 629
 630   /* if there is not enough free space at the end of the buffer */
 631   if (size > pass1_buf_free)
 632     {
 633       /* free some lru nodes */
 634       //DBG("freeing lru nodes");
 635       while (size > pass1_buf_size - pass1_buf_used || pass1_buf_used > pass1_buf_size / 2)
 636         {
 637           if (unlikely(clist_empty(&pass1_lru_list))) // FIXME
 638             die("Buffer too small");
 639           pass1_node_free_lru();
 640         }
 641
 642       pass1_buf_shrink();
 643     }
 644
 645   /* final allocation */
 646   void *result = pass1_buf_pos;
 647   pass1_buf_pos += size;
 648   pass1_buf_free -= size;
 649   pass1_buf_used += size;
 650   pass1_alloc_sum += size;
 651   return result;
 652 }
 653
 654 static struct pass1_node *
 655 pass1_node_new(oid_t oid)
 656 {
 657   DBG("pass1_node_new(%d)", (uns)oid);
 658   if (pass1_hash_table.hash_count == pass1_max_count)
 659     pass1_node_free_lru();
 660   struct pass1_node *node = pass1_hash_new(oid);
 661   mp_flush(pass1_pool);
 662   pass1_reads++;
 663
 664   /* read object */
 665   struct card_attr ca;
 666   bsetpos(fb_card_attrs, (sh_off_t)oid * sizeof(ca)); /* FIXME: these seeks can be easily removed */
 667   bread(fb_card_attrs, &ca, sizeof(ca));
 668
 669   bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT); /* FIXME: maybe a presort should handle these random seeks */
 670   uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
 671   uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
 672   struct odes *obj = obj_read_bucket(buck2obj, pass1_pool, buck_type, buck_len, fb_cards, NULL);
 673   if (unlikely(!obj))
 674     die("Failed to read card");
 675   byte *url = obj_find_aval(obj_find_attr(obj, 'U' + OBJ_ATTR_SON)->son, 'U');
 676   uns url_len = strlen(url);
 677
 678   /* decompress thumbnail */
 679   struct image_obj imo;
 680   imo_init(&imo, pass1_pool, obj);
 681   if (unlikely(!imo_decompress_thumbnail(&imo)))
 682     die("Cannot decompress thumbnail");
 683   node->image = imo.thumb;
 684
 685   /* create duplicates comparision object */
 686   image_dup_init(&node->dup, &node->image, pass1_pool);
 687
 688   /* copy data */
 689   //DBG("loaded image %s s=%d d=%d", url, node->image.size, node->dup.buf_size);
 690   node->buf_size = node->image.size + node->dup.buf_size + url_len + 1;
 691   if (node->buf_size)
 692     {
 693       byte *buf = node->buf = pass1_buf_alloc(node->buf_size);
 694       clist_add_tail(&pass1_buf_list, &node->buf_node);
 695 #define COPY(ptr, size) ({ void *_p=buf; uns _size=(size); buf+=_size; memcpy(_p,(ptr),_size); _p; })
 696       node->url = COPY(url, url_len + 1);
 697       node->image.pixels = COPY(node->image.pixels, node->image.size);
 698       node->dup.buf = COPY(node->dup.buf, node->dup.buf_size);
 699 #undef COPY
 700     }
 701
 702   /* add to lru list */
 703   return node;
 704 }
 705
 706 static inline struct pass1_node *
 707 pass1_node_lock(oid_t oid)
 708 {
 709   DBG("pass1_node_lock(%d)", (uns)oid);
 710   pass1_lookups++;
 711   struct pass1_node *node = pass1_hash_find(oid);
 712   if (node)
 713     {
 714       clist_remove(&node->lru_node);
 715       return node;
 716     }
 717   else
 718     return pass1_node_new(oid);
 719 }
 720
 721 static inline void
 722 pass1_node_unlock(struct pass1_node *node)
 723 {
 724   //DBG("pass1_node_unlock(%d)", (uns)node->oid);
 725   clist_add_tail(&pass1_lru_list, &node->lru_node);
 726 }
 727
 728 static void
 729 pass1_show_stats(void)
 730 {
 731   log(L_INFO, "%d count, %Ld lookups, %Ld reads, %Ld pairs, %Ld dups, %Ld shrinks", tree.count,
 732     (long long int)pass1_lookups, (long long int)pass1_reads,
 733     (long long int)pass1_pairs, (long long int)pass1_dups, (long long int)pass1_shrinks);
 734 }
 735
 736 static void
 737 pass1(void)
 738 {
 739   log(L_INFO, "Looking for duplicates");
 740   ASSERT(tree.nodes);
 741
 742   /* initialization */
 743   pass1_lookups = pass1_reads = pass1_pairs = pass1_dups = pass1_shrinks = pass1_alloc_sum = 0;
 744   fb_cards = bopen("index/cards", O_RDONLY, 10000); // FIXME
 745   fb_card_attrs = bopen("index/card-attrs", O_RDONLY, sizeof(struct card_attr)); // FIXME
 746   buck2obj = buck2obj_alloc();
 747   imo_decompress_thumbnails_init();
 748   clist_init(&pass1_lru_list);
 749   clist_init(&pass1_buf_list);
 750   pass1_hash_init();
 751   pass1_buf_init();
 752   pass1_pool = mp_new(1 << 20);
 753
 754   /* Hilbert sort */
 755   pass1_hilbert_sort();
 756   pass1_hilbert_cleanup();
 757
 758   /* main loop */
 759   for (uns i = 0; i < tree.count; )
 760     {
 761       /* lookup next image */
 762       oid_t oid = tree.leaves[i].oid;
 763       struct pass1_node *node = pass1_node_lock(oid);
 764
 765       /* compare with all near images */
 766       struct image_search search;
 767       image_search_init(&search, &tree, &precords[i]->vec, pass1_search_dist);
 768       /* FIXME: can be faster than general search in KD-tree */
 769       oid_t oid2;
 770       uns dist;
 771       for (uns j = 0; j < pass1_search_count && image_search_next(&search, &oid2, &dist); j++)
 772         {
 773           if (oid < oid2)
 774             {
 775               struct pass1_node *node2 = pass1_node_lock(oid2);
 776               DBG("comparing %d and %d", oid, oid2);
 777               if (image_dup_compare(&node->dup, &node2->dup, IMAGE_DUP_TRANS_ID))
 778                 {
 779                   pass1_dups++;
 780                   log(L_DEBUG, "*** Found duplicates oid1=0x%x oid=0x%x", (uns)node->oid, (uns)node2->oid);
 781                   log(L_DEBUG, "  %s", node->url);
 782                   log(L_DEBUG, "  %s", node2->url);
 783                 }
 784               pass1_pairs++;
 785               pass1_node_unlock(node2);
 786             }
 787         }
 788       image_search_done(&search);
 789       pass1_node_unlock(node);
 790       i++;
 791       if (i % 1000 == 0)
 792         log(L_DEBUG, "... passed %d images", i);
 793     }
 794
 795   /* clean up */
 796   pass1_hash_cleanup();
 797   pass1_buf_cleanup();
 798   mp_delete(pass1_pool);
 799   bclose(fb_cards);
 800   bclose(fb_card_attrs);
 801   buck2obj_free(buck2obj);
 802   imo_decompress_thumbnails_done();
 803
 804   /* print statistics */
 805   pass1_show_stats();
 806 }
 807
 808 /*********************************************************************************/
 809
 810 static uns pass2_clusterings_count = 1;
 811
 812 static void
 813 pass2_estimate_sizes(void)
 814 {
 815   if (!vectors_count)
 816     return;
 817   log(L_DEBUG, "Reading image sizes");
 818
 819   /* FIXME: hack, these reads are not necessary, can be done in previous phases */
 820   struct fastbuf *fb_cards = index_bopen("cards", O_RDONLY);
 821   struct fastbuf *fb_card_attrs = index_bopen("card-attrs", O_RDONLY);
 822   struct mempool *pool = mp_new(1 << 16);
 823   struct buck2obj_buf *bob = buck2obj_alloc();
 824
 825   for (uns i = 0; i < vectors_count; i++)
 826     {
 827       oid_t oid = vectors[i].oid;
 828       struct card_attr ca;
 829       bsetpos(fb_card_attrs, (sh_off_t)oid * sizeof(ca));
 830       bread(fb_card_attrs, &ca, sizeof(ca));
 831       bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT);
 832       uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
 833       uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
 834       mp_flush(pool);
 835       struct odes *obj = obj_read_bucket(bob, pool, buck_type, buck_len, fb_cards, NULL);
 836       byte *attr = obj_find_aval(obj, 'G');
 837       ASSERT(attr);
 838       uns image_width, image_height, image_colors, thumb_width, thumb_height;
 839       byte color_space[MAX_ATTR_SIZE];
 840       sscanf(attr, "%d%d%s%d%d%d", &image_width, &image_height, color_space, &image_colors, &thumb_width, &thumb_height);
 841       vectors[i].temp = image_dup_estimate_size(thumb_width, thumb_height) +
 842         sizeof(struct image_data) + thumb_width * thumb_height * 3;
 843     }
 844   buck2obj_free(bob);
 845   mp_delete(pool);
 846   bclose(fb_cards);
 847   bclose(fb_card_attrs);
 848 }
 849
 850 static void
 851 pass2(void)
 852 {
 853   // FIXME: presorts, much allocated memory when not needed
 854   vectors_read();
 855   pass2_estimate_sizes();
 856   random_clusters_init();
 857   for (uns clustering = 0; clustering < pass2_clusterings_count; clustering++)
 858     {
 859       random_clusters_build();
 860       // FIXME
 861       // - external sort
 862       // - generate and compare pairs in clusters
 863     }
 864   random_clusters_cleanup();
 865   vectors_cleanup();
 866 }
 867
 868 /*********************************************************************************/
 869
 870 static char *shortopts = CF_SHORT_OPTS "";
 871 static struct option longopts[] =
 872 {
 873   CF_LONG_OPTS
 874   { NULL, 0, 0, 0 }
 875 };
 876
 877 static char *help = "\
 878 Usage: image-indexer [<options>]\n\
 879 \n\
 880 Options:\n" CF_USAGE;
 881
 882 static void NONRET
 883 usage(byte *msg)
 884 {
 885   if (msg)
 886   {
 887     fputs(msg, stderr);
 888     fputc('\n', stderr);
 889   }
 890   fputs(help, stderr);
 891   exit(1);
 892 }
 893
 894
 895 int
 896 main(int argc UNUSED, char **argv)
 897 {
 898   int opt;
 899
 900   log_init(argv[0]);
 901   while ((opt = cf_getopt(argc, argv, shortopts, longopts, NULL)) >= 0)
 902     switch (opt)
 903     {
 904       default:
 905       usage("Invalid option");
 906     }
 907   if (optind != argc)
 908     usage("Invalid usage");
 909
 910   srgb_to_luv_init();
 911
 912   generate_signatures(20000);
 913   build_kd_tree();
 914   //pass1();
 915   pass2();
 916
 917   return 0;
 918 }