/*
 * This is a plug-in for the GIMP.
 *
 * Copyright (C) 1995 Spencer Kimball and Peter Mattis
 * Copyright (C) 1996 Torsten Martinsen
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * $Id: autocrop.c,v 1.12 1996/08/22 10:39:07 torsten Exp $
 *
 * @(GIMP)         = <plug-in mblur "Transforms/Autocrop">
 * @(GIMP_DEP)     = <autocrop.c>
 * @(GIMP_OBJ)     = <autocrop.o>
 * @(GIMP_LIB)     = <c m Xt X11>
 * @(GIMP_AUTHOR)  = <Torsten Martinsen>
 * @(GIMP_EMAIL)   = <bullestock@dk-online.dk>
 * @(GIMP_DESC)    = <Remove any borders from the image.>
 * @(GIMP_VERSION) = <$Revision: 1.12 $>
 * @(GIMP_URL)     = <http://www2.dk-online.dk/Users/Torsten_Martinsen/gimp/index.html>
 */

/* 
 * This filter removes any borders from the image.
 * The border colour is defined as the colour that at least two of
 * the corner pixels share.
 */

/* Whether or not you want the 'Delta' button (requires linking with X libs) */
#define COLORDELTA

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "gimp.h"

#ifdef COLORDELTA
#include <X11/Intrinsic.h>
#include <X11/cursorfont.h>
#endif

static void autocrop(Image input, Image output);
static int get_background(Image input);
static int get_new_size(Image input, long * nw, long * nh);
static unsigned long coldistrgb(unsigned char * c1, unsigned char * c2);
static unsigned long coldistgrey(unsigned char * c1, unsigned char * c2);
static unsigned long coldistindexed(unsigned char * c1, unsigned char * c2);
static void scale_callback(int, void *, void *);
static void ok_callback(int, void *, void *);
static void cancel_callback(int, void *, void *);

#ifdef COLORDELTA
static void button_callback(int, void *, void *);
static XColor * DoGrabColor(Widget w);
static void DoGrabPixel(Widget w, Pixel * p, Colormap * cmap);
static void doGrab(Widget w, int *x, int *y);
static void xyToWindowCmap(Display * dpy, int x, int y, Window base,
			   int *nx, int *ny, Window * window, Colormap * cmap);

static Widget toplevel;
static XtAppContext appContext;
#endif

typedef unsigned long (*CmpFun) (unsigned char *, unsigned char *);

static int dialog_ID, scale_ID, image_type;
static long tolerance = 0L;
static unsigned char * cmap;

/*
 * These are filled in by get_background().
 */
static unsigned char corner[4][3], * background;
static int x1, x2, Y1, y2;
static CmpFun coldist;

int
main(int argc, char **argv)
{
    Image input, output;
    void *data;
    long new_width;
    long new_height;
    int group_ID, temp_ID, e;
    
    if (gimp_init(argc, argv)) {
#ifdef COLORDELTA
	int button_ID;
	
	e = 0;
	toplevel = XtAppInitialize(&appContext, "Autocrop",
				   NULL, 0, &e, NULL, NULL, NULL, 0);
#endif
	output = 0;
	input = gimp_get_input_image(0);
	image_type = gimp_image_type(input);

	background = NULL;
	data = gimp_get_params();
	if (data) {
	    tolerance = ((long *) data)[0];
	    if ((image_type == GRAY_IMAGE) && (tolerance > 255))
		tolerance = 255;
	}
	
	dialog_ID = gimp_new_dialog("Autocrop");
	gimp_new_label(dialog_ID, DEFAULT, "Options");
	group_ID = gimp_new_row_group(dialog_ID, DEFAULT, NORMAL, "");
	temp_ID = gimp_new_column_group (dialog_ID, group_ID, NORMAL, "");
	gimp_new_label(dialog_ID, temp_ID, "Color tolerance");
	scale_ID = gimp_new_scale(dialog_ID, group_ID, 0,
				  image_type == GRAY_IMAGE ? 255 : 441,
				  tolerance, 0);
	gimp_add_callback(dialog_ID, scale_ID, scale_callback, &tolerance);

#ifdef COLORDELTA
	button_ID = gimp_new_push_button(dialog_ID, group_ID, "Color Delta");
	gimp_add_callback(dialog_ID, button_ID, button_callback, (void *) input);
#endif
	gimp_add_callback(dialog_ID, gimp_ok_item_id(dialog_ID),
			  ok_callback, 0);
	gimp_add_callback(dialog_ID, gimp_cancel_item_id(dialog_ID),
			  cancel_callback, 0);
	
	if (gimp_show_dialog(dialog_ID)) {
	    gimp_set_params(sizeof(int), &tolerance);
	    
	    e = get_new_size(input, &new_width, &new_height);
	    switch (e) {
	    case 0:
		output = gimp_new_image(0, new_width, new_height, image_type);
		
		if (image_type == INDEXED_IMAGE)
		    gimp_set_image_colors(output, gimp_image_cmap(input),
					  gimp_image_colors(input));
		
		if (input && output) {
		    gimp_display_image(output);
		    autocrop(input, output);
		    gimp_do_progress(5, 5);
		    gimp_update_image(output);
		}
		break;
	    case 1:
		gimp_message("No corners with same colour");
		break;
	    case 2:
		gimp_message("Resulting image too small");
		break;
#if 0
	    case 3:
		gimp_message("No change");
		break;
#endif
	    }
	}
	if (input)
	    gimp_free_image(input);
	if (output)
	    gimp_free_image(output);

	gimp_quit();
    }
    return 0;
}

/*
 * Determine the background colour by finding the colours of the four corners
 * and taking the colour which appears in at least two corners.
 * Return 1 if no two corners have the same colour, else 0.
 */
static int
get_background(Image input)
{
    int x, y, channels, rowstride, i;
    unsigned char * p, * src;
    unsigned long tolsq;
    
    gimp_image_area(input, &x1, &Y1, &x2, &y2);
    src = gimp_image_data(input);
    channels = gimp_image_channels(input);
    rowstride = gimp_image_width(input) * channels;
    tolsq = channels*tolerance*tolerance;

    switch (image_type) {
    case INDEXED_IMAGE:
	cmap = gimp_image_cmap(input);
	coldist = coldistindexed;
	break;
    case GRAY_IMAGE:
    case GRAYA_IMAGE:
	coldist = coldistgrey;
	break;
    default:
	coldist = coldistrgb;
	break;
    }

    for (y = Y1, i = 0; y < y2; y += y2-Y1-1)
	for (x = x1; x < x2; x += x2-x1-1) {
	    p = src + rowstride * y + x * channels;
	    corner[i][0] = *p++;
	    if (channels > 2) {
		corner[i][1] = *p++;
		corner[i][2] = *p;
	    }
	    ++i;
	}

    if ((coldist(corner[0], corner[1]) <= tolsq) ||
	(coldist(corner[0], corner[2]) <= tolsq) ||
	(coldist(corner[0], corner[3]) <= tolsq))
	background = corner[0];
    else if ((coldist(corner[1], corner[2]) <= tolsq) ||
	     (coldist(corner[1], corner[3]) <= tolsq))
	background = corner[1];
    else if (coldist(corner[2], corner[3]) <= tolsq)
	background = corner[2];
    else
	return 1;
    return 0;
}



static int
get_new_size(Image input, long * nw, long * nh)
{
    int width, channels, x, y;
    int right, left, top, bottom, rowstride;
    unsigned char * src, * p;
    unsigned long tolsq;

    if ((background == NULL) && get_background(input))
	return 1;
    gimp_init_progress("Autocrop");
    src = gimp_image_data(input);
    width = gimp_image_width(input);
    channels = gimp_image_channels(input);
    rowstride = width * channels;
    tolsq = channels*tolerance*tolerance;

    /* Find first non-background line. */
    for (top = Y1; top < y2; ++top)
	for (x = x1; x < x2; ++x) {
	    p = src + rowstride * top + x * channels;
	    if (coldist(background, p) > tolsq)
		goto foundtop;
	}	    
foundtop:

    gimp_do_progress(1, 5);

    /* Find last non-background line. */
    for (bottom = y2-1; bottom > top; --bottom)
 	for (x = x1; x < x2; ++x) {
	    p = src + rowstride * bottom + x * channels;
	    if (coldist(background, p) > tolsq)
		goto foundbottom;
	}
foundbottom:

    gimp_do_progress(2, 5);
    
    /* Find first non-background column. */
    left = x2-1;
    for (y = top; y <= bottom; ++y)
	for (x = x1; x < left; x++) {
	    p = src + rowstride * y + x * channels;
	    if (coldist(background, p) > tolsq) {
		left = x;
		break;
	    }
	}

    gimp_do_progress(3, 5);
	
    /* Find last non-background column. */
    right = left;
    for (y = top; y <= bottom; ++y)
	for (x = x2-1; x > right; --x) {
	    p = src + rowstride * y + x * channels;
	    if (coldist(background, p) > tolsq) {
		right = x;
		break;
	    }
	}
    
    gimp_do_progress(4, 5);
	
    /* Check that the size has changed and that the new size is reasonable. */
    if ((x1 == left) && (x2-1 == right) && (Y1 == top) && (y2-1 == bottom))
	return 3;
    if ((bottom - top < 1) || (right - left < 1))
	return 2;

    x1 = left;
    x2 = right;
    Y1 = top;
    y2 = bottom;

    *nw = x2-x1+1;
    *nh = y2-Y1+1;

    return 0;
}

static void
autocrop(Image input, Image output)
{
    int width, height;
    int channels, rowstride;
    unsigned char *src, *dest;
    int row, rowstride_o;

    width = gimp_image_width(input);
    height = gimp_image_height(input);
    channels = gimp_image_channels(input);
    rowstride = width * channels;

    src = gimp_image_data(input);
    dest = gimp_image_data(output);

    src += rowstride * Y1 + x1 * channels;

    rowstride_o = (x2-x1+1) * channels;
    for (row = Y1; row <= y2; row++) {
	memcpy(dest, src, rowstride_o);
	dest += rowstride_o;
	src += rowstride;
    }
}

/*
 * Return the squared Euclidean three-dimensional distance
 * between the two colours in RGB colour space.
 * Maximum value is 195075.
 */
static unsigned long
coldistrgb(unsigned char * c1, unsigned char * c2)
{
    int r, g, b;

    r = *c1++ - *c2++;
    g = *c1++ - *c2++;
    b = *c1++ - *c2++;
    return r*r + g*g + b*b;
}

/*
 * Return the squared distance between the two greyscale values.
 * Maximum value is 65025.
 */
static unsigned long
coldistgrey(unsigned char * c1, unsigned char * c2)
{
    int g;

    g = *c1 - *c2;
    return g*g;
}

/*
 * Return the squared distance between the two RGB values
 * found by indexing into the color map.
 * Maximum value is 195075.
 */
static unsigned long
coldistindexed(unsigned char * c1, unsigned char * c2)
{
    int r, g, b;
    unsigned char * p1, * p2;

    p1 = cmap + *c1 * 3;
    p2 = cmap + *c2 * 3;

    r = *p1++ - *p2++;
    g = *p1++ - *p2++;
    b = *p1++ - *p2++;
    return r*r + g*g + b*b;
}

static void
scale_callback(int item_ID, void *client_data, void *call_data)
{
    *((long *) client_data) = *((long *) call_data);
}

static void
ok_callback(int item_ID, void *client_data, void *call_data)
{
    gimp_close_dialog(dialog_ID, 1);
}

static void
cancel_callback(int item_ID, void *client_data, void *call_data)
{
    gimp_close_dialog(dialog_ID, 0);
}

/*
 * Code for making colour grabs.
 * Adapted (okay, 'stolen' is more like it) from XPaint.
 */
/* +-------------------------------------------------------------------+ */
/* | Copyright 1993, David Koblas (koblas@netcom.com)		       | */
/* |								       | */
/* | Permission to use, copy, modify, and to distribute this software  | */
/* | and its documentation for any purpose is hereby granted without   | */
/* | fee, provided that the above copyright notice appear in all       | */
/* | copies and that both that copyright notice and this permission    | */
/* | notice appear in supporting documentation.	 There is no	       | */
/* | representations about the suitability of this software for	       | */
/* | any purpose.  This software is provided "as is" without express   | */
/* | or implied warranty.					       | */
/* +-------------------------------------------------------------------+ */

#ifdef COLORDELTA
static void
button_callback(int item_ID, void *client_data, void *call_data)
{
    XColor * xcol;
    int rd, gd, bd;
    
    if (get_background((Image) client_data))
	gimp_message("No corners with same colour");

    xcol = DoGrabColor(toplevel);

    rd = background[0] - xcol->red/256;
    if (image_type == GRAY_IMAGE)
	tolerance = abs(rd);
    else {
	gd = background[1] - xcol->green/256;
	bd = background[2] - xcol->blue/256;
	tolerance = sqrt(rd*rd + gd*gd + bd*bd);
    }
    gimp_change_item(dialog_ID, scale_ID, sizeof(tolerance), &tolerance);
}

/*
**  Grab the RGB value from some other window
**
**   General strategy:
**     Grab the cursor
**     Wait for the up/down button event
**     Lookup what window the event is over
**     Query the pixel value
**     Query the colormap of the window
**     Query the rgb pixel value
 */
static XColor *
DoGrabColor(Widget w)
{
    static XColor xcol;
    Colormap cmap;
    Pixel p;

    DoGrabPixel(w, &p, &cmap);

    xcol.pixel = p;
    xcol.flags = DoRed | DoGreen | DoBlue;
    XQueryColor(XtDisplay(w), cmap, &xcol);

    return &xcol;
}

/*
**  Grab the pixel value from some other window
**
**  Store pixel value in *p and colormap ID in *cmap.
 */
static void 
DoGrabPixel(Widget w, Pixel * p, Colormap * cmap)
{
    int x, y, nx, ny;
    XImage *xim;
    Window root = RootWindowOfScreen(XtScreen(w));
    Window window;
    Display *dpy = XtDisplay(w);

    doGrab(w, &x, &y);

    xyToWindowCmap(dpy, x, y, root, &nx, &ny, &window, cmap);

    xim = XGetImage(dpy, window, nx, ny, 1, 1, AllPlanes, ZPixmap);

    *p = XGetPixel(xim, 0, 0);

    XDestroyImage(xim);
}

/*
 * Grab a pixel of some window.
 * Returns coords of event.
 */
static void 
doGrab(Widget w, int *x, int *y)
{
    Display *dpy = XtDisplay(w);
    XtAppContext app = XtWidgetToApplicationContext(w);
    Window root = DefaultRootWindow(dpy);
    XEvent event;
    Cursor cursor = XCreateFontCursor(dpy, XC_crosshair);
    int count = 0;

    /* Set up grab cursor */
    if (XGrabPointer(dpy, root, False,
		     ButtonPressMask | ButtonReleaseMask,
		     GrabModeSync, GrabModeAsync,
		     root, cursor, CurrentTime))
	return;

    do {
	XAllowEvents(dpy, SyncPointer, CurrentTime);
	XtAppNextEvent(app, &event);
	if (event.type == ButtonPress)
	    count++;
	else if (event.type == ButtonRelease) {
	    if (count == 1)
		break;
	    else
		count--;
	} else
	    XtDispatchEvent(&event);
    } while (1);

    XUngrabPointer(dpy, CurrentTime);

    *x = event.xbutton.x;
    *y = event.xbutton.y;
}

/*
 * Given coords x,y in the 'base' window, descend the window hierarchy
 * and find the child window of class InputOutput containing those
 * coordinates. Return coords in child window in (*nx,*ny).
 * If the child window has a colormap, return that; otherwise return
 * the default colormap for the display.
 */
static void 
xyToWindowCmap(Display * dpy, int x, int y, Window base,
	       int *nx, int *ny, Window * window, Colormap * cmap)
{
    Window twin;
    Colormap tmap;
    Window child, sub;
    XWindowAttributes attr;

    twin = base;
    tmap = None;

    sub = base;
    *nx = x;
    *ny = y;

    while (sub != None) {
	x = *nx;
	y = *ny;
	child = sub;
	XTranslateCoordinates(dpy, base, child, x, y, nx, ny, &sub);
	base = child;

	XGetWindowAttributes(dpy, child, &attr);
	if (attr.class == InputOutput && attr.colormap != None) {
	    tmap = attr.colormap;
	    twin = child;
	}
    }

    if (tmap == None)
	*cmap = DefaultColormap(dpy, DefaultScreen(dpy));
    else
	*cmap = tmap;
    *window = twin;
}
#endif /* COLORDELTA */