// Copyright (C) 2004-2021 Artifex Software, Inc.

//

// This file is part of MuPDF.

//

// MuPDF is free software: you can redistribute it and/or modify it under the

// terms of the GNU Affero General Public License as published by the Free

// Software Foundation, either version 3 of the License, or (at your option)

// any later version.

//

// MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY

// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

// FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more

// details.

//

// You should have received a copy of the GNU Affero General Public License

// along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>

//

// Alternative licensing terms are available from the licensor.

// For commercial licensing, see <https://www.artifex.com/> or contact

// Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,

// CA 94129, USA, for further information.

#include "mupdf/fitz.h"

#include "draw-imp.h"

#include "glyph-imp.h"

#include "pixmap-imp.h"

#include <string.h>

#include <math.h>

#define MAX_GLYPH_SIZE 256

#define MAX_CACHE_SIZE (1024*1024)

#define GLYPH_HASH_LEN 509

typedef struct

{

  fz_font *font;

  int a, b;

  int c, d;

  unsigned short gid;

  unsigned char e, f;

  int aa;

} fz_glyph_key;

typedef struct fz_glyph_cache_entry

{

  fz_glyph_key key;

  unsigned hash;

  struct fz_glyph_cache_entry *lru_prev;

  struct fz_glyph_cache_entry *lru_next;

  struct fz_glyph_cache_entry *bucket_next;

  struct fz_glyph_cache_entry *bucket_prev;

  fz_glyph *val;

} fz_glyph_cache_entry;

struct fz_glyph_cache

{

  int refs;

  size_t total;

#ifndef NDEBUG

  int num_evictions;

  ptrdiff_t evicted;

#endif

  fz_glyph_cache_entry *entry[GLYPH_HASH_LEN];

  fz_glyph_cache_entry *lru_head;

  fz_glyph_cache_entry *lru_tail;

};

static size_t

fz_glyph_size(fz_context *ctx, fz_glyph *glyph)

{

  if (glyph == NULL)

    return 0;

  return sizeof(fz_glyph) + glyph->size + fz_pixmap_size(ctx, glyph->pixmap);

}

void

fz_new_glyph_cache_context(fz_context *ctx)

{

  fz_glyph_cache *cache;

  cache = fz_malloc_struct(ctx, fz_glyph_cache);

  cache->total = 0;

  cache->refs = 1;

  ctx->glyph_cache = cache;

}

static void

drop_glyph_cache_entry(fz_context *ctx, fz_glyph_cache_entry *entry)

{

  fz_glyph_cache *cache = ctx->glyph_cache;

  if (entry->lru_next)

    entry->lru_next->lru_prev = entry->lru_prev;

  else

    cache->lru_tail = entry->lru_prev;

  if (entry->lru_prev)

    entry->lru_prev->lru_next = entry->lru_next;

  else

    cache->lru_head = entry->lru_next;

  cache->total -= fz_glyph_size(ctx, entry->val);

  if (entry->bucket_next)

    entry->bucket_next->bucket_prev = entry->bucket_prev;

  if (entry->bucket_prev)

    entry->bucket_prev->bucket_next = entry->bucket_next;

  else

    cache->entry[entry->hash] = entry->bucket_next;

  fz_drop_font(ctx, entry->key.font);

  fz_drop_glyph(ctx, entry->val);

  fz_free(ctx, entry);

}

/* The glyph cache lock is always held when this function is called. */

static void

do_purge(fz_context *ctx)

{

  fz_glyph_cache *cache = ctx->glyph_cache;

  int i;

  for (i = 0; i < GLYPH_HASH_LEN; i++)

  {

    while (cache->entry[i])

      drop_glyph_cache_entry(ctx, cache->entry[i]);

  }

  cache->total = 0;

}

void

fz_purge_glyph_cache(fz_context *ctx)

{

  fz_lock(ctx, FZ_LOCK_GLYPHCACHE);

  do_purge(ctx);

  fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);

}

void

fz_drop_glyph_cache_context(fz_context *ctx)

{

  if (!ctx || !ctx->glyph_cache)

    return;

  fz_lock(ctx, FZ_LOCK_GLYPHCACHE);

  ctx->glyph_cache->refs--;

  if (ctx->glyph_cache->refs == 0)

  {

    do_purge(ctx);

    fz_free(ctx, ctx->glyph_cache);

    ctx->glyph_cache = NULL;

  }

  fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);

}

fz_glyph_cache *

fz_keep_glyph_cache(fz_context *ctx)

{

  fz_lock(ctx, FZ_LOCK_GLYPHCACHE);

  ctx->glyph_cache->refs++;

  fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);

  return ctx->glyph_cache;

}

float

fz_subpixel_adjust(fz_context *ctx, fz_matrix *ctm, fz_matrix *subpix_ctm, unsigned char *qe, unsigned char *qf)

{

  float size = fz_matrix_expansion(*ctm);

  int q, hq, vq, qmin;

  float pix_e, pix_f, r, hr, vr, rmin;

  /* Quantise the subpixel positions. First, in the direction of

   * movement (i.e. normally X). We never need more than 4 subpixel

   * positions for glyphs - arguably even that is too much.

   * Suppress this as we get larger, because it makes less impact. */

  if (size >= 48)

    q = 0, r = 0.5f;

  else if (size >= 24)

    q = 128, r = 0.25f;

  else

    q = 192, r = 0.125f;

  /* Then in the 'downward' direction (normally Y). */

  if (size >= 8)

    qmin = 0, rmin = 0.5f;

  else if (size >= 4)

    qmin = 128, rmin =  0.25f;

  else

    qmin = 192, rmin = 0.125f;

  /* Suppress subpixel antialiasing in y axis if we have a horizontal

   * matrix, and in x axis if we have a vertical matrix, unless we're

   * really small. */

  hq = vq = q;

  hr = vr = r;

  if (ctm->a == 0 && ctm->d == 0)

    hq = qmin, hr = rmin;

  if (ctm->b == 0 && ctm->c == 0)

    vq = qmin, vr = rmin;

  /* Split translation into pixel and subpixel parts */

  subpix_ctm->a = ctm->a;

  subpix_ctm->b = ctm->b;

  subpix_ctm->c = ctm->c;

  subpix_ctm->d = ctm->d;

  subpix_ctm->e = ctm->e + hr;

  pix_e = floorf(subpix_ctm->e);

  subpix_ctm->e -= pix_e;

  subpix_ctm->f = ctm->f + vr;

  pix_f = floorf(subpix_ctm->f);

  subpix_ctm->f -= pix_f;

  /* Quantise the subpixel part */

  *qe = (int)(subpix_ctm->e * 256) & hq;

  subpix_ctm->e = *qe / 256.0f;

  *qf = (int)(subpix_ctm->f * 256) & vq;

  subpix_ctm->f = *qf / 256.0f;

  /* Reassemble the complete translation */

  ctm->e = subpix_ctm->e + pix_e;

  ctm->f = subpix_ctm->f + pix_f;

  return size;

}

fz_glyph *

fz_render_stroked_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix *trm, fz_matrix ctm, fz_colorspace *model, const fz_stroke_state *stroke, const fz_irect *scissor, int aa)

{

  if (fz_font_ft_face(ctx, font))

  {

    fz_matrix subpix_trm;

    unsigned char qe, qf;

    if (stroke->dash_len > 0)

      return NULL;

    (void)fz_subpixel_adjust(ctx, trm, &subpix_trm, &qe, &qf);

    return fz_render_ft_stroked_glyph(ctx, font, gid, subpix_trm, ctm, stroke, aa);

  }

  return fz_render_glyph(ctx, font, gid, trm, model, scissor, 1, aa);

}

static unsigned do_hash(unsigned char *s, int len)

{

  unsigned val = 0;

  int i;

  for (i = 0; i < len; i++)

  {

    val += s[i];

    val += (val << 10);

    val ^= (val >> 6);

  }

  val += (val << 3);

  val ^= (val >> 11);

  val += (val << 15);

  return val;

}

static inline void

move_to_front(fz_glyph_cache *cache, fz_glyph_cache_entry *entry)

{

  if (entry->lru_prev == NULL)

    return; /* At front already */

  /* Unlink */

  entry->lru_prev->lru_next = entry->lru_next;

  if (entry->lru_next)

    entry->lru_next->lru_prev = entry->lru_prev;

  else

    cache->lru_tail = entry->lru_prev;

  /* Relink */

  entry->lru_next = cache->lru_head;

  if (entry->lru_next)

    entry->lru_next->lru_prev = entry;

  cache->lru_head = entry;

  entry->lru_prev = NULL;

}

fz_glyph *

fz_render_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix *ctm, fz_colorspace *model, const fz_irect *scissor, int alpha, int aa)

{

  fz_glyph_cache *cache;

  fz_glyph_key key;

  fz_matrix subpix_ctm;

  fz_irect subpix_scissor;

  float size;

  fz_glyph *val;

  int do_cache, locked, caching;

  fz_glyph_cache_entry *entry;

  unsigned hash;

  int is_ft_font = !!fz_font_ft_face(ctx, font);

  fz_var(locked);

  fz_var(caching);

  fz_var(val);

  memset(&key, 0, sizeof key);

  size = fz_subpixel_adjust(ctx, ctm, &subpix_ctm, &key.e, &key.f);

  if (size <= MAX_GLYPH_SIZE)

  {

    scissor = &fz_infinite_irect;

    do_cache = 1;

  }

  else

  {

    if (is_ft_font)

      return NULL;

    subpix_scissor.x0 = scissor->x0 - floorf(ctm->e);

    subpix_scissor.y0 = scissor->y0 - floorf(ctm->f);

    subpix_scissor.x1 = scissor->x1 - floorf(ctm->e);

    subpix_scissor.y1 = scissor->y1 - floorf(ctm->f);

    scissor = &subpix_scissor;

    do_cache = 0;

  }

  cache = ctx->glyph_cache;

  key.font = font;

  key.gid = gid;

  key.a = subpix_ctm.a * 65536;

  key.b = subpix_ctm.b * 65536;

  key.c = subpix_ctm.c * 65536;

  key.d = subpix_ctm.d * 65536;

  key.aa = aa;

  hash = do_hash((unsigned char *)&key, sizeof(key)) % GLYPH_HASH_LEN;

  fz_lock(ctx, FZ_LOCK_GLYPHCACHE);

  entry = cache->entry[hash];

  while (entry)

  {

    if (memcmp(&entry->key, &key, sizeof(key)) == 0)

    {

      move_to_front(cache, entry);

      val = fz_keep_glyph(ctx, entry->val);

      fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);

      return val;

    }

    entry = entry->bucket_next;

  }

  locked = 1;

  caching = 0;

  val = NULL;

  fz_try(ctx)

  {

    if (is_ft_font)

    {

      val = fz_render_ft_glyph(ctx, font, gid, subpix_ctm, aa);

    }

    else if (fz_font_t3_procs(ctx, font))

    {

      /* We drop the glyphcache here, and execute the t3

       * glyph code. The danger here is that some other

       * thread will come along, and want the same glyph

       * too. If it does, we may both end up rendering

       * pixmaps. We cope with this later on, by ensuring

       * that only one gets inserted into the cache. If

       * we insert ours to find one already there, we

       * abandon ours, and use the one there already.

       */

      fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);

      locked = 0;

      val = fz_render_t3_glyph(ctx, font, gid, subpix_ctm, model, scissor, aa);

      fz_lock(ctx, FZ_LOCK_GLYPHCACHE);

      locked = 1;

    }

    else

    {

      fz_warn(ctx, "assert: uninitialized font structure");

    }

    if (val && do_cache)

    {

      if (val->w < MAX_GLYPH_SIZE && val->h < MAX_GLYPH_SIZE)

      {

        /* If we throw an exception whilst caching,

         * just ignore the exception and carry on. */

        caching = 1;

        if (!is_ft_font)

        {

          /* We had to unlock. Someone else might

           * have rendered in the meantime */

          entry = cache->entry[hash];

          while (entry)

          {

            if (memcmp(&entry->key, &key, sizeof(key)) == 0)

            {

              fz_drop_glyph(ctx, val);

              move_to_front(cache, entry);

              val = fz_keep_glyph(ctx, entry->val);

              goto unlock_and_return_val;

            }

            entry = entry->bucket_next;

          }

        }

        entry = fz_malloc_struct(ctx, fz_glyph_cache_entry);

        entry->key = key;

        entry->hash = hash;

        entry->bucket_next = cache->entry[hash];

        if (entry->bucket_next)

          entry->bucket_next->bucket_prev = entry;

        cache->entry[hash] = entry;

        entry->val = fz_keep_glyph(ctx, val);

        fz_keep_font(ctx, key.font);

        entry->lru_next = cache->lru_head;

        if (entry->lru_next)

          entry->lru_next->lru_prev = entry;

        else

          cache->lru_tail = entry;

        cache->lru_head = entry;

        cache->total += fz_glyph_size(ctx, val);

        while (cache->total > MAX_CACHE_SIZE)

        {

#ifndef NDEBUG

          cache->num_evictions++;

          cache->evicted += fz_glyph_size(ctx, cache->lru_tail->val);

#endif

          drop_glyph_cache_entry(ctx, cache->lru_tail);

        }

      }

    }

unlock_and_return_val:

    {

    }

  }

  fz_always(ctx)

  {

    if (locked)

      fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);

  }

  fz_catch(ctx)

  {

    if (caching)

      fz_warn(ctx, "cannot encache glyph; continuing");

    else

      fz_rethrow(ctx);

  }

  return val;

}

fz_pixmap *

fz_render_glyph_pixmap(fz_context *ctx, fz_font *font, int gid, fz_matrix *ctm, const fz_irect *scissor, int aa)

{

  fz_pixmap *val = NULL;

  unsigned char qe, qf;

  fz_matrix subpix_ctm;

  float size = fz_subpixel_adjust(ctx, ctm, &subpix_ctm, &qe, &qf);

  int is_ft_font = !!fz_font_ft_face(ctx, font);

  if (size <= MAX_GLYPH_SIZE)

  {

    scissor = &fz_infinite_irect;

  }

  else

  {

    if (is_ft_font)

      return NULL;

  }

  if (is_ft_font)

  {

    val = fz_render_ft_glyph_pixmap(ctx, font, gid, subpix_ctm, aa);

  }

  else if (fz_font_t3_procs(ctx, font))

  {

    val = fz_render_t3_glyph_pixmap(ctx, font, gid, subpix_ctm, NULL, scissor, aa);

  }

  else

  {

    fz_warn(ctx, "assert: uninitialized font structure");

    val = NULL;

  }

  return val;

}

void

fz_dump_glyph_cache_stats(fz_context *ctx, fz_output *out)

{

  fz_glyph_cache *cache = ctx->glyph_cache;

  fz_write_printf(ctx, out, "Glyph Cache Size: %zu\n", cache->total);

#ifndef NDEBUG

  fz_write_printf(ctx, out, "Glyph Cache Evictions: %d (%zu bytes)\n", cache->num_evictions, cache->evicted);

#endif

}