/* sf_generate.c
 *
 * Snowflake code by Raph Levien <raph@c2.org> 
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <math.h>
#include <sys/time.h>

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>

#include "getopt.h"
#include "sf.h"

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* defines */

#define MAX_A         256
#define MAX_B         128

#define COS_60_DEG      0.5000000
#define SIN_60_DEG      0.8660254

#define ROOT_3          1.7320508
#ifndef PI
#define PI              3.1415927
#endif

#define SCALE           3.6275987  /* = 2.0 *PI / ROOT_3 */

#define RAND_SEED       0x0601

#define MAX_HASH      256
#define MAX_FRONTIER 1024

#define HASH_SIZE       8             /* 1 2 3 4  5  6  7   8 */
#define HASH_MASK      (HASH_SIZE-1)  /* 0 1 2 3  4  5  6   7 */
#define HASH_BIT       (1<<HASH_MASK) /* 1 2 4 8 16 32 64 128*/

#define HASH_FACTOR     4             /* bits per hex digit */

#define PING_INTERVAL   5000 /* milliseconds */

static char* hex_ch = "0123456789ABCDEF";

#define HEX( ch ) ( (char)( strchr( hex_ch,(int)ch ) - hex_ch ) )

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* types */

/* colours */

typedef unsigned char colour;

const colour gray  = 0;
const colour white = 1;
const colour black = 2;

typedef struct coord
{
  int a;
  int b;
} coord;

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* (static) globals */

static unsigned char   hash[MAX_HASH];
static int             hashptr;
static int             hash_n;

static coord           frontier[MAX_FRONTIER];
static int             frontier_n;

/* flake is a hexagonal matrix
 *  in cartesian space, the A axis is rotated
 *  60 degrees from the B axis */
static colour          flake[MAX_A][MAX_B];

static float           max_dist;

static int             random_number;

static size_e          size          = size_256x256;
static symmetry_e      symmetry      = symmetry_VERTICAL;
static edges_e         edges         = edges_YES;
static colour_scheme_e colour_scheme = colour_scheme_WHITE_ON_BLACK;
static int             banding;
static int             centre;

static char            key[MAX_KEY+1];

static int             image_size    = 0;
static char            white_pixel   = WHITE_PIXEL;
static char            black_pixel   = BLACK_PIXEL;

static int             generating;

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* prototypes */

static snowflake_cmd get_cmd( msg_pipe mp,snowflake_message* msg );

static void hash_key( char* str );
static int  hash_bit( void );
static int  hash_eof( void );

static void seed_rand( void );
static int  next_rand( void );

static void fill             ( int a,int b,int bit );
static void add_if_gray      ( int a,int b );

static void build_snowflake( char* image );
static void rect_to_hex( int x,int y,int o,float s,int* a_,int* b_ );

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

void generation_main( int      argc,
                      char*    argv[],
                      msg_pipe control,
                      int      image_semid,
                      char*    image )
{
  int               pid;
  int               control_pid;
  int               quit;
  snowflake_cmd     cmd;
  snowflake_message msg;
  colour            edge_colour;

  int               bit;
  int               f;
  int               a,
                    b;

  pid = getpid();
  control_pid = getppid();

  generating = FALSE;

  quit       = FALSE;

  while ( !quit && ( ( cmd = get_cmd( control,&msg ) ) != cmd_NULL ) )
  {

    switch ( cmd )
    {
      case cmd_QUIT :      /* Control is telling us to quit */
        quit = TRUE;
        break;

      case cmd_TIMEOUT :   /* get_cmd() timeout, check Control */
        if ( !is_alive( control_pid ) )
        {
          fprintf( stderr,"Generate: Control has died\n" );
          quit = TRUE;
        }
        break;

      case cmd_PING :      /* respond to a Control ping */
        msg.cmd = cmd_PONG;
        msg.data.i = pid;
        if ( !snd_msg( control,&msg ) )
        {
          fprintf( stderr,"Generate: unable to send PONG command\n" );
          quit = TRUE;
        }
        break;

      case cmd_GENERATE :  /* generate request */

        if ( generating )
        {
          msg.cmd = cmd_ACK;
          if ( !snd_msg( control,&msg ) )
          {
            fprintf( stderr,"Generate: unable to send ACK command\n" );
            quit = TRUE;
          }
        }

        generating = TRUE;

        if ( sscanf( msg.data.s,GENERATE_SCAN_FORMAT,
                     key,
                    &size,
                    &symmetry,
                    &edges,
                    &colour_scheme,
                    &banding,
                    &centre ) != 7 )
        {
          fprintf( stderr,"Generate: ill-formed command data\n" );
          quit = TRUE;
          break;
        }

        image_size = get_image_size( size );

        memset( (void*)&flake,gray,sizeof( flake ) );

        max_dist = 1.0;

        frontier_n = 0;
        fill( 0,0,black );

        hash_key( key );

        seed_rand();

        bit = 0;
        while ( !hash_eof() )
        {
          /* choose a random frontier value */

          f = next_rand() % frontier_n;

          if ( frontier[f].b &&
               ( ( bit < centre ) || ( bit % banding ) ) )
            fill( frontier[f].a,frontier[f].b,hash_bit() );
          else
            fill( frontier[f].a,frontier[f].b,black );

          bit++;
        }

        /* change all grays to blacks */

        for ( a = 0; a < MAX_A; a++ ) 
          for ( b = 0; b < MAX_B; b++ )
            if ( flake[a][b] == gray )
              flake[a][b] = black;

        /* display edges? */

        if ( edges != edges_NO )
        {
          if ( edges == edges_YES )
            edge_colour = white;
          else
            edge_colour = gray;

          for ( f = 0; f < frontier_n; f++ )
            flake[ frontier[f].a ][ frontier[f].b ] = edge_colour;
        }

        /* set colour scheme */

        if ( colour_scheme == colour_scheme_WHITE_ON_BLACK )
        {
          white_pixel = WHITE_PIXEL;
          black_pixel = BLACK_PIXEL;
        }
        else
        {
          white_pixel = BLACK_PIXEL;
          black_pixel = WHITE_PIXEL;
        }

        /* wait on semaphore before building image */
        sem_wait( image_semid );

        build_snowflake( image );

        /* signal semaphore after building image */
        sem_signal( image_semid );

        generating = FALSE;

        /* acknowledge generate command */

        msg.cmd = cmd_ACK;
        if ( !snd_msg( control,&msg ) )
        {
          fprintf( stderr,"Generate: unable to send ACK command\n" );
          quit = TRUE;
        }
        break;

      case cmd_PONG :      /* only in response to a PING */
        break;

      case cmd_VIEW :      /* only for the View process */
        break;

      case cmd_ACK :       /* only in response to GENERATE */
        break;

    }
  }

  close( control.snd );
  close( control.rcv );

  exit( 0 );
}

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

static snowflake_cmd get_cmd( msg_pipe mp,snowflake_message* msg )
{
  int            rc;
  int            tt_sec,
                 tt_usec;
  int            fd_sets = FD_SETSIZE;
  fd_set         readfds,
                 writefds,
                 exceptfds;
  struct timeval t_timeout;

  tt_sec   = PING_INTERVAL / 1000;
  tt_usec  = PING_INTERVAL - ( tt_sec * 1000 );
  tt_usec *= 1000;

  FD_ZERO( &readfds );
  FD_SET( mp.rcv,&readfds );
  FD_ZERO( &writefds );
  FD_ZERO( &exceptfds );

  t_timeout.tv_sec  = tt_sec;
  t_timeout.tv_usec = tt_usec;

  if ( ( rc = select( fd_sets,
                     &readfds,&writefds,&exceptfds,
                     &t_timeout ) ) == -1 )
  {
    fprintf( stderr,"Generate: select error = %d\n",errno );
    return cmd_NULL;
  }

  if ( FD_ISSET( mp.rcv,&readfds ) )
  {
    if ( !rcv_msg( mp,msg ) )
    {
      fprintf( stderr,"Generate: incomplete message\n" );
      return cmd_NULL;
    }

    return msg->cmd;
  }

  return cmd_TIMEOUT;
}

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* bit hash */

static void hash_key( char* str )
{
  int           len;
  int           i;
  unsigned char ch;
  unsigned char h;

  
  len = strlen( str );
  if ( len > MAX_HASH-1 )
    len = MAX_HASH-1;

  memset( hash,0,MAX_HASH );

  i = 0;
  do
  {
    ch = toupper( str[i] );
    h = HEX( ch );
    hash[ i / 2 ] |= ( h << ( 4 * ( i & 1 ) ) );
    i++;
  } while ( i < len );

  hash_n = i * HASH_FACTOR;
  hashptr = 0;
}

static int hash_bit( void )
{
  int bit;
  
  bit = ( ( hash[ hashptr / HASH_SIZE ] &
  ( HASH_BIT >> ( hashptr & HASH_MASK ) ) ) != 0 );

  hashptr++;

  return bit;
}

static int hash_eof( void )
{
  return ( hashptr == hash_n );
}

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* random number generation */

static void seed_rand( void )
{
  random_number = RAND_SEED;
}

static int next_rand( void )
{
  random_number = ( ( random_number <<  1 )   & 0x7FFF
                | ( ( random_number >> 13 )
                  ^ ( random_number >> 14 ) ) & 0x0001 );

  return random_number;
}

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* colour a gray pixel, based on the value of the given bit */

static void fill( int a,int b,int bit )
{
  int   i;
  float x,
        y,
        r2;  /* x^2 + y^2 */

  /* delete coord from frontier, if present. */

  for ( i = 0; i < frontier_n; i++ )
    if ( frontier[i].a == a && frontier[i].b == b )
      frontier[i] = frontier[ --frontier_n ];

  if ( bit )
  {
    flake[a][b] = white;

    /* fill 6 neighbours */

    add_if_gray( a + 1,b     );
    add_if_gray( a - 1,b     );
    add_if_gray( a - 1,b + 1 );
    add_if_gray( a,    b + 1 );
    add_if_gray( a + 1,b - 1 );
    add_if_gray( a,    b - 1 );

    /* calculate maximum pixel distance */

    x  = a + b * COS_60_DEG + 1.0;
    y  =     b * SIN_60_DEG + 1.0;
    r2 = x * x + y * y;
    if ( r2 > max_dist )
      max_dist = r2;

  }
  else
    flake[a][b] = black;
}

/* Add to frontier, but only if gray and within the 30 degree slice. */

static void add_if_gray( int a,int b )
{
  int i;

  if ( a < 0 || b < 0 || b > a )
    return;

  if ( flake[a][b] == gray )
  {
    /* add coord to frontier if not already present. */

    for ( i = 0; i < frontier_n; i++ )
      if ( frontier[i].a == a && frontier[i].b == b )
        return;

    frontier[ frontier_n ].a = a;
    frontier[ frontier_n ].b = b;

    frontier_n++;
  }
}

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

static void build_snowflake( char* image )
{
  float  s;  /* scaling factor */
  int    o;  /* offset         */
  int    x,  /* pixel column   */
         y;  /* pixel row      */
  int*   h,  /* horizontal     */
     *   v;  /* vertical       */
  int    a,  /* hex coordinate, integer */
         b;  /* hex coordinate, integer */

  s =  image_size / ( SCALE * sqrt( max_dist + 1.0 ) );
  o = -image_size / 2;

  /* vertical or horizontal symmetry? */

  if ( symmetry == symmetry_VERTICAL )
  {
    v = &x;
    h = &y;
  }
  else
  {
    v = &y;
    h = &x;
  }

  /* write the header lines */

  write_image_header( image,image_size );

  for ( x = 0; x < image_size; x++ )
  {
    for ( y = 0; y < image_size; y++ )
    {
      /* convert coordinates */

      rect_to_hex( *h,*v,o,s,&a,&b );

      /* write the pixel */

      if ( ( a < 0 || a >= MAX_A ) ||                   /* off image */
           ( b < 0 || b >= MAX_B ) )
        write_image_pixel( image,x,y,black_pixel );
      else if ( flake[a][b] == white )                  /* white */
        write_image_pixel( image,x,y,white_pixel );
      else if ( flake[a][b] == black )                  /* black */
        write_image_pixel( image,x,y,black_pixel );
      else                                              /* gray */
      {
        if ( edges == edges_GRAY_SOLID )
          write_image_pixel( image,x,y,GRAY_PIXEL );
        else /* edges_GRAY_SOLID  */
        {
          if ( ( x ^ y ) & 1 )
            write_image_pixel( image,x,y,black_pixel );
          else
            write_image_pixel( image,x,y,white_pixel );
        }
      }

    }
  }

}

/* convert a rectangular coordinate [x,y] to
 *  a hexangular coordinate [a,b].
 *
 * the x and y coordinates are offset and scaled.
 *
 * y                                      b            
 *                                                     
 * |                                    /              
 * + -- + -- + -- +                    + -- + -- + -- +
 * |    |    |    |                   /    /    /    / 
 * + -- + -- + -- +         ==>      + -- + -- + -- +  
 * |    |    |    |                 /    /    /    /   
 * + -- + -- + -- +                + -- + -- + -- +    
 * |    |    |    |               /    /    /    /     
 * + -- + -- + -- + --  x        + -- + -- + -- + --  a
 *
 *
 *   the x axis and a axis are parallel
 */

static void rect_to_hex( int x,int y,int o,float s,int* a_,int* b_ )
{
  float  c,  /* triangular coordinate, real */
         d;  /* triangular coordinate, real */
  int    p,  /* triangular coordinate, integer */
         q;  /* triangular coordinate, integer */
  int    a,  /* hexangular coordinate */
         b;  /* hexangular coordinate */
  int    t;

  /* convert rectangular grid location (x,y)
   *      to triangular  grid location (p,q) */

  c  = ( x + o ) / ( s * SIN_60_DEG );
  d  = ( y + o ) /   s               ;
  d -= c * COS_60_DEG;

  p = 2 * floor( d );
  q =     floor( c );

  if ( c - floor( c ) + d - floor( d ) >= 1.0 )
    p++;

  /* convert triangular grid location (p,q)
   *      to hex        grid location (a,b) */

  a  = floor( ( 2 +   q + p ) / 3.0 );
  b  = floor( ( 3 + 2*q - p ) / 6.0 );

  /* apply hex symmetries */

  if ( b < 0 ) { a =  a + b; b = -b;            }
  if ( a < 0 ) { a = -a;     b =  b - a;        }
  if ( b < 0 ) { a =  a + b; b = -b;            }
  if ( b > a ) { t =  a;     a =  b;     b = t; }

  *a_ = a;
  *b_ = b;
}

/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */