/* $TOG: bitscale.c /main/31 1997/06/09 11:21:46 barstow $ *//*Copyright (c) 1991, 1994  X ConsortiumPermission is hereby granted, free of charge, to any person obtaininga copy of this software and associated documentation files (the"Software"), to deal in the Software without restriction, includingwithout limitation the rights to use, copy, modify, merge, publish,distribute, sublicense, and/or sell copies of the Software, and topermit persons to whom the Software is furnished to do so, subject tothe following conditions:The above copyright notice and this permission notice shall be includedin all copies or substantial portions of the Software.THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESSOR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OFMERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OROTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OROTHER DEALINGS IN THE SOFTWARE.Except as contained in this notice, the name of the X Consortium shallnot be used in advertising or otherwise to promote the sale, use orother dealings in this Software without prior written authorizationfrom the X Consortium.*//* $XFree86: xc/lib/font/bitmap/bitscale.c,v 3.4.2.1 1997/06/11 12:08:40 dawes Exp $ *//* * Author:  Keith Packard, MIT X Consortium */#include "fntfilst.h"#include "bitmap.h"#ifdef _XOPEN_SOURCE#include <math.h>#else#define _XOPEN_SOURCE	/* to get prototype for hypot on some systems */#include <math.h>#undef _XOPEN_SOURCE#endif#ifndef MAX#define   MAX(a,b)    (((a)>(b)) ? a : b)#endifextern Atom MakeAtom();void bitmapUnloadScalable();enum scaleType {    atom, truncate_atom, pixel_size, point_size, resolution_x,    resolution_y, average_width, scaledX, scaledY, unscaled, fontname,    raw_ascent, raw_descent, raw_pixelsize, raw_pointsize,    raw_average_width, uncomputed};typedef struct _fontProp {    char       *name;    Atom        atom;    enum scaleType type;} fontProp;static FontPtr BitmapScaleBitmaps();static FontPtr PrinterScaleBitmaps();typedef FontPtr (*ScaleFunc) ();/* These next two arrays must be kept in step with the renderer array */ScaleFunc scale[] ={    BitmapScaleBitmaps,    BitmapScaleBitmaps,    BitmapScaleBitmaps,    BitmapScaleBitmaps,    BitmapScaleBitmaps,    BitmapScaleBitmaps,    PrinterScaleBitmaps,};static FontEntryPtr FindBestToScale();static FontEntryPtr FindPmfToScale();typedef FontEntryPtr (*FindToScale) ();FindToScale find_scale[] ={    FindBestToScale,    FindBestToScale,    FindBestToScale,    FindBestToScale,    FindBestToScale,    FindBestToScale,    FindPmfToScale,};static unsigned long fontGeneration = 0;	/* initialization flag */static fontProp fontNamePropTable[] = {    "FOUNDRY", 0, atom,    "FAMILY_NAME", 0, atom,    "WEIGHT_NAME", 0, atom,    "SLANT", 0, atom,    "SETWIDTH_NAME", 0, atom,    "ADD_STYLE_NAME", 0, atom,    "PIXEL_SIZE", 0, pixel_size,    "POINT_SIZE", 0, point_size,    "RESOLUTION_X", 0, resolution_x,    "RESOLUTION_Y", 0, resolution_y,    "SPACING", 0, atom,    "AVERAGE_WIDTH", 0, average_width,    "CHARSET_REGISTRY", 0, atom,    "CHARSET_ENCODING", 0, truncate_atom,    "FONT", 0, fontname,    "RAW_ASCENT", 0, raw_ascent,    "RAW_DESCENT", 0, raw_descent,    "RAW_PIXEL_SIZE", 0, raw_pixelsize,    "RAW_POINT_SIZE", 0, raw_pointsize,    "RAW_AVERAGE_WIDTH", 0, raw_average_width};#define TRANSFORM_POINT(matrix, x, y, dest) \	((dest)[0] = (matrix)[0] * (x) + (matrix)[2] * (y), \	 (dest)[1] = (matrix)[1] * (x) + (matrix)[3] * (y))#define CHECK_EXTENT(lsb, rsb, desc, asc, data) \	((lsb) > (data)[0] ? (lsb) = (data)[0] : 0 , \	 (rsb) < (data)[0] ? (rsb) = (data)[0] : 0, \	 (-desc) > (data)[1] ? (desc) = -(data)[1] : 0 , \	 (asc) < (data)[1] ? (asc) = (data)[1] : 0)#define NPROPS (sizeof(fontNamePropTable) / sizeof(fontProp))/* Warning: order of the next two tables is critically interdependent.   Location of "unscaled" properties at the end of fontPropTable[]   is important. */static fontProp fontPropTable[] = {    "MIN_SPACE", 0, scaledX,    "NORM_SPACE", 0, scaledX,    "MAX_SPACE", 0, scaledX,    "END_SPACE", 0, scaledX,    "AVG_CAPITAL_WIDTH", 0, scaledX,    "AVG_LOWERCASE_WIDTH", 0, scaledX,    "QUAD_WIDTH", 0, scaledX,    "FIGURE_WIDTH", 0, scaledX,    "SUPERSCRIPT_X", 0, scaledX,    "SUPERSCRIPT_Y", 0, scaledY,    "SUBSCRIPT_X", 0, scaledX,    "SUBSCRIPT_Y", 0, scaledY,    "SUPERSCRIPT_SIZE", 0, scaledY,    "SUBSCRIPT_SIZE", 0, scaledY,    "SMALL_CAP_SIZE", 0, scaledY,    "UNDERLINE_POSITION", 0, scaledY,    "UNDERLINE_THICKNESS", 0, scaledY,    "STRIKEOUT_ASCENT", 0, scaledY,    "STRIKEOUT_DESCENT", 0, scaledY,    "CAP_HEIGHT", 0, scaledY,    "X_HEIGHT", 0, scaledY,    "ITALIC_ANGLE", 0, unscaled,    "RELATIVE_SETWIDTH", 0, unscaled,    "RELATIVE_WEIGHT", 0, unscaled,    "WEIGHT", 0, unscaled,    "DESTINATION", 0, unscaled,    "PCL_FONT_NAME", 0, unscaled,    "_ADOBE_POSTSCRIPT_FONTNAME", 0, unscaled};static fontProp rawFontPropTable[] = {    "RAW_MIN_SPACE", 0, 0,    "RAW_NORM_SPACE", 0, 0,    "RAW_MAX_SPACE", 0, 0,    "RAW_END_SPACE", 0, 0,    "RAW_AVG_CAPITAL_WIDTH", 0, 0,    "RAW_AVG_LOWERCASE_WIDTH", 0, 0,    "RAW_QUAD_WIDTH", 0, 0,    "RAW_FIGURE_WIDTH", 0, 0,    "RAW_SUPERSCRIPT_X", 0, 0,    "RAW_SUPERSCRIPT_Y", 0, 0,    "RAW_SUBSCRIPT_X", 0, 0,    "RAW_SUBSCRIPT_Y", 0, 0,    "RAW_SUPERSCRIPT_SIZE", 0, 0,    "RAW_SUBSCRIPT_SIZE", 0, 0,    "RAW_SMALL_CAP_SIZE", 0, 0,    "RAW_UNDERLINE_POSITION", 0, 0,    "RAW_UNDERLINE_THICKNESS", 0, 0,    "RAW_STRIKEOUT_ASCENT", 0, 0,    "RAW_STRIKEOUT_DESCENT", 0, 0,    "RAW_CAP_HEIGHT", 0, 0,    "RAW_X_HEIGHT", 0, 0,};static voidinitFontPropTable(){    int         i;    fontProp   *t;    i = sizeof(fontNamePropTable) / sizeof(fontProp);    for (t = fontNamePropTable; i; i--, t++)	t->atom = MakeAtom(t->name, (unsigned) strlen(t->name), TRUE);    i = sizeof(fontPropTable) / sizeof(fontProp);    for (t = fontPropTable; i; i--, t++)	t->atom = MakeAtom(t->name, (unsigned) strlen(t->name), TRUE);    i = sizeof(rawFontPropTable) / sizeof(fontProp);    for (t = rawFontPropTable; i; i--, t++)	t->atom = MakeAtom(t->name, (unsigned) strlen(t->name), TRUE);}static FontEntryPtrGetScalableEntry (fpe, name)    FontPathElementPtr	fpe;    FontNamePtr		name;{    FontDirectoryPtr	dir;    dir = (FontDirectoryPtr) fpe->private;    return FontFileFindNameInDir (&dir->scalable, name);}static doubleget_matrix_horizontal_component(matrix)    double *matrix;{    return hypot(matrix[0], matrix[1]);}static doubleget_matrix_vertical_component(matrix)    double *matrix;{    return hypot(matrix[2], matrix[3]);}static BoolComputeScaleFactors(from, to, dx, dy, sdx, sdy, rescale_x)    FontScalablePtr from,                to;    double     *dx, *sdx,               *dy, *sdy,	       *rescale_x;{    double srcpixelset, destpixelset, srcpixel, destpixel;    srcpixelset = get_matrix_horizontal_component(from->pixel_matrix);    destpixelset = get_matrix_horizontal_component(to->pixel_matrix);    srcpixel = get_matrix_vertical_component(from->pixel_matrix);    destpixel = get_matrix_vertical_component(to->pixel_matrix);    if (srcpixelset >= EPS)    {	*dx = destpixelset / srcpixelset;	*sdx = 1000.0 / srcpixelset;    }    else	*sdx = *dx = 0;    *rescale_x = 1.0;    /* If client specified a width, it overrides setsize; in this       context, we interpret width as applying to the font before any       rotation, even though that's not what is ultimately returned in       the width field. */    if (from->width > 0 && to->width > 0 && fabs(*dx) > EPS)    {	double rescale = (double)to->width / (double)from->width;	/* If the client specified a transformation matrix, the rescaling	   for width does *not* override the setsize.  Instead, just check	   for consistency between the setsize from the matrix and the	   setsize that would result from rescaling according to the width.	   This assumes (perhaps naively) that the width is correctly	   reported in the name.  As an interesting side effect, this test	   may result in choosing a different source bitmap (one that	   scales consistently between the setsize *and* the width) than it	   would choose if a width were not specified.  Sort of a hidden	   multiple-master functionality. */	if ((to->values_supplied & PIXELSIZE_MASK) == PIXELSIZE_ARRAY ||	    (to->values_supplied & POINTSIZE_MASK) == POINTSIZE_ARRAY)	{	    /* Reject if resulting width difference is >= 1 pixel */	    if (fabs(rescale * from->width - *dx * from->width) >= 10)		return FALSE;	}	else	{	    *rescale_x = rescale/(*dx);	    *dx = rescale;	}    }    if (srcpixel >= EPS)    {	*dy = destpixel / srcpixel;	*sdy = 1000.0 / srcpixel;    }    else	*sdy = *dy = 0;    return TRUE;}/* favor enlargement over reduction because of aliasing resulting   from reduction */#define SCORE(m,s) \if (m >= 1.0) { \    if (m == 1.0) \        score += (16 * s); \    else if (m == 2.0) \        score += (4 * s); \    else \        score += (int)(((double)(3 * s)) / m); \} else { \        score += (int)(((double)(2 * s)) * m); \}/* don't need to favor enlargement when looking for bitmap that can   be used unscalable */#define SCORE2(m,s) \if (m >= 1.0) \    score += (int)(((double)(8 * s)) / m); \else \    score += (int)(((double)(8 * s)) * m);static FontEntryPtrFindBestToScale(fpe, entry, vals, best, dxp, dyp, sdxp, sdyp, fpep)    FontPathElementPtr	fpe;    FontEntryPtr	entry;    FontScalablePtr	vals,			best;    double		*dxp, *sdxp,			*dyp, *sdyp;    FontPathElementPtr	*fpep;{    FontScalableRec temp;    int		    source, i;    int		    best_score, best_unscaled_score,		    score;    double	    dx, sdx, dx_amount,		    dy, sdy, dy_amount,		    best_dx, best_sdx, best_dx_amount,		    best_dy, best_sdy, best_dy_amount,		    best_unscaled_sdx, best_unscaled_sdy,		    rescale_x, best_rescale_x,		    best_unscaled_rescale_x;    FontEntryPtr    zero;    FontNameRec	    zeroName;    char	    zeroChars[MAXFONTNAMELEN];    FontDirectoryPtr	dir;    FontScaledPtr   scaled;    FontScalableExtraPtr   extra;    FontScaledPtr   best_scaled, best_unscaled;    FontPathElementPtr	best_fpe, best_unscaled_fpe;    FontEntryPtr    bitmap = NULL;    FontEntryPtr    result;    int		    aliascount = 20;    FontPathElementPtr	bitmap_fpe;    FontNameRec	    xlfdName;    /* find the best match */    rescale_x = 1.0;    best_scaled = 0;    best_score = 0;    best_unscaled = 0;    best_unscaled_score = -1;    memcpy (zeroChars, entry->name.name, entry->name.length);    zeroChars[entry->name.length] = '\0';    zeroName.name = zeroChars;    FontParseXLFDName (zeroChars, &temp, FONT_XLFD_REPLACE_ZERO);    zeroName.length = strlen (zeroChars);    zeroName.ndashes = entry->name.ndashes;    xlfdName.name = vals->xlfdName;    xlfdName.length = strlen(xlfdName.name);    xlfdName.ndashes = FontFileCountDashes(xlfdName.name, xlfdName.length);    restart_bestscale_loop: ;    /*     * Look through all the registered bitmap sources for     * the same zero name as ours; entries along that one     * can be scaled as desired.     */    for (source = 0; source < FontFileBitmapSources.count; source++)    {	/* There might already be a bitmap that satisfies the request	   but didn't have a zero name that was found by the scalable	   font matching logic.  Keep track if there is.  */	if (bitmap == NULL && vals->xlfdName != NULL)	{	    bitmap_fpe = FontFileBitmapSources.fpe[source];	    dir = (FontDirectoryPtr) bitmap_fpe->private;	    bitmap = FontFileFindNameInDir (&dir->nonScalable, &xlfdName);	    if (bitmap && bitmap->type != FONT_ENTRY_BITMAP)	    {		if (bitmap->type == FONT_ENTRY_ALIAS && aliascount > 0)		{		    aliascount--;		    xlfdName.name = bitmap->u.alias.resolved;		    xlfdName.length = strlen(xlfdName.name);		    xlfdName.ndashes = FontFileCountDashes(xlfdName.name,							   xlfdName.length);		    bitmap = NULL;		    goto restart_bestscale_loop;		}		else		    bitmap = NULL;	    }	}	if (FontFileBitmapSources.fpe[source] == fpe)	    zero = entry;	else	{	    dir = (FontDirectoryPtr) FontFileBitmapSources.fpe[source]->private;	    zero = FontFileFindNameInDir (&dir->scalable, &zeroName);	    if (!zero)		continue;	}	extra = zero->u.scalable.extra;	for (i = 0; i < extra->numScaled; i++)	{	    FontScalableRec tmpvals;	    scaled = &extra->scaled[i];	    if (!scaled->bitmap)		continue;	    if (!ComputeScaleFactors(&scaled->vals, vals, &dx, &dy, &sdx, &sdy,				     &rescale_x))		continue;	    score = 0;	    dx_amount = dx;	    dy_amount = dy;	    SCORE(dy_amount, 10);	    SCORE(dx_amount, 1);	    if ((score > best_score) ||		    ((score == best_score) &&		     ((dy_amount < best_dy_amount) || 		      ((dy_amount == best_dy_amount) && 		       (dx_amount < best_dx_amount))))) 	    {		best_fpe = FontFileBitmapSources.fpe[source];	    	best_scaled = scaled;	    	best_score = score;	    	best_dx = dx;	    	best_dy = dy;	    	best_sdx = sdx;	    	best_sdy = sdy;	    	best_dx_amount = dx_amount;	    	best_dy_amount = dy_amount;		best_rescale_x = rescale_x;	    }	    /* Is this font a candidate for use without ugly rescaling? */	    if (fabs(dx) > EPS && fabs(dy) > EPS &&		fabs(vals->pixel_matrix[0] * rescale_x -		     scaled->vals.pixel_matrix[0]) < 1 &&		fabs(vals->pixel_matrix[1] * rescale_x -		     scaled->vals.pixel_matrix[1]) < EPS &&		fabs(vals->pixel_matrix[2] -		     scaled->vals.pixel_matrix[2]) < EPS &&		fabs(vals->pixel_matrix[3] -		     scaled->vals.pixel_matrix[3]) < 1)	    {		/* Yes.  The pixel sizes are close on the diagonal and		   extremely close off the diagonal. */		score = 0;		SCORE2(vals->pixel_matrix[3] /		       scaled->vals.pixel_matrix[3], 10);		SCORE2(vals->pixel_matrix[0] * rescale_x /		       scaled->vals.pixel_matrix[0], 1);		if (score > best_unscaled_score)		{		    best_unscaled_fpe = FontFileBitmapSources.fpe[source];	    	    best_unscaled = scaled;	    	    best_unscaled_sdx = sdx / dx;	    	    best_unscaled_sdy = sdy / dy;		    best_unscaled_score = score;