git.sesse.net Git - rdpsrv/blob - Xserver/lib/font/Type1/spaces.c

   1 /* $XConsortium: spaces.c,v 1.8 95/06/08 23:20:39 gildea Exp $ */
   2 /* Copyright International Business Machines, Corp. 1991
   3  * All Rights Reserved
   4  * Copyright Lexmark International, Inc. 1991
   5  * All Rights Reserved
   6  *
   7  * License to use, copy, modify, and distribute this software and its
   8  * documentation for any purpose and without fee is hereby granted,
   9  * provided that the above copyright notice appear in all copies and that
  10  * both that copyright notice and this permission notice appear in
  11  * supporting documentation, and that the name of IBM or Lexmark not be
  12  * used in advertising or publicity pertaining to distribution of the
  13  * software without specific, written prior permission.
  14  *
  15  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
  16  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
  18  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
  19  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
  20  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
  21  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
  22  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
  23  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  24  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  25  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  26  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
  27  * THIS SOFTWARE.
  28  */
  29  /* SPACES   CWEB         V0021 ********                             */
  30 /*
  31 :h1 id=spaces.SPACES Module - Handles Coordinate Spaces
  32
  33 This module is responsible for handling the TYPE1IMAGER "XYspace" object.
  34
  35 &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
  36
  37
  38 :h3.Include Files
  39 */
  40 #include "objects.h"
  41 #include "spaces.h"
  42 #include "paths.h"
  43 #include "pictures.h"
  44 #include "fonts.h"
  45 #include "arith.h"
  46 #include "trig.h"
  47
  48 static void FindFfcn();
  49 static void FindIfcn();
  50 /*
  51 :h3.Entry Points Provided to the TYPE1IMAGER User
  52 */
  53
  54 /*SHARED LINE(S) ORIGINATED HERE*/
  55
  56 /*
  57 :h3.Entry Points Provided to Other Modules
  58 */
  59
  60 /*
  61 In addition, other modules call the SPACES module through function
  62 vectors in the "XYspace" structure.  The entry points accessed that
  63 way are "FConvert()", "IConvert()", and "ForceFloat()".
  64 */
  65
  66 /*SHARED LINE(S) ORIGINATED HERE*/
  67 /*
  68 :h3.Macros and Typedefs Provided to Other Modules
  69
  70 :h4.Duplicating and Killing Spaces
  71
  72 Destroying XYspaces is so simple we can do it with a
  73 macro:
  74 */
  75
  76 /*SHARED LINE(S) ORIGINATED HERE*/
  77 /*
  78 On the other hand, duplicating XYspaces is slightly more difficult
  79 because of the need to keep a unique ID in the space, see
  80 :hdref refid=dupspace..
  81
  82 :h4.Fixed Point Pel Representation
  83
  84 We represent pel positions with fixed point numbers.  This does NOT
  85 mean integer, but truly means fixed point, with a certain number
  86 of binary digits (FRACTBITS) representing the fractional part of the
  87 pel.
  88 */
  89
  90 /*SHARED LINE(S) ORIGINATED HERE*/
  91 /*
  92 :h2.Data Structures for Coordinate Spaces and Points
  93 */
  94 /*
  95 :h3 id=matrix.Matrices
  96
  97 TYPE1IMAGER uses 2x2 transformation matrices.  We'll use C notation for
  98 such a matrix (M[2][2]), the first index being rows, the second columns.
  99 */
 100
 101 /*
 102 :h3.The "doublematrix" Structure
 103
 104 We frequently find it desirable to store both a matrix and its
 105 inverse.  We store these in a "doublematrix" structure.
 106 */
 107
 108 /*SHARED LINE(S) ORIGINATED HERE*/
 109
 110 /*
 111 :h3.The "XYspace" Structure
 112
 113 The XYspace structure represents the XYspace object.
 114 */
 115
 116 /*SHARED LINE(S) ORIGINATED HERE*/
 117 #define    RESERVED  10      /* 'n' IDs are reserved for invalid & immortal spaces */
 118 /*
 119 */
 120 #define    NEXTID    ((SpaceID < RESERVED) ? (SpaceID = RESERVED) : ++SpaceID)
 121
 122 static unsigned int SpaceID = 1;
 123
 124 struct XYspace *CopySpace(S)
 125        register struct XYspace *S;
 126 {
 127        S = (struct XYspace *)Allocate(sizeof(struct XYspace), S, 0);
 128        S->ID = NEXTID;
 129        return(S);
 130 }
 131 /*
 132 :h3.The "fractpoint" Structure
 133
 134 A fractional point is just a "fractpel" x and y:
 135 */
 136
 137 /*SHARED LINE(S) ORIGINATED HERE*/
 138
 139 /*
 140 :h3.Lazy Evaluation of Matrix Inverses
 141
 142 Calculating the inverse of a matrix is somewhat involved, and we usually
 143 do not need them.  So, we flag whether or not the space has the inverse
 144 already calculated:
 145 */
 146
 147 #define    HASINVERSE(flag)   ((flag)&0x80)
 148
 149 /*
 150 The following macro forces a space to have an inverse:
 151 */
 152
 153 #define    CoerceInverse(S)   if (!HASINVERSE((S)->flag)) { \
 154     MatrixInvert((S)->tofract.normal, (S)->tofract.inverse); (S)->flag |= HASINVERSE(ON); }
 155 /*
 156 :h3.IDENTITY Space
 157
 158 IDENTITY space is (logically) the space corresponding to the identity
 159 transformation matrix.  However, since all our transformation matrices
 160 have a common FRACTFLOAT scale factor to convert to 'fractpel's, that
 161 is actually what we store in 'tofract' matrix of IDENTITY:
 162 */
 163
 164 static struct XYspace identity = { SPACETYPE, ISPERMANENT(ON) + ISIMMORTAL(ON)
 165                         + HASINVERSE(ON), 2, /* added 3-26-91 PNM */
 166                         NULL, NULL,
 167                         NULL, NULL, NULL, NULL,
 168                         INVALIDID + 1, 0,
 169                         FRACTFLOAT, 0.0, 0.0, FRACTFLOAT,
 170                         1.0/FRACTFLOAT, 0.0, 0.0, 1.0/FRACTFLOAT,
 171                         0, 0, 0, 0 };
 172 struct XYspace *IDENTITY = &identity;
 173
 174 /*
 175 */
 176 #define  MAXCONTEXTS   16
 177
 178 static struct doublematrix contexts[MAXCONTEXTS];
 179
 180 #ifdef notdef
 181
 182 static int nextcontext = 1;
 183
 184 /*SHARED LINE(S) ORIGINATED HERE*/
 185
 186 #ifdef __STDC__
 187 #define   pointer          void *
 188 #else
 189 #define   pointer          char *
 190 #endif
 191
 192 /*
 193 :h3.FindDeviceContext() - Find the Context Given a Device
 194
 195 This routine, given a device, returns the index of the device's
 196 transformation matrix in the context array.  If it cannot find it,
 197 it will allocate a new array entry and fill it out.
 198 */
 199
 200 static int FindDeviceContext(device)
 201        pointer device;       /* device token                                 */
 202 {
 203        double M[2][2];       /* temporary matrix                             */
 204        float Xres,Yres;      /* device  resolution                           */
 205        int orient = -1;      /* device orientation                           */
 206        int rc = -1;          /* return code for QueryDeviceState             */
 207
 208        if (rc != 0)          /* we only bother with this check once          */
 209                abort("Context:  QueryDeviceState didn't work");
 210
 211        M[0][0] = M[1][0] = M[0][1] = M[1][1] = 0.0;
 212
 213        switch (orient) {
 214            case 0:
 215                M[0][0] = Xres;  M[1][1] = -Yres;
 216                break;
 217            case 1:
 218                M[1][0] = Yres;  M[0][1] = Xres;
 219                break;
 220            case 2:
 221                M[0][0] = -Xres;  M[1][1] = Yres;
 222                break;
 223            case 3:
 224                M[1][0] = -Yres;  M[0][1] = -Xres;
 225                break;
 226            default:
 227                abort("QueryDeviceState returned invalid orientation");
 228        }
 229        return(FindContext(M));
 230 }
 231
 232 /*
 233 :h3.FindContext() - Find the Context Given a Matrix
 234
 235 This routine, given a matrix, returns the index of that matrix matrix in
 236 the context array.  If it cannot find it, it will allocate a new array
 237 entry and fill it out.
 238 */
 239
 240 int FindContext(M)
 241        double M[2][2];       /* array to search for                          */
 242 {
 243        register int i;       /* loop variable for search                     */
 244        for (i=0; i < nextcontext; i++)
 245                if (M[0][0] == contexts[i].normal[0][0] && M[1][0] == contexts[i].normal[1][0]
 246                    && M[0][1] == contexts[i].normal[0][1] && M[1][1] == contexts[i].normal[1][1])
 247                        break;
 248
 249        if (i >= nextcontext) {
 250                if (i >= MAXCONTEXTS)
 251                        abort("Context:  out of them");
 252                LONGCOPY(contexts[i].normal, M, sizeof(contexts[i].normal));
 253                MatrixInvert(M, contexts[i].inverse);
 254                nextcontext++;
 255        }
 256
 257        return(i);
 258 }
 259
 260 /*
 261 :h3.Context() - Create a Coordinate Space for a Device
 262
 263 This user operator is implemented by first finding the device context
 264 array index, then transforming IDENTITY space to create an appropriate
 265 cooridnate space.
 266 */
 267
 268 struct XYspace *Context(device, units)
 269        pointer device;       /* device token                                 */
 270        double units;         /* multiples of one inch                        */
 271 {
 272        double M[2][2];       /* device transformation matrix                 */
 273        register int n;       /* will hold device context number              */
 274        register struct XYspace *S;  /* XYspace constructed                   */
 275
 276        IfTrace2((MustTraceCalls),"Context(%x, %f)\n", device, &units);
 277
 278        ARGCHECK((device == NULL), "Context of NULLDEVICE not allowed",
 279                     NULL, IDENTITY, (0), struct XYspace *);
 280        ARGCHECK((units == 0.0), "Context: bad units", NULL, IDENTITY, (0), struct XYspace *);
 281
 282        n = FindDeviceContext(device);
 283
 284        LONGCOPY(M, contexts[n].normal, sizeof(M));
 285
 286        M[0][0] *= units;
 287        M[0][1] *= units;
 288        M[1][0] *= units;
 289        M[1][1] *= units;
 290
 291        S = (struct XYspace *)Xform(IDENTITY, M);
 292
 293        S->context = n;
 294        return(S);
 295 }
 296 #endif
 297
 298 /*
 299 :h3.ConsiderContext() - Adjust a Matrix to Take Out Device Transform
 300
 301 Remember, we have :f/x times U times D/ and :f/M/ and and we want :f/x
 302 times U times M times D/.  An easy way to do this is to calculate
 303 :f/D sup <-1> times M times D/, because:
 304 :formula.
 305 x times U times D times D sup <-1> times M times D = x times U times M times D
 306 :formula.
 307 So this subroutine, given an :f/M/and an object, finds the :f/D/ for that
 308 object and modifies :f/M/ so it is :f/D sup <-1> times M times D/.
 309 */
 310
 311 static void ConsiderContext(obj, M)
 312        register struct xobject *obj;  /* object to be transformed            */
 313        register double M[2][2];    /* matrix (may be changed)                */
 314 {
 315        register int context; /* index in contexts array                      */
 316
 317        if (obj == NULL) return;
 318
 319        if (ISPATHTYPE(obj->type)) {
 320                struct segment *path = (struct segment *) obj;
 321
 322                context = path->context;
 323        }
 324        else if (obj->type == SPACETYPE) {
 325                struct XYspace *S = (struct XYspace *) obj;
 326
 327                context = S->context;
 328        }
 329        else if (obj->type == PICTURETYPE) {
 330
 331        }
 332        else
 333                context = NULLCONTEXT;
 334
 335        if (context != NULLCONTEXT) {
 336                MatrixMultiply(contexts[context].inverse, M, M);
 337                MatrixMultiply(M, contexts[context].normal, M);
 338        }
 339 }
 340
 341 /*
 342 :h2.Conversion from User's X,Y to "fractpel" X,Y
 343
 344 When the user is building paths (lines, moves, curves, etc.) he passes
 345 the control points (x,y) for the paths together with an XYspace.  We
 346 must convert from the user's (x,y) to our internal representation
 347 which is in pels (fractpels, actually).  This involves transforming
 348 the user's (x,y) under the coordinate space transformation.  It is
 349 important that we do this quickly.  So, we store pointers to different
 350 conversion functions right in the XYspace structure.  This allows us
 351 to have simpler special case functions for the more commonly
 352 encountered types of transformations.
 353
 354 :h3.Convert(), IConvert(), and ForceFloat() - Called Through "XYspace" Structure
 355
 356 These are functions that fit in the "convert" and "iconvert" function
 357 pointers in the XYspace structure.  They call the "xconvert", "yconvert",
 358 "ixconvert", and "iyconvert" as appropriate to actually do the work.
 359 These secondary routines come in many flavors to handle different
 360 special cases as quickly as possible.
 361 */
 362
 363 static void FXYConvert(pt, S, x, y)
 364        register struct fractpoint *pt;  /* point to set                      */
 365        register struct XYspace *S;  /* relevant coordinate space             */
 366        register double x,y;  /* user's coordinates of point                  */
 367 {
 368        pt->x = (*S->xconvert)(S->tofract.normal[0][0], S->tofract.normal[1][0], x, y);
 369        pt->y = (*S->yconvert)(S->tofract.normal[0][1], S->tofract.normal[1][1], x, y);
 370 }
 371
 372 static void IXYConvert(pt, S, x, y)
 373        register struct fractpoint *pt;  /* point to set                      */
 374        register struct XYspace *S;  /* relevant coordinate space             */
 375        register long x,y;    /* user's coordinates of point                  */
 376 {
 377        pt->x = (*S->ixconvert)(S->itofract[0][0], S->itofract[1][0], x, y);
 378        pt->y = (*S->iyconvert)(S->itofract[0][1], S->itofract[1][1], x, y);
 379 }
 380
 381 /*
 382 ForceFloat is a substitute for IConvert(), when we just do not have
 383 enough significant digits in the coefficients to get high enough
 384 precision in the answer with fixed point arithmetic.  So, we force the
 385 integers to floats, and do the arithmetic all with floats:
 386 */
 387
 388 static void ForceFloat(pt, S, x, y)
 389        register struct fractpoint *pt;  /* point to set                      */
 390        register struct XYspace *S;  /* relevant coordinate space             */
 391        register long x,y;    /* user's coordinates of point                  */
 392 {
 393        (*S->convert)(pt, S, (double) x, (double) y);
 394 }
 395
 396 /*
 397 :h3.FXYboth(), FXonly(), FYonly() - Floating Point Conversion
 398
 399 These are the routines we use when the user has given us floating
 400 point numbers for x and y. FXYboth() is the general purpose routine;
 401 FXonly() and FYonly() are special cases when one of the coefficients
 402 is 0.0.
 403 */
 404
 405 static fractpel FXYboth(cx, cy, x, y)
 406        register double cx,cy;  /* x and y coefficients                       */
 407        register double x,y;  /* user x,y                                     */
 408 {
 409        register double r;    /* temporary float                              */
 410
 411        r = x * cx + y * cy;
 412        return((fractpel) r);
 413 }
 414
 415 /*ARGSUSED*/
 416 static fractpel FXonly(cx, cy, x, y)
 417        register double cx,cy;  /* x and y coefficients                       */
 418        register double x,y;  /* user x,y                                     */
 419 {
 420        register double r;    /* temporary float                              */
 421
 422        r = x * cx;
 423        return((fractpel) r);
 424 }
 425
 426 /*ARGSUSED*/
 427 static fractpel FYonly(cx, cy, x, y)
 428        register double cx,cy;  /* x and y coefficients                       */
 429        register double x,y;  /* user x,y                                     */
 430 {
 431        register double r;    /* temporary float                              */
 432
 433        r = y * cy;
 434        return((fractpel) r);
 435 }
 436
 437 /*
 438 :h3.IXYboth(), IXonly(), IYonly() - Simple Integer Conversion
 439
 440 These are the routines we use when the user has given us integers for
 441 x and y, and the coefficients have enough significant digits to
 442 provide precise answers with only "long" (32 bit?) multiplication.
 443 IXYboth() is the general purpose routine; IXonly() and IYonly() are
 444 special cases when one of the coefficients is 0.
 445 */
 446
 447 static fractpel IXYboth(cx, cy, x, y)
 448        register fractpel cx,cy;  /* x and y coefficients                     */
 449        register long x,y;    /* user x,y                                     */
 450 {
 451        return(x * cx + y * cy);
 452 }
 453
 454 /*ARGSUSED*/
 455 static fractpel IXonly(cx, cy, x, y)
 456        register fractpel cx,cy;  /* x and y coefficients                     */
 457        register long x,y;    /* user x,y                                     */
 458 {
 459        return(x * cx);
 460 }
 461
 462 /*ARGSUSED*/
 463 static fractpel IYonly(cx, cy, x, y)
 464        register fractpel cx,cy;  /* x and y coefficients                     */
 465        register long x,y;    /* user x,y                                     */
 466 {
 467        return(y * cy);
 468 }
 469
 470
 471 /*
 472 :h3.FPXYboth(), FPXonly(), FPYonly() - More Involved Integer Conversion
 473
 474 These are the routines we use when the user has given us integers for
 475 x and y, but the coefficients do not have enough significant digits to
 476 provide precise answers with only "long" (32 bit?)  multiplication.
 477 We have increased the number of significant bits in the coefficients
 478 by FRACTBITS; therefore we must use "double long" (64 bit?)
 479 multiplication by calling FPmult().  FPXYboth() is the general purpose
 480 routine; FPXonly() and FPYonly() are special cases when one of the
 481 coefficients is 0.
 482
 483 Note that it is perfectly possible for us to calculate X with the
 484 "FP" method and Y with the "I" method, or vice versa.  It all depends
 485 on how the functions in the XYspace structure are filled out.
 486 */
 487
 488 static fractpel FPXYboth(cx, cy, x, y)
 489        register fractpel cx,cy;  /* x and y coefficients                     */
 490        register long x,y;    /* user x,y                                     */
 491 {
 492        return( FPmult(x, cx) + FPmult(y, cy) );
 493 }
 494
 495 /*ARGSUSED*/
 496 static fractpel FPXonly(cx, cy, x, y)
 497        register fractpel cx,cy;  /* x and y coefficients                     */
 498        register long x,y;    /* user x,y                                     */
 499 {
 500        return( FPmult(x, cx) );
 501 }
 502
 503 /*ARGSUSED*/
 504 static fractpel FPYonly(cx, cy, x, y)
 505        register fractpel cx,cy;  /* x and y coefficients                     */
 506        register long x,y;    /* user x,y                                     */
 507 {
 508        return( FPmult(y, cy) );
 509 }
 510
 511
 512
 513 /*
 514 :h3.FillOutFcns() - Determine the Appropriate Functions to Use for Conversion
 515
 516 This function fills out the "convert" and "iconvert" function pointers
 517 in an XYspace structure, and also fills the "helper"
 518 functions that actually do the work.
 519 */
 520
 521 static void FillOutFcns(S)
 522        register struct XYspace *S;  /* functions will be set in this structure */
 523 {
 524        S->convert = FXYConvert;
 525        S->iconvert = IXYConvert;
 526
 527        FindFfcn(S->tofract.normal[0][0], S->tofract.normal[1][0], &S->xconvert);
 528        FindFfcn(S->tofract.normal[0][1], S->tofract.normal[1][1], &S->yconvert);
 529        FindIfcn(S->tofract.normal[0][0], S->tofract.normal[1][0],
 530                 &S->itofract[0][0], &S->itofract[1][0], &S->ixconvert);
 531        FindIfcn(S->tofract.normal[0][1], S->tofract.normal[1][1],
 532                 &S->itofract[0][1], &S->itofract[1][1], &S->iyconvert);
 533
 534        if (S->ixconvert == NULL || S->iyconvert == NULL)
 535                 S->iconvert = ForceFloat;
 536 }
 537
 538 /*
 539 :h4.FindFfcn() - Subroutine of FillOutFcns() to Fill Out Floating Functions
 540
 541 This function tests for the special case of one of the coefficients
 542 being zero:
 543 */
 544
 545 static void FindFfcn(cx, cy, fcnP)
 546        register double cx,cy;  /* x and y coefficients                       */
 547        register fractpel (**fcnP)();  /* pointer to function to set          */
 548 {
 549        if (cx == 0.0)
 550                *fcnP = FYonly;
 551        else if (cy == 0.0)
 552                *fcnP = FXonly;
 553        else
 554                *fcnP = FXYboth;
 555 }
 556
 557 /*
 558 :h4.FindIfcn() - Subroutine of FillOutFcns() to Fill Out Integer Functions
 559
 560 There are two types of integer functions, the 'I' type and the 'FP' type.
 561 We use the I type functions when we are satisfied with simple integer
 562 arithmetic.  We used the FP functions when we feel we need higher
 563 precision (but still fixed point) arithmetic.  If all else fails,
 564 we store a NULL indicating that this we should do the conversion in
 565 floating point.
 566 */
 567
 568 static void FindIfcn(cx, cy, icxP, icyP, fcnP)
 569        register double cx,cy;  /* x and y coefficients                       */
 570        register fractpel *icxP,*icyP;  /* fixed point coefficients to set    */
 571        register fractpel (**fcnP)();  /* pointer to function to set          */
 572 {
 573        register fractpel imax;  /* maximum of cx and cy                      */
 574
 575        *icxP = cx;
 576        *icyP = cy;
 577
 578        if (cx != (float) (*icxP) || cy != (float) (*icyP)) {
 579 /*
 580 At this point we know our integer approximations of the coefficients
 581 are not exact.  However, we will still use them if the maximum
 582 coefficient will not fit in a 'fractpel'.   Of course, we have little
 583 choice at that point, but we haven't lost that much precision by
 584 staying with integer arithmetic.  We have enough significant digits
 585 so that
 586 any error we introduce is less than one part in 2:sup/16/.
 587 */
 588
 589                imax = MAX(ABS(*icxP), ABS(*icyP));
 590                if (imax < (fractpel) (1<<(FRACTBITS-1)) ) {
 591 /*
 592 At this point we know our integer approximations just do not have
 593 enough significant digits for accuracy.  We will add FRACTBITS
 594 significant digits to the coefficients (by multiplying them by
 595 1<<FRACTBITS) and go to the "FP" form of the functions.  First, we
 596 check to see if we have ANY significant digits at all (that is, if
 597 imax == 0).  If we don't, we suspect that adding FRACTBITS digits
 598 won't help, so we punt the whole thing.
 599 */
 600                        if (imax == 0) {
 601                                *fcnP = NULL;
 602                                return;
 603                        }
 604                        cx *= FRACTFLOAT;
 605                        cy *= FRACTFLOAT;
 606                        *icxP = cx;
 607                        *icyP = cy;
 608                        *fcnP = FPXYboth;
 609                }
 610                else
 611                        *fcnP = IXYboth;
 612        }
 613        else
 614                *fcnP = IXYboth;
 615 /*
 616 Now we check for special cases where one coefficient is zero (after
 617 integer conversion):
 618 */
 619        if (*icxP == 0)
 620                *fcnP = (*fcnP == FPXYboth) ? FPYonly : IYonly;
 621        else if (*icyP == 0)
 622                *fcnP = (*fcnP == FPXYboth) ? FPXonly : IXonly;
 623 }
 624 /*
 625 :h3.UnConvert() - Find User Coordinates From FractPoints
 626
 627 The interesting thing with this routine is that we avoid calculating
 628 the matrix inverse of the device transformation until we really need
 629 it, which is to say, until this routine is called for the first time
 630 with a given coordinate space.
 631
 632 We also only calculate it only once.  If the inverted matrix is valid,
 633 we don't calculate it; if not, we do.  We never expect matrices with
 634 zero determinants, so by convention, we mark the matrix is invalid by
 635 marking both X terms zero.
 636 */
 637
 638 void UnConvert(S, pt, xp, yp)
 639        register struct XYspace *S;  /* relevant coordinate space             */
 640        register struct fractpoint *pt;  /* device coordinates                */
 641        double *xp,*yp;       /* where to store resulting x,y                 */
 642 {
 643        double x,y;
 644
 645        CoerceInverse(S);
 646        x = pt->x;
 647        y = pt->y;
 648        *xp = S->tofract.inverse[0][0] * x + S->tofract.inverse[1][0] * y;
 649        *yp = S->tofract.inverse[0][1] * x + S->tofract.inverse[1][1] * y;
 650 }
 651
 652 /*
 653 :h2.Transformations
 654 */
 655 /*
 656 :h3 id=xform.Xform() - Transform Object in X and Y
 657
 658 TYPE1IMAGER wants transformations of objects like paths to be identical
 659 to transformations of spaces.  For example, if you scale a line(1,1)
 660 by 10 it should yield the same result as generating the line(1,1) in
 661 a coordinate space that has been scaled by 10.
 662
 663 We handle fonts by storing the accumulated transform, for example, SR
 664 (accumulating on the right).  Then when we map the font through space TD,
 665 for example, we multiply the accumulated font transform on the left by
 666 the space transform on the right, yielding SRTD in this case.  We will
 667 get the same result if we did S, then R, then T on the space and mapping
 668 an unmodified font through that space.
 669 */
 670
 671 struct xobject *t1_Xform(obj, M)
 672        register struct xobject *obj;  /* object to transform                 */
 673        register double M[2][2];    /* transformation matrix                  */
 674 {
 675        if (obj == NULL)
 676                return(NULL);
 677
 678        if (obj->type == FONTTYPE) {
 679                register struct font *F = (struct font *) obj;
 680
 681                F = UniqueFont(F);
 682                return((struct xobject*)F);
 683        }
 684        if (obj->type == PICTURETYPE) {
 685 /*
 686 In the case of a picture, we choose both to update the picture's
 687 transformation matrix and keep the handles up to date.
 688 */
 689                register struct picture *P = (struct picture *) obj;
 690                register struct segment *handles;  /* temporary path to transform handles */
 691
 692                P = UniquePicture(P);
 693                handles = PathSegment(LINETYPE, P->origin.x, P->origin.y);
 694                handles = Join(handles,
 695                               PathSegment(LINETYPE, P->ending.x, P->ending.y) );
 696                handles = (struct segment *)Xform((struct xobject *) handles, M);
 697                P->origin = handles->dest;
 698                P->ending = handles->link->dest;
 699                KillPath(handles);
 700                return((struct xobject *)P);
 701        }
 702
 703        if (ISPATHTYPE(obj->type)) {
 704                struct XYspace pseudo;  /* local temporary space              */
 705                PseudoSpace(&pseudo, M);
 706                return((struct xobject *) PathTransform(obj, &pseudo));
 707        }
 708
 709
 710        if (obj->type == SPACETYPE) {
 711                register struct XYspace *S = (struct XYspace *) obj;
 712
 713 /* replaced ISPERMANENT(S->flag) with S->references > 1 3-26-91 PNM */
 714                if (S->references > 1)
 715                        S = CopySpace(S);
 716                else
 717                        S->ID = NEXTID;
 718
 719                MatrixMultiply(S->tofract.normal, M, S->tofract.normal);
 720                /*
 721                * mark inverted matrix invalid:
 722                */
 723                S->flag &= ~HASINVERSE(ON);
 724
 725                FillOutFcns(S);
 726                return((struct xobject *) S);
 727        }
 728
 729        return(ArgErr("Untransformable object", obj, obj));
 730 }
 731
 732 /*
 733 :h3.Transform() - Transform an Object
 734
 735 This is the external user's entry point.
 736 */
 737 struct xobject *t1_Transform(obj, cxx, cyx, cxy, cyy)
 738        struct xobject *obj;
 739        double cxx,cyx,cxy,cyy;  /* 2x2 transform matrix elements in row order */
 740 {
 741        double M[2][2];
 742
 743        IfTrace1((MustTraceCalls),"Transform(%z,", obj);
 744        IfTrace4((MustTraceCalls)," %f %f %f %f)\n", &cxx, &cyx, &cxy, &cyy);
 745
 746        M[0][0] = cxx;
 747        M[0][1] = cyx;
 748        M[1][0] = cxy;
 749        M[1][1] = cyy;
 750        ConsiderContext(obj, M);
 751        return(Xform(obj, M));
 752 }
 753 /*
 754 :h3.Scale() - Special Case of Transform()
 755
 756 This is a user operator.
 757 */
 758
 759 struct xobject *t1_Scale(obj, sx, sy)
 760        struct xobject *obj;  /* object to scale                              */
 761        double sx,sy;         /* scale factors in x and y                     */
 762 {
 763        double M[2][2];
 764        IfTrace3((MustTraceCalls),"Scale(%z, %f, %f)\n", obj, &sx, &sy);
 765        M[0][0] = sx;
 766        M[1][1] = sy;
 767        M[1][0] = M[0][1] = 0.0;
 768        ConsiderContext(obj, M);
 769        return(Xform(obj, M));
 770 }
 771
 772 /*
 773 :h3 id=rotate.Rotate() - Special Case of Transform()
 774
 775 We special-case different settings of 'degrees' for performance
 776 and accuracy within the DegreeSin() and DegreeCos() routines themselves.
 777 */
 778
 779 #ifdef notdef
 780 struct xobject *xiRotate(obj, degrees)
 781        struct xobject *obj;  /* object to be transformed                     */
 782        double degrees;       /* degrees of COUNTER-clockwise rotation        */
 783 {
 784        double M[2][2];
 785
 786
 787        IfTrace2((MustTraceCalls),"Rotate(%z, %f)\n", obj, &degrees);
 788
 789        M[0][0] = M[1][1] = DegreeCos(degrees);
 790        M[1][0] = - (M[0][1] = DegreeSin(degrees));
 791        ConsiderContext(obj, M);
 792        return(Xform(obj, M));
 793 }
 794 #endif
 795
 796 /*
 797 :h3.PseudoSpace() - Build a Coordinate Space from a Matrix
 798
 799 Since we have built all this optimized code that, given an (x,y) and
 800 a coordinate space, yield transformed (x,y), it seems a shame not to
 801 use the same logic when we need to multiply an (x,y) by an arbitrary
 802 matrix that is not (initially) part of a coordinate space.  This
 803 subroutine takes the arbitrary matrix and builds a coordinate
 804 space, with all its nifty function pointers.
 805 */
 806
 807 void PseudoSpace(S, M)
 808        struct XYspace *S;    /* coordinate space structure to fill out       */
 809        double M[2][2];       /* matrix that will become 'tofract.normal'     */
 810 {
 811        S->type = SPACETYPE;
 812        S->flag = ISPERMANENT(ON) + ISIMMORTAL(ON);
 813        S->references = 2;   /* 3-26-91 added PNM  */
 814        S->tofract.normal[0][0] = M[0][0];
 815        S->tofract.normal[1][0] = M[1][0];
 816        S->tofract.normal[0][1] = M[0][1];
 817        S->tofract.normal[1][1] = M[1][1];
 818
 819        FillOutFcns(S);
 820 }
 821
 822 /*
 823 :h2 id=matrixa.Matrix Arithmetic
 824
 825 Following the convention in Newman and Sproull, :hp1/Interactive
 826 Computer Graphics/,
 827 matrices are organized:
 828 :xmp.
 829        | cxx   cyx |
 830        | cxy   cyy |
 831 :exmp.
 832 A point is horizontal, for example:
 833 :xmp.
 834        [ x y ]
 835 :exmp.
 836 This means that:
 837 :formula/x prime = cxx times x + cxy times y/
 838 :formula/y prime = cyx times x + cyy times y/
 839 I've seen the other convention, where transform matrices are
 840 transposed, equally often in the literature.
 841 */
 842
 843 /*
 844 :h3.MatrixMultiply() - Implements Multiplication of Two Matrices
 845
 846 Implements matrix multiplication, A * B = C.
 847
 848 To remind myself, matrix multiplication goes rows of A times columns
 849 of B.
 850 The output matrix may be the same as one of the input matrices.
 851 */
 852 void MatrixMultiply(A, B, C)
 853        register double A[2][2],B[2][2];  /* input matrices                   */
 854        register double C[2][2];    /* output matrix                          */
 855 {
 856        register double txx,txy,tyx,tyy;
 857
 858        txx = A[0][0] * B[0][0] + A[0][1] * B[1][0];
 859        txy = A[1][0] * B[0][0] + A[1][1] * B[1][0];
 860        tyx = A[0][0] * B[0][1] + A[0][1] * B[1][1];
 861        tyy = A[1][0] * B[0][1] + A[1][1] * B[1][1];
 862
 863        C[0][0] = txx;
 864        C[1][0] = txy;
 865        C[0][1] = tyx;
 866        C[1][1] = tyy;
 867 }
 868 /*
 869 :h3.MatrixInvert() - Invert a Matrix
 870
 871 My reference for matrix inversion was :hp1/Elementary Linear Algebra/
 872 by Paul C. Shields, Worth Publishers, Inc., 1968.
 873 */
 874 void MatrixInvert(M, Mprime)
 875        double M[2][2];       /* input matrix                                 */
 876        double Mprime[2][2];    /* output inverted matrix                     */
 877 {
 878        register double D;    /* determinant of matrix M                      */
 879        register double txx,txy,tyx,tyy;
 880
 881        txx = M[0][0];
 882        txy = M[1][0];
 883        tyx = M[0][1];
 884        tyy = M[1][1];
 885
 886        D = M[1][1] * M[0][0] - M[1][0] * M[0][1];
 887        if (D == 0.0)
 888                abort("MatrixInvert:  can't");
 889
 890        Mprime[0][0] = tyy / D;
 891        Mprime[1][0] = -txy / D;
 892        Mprime[0][1] = -tyx / D;
 893        Mprime[1][1] = txx / D;
 894 }
 895 /*
 896 :h2.Initialization, Queries, and Debug
 897 */
 898 /*
 899 :h3.InitSpaces() - Initialize Constant Spaces
 900
 901 For compatibility, we initialize a coordinate space called USER which
 902 maps 72nds of an inch to pels on the default device.
 903 */
 904
 905 struct XYspace *USER = &identity;
 906
 907 void InitSpaces()
 908 {
 909        extern char *DEFAULTDEVICE;
 910
 911        IDENTITY->type = SPACETYPE;
 912        FillOutFcns(IDENTITY);
 913
 914        contexts[NULLCONTEXT].normal[1][0]
 915              = contexts[NULLCONTEXT].normal[0][1]
 916              = contexts[NULLCONTEXT].inverse[1][0]
 917              = contexts[NULLCONTEXT].inverse[0][1] = 0.0;
 918        contexts[NULLCONTEXT].normal[0][0]
 919              = contexts[NULLCONTEXT].normal[1][1]
 920              = contexts[NULLCONTEXT].inverse[0][0]
 921              = contexts[NULLCONTEXT].inverse[1][1] = 1.0;
 922
 923        USER->flag |= ISIMMORTAL(ON);
 924        CoerceInverse(USER);
 925 }
 926 /*
 927 :h3.QuerySpace() - Returns the Transformation Matrix of a Space
 928
 929 Since the tofract matrix of an XYspace includes the scale factor
 930 necessary to produce fractpel results (i.e., FRACTFLOAT), this
 931 must be taken out before we return the matrix to the user.  Fortunately,
 932 this is simple:  just multiply by the inverse of IDENTITY!
 933 */
 934
 935 void QuerySpace(S, cxxP, cyxP, cxyP, cyyP)
 936        register struct XYspace *S;  /* space asked about                     */
 937        register double *cxxP,*cyxP,*cxyP,*cyyP;  /* where to put answer      */
 938 {
 939        double M[2][2];       /* temp matrix to build user's answer           */
 940
 941        if (S->type != SPACETYPE) {
 942                ArgErr("QuerySpace: not a space", S, NULL);
 943                return;
 944        }
 945        MatrixMultiply(S->tofract.normal, IDENTITY->tofract.inverse, M);
 946        *cxxP = M[0][0];
 947        *cxyP = M[1][0];
 948        *cyxP = M[0][1];
 949        *cyyP = M[1][1];
 950 }
 951
 952 /*
 953 :h3.FormatFP() - Format a Fixed Point Pel
 954
 955 We format the pel as "dddd.XXXX", where XX's are hexidecimal digits,
 956 and the dd's are decimal digits.  This might be a little confusing
 957 mixing hexidecimal and decimal like that, but it is convenient
 958 to use for debug.
 959
 960 We make sure we have N (FRACTBITS/4) digits past the decimal point.
 961 */
 962 #define  FRACTMASK   ((1<<FRACTBITS)-1)  /* mask for fractional part         */
 963
 964 void FormatFP(string, fpel)
 965        register char *string;  /* output string                              */
 966        register fractpel fpel; /* fractional pel input                       */
 967 {
 968        char temp[8];
 969        register char *s;
 970        register char *sign;
 971
 972        if (fpel < 0) {
 973                sign = "-";
 974                fpel = -fpel;
 975        }
 976        else
 977                sign = "";
 978
 979        sprintf(temp, "000%x", fpel & FRACTMASK);
 980        s = temp + strlen(temp) - (FRACTBITS/4);
 981
 982        sprintf(string, "%s%d.%sx", sign, fpel >> FRACTBITS, s);
 983 }
 984
 985 /*
 986 :h3.DumpSpace() - Display a Coordinate Space
 987 */
 988 /*ARGSUSED*/
 989 void DumpSpace(S)
 990        register struct XYspace *S;
 991 {
 992        IfTrace4(TRUE,"--Coordinate space at %x,ID=%d,convert=%x,iconvert=%x\n",
 993                    S, S->ID, S->convert, S->iconvert);
 994        IfTrace2(TRUE,"             |  %12.3f  %12.3f  |",
 995                    &S->tofract.normal[0][0], &S->tofract.normal[0][1]);
 996        IfTrace2(TRUE,"   [  %p  %p ]\n", S->itofract[0][0], S->itofract[0][1]);
 997        IfTrace2(TRUE,"             |  %12.3f  %12.3f  |",
 998                    &S->tofract.normal[1][0], &S->tofract.normal[1][1]);
 999        IfTrace2(TRUE,"   [  %p  %p ]\n", S->itofract[1][0], S->itofract[1][1]);
1000 }