/*-
 * Copyright (c) 1995 The Apache Group. All rights reserved.
 * 
 *
 * Apache httpd license
 * ====================
 * 
 *
 * This is the license for the Apache Server. It covers all the
 * files which come in this distribution, and should never be removed.
 * 
 * The "Apache Group" has based this server, called "Apache", on
 * public domain code distributed under the name "NCSA httpd 1.3".
 * 
 * NCSA httpd 1.3 was placed in the public domain by the National Center 
 * for Supercomputing Applications at the University of Illinois 
 * at Urbana-Champaign.
 * 
 * As requested by NCSA we acknowledge,
 * 
 *  "Portions developed at the National Center for Supercomputing
 *   Applications at the University of Illinois at Urbana-Champaign."
 *
 * Copyright on the sections of code added by the "Apache Group" belong
 * to the "Apache Group" and/or the original authors. The "Apache Group" and
 * authors hereby grant permission for their code, along with the
 * public domain NCSA code, to be distributed under the "Apache" name.
 * 
 * Reuse of "Apache Group" code outside of the Apache distribution should
 * be acknowledged with the following quoted text, to be included with any new
 * work;
 * 
 * "Portions developed by the "Apache Group", taken with permission 
 *  from the Apache Server   http://www.apache.org/apache/   "
 *
 *
 * Permission is hereby granted to anyone to redistribute Apache under
 * the "Apache" name. We do not grant permission for the resale of Apache, but
 * we do grant permission for vendors to bundle Apache free with other software,
 * or to charge a reasonable price for redistribution, provided it is made
 * clear that Apache is free. Permission is also granted for vendors to 
 * sell support for Apache. We explicitly forbid the redistribution of 
 * Apache under any other name.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * 
 */

/*
 * This imagemap module started as a port of the original imagemap.c
 * written by Rob McCool (11/13/93 robm@ncsa.uiuc.edu).
 * This version includes the mapping algorithms found in version 1.3
 * of imagemap.c.
 *
 * Contributors to this code include:
 *
 * Kevin Hughes, kevinh@pulua.hcc.hawaii.edu
 *
 * Eric Haines, erich@eye.com
 * "macmartinized" polygon code copyright 1992 by Eric Haines, erich@eye.com
 *
 * Randy Terbush, randy@zyzzyva.com
 * port to Apache module format, "base_uri" and support for relative URLs
 * 
 * James H. Cloos, Jr., cloos@jhcloos.com
 * Added point datatype, using code in NCSA's version 1.8 imagemap.c
 * program, as distributed with version 1.4.1 of their server.
 * The point code is originally added by Craig Milo Rogers, Rogers@ISI.Edu
 *
 * Nathan Kurz, nate@tripod.com
 * Partial rewrite/reorginazation to be generally more forgiving.
 * main changes:  uses 'default' if no coordinates given (Lynx).
 *                ignores bad lines in map file instead of server error.
 *                bug in uri_base handling that sometimes caused relative
 *		      urls in Location fixed; more schemes checked for.
 *		  'point' directive mixes better with 'default' directive.
 */

#include "httpd.h"
#include "http_config.h"
#include "http_request.h"
#include "http_core.h"
#include "http_protocol.h"
#include "http_main.h"
#include "http_log.h"
#include "util_script.h"


#define IMAP_MAGIC_TYPE "application/x-httpd-imap"
#define MAXLINE 500
#define MAXVERTS 100
#define X 0
#define Y 1

char *getline(char *, int, FILE *);
double strtod();   /* SunOS needed this */

module imap_module;

int pointinrect(double point[2], double coords[MAXVERTS][2])
{
    return ((point[X] >= coords[0][X] && point[X] <= coords[1][X]) &&
	    (point[Y] >= coords[0][Y] && point[Y] <= coords[1][Y]));
}

int pointincircle(double point[2], double coords[MAXVERTS][2])
{
    int radius1, radius2;

    radius1 = ((coords[0][Y] - coords[1][Y]) * (coords[0][Y] - coords[1][Y]))
	+ ((coords[0][X] - coords[1][X]) * (coords[0][X] - coords[1][X]));
    
    radius2 = ((coords[0][Y] - point[Y]) * (coords[0][Y] - point[Y]))
	+ ((coords[0][X] - point[X]) * (coords[0][X] - point[X]));

    return (radius2 <= radius1);
}

int pointinpoly(double point[2], double pgon[MAXVERTS][2])
{
    int i, numverts, inside_flag, xflag0;
    int crossings;
    double *p, *stop;
    double tx, ty, y;

    for (i = 0; pgon[i][X] != -1 && i < MAXVERTS; i++);

    numverts = i;
    crossings = 0;

    tx = point[X];
    ty = point[Y];
    y = pgon[numverts - 1][Y];

    p = (double *) pgon + 1;
    if ((y >= ty) != (*p >= ty)) {

	if ((xflag0 = (pgon[numverts - 1][X] >= tx)) == (*(double *) pgon >= tx)) {
	    if (xflag0)
		crossings++;
	}
	else {
	    crossings += (pgon[numverts - 1][X] - (y - ty) *
			  (*(double *) pgon - pgon[numverts - 1][X]) /
			  (*p - y)) >= tx;
	}
    }

    stop = pgon[numverts];

    for (y = *p, p += 2; p < stop; y = *p, p += 2) {
	
	if (y >= ty) {
        
	    while ((p < stop) && (*p >= ty))
		p += 2;
	    
	    if (p >= stop)
		break;
	    if ((xflag0 = (*(p - 3) >= tx)) == (*(p - 1) >= tx)) {
		
		if (xflag0)
		    crossings++;
	    }
	    else {
		crossings += (*(p - 3) - (*(p - 2) - ty) *
			      (*(p - 1) - *(p - 3)) / (*p - *(p - 2))) >= tx;
	    }
	}
	else {
	    while ((p < stop) && (*p < ty))
		p += 2;

	    if (p >= stop)
		break;

	    if ((xflag0 = (*(p - 3) >= tx)) == (*(p - 1) >= tx)) {
		if (xflag0)
		    crossings++;
	    }
	    else {
		crossings += (*(p - 3) - (*(p - 2) - ty) *
			      (*(p - 1) - *(p - 3)) / (*p - *(p - 2))) >= tx;
	    }
	}
    }

    inside_flag = crossings & 0x01;
    return (inside_flag);
}


int is_closer(double point[2], double coords[MAXVERTS][2], double *closest)
{
  double dist_squared =((point[X] - coords[0][X]) * (point[X] - coords[0][X]))
	     + ((point[Y] - coords[0][Y]) * (point[Y] - coords[0][Y]));

  if (point[X] < 0 || point[Y] < 0 ) 
    return(0);          /* don't mess around with negative coordinates */

  if ( *closest < 0 || dist_squared < *closest ) {
    *closest = dist_squared;
    return(1);         /* if this is the first point or is the closest yet
			  set 'closest' equal to this distance^2 */
  }
  
  return(0);           /* if it's not the first or closest */

}

double get_x_coord(char *args) 
{
  char *endptr = NULL;
  double x_coord = -1;    /* -1 is returned if no coordinate is given */

  if (args == NULL)
    return(-1);           /* in case we aren't passed anything */

  while( *args && !isdigit(*args) && *args != ',') 
    args++;   /* jump to the first digit, but not past a comma or end */

  x_coord = strtod(args, &endptr);

  if (endptr > args)   /* if a conversion was made */
    return(x_coord); 

  return(-1);  /* else if no conversion was made, or if no args was given */
}

double get_y_coord(char *args) 
{
  char *endptr = NULL;
  char *start_of_y = NULL;
  double y_coord = -1;    /* -1 is returned on error */

  if (args == NULL)
    return(-1);           /* in case we aren't passed anything */

  start_of_y = strchr(args, ',');  /* the comma */

  if (start_of_y) {
    
    start_of_y++;    /* start looking at the character after the comma */

    while( *start_of_y && !isdigit(*start_of_y))  
      start_of_y++;  /* jump to the first digit, but not past the end */

    y_coord = strtod(start_of_y, &endptr);

    if (endptr > start_of_y) 
      return(y_coord); 
  }
  
  return(-1);   /* if no conversion was made, or no comma was found in args */
}
  

void set_redirect(request_rec *r, char *base_uri, char *mapurl) 
{
  char redirect[MAXLINE] = {'\0'};
  char *string_pos      = base_uri;
  char *directory       = NULL;

  if (
      (!strncmp(mapurl, "http:", 5))   ||
      (!strncmp(mapurl, "mailto:", 7)) ||
      (!strncmp(mapurl, "news:", 5))   ||
      (!strncmp(mapurl, "ftp:", 4))    ||
      (!strncmp(mapurl, "gopher:", 7)) ||
      (!strncmp(mapurl, "nntp:", 5))       ) {

    table_set(r->headers_out, "Location", mapurl);
    return;                    /* if they give us an absolute URL, use it! */
  }

  while (*string_pos) {   /* starts out the same as base_uri */

    if (*string_pos == '/' && *(string_pos+1) == '/') {
      string_pos += 2;  /* if there are two slashes, jump over them */
      continue;
    }

    if (*string_pos == '/') {  /* the first single slash */
	if ( mapurl[0] == '/' ) {
	  *string_pos = '\0';  
	}              /* if the URL from the map starts from root, end the
			  base URL string at the first single slash */
	else {
	  directory = string_pos; /* save the start of the directory portion */

	  string_pos = strrchr(string_pos, '/');  /* now reuse string_pos */
	  string_pos++;  /* step over that last slash */
	  *string_pos = '\0';
	}              /* otherwise make sure we are dealing with a directory
			  instead of a file */
	break;
      }
	
    string_pos++;   /* until we get to the end of base_uri without finding
		       a slash by itself */
  }
                    /* by this point, base_uri never ends with a slash.
		       it has to come from mapurl if there's to be one. */

  while ( ! strncmp(mapurl, "../", 3) || ! strcmp(mapurl, "..") ) { 
                       /* handle relative mapurl's from the map file */

    if ( directory && (string_pos = strrchr(directory, '/')) ) 
      *string_pos = '\0';
                       /* for each '..',  knock a directory off the end 
			   by ending the string right at the last slash.
			   But only consider the directory portion: don't eat
			   into the server name.  And only try if a directory
			   portion was found */    

    mapurl += 2;      /* jump over the '..' that we found in the mapurl */
      
    if (! strncmp(mapurl, "/../", 4) || ! strcmp(mapurl, "/..") )
                      /* check for both so a file ..foo still works */

      mapurl++;       /* step over the '/' if there are more '..' to do.
			   this way, we leave the starting '/' on mapurl after
			   the last '..', but get rid of it otherwise */ 
     
  }                   /* by this point, mapurl does not start with '..' */

                         
  sprintf(redirect, "%s%s", base_uri, mapurl);   

  table_set(r->headers_out, "Location", redirect);

  return;

}



int imap_handler(request_rec *r)
{
  char base_uri[MAXLINE] = {'\0'};
  char input[MAXLINE] = {'\0'};
  char maptype[MAXLINE] = {'\0'};
  char mapurl[MAXLINE] = {'\0'};
  char mapdflt[MAXLINE] = {'\0'};
  char mapclosest[MAXLINE] = {'\0'};
  double closest = -1;

  double testpoint[2];
  double pointarray[MAXVERTS][2] = { {-1,-1} };
  int vertex = 0;

  char *referer = table_get(r->headers_in, "Referer");

  char *string_pos = NULL;
  int chars_read = 0;

  FILE *imap;
  
  if (! (imap = fopen(r->filename, "r"))) 
    return SERVER_ERROR;

  if (r->server->port == 80 ) 
    sprintf(base_uri, "http://%s", r->server->server_hostname);
  else
    sprintf(base_uri, "http://%s:%d", r->server->server_hostname,
	    r->server->port);
                           /* base_uri starts as http://server_hostname,
			      can later be changed by lines in map file */

  testpoint[X] = get_x_coord(r->args);
  testpoint[Y] = get_y_coord(r->args);

  while (getline(input, MAXLINE, imap)) {

    if ( input[0] == '#' ||  ! input[0] )
      continue;            /* ignore comments and blank lines */

    string_pos = input;   /* always start at the beginning of line */

    bzero(maptype, MAXLINE);
    bzero(mapurl, MAXLINE);  /* clear these just to be safe */

    sscanf(input, "%s %s %n", maptype, mapurl, &chars_read);
    string_pos += chars_read;
    
    if ( ! strcmp(maptype, "base_uri")  ) {         /* base_uri */

      if      ( ! strcmp(mapurl, "map") ) 
	strcpy(base_uri, r->uri);  /* use the map as the base */

      else if ( ! strcmp(mapurl, "referer") )
	if (referer)
	  strcpy(base_uri, referer); /* use the refering page as base */
      /* if there is no refering page, the base is left as http://servername */

      else
	strcpy(base_uri, mapurl);  /* use what we are given as base */

      continue;
    }	

    if ( ! strcmp(maptype, "default")   ) {        /* default */

      strcpy(mapdflt, mapurl);     /* use what is given as the default */
      
      continue;
    }
    
    if ( testpoint[X] < 0 || testpoint[Y] < 0 ) { /* no coordinates */

      /* if we don't have valid test coordinates,
	 don't bother trying any of the tests that 
	 follow (point, rect, poly, etc) */
      continue;
    }

    vertex = 0;
    while ( vertex < MAXVERTS &&  
	   sscanf(string_pos, "%lf,%lf %n", &pointarray[vertex][X], 
		  &pointarray[vertex][Y], &chars_read)   == 2) {
      string_pos += chars_read;
      vertex++;
    }                /* so long as there are more vertices to read, and
			we have room, read them in.  We start where we left
			off of the last sscanf, not at the beginning.*/
                  
    pointarray[vertex][X] = -1;  /* signals the end of vertices */

    
    if ( ! strcmp(maptype, "poly")   ) {        /* poly */

      if (pointinpoly (testpoint, pointarray) ) {
	set_redirect(r, base_uri, mapurl);     
	fclose(imap);
	return REDIRECT;

      }
    }

    if ( ! strcmp(maptype, "circle")   ) {        /* circle */

      if (pointincircle (testpoint, pointarray) ) {
	set_redirect(r, base_uri, mapurl);     
	fclose(imap);
	return REDIRECT;

      }
    }

    if ( ! strcmp(maptype, "rect")   ) {        /* rect */

      if (pointinrect (testpoint, pointarray) ) {
	set_redirect(r, base_uri, mapurl);     
	fclose(imap);
	return REDIRECT;

      }
    }
    
    if ( ! strcmp(maptype, "point") ) {         /* point */
      
      if (is_closer(testpoint, pointarray, &closest) ) 
	strcpy(mapclosest, mapurl);  /* if the closest point yet save it */

      continue;    
    }     /* move on to next line whether it's closest or not */

          /* nothing matched, so we get another line! */
  }       /* (I wonder if that should be logged as an error?) */
        

  fclose(imap);         /* we won't be needing the map file anymore */
  
  if (*mapclosest) {    /* if a 'point' directive has been seen */
    set_redirect(r, base_uri, mapclosest);     
    fclose(imap);       /* redirect to the closest point found */
    return REDIRECT;
  }    

  if (*mapdflt) {       /* if a default has been assigned */
    set_redirect(r, base_uri, mapdflt);
    fclose(imap);       /* redirect to that default */
    return REDIRECT;
  }    

  return SERVER_ERROR;  /* they lose -- but we get here if and only if there
			   was no default and nothing matched */

}


handler_rec imap_handlers[] = {
{ IMAP_MAGIC_TYPE, imap_handler },
{ NULL }
};

module imap_module = {
   STANDARD_MODULE_STUFF,
   NULL,			/* initializer */
   NULL,			/* dir config creater */
   NULL,			/* dir merger --- default is to override */
   NULL,			/* server config */
   NULL,			/* merge server config */
   NULL,			/* command table */
   imap_handlers,		/* handlers */
   NULL,			/* filename translation */
   NULL,			/* check_user_id */
   NULL,			/* check auth */
   NULL,			/* check access */
   NULL,			/* type_checker */
   NULL,			/* fixups */
   NULL				/* logger */
};