#!/usr/bin/perl
# JTAG.pm: functions that define the core JTAG TAP state machine
# Copyright (C) 2009 by Zachary T Welch <zw@superlucidity.net>
# Released under the GNU GPL v2 (or later).

use strict;
use warnings;

# define the JTAG TAP states
my @jtag_state_names = (
		'Exit2-DR', 'Exit1-DR', 'Shift-DR', 'Pause-DR',
		'Select-IR-Scan', 'Update-DR', 'Capture-DR', 'Select-DR-Scan',
		'Exit2-IR', 'Exit1-IR', 'Shift-IR', 'Pause-IR',
		'Run-Test/Idle', 'Update-IR', 'Capture-IR', 'Test-Logic-Reset',
	);
sub jtag_state_names { return @jtag_state_names; }

# create state numbers
my $jtag_num_states = 0;
my %jtag_state_ids = map { $_ => $jtag_num_states++ } @jtag_state_names;

#print "$_=", get_state_id($_), "\n" for sort { get_state_id($a) <=> get_state_id($b) } keys %jtag_state_ids;

sub get_state_name {
	my $id = shift;
	die "invalid id: $id\n" if $id < 0 || $id >= $jtag_num_states;
	return $jtag_state_names[$id];
}
sub get_state_id {
	my $name = shift;
	die "unknown state: $name\n" unless exists $jtag_state_ids{$name};
	return $jtag_state_ids{$name};
}

my %jtag_transitions = (
		'Exit2-DR' => [ 'Shift-DR', 'Update-DR' ],
		'Exit1-DR' => [ 'Pause-DR', 'Update-DR' ],
		'Shift-DR' => [ '*', 'Exit1-DR' ],
		'Pause-DR' => [ '*', 'Exit2-DR' ],
		'Select-IR-Scan' => [ 'Capture-IR', 'Test-Logic-Reset' ],
		'Update-DR' => [ 'Run-Test/Idle', 'Select-DR-Scan' ],
		'Capture-DR' => [ 'Shift-DR', 'Exit1-DR' ],
		'Select-DR-Scan' => [ 'Capture-DR', 'Select-IR-Scan' ],
		'Exit2-IR' => [ 'Shift-IR', 'Update-IR' ],
		'Exit1-IR' => [ 'Pause-IR', 'Update-IR' ],
		'Shift-IR' => [ '*', 'Exit1-IR' ],
		'Pause-IR' => [ '*', 'Exit2-IR' ],
		'Run-Test/Idle' => [ '*', 'Select-DR-Scan' ],
		'Update-IR' => [ 'Run-Test/Idle', 'Select-DR-Scan' ],
		'Capture-IR' => [ 'Shift-IR', 'Exit1-IR' ],
		'Test-Logic-Reset' => [ 'Run-Test/Idle', '*' ],
	);
sub get_next_state {
	my ( $start, $tms ) = @_;
	my $final = $jtag_transitions{$start}->[$tms];
	$final = $start if $final eq '*';
	return $final;
}
sub get_next_states {
	my $name = shift;
	return ( get_next_state($name, 0), get_next_state($name, 1) );
}

my $BAD = 10000;

# find costs of shortest paths between all possible state pairs
sub tap_path_costs {
	my $paths = { };
	for my $start ( @jtag_state_names ) {
		$paths->{$start} = { map { $_ => $BAD } @jtag_state_names };
		$paths->{$start}->{get_next_state($start, 0)} = 1;
		$paths->{$start}->{get_next_state($start, 1)} = 1;
	}
	# use Floyd-Warshall algorithm (see Wikipedia)
	for my $via ( @jtag_state_names ) {
		for my $start ( @jtag_state_names ) {
			for my $finish ( @jtag_state_names ) {
				my $cost = $paths->{$start}->{$via} +
					$paths->{$via}->{$finish};
				next if $paths->{$start}->{$finish} <= $cost;
				$paths->{$start}->{$finish} = $cost;
			}
		}
	}
	return $paths;
}

# find shortest path between two states by using breadth-first search
sub shortest_tap_path
{
	my ( $start, $final ) = @_;
	my @states = ( [ $start, '' ] );
	while ( @states ) 
	{
		my $state = shift @states;
		my $name = $state->[0];
		my $solution = $state->[1];
		return $solution if length($solution) && ($name eq $final);

		push @states, map {
				[ get_next_state($name, $_), $solution . "$_" ]
			} 0 .. 1;
	}
	return "INVALID";
}

# find shortest paths between all possible state pairs
sub tap_path_table {
	my $paths = { };
	for my $start ( @jtag_state_names ) {
		$paths->{$start} = { map {
				$_ => shortest_tap_path($start, $_)
			} @jtag_state_names };
	}
	return $paths;
}