Date:    Sat, 01 Oct 94 12:39:40 EDT
To:      Jef Poskanzer <jef@NETCOM.COM>
cc:      William Perry <wmperry@INDIANA.EDU>,
	 James Stichnoth <stichnot+@CS.CMU.EDU>,
	 Christos Zoulas <christos@DESHAW.COM>

From:    Darrell Kindred <dkindred+@CMU.EDU>
Subject: ppmdither bugs (w/ patch)

Jef,

While using Bill Perry's cool w3 package (emacs WWW browser), Jim
Stichnoth and I ran into a couple of problems with ppmdither.  (W3 has
an uncanny way of exposing bugs in other software, usually emacs.)

The first bug is that ppmdither ignores the maxval in its input, and
assumes it's 255.  This was easily fixed.  

The subtler bug is that a couple of off-by-one errors in ppmdither
cause it to introduce some regularly-spaced pixels of the wrong color.

You can see both of these bugs by doing
       ppmmake white 100 100 | pnmdepth 1 | ppmdither | ppmhist
The first bug is responsible for the fact that the result is mostly
black; the second is responsible for the 312 pixels of odd colors. 

The patch below (based on the 1mar1994 release) fixes both bugs.  Let
me know if you think I should post it to alt.graphics.pixutils.

[Bill: The first bug makes black-and-white gifs in w3 pretty much unviewable;
 see http://www.cs.cmu.edu:8001/Web/People/dkindred/whois-dkindred.html
 I'll send a workaround patch in a separate message.]

Thanks for netpbm--keep up the good work.

- Darrell

*** ppm/ppmdither.c.orig	Mon Oct  4 05:12:21 1993
--- ppm/ppmdither.c	Sat Oct  1 04:22:05 1994
***************
*** 31,37 ****
  static void dith_matrix ARGS((int dim));
  void dith_setup ARGS((int dim, int nr, int ng, int nb, pixel *ptab));
  int dith_color ARGS((float r, float g, float b));
! void dith_dither ARGS((int w, int h, register pixel *t, register pixel *i, register pixel *o));
  /* COLOR():
   *	returns the index in the color table for the
   *      r, g, b values specified.
--- 31,38 ----
  static void dith_matrix ARGS((int dim));
  void dith_setup ARGS((int dim, int nr, int ng, int nb, pixel *ptab));
  int dith_color ARGS((float r, float g, float b));
! void dith_dither ARGS((int w, int h, register pixel *t, register pixel *i, 
! 		       register pixel *o, pixval maxval));
  /* COLOR():
   *	returns the index in the color table for the
   *      r, g, b values specified.
***************
*** 50,56 ****
   *      s = the number of levels of the primary
   *
   */
! #define DITHER(p,d,s) ((ubyte) ((LEVELS(s) * (p) + (d)) / (dith_dm2 * NS)))
  
  
  /* dith_value():
--- 51,58 ----
   *      s = the number of levels of the primary
   *
   */
! #define DITHER(p,d,s) ((ubyte) ((LEVELS(s) * (p) + (d)) / \
! 				(dith_dm2 * (NS-1) + 1)))
  
  
  /* dith_value():
***************
*** 80,86 ****
  
  /* dith_matrix():
   *	Form the dithering matrix for the dimension specified
!  *	(Scaled by NS)
   */
  static void
  dith_matrix(dim)
--- 82,88 ----
  
  /* dith_matrix():
   *	Form the dithering matrix for the dimension specified
!  *	(Scaled by NS-1)
   */
  static void
  dith_matrix(dim)
***************
*** 103,109 ****
  
      for (y = 0; y < dith_dim; y++) {
  	for (x = 0; x < dith_dim; x++) {
! 	     dith_mat[y][x] = NS * dith_value(y, x, dim);
  #ifdef DEBUG
  	     (void) fprintf(stderr, "%4d ", dith_mat[y][x]);
  #endif
--- 105,111 ----
  
      for (y = 0; y < dith_dim; y++) {
  	for (x = 0; x < dith_dim; x++) {
! 	     dith_mat[y][x] = (NS-1) * dith_value(y, x, dim);
  #ifdef DEBUG
  	     (void) fprintf(stderr, "%4d ", dith_mat[y][x]);
  #endif
***************
*** 173,180 ****
   *  Dither height scanlines at a time
   */
  void
! dith_dither(w, h, t, i, o)
  int w, h;
  register pixel *t;
  register pixel *i;
  register pixel *o;
--- 175,183 ----
   *  Dither height scanlines at a time
   */
  void
! dith_dither(w, h, t, i, o, maxval)
  int w, h;
+ pixval maxval;
  register pixel *t;
  register pixel *i;
  register pixel *o;
***************
*** 186,194 ****
      for (y = 0; y < h; y++)
  	for (m = dith_mat[y & dm], x = w; --x >= 0;i++) {
  	    d = m[x & dm];
! 	    *o++ = t[COLOR(DITHER(PPM_GETR(*i), d, dith_nr), 
! 		           DITHER(PPM_GETG(*i), d, dith_ng), 
! 		           DITHER(PPM_GETB(*i), d, dith_nb))];
  	}
  } /* end dith_dither */
  
--- 189,197 ----
      for (y = 0; y < h; y++)
  	for (m = dith_mat[y & dm], x = w; --x >= 0;i++) {
  	    d = m[x & dm];
! 	    *o++ = t[COLOR(DITHER(PPM_GETR(*i) * 255 / maxval, d, dith_nr), 
! 		           DITHER(PPM_GETG(*i) * 255 / maxval, d, dith_ng), 
! 		           DITHER(PPM_GETB(*i) * 255 / maxval, d, dith_nb))];
  	}
  } /* end dith_dither */
  
***************
*** 253,261 ****
      ipixels = ppm_readppm( ifp, &cols, &rows, &maxval );
      pm_close( ifp );
      opixels = ppm_allocarray(cols, rows);
-     maxval = 255;
      dith_setup(dith_dim, dith_nr, dith_ng, dith_nb, ptab);
!     dith_dither(cols, rows, ptab, &ipixels[0][0], &opixels[0][0]);
      ppm_writeppm(stdout, opixels, cols, rows, maxval, 0);
      pm_close(stdout);
      exit(0);
--- 256,264 ----
      ipixels = ppm_readppm( ifp, &cols, &rows, &maxval );
      pm_close( ifp );
      opixels = ppm_allocarray(cols, rows);
      dith_setup(dith_dim, dith_nr, dith_ng, dith_nb, ptab);
!     dith_dither(cols, rows, ptab, &ipixels[0][0], &opixels[0][0], maxval);
!     maxval = 255;
      ppm_writeppm(stdout, opixels, cols, rows, maxval, 0);
      pm_close(stdout);
      exit(0);