/* The Computer Language Benchmarks Game
   http://shootout.alioth.debian.org/

   contributed by Greg Buchholz (original iterative version)
   modified by Yannick Gingras (made tail recursive)
   adjusted slightly for Utah CS 4960-01 by Matthew Flatt
*/

#include <stdio.h>
#include <stdlib.h>

int iterate(double Zr, double Zi,
	    double Tr, double Ti,
	    double Cr, double Ci,
	    int iter)
{

  if (iter == 0)
    return 1;

  Zi = 2.0 * Zr * Zi + Ci;
  Zr = Tr - Ti + Cr;
  Tr = Zr * Zr;
  Ti = Zi * Zi;

  if (Tr + Ti > 4.0)
    return 0;

  return iterate (Zr, Zi, Tr, Ti, Cr, Ci, iter - 1);
}

int main (int argc, char **argv)
{
  int w, h, buflen, rowlen, bit_num = 0;
  char byte_acc = 0;
  char *buf, *pbuf;
  double x, y, wrat, hrat;
  double Cr, Ci;

  w = h = atoi (argv[1]);
  wrat = 2.0 / w;
  hrat = 2.0 / h;
  rowlen = (w / 8 + (w % 8 ? 1 : 0));
  buflen = rowlen * h;
  buf = (char *) malloc (buflen);
  pbuf = buf;

  /* The mandelbort image is written to buf, which is an array
     of rowlen * h bytes, where each rowlen bytes is one line
     of the image (representing w pixels). */

  printf ("P4\n%d %d\n", w, h);

  for (y = 0; y < h; ++y)
    {
      Ci = y * hrat - 1.0;

      for (x = 0; x < w; ++x)
	{
	  Cr = x * wrat - 1.5;

	  byte_acc <<= 1;
	  if (iterate (0.0, 0.0, 0.0, 0.0, Cr, Ci, 50))
	    byte_acc |= 0x01;

	  if (++bit_num == 8)
	    {
	      *(pbuf++) = byte_acc;
	      bit_num = byte_acc = 0;
	    }
	}

      if (bit_num)
	{
	  byte_acc <<= (8 - w % 8);

	  *(pbuf++) = byte_acc;
	  bit_num = byte_acc = 0;
	}
    }

  fwrite (buf, buflen, 1, stdout);
  return 0;
}