<?php

/* --------------------------------------------------------------------
    ULAM SPIRAL GENERATOR
      Returns PNG image of ulam spiral with resolution of 1 pixel.
        Defined: http://en.wikipedia.org/wiki/Ulam_spiral
      
      Based on the work of Mgccl at:
        http://mgccl.com/2007/05/07/the-most-optimal-php-prime-spiral-generator-yet

      Modified by Robert Mark Howting, Nov. 2, 2008.
      
      Modifications:
      1) Will return an irregular rectangle of specified height 
         and width (cropped from original square) image.
      2) esprime() optimized for two being the only even prime.
      3) Rewrite of coordinate calculation for prime pixels.
         Calculations are now based on the value and coordinates of 
         the corner pixel where the $n row and column intersect.
      4) Image size may be passed in the query string:
           .../ulam.php?height=480&width=640
         If only one is passed, a square image is returned.
      5) Background and highlight colors may be passed in the query 
         string as six character hex numbers "rrggbb".
           .../ulam.php?hi=ff00ff&bg=0000a0

      The basic quick logic by Mgccl remains.  Changes to esprime() 
      result in a slight speed improvement.  Coordinate calculations 
      provide no more speed but are easier to follow. 
-------------------------------------------------------------------- */

//=== HEIGHT, WIDTH & COLORS from QUERY STRING
$height = 0; $width = 0; $bg = ''; $hi = '';
if(isset($_GET['height']) && is_numeric($_GET['height'])) 
  $height = intval( $_GET['height'] );
if(isset($_GET['width']) && is_numeric($_GET['width'])) 
  $width = intval( $_GET['width'] ); 
if     ($height>1 && empty($width))  $width  = $height;
elseif ($width>1  && empty($height)) $height = $width;
if(isset($_GET['bg'])) $bg = color_string2array($_GET['bg']);
if(isset($_GET['hi'])) $hi = color_string2array($_GET['hi']);

//=== HEIGHT, WIDTH and COLOR DEFAULTS
if (empty($height)) $height = 160;  // Crop image to rectangle 
if (empty($width))  $width  = 160;  // with these dimensions.
if (empty($bg))     $bg = array(0,0,0);        // Background color rgb.
if (empty($hi))     $hi = array(255,255,255);  // Prime pixel color rgb.

//=== CREATE BLANK IMAGE ===
$size     = max($height,$width);       // Build original image as 
$image    = imagecreate($size,$size);  // a square of max size. 
$bg_color = imagecolorallocate($image,$bg[0],$bg[1],$bg[2]);
$hi_color = imagecolorallocate($image,$hi[0],$hi[1],$hi[2]);

//=== GET ARRAY of PRIMES ===
$prime = esprime($size * $size);

//=== HIGHLIGHT PRIME PIXELS IN IMAGE ===
$x_adj    = ~$size&1;       // Shift 1px left if $size is even
$i = 0; $n = 2; $sn = 4;    // Start $n=2 (1 is not a prime)
$center   = floor($size/2); // Center Pixel (value 1)
$corner_y = $center - 1;    // Vertical offset from center
$corner_x = $center + 1;    // Horizontal offset from center
$corner = 3;                // Value at $corner_x, $corner_y
while($n<=$size) {
  if($prime[$i]<=$sn) {
    $p = $prime[$i++];
    $y = $corner_y;     // Calculate offset and direction
    $x = $corner_x;     //    from the current corner.
    if($n&1) $offset = $p - $corner;  // OFFSET from corner, $n even
    else     $offset = $corner - $p;  // OFFSET from corner, $n odd
    if($p<$corner) $y += $offset;     // VERTICAL offset 
    else           $x += $offset;     // HORIZONTAL offset 
    imagesetpixel($image,$x-$x_adj,$y,$hi_color);
    if($i==count($prime)) break; } // Exit if all primes highlighted
  else {
    $n++; 
    $sn = $n * $n;
    //=== Calc corner cordinates and value for $n
    $offset = floor($n/2);
    if($n&1) { $corner_y = $center + $offset;
               $corner_x = $center - $offset; }
    else {     $corner_y = $center - $offset;
               $corner_x = $center + $offset; }
    $corner = $sn - $n + 1; } }

//=== CROP & RETURN IMAGE ===
header("Content-type: image/png");
if($height!=$width) {
  $image_cropped = imagecreate($width,$height);
  $x = 0; $y = 0;
  if ($width>$height) $y = floor(($width-$height)/2);
  else                $x = floor(($height-$width)/2);
  imagecopy($image_cropped,$image,0,0,$x,$y,$width,$height);
  imagepng($image_cropped); }
else {
  imagepng($image); }

//=== END ===
exit;


//======================================================
//=== SIEVE of ERATOSTHENES
//===   Like the Mgccl original but optimized
//===   for two being the only even prime.
//======================================================
function esprime($limit) {
  //=== Build data string with even numbers excluded.
  $i = str_repeat('01',ceil($limit/2));
  //=== Exclude odd non-primes
  $sqrtlimit = sqrt($limit);
  $n = 3;
  while($n < $sqrtlimit) {
    if ($i[$n]) {
      $k = $n * $n;
      $i[$k] = 0;
      while($k<=$limit) {
        $k += $n;
        $i[$k] = 0; } }
    $n += 2; }
  //=== Return two as prime.
  if($limit>=2) $primes[0] = 2;
  //=== Return odd primes.  
  $n = 3;
  while($n<$limit) {
    if($i[$n]) $primes[] = $n;
    $n += 2; }
  return $primes; }

//======================================================
//=== RGB ARRAY FROM HEX COLOR STRING ffffff
//======================================================
function color_string2array($c) {
  if (empty($c) || strlen($c)!=6) return array(127,127,127);
  $r = hexdec(substr($c,0,2));
  $g = hexdec(substr($c,2,2));
  $b = hexdec(substr($c,4,2));
  return array($r,$g,$b);
}

  
?>