QRScanner/mobile/jni/fitz/stext-device.c

   1 #include "mupdf/fitz.h"
   2 #include "ucdn.h"
   3
   4 /* Extract text into an unsorted span soup. */
   5
   6 #define LINE_DIST 0.9f
   7 #define SPACE_DIST 0.2f
   8 #define SPACE_MAX_DIST 0.8f
   9 #define PARAGRAPH_DIST 0.5f
  10
  11 #undef DEBUG_SPANS
  12 #undef DEBUG_INTERNALS
  13 #undef DEBUG_LINE_HEIGHTS
  14 #undef DEBUG_MASKS
  15 #undef DEBUG_ALIGN
  16 #undef DEBUG_INDENTS
  17
  18 #include <ft2build.h>
  19 #include FT_FREETYPE_H
  20 #include FT_ADVANCES_H
  21
  22 typedef struct fz_text_device_s fz_text_device;
  23
  24 typedef struct span_soup_s span_soup;
  25
  26 struct fz_text_device_s
  27 {
  28         fz_text_sheet *sheet;
  29         fz_text_page *page;
  30         span_soup *spans;
  31         fz_text_span *cur_span;
  32         int lastchar;
  33 };
  34
  35 static fz_rect *
  36 add_point_to_rect(fz_rect *a, const fz_point *p)
  37 {
  38         if (p->x < a->x0)
  39                 a->x0 = p->x;
  40         if (p->x > a->x1)
  41                 a->x1 = p->x;
  42         if (p->y < a->y0)
  43                 a->y0 = p->y;
  44         if (p->y > a->y1)
  45                 a->y1 = p->y;
  46         return a;
  47 }
  48
  49 fz_rect *
  50 fz_text_char_bbox(fz_rect *bbox, fz_text_span *span, int i)
  51 {
  52         fz_point a, d;
  53         const fz_point *max;
  54         fz_text_char *ch;
  55
  56         if (!span || i >= span->len)
  57         {
  58                 *bbox = fz_empty_rect;
  59                 return bbox;
  60         }
  61         ch = &span->text[i];
  62         if (i == span->len-1)
  63                 max = &span->max;
  64         else
  65                 max = &span->text[i+1].p;
  66         a.x = 0;
  67         a.y = span->ascender_max;
  68         fz_transform_vector(&a, &span->transform);
  69         d.x = 0;
  70         d.y = span->descender_min;
  71         fz_transform_vector(&d, &span->transform);
  72         bbox->x0 = bbox->x1 = ch->p.x + a.x;
  73         bbox->y0 = bbox->y1 = ch->p.y + a.y;
  74         a.x += max->x;
  75         a.y += max->y;
  76         add_point_to_rect(bbox, &a);
  77         a.x = ch->p.x + d.x;
  78         a.y = ch->p.y + d.y;
  79         add_point_to_rect(bbox, &a);
  80         a.x = max->x + d.x;
  81         a.y = max->y + d.y;
  82         add_point_to_rect(bbox, &a);
  83         return bbox;
  84 }
  85
  86 static void
  87 add_bbox_to_span(fz_text_span *span)
  88 {
  89         fz_point a, d;
  90         fz_rect *bbox = &span->bbox;
  91
  92         if (!span)
  93                 return;
  94         a.x = 0;
  95         a.y = span->ascender_max;
  96         fz_transform_vector(&a, &span->transform);
  97         d.x = 0;
  98         d.y = span->descender_min;
  99         fz_transform_vector(&d, &span->transform);
 100         bbox->x0 = bbox->x1 = span->min.x + a.x;
 101         bbox->y0 = bbox->y1 = span->min.y + a.y;
 102         a.x += span->max.x;
 103         a.y += span->max.y;
 104         add_point_to_rect(bbox, &a);
 105         a.x = span->min.x + d.x;
 106         a.y = span->min.y + d.y;
 107         add_point_to_rect(bbox, &a);
 108         a.x = span->max.x + d.x;
 109         a.y = span->max.y + d.y;
 110         add_point_to_rect(bbox, &a);
 111 }
 112
 113 struct span_soup_s
 114 {
 115         fz_context *ctx;
 116         int len, cap;
 117         fz_text_span **spans;
 118 };
 119
 120 static span_soup *
 121 new_span_soup(fz_context *ctx)
 122 {
 123         span_soup *soup = fz_malloc_struct(ctx, span_soup);
 124         soup->ctx = ctx;
 125         soup->len = 0;
 126         soup->cap = 0;
 127         soup->spans = NULL;
 128         return soup;
 129 }
 130
 131 static void
 132 free_span_soup(span_soup *soup)
 133 {
 134         int i;
 135
 136         if (soup == NULL)
 137                 return;
 138         for (i = 0; i < soup->len; i++)
 139         {
 140                 fz_free(soup->ctx, soup->spans[i]);
 141         }
 142         fz_free(soup->ctx, soup->spans);
 143         fz_free(soup->ctx, soup);
 144 }
 145
 146 static void
 147 add_span_to_soup(span_soup *soup, fz_text_span *span)
 148 {
 149         if (span == NULL)
 150                 return;
 151         if (soup->len == soup->cap)
 152         {
 153                 int newcap = (soup->cap ? soup->cap * 2 : 16);
 154                 soup->spans = fz_resize_array(soup->ctx, soup->spans, newcap, sizeof(*soup->spans));
 155                 soup->cap = newcap;
 156         }
 157         add_bbox_to_span(span);
 158         soup->spans[soup->len++] = span;
 159 }
 160
 161 static fz_text_line *
 162 push_span(fz_context *ctx, fz_text_device *tdev, fz_text_span *span, int new_line, float distance)
 163 {
 164         fz_text_line *line;
 165         fz_text_block *block;
 166         fz_text_page *page = tdev->page;
 167         int prev_not_text = 0;
 168
 169         if (page->len == 0 || page->blocks[page->len-1].type != FZ_PAGE_BLOCK_TEXT)
 170                 prev_not_text = 1;
 171
 172         if (new_line || prev_not_text)
 173         {
 174                 float size = fz_matrix_expansion(&span->transform);
 175                 /* So, a new line. Part of the same block or not? */
 176                 if (distance == 0 || distance > size * 1.5 || distance < -size * PARAGRAPH_DIST || page->len == 0 || prev_not_text)
 177                 {
 178                         /* New block */
 179                         if (page->len == page->cap)
 180                         {
 181                                 int newcap = (page->cap ? page->cap*2 : 4);
 182                                 page->blocks = fz_resize_array(ctx, page->blocks, newcap, sizeof(*page->blocks));
 183                                 page->cap = newcap;
 184                         }
 185                         block = fz_malloc_struct(ctx, fz_text_block);
 186                         page->blocks[page->len].type = FZ_PAGE_BLOCK_TEXT;
 187                         page->blocks[page->len].u.text = block;
 188                         block->cap = 0;
 189                         block->len = 0;
 190                         block->lines = 0;
 191                         block->bbox = fz_empty_rect;
 192                         page->len++;
 193                         distance = 0;
 194                 }
 195
 196                 /* New line */
 197                 block = page->blocks[page->len-1].u.text;
 198                 if (block->len == block->cap)
 199                 {
 200                         int newcap = (block->cap ? block->cap*2 : 4);
 201                         block->lines = fz_resize_array(ctx, block->lines, newcap, sizeof(*block->lines));
 202                         block->cap = newcap;
 203                 }
 204                 block->lines[block->len].first_span = NULL;
 205                 block->lines[block->len].last_span = NULL;
 206                 block->lines[block->len].distance = distance;
 207                 block->lines[block->len].bbox = fz_empty_rect;
 208                 block->len++;
 209         }
 210
 211         /* Find last line and append to it */
 212         block = page->blocks[page->len-1].u.text;
 213         line = &block->lines[block->len-1];
 214
 215         fz_union_rect(&block->lines[block->len-1].bbox, &span->bbox);
 216         fz_union_rect(&block->bbox, &span->bbox);
 217         span->base_offset = (new_line ? 0 : distance);
 218
 219         if (!line->first_span)
 220         {
 221                 line->first_span = line->last_span = span;
 222                 span->next = NULL;
 223         }
 224         else
 225         {
 226                 line->last_span->next = span;
 227                 line->last_span = span;
 228         }
 229
 230         return line;
 231 }
 232
 233 #if defined(DEBUG_SPANS) || defined(DEBUG_ALIGN) || defined(DEBUG_INDENTS)
 234 static void
 235 dump_span(fz_text_span *s)
 236 {
 237         int i;
 238         for (i=0; i < s->len; i++)
 239         {
 240                 printf("%c", s->text[i].c);
 241         }
 242 }
 243 #endif
 244
 245 #ifdef DEBUG_ALIGN
 246 static void
 247 dump_line(fz_text_line *line)
 248 {
 249         int i;
 250         for (i=0; i < line->len; i++)
 251         {
 252                 fz_text_span *s = line->spans[i];
 253                 if (s->spacing > 1)
 254                         printf(" ");
 255                 dump_span(s);
 256         }
 257         printf("\n");
 258 }
 259 #endif
 260
 261 static void
 262 strain_soup(fz_context *ctx, fz_text_device *tdev)
 263 {
 264         span_soup *soup = tdev->spans;
 265         fz_text_line *last_line = NULL;
 266         fz_text_span *last_span = NULL;
 267         int span_num;
 268
 269         /* Really dumb implementation to match what we had before */
 270         for (span_num=0; span_num < soup->len; span_num++)
 271         {
 272                 fz_text_span *span = soup->spans[span_num];
 273                 int new_line = 1;
 274                 float distance = 0;
 275                 float spacing = 0;
 276                 soup->spans[span_num] = NULL;
 277                 if (last_span)
 278                 {
 279                         /* If we have a last_span, we must have a last_line */
 280                         /* Do span and last_line share the same baseline? */
 281                         fz_point p, q, perp_r;
 282                         float dot;
 283                         float size = fz_matrix_expansion(&span->transform);
 284
 285 #ifdef DEBUG_SPANS
 286                         {
 287                                 printf("Comparing: \"");
 288                                 dump_span(last_span);
 289                                 printf("\" and \"");
 290                                 dump_span(span);
 291                                 printf("\"\n");
 292                         }
 293 #endif
 294
 295                         p.x = last_line->first_span->max.x - last_line->first_span->min.x;
 296                         p.y = last_line->first_span->max.y - last_line->first_span->min.y;
 297                         fz_normalize_vector(&p);
 298                         q.x = span->max.x - span->min.x;
 299                         q.y = span->max.y - span->min.y;
 300                         fz_normalize_vector(&q);
 301 #ifdef DEBUG_SPANS
 302                         printf("last_span=%g %g -> %g %g = %g %g\n", last_span->min.x, last_span->min.y, last_span->max.x, last_span->max.y, p.x, p.y);
 303                         printf("span     =%g %g -> %g %g = %g %g\n", span->min.x, span->min.y, span->max.x, span->max.y, q.x, q.y);
 304 #endif
 305                         perp_r.y = last_line->first_span->min.x - span->min.x;
 306                         perp_r.x = -(last_line->first_span->min.y - span->min.y);
 307                         /* Check if p and q are parallel. If so, then this
 308                          * line is parallel with the last one. */
 309                         dot = p.x * q.x + p.y * q.y;
 310                         if (fabsf(dot) > 0.9995)
 311                         {
 312                                 /* If we take the dot product of normalised(p) and
 313                                  * perp(r), we get the perpendicular distance from
 314                                  * one line to the next (assuming they are parallel). */
 315                                 distance = p.x * perp_r.x + p.y * perp_r.y;
 316                                 /* We allow 'small' distances of baseline changes
 317                                  * to cope with super/subscript. FIXME: We should
 318                                  * gather subscript/superscript information here. */
 319                                 new_line = (fabsf(distance) > size * LINE_DIST);
 320                         }
 321                         else
 322                         {
 323                                 new_line = 1;
 324                                 distance = 0;
 325                         }
 326                         if (!new_line)
 327                         {
 328                                 fz_point delta;
 329
 330                                 delta.x = span->min.x - last_span->max.x;
 331                                 delta.y = span->min.y - last_span->max.y;
 332
 333                                 spacing = (p.x * delta.x + p.y * delta.y);
 334                                 spacing = fabsf(spacing);
 335                                 /* Only allow changes in baseline (subscript/superscript etc)
 336                                  * when the spacing is small. */
 337                                 if (spacing * fabsf(distance) > size * LINE_DIST && fabsf(distance) > size * 0.1f)
 338                                 {
 339                                         new_line = 1;
 340                                         distance = 0;
 341                                         spacing = 0;
 342                                 }
 343                                 else
 344                                 {
 345                                         spacing /= size * SPACE_DIST;
 346                                         /* Apply the same logic here as when we're adding chars to build spans. */
 347                                         if (spacing >= 1 && spacing < (SPACE_MAX_DIST/SPACE_DIST))
 348                                                 spacing = 1;
 349                                 }
 350                         }
 351 #ifdef DEBUG_SPANS
 352                         printf("dot=%g new_line=%d distance=%g size=%g spacing=%g\n", dot, new_line, distance, size, spacing);
 353 #endif
 354                 }
 355                 span->spacing = spacing;
 356                 last_line = push_span(ctx, tdev, span, new_line, distance);
 357                 last_span = span;
 358         }
 359 }
 360
 361 fz_text_sheet *
 362 fz_new_text_sheet(fz_context *ctx)
 363 {
 364         fz_text_sheet *sheet = fz_malloc(ctx, sizeof *sheet);
 365         sheet->maxid = 0;
 366         sheet->style = NULL;
 367         return sheet;
 368 }
 369
 370 void
 371 fz_free_text_sheet(fz_context *ctx, fz_text_sheet *sheet)
 372 {
 373         fz_text_style *style;
 374
 375         if (sheet == NULL)
 376                 return;
 377
 378         style = sheet->style;
 379         while (style)
 380         {
 381                 fz_text_style *next = style->next;
 382                 fz_drop_font(ctx, style->font);
 383                 fz_free(ctx, style);
 384                 style = next;
 385         }
 386         fz_free(ctx, sheet);
 387 }
 388
 389 static fz_text_style *
 390 fz_lookup_text_style_imp(fz_context *ctx, fz_text_sheet *sheet,
 391         float size, fz_font *font, int wmode, int script)
 392 {
 393         fz_text_style *style;
 394
 395         for (style = sheet->style; style; style = style->next)
 396         {
 397                 if (style->font == font &&
 398                         style->size == size &&
 399                         style->wmode == wmode &&
 400                         style->script == script) /* FIXME: others */
 401                 {
 402                         return style;
 403                 }
 404         }
 405
 406         /* Better make a new one and add it to our list */
 407         style = fz_malloc(ctx, sizeof *style);
 408         style->id = sheet->maxid++;
 409         style->font = fz_keep_font(ctx, font);
 410         style->size = size;
 411         style->wmode = wmode;
 412         style->script = script;
 413         style->next = sheet->style;
 414         sheet->style = style;
 415         return style;
 416 }
 417
 418 static fz_text_style *
 419 fz_lookup_text_style(fz_context *ctx, fz_text_sheet *sheet, fz_text *text, const fz_matrix *ctm,
 420         fz_colorspace *colorspace, float *color, float alpha, fz_stroke_state *stroke)
 421 {
 422         float size = 1.0f;
 423         fz_font *font = text ? text->font : NULL;
 424         int wmode = text ? text->wmode : 0;
 425         if (ctm && text)
 426         {
 427                 fz_matrix tm = text->trm;
 428                 fz_matrix trm;
 429                 tm.e = 0;
 430                 tm.f = 0;
 431                 fz_concat(&trm, &tm, ctm);
 432                 size = fz_matrix_expansion(&trm);
 433         }
 434         return fz_lookup_text_style_imp(ctx, sheet, size, font, wmode, 0);
 435 }
 436
 437 fz_text_page *
 438 fz_new_text_page(fz_context *ctx)
 439 {
 440         fz_text_page *page = fz_malloc(ctx, sizeof(*page));
 441         page->mediabox = fz_empty_rect;
 442         page->len = 0;
 443         page->cap = 0;
 444         page->blocks = NULL;
 445         page->next = NULL;
 446         return page;
 447 }
 448
 449 static void
 450 fz_free_text_line_contents(fz_context *ctx, fz_text_line *line)
 451 {
 452         fz_text_span *span, *next;
 453         for (span = line->first_span; span; span=next)
 454         {
 455                 next = span->next;
 456                 fz_free(ctx, span->text);
 457                 fz_free(ctx, span);
 458         }
 459 }
 460
 461 static void
 462 fz_free_text_block(fz_context *ctx, fz_text_block *block)
 463 {
 464         fz_text_line *line;
 465         if (block == NULL)
 466                 return;
 467         for (line = block->lines; line < block->lines + block->len; line++)
 468                 fz_free_text_line_contents(ctx, line);
 469         fz_free(ctx, block->lines);
 470         fz_free(ctx, block);
 471 }
 472
 473 static void
 474 fz_free_image_block(fz_context *ctx, fz_image_block *block)
 475 {
 476         if (block == NULL)
 477                 return;
 478         fz_drop_image(ctx, block->image);
 479         fz_drop_colorspace(ctx, block->cspace);
 480         fz_free(ctx, block);
 481 }
 482
 483 void
 484 fz_free_text_page(fz_context *ctx, fz_text_page *page)
 485 {
 486         fz_page_block *block;
 487         if (page == NULL)
 488                 return;
 489         for (block = page->blocks; block < page->blocks + page->len; block++)
 490         {
 491                 switch (block->type)
 492                 {
 493                 case FZ_PAGE_BLOCK_TEXT:
 494                         fz_free_text_block(ctx, block->u.text);
 495                         break;
 496                 case FZ_PAGE_BLOCK_IMAGE:
 497                         fz_free_image_block(ctx, block->u.image);
 498                         break;
 499                 }
 500         }
 501         fz_free(ctx, page->blocks);
 502         fz_free(ctx, page);
 503 }
 504
 505 static fz_text_span *
 506 fz_new_text_span(fz_context *ctx, const fz_point *p, int wmode, const fz_matrix *trm)
 507 {
 508         fz_text_span *span = fz_malloc_struct(ctx, fz_text_span);
 509         span->ascender_max = 0;
 510         span->descender_min = 0;
 511         span->cap = 0;
 512         span->len = 0;
 513         span->min = *p;
 514         span->max = *p;
 515         span->wmode = wmode;
 516         span->transform.a = trm->a;
 517         span->transform.b = trm->b;
 518         span->transform.c = trm->c;
 519         span->transform.d = trm->d;
 520         span->transform.e = 0;
 521         span->transform.f = 0;
 522         span->text = NULL;
 523         span->next = NULL;
 524         return span;
 525 }
 526
 527 static void
 528 add_char_to_span(fz_context *ctx, fz_text_span *span, int c, fz_point *p, fz_point *max, fz_text_style *style)
 529 {
 530         if (span->len == span->cap)
 531         {
 532                 int newcap = (span->cap ? span->cap * 2 : 16);
 533                 span->text = fz_resize_array(ctx, span->text, newcap, sizeof(fz_text_char));
 534                 span->cap = newcap;
 535                 span->bbox = fz_empty_rect;
 536         }
 537         span->max = *max;
 538         if (style->ascender > span->ascender_max)
 539                 span->ascender_max = style->ascender;
 540         if (style->descender < span->descender_min)
 541                 span->descender_min = style->descender;
 542         span->text[span->len].c = c;
 543         span->text[span->len].p = *p;
 544         span->text[span->len].style = style;
 545         span->len++;
 546 }
 547
 548 static void
 549 fz_add_text_char_imp(fz_context *ctx, fz_text_device *dev, fz_text_style *style, int c, fz_matrix *trm, float adv, int wmode)
 550 {
 551         int can_append = 1;
 552         int add_space = 0;
 553         fz_point dir, ndir, p, q;
 554         float size;
 555         fz_point delta;
 556         float spacing = 0;
 557         float base_offset = 0;
 558
 559         if (wmode == 0)
 560         {
 561                 dir.x = 1;
 562                 dir.y = 0;
 563         }
 564         else
 565         {
 566                 dir.x = 0;
 567                 dir.y = 1;
 568         }
 569         fz_transform_vector(&dir, trm);
 570         ndir = dir;
 571         fz_normalize_vector(&ndir);
 572         /* dir = direction vector for motion. ndir = normalised(dir) */
 573
 574         size = fz_matrix_expansion(trm);
 575
 576         if (dev->cur_span == NULL ||
 577                 trm->a != dev->cur_span->transform.a || trm->b != dev->cur_span->transform.b ||
 578                 trm->c != dev->cur_span->transform.c || trm->d != dev->cur_span->transform.d)
 579         {
 580                 /* If the matrix has changed (or if we don't have a span at
 581                  * all), then we can't append. */
 582 #ifdef DEBUG_SPANS
 583                 printf("Transform changed\n");
 584 #endif
 585                 can_append = 0;
 586         }
 587         else
 588         {
 589                 /* Calculate how far we've moved since the end of the current
 590                  * span. */
 591                 delta.x = trm->e - dev->cur_span->max.x;
 592                 delta.y = trm->f - dev->cur_span->max.y;
 593
 594                 /* The transform has not changed, so we know we're in the same
 595                  * direction. Calculate 2 distances; how far off the previous
 596                  * baseline we are, together with how far along the baseline
 597                  * we are from the expected position. */
 598                 spacing = ndir.x * delta.x + ndir.y * delta.y;
 599                 base_offset = -ndir.y * delta.x + ndir.x * delta.y;
 600
 601                 spacing /= size * SPACE_DIST;
 602                 spacing = fabsf(spacing);
 603                 if (fabsf(base_offset) < size * 0.1)
 604                 {
 605                         /* Only a small amount off the baseline - we'll take this */
 606                         if (spacing < 1.0)
 607                         {
 608                                 /* Motion is in line, and small. */
 609                         }
 610                         else if (spacing >= 1 && spacing < (SPACE_MAX_DIST/SPACE_DIST))
 611                         {
 612                                 /* Motion is in line, but large enough
 613                                  * to warrant us adding a space */
 614                                 if (dev->lastchar != ' ' && wmode == 0)
 615                                         add_space = 1;
 616                         }
 617                         else
 618                         {
 619                                 /* Motion is in line, but too large - split to a new span */
 620                                 can_append = 0;
 621                         }
 622                 }
 623                 else
 624                 {
 625                         can_append = 0;
 626 #ifdef DEBUG_SPANS
 627                         spacing = 0;
 628 #endif
 629                 }
 630         }
 631
 632 #ifdef DEBUG_SPANS
 633         printf("%c%c append=%d space=%d size=%g spacing=%g base_offset=%g\n", dev->lastchar, c, can_append, add_space, size, spacing, base_offset);
 634 #endif
 635
 636         p.x = trm->e;
 637         p.y = trm->f;
 638         if (can_append == 0)
 639         {
 640                 /* Start a new span */
 641                 add_span_to_soup(dev->spans, dev->cur_span);
 642                 dev->cur_span = NULL;
 643                 dev->cur_span = fz_new_text_span(ctx, &p, wmode, trm);
 644                 dev->cur_span->spacing = 0;
 645         }
 646         if (add_space)
 647         {
 648                 q.x = - 0.2f;
 649                 q.y = 0;
 650                 fz_transform_point(&q, trm);
 651                 add_char_to_span(ctx, dev->cur_span, ' ', &p, &q, style);
 652         }
 653         /* Advance the matrix */
 654         q.x = trm->e += adv * dir.x;
 655         q.y = trm->f += adv * dir.y;
 656         add_char_to_span(ctx, dev->cur_span, c, &p, &q, style);
 657 }
 658
 659 static void
 660 fz_add_text_char(fz_context *ctx, fz_text_device *dev, fz_text_style *style, int c, fz_matrix *trm, float adv, int wmode)
 661 {
 662         switch (c)
 663         {
 664         case -1: /* ignore when one unicode character maps to multiple glyphs */
 665                 break;
 666         case 0xFB00: /* ff */
 667                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/2, wmode);
 668                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/2, wmode);
 669                 break;
 670         case 0xFB01: /* fi */
 671                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/2, wmode);
 672                 fz_add_text_char_imp(ctx, dev, style, 'i', trm, adv/2, wmode);
 673                 break;
 674         case 0xFB02: /* fl */
 675                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/2, wmode);
 676                 fz_add_text_char_imp(ctx, dev, style, 'l', trm, adv/2, wmode);
 677                 break;
 678         case 0xFB03: /* ffi */
 679                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/3, wmode);
 680                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/3, wmode);
 681                 fz_add_text_char_imp(ctx, dev, style, 'i', trm, adv/3, wmode);
 682                 break;
 683         case 0xFB04: /* ffl */
 684                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/3, wmode);
 685                 fz_add_text_char_imp(ctx, dev, style, 'f', trm, adv/3, wmode);
 686                 fz_add_text_char_imp(ctx, dev, style, 'l', trm, adv/3, wmode);
 687                 break;
 688         case 0xFB05: /* long st */
 689         case 0xFB06: /* st */
 690                 fz_add_text_char_imp(ctx, dev, style, 's', trm, adv/2, wmode);
 691                 fz_add_text_char_imp(ctx, dev, style, 't', trm, adv/2, wmode);
 692                 break;
 693         default:
 694                 fz_add_text_char_imp(ctx, dev, style, c, trm, adv, wmode);
 695                 break;
 696         }
 697 }
 698
 699 static void
 700 fz_text_extract(fz_context *ctx, fz_text_device *dev, fz_text *text, const fz_matrix *ctm, fz_text_style *style)
 701 {
 702         fz_font *font = text->font;
 703         FT_Face face = font->ft_face;
 704         fz_matrix tm = text->trm;
 705         fz_matrix trm;
 706         float adv;
 707         float ascender = 1;
 708         float descender = 0;
 709         int multi;
 710         int i, j, err;
 711
 712         if (text->len == 0)
 713                 return;
 714
 715         if (font->ft_face)
 716         {
 717                 fz_lock(ctx, FZ_LOCK_FREETYPE);
 718                 err = FT_Set_Char_Size(font->ft_face, 64, 64, 72, 72);
 719                 if (err)
 720                         fz_warn(ctx, "freetype set character size: %s", ft_error_string(err));
 721                 ascender = (float)face->ascender / face->units_per_EM;
 722                 descender = (float)face->descender / face->units_per_EM;
 723                 fz_unlock(ctx, FZ_LOCK_FREETYPE);
 724         }
 725         else if (font->t3procs && !fz_is_empty_rect(&font->bbox))
 726         {
 727                 ascender = font->bbox.y1;
 728                 descender = font->bbox.y0;
 729         }
 730         style->ascender = ascender;
 731         style->descender = descender;
 732
 733         tm.e = 0;
 734         tm.f = 0;
 735         fz_concat(&trm, &tm, ctm);
 736
 737         for (i = 0; i < text->len; i++)
 738         {
 739                 /* Calculate new pen location and delta */
 740                 tm.e = text->items[i].x;
 741                 tm.f = text->items[i].y;
 742                 fz_concat(&trm, &tm, ctm);
 743
 744                 /* Calculate bounding box and new pen position based on font metrics */
 745                 if (font->ft_face)
 746                 {
 747                         FT_Fixed ftadv = 0;
 748                         int mask = FT_LOAD_NO_BITMAP | FT_LOAD_NO_HINTING | FT_LOAD_IGNORE_TRANSFORM;
 749
 750                         /* TODO: freetype returns broken vertical metrics */
 751                         /* if (text->wmode) mask |= FT_LOAD_VERTICAL_LAYOUT; */
 752
 753                         fz_lock(ctx, FZ_LOCK_FREETYPE);
 754                         err = FT_Set_Char_Size(font->ft_face, 64, 64, 72, 72);
 755                         if (err)
 756                                 fz_warn(ctx, "freetype set character size: %s", ft_error_string(err));
 757                         FT_Get_Advance(font->ft_face, text->items[i].gid, mask, &ftadv);
 758                         adv = ftadv / 65536.0f;
 759                         fz_unlock(ctx, FZ_LOCK_FREETYPE);
 760                 }
 761                 else
 762                 {
 763                         adv = font->t3widths[text->items[i].gid];
 764                 }
 765
 766                 /* Check for one glyph to many char mapping */
 767                 for (j = i + 1; j < text->len; j++)
 768                         if (text->items[j].gid >= 0)
 769                                 break;
 770                 multi = j - i;
 771
 772                 if (multi == 1)
 773                 {
 774                         fz_add_text_char(ctx, dev, style, text->items[i].ucs, &trm, adv, text->wmode);
 775                 }
 776                 else
 777                 {
 778                         for (j = 0; j < multi; j++)
 779                         {
 780                                 fz_add_text_char(ctx, dev, style, text->items[i + j].ucs, &trm, adv/multi, text->wmode);
 781                         }
 782                         i += j - 1;
 783                 }
 784
 785                 dev->lastchar = text->items[i].ucs;
 786         }
 787 }
 788
 789 static void
 790 fz_text_fill_text(fz_device *dev, fz_text *text, const fz_matrix *ctm,
 791         fz_colorspace *colorspace, float *color, float alpha)
 792 {
 793         fz_text_device *tdev = dev->user;
 794         fz_text_style *style;
 795         style = fz_lookup_text_style(dev->ctx, tdev->sheet, text, ctm, colorspace, color, alpha, NULL);
 796         fz_text_extract(dev->ctx, tdev, text, ctm, style);
 797 }
 798
 799 static void
 800 fz_text_stroke_text(fz_device *dev, fz_text *text, fz_stroke_state *stroke, const fz_matrix *ctm,
 801         fz_colorspace *colorspace, float *color, float alpha)
 802 {
 803         fz_text_device *tdev = dev->user;
 804         fz_text_style *style;
 805         style = fz_lookup_text_style(dev->ctx, tdev->sheet, text, ctm, colorspace, color, alpha, stroke);
 806         fz_text_extract(dev->ctx, tdev, text, ctm, style);
 807 }
 808
 809 static void
 810 fz_text_clip_text(fz_device *dev, fz_text *text, const fz_matrix *ctm, int accumulate)
 811 {
 812         fz_text_device *tdev = dev->user;
 813         fz_text_style *style;
 814         style = fz_lookup_text_style(dev->ctx, tdev->sheet, text, ctm, NULL, NULL, 0, NULL);
 815         fz_text_extract(dev->ctx, tdev, text, ctm, style);
 816 }
 817
 818 static void
 819 fz_text_clip_stroke_text(fz_device *dev, fz_text *text, fz_stroke_state *stroke, const fz_matrix *ctm)
 820 {
 821         fz_text_device *tdev = dev->user;
 822         fz_text_style *style;
 823         style = fz_lookup_text_style(dev->ctx, tdev->sheet, text, ctm, NULL, NULL, 0, stroke);
 824         fz_text_extract(dev->ctx, tdev, text, ctm, style);
 825 }
 826
 827 static void
 828 fz_text_ignore_text(fz_device *dev, fz_text *text, const fz_matrix *ctm)
 829 {
 830         fz_text_device *tdev = dev->user;
 831         fz_text_style *style;
 832         style = fz_lookup_text_style(dev->ctx, tdev->sheet, text, ctm, NULL, NULL, 0, NULL);
 833         fz_text_extract(dev->ctx, tdev, text, ctm, style);
 834 }
 835
 836 static void
 837 fz_text_fill_image_mask(fz_device *dev, fz_image *img, const fz_matrix *ctm,
 838                 fz_colorspace *cspace, float *color, float alpha)
 839 {
 840         fz_text_device *tdev = dev->user;
 841         fz_text_page *page = tdev->page;
 842         fz_image_block *block;
 843         fz_context *ctx = dev->ctx;
 844
 845         /* If the alpha is less than 50% then it's probably a watermark or
 846          * effect or something. Skip it */
 847         if (alpha < 0.5)
 848                 return;
 849
 850         /* New block */
 851         if (page->len == page->cap)
 852         {
 853                 int newcap = (page->cap ? page->cap*2 : 4);
 854                 page->blocks = fz_resize_array(ctx, page->blocks, newcap, sizeof(*page->blocks));
 855                 page->cap = newcap;
 856         }
 857         block = fz_malloc_struct(ctx, fz_image_block);
 858         page->blocks[page->len].type = FZ_PAGE_BLOCK_IMAGE;
 859         page->blocks[page->len].u.image = block;
 860         block->image = fz_keep_image(ctx, img);
 861         block->cspace = fz_keep_colorspace(ctx, cspace);
 862         if (cspace)
 863                 memcpy(block->colors, color, sizeof(block->colors[0])*cspace->n);
 864         page->len++;
 865 }
 866
 867 static void
 868 fz_text_fill_image(fz_device *dev, fz_image *img, const fz_matrix *ctm, float alpha)
 869 {
 870         fz_text_fill_image_mask(dev, img, ctm, NULL, NULL, alpha);
 871 }
 872
 873 static int
 874 fz_bidi_direction(int bidiclass, int curdir)
 875 {
 876         switch (bidiclass)
 877         {
 878         /* strong */
 879         case UCDN_BIDI_CLASS_L: return 1;
 880         case UCDN_BIDI_CLASS_R: return -1;
 881         case UCDN_BIDI_CLASS_AL: return -1;
 882
 883         /* weak */
 884         case UCDN_BIDI_CLASS_EN:
 885         case UCDN_BIDI_CLASS_ES:
 886         case UCDN_BIDI_CLASS_ET:
 887         case UCDN_BIDI_CLASS_AN:
 888         case UCDN_BIDI_CLASS_CS:
 889         case UCDN_BIDI_CLASS_NSM:
 890         case UCDN_BIDI_CLASS_BN:
 891                 return curdir;
 892
 893         /* neutral */
 894         case UCDN_BIDI_CLASS_B:
 895         case UCDN_BIDI_CLASS_S:
 896         case UCDN_BIDI_CLASS_WS:
 897         case UCDN_BIDI_CLASS_ON:
 898                 return curdir;
 899
 900         /* embedding, override, pop ... we don't support them */
 901         default:
 902                 return 0;
 903         }
 904 }
 905
 906 static void
 907 fz_bidi_reorder_run(fz_text_span *span, int a, int b, int dir)
 908 {
 909         if (a < b && dir == -1)
 910         {
 911                 fz_text_char c;
 912                 int m = a + (b - a) / 2;
 913                 while (a < m)
 914                 {
 915                         b--;
 916                         c = span->text[a];
 917                         span->text[a] = span->text[b];
 918                         span->text[b] = c;
 919                         a++;
 920                 }
 921         }
 922 }
 923
 924 static void
 925 fz_bidi_reorder_span(fz_text_span *span)
 926 {
 927         int a, b, dir, curdir;
 928
 929         a = 0;
 930         curdir = 1;
 931         for (b = 0; b < span->len; b++)
 932         {
 933                 dir = fz_bidi_direction(ucdn_get_bidi_class(span->text[b].c), curdir);
 934                 if (dir != curdir)
 935                 {
 936                         fz_bidi_reorder_run(span, a, b, curdir);
 937                         curdir = dir;
 938                         a = b;
 939                 }
 940         }
 941         fz_bidi_reorder_run(span, a, b, curdir);
 942 }
 943
 944 static void
 945 fz_bidi_reorder_text_page(fz_context *ctx, fz_text_page *page)
 946 {
 947         fz_page_block *pageblock;
 948         fz_text_block *block;
 949         fz_text_line *line;
 950         fz_text_span *span;
 951
 952         for (pageblock = page->blocks; pageblock < page->blocks + page->len; pageblock++)
 953                 if (pageblock->type == FZ_PAGE_BLOCK_TEXT)
 954                         for (block = pageblock->u.text, line = block->lines; line < block->lines + block->len; line++)
 955                                 for (span = line->first_span; span; span = span->next)
 956                                         fz_bidi_reorder_span(span);
 957 }
 958
 959 static void
 960 fz_text_begin_page(fz_device *dev, const fz_rect *mediabox, const fz_matrix *ctm)
 961 {
 962         fz_context *ctx = dev->ctx;
 963         fz_text_device *tdev = dev->user;
 964
 965         if (tdev->page->len)
 966         {
 967                 tdev->page->next = fz_new_text_page(ctx);
 968                 tdev->page = tdev->page->next;
 969         }
 970
 971         tdev->page->mediabox = *mediabox;
 972         fz_transform_rect(&tdev->page->mediabox, ctm);
 973
 974         tdev->spans = new_span_soup(ctx);
 975 }
 976
 977 static void
 978 fz_text_end_page(fz_device *dev)
 979 {
 980         fz_context *ctx = dev->ctx;
 981         fz_text_device *tdev = dev->user;
 982
 983         add_span_to_soup(tdev->spans, tdev->cur_span);
 984         tdev->cur_span = NULL;
 985
 986         strain_soup(ctx, tdev);
 987         free_span_soup(tdev->spans);
 988         tdev->spans = NULL;
 989
 990         /* TODO: smart sorting of blocks in reading order */
 991         /* TODO: unicode NFC normalization */
 992
 993         fz_bidi_reorder_text_page(ctx, tdev->page);
 994 }
 995
 996 static void
 997 fz_text_free_user(fz_device *dev)
 998 {
 999         fz_text_device *tdev = dev->user;
1000         free_span_soup(tdev->spans);
1001         fz_free(dev->ctx, tdev);
1002 }
1003
1004 fz_device *
1005 fz_new_text_device(fz_context *ctx, fz_text_sheet *sheet, fz_text_page *page)
1006 {
1007         fz_device *dev;
1008
1009         fz_text_device *tdev = fz_malloc_struct(ctx, fz_text_device);
1010         tdev->sheet = sheet;
1011         tdev->page = page;
1012         tdev->spans = NULL;
1013         tdev->cur_span = NULL;
1014         tdev->lastchar = ' ';
1015
1016         dev = fz_new_device(ctx, tdev);
1017         dev->hints = FZ_IGNORE_IMAGE | FZ_IGNORE_SHADE;
1018         dev->begin_page = fz_text_begin_page;
1019         dev->end_page = fz_text_end_page;
1020         dev->free_user = fz_text_free_user;
1021         dev->fill_text = fz_text_fill_text;
1022         dev->stroke_text = fz_text_stroke_text;
1023         dev->clip_text = fz_text_clip_text;
1024         dev->clip_stroke_text = fz_text_clip_stroke_text;
1025         dev->ignore_text = fz_text_ignore_text;
1026         dev->fill_image = fz_text_fill_image;
1027         dev->fill_image_mask = fz_text_fill_image_mask;
1028
1029         return dev;
1030 }