path: root/devtools/cycle_analyzer

#!/usr/bin/env python
"""
cycle_analyzer - perform cycle analysis on GPS log files

This tool analyzes one or more NMEA or JSON files to determine the
cycle sequence of sentences. JSON files must be reports from a gpsd
driver which is without the CYCLE_END_RELIABLE capability and
therefore ships every sentence containing a fix; otherwise the results
will be meaningless.

One purpose of this tool is to determine the end-of-cycle sentence
that a binary-protocol device emits, so the result can be patched into
the driver as a CYCLE_END_RELIABLE capability.  To get this, apply the
tool to the JSON output from the driver (a log file beginning with a
JSON sentence).  It will ignore everything but tag and timestamp
fields, and will also ignore any NMEA in the file.

Another purpose is to sanity-check the assumptions of the NMEA end-of-cycle
detector. If a device has a regular reporting cycle with a constant
end-of-cycle sentence, this tool will confirm that.  Otherwise, it will
perform various checks attempting to find an end-of-cycle marker and report
on what it finds.

When cycle_analyzer reports a split- or variable-cycle device, some arguments
to the -d switch can dump various analysis stages so you can get a better
idea what is going on.  These are:

   sequence - the entire sequence of dump tag/timestamp pairs from the log
   events   - show how those reduce to event sequences
   bursts   - show how sentences are grouped into bursts
   trim     - show the burst list after the end bursts have been removed 

In an event sequence, a '<' is a nornal start of cycle where the
timestamp increments. A '>' is where the timestamp actually
*decreases* between a a sentence and the one that follows. The NMEA
cycle-end detector will ignore the '>' event; it sometimes occurs when
GPZDA starts a cycle, but has no effect on where the asctual end of
fix reporting is.

If you see a message saying 'cycle-enders ... also occur in mid-cycle', the
device will break the NMEA cycle detector.

"""
import sys, getopt, json

verbose = 0

class analyze_error:
    def __init__(self, filename, lineno, msg):
        self.filename = filename
        self.lineno = lineno
        self.msg = msg
    def __str__(self):
        return '"%s", line %d: %s' % (self.filename, self.lineno, self.msg)

class event:
    def __init__(self, tag, time=0):
        self.tag = tag
        self.time = time
    def __str__(self):
        if self.time == 0:
            return self.tag
        else:
            return self.tag + ":" + self.time
    __repr__ = __str__

def tags(lst):
    return map(lambda x: x.tag, lst)

def extract_from_nmea(filename, lineno, line):
    "Extend sequence of tag/timestamp tuples from an NMEA sentence"
    hhmmss = {
        "RMC": 1,
        "GLL": 5,
        "GGA": 1,
        "GBS": 1,
        "ZDA": 1,
        "PASHR": 4,
        }
    fields = line.split(",")
    tag = fields[0]
    if tag.startswith("$GP") or tag.startswith("$IN"):
        tag = tag[3:]
    elif tag[0] == "$":
        tag = tag[1:]
    if tag in hhmmss:
        timestamp = fields[hhmmss[tag]]
        return [event(tag, timestamp)]
    else:
        return []

def extract_from_json(filename, lineno, line):
    "Extend sequence of tag/timestamp tuples from a JSON dump of a sentence"
    # FIXME: Analyze JSON sentences
    raise analyze_error(filename, lineno, "JSON analsis not yet implemented.")

def extract_timestamped_sentences(fp):
    "Do the basic work of extracting tags and timestamps"
    sequence = []
    filetype = None
    lineno = 0
    while True:
        line = fp.readline()
        if not line:
            break
        lineno += 1
        if line.startswith("#"):
            continue
        elif filetype == None:
            if line.startswith("$"):
                filetype = "NMEA"
            elif line.startswith("{"):
                filetype = "JSON"
            else:
                print "%s: unknown sentence type." % fp.name
                return []
            if verbose:
                print "%s: is %s" % (fp.name, filetype)
        # The reason for this odd logic is that we want to oock onto
        # either (a) analyzing NMEA only, or (b) analyzing JSON only
        # and ignoring NMEA, depending on which kind the first data
        # line of the file is.  This gives the ability to run against
        # either raw NMEA or regression-test .chk files generated by
        # binary-format devices, without haviong to run gpsd to
        # do reanalysis.
        if filetype == "NMEA" and line.startswith("$"):
            sequence += extract_from_nmea(fp.name, lineno, line)
        elif filetype == "JSON" and line.startswith("{"):
            sequence + extract_from_json(fp.name, lineno, line)
    return sequence


def analyze(fp, stages):
    "Analyze the cycle sequence of a device from its output logs."
    # First, extract tags and timestamps
    regular = False
    sequence = extract_timestamped_sentences(fp)
    if not sequence:
        return
    if "sequence" in stages:
        print "Raw tag/timestamp sequence"
        for e in sequence:
            print e
    # Then, do cycle detection
    events = []
    out_of_order = False
    for i in range(len(sequence)):
        this = sequence[i]
        if this.time == "" or float(this.time) == 0:
            continue
        events.append(this)
        if i < len(sequence)-1:
            next = sequence[i+1]
            if float(this.time) < float(next.time):
                events.append(event("<"))
            if float(this.time) > float(next.time):
                events.append(event(">"))
                out_of_order = True
    if out_of_order:
        sys.stderr.write("%s: has some timestamps out of order.\n" % fp.name)
    if "events" in stages:
        print "Event list:"
        for e in events:
            print e
    # Now group events into bursts
    bursts = []
    current = []
    for e in events + [event('<')]:
        if e.tag == '<':
            bursts.append(tuple(current))
            current = []
        else:
            current.append(e)
    if "bursts" in stages:
        print "Burst list:"
        for burst in bursts:
            print burst
    # We need 4 cycles because the first and last might be incomplete.
    if tags(events).count("<") < 4:
        sys.stderr.write("%s: has fewer than 4 cycles.\n" % fp.name)
        return
    # First try at detecting a regular cycle
    unequal = False
    for i in range(len(bursts)-1):
        if tags(bursts[i]) != tags(bursts[i+1]):
            unequal = True
            break
    if not unequal:
        # All bursts looked the same
        regular = True
    else:
        # Trim off first and last bursts, which are likely incomplete.
        bursts = bursts[1:-1]
        if "trim" in stages:
            "After trimming:"
            for burst in bursts:
                print burst
        # Now the actual clique analysis
        unequal = False
        for i in range(len(bursts)-1):
            if tags(bursts[i]) != tags(bursts[i+1]):
                unequal = True
                break
        if not unequal:
            regular = True
    # Should know now if cycle is regular
    if regular:
        print "%s: has a regular cycle %s." % (filename, " ".join(tags(bursts[0])))
    else:
        # If it was not the case that all cycles matched, then we need
        # a minimum of 6 cycles because the first and last might be
        # incomplete, and we need at least 4 cycles in the middle to
        # have two full ones on split-cycle devices like old Garmins.
        if tags(events).count("<") < 6:
            sys.stderr.write("%s: variable-cycle log has has fewer than 6 cycles.\n" % fp.name)
            return
        print "%s: has a split or variable cycle." % filename
        cycle_enders = []
        for burst in bursts:
            if burst[-1].tag not in cycle_enders:
                cycle_enders.append(burst[-1].tag)
        if len(cycle_enders) == 1:
            print "%s: has a fixed end-of-cycle sentence %s." % (filename, cycle_enders[0])
        else:
            print "%s: has multiple cycle-enders %s." % (filename, " ".join(cycle_enders))
        # Sanity check
        pathological = []
        for ender in cycle_enders:
            for burst in bursts:
                if ender in tags(burst) and not ender == burst[-1].tag and not ender in pathological:
                    pathological.append(ender)
        if pathological:
            print "%s: cycle-enders %s also occur in mid-cycle!" % (filename, " ".join(pathological))

if __name__ == "__main__":
    stages = ""
    try:
        (options, arguments) = getopt.getopt(sys.argv[1:], "d:v")
        for (switch, val) in options:
            if (switch == '-d'):		# Debug
                stages = val
            elif (switch == '-v'):		# Verbose
                verbose += 1
    except getopt.GetoptError, msg:
        print "cycle_analyzer: " + str(msg)
        raise SystemExit, 1

    try:
        if arguments:
            for filename in arguments:
                fp = open(filename)
                analyze(fp, stages)
                fp.close()
        else:
            analyze(sys.stdin)
    except analyze_error, e:
        print str(e)
        raise SystemExit, 1