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