/* Copyright (C) 1995, 1996, 1997, 1999, 2000 artofcode LLC.  All rights reserved.
  
  This program is free software; you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the
  Free Software Foundation; either version 2 of the License, or (at your
  option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License along
  with this program; if not, write to the Free Software Foundation, Inc.,
  59 Temple Place, Suite 330, Boston, MA, 02111-1307.

*/

/*$Id: gxdht.h,v 1.4.6.1.2.1 2003/01/17 00:49:03 giles Exp $ */
/* Definition of device halftones */

#ifndef gxdht_INCLUDED
#  define gxdht_INCLUDED

#include "gsrefct.h"
#include "gscsepnm.h"
#include "gsmatrix.h"
#include "gxarith.h"		/* for igcd */
#include "gxhttype.h"

/*
 * We represent a halftone tile as a rectangular super-cell consisting of
 * multiple copies of a multi-cell whose corners lie on integral
 * coordinates, which in turn is a parallelogram (normally square) array of
 * basic parallelogram (normally square) cells whose corners lie on rational
 * coordinates.
 *
 * Let T be the aspect ratio (ratio of physical pixel height to physical
 * pixel width), which is abs(xx/yy) for portrait devices and abs(yx/xy) for
 * landscape devices.  We characterize the basic cell by four rational
 * numbers U(') = M(')/R(') and V(') = N(')/R(') where R(') is positive, at
 * least one of U and V (and the corresponding one of U' and V') is
 * non-zero, and U' is approximately U/T and V' is approximately V*T; these
 * numbers define the vertices of the basic cell at device space coordinates
 * (0,0), (U,V), (U-V',U'+V), and (-V',U'); then the multi-cell is defined
 * similarly by M(') and N(').  From these definitions, the basic cell has
 * an area of B = U*U' + V*V' = (M*M' + N*N') / R*R' pixels, and the
 * multi-cell has an area of C = B * R*R' = M*M' + N*N' pixels.
 *
 * If the coefficients of the default device transformation matrix are xx,
 * xy, yx, and yy, then U and V are related to the frequency F and the angle
 * A by:
 *      P = 72 / F;
 *      U = P * (xx * cos(A) + yx * sin(A));
 *      V = P * (xy * cos(A) + yy * sin(A)).
 *
 * We can tile the plane with any rectangular super-cell that consists of
 * repetitions of the multi-cell and whose corners coincide with multi-cell
 * coordinates (0,0).  We observe that for any integers i, j such that i*N -
 * j*M' = 0, a multi-cell corner lies on the X axis at W = i*M + j*N';
 * similarly, if i'*M - j'*N' = 0, a corner lies on the Y axis at W' = i'*N
 * + j'*M'.  Then the super-cell occupies Z = W * W' pixels, consisting of Z
 * / C multi-cells or Z / B basic cells.  The trick in all this is to find
 * values of F and A that aren't too far from the requested ones, and that
 * yield a manageably small value for Z.
 *
 * Note that the super-cell only has to be so large because we want to use
 * it directly to tile the plane.  In fact, we can decompose it into W' / D
 * horizontal strips of width W and height D, shifted horizontally with
 * respect to each other by S pixels, where we compute S by finding h and k
 * such that h*N - k*M' = D and then S = h*M + k*N'.  The halftone setup
 * routines only generate a single strip of samples, and let
 * gx_ht_construct_spot_order construct the rest.  If W' is large, we
 * actually keep only one strip, and let the strip_tile_rectangle routines
 * do the shifting at rendering time.
 */
typedef struct gx_ht_cell_params_s {
    /* Defining values.  M * M1 != 0 or N * N1 != 0; R > 0, R1 > 0. */
    /* R and D are short rather than ushort so that we don't get */
    /* unsigned results from arithmetic. */
    short M, N, R;
    short M1, N1, R1;
    /* Derived values. */
    ulong C;
    short D, D1;
    uint W, W1;
    int S;
} gx_ht_cell_params_t;

/* Compute the derived values from the defining values. */
void gx_compute_cell_values(P1(gx_ht_cell_params_t *));

/*
 * The whitening order is represented by a pair of arrays.
 * The levels array contains an integer (an index into the bit_data array)
 * for each distinct halftone level, indicating how many pixels should be
 * whitened for that level; levels[0] = 0, levels[i] <= levels[i+1], and
 * levels[num_levels-1] <= num_bits.  The bit_data array contains data to
 * specify which bits should be set for each level: it has several
 * different representations depending on space/time tradeoffs.
 *
 * The default bit_data representation is an (offset,mask) pair for each
 * pixel in the tile.  bits[i].offset is the (properly aligned) byte index
 * of a pixel in the tile; bits[i].mask is the mask to be or'ed into this
 * byte and following ones.  This is arranged so it will work properly on
 * either big- or little-endian machines, and with different mask widths.
 */
/*
 * The mask width must be at least as wide as uint,
 * and must not be wider than the width implied by align_bitmap_mod.
 */
typedef uint ht_mask_t;

#define ht_mask_bits (sizeof(ht_mask_t) * 8)
typedef struct gx_ht_bit_s {
    uint offset;
    ht_mask_t mask;
} gx_ht_bit;

/* During sampling, bits[i].mask is used to hold a normalized sample value. */
typedef ht_mask_t ht_sample_t;

/* The following awkward expression avoids integer overflow. */
#define max_ht_sample (ht_sample_t)(((1 << (ht_mask_bits - 2)) - 1) * 2 + 1)

/*
 * Define the internal representation of a halftone order.
 * Note that it may include a cached transfer function.
 *
 * Halftone orders exist in two slightly different configurations, strip and
 * complete.  In a complete order, shift = 0 and full_height = height; in a
 * strip order, shift != 0 and full_height is the height of a fully expanded
 * halftone made up of enough shifted strip copies to get back to a zero
 * shift.  In other words, full_height is a cached value, but it is an
 * important one, since it is the modulus used for computing the
 * tile-relative phase.  Requirements:
 *      width > 0, height > 0, multiple > 0
 *      raster >= bitmap_raster(width)
 *      0 <= shift < width
 *      num_bits = width * height
 * For complete orders:
 *      full_height = height
 * For strip orders:
 *      full_height = height * width / gcd(width, shift)
 * Note that during the sampling of a complete spot halftone, these
 * invariants may be violated; in particular, it is possible that shift != 0
 * and height < full_height, even though num_bits and num_levels reflect the
 * full height.  In this case, the invariant is restored (by resetting
 * shift and height) when sampling is finished.  However, we must save the
 * original height and shift values used for sampling, since sometimes we
 * run the "finishing" routines more than once.  (This is ugly, but it's
 * too hard to fix.)
 *
 * See gxbitmap.h for more details about strip halftones.
 */
typedef struct gx_ht_cache_s gx_ht_cache;
#ifndef gx_ht_order_DEFINED
#  define gx_ht_order_DEFINED
typedef struct gx_ht_order_s gx_ht_order;
#endif
#ifndef gx_ht_tile_DEFINED
#  define gx_ht_tile_DEFINED
typedef struct gx_ht_tile_s gx_ht_tile;
#endif
typedef struct gx_ht_order_procs_s {

    /* Define the size of each element of bit_data. */

    uint bit_data_elt_size;

    /* Construct the order from the threshold array. */
    /* Note that for 16-bit threshold values, */
    /* each value is 2 bytes in big-endian order (Adobe spec). */

    int (*construct_order)(P2(gx_ht_order *order, const byte *thresholds));

    /* Return the (x,y) coordinate of an element of bit_data. */

    int (*bit_index)(P3(const gx_ht_order *order, uint index,
			gs_int_point *ppt));

    /* Update a halftone cache tile to match this order. */

    int (*render)(P3(gx_ht_tile *tile, int new_bit_level,
		     const gx_ht_order *order));

} gx_ht_order_procs_t;
/*
 * Define the procedure vectors for the supported implementations
 * (in gxhtbit.c).
 */
extern const gx_ht_order_procs_t ht_order_procs_table[2];
#define ht_order_procs_default ht_order_procs_table[0]	/* bit_data is gx_ht_bit[] */
#define ht_order_procs_short ht_order_procs_table[1]	/* bit_data is ushort[] */
/* For screen/spot halftones, we must record additional parameters. */
typedef struct gx_ht_order_screen_params_s {
    gs_matrix matrix;		/* CTM when the function was sampled */
    ulong max_size;		/* max bitmap size */
} gx_ht_order_screen_params_t;
struct gx_ht_order_s {
    gx_ht_cell_params_t params;	/* parameters defining the cells */
    ushort width;
    ushort height;
    ushort raster;
    ushort shift;
    ushort orig_height;
    ushort orig_shift;
    uint full_height;
    uint num_levels;		/* = levels size */
    uint num_bits;		/* = countof(bit_data) = width * height */
    const gx_ht_order_procs_t *procs;
    gs_memory_t *data_memory;	/* for levels and bit_data, may be 0 */
    uint *levels;
    void *bit_data;
    gx_ht_cache *cache;		/* cache to use */
    gx_transfer_map *transfer;	/* TransferFunction or 0 */
    gx_ht_order_screen_params_t screen_params;
};

#define ht_order_is_complete(porder)\
  ((porder)->shift == 0)
#define ht_order_full_height(porder)\
  ((porder)->shift == 0 ? (porder)->height :\
   (porder)->width / igcd((porder)->width, (porder)->shift) *\
     (porder)->height)

/* We only export st_ht_order for use in st_screen_enum. */
extern_st(st_ht_order);
#define public_st_ht_order()	/* in gsht.c */\
  gs_public_st_composite(st_ht_order, gx_ht_order, "gx_ht_order",\
    ht_order_enum_ptrs, ht_order_reloc_ptrs)
#define st_ht_order_max_ptrs 4

/*
 * Define a device halftone.  This consists of one or more orders.
 * If components = 0, then order is the only current halftone screen
 * (set by setscreen, Type 1 sethalftone, Type 3 sethalftone, or
 * Type 5 sethalftone with only a Default).  Otherwise, order is the
 * gray or black screen (for gray/RGB or CMYK devices respectively),
 * and components is an array of gx_ht_order_components parallel to
 * the components of the client halftone (set by setcolorscreen or
 * Type 5 sethalftone).
 *
 * Multi-component halftone orders may be required even in Level 1 systems,
 * because they are needed for setcolorscreen.
 *
 * NOTE: it is assumed that all subsidiary structures of device halftones
 * (the components array, and the bit_data, levels, cache, and transfer
 * members of any gx_ht_orders, both the default order and any component
 * orders) are allocated with the same allocator as the device halftone
 * itself.
 */
typedef struct gx_ht_order_component_s {
    gx_ht_order corder;
    gs_ht_separation_name cname;
} gx_ht_order_component;

#define private_st_ht_order_component()	/* in gsht.c */\
  gs_private_st_ptrs_add0(st_ht_order_component, gx_ht_order_component,\
    "gx_ht_order_component", ht_order_component_enum_ptrs,\
     ht_order_component_reloc_ptrs, st_ht_order, corder)
#define st_ht_order_component_max_ptrs st_ht_order_max_ptrs
/* We only export st_ht_order_component_element for use in banding. */
extern_st(st_ht_order_component_element);
#define public_st_ht_order_comp_element() /* in gsht.c */\
  gs_public_st_element(st_ht_order_component_element, gx_ht_order_component,\
    "gx_ht_order_component[]", ht_order_element_enum_ptrs,\
    ht_order_element_reloc_ptrs, st_ht_order_component)

#ifndef gx_device_halftone_DEFINED
#  define gx_device_halftone_DEFINED
typedef struct gx_device_halftone_s gx_device_halftone;
#endif

/*
 * color_indices is a cache that gives the indices in components of
 * the screens for the 1, 3, or 4 primary color(s).  These indices are
 * always in the same order, namely:
 *      -,-,-,W(gray)
 *      R,G,B,-
 *      C,M,Y,K
 */
struct gx_device_halftone_s {
    gx_ht_order order;		/* must be first, for subclassing */
    rc_header rc;
    gs_id id;			/* the id changes whenever the data change */
    /*
     * We have to keep the halftone type so that we can pass it
     * through the band list for gx_imager_dev_ht_install.
     */
    gs_halftone_type type;
    gx_ht_order_component *components;
    uint num_comp;
    /* The following are computed from the above. */
    uint color_indices[4];
    int lcm_width, lcm_height;	/* LCM of primary color tile sizes, */
    /* max_int if overflowed */
};

extern_st(st_device_halftone);
#define public_st_device_halftone() /* in gsht.c */\
  gs_public_st_ptrs_add1(st_device_halftone, gx_device_halftone,\
    "gx_device_halftone", device_halftone_enum_ptrs,\
    device_halftone_reloc_ptrs, st_ht_order, order, components)
#define st_device_halftone_max_ptrs (st_ht_order_max_ptrs + 1)

/* Complete a halftone order defined by a threshold array. */
void gx_ht_complete_threshold_order(P1(gx_ht_order *porder));

/* Release a gx_device_halftone by freeing its components. */
/* (Don't free the gx_device_halftone itself.) */
void gx_device_halftone_release(P2(gx_device_halftone * pdht,
				   gs_memory_t * mem));

#endif /* gxdht_INCLUDED */