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