Lib/fontTools/cffLib/width.py

# -*- coding: utf-8 -*-

"""T2CharString glyph width optimizer."""

from __future__ import print_function, division, absolute_import
from fontTools.misc.py23 import *
from fontTools.ttLib import TTFont, getTableClass
from collections import defaultdict
from operator import add
from functools import partial, reduce


class missingdict(dict):
	def __init__(self, missing_func):
		self.missing_func = missing_func
	def __missing__(self, v):
		return self.missing_func(v)

def cumSum(f, op=add, start=0, decreasing=False):
	
	keys = sorted(f.keys())
	minx, maxx = keys[0], keys[-1]

	total = reduce(op, f.values(), start)

	if decreasing:
		missing = lambda x: start if x > maxx else total
		domain = range(maxx, minx - 1, -1)
	else:
		missing = lambda x: start if x < minx else total
		domain = range(minx, maxx + 1)

	out = missingdict(missing)

	v = start
	for x in domain:
		v = op(v, f[x])
		out[x] = v

	return out

def byteCost(widths, default, nominal):

	if not hasattr(widths, 'items'):
		d = defaultdict(int)
		for w in widths:
			d[w] += 1
		widths = d

	cost = 0
	for w,freq in widths.items():
		if w == default: continue
		diff = abs(w - nominal)
		if diff <= 107:
			cost += freq
		elif diff <= 1131:
			cost += freq * 2
		else:
			cost += freq * 5
	return cost


def optimizeWidthsBruteforce(widths):
	"""Bruteforce version.  Veeeeeeeeeeeeeeeeery slow.  Only works for smallests of fonts."""

	d = defaultdict(int)
	for w in widths:
		d[w] += 1

	# Maximum number of bytes using default can possibly save
	maxDefaultAdvantage = 5 * max(d.values())

	minw, maxw = min(widths), max(widths)
	domain = list(range(minw, maxw+1))

	bestCostWithoutDefault = min(byteCost(widths, None, nominal) for nominal in domain)

	bestCost = len(widths) * 5 + 1
	for nominal in domain:
		if byteCost(widths, None, nominal) > bestCost + maxDefaultAdvantage:
			continue
		for default in domain:
			cost = byteCost(widths, default, nominal)
			if cost < bestCost:
				bestCost = cost
				bestDefault = default
				bestNominal = nominal

	return bestDefault, bestNominal


def optimizeWidths(widths):
	"""Given a list of glyph widths, or dictionary mapping glyph width to number of
	glyphs having that, returns a tuple of best CFF default and nominal glyph widths.

	This algorithm is linear in UPEM+numGlyphs."""

	if not hasattr(widths, 'items'):
		d = defaultdict(int)
		for w in widths:
			d[w] += 1
		widths = d
	
	keys = sorted(widths.keys())
	minw, maxw = keys[0], keys[-1]
	domain = list(range(minw, maxw+1))

	# Cumulative sum/max forward/backward.
	cumFrqU = cumSum(widths, op=add)
	cumMaxU = cumSum(widths, op=max)
	cumFrqD = cumSum(widths, op=add, decreasing=True)
	cumMaxD = cumSum(widths, op=max, decreasing=True)

	# Cost per nominal choice, without default consideration.
	nomnCostU = missingdict(lambda x: cumFrqU[x] + cumFrqU[x-108] + cumFrqU[x-1132]*3)
	nomnCostD = missingdict(lambda x: cumFrqD[x] + cumFrqD[x+108] + cumFrqD[x+1132]*3)
	nomnCost  = missingdict(lambda x: nomnCostU[x] + nomnCostD[x] - widths[x])

	# Cost-saving per nominal choice, by best default choice.
	dfltCostU = missingdict(lambda x: max(cumMaxU[x], cumMaxU[x-108]*2, cumMaxU[x-1132]*5))
	dfltCostD = missingdict(lambda x: max(cumMaxD[x], cumMaxD[x+108]*2, cumMaxD[x+1132]*5))
	dfltCost  = missingdict(lambda x: max(dfltCostU[x], dfltCostD[x]))

	# Combined cost per nominal choice.
	bestCost  = missingdict(lambda x: nomnCost[x] - dfltCost[x])

	# Best nominal.
	nominal = min(domain, key=lambda x: bestCost[x])

	# Work back the best default.
	bestC = bestCost[nominal]
	dfltC = nomnCost[nominal] - bestCost[nominal]
	ends = []
	if dfltC == dfltCostU[nominal]:
		starts = [nominal, nominal-108, nominal-1131]
		for start in starts:
			while cumMaxU[start] and cumMaxU[start] == cumMaxU[start-1]:
				start -= 1
			ends.append(start)
	else:
		starts = [nominal, nominal+108, nominal+1131]
		for start in starts:
			while cumMaxD[start] and cumMaxD[start] == cumMaxD[start+1]:
				start += 1
			ends.append(start)
	default = min(ends, key=lambda default: byteCost(widths, default, nominal))

	return default, nominal


if __name__ == '__main__':
	import sys
	if len(sys.argv) == 1:
		import doctest
		sys.exit(doctest.testmod().failed)
	for fontfile in sys.argv[1:]:
		font = TTFont(fontfile)
		hmtx = font['hmtx']
		widths = [m[0] for m in hmtx.metrics.values()]
		default, nominal = optimizeWidths(widths)
		print("glyphs=%d default=%d nominal=%d byteCost=%d" % (len(widths), default, nominal, byteCost(widths, default, nominal)))
		#default, nominal = optimizeWidthsBruteforce(widths)
		#print("glyphs=%d default=%d nominal=%d byteCost=%d" % (len(widths), default, nominal, byteCost(widths, default, nominal)))