/******************************************************************************

  File:     $Id: eprnfs.c,v 1.6 2001/05/01 07:02:01 Martin Rel $

  Contents: Floyd-Steinberg error diffusion for eprn

  Author:   Martin Lottermoser, Greifswaldstrasse 28, 38124 Braunschweig,

            Germany; e-mail: Martin.Lottermoser@t-online.de.

*******************************************************************************

*                       *

* Copyright (C) 2001 by Martin Lottermoser            *

* All rights reserved                 *

*                       *

*******************************************************************************

  Information about Floyd-Steinberg error diffusion should be available in a

  number of places. I've used:

    James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes

    "Computer Graphics"

    Second edition in C

    Reading/Massachusetts, etc.: Addison-Wesley, 1996

    ISBN 0-201-84840-6

******************************************************************************/

/*****************************************************************************/

#ifndef _XOPEN_SOURCE

#define _XOPEN_SOURCE 500

#endif

#include "gdeveprn.h"

/*****************************************************************************/

/* Here follow some macros for code sections used in several routines. */

#define fit_to_octet(value) ((value) < 0? 0: (value) > 255? 255: (value))

#define FS_assign()       \

        new_value = *to + correction;   \

        if (new_value < 0) {     \

          *to = 0;        \

          remaining_error += new_value;   \

        }          \

        else if (255 < new_value) {   \

          *to = 255;        \

          remaining_error += new_value - 255; \

        }          \

        else *to = new_value;

#define error_propagation_Gray()        \

  if (error != 0) {           \

    remaining_error = error;          \

                                                                \

    /* 7/16 of the error goes to the right */     \

    correction = (7*error)/16;          \

    remaining_error -= correction;        \

    if (pixel < max_pixel) {         \

      to = from + 1;            \

      FS_assign()            \

      if (pixel == pixels - 1 && *to > 0) {     \

        pixels++;           \

        line->length++;           \

      }                \

    }               \

                                                                \

    /* 3/16 of the error goes to the left and below */    \

    correction = (3*error)/16;          \

    remaining_error -= correction;        \

    if (pixel > 0) {           \

      to = next_line->str + (pixel - 1);      \

      FS_assign()            \

      if (next_line->length < pixel && *to > 0) next_line->length = pixel; \

    }               \

                                                                \

    /* 5/16 of the error goes below */        \

    correction = (5*error)/16;          \

    remaining_error -= correction;        \

    to = next_line->str + pixel;        \

    FS_assign()              \

    if (next_line->length <= pixel && *to > 0) next_line->length = pixel + 1; \

                                                                \

    /* The remainder (about 1/16 of the error) is added to the right and */ \

    /* below. */            \

    if (pixel < max_pixel) {         \

      to = next_line->str + (pixel+1);        \

      new_value = *to + remaining_error;      \

      *to = fit_to_octet(new_value);        \

      if (next_line->length < pixel + 2 && *to > 0)   \

        next_line->length = pixel + 2;       \

    }               \

  }

/* Number of octets per pixel for the non-monochrome cases */

#define OCTETS_PER_PIXEL  4

#define error_propagation_colour()        \

  if (error != 0) {           \

    remaining_error = error;          \

                                                                \

    /* 7/16 of the error goes to the right */     \

    correction = (7*error)/16;          \

    remaining_error -= correction;        \

    if (pixel < max_pixel) {         \

      to = from + OCTETS_PER_PIXEL;       \

      FS_assign()            \

      if (pixel == pixels - 1 && *to > 0) {     \

        pixels++;           \

        line->length += OCTETS_PER_PIXEL;     \

      }               \

    }               \

                                                                \

    /* 3/16 of the error goes to the left and below */    \

    correction = (3*error)/16;          \

    remaining_error -= correction;        \

    if (pixel > 0) {           \

      to = next_line->str + (pixel - 1)*OCTETS_PER_PIXEL + colorant; \

      FS_assign()            \

      if (next_line->length < pixel*OCTETS_PER_PIXEL && *to > 0) \

        next_line->length = pixel*OCTETS_PER_PIXEL;   \

    }               \

                                                                \

    /* 5/16 of the error goes below */        \

    correction = (5*error)/16;          \

    remaining_error -= correction;        \

    to = next_line->str + pixel*OCTETS_PER_PIXEL + colorant;  \

    FS_assign()              \

    if (next_line->length <= pixel*OCTETS_PER_PIXEL && *to > 0) \

      next_line->length = (pixel + 1)*OCTETS_PER_PIXEL;   \

                                                                \

    /* The remainder (about 1/16 of the error) is added to the right and */ \

    /* below. */            \

    if (pixel < max_pixel) {         \

      to = next_line->str + (pixel+1)*OCTETS_PER_PIXEL + colorant; \

      new_value = *to + remaining_error;      \

      *to = fit_to_octet(new_value);        \

      if (next_line->length < (pixel + 2)*OCTETS_PER_PIXEL && *to > 0) \

        next_line->length = (pixel + 2)*OCTETS_PER_PIXEL; \

    }               \

  }

/******************************************************************************

  Function: split_Gray_2

  Floyd-Steinberg error diffusion for the process colour model Gray and

  2 intensity levels.

******************************************************************************/

static void split_Gray_2(eprn_OctetString *line, eprn_OctetString *next_line,

  int max_octets, eprn_OctetString bitplanes[])

{

  const int

    max_pixel = max_octets - 1;

  int

    correction,

    error,

    new_value,

    pixel,

    pixel_mod_8,

    pixels = line->length,

    remaining_error;

  eprn_Octet

    approx,

    *from,

    *ptr,

    *to;

  ptr = bitplanes[0].str;

  /* Loop over pixels in the scan line. Note that 'pixels' may increase

     within the loop. */

  for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {

    if (pixel_mod_8 == 8) {

      pixel_mod_8 = 0;

      *ptr = 0;

    }

    /* Determine approximation and error for this pixel */

    from = line->str + pixel;

    approx = *from >> 7;  /* take the most significant bit */

    error = *from - 255*approx;

     /* The sign of 'error' is chosen such that 'error' is positive if

        colorant intensity has to be added to the picture. */

    /* Insert the approximation into the output plane */

    *ptr = (*ptr << 1) | approx;

    error_propagation_Gray()

    if (pixel_mod_8 == 7) ptr++;

  }

  eprn_finalize(false, 0, 1, bitplanes, &ptr, pixels);

  return;

}

/******************************************************************************

  Function: split_Gray()

  Floyd-Steinberg error diffusion for the process colour model Gray and an

  arbitrary number of intensity levels.

******************************************************************************/

static void split_Gray(eprn_OctetString *line, eprn_OctetString *next_line,

  int max_octets, unsigned int black_levels, eprn_OctetString bitplanes[])

{

  const int

    max_pixel = max_octets - 1,

    planes = eprn_bits_for_levels(black_levels);

  int

    correction,

    error,

    new_value,

    pixel,

    pixel_mod_8,

    pixels = line->length,

    plane,

    remaining_error;

  eprn_Octet

    approx,

    *from,

    *ptr[8],

    *to;

  const unsigned int

    divisor = 256/black_levels,

    max_level = black_levels - 1;

  for (plane = 0; plane < planes; plane++) ptr[plane] = bitplanes[plane].str;

  /* Loop over pixels in the scan line. Note that 'pixels' may increase

     within the loop. */

  for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {

    if (pixel_mod_8 == 8) {

      pixel_mod_8 = 0;

      for (plane = 0; plane < planes; plane++) *ptr[plane] = 0;

    }

    /* Determine approximation and error for this pixel */

    from = line->str + pixel;

    approx = *from/divisor;

    error = *from - (255*approx)/max_level;

     /* The sign of 'error' is chosen such that 'error' is positive if

        colorant intensity has to be added to the picture. */

    /* Distribute the approximation over the bit planes */

    for (plane = 0; plane < planes; plane++) {

      *ptr[plane] = (*ptr[plane] << 1) | (approx & 0x01);

      approx >>= 1;

    }

    error_propagation_Gray()

    if (pixel_mod_8 == 7)

      for (plane = 0; plane < planes; plane++) ptr[plane]++;

  }

  eprn_finalize(false, 0, planes, bitplanes, ptr, pixels);

  return;

}

/*****************************************************************************/

/* Index of the black colorant in a pixel value (gx_color_index) for the

   non-monochrome cases */

#define BLACK_INDEX   3

/******************************************************************************

  Function: split_colour_CMYK_2()

  Floyd-Steinberg error diffusion for the CMYK colour model using 2 intensity

  levels for all colorants.

  This function is about 14 % faster than split_colour_at_most_2(), and every

  bit helps.

******************************************************************************/

#define PLANES    4

static void split_colour_CMYK_2(eprn_OctetString *line,

  eprn_OctetString *next_line, int max_octets, eprn_OctetString bitplanes[])

{

  const int

    max_pixel = max_octets/OCTETS_PER_PIXEL - 1;

  int

    colorant,

    correction,

    error,

    new_value,

    pixel,

    pixel_mod_8,

    pixels = line->length/OCTETS_PER_PIXEL,

    plane,

    remaining_error;

  eprn_Octet

    approx,

    *from,

    *ptr[4],

    *to;

  for (plane = 0; plane < PLANES; plane++) ptr[plane] = bitplanes[plane].str;

  /* Loop over pixels in the scan line. Note that 'pixels' may increase

     within the loop. */

  for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {

    if (pixel_mod_8 == 8) {

      pixel_mod_8 = 0;

      for (plane = 0; plane < PLANES; plane++) *ptr[plane] = 0;

    }

    /* Loop over colorants within a scan line. Remember that the order within

       a pixel is YMCK. */

    for (colorant = BLACK_INDEX; colorant >= 0; colorant--) {

      from = line->str + pixel*OCTETS_PER_PIXEL + colorant;

      /* Determine approximation and error for this pixel */

      approx = *from >> 7;

      error = *from - 255*approx;

       /* The sign of 'error' is chosen such that 'error' is positive if

          colorant intensity has to be added to the picture. */

      /* Insert the approximation in the bit plane */

      plane = BLACK_INDEX - colorant;

      *ptr[plane] = (*ptr[plane] << 1) | approx;

      error_propagation_colour()

    }

    if (pixel_mod_8 == 7)

      for (plane = 0; plane < PLANES; plane++) ptr[plane]++;

  }

  eprn_finalize(false, 2, PLANES, bitplanes, ptr, pixels);

  return;

}

/******************************************************************************

  Function: split_colour_at_most_2()

  Floyd-Steinberg error diffusion for the non-monochrome process colour models

  using 2 intensity levels for the CMY colorants and at most 2 for the black

  colorant.

******************************************************************************/

static void split_colour_at_most_2(eprn_OctetString *line,

  eprn_OctetString *next_line, int max_octets, eprn_ColourModel colour_model,

  eprn_OctetString bitplanes[])

{

  const int

    last_colorant =

      colour_model == eprn_DeviceCMY_plus_K || colour_model == eprn_DeviceCMYK?

        BLACK_INDEX: 2,

    max_pixel = max_octets/OCTETS_PER_PIXEL - 1,

    planes =

      colour_model == eprn_DeviceCMY_plus_K || colour_model == eprn_DeviceCMYK?

        4: 3;

  int

    colorant,

    correction,

    error,

    new_value,

    pixel,

    pixel_mod_8,

    pixels = line->length/OCTETS_PER_PIXEL,

    plane,

    remaining_error;

  eprn_Octet

    approx[4],

    *from,

    *ptr[4],

    *to;

  for (plane = 0; plane < planes; plane++) ptr[plane] = bitplanes[plane].str;

  /* Loop over pixels in the scan line. Note that 'pixels' may increase

     within the loop. */

  for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {

    if (pixel_mod_8 == 8) {

      pixel_mod_8 = 0;

      for (plane = 0; plane < planes; plane++) *ptr[plane] = 0;

    }

    /* Loop over colorants within a scan line. Remember that the order within

       a pixel is YMCK or BGR-. */

    for (colorant = last_colorant; colorant >= 0; colorant--) {

      from = line->str + pixel*OCTETS_PER_PIXEL + colorant;

      /* Determine approximation and error for this pixel */

      approx[colorant] = *from >> 7;

      error = *from - 255*approx[colorant];

       /* The sign of 'error' is chosen such that 'error' is positive if

          colorant intensity has to be added to the picture. */

      error_propagation_colour()

    }

    /* Determine the black component for CMY+K */

    if (colour_model == eprn_DeviceCMY_plus_K &&

        approx[0] == approx[1] && approx[1] == approx[2] && approx[0] > 0) {

      approx[BLACK_INDEX] = approx[0];

      approx[0] = approx[1] = approx[2] = 0;

    }

    /* Distribute the approximation over the bit planes */

    for (colorant = last_colorant, plane = 0; colorant >= 0;

        colorant--, plane++) {

      *ptr[plane] = (*ptr[plane] << 1) | approx[colorant];

    }

    if (pixel_mod_8 == 7)

      for (plane = 0; plane < planes; plane++) ptr[plane]++;

  }

  eprn_finalize(colour_model == eprn_DeviceRGB, 2, planes, bitplanes, ptr,

    pixels);

  return;

}

/******************************************************************************

  Function: split_colour()

  Floyd-Steinberg error diffusion for the non-monochrome process colour models

  and an arbitrary number of intensity levels.

******************************************************************************/

static void split_colour(eprn_OctetString *line, eprn_OctetString *next_line,

  int max_octets, eprn_ColourModel colour_model,

  unsigned int black_levels, unsigned int non_black_levels,

  eprn_OctetString bitplanes[])

{

  const int

    black_planes = eprn_bits_for_levels(black_levels),

    last_colorant = black_levels > 0? BLACK_INDEX: 2,

    max_pixel = max_octets/OCTETS_PER_PIXEL - 1,

    non_black_planes = eprn_bits_for_levels(non_black_levels),

    planes = black_planes + 3*non_black_planes;

  int

    colorant,

    correction,

    error,

    new_value,

    next_plane[4],

    pixel,

    pixel_mod_8,

    pixels = line->length/OCTETS_PER_PIXEL,

    plane,

    remaining_error;

  eprn_Octet

    approx[4],

    *from,

    *ptr[32],

    *to;

  unsigned int

    divisor[4],

    max_level[4];

  if (black_levels > 0) {

    divisor[BLACK_INDEX] = 256/black_levels;

    max_level[BLACK_INDEX] = black_levels - 1;

  }

  else {

    divisor[BLACK_INDEX] = 0;

    max_level[BLACK_INDEX] = 0;

  }

  next_plane[BLACK_INDEX] = black_planes;

  for (colorant = 0; colorant < BLACK_INDEX; colorant++) {

    divisor[colorant] = 256/non_black_levels;

    max_level[colorant] = non_black_levels - 1;

    next_plane[colorant] = (3 - colorant)*non_black_planes + black_planes;

  }

  for (plane = 0; plane < planes; plane++) ptr[plane] = bitplanes[plane].str;

  /* Loop over pixels in the scan line. Note that 'pixels' may increase

     within the loop. */

  for (pixel = 0, pixel_mod_8 = 8; pixel < pixels; pixel++, pixel_mod_8++) {

    if (pixel_mod_8 == 8) {

      pixel_mod_8 = 0;

      for (plane = 0; plane < planes; plane++) *ptr[plane] = 0;

    }

    /* Loop over colorants within a scan line */

    for (colorant = last_colorant; colorant >= 0; colorant--) {

      from = line->str + pixel*OCTETS_PER_PIXEL + colorant;

      /* Determine approximation and error for this pixel */

      approx[colorant] = *from/divisor[colorant];

      error = *from - (255*approx[colorant])/max_level[colorant];

       /* The sign of 'error' is chosen such that 'error' is positive if

          colorant intensity has to be added to the picture. */

      error_propagation_colour()

    }

    /* Determine the black component for CMY+K */

    if (colour_model == eprn_DeviceCMY_plus_K &&

        approx[0] == approx[1] && approx[1] == approx[2] && approx[0] > 0) {

      int value = approx[0]*(black_levels - 1);

      if (value % (non_black_levels - 1) == 0) {

        /* Black does have a level at the same intensity as the CMY levels */

        approx[BLACK_INDEX] = value/(non_black_levels - 1);

        approx[0] = approx[1] = approx[2] = 0;

      }

    }

    /* Distribute the approximation over the bit planes */

    plane = 0;

    for (colorant = last_colorant; colorant >= 0; colorant--) {

      while (plane < next_plane[colorant]) {

        *ptr[plane] = (*ptr[plane] << 1) | (approx[colorant] & 0x01);

        approx[colorant] >>= 1;

        plane++;

      }

    }

    if (pixel_mod_8 == 7) {

      int j;

      for (j = 0; j < planes; j++) ptr[j]++;

    }

  }

  eprn_finalize(colour_model == eprn_DeviceRGB, non_black_levels, planes,

    bitplanes, ptr, pixels);

  return;

}

/******************************************************************************

  Function: eprn_split_FS

  This function performs Floyd-Steinberg error diffusion on a scan line

  and returns the result as bitplanes.

  'line' points to the scan line to be split, 'next_line' to the following one.

  Both lines will be modified by this process. This modification assumes that

  the function is called successively for all lines, starting with the first.

  All octets up to 'max_octets' must be available in the input lines and, as

  far as they have not been included in the length fields, must be zero.

  The parameter 'colour_model' specifies the process colour model used.

  'black_levels' is the number of intensity levels for the black colorant,

  'non_black_levels' the corresponding number for the other colorants.

  'bitplanes' is an array of bitplanes into which the result will be stored

  in the usual format.

******************************************************************************/

void eprn_split_FS(eprn_OctetString *line, eprn_OctetString *next_line,

  int max_octets, eprn_ColourModel colour_model,

  unsigned int black_levels, unsigned int non_black_levels,

  eprn_OctetString bitplanes[])

{

  if (colour_model == eprn_DeviceGray) {

    if (black_levels == 2)

      split_Gray_2(line, next_line, max_octets, bitplanes);

    else

      split_Gray(line, next_line, max_octets, black_levels, bitplanes);

  }

  else if (colour_model == eprn_DeviceCMYK &&

      black_levels == 2 && non_black_levels == 2)

    split_colour_CMYK_2(line, next_line, max_octets, bitplanes);

  else {

    if (black_levels <= 2 && non_black_levels == 2)

      split_colour_at_most_2(line, next_line, max_octets, colour_model,

        bitplanes);

    else

      split_colour(line, next_line, max_octets, colour_model, black_levels,

        non_black_levels, bitplanes);

  }

  return;

}