generate_fir_coeff.py 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. #!/usr/bin/python
  2. '''
  3. Copyright 2013 Google Inc.
  4. Use of this source code is governed by a BSD-style license that can be
  5. found in the LICENSE file.
  6. '''
  7. import math
  8. import pprint
  9. def withinStdDev(n):
  10. """Returns the percent of samples within n std deviations of the normal."""
  11. return math.erf(n / math.sqrt(2))
  12. def withinStdDevRange(a, b):
  13. """Returns the percent of samples within the std deviation range a, b"""
  14. if b < a:
  15. return 0;
  16. if a < 0:
  17. if b < 0:
  18. return (withinStdDev(-a) - withinStdDev(-b)) / 2;
  19. else:
  20. return (withinStdDev(-a) + withinStdDev(b)) / 2;
  21. else:
  22. return (withinStdDev(b) - withinStdDev(a)) / 2;
  23. # We have some smudged samples which represent the average coverage of a range.
  24. # We have a 'center' which may not line up with those samples.
  25. # From center make a normal where 5 sample widths out is at 3 std deviations.
  26. # The first and last samples may not be fully covered.
  27. # This is the sub-sample shift for each set of FIR coefficients
  28. # (the centers of the lcds in the samples)
  29. # Each subpxl takes up 1/3 of a pixel,
  30. # so they are centered at x=(i/n+1/2n), or 1/6, 3/6, 5/6 of a pixel.
  31. # Each sample takes up 1/4 of a pixel,
  32. # so the results fall at (x*4)%1, or 2/3, 0, 1/3 of a sample.
  33. samples_per_pixel = 4
  34. subpxls_per_pixel = 3
  35. #sample_offsets is (frac, int) in sample units.
  36. sample_offsets = [
  37. math.modf(
  38. (float(subpxl_index)/subpxls_per_pixel + 1.0/(2.0*subpxls_per_pixel))
  39. * samples_per_pixel
  40. ) for subpxl_index in range(subpxls_per_pixel)
  41. ]
  42. #How many samples to consider to the left and right of the subpxl center.
  43. sample_units_width = 5
  44. #The std deviation at sample_units_width.
  45. std_dev_max = 3
  46. #The target sum is in some fixed point representation.
  47. #Values larger the 1 in fixed point simulate ink spread.
  48. target_sum = 0x110
  49. for sample_offset, sample_align in sample_offsets:
  50. coeffs = []
  51. coeffs_rounded = []
  52. #We start at sample_offset - sample_units_width
  53. current_sample_left = sample_offset - sample_units_width
  54. current_std_dev_left = -std_dev_max
  55. done = False
  56. while not done:
  57. current_sample_right = math.floor(current_sample_left + 1)
  58. if current_sample_right > sample_offset + sample_units_width:
  59. done = True
  60. current_sample_right = sample_offset + sample_units_width
  61. current_std_dev_right = current_std_dev_left + (
  62. (current_sample_right - current_sample_left) / sample_units_width
  63. ) * std_dev_max
  64. coverage = withinStdDevRange(current_std_dev_left, current_std_dev_right)
  65. coeffs.append(coverage * target_sum)
  66. coeffs_rounded.append(int(round(coverage * target_sum)))
  67. current_sample_left = current_sample_right
  68. current_std_dev_left = current_std_dev_right
  69. # Have the numbers, but rounding needs to add up to target_sum.
  70. delta = 0
  71. coeffs_rounded_sum = sum(coeffs_rounded)
  72. if coeffs_rounded_sum > target_sum:
  73. # The coeffs add up to too much.
  74. # Subtract 1 from the ones which were rounded up the most.
  75. delta = -1
  76. if coeffs_rounded_sum < target_sum:
  77. # The coeffs add up to too little.
  78. # Add 1 to the ones which were rounded down the most.
  79. delta = 1
  80. if delta:
  81. print "Initial sum is 0x%0.2X, adjusting." % (coeffs_rounded_sum,)
  82. coeff_diff = [(coeff_rounded - coeff) * delta
  83. for coeff, coeff_rounded in zip(coeffs, coeffs_rounded)]
  84. class IndexTracker:
  85. def __init__(self, index, item):
  86. self.index = index
  87. self.item = item
  88. def __lt__(self, other):
  89. return self.item < other.item
  90. def __repr__(self):
  91. return "arr[%d] == %s" % (self.index, repr(self.item))
  92. coeff_pkg = [IndexTracker(i, diff) for i, diff in enumerate(coeff_diff)]
  93. coeff_pkg.sort()
  94. # num_elements_to_force_round better be < (2 * sample_units_width + 1) or
  95. # * our math was wildy wrong
  96. # * an awful lot of the curve is out side our sample
  97. # either is pretty bad, and probably means the results will not be useful.
  98. num_elements_to_force_round = abs(coeffs_rounded_sum - target_sum)
  99. for i in xrange(num_elements_to_force_round):
  100. print "Adding %d to index %d to force round %f." % (
  101. delta, coeff_pkg[i].index, coeffs[coeff_pkg[i].index])
  102. coeffs_rounded[coeff_pkg[i].index] += delta
  103. print "Prepending %d 0x00 for allignment." % (sample_align,)
  104. coeffs_rounded_aligned = ([0] * int(sample_align)) + coeffs_rounded
  105. print ', '.join(["0x%0.2X" % coeff_rounded
  106. for coeff_rounded in coeffs_rounded_aligned])
  107. print sum(coeffs), hex(sum(coeffs_rounded))
  108. print