#ifndef lint
static char SccsDitherId[] = "%W%  %G%";
#endif

/* Module:	Dither.def
 * Purpose:	Declare and initialize dither weight matrices and
 *		random error vals (includes sample of code to generate it)
 * Modified:	{0} Michael VanHilst	initial version	    31 December 1987
 *		{n} <who> -- <does what> -- <when>
 */

/* FATTING DITHER PATTERN WEIGHT MATRIX - AS USED BY UTAH RLE LIBRARY */
short dotmatrix1 [16][16] = {
  {  0,222, 48,206, 14,236, 62,220,  3,225, 51,209, 13,235, 61,219},
  {175, 79,127, 95,189, 93,141,109,178, 82,130, 98,188, 92,140,108},
  {191, 32,238, 16,204, 46,252, 30,193, 35,241, 19,203, 45,251, 29},
  {111,143, 64,159,125,157, 77,173,114,146, 66,162,124,156, 76,172},
  { 11,233, 59,217,  5,227, 53,211,  8,230, 56,214,  6,228, 54,212},
  {186, 90,138,106,180, 84,132,100,183, 87,135,103,181, 85,133,101},
  {201, 43,249, 27,195, 37,243, 21,198, 40,246, 24,196, 38,244, 22},
  {122,154, 74,170,116,148, 68,164,119,151, 71,167,117,149, 69,165},
  { 12,234, 60,218,  2,224, 50,208, 15,237, 63,221,  1,223, 49,207},
  {187, 91,139,107,177, 81,129, 97,190, 94,142,110,176, 80,128, 96},
  {202, 44,250, 28,192, 34,240, 18,205, 47,253, 31,191, 33,239, 17},
  {123,155, 75,171,113,145, 65,161,126,158, 78,174,112,144, 64,160},
  {  7,229, 55,213,  9,231, 57,215,  4,226, 52,210, 10,232, 58,216},
  {182, 86,134,102,184, 88,136,104,179, 83,131, 99,185, 89,137,105},
  {197, 39,245, 23,199, 41,247, 25,194, 36,242, 20,200, 42,248, 26},
  {118,150, 70,166,120,152, 72,168,115,147, 67,163,121,153, 73,169}};

/* MINIMUM CLUMPING WEIGHT MATRIX - BASED ON MAXIMUM GEOMETRIC SYMMETRY */
short dotmatrix2 [16][16] = {
  {  0,192, 48,240, 12,204, 60,252,  3,195, 51,243, 15,207, 63,254},
  {128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127},
  { 32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223},
  {160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95},
  {  8,200, 56,248,  4,196, 52,244, 11,203, 59,251,  7,199, 55,247},
  {136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119},
  { 40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215},
  {168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87},
  {  2,194, 50,242, 14,206, 62,254,  1,193, 49,241, 13,205, 61,253},
  {130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125},
  { 34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221},
  {162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93},
  { 10,202, 58,250,  6,198, 54,246,  9,201, 57,249,  5,197, 53,245},
  {138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117},
  { 42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213},
  {170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85}};

#define ERRBUFSZ 1202	/* longest bitmap line plus 2 */
/* RANDOM VALUES TO INITIALIZE THE ERROR DIFFUSION BUFFER */
short errbuf [ERRBUFSZ] = {
  247, 17,122,232, 90,238,167,  5,131, 51,240, 52, 96,203, 73, 68, 91, 32,
  180,188,205,234,130,195,116,120, 76,156, 18,127, 56, 10,144,178,243,234,
  161,154,240, 36,206,224, 88, 47,171,162,116,  7,195, 40,195,144, 18, 70,
   83,135,191,160, 36,210, 32, 92,220,176, 14,208,155,176,107,139,212, 57,
  108, 45,105, 23,208,221, 30,147,  5,226, 36, 24, 41,120,159,232, 24,195,
  187, 57, 31,151,233, 46,103,133,223,211, 16,179, 13,124,225,118,148,177,
   84,179, 69, 90,150,105,114,191,225, 17,168,250,213, 99, 51,244,251, 29,
   35, 99,162,  2, 54,179,182, 67, 48,152,186,196, 73, 14,120,142,104, 14,
  248,218,206,217,236,119,212,193,219,  8,182,214, 37,218, 58,200,220,112,
  123,147,180,171, 43,110,112,117,125,233,  4,229,248,252,192,198,214,172,
   62,171,110, 25,179, 36,240,217,254, 42,161,219,155, 29,111, 80,201,155,
  190, 57, 16, 59, 35, 21, 33, 27, 17,225,226,232,142, 32,147,252, 58, 70,
   32, 42, 31, 31, 85,193,251,241,222,106, 65,167,  5,  0,225, 22, 60,  4,
   43, 94, 31, 61, 63,  1, 37,206, 34,184,202, 92,255,235,135, 31, 11,221,
  224,  6,206,191,113, 16,102,118, 17, 71,141, 78, 75,184,172,107,246,236,
  109, 27,186,143,212,133,235,211,112,115,243,123, 80,211,130, 31,146,243,
   48,249,105, 65, 64,247,143,140,176, 59,248,166, 40,101,193,226,244,150,
  103,224,105,216, 83, 93, 84,164, 48,214,196,195,201,244,188, 51, 53,253,
   42,197,138,218,  1,130,129, 41,231, 66, 12,220,217,116,189, 67, 76, 17,
  160,160,181,208,118,122,148, 63,110, 80,114,164, 78,157,105,216,119,107,
   90,248,149, 66, 59,161, 31, 20, 21,220, 87, 98,238,247,  2,164,200,121,
   30, 92,185,140,173, 43, 48,251,201,154,212, 64,  6, 46, 57,155,113,117,
   60,145,138, 82,110,226,180, 92,218,183,  0,163, 48, 30,255,233,171,173,
   21,220,168,222,118,124, 31,125,171, 89, 24, 29,207, 85,174, 89,167, 28,
   60, 91,121, 22, 19,121,185, 67,152,185, 45, 67,102, 67, 31, 15, 33,150,
  140, 65, 19, 56,155, 43, 86,106,128,  5,196, 40, 33,  1,132,155, 23,151,
   20,209,219,172,139,  8,240,242, 75, 15,  2,109,165,143,174,184,199, 74,
  228, 30,181,101, 35,121,141, 69,123, 17,224,147,169,245,100,132,161,240,
  140,146,226,215,161,229, 69, 70,116,244,255, 60, 62,227, 90,243, 72,125,
  109,214,195,232,231,163,123,144,152,224, 21, 58,209,161,204,180,121,109,
  153,190,180, 14,178,180, 74,240,151,165,228,224, 35, 82,182,230, 58,158,
  137,182, 47, 34,151, 68, 93,105,230, 41, 29, 95,151,183, 29, 76,197,207,
    0, 15,192,152,180,165,120,215,247, 47,189, 50,206, 71,232,253,106,128,
   66,199,234, 40,240,  7,135,136,190,165,212,132,117,213,147, 53,109, 72,
  218,230, 32,210, 22,222,  4,228, 37,237,226,143,109, 37, 87, 87, 77, 71,
   95,213,208, 30,123,165,162,240,122, 54, 38,232,127,  1,207,159,211,229,
  125,215,201,163,196,172, 51, 50,209,138,138, 30,210,234,244,162,  8,112,
   71,171, 96,194,226,135,170, 97,136,122,  0, 92, 95,126, 52, 40, 33,248,
  213, 84, 43,166,223,182,197,177,160,186, 83,169, 42,155, 84,138, 93, 55,
   17,  8,152,154,130,153,247,226, 23, 43, 11, 57, 36,224,142, 79,134,109,
    5, 75, 30,166,  6,114, 79, 48, 13,164,186,107,219,204,116,115,103,247,
   12, 94,217, 36,137,228, 94,174,197,236,253, 75, 90,  3,151,120,169,157,
  235,249,205,249,157,136,100,120, 85,217,235,188,209,248, 27,170, 29,165,
  143,123, 83, 84,104, 81,160,194, 85, 55, 59,255,213, 38,248,163, 31,149,
   43,132, 13,128, 94,249, 61, 47,242, 89,218, 16,254,106,139, 82,191,244,
  164, 95,182,249,151,242,249,108, 24,242, 16, 56,135, 59,189,149,188, 27,
  143,250, 75,130, 83, 38,146, 82,144, 30,165, 80, 18, 73,175,201, 67, 71,
  187, 61,180,211, 47,196, 12,183,255,201, 76,188,229,220,183, 49, 94, 11,
   87,240, 93,232, 14,  3, 56, 33, 77,232,234,145, 47,165,206,228,120,253,
  168,133,180,168, 79,  1,100, 52,222, 28,102, 60, 39,190, 45,132,166, 59,
  136,223, 92,213,200, 70,102,248,235, 52,220,100, 50,132,233,231, 44, 56,
  233,145,109,199,173,212,  3,212,146, 48, 89, 57,108,225, 24,201,183,225,
   16, 29,217,252, 82,181, 96,132, 57, 74,108,102,131, 85,248,241, 28,165,
  197, 32,122, 88, 81,211,145,190,181,170,135,108,139,152,137,100,148,220,
   26,245, 96, 84, 64,204,186,196, 33,178,181, 62, 88,123, 94,210,211,176,
  165,101,110, 91, 15,246,199,154,142, 81,255, 35, 45, 25, 25,142,109, 89,
   90, 40, 29,124,219,211,187, 51, 79, 26,  5, 35,202,171,136, 57,  6,151,
   48,206, 50,190, 32, 49,226, 78, 75,251,220,185, 85, 55,226,115,180,189,
   70,111,240,150,137,245,186, 84,161, 66,142,168,218,190,119, 12,125,151,
   62, 95,229,138, 91,194, 68,176,249, 38, 35,173,227,106, 29,211,  0,167,
  201,186,251,107,253,137, 19,215, 72,139,228,197, 34, 35, 36,  8,174,127,
  202,242, 47,196, 24, 83,113,251,189,142,206,189, 54,152,120, 49,  3,118,
  187, 23, 78,  3,162, 50,201,197, 86,237,205,  4,109,152,246,157, 92, 14,
  240,206,  9,173, 92,216,107,147,113,228,196,116, 90,128,139,168,132, 46,
  219, 77,243, 49, 59,192, 54,169, 88, 44, 71,181, 59, 55,131, 68,229,224,
   29, 81,115,142, 54, 56,  3,144,185,143, 57, 61,189, 21,139,176, 71,199,
  113,125,113,202,170,184,127,229,240,  2, 42,213,227, 71};


#ifdef EXCESS

/* ALGORYTHM USED TO GENERATE RLE DITHER PATTERN */
int magic4x4[4][4] =  {
 	 0, 14,  3, 13,
	11,  5,  8,  6,
	12,  2, 15,  1,
	 7,  9,  4, 10
};
/*****************************************************************
 * TAG( make_square )
 * 
 * Build the magic square for a given number of levels.
 * Inputs:
 * 	N:		Pixel values per level (255.0 / levels).
 * Outputs:
 * 	divN:		Integer value of pixval / N
 *	modN:		Integer remainder between pixval and divN[pixval]*N
 *	magic:		Magic square for dithering to N sublevels.
 * Assumptions:
 * 	
 * Algorithm:
 *	divN[pixval] = (int)(pixval / N) maps pixval to its appropriate level.
 *	modN[pixval] = pixval - (int)(N * divN[pixval]) maps pixval to
 *	its sublevel, and is used in the dithering computation.
 *	The magic square is computed as the (modified) outer product of
 *	a 4x4 magic square with itself.
 *	magic[4*k + i][4*l + j] = (magic4x4[i][j] + magic4x4[k][l]/16.0)
 *	multiplied by an appropriate factor to get the correct dithering
 *	range.
 */
make_square( N, divN, modN, magic )
double N;
int divN[256];
int modN[256];
int magic[16][16] ;
{
    register int i, j, k, l;
    double magicfact;

    for ( i = 0; i < 256; i++ )
    {
	divN[i] = (int)(i / N);
	modN[i] = i - (int)(N * divN[i]);
    }

    /*
     * Expand 4x4 dither pattern to 16x16.  4x4 leaves obvious patterning,
     * and doesn't give us full intensity range (only 17 sublevels,
     * we want at least 51).  Note that 8x8 would be sufficient, but
     * 16x16 is easier to build.
     * 
     * magicfact is (N - 2)/16 so that we get numbers in the matrix from 0 to
     * N - 2: mod N gives numbers in 0 to N - 1, we want some chance that the
     * number is greater than a matrix entry, so the highest matrix
     * entry must be N - 2.
     */
    magicfact = (N - 2) / 16.;
    for ( i = 0; i < 4; i++ )
	for ( j = 0; j < 4; j++ )
	    for ( k = 0; k < 4; k++ )
		for ( l = 0; l < 4; l++ )
		    magic[4*k+i][4*l+j] =
			(int)(0.5 + magic4x4[i][j] * magicfact +
			      (magic4x4[k][l] / 16.) * magicfact);
}


/* ALGORITHM FOR 2ND DITHER WEIGHT MATRIX */
/* SATISFIES CONDITION OF MINIMUM CLUMPING AT ALL LEVELS ...
 ... BY MAXIMIZING UNIFORMITY OF PATTERN DISTRIBUTION (PATTERN REGULARITY) */
static int ix[4] = {0,1,0,1}, iy[4] = {0,1,1,0};
makematrix ( matrix )
     short matrix[16][16];
{
  int i,j,k,l;
  int ax,bx,cx,dx;
  int ay,by,cy,dy;
  int indx, indy;
  short val;

  val = 0;
  /* ASSIGNMENT PATTERN NESTS CORNERS OF SUCCESSIVELY LARGER SQUARES */
  /* 2x2 SQUARE */
  for (i = 0; i < 4; i++) {
    ax = ix[i];
    ay = iy[i];
    /* SAME PATTERN 4x4 SQUARE */
    for (j = 0; j < 4; j++) {
      bx = ix[j] * 2;
      by = iy[j] * 2;
      /* SAME PATTERN 8x8 SQUARE */
      for (k = 0; k < 4; k++) {
	cx = ix[k] * 4;
	cy = iy[k] * 4;
	/* SAME PATTERN 16x16 SQUARE */
	for (l = 0; l < 4; l++) {
	  dx = ix[l] * 8;
	  dy = iy[l] * 8;
	  indx = ax + bx + cx + dx;
	  indy = ay + by + cy + dy;
	  matrix[indx][indy] = val++;
	}
      }
    }
  }
  /* TOP VAL (255) CAN'T BE EXCEEDED BY DATA SO REDUCE IT BY ONE */
  --matrix[indx][indy];
  return;
}

/* DITHER WEIGHT MATRIX - CONTIGUOUS FROM UPPER LEFT CORNER */
/* SATISFIES CONDITION OF MAXIMUM CLUMPING, HAS ONLY 64 LEVELS */
/* SUITED FOR PRINTERS WHERE BLACK DOTS ARE BIGGER THAN WHITE DOTS */
/*
short dotmatrix3 [16][16] = {
  {  0,  8, 20, 36, 56, 80,108,140,  0,  8, 20, 36, 56, 80,108,140},
  {  4, 16, 32, 52, 76,104,136,168,  4, 16, 32, 52, 76,104,136,168},
  { 12, 28, 48, 72,100,132,164,192, 12, 28, 48, 72,100,132,164,192},
  { 24, 44, 68, 96,128,160,188,212, 24, 44, 68, 96,128,160,188,212},
  { 40, 64, 92,124,156,184,208,228, 40, 64, 92,124,156,184,208,228},
  { 60, 88,120,152,180,204,224,240, 60, 88,120,152,180,204,224,240},
  { 84,116,148,176,200,220,236,248, 84,116,148,176,200,220,236,248},
  {112,144,172,196,216,232,244,252,112,144,172,196,216,232,244,252},
  {  0,  8, 20, 36, 56, 80,108,140,  0,  8, 20, 36, 56, 80,108,140},
  {  4, 16, 32, 52, 76,104,136,168,  4, 16, 32, 52, 76,104,136,168},
  { 12, 28, 48, 72,100,132,164,192, 12, 28, 48, 72,100,132,164,192},
  { 24, 44, 68, 96,128,160,188,212, 24, 44, 68, 96,128,160,188,212},
  { 40, 64, 92,124,156,184,208,228, 40, 64, 92,124,156,184,208,228},
  { 60, 88,120,152,180,204,224,240, 60, 88,120,152,180,204,224,240},
  { 84,116,148,176,200,220,236,248, 84,116,148,176,200,220,236,248},
  {112,144,172,196,216,232,244,252,112,144,172,196,216,232,244,252}};
*/

/* program to print out a dither matrix for use in array initialization */
main()
  int argc;
  char **argv;
{
  short matrix[16][16];
  int i, j;

  makematrix(matrix);
  for( i=0; i<16; i++ ) {
    (void)printf("  {");
    for( j=0; j<15; j++ ) {
      (void)printf("%3d,",matrix[j][i]);
    }
    if( i<15 )
      (void)printf("%3d},\n",matrix[15][i]);
    else
      (void)printf("%3d}};\n",matrix[15][i]);
  }
}

/* program to print out random values for error diffusion buffer */
main()
{
  int iscale = 256;
  int errbufsize = 1202;
  int iseed = 5121953;
  float ran_();
  int i, j;

  j = 0;
  /* RANDOMLY INITIALIZE ERRORS TO SUPRESS ANY PATTERNS */
  (void)printf("\n  ");
  for (i = 0; i < errbufsize; i++) {
    (void)printf("%3d,",(int)((float)iscale * ran_(&iseed)));
    if( ++j > 17 ) {
      (void)printf("\n  ");
      j = 0;
    }
  }
  (void)printf("\n");
}

static int rflag=0;

float ran_(seed)
int *seed;
{
  float r;
  if(rflag==0) {
    srandom(1);
    rflag = 1;
  }
  r = (float)random();
  return(r/(float)0x7fffffff);
}

#endif
