# Quadrature state machine generator
# Copyright 2006 Jeff Epler
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
# Configuration section
# N is the divisor. It could be 1, 2, 4, 8, or 16.
# M is the size of the table, at least 4N.
# x(s, i) gives the state table address for old state s and transition i
# ux(s) gives the quadrature output for state s (used for the validation tests)
# ux = None disables that test (if your output isn't quadrature)
N = 16
M = 256
#def x(s, i):
# "Divide-by-16, quadrature output in bits 3 and 4 (tiny13 divider)"
# a, b, c, d, e, f = [bool(s & (1<>3) & 3
def x(s, i):
"Divide-by-16, quadrature output in bits 6 and 7 (mega8 triple divider)"
q = (s & 128) >> 1
return i | (s<<2) ^ ((s & 32)<<1)
def ux(s):
return s >> 6
# End configuration section
# In this table, the rows are quadrature states from 0 to 4,
# and the columns are quadrature inputs 00, 01, 10, 11
# the table gives the direction of change
qt = [ [ 0, 1, -1, 0 ], [ -1, 0, 0, 1 ], [ 0, -1, 1, 0 ], [ 1, 0, 0, -1 ] ]
# Actually assemble the state table
states = [-1] * M
for i in range(N*4):
for k in range(4):
q = i % 4
ch = qt[q][k]
j = (i + ch + N*4) % (N*4)
xi = x(i, k)
assert states[xi] == -1, "states[0x%02x] = 0x%02x" % (xi, states[xi])
states[xi] = x(j, 0)
# Test 1: Check that the right number of states are reachable
seen = [0]
for s in seen:
for k in range(4):
j = states[s | k]
assert j != -1, "Uninitialized entry is reachable: 0x%02x|%x" % (s, k)
if j in seen: continue
seen.append(j)
assert len(seen) == N * 4, "Reachable test: %d %r" % (len(seen), seen)
def compressrepeat(seq):
last = None
res = []
for i in seq:
if i != last:
res.append(i)
last = i
return res
# Test 2: check that going forward in quadrature 4N times brings us back to 0
quadrature = [1, 3, 2, 0] * N
sts = []
st = 0
for i in quadrature:
st = states[st | i]
sts.append(st)
assert sts[-1] == 0 and sts.count(0) == 1, "Forward test: %r" % (sts,)
if ux:
# Test 2a: check that the quadrature outputs go in the right direction
sts = compressrepeat([ux(i) for i in sts])
assert sts == [0, 1, 3, 2, 0], sts
# Test 3: check that going backward in quadrature 4N times brings us back to 0
quadrature = [2, 3, 1, 0] * N
sts = []
st = 0
for i in quadrature:
st = states[st | i]
sts.append(st)
assert sts[-1] == 0 and sts.count(0) == 1, "Backward test: %r" % (sts)
if ux:
# Test 3a: check that the quadrature outputs go in the right direction
sts = compressrepeat([ux(i) for i in sts])
assert sts == [2, 3, 1, 0], sts
# Test 4: check that every glitch leaves us where we started
# For each step S0 and quadrature-adjacent transitions T1 and T2:
# From state S0, take transition S0|T1 to get state S1
# If S0 and S1 are the same, this subtest passes
# Otherwise, take transitions S2=T[S1|T2] and S3=T[S2|T1]
# IF S1 and S3 are the same, this subtest passes
#
# Then for the second subtest, do likewise with S1 and S2 reversed
quadrature = [0, 1, 3, 2]
for st in range(0, 4*N, 4):
for j in range(4):
t1 = quadrature[j]
t2 = quadrature[(j+1) % 4]
st1 = states[st|t1]
st2 = states[st1|t2]
st3 = states[st2|t1]
assert st == st1 or st3 == st1, "Glitch test A st=%d j=%d" % (st, j)
st1 = states[st|t2]
st2 = states[st1|t1]
st3 = states[st2|t2]
assert st == st1 or st3 == st1, "Glitch test B st=%d j=%d" % (st, j)
# Test 5: check that from each state there are two no-change and two changes
from sets import Set
for st in range(0, 4*N, 4):
q = states[st : st+4]
assert q.count(st) == 2, "State test, st=%d q=%r" % (st, q)
assert len(Set(q)) == 3, "State test, st=%d q=%r" % (st, q)
# Write the table
import sys
def print_c():
sys.stdout.write("/* Quadrature division table N=%d */\n" % N)
sys.stdout.write("/* %s */\n" % x.__doc__)
sys.stdout.write("uint8_t states[%d] = {" % len(states))
for i, s in enumerate(states):
if i % 8 == 0: sys.stdout.write("\n /* 0x%02x */\t" % i)
if i % 8 == 4: sys.stdout.write("\t")
sys.stdout.write(" 0x%02x," % s,)
sys.stdout.write("\n};\n")
def print_asm():
sys.stdout.write("; Quadrature division table N=%d\n" % N)
sys.stdout.write("; %s\n" % x.__doc__)
sys.stdout.write("states: ; %d\n" % len(states))
for i, s in enumerate(states):
if i % 8 == 0: sys.stdout.write(".byte ");
if i % 8 == 4: sys.stdout.write("\t")
if i % 8 == 7:
sys.stdout.write(" 0x%02x\t/* 0x%02x */\t\n" % (s, i))
else:
sys.stdout.write(" 0x%02x," % s,)
sys.stdout.write("\n")
print_asm()