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 #if 0
 455
 456 struct pass1_hilbert {
 457   u32 index;
 458   struct image_vector vec;
 459 };
 460
 461 struct pass1_node {
 462   cnode lru_node;
 463   cnode buf_node;
 464   uns buf_size;
 465   byte *buf;
 466   oid_t oid;
 467   byte *url;
 468   struct image image;
 469   struct image_dup dup;
 470 };
 471
 472 static uns pass1_buf_size = 400 << 20;
 473 static uns pass1_max_count = 100000;
 474 static uns pass1_search_dist = 40;
 475 static uns pass1_search_count = 500;
 476
 477 static struct mempool *pass1_pool;
 478 static struct pass1_hilbert *pass1_hilbert_list;
 479 static byte *pass1_buf_start;
 480 static byte *pass1_buf_pos;
 481 static uns pass1_buf_free;
 482 static uns pass1_buf_used;
 483 static clist pass1_buf_list;
 484 static clist pass1_lru_list;
 485 static u64 pass1_lookups;
 486 static u64 pass1_reads;
 487 static u64 pass1_pairs;
 488 static u64 pass1_dups;
 489 static u64 pass1_shrinks;
 490 static u64 pass1_alloc_sum;
 491
 492 #define HILBERT_PREFIX(x) pass1_hilbert_##x
 493 #define HILBERT_TYPE byte
 494 #define HILBERT_ORDER 8
 495 #define HILBERT_DIM IMAGE_VEC_K
 496 #define HILBERT_WANT_ENCODE
 497 #include "images/hilbert.h"
 498
 499 #define ASORT_PREFIX(x) pass1_hilbert_sort_##x
 500 #define ASORT_KEY_TYPE struct image_vector *
 501 #define ASORT_ELT(i) (&pass1_hilbert_list[i].vec)
 502 #define ASORT_LT(x,y) (memcmp(x, y, sizeof(*x)) < 0)
 503 #define ASORT_SWAP(i,j) do { struct pass1_hilbert _s;           \
 504                 _s = pass1_hilbert_list[i];                     \
 505                 pass1_hilbert_list[i] = pass1_hilbert_list[j];  \
 506                 pass1_hilbert_list[j] = _s; } while(0)
 507 #include "lib/arraysort.h"
 508
 509 static void
 510 pass1_hilbert_sort(void)
 511 {
 512   DBG("Computing positions on the Hilbert curve");
 513   pass1_hilbert_list = xmalloc(tree.count * sizeof(struct pass1_hilbert));
 514   for (uns i = 0; i < tree.count; i++)
 515     {
 516       struct pass1_hilbert *h = pass1_hilbert_list + i;
 517       h->index = i;
 518       byte vec[IMAGE_VEC_K];
 519       pass1_hilbert_encode(vec, precords[i]->vec.f);
 520       for (uns j = 0; j < IMAGE_VEC_K; j++)
 521         h->vec.f[j] = vec[IMAGE_VEC_K - 1 - j];
 522     }
 523   DBG("Sorting signatures in order of incresing parameters on the Hilbert curve");
 524   pass1_hilbert_sort_sort(tree.count);
 525 #if 0
 526   for (uns i = 0; i < tree.count; i++)
 527     {
 528       if (i)
 529         {
 530           byte *v1 = precords[pass1_hilbert_list[i - 1].index]->vec.f;
 531           byte *v2 = precords[pass1_hilbert_list[i].index]->vec.f;
 532 #define SQR(x) ((x)*(x))
 533            uns dist = 0;
 534           for (uns j = 0; j < 6; j++)
 535             dist += SQR(v1[j] - v2[j]);
 536           DBG("dist %d", dist);
 537         }
 538       DBG("index %d", pass1_hilbert_list[i].index);
 539     }
 540 #endif
 541 }
 542
 543 static void
 544 pass1_hilbert_cleanup(void)
 545 {
 546   xfree(pass1_hilbert_list);
 547 }
 548
 549 #define HASH_PREFIX(x) pass1_hash_##x
 550 #define HASH_NODE struct pass1_node
 551 #define HASH_KEY_ATOMIC oid
 552 #define HASH_WANT_CLEANUP
 553 #define HASH_WANT_FIND
 554 #define HASH_WANT_NEW
 555 #define HASH_WANT_REMOVE
 556 #include "lib/hashtable.h"
 557
 558 static inline void
 559 pass1_buf_init(void)
 560 {
 561   //DBG("pass1_buf_init()");
 562   pass1_buf_free = pass1_buf_size;
 563   pass1_buf_start = pass1_buf_pos = xmalloc(pass1_buf_size);
 564   pass1_buf_used = 0;
 565 }
 566
 567 static inline void
 568 pass1_buf_cleanup(void)
 569 {
 570   //DBG("pass1_buf_cleanup()");
 571   xfree(pass1_buf_start);
 572 }
 573
 574 static void
 575 pass1_node_free(struct pass1_node *node)
 576 {
 577   //DBG("pass1_node_free(%d)", (uns)node->oid);
 578   if (node->buf_size)
 579     {
 580       pass1_buf_used -= node->buf_size;
 581       clist_remove(&node->buf_node);
 582     }
 583   clist_remove(&node->lru_node);
 584   pass1_hash_remove(node);
 585 }
 586
 587 static inline void
 588 pass1_node_free_lru(void)
 589 {
 590   ASSERT(!clist_empty(&pass1_lru_list));
 591   pass1_node_free(SKIP_BACK(struct pass1_node, lru_node, clist_head(&pass1_lru_list)));
 592 }
 593
 594 static inline void
 595 pass1_node_after_move(struct pass1_node *node, addr_int_t move)
 596 {
 597   //DBG("pass1_node_after_mode(%d, %d)", (uns)node->oid, (uns)move);
 598   /* adjust internal pointers */
 599 #define MOVE(x) x = (byte *)(x) - move
 600   MOVE(node->url);
 601   MOVE(node->image.pixels);
 602   MOVE(node->dup.buf);
 603 #undef MOVE
 604 }
 605
 606 static inline void
 607 pass1_buf_shrink(void)
 608 {
 609   DBG("pass1_buf_shrink()");
 610   pass1_shrinks++;
 611   pass1_buf_free = pass1_buf_size;
 612   pass1_buf_pos = pass1_buf_start;
 613   CLIST_FOR_EACH(void *, p, pass1_buf_list)
 614     {
 615       struct pass1_node *node = SKIP_BACK(struct pass1_node, buf_node, p);
 616       if (node->buf != pass1_buf_pos)
 617         {
 618           memmove(pass1_buf_pos, node->buf, node->buf_size);
 619           pass1_node_after_move(node, node->buf - pass1_buf_pos);
 620           node->buf = pass1_buf_pos;
 621         }
 622       pass1_buf_pos += node->buf_size;
 623       pass1_buf_free -= node->buf_size;
 624     }
 625 }
 626
 627 static void *
 628 pass1_buf_alloc(uns size)
 629 {
 630   //DBG("pass1_buf_alloc(%d)", size);
 631
 632   /* if there is not enough free space at the end of the buffer */
 633   if (size > pass1_buf_free)
 634     {
 635       /* free some lru nodes */
 636       //DBG("freeing lru nodes");
 637       while (size > pass1_buf_size - pass1_buf_used || pass1_buf_used > pass1_buf_size / 2)
 638         {
 639           if (unlikely(clist_empty(&pass1_lru_list))) // FIXME
 640             die("Buffer too small");
 641           pass1_node_free_lru();
 642         }
 643
 644       pass1_buf_shrink();
 645     }
 646
 647   /* final allocation */
 648   void *result = pass1_buf_pos;
 649   pass1_buf_pos += size;
 650   pass1_buf_free -= size;
 651   pass1_buf_used += size;
 652   pass1_alloc_sum += size;
 653   return result;
 654 }
 655
 656 static struct pass1_node *
 657 pass1_node_new(oid_t oid)
 658 {
 659   DBG("pass1_node_new(%d)", (uns)oid);
 660   if (pass1_hash_table.hash_count == pass1_max_count)
 661     pass1_node_free_lru();
 662   struct pass1_node *node = pass1_hash_new(oid);
 663   mp_flush(pass1_pool);
 664   pass1_reads++;
 665
 666   /* read object */
 667   struct card_attr ca;
 668   bsetpos(fb_card_attrs, (sh_off_t)oid * sizeof(ca)); /* FIXME: these seeks can be easily removed */
 669   bread(fb_card_attrs, &ca, sizeof(ca));
 670
 671   bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT); /* FIXME: maybe a presort should handle these random seeks */
 672   uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
 673   uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
 674   struct odes *obj = obj_read_bucket(buck2obj, pass1_pool, buck_type, buck_len, fb_cards, NULL);
 675   if (unlikely(!obj))
 676     die("Failed to read card");
 677   byte *url = obj_find_aval(obj_find_attr(obj, 'U' + OBJ_ATTR_SON)->son, 'U');
 678   uns url_len = strlen(url);
 679
 680   /* decompress thumbnail */
 681   struct image_obj imo;
 682   imo_init(&imo, pass1_pool, obj);
 683   if (unlikely(!imo_decompress_thumbnail(&imo)))
 684     die("Cannot decompress thumbnail");
 685   node->image = imo.thumb;
 686
 687   /* create duplicates comparision object */
 688   image_dup_init(&node->dup, &node->image, pass1_pool);
 689
 690   /* copy data */
 691   //DBG("loaded image %s s=%d d=%d", url, node->image.size, node->dup.buf_size);
 692   node->buf_size = node->image.size + node->dup.buf_size + url_len + 1;
 693   if (node->buf_size)
 694     {
 695       byte *buf = node->buf = pass1_buf_alloc(node->buf_size);
 696       clist_add_tail(&pass1_buf_list, &node->buf_node);
 697 #define COPY(ptr, size) ({ void *_p=buf; uns _size=(size); buf+=_size; memcpy(_p,(ptr),_size); _p; })
 698       node->url = COPY(url, url_len + 1);
 699       node->image.pixels = COPY(node->image.pixels, node->image.size);
 700       node->dup.buf = COPY(node->dup.buf, node->dup.buf_size);
 701 #undef COPY
 702     }
 703
 704   /* add to lru list */
 705   return node;
 706 }
 707
 708 static inline struct pass1_node *
 709 pass1_node_lock(oid_t oid)
 710 {
 711   DBG("pass1_node_lock(%d)", (uns)oid);
 712   pass1_lookups++;
 713   struct pass1_node *node = pass1_hash_find(oid);
 714   if (node)
 715     {
 716       clist_remove(&node->lru_node);
 717       return node;
 718     }
 719   else
 720     return pass1_node_new(oid);
 721 }
 722
 723 static inline void
 724 pass1_node_unlock(struct pass1_node *node)
 725 {
 726   //DBG("pass1_node_unlock(%d)", (uns)node->oid);
 727   clist_add_tail(&pass1_lru_list, &node->lru_node);
 728 }
 729
 730 static void
 731 pass1_show_stats(void)
 732 {
 733   log(L_INFO, "%d count, %Ld lookups, %Ld reads, %Ld pairs, %Ld dups, %Ld shrinks", tree.count,
 734     (long long int)pass1_lookups, (long long int)pass1_reads,
 735     (long long int)pass1_pairs, (long long int)pass1_dups, (long long int)pass1_shrinks);
 736 }
 737
 738 static void
 739 pass1(void)
 740 {
 741   log(L_INFO, "Looking for duplicates");
 742   ASSERT(tree.nodes);
 743
 744   /* initialization */
 745   pass1_lookups = pass1_reads = pass1_pairs = pass1_dups = pass1_shrinks = pass1_alloc_sum = 0;
 746   fb_cards = bopen("index/cards", O_RDONLY, 10000); // FIXME
 747   fb_card_attrs = bopen("index/card-attrs", O_RDONLY, sizeof(struct card_attr)); // FIXME
 748   buck2obj = buck2obj_alloc();
 749   imo_decompress_thumbnails_init();
 750   clist_init(&pass1_lru_list);
 751   clist_init(&pass1_buf_list);
 752   pass1_hash_init();
 753   pass1_buf_init();
 754   pass1_pool = mp_new(1 << 20);
 755
 756   /* Hilbert sort */
 757   pass1_hilbert_sort();
 758   pass1_hilbert_cleanup();
 759
 760   /* main loop */
 761   for (uns i = 0; i < tree.count; )
 762     {
 763       /* lookup next image */
 764       oid_t oid = tree.leaves[i].oid;
 765       struct pass1_node *node = pass1_node_lock(oid);
 766
 767       /* compare with all near images */
 768       struct image_search search;
 769       image_search_init(&search, &tree, &precords[i]->vec, pass1_search_dist);
 770       /* FIXME: can be faster than general search in KD-tree */
 771       oid_t oid2;
 772       uns dist;
 773       for (uns j = 0; j < pass1_search_count && image_search_next(&search, &oid2, &dist); j++)
 774         {
 775           if (oid < oid2)
 776             {
 777               struct pass1_node *node2 = pass1_node_lock(oid2);
 778               DBG("comparing %d and %d", oid, oid2);
 779               if (image_dup_compare(&node->dup, &node2->dup, IMAGE_DUP_TRANS_ID))
 780                 {
 781                   pass1_dups++;
 782                   log(L_DEBUG, "*** Found duplicates oid1=0x%x oid=0x%x", (uns)node->oid, (uns)node2->oid);
 783                   log(L_DEBUG, "  %s", node->url);
 784                   log(L_DEBUG, "  %s", node2->url);
 785                 }
 786               pass1_pairs++;
 787               pass1_node_unlock(node2);
 788             }
 789         }
 790       image_search_done(&search);
 791       pass1_node_unlock(node);
 792       i++;
 793       if (i % 1000 == 0)
 794         log(L_DEBUG, "... passed %d images", i);
 795     }
 796
 797   /* clean up */
 798   pass1_hash_cleanup();
 799   pass1_buf_cleanup();
 800   mp_delete(pass1_pool);
 801   bclose(fb_cards);
 802   bclose(fb_card_attrs);
 803   buck2obj_free(buck2obj);
 804   imo_decompress_thumbnails_done();
 805
 806   /* print statistics */
 807   pass1_show_stats();
 808 }
 809
 810 /*********************************************************************************/
 811
 812 static uns pass2_clusterings_count = 1;
 813
 814 static void
 815 pass2_estimate_sizes(void)
 816 {
 817   if (!vectors_count)
 818     return;
 819   log(L_DEBUG, "Reading image sizes");
 820
 821   /* FIXME: hack, these reads are not necessary, can be done in previous phases */
 822   struct fastbuf *fb_cards = index_bopen("cards", O_RDONLY);
 823   struct fastbuf *fb_card_attrs = index_bopen("card-attrs", O_RDONLY);
 824   struct mempool *pool = mp_new(1 << 16);
 825   struct buck2obj_buf *bob = buck2obj_alloc();
 826
 827   for (uns i = 0; i < vectors_count; i++)
 828     {
 829       oid_t oid = vectors[i].oid;
 830       struct card_attr ca;
 831       bsetpos(fb_card_attrs, (sh_off_t)oid * sizeof(ca));
 832       bread(fb_card_attrs, &ca, sizeof(ca));
 833       bsetpos(fb_cards, (sh_off_t)ca.card << CARD_POS_SHIFT);
 834       uns buck_len = bgetl(fb_cards) - (LIZARD_COMPRESS_HEADER - 1);
 835       uns buck_type = bgetc(fb_cards) + BUCKET_TYPE_PLAIN;
 836       mp_flush(pool);
 837       struct odes *obj = obj_read_bucket(bob, pool, buck_type, buck_len, fb_cards, NULL);
 838       byte *attr = obj_find_aval(obj, 'G');
 839       ASSERT(attr);
 840       uns image_width, image_height, image_colors, thumb_width, thumb_height;
 841       byte color_space[MAX_ATTR_SIZE];
 842       sscanf(attr, "%d%d%s%d%d%d", &image_width, &image_height, color_space, &image_colors, &thumb_width, &thumb_height);
 843       vectors[i].temp = image_dup_estimate_size(thumb_width, thumb_height) +
 844         sizeof(struct image) + thumb_width * thumb_height * 3;
 845     }
 846   buck2obj_free(bob);
 847   mp_delete(pool);
 848   bclose(fb_cards);
 849   bclose(fb_card_attrs);
 850 }
 851
 852 static void
 853 pass2(void)
 854 {
 855   // FIXME: presorts, much allocated memory when not needed
 856   vectors_read();
 857   pass2_estimate_sizes();
 858   random_clusters_init();
 859   for (uns clustering = 0; clustering < pass2_clusterings_count; clustering++)
 860     {
 861       random_clusters_build();
 862       // FIXME
 863       // - external sort
 864       // - generate and compare pairs in clusters
 865     }
 866   random_clusters_cleanup();
 867   vectors_cleanup();
 868 }
 869 #endif
 870
 871 /*********************************************************************************/
 872
 873 static char *shortopts = CF_SHORT_OPTS "";
 874 static struct option longopts[] =
 875 {
 876   CF_LONG_OPTS
 877   { NULL, 0, 0, 0 }
 878 };
 879
 880 static char *help = "\
 881 Usage: image-indexer [<options>]\n\
 882 \n\
 883 Options:\n" CF_USAGE;
 884
 885 static void NONRET
 886 usage(byte *msg)
 887 {
 888   if (msg)
 889   {
 890     fputs(msg, stderr);
 891     fputc('\n', stderr);
 892   }
 893   fputs(help, stderr);
 894   exit(1);
 895 }
 896
 897
 898 int
 899 main(int argc UNUSED, char **argv)
 900 {
 901   int opt;
 902
 903   log_init(argv[0]);
 904   while ((opt = cf_getopt(argc, argv, shortopts, longopts, NULL)) >= 0)
 905     switch (opt)
 906     {
 907       default:
 908       usage("Invalid option");
 909     }
 910   if (optind != argc)
 911     usage("Invalid usage");
 912
 913   srgb_to_luv_init();
 914
 915 #if 0
 916   while (1)
 917   {
 918   struct mempool *pool = mp_new(1024);
 919   struct fastbuf *fb = bopen("a.jpg", O_RDONLY, 1024);
 920   struct image_io io;
 921   log(L_DEBUG, "opening");
 922   image_open(&io, fb, pool);
 923   io.format = IMAGE_FORMAT_JPEG;
 924   log(L_DEBUG, "reading");
 925   int i;
 926   i = image_read(&io);
 927   log(L_DEBUG, "done %d %d %d", i, io.image.width, io.image.height);
 928   for (i = 0; i < 1000000000; i++)
 929     ;
 930   image_close(&io);
 931   mp_delete(pool);
 932   bclose(fb);
 933   }
 934 #endif
 935
 936 #if 0
 937   generate_signatures(20000);
 938   build_kd_tree();
 939   //pass1();
 940   pass2();
 941 #endif
 942
 943   return 0;
 944 }