1from fontTools.misc.roundTools import noRound, otRound
2from fontTools.ttLib.tables import otTables as ot
3from fontTools.varLib.models import supportScalar
4from fontTools.varLib.builder import (buildVarRegionList, buildVarStore,
5				      buildVarRegion, buildVarData)
6from functools import partial
7from collections import defaultdict
8
9
10def _getLocationKey(loc):
11	return tuple(sorted(loc.items(), key=lambda kv: kv[0]))
12
13
14class OnlineVarStoreBuilder(object):
15
16	def __init__(self, axisTags):
17		self._axisTags = axisTags
18		self._regionMap = {}
19		self._regionList = buildVarRegionList([], axisTags)
20		self._store = buildVarStore(self._regionList, [])
21		self._data = None
22		self._model = None
23		self._supports = None
24		self._varDataIndices = {}
25		self._varDataCaches = {}
26		self._cache = {}
27
28	def setModel(self, model):
29		self.setSupports(model.supports)
30		self._model = model
31
32	def setSupports(self, supports):
33		self._model = None
34		self._supports = list(supports)
35		if not self._supports[0]:
36			del self._supports[0] # Drop base master support
37		self._cache = {}
38		self._data = None
39
40	def finish(self, optimize=True):
41		self._regionList.RegionCount = len(self._regionList.Region)
42		self._store.VarDataCount = len(self._store.VarData)
43		for data in self._store.VarData:
44			data.ItemCount = len(data.Item)
45			data.calculateNumShorts(optimize=optimize)
46		return self._store
47
48	def _add_VarData(self):
49		regionMap = self._regionMap
50		regionList = self._regionList
51
52		regions = self._supports
53		regionIndices = []
54		for region in regions:
55			key = _getLocationKey(region)
56			idx = regionMap.get(key)
57			if idx is None:
58				varRegion = buildVarRegion(region, self._axisTags)
59				idx = regionMap[key] = len(regionList.Region)
60				regionList.Region.append(varRegion)
61			regionIndices.append(idx)
62
63		# Check if we have one already...
64		key = tuple(regionIndices)
65		varDataIdx = self._varDataIndices.get(key)
66		if varDataIdx is not None:
67			self._outer = varDataIdx
68			self._data = self._store.VarData[varDataIdx]
69			self._cache = self._varDataCaches[key]
70			if len(self._data.Item) == 0xFFFF:
71				# This is full.  Need new one.
72				varDataIdx = None
73
74		if varDataIdx is None:
75			self._data = buildVarData(regionIndices, [], optimize=False)
76			self._outer = len(self._store.VarData)
77			self._store.VarData.append(self._data)
78			self._varDataIndices[key] = self._outer
79			if key not in self._varDataCaches:
80				self._varDataCaches[key] = {}
81			self._cache = self._varDataCaches[key]
82
83
84	def storeMasters(self, master_values):
85		deltas = self._model.getDeltas(master_values, round=round)
86		base = deltas.pop(0)
87		return base, self.storeDeltas(deltas, round=noRound)
88
89	def storeDeltas(self, deltas, *, round=round):
90		deltas = [round(d) for d in deltas]
91		if len(deltas) == len(self._supports) + 1:
92			deltas = tuple(deltas[1:])
93		else:
94			assert len(deltas) == len(self._supports)
95			deltas = tuple(deltas)
96
97		varIdx = self._cache.get(deltas)
98		if varIdx is not None:
99			return varIdx
100
101		if not self._data:
102			self._add_VarData()
103		inner = len(self._data.Item)
104		if inner == 0xFFFF:
105			# Full array. Start new one.
106			self._add_VarData()
107			return self.storeDeltas(deltas)
108		self._data.addItem(deltas, round=noRound)
109
110		varIdx = (self._outer << 16) + inner
111		self._cache[deltas] = varIdx
112		return varIdx
113
114def VarData_addItem(self, deltas, *, round=round):
115	deltas = [round(d) for d in deltas]
116
117	countUs = self.VarRegionCount
118	countThem = len(deltas)
119	if countUs + 1 == countThem:
120		deltas = tuple(deltas[1:])
121	else:
122		assert countUs == countThem, (countUs, countThem)
123		deltas = tuple(deltas)
124	self.Item.append(list(deltas))
125	self.ItemCount = len(self.Item)
126
127ot.VarData.addItem = VarData_addItem
128
129def VarRegion_get_support(self, fvar_axes):
130	return {
131		fvar_axes[i].axisTag: (reg.StartCoord,reg.PeakCoord,reg.EndCoord)
132		for i, reg in enumerate(self.VarRegionAxis)
133		if reg.PeakCoord != 0
134	}
135
136ot.VarRegion.get_support = VarRegion_get_support
137
138class VarStoreInstancer(object):
139
140	def __init__(self, varstore, fvar_axes, location={}):
141		self.fvar_axes = fvar_axes
142		assert varstore is None or varstore.Format == 1
143		self._varData = varstore.VarData if varstore else []
144		self._regions = varstore.VarRegionList.Region if varstore else []
145		self.setLocation(location)
146
147	def setLocation(self, location):
148		self.location = dict(location)
149		self._clearCaches()
150
151	def _clearCaches(self):
152		self._scalars = {}
153
154	def _getScalar(self, regionIdx):
155		scalar = self._scalars.get(regionIdx)
156		if scalar is None:
157			support = self._regions[regionIdx].get_support(self.fvar_axes)
158			scalar = supportScalar(self.location, support)
159			self._scalars[regionIdx] = scalar
160		return scalar
161
162	@staticmethod
163	def interpolateFromDeltasAndScalars(deltas, scalars):
164		delta = 0.
165		for d,s in zip(deltas, scalars):
166			if not s: continue
167			delta += d * s
168		return delta
169
170	def __getitem__(self, varidx):
171		major, minor = varidx >> 16, varidx & 0xFFFF
172		varData = self._varData
173		scalars = [self._getScalar(ri) for ri in varData[major].VarRegionIndex]
174		deltas = varData[major].Item[minor]
175		return self.interpolateFromDeltasAndScalars(deltas, scalars)
176
177	def interpolateFromDeltas(self, varDataIndex, deltas):
178		varData = self._varData
179		scalars = [self._getScalar(ri) for ri in
180					varData[varDataIndex].VarRegionIndex]
181		return self.interpolateFromDeltasAndScalars(deltas, scalars)
182
183
184#
185# Optimizations
186#
187# retainFirstMap - If true, major 0 mappings are retained. Deltas for unused indices are zeroed
188# advIdxes - Set of major 0 indices for advance deltas to be listed first. Other major 0 indices follow.
189
190def VarStore_subset_varidxes(self, varIdxes, optimize=True, retainFirstMap=False, advIdxes=set()):
191
192	# Sort out used varIdxes by major/minor.
193	used = {}
194	for varIdx in varIdxes:
195		major = varIdx >> 16
196		minor = varIdx & 0xFFFF
197		d = used.get(major)
198		if d is None:
199			d = used[major] = set()
200		d.add(minor)
201	del varIdxes
202
203	#
204	# Subset VarData
205	#
206
207	varData = self.VarData
208	newVarData = []
209	varDataMap = {}
210	for major,data in enumerate(varData):
211		usedMinors = used.get(major)
212		if usedMinors is None:
213			continue
214		newMajor = len(newVarData)
215		newVarData.append(data)
216
217		items = data.Item
218		newItems = []
219		if major == 0 and retainFirstMap:
220			for minor in range(len(items)):
221				newItems.append(items[minor] if minor in usedMinors else [0] * len(items[minor]))
222				varDataMap[minor] = minor
223		else:
224			if major == 0:
225				minors = sorted(advIdxes) + sorted(usedMinors - advIdxes)
226			else:
227				minors = sorted(usedMinors)
228			for minor in minors:
229				newMinor = len(newItems)
230				newItems.append(items[minor])
231				varDataMap[(major<<16)+minor] = (newMajor<<16)+newMinor
232
233		data.Item = newItems
234		data.ItemCount = len(data.Item)
235
236		data.calculateNumShorts(optimize=optimize)
237
238	self.VarData = newVarData
239	self.VarDataCount = len(self.VarData)
240
241	self.prune_regions()
242
243	return varDataMap
244
245ot.VarStore.subset_varidxes = VarStore_subset_varidxes
246
247def VarStore_prune_regions(self):
248	"""Remove unused VarRegions."""
249	#
250	# Subset VarRegionList
251	#
252
253	# Collect.
254	usedRegions = set()
255	for data in self.VarData:
256		usedRegions.update(data.VarRegionIndex)
257	# Subset.
258	regionList = self.VarRegionList
259	regions = regionList.Region
260	newRegions = []
261	regionMap = {}
262	for i in sorted(usedRegions):
263		regionMap[i] = len(newRegions)
264		newRegions.append(regions[i])
265	regionList.Region = newRegions
266	regionList.RegionCount = len(regionList.Region)
267	# Map.
268	for data in self.VarData:
269		data.VarRegionIndex = [regionMap[i] for i in data.VarRegionIndex]
270
271ot.VarStore.prune_regions = VarStore_prune_regions
272
273
274def _visit(self, func):
275	"""Recurse down from self, if type of an object is ot.Device,
276	call func() on it.  Works on otData-style classes."""
277
278	if type(self) == ot.Device:
279		func(self)
280
281	elif isinstance(self, list):
282		for that in self:
283			_visit(that, func)
284
285	elif hasattr(self, 'getConverters') and not hasattr(self, 'postRead'):
286		for conv in self.getConverters():
287			that = getattr(self, conv.name, None)
288			if that is not None:
289				_visit(that, func)
290
291	elif isinstance(self, ot.ValueRecord):
292		for that in self.__dict__.values():
293			_visit(that, func)
294
295def _Device_recordVarIdx(self, s):
296	"""Add VarIdx in this Device table (if any) to the set s."""
297	if self.DeltaFormat == 0x8000:
298		s.add((self.StartSize<<16)+self.EndSize)
299
300def Object_collect_device_varidxes(self, varidxes):
301	adder = partial(_Device_recordVarIdx, s=varidxes)
302	_visit(self, adder)
303
304ot.GDEF.collect_device_varidxes = Object_collect_device_varidxes
305ot.GPOS.collect_device_varidxes = Object_collect_device_varidxes
306
307def _Device_mapVarIdx(self, mapping, done):
308	"""Map VarIdx in this Device table (if any) through mapping."""
309	if id(self) in done:
310		return
311	done.add(id(self))
312	if self.DeltaFormat == 0x8000:
313		varIdx = mapping[(self.StartSize<<16)+self.EndSize]
314		self.StartSize = varIdx >> 16
315		self.EndSize = varIdx & 0xFFFF
316
317def Object_remap_device_varidxes(self, varidxes_map):
318	mapper = partial(_Device_mapVarIdx, mapping=varidxes_map, done=set())
319	_visit(self, mapper)
320
321ot.GDEF.remap_device_varidxes = Object_remap_device_varidxes
322ot.GPOS.remap_device_varidxes = Object_remap_device_varidxes
323
324
325class _Encoding(object):
326
327	def __init__(self, chars):
328		self.chars = chars
329		self.width = self._popcount(chars)
330		self.overhead = self._characteristic_overhead(chars)
331		self.items = set()
332
333	def append(self, row):
334		self.items.add(row)
335
336	def extend(self, lst):
337		self.items.update(lst)
338
339	def get_room(self):
340		"""Maximum number of bytes that can be added to characteristic
341		while still being beneficial to merge it into another one."""
342		count = len(self.items)
343		return max(0, (self.overhead - 1) // count - self.width)
344	room = property(get_room)
345
346	@property
347	def gain(self):
348		"""Maximum possible byte gain from merging this into another
349		characteristic."""
350		count = len(self.items)
351		return max(0, self.overhead - count * (self.width + 1))
352
353	def sort_key(self):
354		return self.width, self.chars
355
356	def __len__(self):
357		return len(self.items)
358
359	def can_encode(self, chars):
360		return not (chars & ~self.chars)
361
362	def __sub__(self, other):
363		return self._popcount(self.chars & ~other.chars)
364
365	@staticmethod
366	def _popcount(n):
367		# Apparently this is the fastest native way to do it...
368		# https://stackoverflow.com/a/9831671
369		return bin(n).count('1')
370
371	@staticmethod
372	def _characteristic_overhead(chars):
373		"""Returns overhead in bytes of encoding this characteristic
374		as a VarData."""
375		c = 6
376		while chars:
377			if chars & 0b1111:
378				c += 2
379			chars >>= 4
380		return c
381
382	def _find_yourself_best_new_encoding(self, done_by_width):
383		self.best_new_encoding = None
384		for new_width in range(self.width+1, self.width+self.room+1):
385			for new_encoding in done_by_width[new_width]:
386				if new_encoding.can_encode(self.chars):
387					break
388			else:
389				new_encoding = None
390			self.best_new_encoding = new_encoding
391
392
393class _EncodingDict(dict):
394
395	def __missing__(self, chars):
396		r = self[chars] = _Encoding(chars)
397		return r
398
399	def add_row(self, row):
400		chars = self._row_characteristics(row)
401		self[chars].append(row)
402
403	@staticmethod
404	def _row_characteristics(row):
405		"""Returns encoding characteristics for a row."""
406		longWords = False
407
408		chars = 0
409		i = 1
410		for v in row:
411			if v:
412				chars += i
413			if not (-128 <= v <= 127):
414				chars += i * 0b0010
415			if not (-32768 <= v <= 32767):
416				longWords = True
417				break
418			i <<= 4
419
420		if longWords:
421			# Redo; only allow 2byte/4byte encoding
422			chars = 0
423			i = 1
424			for v in row:
425				if v:
426					chars += i * 0b0011
427				if not (-32768 <= v <= 32767):
428					chars += i * 0b1100
429				i <<= 4
430
431		return chars
432
433
434def VarStore_optimize(self):
435	"""Optimize storage. Returns mapping from old VarIdxes to new ones."""
436
437	# TODO
438	# Check that no two VarRegions are the same; if they are, fold them.
439
440	n = len(self.VarRegionList.Region) # Number of columns
441	zeroes = [0] * n
442
443	front_mapping = {} # Map from old VarIdxes to full row tuples
444
445	encodings = _EncodingDict()
446
447	# Collect all items into a set of full rows (with lots of zeroes.)
448	for major,data in enumerate(self.VarData):
449		regionIndices = data.VarRegionIndex
450
451		for minor,item in enumerate(data.Item):
452
453			row = list(zeroes)
454			for regionIdx,v in zip(regionIndices, item):
455				row[regionIdx] += v
456			row = tuple(row)
457
458			encodings.add_row(row)
459			front_mapping[(major<<16)+minor] = row
460
461	# Separate encodings that have no gain (are decided) and those having
462	# possible gain (possibly to be merged into others.)
463	encodings = sorted(encodings.values(), key=_Encoding.__len__, reverse=True)
464	done_by_width = defaultdict(list)
465	todo = []
466	for encoding in encodings:
467		if not encoding.gain:
468			done_by_width[encoding.width].append(encoding)
469		else:
470			todo.append(encoding)
471
472	# For each encoding that is possibly to be merged, find the best match
473	# in the decided encodings, and record that.
474	todo.sort(key=_Encoding.get_room)
475	for encoding in todo:
476		encoding._find_yourself_best_new_encoding(done_by_width)
477
478	# Walk through todo encodings, for each, see if merging it with
479	# another todo encoding gains more than each of them merging with
480	# their best decided encoding. If yes, merge them and add resulting
481	# encoding back to todo queue.  If not, move the enconding to decided
482	# list.  Repeat till done.
483	while todo:
484		encoding = todo.pop()
485		best_idx = None
486		best_gain = 0
487		for i,other_encoding in enumerate(todo):
488			combined_chars = other_encoding.chars | encoding.chars
489			combined_width = _Encoding._popcount(combined_chars)
490			combined_overhead = _Encoding._characteristic_overhead(combined_chars)
491			combined_gain = (
492					+ encoding.overhead
493					+ other_encoding.overhead
494					- combined_overhead
495					- (combined_width - encoding.width) * len(encoding)
496					- (combined_width - other_encoding.width) * len(other_encoding)
497					)
498			this_gain = 0 if encoding.best_new_encoding is None else (
499						+ encoding.overhead
500						- (encoding.best_new_encoding.width - encoding.width) * len(encoding)
501					)
502			other_gain = 0 if other_encoding.best_new_encoding is None else (
503						+ other_encoding.overhead
504						- (other_encoding.best_new_encoding.width - other_encoding.width) * len(other_encoding)
505					)
506			separate_gain = this_gain + other_gain
507
508			if combined_gain > separate_gain:
509				best_idx = i
510				best_gain = combined_gain - separate_gain
511
512		if best_idx is None:
513			# Encoding is decided as is
514			done_by_width[encoding.width].append(encoding)
515		else:
516			other_encoding = todo[best_idx]
517			combined_chars = other_encoding.chars | encoding.chars
518			combined_encoding = _Encoding(combined_chars)
519			combined_encoding.extend(encoding.items)
520			combined_encoding.extend(other_encoding.items)
521			combined_encoding._find_yourself_best_new_encoding(done_by_width)
522			del todo[best_idx]
523			todo.append(combined_encoding)
524
525	# Assemble final store.
526	back_mapping = {} # Mapping from full rows to new VarIdxes
527	encodings = sum(done_by_width.values(), [])
528	encodings.sort(key=_Encoding.sort_key)
529	self.VarData = []
530	for major,encoding in enumerate(encodings):
531		data = ot.VarData()
532		self.VarData.append(data)
533		data.VarRegionIndex = range(n)
534		data.VarRegionCount = len(data.VarRegionIndex)
535		data.Item = sorted(encoding.items)
536		for minor,item in enumerate(data.Item):
537			back_mapping[item] = (major<<16)+minor
538
539	# Compile final mapping.
540	varidx_map = {}
541	for k,v in front_mapping.items():
542		varidx_map[k] = back_mapping[v]
543
544	# Remove unused regions.
545	self.prune_regions()
546
547	# Recalculate things and go home.
548	self.VarRegionList.RegionCount = len(self.VarRegionList.Region)
549	self.VarDataCount = len(self.VarData)
550	for data in self.VarData:
551		data.ItemCount = len(data.Item)
552		data.optimize()
553
554	return varidx_map
555
556ot.VarStore.optimize = VarStore_optimize
557
558
559def main(args=None):
560	"""Optimize a font's GDEF variation store"""
561	from argparse import ArgumentParser
562	from fontTools import configLogger
563	from fontTools.ttLib import TTFont
564	from fontTools.ttLib.tables.otBase import OTTableWriter
565
566	parser = ArgumentParser(prog='varLib.varStore', description= main.__doc__)
567	parser.add_argument('fontfile')
568	parser.add_argument('outfile', nargs='?')
569	options = parser.parse_args(args)
570
571	# TODO: allow user to configure logging via command-line options
572	configLogger(level="INFO")
573
574	fontfile = options.fontfile
575	outfile = options.outfile
576
577	font = TTFont(fontfile)
578	gdef = font['GDEF']
579	store = gdef.table.VarStore
580
581	writer = OTTableWriter()
582	store.compile(writer, font)
583	size = len(writer.getAllData())
584	print("Before: %7d bytes" % size)
585
586	varidx_map = store.optimize()
587
588	gdef.table.remap_device_varidxes(varidx_map)
589	if 'GPOS' in font:
590		font['GPOS'].table.remap_device_varidxes(varidx_map)
591
592	writer = OTTableWriter()
593	store.compile(writer, font)
594	size = len(writer.getAllData())
595	print("After:  %7d bytes" % size)
596
597	if outfile is not None:
598		font.save(outfile)
599
600
601if __name__ == "__main__":
602	import sys
603	if len(sys.argv) > 1:
604		sys.exit(main())
605	import doctest
606	sys.exit(doctest.testmod().failed)
607