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