/*****************************************************************
 * flflyd.c: FBM Release 1.0 25-Feb-90 Michael Mauldin
 *
 * Copyright (C) 1989,1990 by Michael Mauldin.  Permission is granted
 * to use this file in whole or in part for any purpose, educational,
 * recreational or commercial, provided that this copyright notice
 * is retained unchanged.  This software is available to all free of
 * charge by anonymous FTP and in the UUNET archives.
 *
 * flflyd.c: 
 *
 * CONTENTS
 *	floyd_fbm (input, output)
 *
 * EDITLOG
 *	LastEditDate = Mon Jun 25 00:07:41 1990 - Michael Mauldin
 *	LastFileName = /usr2/mlm/src/misc/fbm/flflyd.c
 *
 * HISTORY
 * 25-Jun-90  Michael Mauldin (mlm@cs.cmu.edu) Carnegie Mellon
 *	Package for Release 1.0
 *
 * 20-May-89  Michael Mauldin (mlm) at Carnegie Mellon University
 *	Bug fix from Dave Cohrs <dave@cs.wisc.edu>
 *
 * 07-Mar-89  Michael Mauldin (mlm) at Carnegie Mellon University
 *	Beta release (version 0.9) mlm@cs.cmu.edu
 *
 * 12-Nov-88  Michael Mauldin (mlm) at Carnegie-Mellon University
 *	Created.
 *****************************************************************/

# include <stdio.h>
# include <math.h>
# include <ctype.h>
# include "fbm.h"

/*****************************************************************
 * floyd_fbm: Classical Floyd-Steinberg Halftoning
 *
 * REFERENCES
 *	Digital Halftoning, by Robert Ulichney (1986 MIT Press)
 *****************************************************************/

# define RAND(RN) (((seed = 1103515245 * seed + 12345) >> 12) % (RN))
# define INITERR(X,Y) \
	(((int) X) - (((int) Y)?WHITE:BLACK) + ((WHITE/2)-((int) X))/2)

#ifndef lint
static char *fbmid =
"$FBM flflyd.c <1.0> 25-Jun-90  (C) 1989,1990 by Michael Mauldin, source \
code available free from MLM@CS.CMU.EDU and from UUNET archives$";
#endif

floyd_fbm (input, output)
FBM *input, *output;
{ register unsigned char *bmp, *obm;
  register int i, j, rowlen, gray, error, w, h, den, outrow;
  int *lerr, *cerr, *terr;
  register int seed = 0;

  if (input->hdr.planes != 1)
  { fprintf (stderr, "floyd_fbm: can't halftone color images\n");
    return (0);
  }

  fprintf (stderr, "Floyd-Steinberg halftoning\n");

  /* Allocate output */
  free_fbm (output);
  output->hdr = input->hdr;
  output->hdr.bits = 1;
  output->hdr.physbits = 8;
  outrow = 16 * ((input->hdr.cols + 15) / 16); /* Pad to even byte boundary */
  output->hdr.rowlen = outrow;
  output->hdr.plnlen = outrow*output->hdr.rows;
  alloc_fbm (output);

  w = input->hdr.cols;
  h = input->hdr.rows;
  rowlen = input->hdr.rowlen;
  
  /* Allocate space for error arrays */
  lerr = (int *) malloc (w * sizeof (*lerr));
  cerr = (int *) malloc (w * sizeof (*cerr));
  for (i=0; i<w; i++) lerr[i] = cerr[i] = 0;

  /* The left border */
  error = 0;
  for (j=0; j<h; j++)
  { register int thresh = (WHITE/2 + RAND (129) - 64);

    gray = input->bm[j*rowlen] + error;
    den = gray > thresh ? WHITE : BLACK;
    error = gray - den;
    output->bm[j*outrow] = den;
  }

  /* The right border */
  error = 0;
  for (j=0; j<h; j++)
  { register int thresh = (WHITE/2 + RAND (129) - 64);

    gray = input->bm[j*rowlen + (w-1)] + error;
    den = gray > thresh ? WHITE : BLACK;
    error = gray - den;
    output->bm[j*outrow + (w-1)] = den;
  }

  /* The top border */
  error = 0;
  for (i=0; i<w; i++)
  { register int thresh = (WHITE/2 + RAND (129) - 64);

    gray = input->bm[i] + error;
    den = gray > thresh ? WHITE : BLACK;
    error = gray - den;
    output->bm[i] = den;
    lerr[i] = INITERR (input->bm[i], den);
  }

  /*
   * Now process the interior bits
   *
   *  Weights:			1 5 3
   *				7 *
   */

  for (j=1; j<h; j++)
  { /* scan left to right */
    bmp = &input->bm[j*rowlen];
    obm = &output->bm[j*outrow];

    cerr[0] = INITERR (bmp[0], obm[0]);

    for (i=1; i<w-1; i++)
    {
      error =  (lerr[i-1] + 5 * lerr[i] + 3 * lerr[i+1] + 7 * cerr[i-1]) / 16;

# ifdef DEBUG
      if (i > 5 && i < 9 && j > 5 && j < 9)
      { fprintf (stderr, "<%2d,%2d>  Input %3d, Error %5d, Output %d\n",
		 i, j, bmp[i], error, bmp[i] + error > (WHITE/2));
	fprintf (stderr, "Errors:   %5d  %5d  %5d\n          %5d      *\n\n", 
		 lerr[i-1], lerr[i], lerr[i+1], cerr[i-1]);
      }
# endif

      gray = bmp[i] + error;

      if (gray > (WHITE/2))
      { obm[i] = WHITE;	cerr[i] = gray - WHITE; }
      else
      { obm[i] = BLACK;	cerr[i] = gray - BLACK; }
    }
    
    /* Set errors for ends of the row */
    cerr[0]   = INITERR (bmp[0], obm[0]);
    cerr[w-1] = INITERR (bmp[w-1], obm[w-1]);
    
    /* Swap error buffers */
    terr = lerr; lerr = cerr; cerr = terr;
  }
  
  return (1);
}