X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=images%2Fdup-cmp.c;h=b71feaef9fa871fc4e4ff8675b593e956e9604ea;hb=5da13cd16371faa6df5b880387b5b172a1704aef;hp=6a249ec3301db9d4d2b703f181275fbcd480fb5e;hpb=6b5e227f5965a1d63cef2e1391cbebb25fa2bdd7;p=libucw.git

diff --git a/images/dup-cmp.c b/images/dup-cmp.c
index 6a249ec3..b71feaef 100644
--- a/images/dup-cmp.c
+++ b/images/dup-cmp.c
@@ -5,119 +5,17 @@
  *
  *      This software may be freely distributed and used according to the terms
  *      of the GNU Lesser General Public License.
- *
- *
- *      FIXME:
- *      - many possible optimization
- *      - compare normalized pictures (brightness, ...)
- *      - better image scale... now it can completely miss some rows/cols of pixels
- *      - maybe better/slower last step
- *      - different thresholds for various transformations
- *      - do not test all transformations for symetric pictures
- *      - ... secret ideas :-)
  */
 
 #undef LOCAL_DEBUG
 
-#include "sherlock/sherlock.h"
+#include "lib/lib.h"
 #include "lib/mempool.h"
+#include "lib/fastbuf.h"
 #include "images/images.h"
-#include "images/dup-cmp.h"
-
-static uns image_dup_scale_min_size = 16;
-static uns image_dup_ratio_threshold = 140;
-static uns image_dup_error_threshold = 50;
-
-static inline byte *
-image_dup_block(struct image_dup *dup, uns col, uns row)
-{
-  ASSERT(col <= dup->cols && row <= dup->rows);
-  return dup->buf + (dup->line << row) + (3 << (row + col));
-}
-
-static inline void
-pixels_average(byte *dest, byte *src1, byte *src2)
-{
-  dest[0] = ((uns)src1[0] + (uns)src2[0]) >> 1;
-  dest[1] = ((uns)src1[1] + (uns)src2[1]) >> 1;
-  dest[2] = ((uns)src1[2] + (uns)src2[2]) >> 1;
-}
-
-void
-image_dup_init(struct image_dup *dup, struct image *image, struct mempool *pool)
-{
-  ASSERT(image->width && image->height);
-  
-  dup->image = image;
-  dup->width = image->width;
-  dup->height = image->height;
-  for (dup->cols = 0; (uns)(2 << dup->cols) < image->width; dup->cols++);
-  for (dup->rows = 0; (uns)(2 << dup->rows) < image->height; dup->rows++);
-  dup->buf = mp_alloc(pool, dup->buf_size = (12 << (dup->cols + dup->rows)));
-  dup->line = 6 << dup->cols;
-  dup->flags = 0;
-  if (image->width >= image_dup_scale_min_size && image->height >= image_dup_scale_min_size)
-    dup->flags |= IMAGE_DUP_FLAG_SCALE;
-  
-  /* Scale original image to right bottom block */
-  {
-    byte *d = image_dup_block(dup, dup->cols, dup->rows);
-    uns width = 1 << dup->cols;
-    uns height = 1 << dup->rows;
-    uns line_size = 3 * image->width;
-    uns src_y = 0;
-    for (uns y = 0; y < height; y++)
-      {
-	byte *line = image->pixels + line_size * (src_y >> dup->rows);
-        uns src_x = 0;
-        for (uns x = 0; x < width; x++)
-          {
-	    byte *s = line + 3 * (src_x >> dup->cols);
-	    d[0] = s[0];
-	    d[1] = s[1];
-	    d[2] = s[2];
-	    d += 3;
-	    src_x += image->width;
-	  }
-	src_y += image->height;
-      }
-  }
+#include "images/duplicates.h"
 
-  /* Complete bottom row */
-  for (uns i = dup->cols; i--; )
-    {
-      byte *d = image_dup_block(dup, i, dup->rows);
-      byte *s = image_dup_block(dup, i + 1, dup->rows);
-      for (uns y = 0; y < (uns)(1 << dup->rows); y++)
-	for (uns x = 0; x < (uns)(1 << i); x++)
-	  {
-	    pixels_average(d, s, s + 3);
-	    d += 3;
-	    s += 6;
-	  }
-    }
- 
-  /* Complete remaining blocks */
-  for (uns i = 0; i <= dup->cols; i++)
-    {
-      uns line_size = (3 << i);
-      for (uns j = dup->rows; j--; )
-        {
-          byte *d = image_dup_block(dup, i, j);
-          byte *s = image_dup_block(dup, i, j + 1);
-          for (uns y = 0; y < (uns)(1 << j); y++)
-            {
-              for (uns x = 0; x < (uns)(1 << i); x++)
-                {
- 	          pixels_average(d, s, s + line_size);
-		  d += 3;
-		  s += 3;
-		}
-	      s += line_size;
-	    }
-        }
-    }
-}
+#include <fcntl.h>
 
 static inline uns
 err (int a, int b)
@@ -126,46 +24,59 @@ err (int a, int b)
   return a * a;
 }
 
-static inline uns
-err_sum(byte *pos1, byte *end1, byte *pos2)
+static inline u64
+err_sum(byte *pos1, byte *pos2, uns count)
 {
-  uns e = 0;
-  while (pos1 != end1)
-    e += err(*pos1++, *pos2++);
-  return e;
+  uns e64 = 0;
+  while (count--)
+    {
+      uns e = err(*pos1++, *pos2++);
+      e += err(*pos1++, *pos2++);
+      e += err(*pos1++, *pos2++);
+      e64 += e;
+    }
+  return e64;
 }
 
-static inline uns
-err_sum_transformed(byte *pos1, byte *end1, byte *pos2, uns width, int add1, int add2)
+static inline u64
+err_sum_transformed(byte *pos1, byte *pos2, uns cols, uns rows, int row_step_1, int col_step_2, int row_step_2)
 {
-  DBG("err_sum_transformed(): %p %p %p %d %d %d", pos1, end1, pos2, width, add1, add2);
-  uns e = 0;
-  while (pos1 != end1)
+  DBG("err_sum_transformed(pos1=%p pos2=%p cols=%u rows=%u row_step_1=%d col_step_2=%d row_step_2=%d)",
+      pos1, pos2, cols, rows, row_step_1, col_step_2, row_step_2);
+  u64 e64 = 0;
+  for (uns j = rows; j--; )
     {
-      for (uns i = 0; i < width; i++, pos2 += add1)
+      byte *p1 = pos1;
+      byte *p2 = pos2;
+      uns e = 0;
+      for (uns i = cols; i--; )
       {
-	e += err(pos1[0], pos2[0]);
-	e += err(pos1[1], pos2[1]);
-	e += err(pos1[2], pos2[2]);
-	pos1 += 3;
+	e += err(p1[0], p2[0]);
+	e += err(p1[1], p2[1]);
+	e += err(p1[2], p2[2]);
+	p1 += 3;
+	p2 += col_step_2;
       }
-      pos2 += add2;
+      pos1 += row_step_1;
+      pos2 += row_step_2;
+      e64 += e;
     }
-  return e;
+  return e64;
 }
 
 static inline int
-aspect_ratio_test(uns width1, uns height1, uns width2, uns height2)
+aspect_ratio_test(struct image_dup_context *ctx, uns cols1, uns rows1, uns cols2, uns rows2)
 {
-  uns r1 = width1 * height2;
-  uns r2 = height1 * width2;
+  DBG("aspect_ratio_test(cols1=%u rows1=%u cols2=%u rows2=%u)", cols1, rows1, cols2, rows2);
+  uns r1 = cols1 * rows2;
+  uns r2 = rows1 * cols2;
   return
-    r1 <= ((r2 * image_dup_ratio_threshold) >> 5) && 
-    r2 <= ((r1 * image_dup_ratio_threshold) >> 5);
+    r1 <= ((r2 * ctx->ratio_threshold) >> 7) &&
+    r2 <= ((r1 * ctx->ratio_threshold) >> 7);
 }
 
 static inline int
-average_compare(struct image_dup *dup1, struct image_dup *dup2)
+average_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 {
   byte *block1 = image_dup_block(dup1, 0, 0);
   byte *block2 = image_dup_block(dup2, 0, 0);
@@ -173,183 +84,219 @@ average_compare(struct image_dup *dup1, struct image_dup *dup2)
     err(block1[0], block2[0]) +
     err(block1[1], block2[1]) +
     err(block1[2], block2[2]);
-  return e <= image_dup_error_threshold;
+  return e <= ctx->error_threshold;
 }
 
 static int
-blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns col, uns row, uns trans)
+blocks_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans)
 {
-  DBG("blocks_compare(): col=%d row=%d trans=%d", col, row, trans);
-  byte *block1 = image_dup_block(dup1, col, row);
-  byte *block2 = (trans < 4) ? image_dup_block(dup2, col, row) : image_dup_block(dup2, row, col);
-  int add1, add2;
+  DBG("blocks_compare(tab_col=%d tab_row=%d trans=%d)", tab_col, tab_row, trans);
+  ctx->sum_pixels += 1 << (tab_col + tab_row);
+  byte *block1 = image_dup_block(dup1, tab_col, tab_row);
+  byte *block2;
+  int col_step, row_step;
+  if (trans < 4)
+    block2 = image_dup_block(dup2, tab_col, tab_row);
+  else
+    block2 = image_dup_block(dup2, tab_row, tab_col);
   switch (trans)
     {
       case 0: ;
-	uns err = (err_sum(block1, block1 + (3 << (col + row)), block2) >> (col + row));
+	uns err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row));
 	DBG("average error=%d", err);
-	return err <= image_dup_error_threshold;
+	ctx->error = err;
+	return err <= ctx->error_threshold;
       case 1:
-	add1 = -3;
-	add2 = 6 << col;
-	block2 += (3 << col) - 3;
+	col_step = -3;
+	row_step = (3 << tab_col);
+	block2 += row_step - 3;
 	break;
       case 2:
-	add1 = 1;
-	add2 = -(6 << col);
-	block2 += (3 << (col + row)) - (3 << col);
+	col_step = 3;
+	row_step = -(3 << tab_col);
+	block2 += (3 << (tab_col + tab_row)) + row_step;
 	break;
       case 3:
-	add1 = -3;
-	add2 = 0;
-	block2 += (3 << (col + row)) - 3;
+	col_step = -3;
+	row_step = -(3 << tab_col);
+	block2 += (3 << (tab_col + tab_row)) - 3;
 	break;
       case 4:
-	add1 = (3 << col);
-	add2 = -(3 << (col + row)) + 3;
+	col_step = (3 << tab_row);
+	row_step = 3;
 	break;
       case 5:
-	add1 = -(3 << col);
-	add2 = (3 << (col + row)) + 3;
-	block2 += (3 << (col + row)) - (3 << col);
+	col_step = -(3 << tab_row);
+	row_step = 3;
+	block2 += (3 << (tab_col + tab_row)) + col_step;
 	break;
       case 6:
-	add1 = (3 << col);
-	add2 = -(3 << (col + row)) - 3;
-	block2 += (3 << col) - 3;
+	col_step = (3 << tab_row);
+	row_step = -3;
+	block2 += col_step - 3;
 	break;
       case 7:
-	add1 = -(3 << col);
-	add2 = (3 << (col + row)) - 3;
-	block2 += (3 << (col + row)) - 3;
+	col_step = -(3 << tab_row);
+	row_step = -3;
+	block2 += (3 << (tab_col + tab_row)) - 3;
 	break;
       default:
 	ASSERT(0);
     }
-  uns err = (err_sum_transformed(block1, block1 + (3 << (col + row)), block2, (1 << col), add1, add2) >> (col + row));
+  uns err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row));
   DBG("average error=%d", err);
-  return err <= image_dup_error_threshold;
+  ctx->error = err;
+  return err <= ctx->error_threshold;
 }
 
 static int
-same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
+same_size_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns trans)
 {
-  byte *block1 = dup1->image->pixels;
-  byte *block2 = dup2->image->pixels;
-  DBG("same_size_compare(): trans=%d",  trans);
-  int add1, add2;
+  struct image *img1 = &dup1->image;
+  struct image *img2 = &dup2->image;
+  if (!img1->pixels || !img2->pixels)
+    return 1;
+  ctx->sum_pixels += img1->cols * img1->rows;
+  byte *block1 = img1->pixels;
+  byte *block2 = img2->pixels;
+  int col_step, row_step;
+  DBG("same_size_compare(trans=%d)",  trans);
   switch (trans)
     {
       case 0: ;
-        uns err = (err_sum(block1, block1 + 3 * dup1->width * dup1->height, block2) / (dup1->width * dup1->height));
-	DBG("average error=%d", err);
-	return err <= image_dup_error_threshold;
+	col_step = 3;
+	row_step = img2->row_size;
+	break;
       case 1:
-	add1 = -3;
-	add2 = 6 * dup1->width;
-	block2 += 3 * (dup1->width - 1);
+	col_step = -3;
+	row_step = img2->row_size;
+	block2 += 3 * (img2->cols - 1);
 	break;
       case 2:
-	add1 = 1;
-	add2 = -6 * dup1->width;
-	block2 += 3 * dup1->width * (dup1->height - 1);
+	col_step = 3;
+	row_step = -img2->row_size;
+	block2 += img2->row_size * (img2->rows - 1);
 	break;
       case 3:
-	add1 = -3;
-	add2 = 0;
-	block2 += 3 * (dup1->width * dup1->height - 1);
+	col_step = -3;
+	row_step = -img2->row_size;
+	block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 	break;
       case 4:
-	add1 = 3 * dup1->width;
-	add2 = -3 * (dup1->width * dup1->height - 1);
+	col_step = img2->row_size;
+	row_step = 3;
 	break;
       case 5:
-	add1 = -3 * dup1->width;
-	add2 = 3 * (dup1->width * dup1->height + 1);
-	block2 += 3 * dup1->width * (dup1->height - 1);
+	col_step = -img2->row_size;
+	row_step = 3;
+	block2 += img2->row_size * (img2->rows - 1);
 	break;
       case 6:
-	add1 = 3 * dup1->width;
-	add2 = -3 * (dup1->width * dup1->height + 1);
-	block2 += 3 * (dup1->width - 1);
+	col_step = img2->row_size;
+	row_step = -3;
+	block2 += 3 * (img2->cols - 1);
 	break;
       case 7:
-	add1 = -3 * dup1->width;
-	add2 = 3 * (dup1->width * dup1->height - 1);
-	block2 += 3 * (dup1->width * dup1->height - 1);
+	col_step = -img2->row_size;
+	row_step = -3;
+	block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
 	break;
       default:
 	ASSERT(0);
     }
-  uns err = (err_sum_transformed(block1, block1 + 3 * dup1->width * dup1->height, block2, dup1->width, add1, add2) / (dup1->width * dup1->height));
+  uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
   DBG("average error=%d", err);
-  return err <= image_dup_error_threshold;
+  ctx->error = err;
+  return err <= ctx->error_threshold;
 }
 
-int
-image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
+uns
+image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2)
 {
-  if (!average_compare(dup1, dup2))
+  DBG("image_dup_compare(%p, %p)", dup1, dup2);
+  if (!average_compare(ctx, dup1, dup2))
     return 0;
-  if ((dup1->flags & dup2->flags) & IMAGE_DUP_FLAG_SCALE)
+  struct image *img1 = &dup1->image;
+  struct image *img2 = &dup2->image;
+  uns flags = ctx->flags;
+  if (flags & IMAGE_DUP_SCALE)
     {
       DBG("Scale support");
-      if (!aspect_ratio_test(dup1->width, dup1->height, dup2->width, dup2->height))
-	trans &= 0xf0;
-      if (!aspect_ratio_test(dup1->width, dup1->height, dup2->height, dup2->width))
-	trans &= 0x0f;
+      if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows))
+	flags &= ~0x0f;
+      if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols))
+	flags &= ~0xf0;
     }
   else
     {
       DBG("No scale support");
-      if (!(dup1->width == dup2->width && dup1->height == dup2->height))
-	trans &= 0xf0;
-      if (!(dup1->width == dup2->height && dup1->height == dup2->width))
-	trans &= 0x0f;
+      if (!(img1->cols == img2->cols && img1->rows == img2->rows))
+	flags &= ~0x0f;
+      if (!(img1->cols == img2->rows && img1->rows == img2->cols))
+	flags &= ~0xf0;
     }
-  if (!trans)
+  if (!(flags & 0xff))
     return 0;
-  if (trans & 0x0f)
+  uns result = 0;
+  if (flags & 0x0f)
     {
-      uns cols = MIN(dup1->cols, dup2->cols);
-      uns rows = MIN(dup1->rows, dup2->rows);
+      uns cols = MIN(dup1->tab_cols, dup2->tab_cols);
+      uns rows = MIN(dup1->tab_rows, dup2->tab_rows);
       for (uns t = 0; t < 4; t++)
-	if (trans & (1 << t))
+	if (flags & (1 << t))
 	  {
 	    DBG("Testing trans %d", t);
-            for (uns i = MAX(cols, rows); i--; )
+	    uns i = MAX(cols, rows), depth = 1;
+            while (i--)
               {
+		depth++;
 	        uns col = MAX(0, (int)(cols - i));
 	        uns row = MAX(0, (int)(rows - i));
-	        if (!blocks_compare(dup1, dup2, col, row, t))
+	        if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 		  break;
 		if (!i &&
-		    (dup1->width != dup2->width || dup1->height != dup2->height ||
-		    same_size_compare(dup1, dup2, t)))
-		  return 1;
+		    (img1->cols != img2->cols || img1->rows != img2->rows ||
+		    same_size_compare(ctx, dup1, dup2, t)))
+		  {
+		    result |= 1 << t;
+		    if (!(flags & IMAGE_DUP_WANT_ALL))
+		      return result;
+		    else
+		      break;
+		  }
 	      }
+	    ctx->sum_depth += depth;
 	  }
     }
-  if (trans & 0xf0)
+  if (flags & 0xf0)
     {
-      uns cols = MIN(dup1->cols, dup2->rows);
-      uns rows = MIN(dup1->rows, dup2->cols);
+      uns cols = MIN(dup1->tab_cols, dup2->tab_rows);
+      uns rows = MIN(dup1->tab_rows, dup2->tab_cols);
       for (uns t = 4; t < 8; t++)
-	if (trans & (1 << t))
+	if (flags & (1 << t))
 	  {
 	    DBG("Testing trans %d", t);
-            for (uns i = MAX(cols, rows); i--; )
+	    uns i = MAX(cols, rows), depth = 1;
+            while (i--)
               {
+		depth++;
 	        uns col = MAX(0, (int)(cols - i));
 	        uns row = MAX(0, (int)(rows - i));
-	        if (!blocks_compare(dup1, dup2, col, row, t))
+	        if (!blocks_compare(ctx, dup1, dup2, col, row, t))
 		  break;
 		if (!i &&
-		    (dup1->width != dup2->height || dup1->height != dup2->width ||
-		    same_size_compare(dup1, dup2, t)) )
-		  return 1;
+		    (img1->cols != img2->rows || img1->rows != img2->cols ||
+		    same_size_compare(ctx, dup1, dup2, t)) )
+		  {
+		    result |= 1 << t;
+		    if (!(flags & IMAGE_DUP_WANT_ALL))
+		      return result;
+		    else
+		      break;
+		  }
 	      }
+	    ctx->sum_depth += depth;
 	  }
     }
-  return 0;
+  return result;
 }