//========================================================================
//
// AOutputDev.cc
//
// adapted from XOutputDev.cc - Copyright 1996 Derek B. Noonburg
//
// changes are copyright 1999 Emmanuel Lesueur
//
//========================================================================

#ifdef __GNUC__
#pragma implementation
#endif

#define DB(x) //x

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define Object ZZObject
#include <graphics/gfx.h>
#include <graphics/text.h>
#undef Object
#include "gmem.h"
#include "GString.h"
#include "Object.h"
#include "Stream.h"
#include "GfxState.h"
#include "GfxFont.h"
#include "Error.h"
#include "TextOutputDev.h"
#include "AOutputDev.h"
#include "AGfx.h"
#include "FontOutputDev.h"


//------------------------------------------------------------------------
// Constants and macros
//------------------------------------------------------------------------

inline int xoutRound(double x) { return int(x + 0.5); }

const int maxCurveSplits=6;  // max number of splits when recursively
			     //   drawing Bezier curves

PArea<short> xoutRound(const PArea<double>& a) {
  PArea<short> r;
  r.rule(PArea<short>::Rule(a.rule()));
  r.reserve(a.size());
  for(PArea<double>::const_iterator p(a.begin()); p != a.end(); ++p) {
    Polygon<short> t;
    t.reserve(p->size());
    for(Polygon<double>::const_iterator v(p->begin()); v != p->end(); ++v)
      t.push_back(Vertex<short>(xoutRound(v->x), xoutRound(v->y)));
    r.push_back(t);
  }
  return r;
}

//------------------------------------------------------------------------
// Parameters
//------------------------------------------------------------------------

extern int maxColors;

//------------------------------------------------------------------------
// ColorTable
//------------------------------------------------------------------------

Gulong ColorTable::add(Gulong x) {
  if (num == maxEntries) {
    maxEntries = (maxEntries * 3) / 2 + 16;
    entries = (entry*) grealloc(entries, maxEntries*sizeof(entry));
  }
  Gulong n = num;
  entry *p = entries;
  while (n > 0) {
    Gulong k = n / 2;
    entry *q = p + k;
    if (x > q->val) {
      p = q + 1;
      n -= k + 1;
    } else if(x != q->val)
      n = k;
    else {
      p = q;
      break;
    }
  }
  if (p != entries + num)
    memmove(p+1, p, (entries+num-p)*sizeof(entry));
  p->n = num;
  p->val = x;
  return num++;
}

Gulong ColorTable::find(Gulong x) const {
  Gulong n = num;
  entry *p = entries;
  while (n > 0) {
    Gulong k = n / 2;
    entry *q = p + k;
    if (x > q->val) {
      p = q + 1;
      n -= k + 1;
    } else if(x != q->val)
      n = k;
    else
      return q->n;
  }
  return Gulong(-1);
}

// find the RGB value of pen n
// slow, but only used int drawImageMask...
Gulong ColorTable::find_rgb(Gulong n) const {
  if (n < num) {
    entry *p = entries;
    while (p->n != n)
      ++p;
    return p->val;
  }
  return 0; // should not happen...
}

//------------------------------------------------------------------------
// Constructed characters
//------------------------------------------------------------------------

#define lastRegularChar 0x0ff
#define firstSubstChar  0x100
#define lastSubstChar   0x104
#define firstConstrChar 0x105
#define lastConstrChar  0x106
#define firstMultiChar  0x107
#define lastMultiChar   0x10d

// substituted chars
static Guchar substChars[] = {
  0x27,                         // 100: quotesingle --> quoteright
  0x2d,                         // 101: emdash --> hyphen
  0xad,                         // 102: hyphen --> endash
  0x2f,                         // 103: fraction --> slash
  0xb0,                         // 104: ring --> degree
};

// constructed chars
// 105: bullet
// 106: trademark

// built-up chars
static char *multiChars[] = {
  "fi",                         // 107: fi
  "fl",                         // 108: fl
  "OE",                         // 109: OE
  "oe",                         // 10a: oe
  "...",                        // 10b: ellipsis
  "``",                         // 10c: quotedblleft
  "''"                          // 10d: quotedblright
};

// ignored chars
// 10c: Lslash
// 10d: Scaron
// 10e: Zcaron
// 10f: Ydieresis
// 110: breve
// 111: caron
// 112: circumflex
// 113: dagger
// 114: daggerdbl
// 115: dotaccent
// 116: dotlessi
// 117: florin
// 118: grave
// 119: guilsinglleft
// 11a: guilsinglright
// 11b: hungarumlaut
// 11c: lslash
// 11d: ogonek
// 11e: perthousand
// 11f: quotedblbase
// 120: quotesinglbase
// 121: scaron
// 122: tilde
// 123: zcaron

//------------------------------------------------------------------------
// AOutputFont
//------------------------------------------------------------------------

int AOutputFont::xFontCount;

// Note: if real font is substantially narrower than substituted
// font, the size is reduced accordingly.
AOutputFont::AOutputFont(AGfx& gfx1, GfxFont *gfxFont, double m11, double m12,
			 double m21, double m22) : gfx(gfx1) {
  GfxFontEncoding *encoding;
  const char *fontName;
  int fontStyle;
  //GBool rotated;
  double size;
  int startSize, sz;
  int index;
  int code, code2;
  char *charName;
  int n;
  double w1, w2;

  // init
  id = gfxFont->getID();
  mat11 = m11;
  mat12 = m12;
  mat21 = m21;
  mat22 = m22;
  xFont = NULL;
  hex = gFalse;

  // construct X font name
  fontName = getAFont(gfxFont, encoding, fontStyle, w1, w2);
  m11 *= w1;
  m12 *= w2;
  m21 *= w1;
  m22 *= w2;

  // Construct forward and reverse map.
  // This tries to deal with font subset character names of the
  // form 'Bxx', 'Cxx', 'Gxx', with decimal or hex numbering.

  for (code = 0; code < 256; ++code)
    revMap[code] = 0;
  if (encoding) {
    for (code = 0; code < 256; ++code) {
      if ((charName = gfxFont->getCharName(code))) {
	if ((charName[0] == 'B' || charName[0] == 'C' ||
	     charName[0] == 'G') &&
	    strlen(charName) == 3 &&
	    ((charName[1] >= 'a' && charName[1] <= 'f') ||
	     (charName[1] >= 'A' && charName[1] <= 'F') ||
	     (charName[2] >= 'a' && charName[2] <= 'f') ||
	     (charName[2] >= 'A' && charName[2] <= 'F'))) {
	  hex = gTrue;
	  break;
	}
      }
    }
    for (code = 0; code < 256; ++code) {
      if ((charName = gfxFont->getCharName(code))) {
	if ((code2 = encoding->getCharCode(charName)) < 0) {
	  n = strlen(charName);
	  if (hex && n == 3 &&
	      (charName[0] == 'B' || charName[0] == 'C' ||
	       charName[0] == 'G') &&
	      isxdigit(charName[1]) && isxdigit(charName[2])) {
	    //sscanf(charName+1, "%x", &code2);
	    code2 = strtol(charName+1, NULL, 16);
	  } else if (!hex && n >= 2 && n <= 3 &&
		     isdigit(charName[0]) && isdigit(charName[1])) {
	    code2 = atoi(charName);
	    if (code2 >= 256)
	      code2 = -1;
	  } else if (!hex && n >= 3 && n <= 5 && isdigit(charName[1])) {
	    code2 = atoi(charName+1);
	    if (code2 >= 256)
	      code2 = -1;
	  }
	  //~ this is a kludge -- is there a standard internal encoding
	  //~ used by all/most Type 1 fonts?
	  if (code2 == 262)           // hyphen
	    code2 = 45;
	  else if (code2 == 266)      // emdash
	    code2 = 208;
	}
	if (code2 >= 0) {
	  map[code] = (Gushort)code2;
	  if (code2 < 256)
	    revMap[code2] = (Guchar)code;
	} else {
	  map[code] = 0;
	}
      } else {
	map[code] = 0;
      }
    }
  } else {
    code2 = 0; // to make gcc happy
    //~ this is a hack to get around the fact that X won't draw
    //~ chars 0..31; this works when the fonts have duplicate encodings
    //~ for those chars
    for (code = 0; code < 32; ++code) {
      if ((charName = gfxFont->getCharName(code)) &&
	  (code2 = gfxFont->getCharCode(charName)) >= 0) {
	map[code] = (Gushort)code2;
	if (code2 < 256)
	  revMap[code2] = (Guchar)code;
      }
    }
    for (code = 32; code < 256; ++code) {
      map[code] = (Gushort)code;
      revMap[code] = (Guchar)code;
    }
  }

  // compute size, normalize matrix
  size = sqrt(m21*m21 + m22*m22);
  m11 = m11 / size;
  m12 = -m12 / size;
  m21 = m21 / size;
  m22 = -m22 / size;
  startSize = (int)size;

  // try to get a rotated font?
  /*rotated = !(mat11 > 0 && mat22 > 0 && fabs(mat11/mat22 - 1) < 0.2 &&
	      fabs(mat12) < 0.01 && fabs(mat21) < 0.01);

  // open X font -- if font is not found (which means the server can't
  // scale fonts), try progressively smaller and then larger sizes
  //~ This does a linear search -- it should get a list of fonts from
  //~ the server and pick the closest.
  if (rotated)
    sprintf(fontSize, "[%s%0.2f %s%0.2f %s%0.2f %s%0.2f]",
	    m11<0 ? "~" : "", fabs(m11 * startSize),
	    m12<0 ? "~" : "", fabs(m12 * startSize),
	    m21<0 ? "~" : "", fabs(m21 * startSize),
	    m22<0 ? "~" : "", fabs(m22 * startSize));
  else
    sprintf(fontSize, "%d", startSize);*/

  xFont = xFontCount++;
  gfx.openfont(xFont, fontName, startSize, fontStyle);
}

AOutputFont::~AOutputFont() {
  gfx.closefont(xFont);
}

//------------------------------------------------------------------------
// AOutputFontCache
//------------------------------------------------------------------------

AOutputFontCache::AOutputFontCache(AGfx& g) : gfx(g) {
  int i;

  for (i = 0; i < fontCacheSize; ++i)
    fonts[i] = NULL;
  numFonts = 0;
}

AOutputFontCache::~AOutputFontCache() {
  int i;

  for (i = 0; i < numFonts; ++i)
    delete fonts[i];
}

AOutputFont *AOutputFontCache::getFont(GfxFont *gfxFont,
				       double m11, double m12,
				       double m21, double m22) {
  AOutputFont *font;
  int i, j;

  // is it the most recently used font?
  if (numFonts > 0 && fonts[0]->matches(gfxFont->getID(),
					m11, m12, m21, m22))
    return fonts[0];

  // is it in the cache?
  for (i = 1; i < numFonts; ++i) {
    if (fonts[i]->matches(gfxFont->getID(), m11, m12, m21, m22)) {
      font = fonts[i];
      for (j = i; j > 0; --j)
	fonts[j] = fonts[j-1];
      fonts[0] = font;
      return font;
    }
  }

  // make a new font
  font = new AOutputFont(gfx, gfxFont, m11, m12, m21, m22);
  /*if (!font->getTextFont()) {
    delete font;
    return NULL;
  }*/

  // insert font in cache
  if (numFonts == fontCacheSize) {
    --numFonts;
    delete fonts[numFonts];
  }
  for (j = numFonts; j > 0; --j)
    fonts[j] = fonts[j-1];
  fonts[0] = font;
  ++numFonts;

  // return it
  return font;
}

//------------------------------------------------------------------------
// AOutputDev
//------------------------------------------------------------------------

AOutputDev::AOutputDev(AGfx& gfx1, Guint depth1, ColorMap* colormap1)
    : gfx(gfx1) {
  Gulong mask;
  int r, g, b, n, m, i;
  GBool ok;

  // get display/pixmap info
  depth = depth1;
  colormap = colormap1;

  rShift = 4;
  gShift = 4;
  bShift = 4;
  rMul = (1 << rShift) - 1;
  gMul = (1 << gShift) - 1;
  bMul = (1 << bShift) - 1;
  colorMask = 0x00f0f0f0;

  // check for TrueColor visual
  trueColor = depth>8;

  // set up the font cache and fonts
  gfxFont = NULL;
  font = NULL;
  fontCache = new AOutputFontCache(gfx);

  // create text object
  text = new TextPage(gFalse);
}

AOutputDev::~AOutputDev() {
  delete fontCache;
  delete text;
}

void AOutputDev::startPage(int pageNum, GfxState *state) {
  GfxColor color;

  capStyle = CapButt;
  joinStyle = JoinBevel;
  curColor = penColor;
  strokeColor = curColor;
  fillColor = curColor;
  linkColor = Gulong(-1);

  clipRegion.clear();
  installClip();
  Polygon<double> p;
  p.reserve(4);
  p.push_back(Vertex<double>(0,0));
  p.push_back(Vertex<double>(10000,0));
  p.push_back(Vertex<double>(10000,10000));
  p.push_back(Vertex<double>(0,10000));
  clipRegion.push_back(p);
  clipStack.clear();

  // default line flatness
  flatness = 0;

  // clear font
  gfxFont = NULL;
  font = NULL;

  // clear text object
  text->clear();

  gfx.init();
  gfx.start_page();
  colorTable.clear();
  colorTable.add(0x000000UL);
  colorTable.add(0xf0f0f0UL);
}

void AOutputDev::endPage() {
  gfx.end_page();
  gfx.flush();
  text->coalesce();
}

void AOutputDev::drawLinkBorder(double x1, double y1, double x2, double y2,
				double w) {
  int x, y;
  DB(printf("\ndrawlink(%f,%f,%f,%f,%f)\n",x1,y1,x2,y2,w);)
  if (linkColor == Gulong(-1)) {
      GfxColor color;
      color.setRGB(0, 0, 1);
      linkColor = findColor(&color);
  }
  if (curColor != linkColor) {
      curColor = linkColor;
      gfx.setapen(curColor);
  }
  //XSetLineAttributes(display, strokeGC, xoutRound(w),
  //                   LineSolid, CapRound, JoinRound);
  Polygon<short> points;
  points.reserve(5);
  cvtUserToDev(x1, y1, &x, &y);
  Vertex<short> orig(x,y);
  points.push_back(orig);
  cvtUserToDev(x2, y1, &x, &y);
  points.push_back(Vertex<short>(x,y));
  cvtUserToDev(x2, y2, &x, &y);
  points.push_back(Vertex<short>(x,y));
  cvtUserToDev(x1, y2, &x, &y);
  points.push_back(Vertex<short>(x,y));
  points.push_back(orig);
  gfx.polydraw(points);
}

void AOutputDev::saveState(GfxState *state) {
  DB(printf("\nsave state\n");)
  clipStack.push_back(clipRegion);
}

void AOutputDev::restoreState(GfxState *state) {
  DB(printf("\nrestore state\n");)
  clipRegion = clipStack.back();
  clipStack.pop_back();
  curColor = Gulong(-1);
  updateAll(state);
  installClip();
}

void AOutputDev::updateAll(GfxState *state) {
  updateLineAttrs(state, gTrue);
  updateFlatness(state);
  updateMiterLimit(state);
  updateFillColor(state);
  updateStrokeColor(state);
  updateFont(state);
}

void AOutputDev::updateCTM(GfxState *state, double m11, double m12,
			   double m21, double m22, double m31, double m32) {
  updateLineAttrs(state, gTrue);
}

void AOutputDev::updateLineDash(GfxState *state) {
  updateLineAttrs(state, gTrue);
}

void AOutputDev::updateFlatness(GfxState *state) {
  flatness = state->getFlatness();
}

void AOutputDev::updateLineJoin(GfxState *state) {
  updateLineAttrs(state, gFalse);
}

void AOutputDev::updateLineCap(GfxState *state) {
  updateLineAttrs(state, gFalse);
}

// unimplemented
void AOutputDev::updateMiterLimit(GfxState *state) {
}

void AOutputDev::updateLineWidth(GfxState *state) {
  updateLineAttrs(state, gFalse);
}

void AOutputDev::updateLineAttrs(GfxState *state, GBool updateDash) {
  CapStyle cap;
  JoinStyle join;
  double *dashPattern;
  int dashLength;
  double dashStart;
  int i;

  lineWidth = state->getTransformedLineWidth();
  switch (state->getLineCap()) {
  case 0: cap = CapButt; break;
  case 1: cap = CapRound; break;
  case 2: cap = CapProjecting; break;
  default:
    error(-1, "Bad line cap style (%d)", state->getLineCap());
    cap = CapButt;
    break;
  }
  capStyle = cap;
  switch (state->getLineJoin()) {
  case 0: join = JoinMiter; break;
  case 1: join = JoinRound; break;
  case 2: join = JoinBevel; break;
  default:
    error(-1, "Bad line join style (%d)", state->getLineJoin());
    join = JoinMiter;
    break;
  }
  joinStyle = join;
  state->getLineDash(&dashPattern, &dashLength, &dashStart);
  /*XSetLineAttributes(display, strokeGC, xoutRound(width),
		     dashLength > 0 ? LineOnOffDash : LineSolid,
		     cap, join);*/
  if (updateDash) {
    unsigned mask = 0xffff;
    short start = 0;
    if (dashLength > 0) {
      int n = 16;
      for (i = 0; i < dashLength; ++i) {
	int k = xoutRound(state->transformWidth(dashPattern[i]));
	if (k < n) {
	  mask ^= (1 << n-k) - 1;
	  n -= k;
	} else
	  break;
      }
      start = xoutRound(dashStart);
    }
    gfx.set_line_ptrn(mask, start);
  }
}

void AOutputDev::updateFillColor(GfxState *state) {
  fillColor = findColor(state->getFillColor());
  DB(printf("\nfill color=%d\n",fillColor);)
}

void AOutputDev::updateStrokeColor(GfxState *state) {
  strokeColor = findColor(state->getStrokeColor());
  DB(printf("\nstroke color=%d\n",strokeColor);)
}

void AOutputDev::updateFont(GfxState *state) {
  double m11, m12, m21, m22;

  if (!(gfxFont = state->getFont())) {
    font = NULL;
    return;
  }
  state->getFontTransMat(&m11, &m12, &m21, &m22);
  m11 *= state->getHorizScaling();
  m21 *= state->getHorizScaling();
  font = fontCache->getFont(gfxFont, m11, m12, m21, m22);
  if (font)
    gfx.setfont(font->getTextFont());
  else {
      DB(printf("\nupdateFont failed.\n");)
  }
}

void AOutputDev::stroke(GfxState *state) {

  if (curColor != strokeColor) {
    curColor = strokeColor;
    gfx.setapen(curColor);
  }

  // transform points
  PArea<double> area(convertPath(state));

  // draw each subpath
  if (lineWidth <= 1.5) {

    PArea<short> iarea(xoutRound(area));
    for (PArea<short>::const_iterator p(iarea.begin()); p != iarea.end(); ++p)
      if(!p->empty()) {
	DB(printf("\nstroke(%d)\n",p->size());)
	gfx.polydraw(*p);
      }

  } else {

    for (PArea<double>::const_iterator q(area.begin()); q != area.end(); ++q) {
      Polygon<double>::const_iterator p(q->begin());
      for (int k = 1; k < q->size(); ++k, ++p) {
	if (floor(p[0].x + 0.5) == floor(p[1].x + 0.5)) {
	  DB(printf("\nthickVstroke\n");)
	  short x1 = xoutRound(p[0].x - lineWidth/2);
	  short x2 = xoutRound(p[0].x + lineWidth/2);
	  short y1 = xoutRound(p[0].y);
	  short y2 = xoutRound(p[1].y);
	  if (y1 > y2) {
	      short t = y1;
	      y1 = y2;
	      y2 = t;
	  }
	  gfx.rectfill(x1,y1,x2,y2);
	} else if (floor(p[0].y + 0.5) == floor(p[1].y + 0.5)) {
	  DB(printf("\nthickHstroke\n");)
	  short y1 = xoutRound(p[0].y - lineWidth/2);
	  short y2 = xoutRound(p[0].y + lineWidth/2);
	  short x1 = xoutRound(p[0].x);
	  short x2 = xoutRound(p[1].x);
	  if (x1 > x2) {
	      short t = x1;
	      x1 = x2;
	      x2 = t;
	  }
	  gfx.rectfill(x1,y1,x2,y2);
	} else {
	  DB(printf("\nthickstroke\n");)
	  double w = lineWidth/2;
	  double dx = p[1].x - p[0].x;
	  double dy = p[1].y - p[0].y;
	  double l = sqrt(dx*dx+dy*dy);
	  double c = dx/l;
	  double s = dy/l;
	  Polygon<short> pts;
	  pts.reserve(4);
	  pts.push_back(Vertex<short>(xoutRound(p[0].x - w*s),
				      xoutRound(p[0].y - w*c)));
	  pts.push_back(Vertex<short>(xoutRound(p[1].x - w*s),
				      xoutRound(p[1].y - w*c)));
	  pts.push_back(Vertex<short>(xoutRound(p[1].x + w*s),
				      xoutRound(p[1].y + w*c)));
	  pts.push_back(Vertex<short>(xoutRound(p[0].x + w*s),
				      xoutRound(p[0].y + w*c)));
	  AGfx::AreaDrawer(gfx).add(pts);
	}
      }
    }
  }
}

void AOutputDev::fill(GfxState *state) {
  DB(printf("\nfill\n");)
  doFill(state, PArea<double>::winding);
}

void AOutputDev::eoFill(GfxState *state) {
  DB(printf("\neofill\n");)
  doFill(state, PArea<double>::even_odd);
}

void AOutputDev::doFill(GfxState *state, int rule) {

  if (curColor != fillColor) {
    curColor = fillColor;
    gfx.setapen(curColor);
  }

  // transform points
  PArea<short> area;
  {
    PArea<double> t(convertPath(state));
    t.rule(PArea<double>::Rule(rule));
    t.reduce();
    if(rule == PArea<double>::winding)
      t = t.make_convex_union();
    area = xoutRound(t);
  }

  /*for (PArea<short>::const_iterator p(area.begin()); p != area.end(); ++p)
      if(!p->empty()) {
	Polygon<short> q(*p);
	DB(printf("\nfill(%d)\n",q.size());)
	q.push_back(*q.begin());
	gfx.polydraw(q);
      }*/

  // fill them
  if(area.is_disjoint_rectangle_union()) {
    for(PArea<short>::const_iterator p(area.begin()); p != area.end(); ++p) {
      if(!p->empty()) {
	Polygon<short>::const_iterator points(p->begin());
	short x1,x2,y1,y2;
	if(points[0].x>points[2].x) {
	    x1=points[2].x;
	    x2=points[0].x;
	} else {
	    x1=points[0].x;
	    x2=points[2].x;
	}
	if(points[0].y>points[2].y) {
	    y1=points[2].y;
	    y2=points[0].y;
	} else {
	    y1=points[0].y;
	    y2=points[2].y;
	}
	DB(printf("rectfill: (%d,%d)-(%d,%d)\n",x1,y1,x2,y2);)
	gfx.rectfill(x1,y1,x2,y2);
      }
    }
  } else {
    DB(printf("polyfill:");)
    AGfx::AreaDrawer ad(gfx);
    for(PArea<short>::const_iterator p(area.begin()); p != area.end(); ++p)
      ad.add(*p);
  }

}

void AOutputDev::clip(GfxState *state) {
  DB(printf("\nclip\n");)
  doClip(state, PArea<double>::winding);
}

void AOutputDev::eoClip(GfxState *state) {
  DB(printf("\neoclip\n");)
  doClip(state, PArea<double>::even_odd);
}

void AOutputDev::doClip(GfxState *state, int rule) {

  // transform points
  PArea<double> area(convertPath(state));
  area.rule(PArea<double>::Rule(rule));

  // open closed paths
  area.reduce();

  area = area.make_convex_union();

  // intersect with clipping region
  clipRegion = clipRegion & area;
  clipRegion.reduce();

  installClip();
}

void AOutputDev::installClip() {
  PArea<short> c(xoutRound(clipRegion));
  gfx.clearclip();
  for(PArea<short>::const_iterator p(c.begin()); p != c.end(); ++p) {
    if(!p->empty()) {
      if(p->is_rectangle()) {
	Polygon<short>::const_iterator points(p->begin());
	short x1,x2,y1,y2;
	if(points[0].x>points[2].x) {
	    x1=points[2].x;
	    x2=points[0].x;
	} else {
	    x1=points[0].x;
	    x2=points[2].x;
	}
	if(points[0].y>points[2].y) {
	    y1=points[2].y;
	    y2=points[0].y;
	} else {
	    y1=points[0].y;
	    y2=points[2].y;
	}
	DB(printf("cliprect: (%d,%d)-(%d,%d)\n",x1,y1,x2,y2);)
	gfx.rectclip(x1,y1,x2,y2);
      } else {
	DB(printf("clippoly(%d):\n",p->size());)
	gfx.polyclip(*p);
      }
    }
  }
  gfx.installclip();
}

//
// Transform points in the path and convert curves to line segments.
//
PArea<double> AOutputDev::convertPath(GfxState *state) {
  DB(printf("path[");)
  PArea<double> res;

  // get path and number of subpaths
  GfxPath *path = state->getPath();
  int n = path->getNumSubpaths();

  // do each subpath
  for (int i = 0; i < n; ++i)
    res.push_back(convertSubpath(state, path->getSubpath(i)));

  DB(printf("]\n");)
  return res;
}

//
// Transform points in a single subpath and convert curves to line
// segments.
//
Polygon<double> AOutputDev::convertSubpath(GfxState *state, GfxSubpath *subpath) {
  DB(printf("[");)
  DB(int k = 0;)
  double x0, y0, x1, y1, x2, y2, x3, y3;
  int m, i;
  Polygon<double> poly;

  m = subpath->getNumPoints();
  i = 0;
  while (i < m) {
    if (i >= 1 && subpath->getCurve(i)) {
      state->transform(subpath->getX(i-1), subpath->getY(i-1), &x0, &y0);
      state->transform(subpath->getX(i), subpath->getY(i), &x1, &y1);
      state->transform(subpath->getX(i+1), subpath->getY(i+1), &x2, &y2);
      state->transform(subpath->getX(i+2), subpath->getY(i+2), &x3, &y3);
      doCurve(poly, x0, y0, x1, y1, x2, y2, x3, y3);
      i += 3;
    } else {
      state->transform(subpath->getX(i), subpath->getY(i), &x1, &y1);
      DB(if(!(k++&3))printf("\n");printf(" (%g,%g)",x1,y1);)
      poly.push_back(Vertex<double>(x1, y1));
      ++i;
    }
  }
  DB(printf(" ]\n");)
  return poly;
}

//
// Subdivide a Bezier curve.  This uses floating point to avoid
// propagating rounding errors.  (The curves look noticeably more
// jagged with integer arithmetic.)
//
void AOutputDev::doCurve(Polygon<double>& poly,
			 double x0, double y0, double x1, double y1,
			 double x2, double y2, double x3, double y3) {
  double x[(1<<maxCurveSplits)+1][3];
  double y[(1<<maxCurveSplits)+1][3];
  int next[1<<maxCurveSplits];
  int p1, p2, p3;
  double xx1, yy1, xx2, yy2;
  double dx, dy, mx, my, d1, d2;
  double xl0, yl0, xl1, yl1, xl2, yl2;
  double xr0, yr0, xr1, yr1, xr2, yr2, xr3, yr3;
  double xh, yh;
  double flat;

  flat = (double)(flatness * flatness);
  if (flat < 1)
    flat = 1;

  // initial segment
  p1 = 0;
  p2 = 1<<maxCurveSplits;
  x[p1][0] = x0;  y[p1][0] = y0;
  x[p1][1] = x1;  y[p1][1] = y1;
  x[p1][2] = x2;  y[p1][2] = y2;
  x[p2][0] = x3;  y[p2][0] = y3;
  next[p1] = p2;

  while (p1 < (1<<maxCurveSplits)) {

    // get next segment
    xl0 = x[p1][0];  yl0 = y[p1][0];
    xx1 = x[p1][1];  yy1 = y[p1][1];
    xx2 = x[p1][2];  yy2 = y[p1][2];
    p2 = next[p1];
    xr3 = x[p2][0];  yr3 = y[p2][0];

    // compute distances from control points to midpoint of the
    // straight line (this is a bit of a hack, but it's much faster
    // than computing the actual distances to the line)
    mx = (xl0 + xr3) * 0.5;
    my = (yl0 + yr3) * 0.5;
    dx = xx1 - mx;
    dy = yy1 - my;
    d1 = dx*dx + dy*dy;
    dx = xx2 - mx;
    dy = yy2 - my;
    d2 = dx*dx + dy*dy;

    // if curve is flat enough, or no more divisions allowed then
    // add the straight line segment
    if (p2 - p1 <= 1 || (d1 <= flat && d2 <= flat)) {
      DB(printf(" (%g,%g)",xr3,yr3);)
      poly.push_back(Vertex<double>(xr3, yr3));
      p1 = p2;

    // otherwise, subdivide the curve
    } else {
      xl1 = (xl0 + xx1) * 0.5;
      yl1 = (yl0 + yy1) * 0.5;
      xh = (xx1 + xx2) * 0.5;
      yh = (yy1 + yy2) * 0.5;
      xl2 = (xl1 + xh) * 0.5;
      yl2 = (yl1 + yh) * 0.5;
      xr2 = (xx2 + xr3) * 0.5;
      yr2 = (yy2 + yr3) * 0.5;
      xr1 = (xh + xr2) * 0.5;
      yr1 = (yh + yr2) * 0.5;
      xr0 = (xl2 + xr1) * 0.5;
      yr0 = (yl2 + yr1) * 0.5;

      // add the new subdivision points
      p3 = (p1 + p2) / 2;
      x[p1][1] = xl1;  y[p1][1] = yl1;
      x[p1][2] = xl2;  y[p1][2] = yl2;
      next[p1] = p3;
      x[p3][0] = xr0;  y[p3][0] = yr0;
      x[p3][1] = xr1;  y[p3][1] = yr1;
      x[p3][2] = xr2;  y[p3][2] = yr2;
      next[p3] = p2;
    }
  }
}

void AOutputDev::beginString(GfxState *state, GString *s) {
  text->beginString(state, s, font ? font->isHex() : gFalse);
}

void AOutputDev::endString(GfxState *state) {
  text->endString();
}

void AOutputDev::drawChar(GfxState *state, double x, double y,
			  double dx, double dy, Guchar c) {
  Gushort c1;
  char *p;
  int n, i;
  double x1, y1;
  double tx;

  text->addChar(state, x, y, dx, dy, c);

  if (!font || c==13)
    return;

  // check for invisible text -- this is used by Acrobat Capture
  if ((state->getRender() & 3) == 3)
    return;

  DB(if(c>=32)printf("%c",c);else printf(" char(%x) ",c);)
  if (state->getRender() & 1) {
      if (curColor != strokeColor) {
	  curColor = strokeColor;
	  gfx.setapen(curColor);
      }
  } else {
      if (curColor != fillColor) {
	  curColor = fillColor;
	  gfx.setapen(curColor);
      }
  }

  state->transform(x, y, &x1, &y1);
  c1 = font->mapChar(c);
  if (c1 <= lastRegularChar)
    gfx.addchar(xoutRound(x1), xoutRound(y1), c1);
  else if (c1 <= lastSubstChar) {
    char c = (char)substChars[c1 - firstSubstChar];
    gfx.addchar(xoutRound(x1), xoutRound(y1), c);
  } else if (c1 <= lastConstrChar) {
    //~ need to deal with rotated text here
    switch (c1 - firstConstrChar) {
    case 0: // bullet
      tx = 0.25 * state->getTransformedFontSize() * gfxFont->getWidth(c);
      y1 -= 0.3 * state->getTransformedFontSize() * gfxFont->getWidth(c);
      //***y1 -= 0.4 * font->getTextFont()->tf_Baseline;
      gfx.rectfill(xoutRound(x1 + tx), xoutRound(y1 - tx),
		   xoutRound(x1 + 3 * tx), xoutRound(y1 + tx));
      break;
    case 1: // trademark
//~ this should use a smaller font
//      tx = state->getTransformedFontSize() *
//           (gfxFont->getWidth(c) -
//            gfxFont->getWidth(font->revCharMap('M')));
      tx = 0.9 * state->getTransformedFontSize() *
	   gfxFont->getWidth(font->revMapChar('T'));
      y1 -= 0.33 * state->getTransformedFontSize() *
	    gfxFont->getWidth(font->revMapChar('T'));
      //***y1 -= 0.33 * (double)font->getTextFont()->tf_Baseline;
      gfx.addchar(xoutRound(x1), xoutRound(y1), 'T');
      x1 += tx;
      gfx.addchar(xoutRound(x1), xoutRound(y1), 'M');
      break;
    }
  } else if (c1 <= lastMultiChar) {
    p = multiChars[c1 - firstMultiChar];
    n = strlen(p);
    tx = gfxFont->getWidth(c);
    tx -= gfxFont->getWidth(font->revMapChar(p[n-1]));
    tx = tx * state->getTransformedFontSize() / (double)(n - 1);
    for (i = 0; i < n; ++i) {
      gfx.addchar(xoutRound(x1), xoutRound(y1), p[i]);
      x1 += tx;
    }
  }
}

void AOutputDev::drawChar16(GfxState *state, double x, double y,
			    double dx, double dy, int c) {
  DB(printf("\ndrawchar16\n");)
}

// These four functions are defined to work around a bug
// in egcs for 68k: it gets confused when trying to inline
// calls to Read/WritePixelArrays(8).
void getimage(AGfx& gfx,AGfx::Image& im,short x,short y) {
    gfx.get_image(im, x, y);
}

void getimage(AGfx& gfx,AGfx::Image24& im,short x,short y) {
    gfx.get_image(im, x, y);
}

void putimage(AGfx& gfx,AGfx::Image& im,short x,short y) {
    gfx.put_image(im, x, y);
}

void putimage(AGfx& gfx,AGfx::Image24& im,short x,short y) {
    gfx.put_image(im, x, y);
}

void AOutputDev::drawImageMask(GfxState *state, Stream *str,
			       int width, int height, GBool invert,
			       GBool inlineImg) {
  int x0, y0;                   // top left corner of image
  int w0, h0, w1, h1;           // size of image
  //int x2, y2;
  //int w2, h2;
  double xt, yt, wt, ht;
  GBool rotate, xFlip, yFlip;
  int x, y;
  int ix, iy;
  int px1, px2, qx, dx;
  int py1, py2, qy, dy;
  Guchar pixBuf;
  int i, j;

  // get image position and size
  state->transform(0, 0, &xt, &yt);
  state->transformDelta(1, 1, &wt, &ht);
  if (wt > 0) {
    x0 = xoutRound(xt);
    w0 = xoutRound(wt);
  } else {
    x0 = xoutRound(xt + wt);
    w0 = xoutRound(-wt);
  }
  if (ht > 0) {
    y0 = xoutRound(yt);
    h0 = xoutRound(ht);
  } else {
    y0 = xoutRound(yt + ht);
    h0 = xoutRound(-ht);
  }
  state->transformDelta(1, 0, &xt, &yt);
  rotate = fabs(xt) < fabs(yt);
  if (rotate) {
    w1 = h0;
    h1 = w0;
    xFlip = ht < 0;
    yFlip = wt > 0;
  } else {
    w1 = w0;
    h1 = h0;
    xFlip = wt < 0;
    yFlip = ht > 0;
  }

  // check for tiny (zero width or height) images
  if (w0 == 0 || h0 == 0) {
    j = height * ((width + 7) / 8);
    str->reset();
    for (i = 0; i < j; ++i)
      str->getChar();
    return;
  }

  // Bresenham parameters
  px1 = w1 / width;
  px2 = w1 - px1 * width;
  py1 = h1 / height;
  py2 = h1 - py1 * height;

  // initialize the image stream
  str->resetImage(width, 1, 1);

  // first line (column)
  y = yFlip ? h1 - 1 : 0;
  qy = 0;

  if(trueColor) {
    Gulong rgb = colorTable.find_rgb(fillColor);
    Color color;
    color.r = UBYTE(rgb >> 16);
    color.g = UBYTE(rgb >> 8);
    color.b = UBYTE(rgb);

    // allocate XImage
    AGfx::Image24Ptr image(gfx.allocate_image24(w0,h0));
    /*if (x0 + w0 > pixmapW)
      w2 = pixmapW - x0;
    else
      w2 = w0;
    if (x0 < 0) {
      x2 = -x0;
      w2 += x0;
      x0 = 0;
    } else {
      x2 = 0;
    }
    if (y0 + h0 > pixmapH)
      h2 = pixmapH - y0;
    else
      h2 = h0;
    if (y0 < 0) {
      y2 = -y0;
      h2 += y0;
      y0 = 0;
    } else {
      y2 = 0;
    }
    XGetSubImage(display, pixmap, x0, y0, w2, h2, (1 << depth) - 1, ZPixmap,
		 image, x2, y2);*/
    getimage(gfx, *image, x0, y0);

    // read image
    for (i = 0; i < height; ++i) {

      // vertical (horizontal) Bresenham
      dy = py1;
      if ((qy += py2) >= height) {
	++dy;
	qy -= height;
      }

      // drop a line (column)
      if (dy == 0) {
	str->skipImageLine();

      } else {

	// first column (line)
	x = xFlip ? w1 - 1 : 0;
	qx = 0;

	// for each column (line)...
	for (j = 0; j < width; ++j) {

	  // horizontal (vertical) Bresenham
	  dx = px1;
	  if ((qx += px2) >= width) {
	    ++dx;
	    qx -= width;
	  }

	  // get image pixel
	  str->getImagePixel(&pixBuf);
	  if (invert)
	    pixBuf ^= 1;

	  // draw image pixel
	  if (dx > 0 && pixBuf == 0) {
	    if (dx == 1 && dy == 1) {
	      if (rotate)
		image->put(y, x, color);
	      else
		image->put(x, y, color);
	    } else {
	      for (ix = 0; ix < dx; ++ix) {
		for (iy = 0; iy < dy; ++iy) {
		  if (rotate)
		    image->put(yFlip ? y - iy : y + iy,
			       xFlip ? x - ix : x + ix, color);
		  else
		    image->put(xFlip ? x - ix : x + ix,
			       yFlip ? y - iy : y + iy, color);
		}
	      }
	    }
	  }

	  // next column (line)
	  if (xFlip)
	    x -= dx;
	  else
	    x += dx;
	}
      }

      // next line (column)
      if (yFlip)
	y -= dy;
      else
	y += dy;
    }

    // blit the image into the pixmap
    DB(printf("\nimagemask24(%d,%d)->(%d,%d,%d,%d)\n",width,height,x0,y0,w0,h0);)
    putimage(gfx, *image, x0, y0);
  } else {
    // Inefficient hack. I should add a get_color() memberin AGfx...
    Gulong color;
    {
	AGfx::ColorTable table(1);
	ColorEntry* p=table.data();
	Gulong rgb = colorTable.find_rgb(fillColor);
	p->color.r = UBYTE(rgb >> 16) * 0x01010101;
	p->color.g = UBYTE(rgb >> 8) * 0x01010101;
	p->color.b = UBYTE(rgb) * 0x01010101;
	gfx.get_colors(table,1);
	color = table.data()->index;
    }

    // allocate XImage
    AGfx::ImagePtr image(gfx.allocate_image(w0,h0));
    /*if (x0 + w0 > pixmapW)
      w2 = pixmapW - x0;
    else
      w2 = w0;
    if (x0 < 0) {
      x2 = -x0;
      w2 += x0;
      x0 = 0;
    } else {
      x2 = 0;
    }
    if (y0 + h0 > pixmapH)
      h2 = pixmapH - y0;
    else
      h2 = h0;
    if (y0 < 0) {
      y2 = -y0;
      h2 += y0;
      y0 = 0;
    } else {
      y2 = 0;
    }
    XGetSubImage(display, pixmap, x0, y0, w2, h2, (1 << depth) - 1, ZPixmap,
		 image, x2, y2);*/
    getimage(gfx, *image, x0, y0);

    // read image
    for (i = 0; i < height; ++i) {

      // vertical (horizontal) Bresenham
      dy = py1;
      if ((qy += py2) >= height) {
	++dy;
	qy -= height;
      }

      // drop a line (column)
      if (dy == 0) {
	str->skipImageLine();

      } else {

	// first column (line)
	x = xFlip ? w1 - 1 : 0;
	qx = 0;

	// for each column (line)...
	for (j = 0; j < width; ++j) {

	  // horizontal (vertical) Bresenham
	  dx = px1;
	  if ((qx += px2) >= width) {
	    ++dx;
	    qx -= width;
	  }

	  // get image pixel
	  str->getImagePixel(&pixBuf);
	  if (invert)
	    pixBuf ^= 1;

	  // draw image pixel
	  if (dx > 0 && pixBuf == 0) {
	    if (dx == 1 && dy == 1) {
	      if (rotate)
		image->put(y, x, color);
	      else
		image->put(x, y, color);
	    } else {
	      for (ix = 0; ix < dx; ++ix) {
		for (iy = 0; iy < dy; ++iy) {
		  if (rotate)
		    image->put(yFlip ? y - iy : y + iy,
			       xFlip ? x - ix : x + ix, color);
		  else
		    image->put(xFlip ? x - ix : x + ix,
			       yFlip ? y - iy : y + iy, color);
		}
	      }
	    }
	  }

	  // next column (line)
	  if (xFlip)
	    x -= dx;
	  else
	    x += dx;
	}
      }

      // next line (column)
      if (yFlip)
	y -= dy;
      else
	y += dy;
    }

    // blit the image into the pixmap
    DB(printf("\nimagemask(%d,%d)->(%d,%d,%d,%d)\n",width,height,x0,y0,w0,h0);)
    putimage(gfx,*image, x0, y0);
  }
}

#if 1

// Color quantization code, to display true color embedded pictures
// on colormap screens.
// Not sure where I got that algorithm from. Maybe the newsgroup
// comp.graphics.algorithm, maybe Xv, maybe somewhere else...

struct ColorDiff32 {
    LONG r, g, b;
};

struct col_hist {
  Color color;
  int value;
};

static col_hist* get_color_hist(const Color* p,int size,int maxcols,int& hist_size,UBYTE mask) {

  class hash_table {
    enum { hash_table_size = 6553 };
    struct node {
      node* next;
      col_hist ch;
    };
    static bool equal(const Color& c1,const Color& c2,UBYTE mask) {
      return (((c1.r^c2.r)|(c1.g^c2.g)|(c1.b^c2.b))&mask)==0;
    }
    static int hash(const Color& c, UBYTE m) {
      return ((c.r & m) * 33023 +
	      (c.g & m) * 30013 +
	      (c.b & m) * 27011) % hash_table_size;
    }
  public:
    class iterator {
      friend class hash_table;
    public:
      bool operator == (const iterator& i) const { return q == i.q; }
      bool operator != (const iterator& i) const { return q != i.q; }
      col_hist& operator * () const { return q->ch; }
      iterator& operator ++ () {
	q=q->next;
	if(!q) {
	  while (++p != end && !*p);
	  if (p != end)
	    q=*p;
	}
	return *this;
      }
    private:
      node** p;
      node* q;
      node** end;
    };

    hash_table() : nodes(new node* [hash_table_size]),sz(0) {
      memset(nodes,0,sizeof(*nodes)*hash_table_size);
    }
    ~hash_table() {
      for(int k = 0; k < hash_table_size; ++k) {
	node* p = nodes[k];
	while(p) {
	  node* q = p->next;
	  delete p;
	  p = q;
	}
      }
      delete [] nodes;
    }

    int size() const { return sz; }

    iterator begin() {
      iterator i;
      i.p = nodes;
      i.end = nodes + hash_table_size;
      while (!*i.p && ++i.p != i.end);
      if (i.p != i.end)
	i.q = *i.p;
      else
	i.q = NULL;
      return i;
    }

    iterator end() {
	iterator i;
	i.q = NULL;
	return i;
    }

    col_hist& get(const Color& c,UBYTE mask) {
      int h = hash(c, mask);
      for(node* hn = nodes[h]; hn; hn = hn->next)
	if(equal(c, hn->ch.color, mask))
	   return hn->ch;
      ++sz;
      node* hn = new node;
      hn->ch.color = c;
      hn->ch.value = 0;
      hn->next = nodes[h];
      nodes[h] = hn;
      return hn->ch;
    }
  private:
    node** nodes;
    int sz;
  };


  hash_table ht;

  while (--size >= 0) {
    col_hist& hn = ht.get(*p++, mask);
    ++hn.value;
    if (ht.size() > maxcols)
      return NULL;
  }

  hist_size = ht.size();
  col_hist* ch = new col_hist [hist_size];
  col_hist* q = ch;
  hash_table::iterator e(ht.end());
  for(hash_table::iterator i(ht.begin()); i != e; ++i)
      *q++ = *i;

  return ch;
}

static int redcmp(const void *p1, const void *p2) {
    const col_hist *ch1 = (const col_hist *)p1;
    const col_hist *ch2 = (const col_hist *)p2;
    return ch1->color.r - ch2->color.r;
}
static int greencmp(const void *p1, const void *p2) {
    const col_hist *ch1 = (const col_hist *)p1;
    const col_hist *ch2 = (const col_hist *)p2;
    return ch1->color.g - ch2->color.g;
}
static int bluecmp(const void *p1, const void *p2) {
    const col_hist *ch1 = (const col_hist *)p1;
    const col_hist *ch2 = (const col_hist *)p2;
    return ch1->color.b - ch2->color.b;
}


static bool median_cut(ColorEntry* cm, col_hist* ch, int colors, long sum, int newcolors) {
  struct box {
    int index;
    int colors;
    long sum;
  };

   box* boxes = new box [newcolors];
/*
 * Start with 1 big box
 */
   int nboxes = 1;
   boxes[0].index = 0;
   boxes[0].colors = colors;
   boxes[0].sum = sum;

/*
 * Split boxes
 */

  while (nboxes < newcolors) {
    int bi;
    UBYTE minr, maxr, ming, maxg, minb, maxb;

    /*
     * Find the first splitable box. Boxes are sorted by sums.
     */
    for(bi = 0; bi < nboxes && boxes[bi].colors < 2; bi++);
    if (bi == nboxes)
      break;

    int indx = boxes[bi].index;
    int clrs = boxes[bi].colors;
    long sm = boxes[bi].sum;

    /*
     * Find the boundaries of the box
     */

    minr = maxr = ch[indx].color.r;
    ming = maxg = ch[indx].color.g;
    minb = maxb = ch[indx].color.b;

    for(int i = 1; i < clrs; ++i) {
      UBYTE v = ch[i].color.r;
      if (v < minr) minr = v; else if (v > maxr) maxr = v;
      v = ch[i].color.g;
      if (v < ming) ming = v; else if (v > maxg) maxg = v;
      v = ch[i].color.b;
      if (v < minb) minb = v; else if (v > maxb) maxb = v;
    }

    /*
     * Find the largest dimension, and sort the colors in the box by
     * this component.
     */
    int rl = 77 * (maxr - minr);
    int gl = 150 * (maxg - ming);
    int bl = 29 * (maxb - minb);

    if (rl >= gl && rl >= bl)
      qsort(&ch[indx], clrs, sizeof(col_hist), redcmp);
    else if (gl >= bl)
      qsort(&ch[indx], clrs, sizeof(col_hist), greencmp);
    else
      qsort(&ch[indx], clrs, sizeof(col_hist), bluecmp);

    /*
     * Split the box.
     */

    long lsum = ch[indx].value;
    long hsum = sm / 2;
    int i;
    for (i = 1; i < clrs-1; i++) {
      if (lsum >= hsum)
	break;
      lsum += ch[indx+i].value;
    }
    sm -= lsum;

    /*
     * Add the two boxes in the right order
     */
    boxes[nboxes].sum=0;
    int a;
    for(a = bi+1; boxes[a].sum > lsum; ++a);
    --a;
    if (a != bi)
      memmove(&boxes[bi], &boxes[bi+1], (a-bi) * sizeof(box));
    boxes[a].index = indx;
    boxes[a].colors = i;
    boxes[a].sum = lsum;
    for (++a; boxes[a].sum > sm; ++a);
    if (a != nboxes)
      memmove(&boxes[a+1], &boxes[a], (nboxes-a) * sizeof(box));
    boxes[a].index = indx + i;
    boxes[a].colors = clrs - i;
    boxes[a].sum = sm;
    ++nboxes;
  }

/*
 * Find a representative color for each box.
 */

  for (int i = 0; i < nboxes; ++i) {
    long s=0, r=0, g=0, b=0;
    col_hist* p = &ch[boxes[i].index];

    for (int j = 0; j < boxes[i].colors; ++j, ++p) {
      r += p->color.r * p->value;
      g += p->color.g * p->value;
      b += p->color.b * p->value;
      s += p->value;
    }
    r /= s;
    g /= s;
    b /= s;
    cm[i].color.r = r | (r << 8) | (r << 16) | (r << 24);
    cm[i].color.g = g | (g << 8) | (g << 16) | (g << 24);
    cm[i].color.b = b | (b << 8) | (b << 16) | (b << 24);
  }

  delete [] boxes;
  return true;
}




class hash_table {
  enum { hash_table_size = 6553 };
  struct node {
    node* next;
    ColorDiff32 color;
    ColorDiff32 err;
    int index;
  };
  static int hash(const ColorDiff32& c) {
      return ((c.r >> 8) * 33023 +
	      (c.g >> 8) * 30013 +
	      (c.b >> 8) * 27011) % hash_table_size;
  }
  static ULONG sq(LONG x) { return ULONG(x * x) >> 4; }
public:
  hash_table(ColorEntry* t, int n)
    : nodes(new node* [hash_table_size]), table(t), colors(n) {
    memset(nodes,0,sizeof(*nodes)*hash_table_size);
  }
  ~hash_table() {
    for(int k = 0; k < hash_table_size; ++k) {
      node* p = nodes[k];
      while(p) {
	node* q = p->next;
	delete p;
	p = q;
      }
    }
    delete [] nodes;
  }

  int get(const ColorDiff32& c, ColorDiff32& err) {
    int h = hash(c);
    for(node* hn = nodes[h]; hn; hn = hn->next)
      if((((hn->color.r ^ c.r) |
	   (hn->color.g ^ c.g) |
	   (hn->color.b ^ c.b)) & 0xff00) == 0) {
	err = hn->err;
	return hn->index;
      }

    ULONG d = 0xffffffffL;
    ColorEntry* q = table;
    ColorEntry* e = q;
    for (int k = 0; k < colors; ++k, ++q) {
      ULONG d2 = sq(c.r - (q->color.r >> 16)) +
		 sq(c.g - (q->color.g >> 16)) +
		 sq(c.b - (q->color.b >> 16));
      if (d2 < d) {
	d = d2;
	e = q;
      }
    }
    err.r = c.r - (e->color.r >> 16);
    err.g = c.g - (e->color.g >> 16);
    err.b = c.b - (e->color.b >> 16);
    node* hn = new node;
    hn->color = c;
    hn->err = err;
    hn->index = e->index;
    hn->next = nodes[h];
    nodes[h] = hn;
    return e->index;
  }
private:
  node** nodes;
  int colors;
  ColorEntry* table;
};



void AOutputDev::drawImage(GfxState *state, Stream *str, int width,
			   int height, GfxImageColorMap *colorMap,
			   GBool inlineImg) {
  int x0, y0;                   // top left corner of image
  int w0, h0, w1, h1;           // size of image
  double xt, yt, wt, ht;
  GBool rotate, xFlip, yFlip;
  GBool dither;
  int x, y;
  int ix, iy;
  int px1, px2, qx, dx;
  int py1, py2, qy, dy;
  Guchar pixBuf[4];
  int nComps, nVals, nBits;
  int i, j;

  // get image position and size
  state->transform(0, 0, &xt, &yt);
  state->transformDelta(1, 1, &wt, &ht);
  if (wt > 0) {
    x0 = xoutRound(xt);
    w0 = xoutRound(wt);
  } else {
    x0 = xoutRound(xt + wt);
    w0 = xoutRound(-wt);
  }
  if (ht > 0) {
    y0 = xoutRound(yt);
    h0 = xoutRound(ht);
  } else {
    y0 = xoutRound(yt + ht);
    h0 = xoutRound(-ht);
  }
  state->transformDelta(1, 0, &xt, &yt);
  rotate = fabs(xt) < fabs(yt);
  if (rotate) {
    w1 = h0;
    h1 = w0;
    xFlip = ht < 0;
    yFlip = wt > 0;
  } else {
    w1 = w0;
    h1 = h0;
    xFlip = wt < 0;
    yFlip = ht > 0;
  }

  DB(printf("image(%dx%d)->(%d,%d)\n",width,height,w0,h0);)
  // set up
  nComps = colorMap->getNumPixelComps();
  nVals = width * nComps;
  nBits = colorMap->getBits();
  dither = nComps > 1 || nBits > 1;

  // check for tiny (zero width or height) images
  if (w0 == 0 || h0 == 0) {
    j = height * ((nVals * nBits + 7) / 8);
    str->reset();
    for (i = 0; i < j; ++i)
      str->getChar();
    return;
  }

  // Bresenham parameters
  px1 = w1 / width;
  px2 = w1 - px1 * width;
  py1 = h1 / height;
  py2 = h1 - py1 * height;

  // allocate the true color image
  AGfx::Image24Ptr image24(gfx.allocate_image24(w0, h0));

  // initialize the image stream
  str->resetImage(width, nComps, nBits);

  // first line (column)
  y = yFlip ? h1 - 1 : 0;
  qy = 0;

  // read image
  for (i = 0; i < height; ++i) {

    // vertical (horizontal) Bresenham
    dy = py1;
    if ((qy += py2) >= height) {
      ++dy;
      qy -= height;
    }

    // drop a line (column)
    if (dy == 0) {
      str->skipImageLine();

    } else {

      // first column (line)
      x = xFlip ? w1 - 1 : 0;
      qx = 0;

      // for each column (line)...
      for (j = 0; j < width; ++j) {

	// horizontal (vertical) Bresenham
	dx = px1;
	if ((qx += px2) >= width) {
	  ++dx;
	  qx -= width;
	}

	// get image pixel
	str->getImagePixel(pixBuf);
	GfxColor color;
	colorMap->getColor(pixBuf, &color);
	Color c;
	c.r = (UBYTE)(255 * color.getR());
	c.g = (UBYTE)(255 * color.getG());
	c.b = (UBYTE)(255 * color.getB());

	// draw image pixel
	if (dx > 0) {
	  for (iy = 0; iy < dy; ++iy) {
	    for (ix = 0; ix < dx; ++ix) {
	      if (rotate)
		image24->put(yFlip ? y - iy : y + iy,
			     xFlip ? x - ix : x + ix, c);
	      else
		image24->put(xFlip ? x - ix : x + ix,
			     yFlip ? y - iy : y + iy, c);
	    }
	  }
	}

	// next column (line)
	if (xFlip)
	  x -= dx;
	else
	  x += dx;
      }
    }

    // next line (column)
    if (yFlip)
      y -= dy;
    else
      y += dy;
  }

  if (trueColor) {
    putimage(gfx,*image24, x0, y0);
    DB(printf("\nimage24(%d,%d)->(%d,%d,%d,%d)\n",width,height,x0,y0,w0,h0);)
    return;
  }

  // compute color histogram
  const int max_colors = 32767;

  int colors;
  UBYTE mask = 255;//...
  int newColors = maxColors<2?2:maxColors;
  col_hist* ch;
  do {
    ch = get_color_hist(image24->data(), w0*h0, max_colors, colors, mask);
    mask = ~((((~mask)+1)<<1)-1);
  } while (!ch);

  // find the prefered colors
  if (colors < newColors)
    newColors = colors;
  AGfx::ColorTablePtr colorTable2(gfx.allocate_color_table(newColors));
  median_cut(colorTable2->data(), ch, colors, w0*h0, newColors);

  // allocate those colors
  gfx.get_colors(*colorTable2, newColors);
  {
    ColorEntry* p = colorTable2->data();
    for(int k = 0; k < newColors; ++k, ++p)
      colorTable.add(((p->color.r >> 8) & 0xff0000)|
		     ((p->color.g >> 16) & 0x00ff00) |
		     ((p->color.b >> 24) & 0x0000ff));
  }

  // allocate image
  AGfx::ImagePtr image(gfx.allocate_image(w0, h0));

  // allocate error diffusion accumulators
  ColorDiff32 errRight, *errDown;
  if (dither) {
    errDown = new ColorDiff32 [w0];
    memset(errDown, 0, w0*sizeof(Color32));
  } else {
    errDown = NULL;
  }

  hash_table table(colorTable2->data(), newColors);

  // first line
  Color* p = image24->data();

  // read image
  for (y = 0; y < h0; ++y) {

    // clear error accumulator
    errRight.r = errRight.g = errRight.b = 0;

    // for each column (line)...
    for (x = 0; x < w0; ++x) {

      // draw image pixel
      ColorDiff32 color1;
      color1.r = LONG(p->r << 8);
      color1.g = LONG(p->g << 8);
      color1.b = LONG(p->b << 8);
      ++p;

      if (dither) {
	color1.r += errRight.r + errDown[x].r;
	if (color1.r > 0xffff)
	  color1.r = 0xffff;
	else if (color1.r < 0)
	  color1.r = 0;
	color1.g += errRight.g + errDown[x].g;
	if (color1.g > 0xffff)
	  color1.g = 0xffff;
	else if (color1.g < 0)
	  color1.g = 0;
	color1.b += errRight.b + errDown[x].b;
	if (color1.b > 0xffff)
	  color1.b = 0xffff;
	else if (color1.b < 0)
	  color1.b = 0;
      }
      ColorDiff32 err;
      image->put(x, y, table.get(color1, err));
      if (dither) {
	errRight.r = errDown[x].r = err.r / 2;
	errRight.g = errDown[x].g = err.g / 2;
	errRight.b = errDown[x].b = err.b / 2;
      }
    }
  }

  // blit the image into the pixmap
  putimage(gfx,*image, x0, y0/*, w0, h0*/);
  DB(printf("\nimage(%d,%d)->(%d,%d,%d,%d)\n",width,height,x0,y0,w0,h0);)

  // free memory
  delete [] errDown;
}
#else

inline Gulong AOutputDev::findColor(RGBColor *x, RGBColor *err) {
  double gray;
  int r, g, b;
  Gulong pixel;

  /*if (trueColor) {
    r = xoutRound(x->r * rMul);
    g = xoutRound(x->g * gMul);
    b = xoutRound(x->b * bMul);
    pixel = ((Gulong)r << rShift) +
	    ((Gulong)g << gShift) +
	    ((Gulong)b << bShift);
    err->r = x->r - (double)r / rMul;
    err->g = x->g - (double)g / gMul;
    err->b = x->b - (double)b / bMul;
  } else if (numColors == 1) {*/
    gray = 0.299 * x->r + 0.587 * x->g + 0.114 * x->b;
    if (gray < 0.5) {
      pixel = 0;//colors[0];
      err->r = x->r;
      err->g = x->g;
      err->b = x->b;
    } else {
      pixel = 1;//colors[1];
      err->r = x->r - 1;
      err->g = x->g - 1;
      err->b = x->b - 1;
    }
  /*} else {
    r = xoutRound(x->r * (numColors - 1));
    g = xoutRound(x->g * (numColors - 1));
    b = xoutRound(x->b * (numColors - 1));
    pixel = colors[(r * numColors + g) * numColors + b];
    err->r = x->r - (double)r / (numColors - 1);
    err->g = x->g - (double)g / (numColors - 1);
    err->b = x->b - (double)b / (numColors - 1);
  }*/
  return pixel;
}

void AOutputDev::drawImage(GfxState *state, Stream *str, int width,
			   int height, GfxImageColorMap *colorMap,
			   GBool inlineImg) {
  AGfx::ImagePtr image;
  int x0, y0;                   // top left corner of image
  int w0, h0, w1, h1;           // size of image
  double xt, yt, wt, ht;
  GBool rotate, xFlip, yFlip;
  GBool dither;
  int x, y;
  int ix, iy;
  int px1, px2, qx, dx;
  int py1, py2, qy, dy;
  Guchar pixBuf[4];
  Gulong pixel;
  int nComps, nVals, nBits;
  double r1, g1, b1;
  GfxColor color;
  RGBColor color2, err;
  RGBColor *errRight, *errDown;
  int i, j;

  // get image position and size
  state->transform(0, 0, &xt, &yt);
  state->transformDelta(1, 1, &wt, &ht);
  if (wt > 0) {
    x0 = xoutRound(xt);
    w0 = xoutRound(wt);
  } else {
    x0 = xoutRound(xt + wt);
    w0 = xoutRound(-wt);
  }
  if (ht > 0) {
    y0 = xoutRound(yt);
    h0 = xoutRound(ht);
  } else {
    y0 = xoutRound(yt + ht);
    h0 = xoutRound(-ht);
  }
  state->transformDelta(1, 0, &xt, &yt);
  rotate = fabs(xt) < fabs(yt);
  if (rotate) {
    w1 = h0;
    h1 = w0;
    xFlip = ht < 0;
    yFlip = wt > 0;
  } else {
    w1 = w0;
    h1 = h0;
    xFlip = wt < 0;
    yFlip = ht > 0;
  }

  // set up
  nComps = colorMap->getNumPixelComps();
  nVals = width * nComps;
  nBits = colorMap->getBits();
  dither = nComps > 1 || nBits > 1;

  // check for tiny (zero width or height) images
  if (w0 == 0 || h0 == 0) {
    j = height * ((nVals * nBits + 7) / 8);
    str->reset();
    for (i = 0; i < j; ++i)
      str->getChar();
    return;
  }

  // Bresenham parameters
  px1 = w1 / width;
  px2 = w1 - px1 * width;
  py1 = h1 / height;
  py2 = h1 - py1 * height;

  // allocate XImage
  /*
  image = XCreateImage(display, DefaultVisual(display, screenNum),
		       depth, ZPixmap, 0, NULL, w0, h0, 8, 0);
  image->data = (char *)gmalloc(h0 * image->bytes_per_line);*/
  image = gfx.allocate_image(w0,h0);

  // allocate error diffusion accumulators
  if (dither) {
    errDown = (RGBColor *)gmalloc(w1 * sizeof(RGBColor));
    errRight = (RGBColor *)gmalloc((py1 + 1) * sizeof(RGBColor));
    for (j = 0; j < w1; ++j)
      errDown[j].r = errDown[j].g = errDown[j].b = 0;
  } else {
    errDown = NULL;
    errRight = NULL;
  }

  // initialize the image stream
  str->resetImage(width, nComps, nBits);

  // first line (column)
  y = yFlip ? h1 - 1 : 0;
  qy = 0;

  // read image
  for (i = 0; i < height; ++i) {

    // vertical (horizontal) Bresenham
    dy = py1;
    if ((qy += py2) >= height) {
      ++dy;
      qy -= height;
    }

    // drop a line (column)
    if (dy == 0) {
      str->skipImageLine();

    } else {

      // first column (line)
      x = xFlip ? w1 - 1 : 0;
      qx = 0;

      // clear error accumulator
      if (dither) {
	for (j = 0; j <= py1; ++j)
	  errRight[j].r = errRight[j].g = errRight[j].b = 0;
      }

      // for each column (line)...
      for (j = 0; j < width; ++j) {

	// horizontal (vertical) Bresenham
	dx = px1;
	if ((qx += px2) >= width) {
	  ++dx;
	  qx -= width;
	}

	// get image pixel
	str->getImagePixel(pixBuf);

	// draw image pixel
	if (dx > 0) {
	  colorMap->getColor(pixBuf, &color);
	  r1 = color.getR();
	  g1 = color.getG();
	  b1 = color.getB();
	  if (dither) {
	    pixel = 0;
	  } else {
	    color2.r = r1;
	    color2.g = g1;
	    color2.b = b1;
	    pixel = findColor(&color2, &err);
	  }
	  if (dx == 1 && dy == 1) {
	    if (dither) {
	      color2.r = r1 + errRight[0].r + errDown[x].r;
	      if (color2.r > 1)
		color2.r = 1;
	      else if (color2.r < 0)
		color2.r = 0;
	      color2.g = g1 + errRight[0].g + errDown[x].g;
	      if (color2.g > 1)
		color2.g = 1;
	      else if (color2.g < 0)
		color2.g = 0;
	      color2.b = b1 + errRight[0].b + errDown[x].b;
	      if (color2.b > 1)
		color2.b = 1;
	      else if (color2.b < 0)
		color2.b = 0;
	      pixel = findColor(&color2, &err);
	      errRight[0].r = errDown[x].r = err.r / 2;
	      errRight[0].g = errDown[x].g = err.g / 2;
	      errRight[0].b = errDown[x].b = err.b / 2;
	    }
	    if (rotate)
	      image->put(y, x, pixel);
	    else
	      image->put(x, y, pixel);
	  } else {
	    for (iy = 0; iy < dy; ++iy) {
	      for (ix = 0; ix < dx; ++ix) {
		if (dither) {
		  color2.r = r1 + errRight[iy].r +
		    errDown[xFlip ? x - ix : x + ix].r;
		  if (color2.r > 1)
		    color2.r = 1;
		  else if (color2.r < 0)
		    color2.r = 0;
		  color2.g = g1 + errRight[iy].g +
		    errDown[xFlip ? x - ix : x + ix].g;
		  if (color2.g > 1)
		    color2.g = 1;
		  else if (color2.g < 0)
		    color2.g = 0;
		  color2.b = b1 + errRight[iy].b +
		    errDown[xFlip ? x - ix : x + ix].b;
		  if (color2.b > 1)
		    color2.b = 1;
		  else if (color2.b < 0)
		    color2.b = 0;
		  pixel = findColor(&color2, &err);
		  errRight[iy].r = errDown[xFlip ? x - ix : x + ix].r =
		    err.r / 2;
		  errRight[iy].g = errDown[xFlip ? x - ix : x + ix].g =
		    err.g / 2;
		  errRight[iy].b = errDown[xFlip ? x - ix : x + ix].b =
		    err.b / 2;
		}
		if (rotate)
		  image->put(yFlip ? y - iy : y + iy,
			     xFlip ? x - ix : x + ix, pixel);
		else
		  image->put(xFlip ? x - ix : x + ix,
			     yFlip ? y - iy : y + iy, pixel);
	      }
	    }
	  }
	}

	// next column (line)
	if (xFlip)
	  x -= dx;
	else
	  x += dx;
      }
    }

    // next line (column)
    if (yFlip)
      y -= dy;
    else
      y += dy;
  }

  // blit the image into the pixmap
  gfx.put_image(*image, x0, y0/*, w0, h0*/);
  DB(printf("\nimage(%d,%d)->(%d,%d,%d,%d)\n",width,height,x0,y0,w0,h0);)

  // free memory
  gfree(errRight);
  gfree(errDown);
}
#endif

Gulong AOutputDev::findColor(GfxColor *color) {
  int r, g, b;
  Gulong pixel;

#if !defined(__HAVE_68881__) && !defined(__PPC__)
  // when compiling for 68k without fpu, I get r==256 if
  // getR()==1.0, which is wrong. Unfortunately have been
  // unable to reproduce the problem on a small snipset...
  r = int(color->getR() * 255);
  g = int(color->getG() * 255);
  b = int(color->getB() * 255);
#else
  r = xoutRound(color->getR() * 255);
  g = xoutRound(color->getG() * 255);
  b = xoutRound(color->getB() * 255);
#endif

  pixel = (((Gulong)r << 16) +
	   ((Gulong)g << 8) +
	   ((Gulong)b << 0)) & colorMask;

  Gulong c = colorTable.find(pixel);
  if (c != Gulong(-1))
      return c;
  else {
      gfx.color(Gulong(color->getR() * 0xffffffffUL + 0.5),
		Gulong(color->getG() * 0xffffffffUL + 0.5),
		Gulong(color->getB() * 0xffffffffUL + 0.5));
      return colorTable.add(pixel);
  }
#if 0
  double gray;

  if (trueColor) {
  } else if (numColors == 1) {
    gray = color->getGray();
    if (gray < 0.5)
      pixel = colors[0];
    else
      pixel = colors[1];
  } else {
    r = xoutRound(color->getR() * (numColors - 1));
    g = xoutRound(color->getG() * (numColors - 1));
    b = xoutRound(color->getB() * (numColors - 1));
#if 0 //~ this makes things worse as often as better
    // even a very light color shouldn't map to white
    if (r == numColors - 1 && g == numColors - 1 && b == numColors - 1) {
      if (color->getR() < 0.95)
	--r;
      if (color->getG() < 0.95)
	--g;
      if (color->getB() < 0.95)
	--b;
    }
#endif
    pixel = colors[(r * numColors + g) * numColors + b];
  }
  return pixel;
#endif
}

GBool AOutputDev::findText(char *s, GBool top, GBool bottom,
			   int *xMin, int *yMin, int *xMax, int *yMax) {
  double xMin1, yMin1, xMax1, yMax1;

  xMin1 = (double)*xMin;
  yMin1 = (double)*yMin;
  xMax1 = (double)*xMax;
  yMax1 = (double)*yMax;
  if (text->findText(s, top, bottom, &xMin1, &yMin1, &xMax1, &yMax1)) {
    *xMin = xoutRound(xMin1);
    *xMax = xoutRound(xMax1);
    *yMin = xoutRound(yMin1);
    *yMax = xoutRound(yMax1);
    return gTrue;
  }
  return gFalse;
}

GString *AOutputDev::getText(int xMin, int yMin, int xMax, int yMax) {
  return text->getText((double)xMin, (double)yMin,
		       (double)xMax, (double)yMax);
}