glyph.c (19321B)
1 /* 2 * 3 * Copyright © 2000 SuSE, Inc. 4 * 5 * Permission to use, copy, modify, distribute, and sell this software and its 6 * documentation for any purpose is hereby granted without fee, provided that 7 * the above copyright notice appear in all copies and that both that 8 * copyright notice and this permission notice appear in supporting 9 * documentation, and that the name of SuSE not be used in advertising or 10 * publicity pertaining to distribution of the software without specific, 11 * written prior permission. SuSE makes no representations about the 12 * suitability of this software for any purpose. It is provided "as is" 13 * without express or implied warranty. 14 * 15 * SuSE DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL SuSE 17 * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 19 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 20 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 21 * 22 * Author: Keith Packard, SuSE, Inc. 23 */ 24 25 #ifdef HAVE_DIX_CONFIG_H 26 #include <dix-config.h> 27 #endif 28 29 #include "xsha1.h" 30 31 #include "misc.h" 32 #include "scrnintstr.h" 33 #include "os.h" 34 #include "regionstr.h" 35 #include "validate.h" 36 #include "windowstr.h" 37 #include "input.h" 38 #include "resource.h" 39 #include "colormapst.h" 40 #include "cursorstr.h" 41 #include "dixstruct.h" 42 #include "gcstruct.h" 43 #include "servermd.h" 44 #include "picturestr.h" 45 #include "glyphstr.h" 46 #include "mipict.h" 47 48 /* 49 * From Knuth -- a good choice for hash/rehash values is p, p-2 where 50 * p and p-2 are both prime. These tables are sized to have an extra 10% 51 * free to avoid exponential performance degradation as the hash table fills 52 */ 53 static GlyphHashSetRec glyphHashSets[] = { 54 {32, 43, 41}, 55 {64, 73, 71}, 56 {128, 151, 149}, 57 {256, 283, 281}, 58 {512, 571, 569}, 59 {1024, 1153, 1151}, 60 {2048, 2269, 2267}, 61 {4096, 4519, 4517}, 62 {8192, 9013, 9011}, 63 {16384, 18043, 18041}, 64 {32768, 36109, 36107}, 65 {65536, 72091, 72089}, 66 {131072, 144409, 144407}, 67 {262144, 288361, 288359}, 68 {524288, 576883, 576881}, 69 {1048576, 1153459, 1153457}, 70 {2097152, 2307163, 2307161}, 71 {4194304, 4613893, 4613891}, 72 {8388608, 9227641, 9227639}, 73 {16777216, 18455029, 18455027}, 74 {33554432, 36911011, 36911009}, 75 {67108864, 73819861, 73819859}, 76 {134217728, 147639589, 147639587}, 77 {268435456, 295279081, 295279079}, 78 {536870912, 590559793, 590559791} 79 }; 80 81 #define NGLYPHHASHSETS ARRAY_SIZE(glyphHashSets) 82 83 static GlyphHashRec globalGlyphs[GlyphFormatNum]; 84 85 void 86 GlyphUninit(ScreenPtr pScreen) 87 { 88 PictureScreenPtr ps = GetPictureScreen(pScreen); 89 GlyphPtr glyph; 90 int fdepth, i; 91 92 for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++) { 93 if (!globalGlyphs[fdepth].hashSet) 94 continue; 95 96 for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++) { 97 glyph = globalGlyphs[fdepth].table[i].glyph; 98 if (glyph && glyph != DeletedGlyph) { 99 if (GetGlyphPicture(glyph, pScreen)) { 100 FreePicture((void *) GetGlyphPicture(glyph, pScreen), 0); 101 SetGlyphPicture(glyph, pScreen, NULL); 102 } 103 (*ps->UnrealizeGlyph) (pScreen, glyph); 104 } 105 } 106 } 107 } 108 109 static GlyphHashSetPtr 110 FindGlyphHashSet(CARD32 filled) 111 { 112 int i; 113 114 for (i = 0; i < NGLYPHHASHSETS; i++) 115 if (glyphHashSets[i].entries >= filled) 116 return &glyphHashSets[i]; 117 return 0; 118 } 119 120 static GlyphRefPtr 121 FindGlyphRef(GlyphHashPtr hash, 122 CARD32 signature, Bool match, unsigned char sha1[20]) 123 { 124 CARD32 elt, step, s; 125 GlyphPtr glyph; 126 GlyphRefPtr table, gr, del; 127 CARD32 tableSize = hash->hashSet->size; 128 129 table = hash->table; 130 elt = signature % tableSize; 131 step = 0; 132 del = 0; 133 for (;;) { 134 gr = &table[elt]; 135 s = gr->signature; 136 glyph = gr->glyph; 137 if (!glyph) { 138 if (del) 139 gr = del; 140 break; 141 } 142 if (glyph == DeletedGlyph) { 143 if (!del) 144 del = gr; 145 else if (gr == del) 146 break; 147 } 148 else if (s == signature && 149 (!match || memcmp(glyph->sha1, sha1, 20) == 0)) { 150 break; 151 } 152 if (!step) { 153 step = signature % hash->hashSet->rehash; 154 if (!step) 155 step = 1; 156 } 157 elt += step; 158 if (elt >= tableSize) 159 elt -= tableSize; 160 } 161 return gr; 162 } 163 164 int 165 HashGlyph(xGlyphInfo * gi, 166 CARD8 *bits, unsigned long size, unsigned char sha1[20]) 167 { 168 void *ctx = x_sha1_init(); 169 int success; 170 171 if (!ctx) 172 return BadAlloc; 173 174 success = x_sha1_update(ctx, gi, sizeof(xGlyphInfo)); 175 if (!success) 176 return BadAlloc; 177 success = x_sha1_update(ctx, bits, size); 178 if (!success) 179 return BadAlloc; 180 success = x_sha1_final(ctx, sha1); 181 if (!success) 182 return BadAlloc; 183 return Success; 184 } 185 186 GlyphPtr 187 FindGlyphByHash(unsigned char sha1[20], int format) 188 { 189 GlyphRefPtr gr; 190 CARD32 signature = *(CARD32 *) sha1; 191 192 if (!globalGlyphs[format].hashSet) 193 return NULL; 194 195 gr = FindGlyphRef(&globalGlyphs[format], signature, TRUE, sha1); 196 197 if (gr->glyph && gr->glyph != DeletedGlyph) 198 return gr->glyph; 199 else 200 return NULL; 201 } 202 203 #ifdef CHECK_DUPLICATES 204 void 205 DuplicateRef(GlyphPtr glyph, char *where) 206 { 207 ErrorF("Duplicate Glyph 0x%x from %s\n", glyph, where); 208 } 209 210 void 211 CheckDuplicates(GlyphHashPtr hash, char *where) 212 { 213 GlyphPtr g; 214 int i, j; 215 216 for (i = 0; i < hash->hashSet->size; i++) { 217 g = hash->table[i].glyph; 218 if (!g || g == DeletedGlyph) 219 continue; 220 for (j = i + 1; j < hash->hashSet->size; j++) 221 if (hash->table[j].glyph == g) 222 DuplicateRef(g, where); 223 } 224 } 225 #else 226 #define CheckDuplicates(a,b) 227 #define DuplicateRef(a,b) 228 #endif 229 230 static void 231 FreeGlyphPicture(GlyphPtr glyph) 232 { 233 PictureScreenPtr ps; 234 int i; 235 236 for (i = 0; i < screenInfo.numScreens; i++) { 237 ScreenPtr pScreen = screenInfo.screens[i]; 238 239 if (GetGlyphPicture(glyph, pScreen)) 240 FreePicture((void *) GetGlyphPicture(glyph, pScreen), 0); 241 242 ps = GetPictureScreenIfSet(pScreen); 243 if (ps) 244 (*ps->UnrealizeGlyph) (pScreen, glyph); 245 } 246 } 247 248 static void 249 FreeGlyph(GlyphPtr glyph, int format) 250 { 251 CheckDuplicates(&globalGlyphs[format], "FreeGlyph"); 252 if (--glyph->refcnt == 0) { 253 GlyphRefPtr gr; 254 int i; 255 int first; 256 CARD32 signature; 257 258 first = -1; 259 for (i = 0; i < globalGlyphs[format].hashSet->size; i++) 260 if (globalGlyphs[format].table[i].glyph == glyph) { 261 if (first != -1) 262 DuplicateRef(glyph, "FreeGlyph check"); 263 first = i; 264 } 265 266 signature = *(CARD32 *) glyph->sha1; 267 gr = FindGlyphRef(&globalGlyphs[format], signature, TRUE, glyph->sha1); 268 if (gr - globalGlyphs[format].table != first) 269 DuplicateRef(glyph, "Found wrong one"); 270 if (gr->glyph && gr->glyph != DeletedGlyph) { 271 gr->glyph = DeletedGlyph; 272 gr->signature = 0; 273 globalGlyphs[format].tableEntries--; 274 } 275 276 FreeGlyphPicture(glyph); 277 dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH); 278 } 279 } 280 281 void 282 AddGlyph(GlyphSetPtr glyphSet, GlyphPtr glyph, Glyph id) 283 { 284 GlyphRefPtr gr; 285 CARD32 signature; 286 287 CheckDuplicates(&globalGlyphs[glyphSet->fdepth], "AddGlyph top global"); 288 /* Locate existing matching glyph */ 289 signature = *(CARD32 *) glyph->sha1; 290 gr = FindGlyphRef(&globalGlyphs[glyphSet->fdepth], signature, 291 TRUE, glyph->sha1); 292 if (gr->glyph && gr->glyph != DeletedGlyph && gr->glyph != glyph) { 293 FreeGlyphPicture(glyph); 294 dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH); 295 glyph = gr->glyph; 296 } 297 else if (gr->glyph != glyph) { 298 gr->glyph = glyph; 299 gr->signature = signature; 300 globalGlyphs[glyphSet->fdepth].tableEntries++; 301 } 302 303 /* Insert/replace glyphset value */ 304 gr = FindGlyphRef(&glyphSet->hash, id, FALSE, 0); 305 ++glyph->refcnt; 306 if (gr->glyph && gr->glyph != DeletedGlyph) 307 FreeGlyph(gr->glyph, glyphSet->fdepth); 308 else 309 glyphSet->hash.tableEntries++; 310 gr->glyph = glyph; 311 gr->signature = id; 312 CheckDuplicates(&globalGlyphs[glyphSet->fdepth], "AddGlyph bottom"); 313 } 314 315 Bool 316 DeleteGlyph(GlyphSetPtr glyphSet, Glyph id) 317 { 318 GlyphRefPtr gr; 319 GlyphPtr glyph; 320 321 gr = FindGlyphRef(&glyphSet->hash, id, FALSE, 0); 322 glyph = gr->glyph; 323 if (glyph && glyph != DeletedGlyph) { 324 gr->glyph = DeletedGlyph; 325 glyphSet->hash.tableEntries--; 326 FreeGlyph(glyph, glyphSet->fdepth); 327 return TRUE; 328 } 329 return FALSE; 330 } 331 332 GlyphPtr 333 FindGlyph(GlyphSetPtr glyphSet, Glyph id) 334 { 335 GlyphPtr glyph; 336 337 glyph = FindGlyphRef(&glyphSet->hash, id, FALSE, 0)->glyph; 338 if (glyph == DeletedGlyph) 339 glyph = 0; 340 return glyph; 341 } 342 343 GlyphPtr 344 AllocateGlyph(xGlyphInfo * gi, int fdepth) 345 { 346 PictureScreenPtr ps; 347 int size; 348 GlyphPtr glyph; 349 int i; 350 int head_size; 351 352 head_size = sizeof(GlyphRec) + screenInfo.numScreens * sizeof(PicturePtr); 353 size = (head_size + dixPrivatesSize(PRIVATE_GLYPH)); 354 glyph = (GlyphPtr) malloc(size); 355 if (!glyph) 356 return 0; 357 glyph->refcnt = 0; 358 glyph->size = size + sizeof(xGlyphInfo); 359 glyph->info = *gi; 360 dixInitPrivates(glyph, (char *) glyph + head_size, PRIVATE_GLYPH); 361 362 for (i = 0; i < screenInfo.numScreens; i++) { 363 ScreenPtr pScreen = screenInfo.screens[i]; 364 SetGlyphPicture(glyph, pScreen, NULL); 365 ps = GetPictureScreenIfSet(pScreen); 366 367 if (ps) { 368 if (!(*ps->RealizeGlyph) (pScreen, glyph)) 369 goto bail; 370 } 371 } 372 373 return glyph; 374 375 bail: 376 while (i--) { 377 ps = GetPictureScreenIfSet(screenInfo.screens[i]); 378 if (ps) 379 (*ps->UnrealizeGlyph) (screenInfo.screens[i], glyph); 380 } 381 382 dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH); 383 return 0; 384 } 385 386 static Bool 387 AllocateGlyphHash(GlyphHashPtr hash, GlyphHashSetPtr hashSet) 388 { 389 hash->table = calloc(hashSet->size, sizeof(GlyphRefRec)); 390 if (!hash->table) 391 return FALSE; 392 hash->hashSet = hashSet; 393 hash->tableEntries = 0; 394 return TRUE; 395 } 396 397 static Bool 398 ResizeGlyphHash(GlyphHashPtr hash, CARD32 change, Bool global) 399 { 400 CARD32 tableEntries; 401 GlyphHashSetPtr hashSet; 402 GlyphHashRec newHash; 403 GlyphRefPtr gr; 404 GlyphPtr glyph; 405 int i; 406 int oldSize; 407 CARD32 s; 408 409 tableEntries = hash->tableEntries + change; 410 hashSet = FindGlyphHashSet(tableEntries); 411 if (hashSet == hash->hashSet) 412 return TRUE; 413 if (global) 414 CheckDuplicates(hash, "ResizeGlyphHash top"); 415 if (!AllocateGlyphHash(&newHash, hashSet)) 416 return FALSE; 417 if (hash->table) { 418 oldSize = hash->hashSet->size; 419 for (i = 0; i < oldSize; i++) { 420 glyph = hash->table[i].glyph; 421 if (glyph && glyph != DeletedGlyph) { 422 s = hash->table[i].signature; 423 gr = FindGlyphRef(&newHash, s, global, glyph->sha1); 424 425 gr->signature = s; 426 gr->glyph = glyph; 427 ++newHash.tableEntries; 428 } 429 } 430 free(hash->table); 431 } 432 *hash = newHash; 433 if (global) 434 CheckDuplicates(hash, "ResizeGlyphHash bottom"); 435 return TRUE; 436 } 437 438 Bool 439 ResizeGlyphSet(GlyphSetPtr glyphSet, CARD32 change) 440 { 441 return (ResizeGlyphHash(&glyphSet->hash, change, FALSE) && 442 ResizeGlyphHash(&globalGlyphs[glyphSet->fdepth], change, TRUE)); 443 } 444 445 GlyphSetPtr 446 AllocateGlyphSet(int fdepth, PictFormatPtr format) 447 { 448 GlyphSetPtr glyphSet; 449 450 if (!globalGlyphs[fdepth].hashSet) { 451 if (!AllocateGlyphHash(&globalGlyphs[fdepth], &glyphHashSets[0])) 452 return FALSE; 453 } 454 455 glyphSet = dixAllocateObjectWithPrivates(GlyphSetRec, PRIVATE_GLYPHSET); 456 if (!glyphSet) 457 return FALSE; 458 459 if (!AllocateGlyphHash(&glyphSet->hash, &glyphHashSets[0])) { 460 free(glyphSet); 461 return FALSE; 462 } 463 glyphSet->refcnt = 1; 464 glyphSet->fdepth = fdepth; 465 glyphSet->format = format; 466 return glyphSet; 467 } 468 469 int 470 FreeGlyphSet(void *value, XID gid) 471 { 472 GlyphSetPtr glyphSet = (GlyphSetPtr) value; 473 474 if (--glyphSet->refcnt == 0) { 475 CARD32 i, tableSize = glyphSet->hash.hashSet->size; 476 GlyphRefPtr table = glyphSet->hash.table; 477 GlyphPtr glyph; 478 479 for (i = 0; i < tableSize; i++) { 480 glyph = table[i].glyph; 481 if (glyph && glyph != DeletedGlyph) 482 FreeGlyph(glyph, glyphSet->fdepth); 483 } 484 if (!globalGlyphs[glyphSet->fdepth].tableEntries) { 485 free(globalGlyphs[glyphSet->fdepth].table); 486 globalGlyphs[glyphSet->fdepth].table = 0; 487 globalGlyphs[glyphSet->fdepth].hashSet = 0; 488 } 489 else 490 ResizeGlyphHash(&globalGlyphs[glyphSet->fdepth], 0, TRUE); 491 free(table); 492 dixFreeObjectWithPrivates(glyphSet, PRIVATE_GLYPHSET); 493 } 494 return Success; 495 } 496 497 static void 498 GlyphExtents(int nlist, GlyphListPtr list, GlyphPtr * glyphs, BoxPtr extents) 499 { 500 int x1, x2, y1, y2; 501 int n; 502 GlyphPtr glyph; 503 int x, y; 504 505 x = 0; 506 y = 0; 507 extents->x1 = MAXSHORT; 508 extents->x2 = MINSHORT; 509 extents->y1 = MAXSHORT; 510 extents->y2 = MINSHORT; 511 while (nlist--) { 512 x += list->xOff; 513 y += list->yOff; 514 n = list->len; 515 list++; 516 while (n--) { 517 glyph = *glyphs++; 518 x1 = x - glyph->info.x; 519 if (x1 < MINSHORT) 520 x1 = MINSHORT; 521 y1 = y - glyph->info.y; 522 if (y1 < MINSHORT) 523 y1 = MINSHORT; 524 x2 = x1 + glyph->info.width; 525 if (x2 > MAXSHORT) 526 x2 = MAXSHORT; 527 y2 = y1 + glyph->info.height; 528 if (y2 > MAXSHORT) 529 y2 = MAXSHORT; 530 if (x1 < extents->x1) 531 extents->x1 = x1; 532 if (x2 > extents->x2) 533 extents->x2 = x2; 534 if (y1 < extents->y1) 535 extents->y1 = y1; 536 if (y2 > extents->y2) 537 extents->y2 = y2; 538 x += glyph->info.xOff; 539 y += glyph->info.yOff; 540 } 541 } 542 } 543 544 #define NeedsComponent(f) (PICT_FORMAT_A(f) != 0 && PICT_FORMAT_RGB(f) != 0) 545 546 void 547 CompositeGlyphs(CARD8 op, 548 PicturePtr pSrc, 549 PicturePtr pDst, 550 PictFormatPtr maskFormat, 551 INT16 xSrc, 552 INT16 ySrc, int nlist, GlyphListPtr lists, GlyphPtr * glyphs) 553 { 554 PictureScreenPtr ps = GetPictureScreen(pDst->pDrawable->pScreen); 555 556 ValidatePicture(pSrc); 557 ValidatePicture(pDst); 558 (*ps->Glyphs) (op, pSrc, pDst, maskFormat, xSrc, ySrc, nlist, lists, 559 glyphs); 560 } 561 562 Bool 563 miRealizeGlyph(ScreenPtr pScreen, GlyphPtr glyph) 564 { 565 return TRUE; 566 } 567 568 void 569 miUnrealizeGlyph(ScreenPtr pScreen, GlyphPtr glyph) 570 { 571 } 572 573 void 574 miGlyphs(CARD8 op, 575 PicturePtr pSrc, 576 PicturePtr pDst, 577 PictFormatPtr maskFormat, 578 INT16 xSrc, 579 INT16 ySrc, int nlist, GlyphListPtr list, GlyphPtr * glyphs) 580 { 581 PicturePtr pPicture; 582 PixmapPtr pMaskPixmap = 0; 583 PicturePtr pMask; 584 ScreenPtr pScreen = pDst->pDrawable->pScreen; 585 int width = 0, height = 0; 586 int x, y; 587 int xDst = list->xOff, yDst = list->yOff; 588 int n; 589 GlyphPtr glyph; 590 int error; 591 BoxRec extents = { 0, 0, 0, 0 }; 592 CARD32 component_alpha; 593 594 if (maskFormat) { 595 GCPtr pGC; 596 xRectangle rect; 597 598 GlyphExtents(nlist, list, glyphs, &extents); 599 600 if (extents.x2 <= extents.x1 || extents.y2 <= extents.y1) 601 return; 602 width = extents.x2 - extents.x1; 603 height = extents.y2 - extents.y1; 604 pMaskPixmap = (*pScreen->CreatePixmap) (pScreen, width, height, 605 maskFormat->depth, 606 CREATE_PIXMAP_USAGE_SCRATCH); 607 if (!pMaskPixmap) 608 return; 609 component_alpha = NeedsComponent(maskFormat->format); 610 pMask = CreatePicture(0, &pMaskPixmap->drawable, 611 maskFormat, CPComponentAlpha, &component_alpha, 612 serverClient, &error); 613 if (!pMask) { 614 (*pScreen->DestroyPixmap) (pMaskPixmap); 615 return; 616 } 617 pGC = GetScratchGC(pMaskPixmap->drawable.depth, pScreen); 618 ValidateGC(&pMaskPixmap->drawable, pGC); 619 rect.x = 0; 620 rect.y = 0; 621 rect.width = width; 622 rect.height = height; 623 (*pGC->ops->PolyFillRect) (&pMaskPixmap->drawable, pGC, 1, &rect); 624 FreeScratchGC(pGC); 625 x = -extents.x1; 626 y = -extents.y1; 627 } 628 else { 629 pMask = pDst; 630 x = 0; 631 y = 0; 632 } 633 while (nlist--) { 634 x += list->xOff; 635 y += list->yOff; 636 n = list->len; 637 while (n--) { 638 glyph = *glyphs++; 639 pPicture = GetGlyphPicture(glyph, pScreen); 640 641 if (pPicture) { 642 if (maskFormat) { 643 CompositePicture(PictOpAdd, 644 pPicture, 645 None, 646 pMask, 647 0, 0, 648 0, 0, 649 x - glyph->info.x, 650 y - glyph->info.y, 651 glyph->info.width, glyph->info.height); 652 } 653 else { 654 CompositePicture(op, 655 pSrc, 656 pPicture, 657 pDst, 658 xSrc + (x - glyph->info.x) - xDst, 659 ySrc + (y - glyph->info.y) - yDst, 660 0, 0, 661 x - glyph->info.x, 662 y - glyph->info.y, 663 glyph->info.width, glyph->info.height); 664 } 665 } 666 667 x += glyph->info.xOff; 668 y += glyph->info.yOff; 669 } 670 list++; 671 } 672 if (maskFormat) { 673 x = extents.x1; 674 y = extents.y1; 675 CompositePicture(op, 676 pSrc, 677 pMask, 678 pDst, 679 xSrc + x - xDst, 680 ySrc + y - yDst, 0, 0, x, y, width, height); 681 FreePicture((void *) pMask, (XID) 0); 682 (*pScreen->DestroyPixmap) (pMaskPixmap); 683 } 684 } 685 686 PicturePtr GetGlyphPicture(GlyphPtr glyph, ScreenPtr pScreen) 687 { 688 if (pScreen->isGPU) 689 return NULL; 690 return GlyphPicture(glyph)[pScreen->myNum]; 691 } 692 693 void SetGlyphPicture(GlyphPtr glyph, ScreenPtr pScreen, PicturePtr picture) 694 { 695 GlyphPicture(glyph)[pScreen->myNum] = picture; 696 }