Class: Fontisan::Optimizers::StackTracker

Inherits:
Object
  • Object
show all
Defined in:
lib/fontisan/optimizers/stack_tracker.rb

Overview

Tracks operand stack depth during CharString execution without full interpretation. Used to identify stack-neutral patterns suitable for subroutinization.

A stack-neutral pattern is one where the stack depth is the same before and after the pattern executes. This ensures that replacing the pattern with a subroutine call won’t cause stack underflow/overflow.

Examples:

Basic usage

tracker = StackTracker.new(charstring_bytes)
stack_map = tracker.track
start_depth = stack_map[start_pos]
end_depth = stack_map[end_pos]
is_neutral = (start_depth == end_depth)

See Also:

  • docs/SUBROUTINE_ARCHITECTUREdocs/SUBROUTINE_ARCHITECTURE.md

Constant Summary collapse

OPERATOR_STACK_EFFECTS =

Type 2 CharString operator stack effects Maps operator => [operands_consumed, operands_produced]

{
  # Path construction operators
  hstem: [2, 0],           # y dy hstem
  vstem: [2, 0],           # x dx vstem
  vmoveto: [1, 0],         # dy vmoveto
  rlineto: [-1, 0],        # {dxa dya}+ (variable, pairs)
  hlineto: [-1, 0],        # dx1 {dya dxb}* (variable, alternating)
  vlineto: [-1, 0],        # dy1 {dxb dya}* (variable, alternating)
  rrcurveto: [-1, 0],      # {dxa dya dxb dyb dxc dyc}+ (variable, 6-tuples)
  callsubr: [1, 0],        # subr# callsubr (note: subr may affect stack)
  return: [0, 0],          # return
  endchar: [0, 0],         # endchar
  hstemhm: [2, 0],         # y dy hstemhm
  hintmask: [0, 0],        # hintmask
  cntrmask: [0, 0],        # cntrmask
  rmoveto: [2, 0],         # dx dy rmoveto
  hmoveto: [1, 0],         # dx hmoveto
  vstemhm: [2, 0],         # x dx vstemhm
  rcurveline: [-1, 0],     # {dxa dya dxb dyb dxc dyc}+ dxd dyd (variable)
  rlinecurve: [-1, 0],     # {dxa dya}+ dxb dyb dxc dyc dxd dyd (variable)
  vvcurveto: [-1, 0],      # dx1? {dya dxb dyb dyc}+ (variable)
  hhcurveto: [-1, 0],      # dy1? {dxa dxb dyb dxc}+ (variable)
  shortint: [0, 1],        # (16-bit number)
  callgsubr: [1, 0],       # subr# callgsubr
  vhcurveto: [-1, 0],      # dy1 dx2 dy2 dx3 {dxa dxb dyb dyc dyd dxe dye dxf}* (variable)
  hvcurveto: [-1, 0],      # dx1 dx2 dy2 dy3 {dya dxb dyb dxc dxd dxe dye dyf}* (variable)

  # Arithmetic operators (12 prefix)
  and: [2, 1],             # num1 num2 and
  or: [2, 1],              # num1 num2 or
  not: [1, 1],             # num1 not
  abs: [1, 1],             # num abs
  add: [2, 1],             # num1 num2 add
  sub: [2, 1],             # num1 num2 sub
  div: [2, 1],             # num1 num2 div
  neg: [1, 1],             # num neg
  eq: [2, 1],              # num1 num2 eq
  drop: [1, 0],            # any drop
  put: [2, 0],             # val i put
  get: [1, 1],             # i get
  ifelse: [4, 1],          # v1 v2 s1 s2 ifelse
  random: [0, 1],          # random
  mul: [2, 1],             # num1 num2 mul
  sqrt: [1, 1],            # num sqrt
  dup: [1, 2],             # any dup
  exch: [2, 2],            # any1 any2 exch
  index: [1, 1],           # i index (actually [i+1, i+1])
  roll: [2, 0],            # N J roll (rotates top N elements)

  # Flex operators (12 prefix)
  hflex: [7, 0],           # dx1 dx2 dy2 dx3 dx4 dx5 dx6 hflex
  flex: [13, 0],           # dx1 dy1 dx2 dy2 dx3 dy3 dx4 dy4 dx5 dy5 dx6 dy6 fd flex
  hflex1: [9, 0],          # dx1 dy1 dx2 dy2 dx3 dx4 dx5 dy5 dx6 hflex1
  flex1: [11, 0],          # dx1 dy1 dx2 dy2 dx3 dy3 dx4 dy4 dx5 dy5 d6 flex1
}.freeze
OPERATORS =

Type 2 CharString operator codes

{
  1 => :hstem,
  3 => :vstem,
  4 => :vmoveto,
  5 => :rlineto,
  6 => :hlineto,
  7 => :vlineto,
  8 => :rrcurveto,
  10 => :callsubr,
  11 => :return,
  14 => :endchar,
  18 => :hstemhm,
  19 => :hintmask,
  20 => :cntrmask,
  21 => :rmoveto,
  22 => :hmoveto,
  23 => :vstemhm,
  24 => :rcurveline,
  25 => :rlinecurve,
  26 => :vvcurveto,
  27 => :hhcurveto,
  28 => :shortint,
  29 => :callgsubr,
  30 => :vhcurveto,
  31 => :hvcurveto,
  [12, 3] => :and,
  [12, 4] => :or,
  [12, 5] => :not,
  [12, 9] => :abs,
  [12, 10] => :add,
  [12, 11] => :sub,
  [12, 12] => :div,
  [12, 14] => :neg,
  [12, 15] => :eq,
  [12, 18] => :drop,
  [12, 20] => :put,
  [12, 21] => :get,
  [12, 22] => :ifelse,
  [12, 23] => :random,
  [12, 24] => :mul,
  [12, 26] => :sqrt,
  [12, 27] => :dup,
  [12, 28] => :exch,
  [12, 29] => :index,
  [12, 30] => :roll,
  [12, 34] => :hflex,
  [12, 35] => :flex,
  [12, 36] => :hflex1,
  [12, 37] => :flex1,
}.freeze

Instance Method Summary collapse

Constructor Details

#initialize(charstring) ⇒ StackTracker

Initialize stack tracker

Parameters:

  • charstring (String) —

    CharString bytes to track



136
137
138
139
 
# File 'lib/fontisan/optimizers/stack_tracker.rb', line 136

def initialize(charstring)
  @charstring = charstring
  @stack_depth_map = {}
end

Instance Method Details

#depth_at(position) ⇒ Integer?

Get stack depth at a position

Parameters:

  • position (Integer) —

    byte position

Returns:

  • (Integer, nil) —

    stack depth or nil if not tracked



185
186
187
 
# File 'lib/fontisan/optimizers/stack_tracker.rb', line 185

def depth_at(position)
  @stack_depth_map[position]
end

#stack_neutral?(start_pos, end_pos) ⇒ Boolean

Check if a pattern is stack-neutral

Parameters:

  • start_pos (Integer) —

    pattern start position

  • end_pos (Integer) —

    pattern end position (exclusive)

Returns:

  • (Boolean) —

    true if stack depth is same at start and end



175
176
177
178
179
180
 
# File 'lib/fontisan/optimizers/stack_tracker.rb', line 175

def stack_neutral?(start_pos, end_pos)
  return false unless @stack_depth_map.key?(start_pos)
  return false unless @stack_depth_map.key?(end_pos)

  @stack_depth_map[start_pos] == @stack_depth_map[end_pos]
end

#track ⇒ Hash<Integer, Integer>

Track stack depth at each byte position

Returns:

  • (Hash<Integer, Integer>) —

    position => stack_depth



143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
# File 'lib/fontisan/optimizers/stack_tracker.rb', line 143

def track
  io = StringIO.new(@charstring)
  depth = 0

  # Record initial depth
  @stack_depth_map[0] = depth

  while !io.eof?
    byte = io.getbyte

    if byte <= 31 && byte != 28
      # Operator
      operator = read_operator(io, byte)
      depth = apply_operator_effect(operator, depth)
    else
      # Number - pushes one value
      io.pos -= 1
      skip_number(io)
      depth += 1
    end

    # Record depth after processing this element
    @stack_depth_map[io.pos] = depth
  end

  @stack_depth_map
end