]> mj.ucw.cz Git - libucw.git/blob - images/image-idx.c
Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git
[libucw.git] / 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 }