#    Quadrature state machine generator
#    Copyright 2006 Jeff Epler <jepler@unpythonic.net>
#
#    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<<j)) for j in range(6)]
#    return i | (f<<4) | ((e^f)<<3) | (a<<2) | (b<<5) | (c<<6) | (d<<7)
#def ux(s):
#    return (s>>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()