summaryrefslogtreecommitdiff
path: root/src/org/noreply/fancydress/type3/PathSpec.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/org/noreply/fancydress/type3/PathSpec.java')
-rw-r--r--src/org/noreply/fancydress/type3/PathSpec.java366
1 files changed, 312 insertions, 54 deletions
diff --git a/src/org/noreply/fancydress/type3/PathSpec.java b/src/org/noreply/fancydress/type3/PathSpec.java
index cbc608f..9e975c6 100644
--- a/src/org/noreply/fancydress/type3/PathSpec.java
+++ b/src/org/noreply/fancydress/type3/PathSpec.java
@@ -11,53 +11,125 @@ import java.util.*;
public class PathSpec {
- String pathSpec;
- Path singlePath;
+ Directory dir;
+ PathComponent[] pathComponents;
+ boolean singleLeg;
- private String[] tokenize(String path) throws Mix3Exception {
- ArrayList nicks = new ArrayList();
- int indexFrom = 0;
- int indexOf;
-
- while ((indexOf = path.indexOf(',', indexFrom)) != -1) {
- String v = path.substring(indexFrom, indexOf).trim();
- if (v.equals(""))
- throw new Mix3Exception("Invalid path.");
- nicks.add( v );
- indexFrom = indexOf + 1;
+ private class PathComponent {
+ public final static double GAUSS_STD_DEV = 1.5;
+
+ public final static int TYPE_NICKNAME = 1;
+ public final static int TYPE_RANDOM = 2;
+ public final static int TYPE_RANDOM_GAUSS = 3;
+ public final static int TYPE_CROSSOVER = 4;
+ int type;
+ Server byNickname;
+ int numRandoms;
+
+ public PathComponent(Directory dir, String component) throws Mix3BadArgumentsIllegalPathSpecException {
+ String c = component.trim();
+ if (c.equals(""))
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: empty path component");
+ char b = c.charAt(0);
+
+ Integer integer;
+ switch (b) {
+ case '*' :
+ try {
+ integer = new Integer(c.substring(1));
+ } catch (NumberFormatException e) {
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+ }
+ type = TYPE_RANDOM;
+ numRandoms = integer.intValue();
+ break;
+ case '~' :
+ try {
+ integer = new Integer(c.substring(1));
+ } catch (NumberFormatException e) {
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+ }
+ type = TYPE_RANDOM_GAUSS;
+ numRandoms = integer.intValue();
+ break;
+ case '?' :
+ if (c.length() > 1)
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+ type = TYPE_RANDOM;
+ numRandoms = 1;
+ break;
+ case ':' :
+ if (c.length() > 1)
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+ type = TYPE_CROSSOVER;
+ break;
+ default :
+ Server server = dir.getServer(c);
+ if (server == null)
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Nickname '"+c+"' not found");
+ if (!server.isUseable())
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Nickname '"+c+"' is not useable");
+ byNickname = server;
+ type = TYPE_NICKNAME;
+ break;
+ }
}
- String v = path.substring(indexFrom).trim();
- if (v.equals(""))
- throw new Mix3Exception("Invalid path.");
- nicks.add( v );
- String[] result = new String[nicks.size()];
- for (int i=0; i<result.length; i++)
- result[i] = (String) nicks.get(i);
+ public boolean isCrossover() {
+ return (type == TYPE_CROSSOVER);
+ }
- return result;
+ public Server[] getHops() {
+ Server[] result;
+ switch (type) {
+ case TYPE_NICKNAME :
+ result = new Server[1];
+ result[0] = byNickname;
+ break;
+ case TYPE_RANDOM :
+ result = new Server[numRandoms];
+ break;
+ case TYPE_RANDOM_GAUSS :
+ double d = CryptoPrimitives.normal(numRandoms, GAUSS_STD_DEV);
+ int num = (int) (d+0.5);
+ result = new Server[ num<0 ? 0 : num ];
+ break;
+ default :
+ throw new Error("Unkown type "+type);
+ }
+ return result;
+ }
}
- private Hop[] parseHalfPath(Directory dir, String path) throws Mix3Exception {
- String[] nicks = tokenize(path);
- Hop[] hops = new Hop[nicks.length];
-
- for (int i=0; i<hops.length; i++) {
- Server server = dir.getServer(nicks[i]);
- if (server == null)
- throw new Mix3Exception("Invalid path: "+nicks[i]+" not found");
- ServerDescriptor desc = server.getDescriptor();
- IncomingMMTPSection incoming = desc.getIncomingMMTPSection();
- Routing routing;
-
- if (incoming.getHostname() != null) { /* FIXME */
- routing = new RoutingHOST(incoming.getHostname(), incoming.getPort(), server.getKeyID());
- } else {
- routing = new RoutingIP4(incoming.getIP(), incoming.getPort(), server.getKeyID());
- }
- hops[i] = new Hop(routing, desc.getPacketKey());
+ private void splitCrossover(ArrayList tokens, String s) throws Mix3BadArgumentsIllegalPathSpecException {
+ int indexOf = s.indexOf(':');
+ if (indexOf != -1) {
+ String s1 = s.substring(0, indexOf).trim();
+ String s2 = s.substring(indexOf+1).trim();
+ if (s1.equals(""))
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop before crossover point.");
+ if (s2.equals(""))
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop after crossover point.");
+ tokens.add(s1.trim());
+ tokens.add(s2.trim());
+ } else {
+ if (s.equals(""))
+ throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop in path.");
+ tokens.add(s);
}
- return hops;
+ }
+
+ private PathComponent[] parsePath(Directory dir, String path) throws Mix3BadArgumentsIllegalPathSpecException {
+ ArrayList nicks = new ArrayList();
+ String[] tokens = Util.tokenize(path, ',');
+ for (int i=0; i<tokens.length; i++)
+ splitCrossover( nicks, tokens[i] );
+
+ PathComponent[] components = new PathComponent[nicks.size()];
+ for (int i=0; i<nicks.size(); i++)
+ components[i] = new PathComponent(dir, (String) nicks.get(i));
+
+ return components;
}
@@ -70,26 +142,212 @@ public class PathSpec {
*
* @param path given path
*/
- public PathSpec(Directory dir, String pathSpec, boolean singleLeg) throws Mix3Exception {
- this.pathSpec = pathSpec;
+ public PathSpec(Directory dir, String pathSpec, boolean singleLeg) throws Mix3BadArgumentsIllegalPathSpecException {
+ this.dir = dir;
+ this.singleLeg = singleLeg;
+
+ if (singleLeg) {
+ /* single legs do not have a crossover point */
+ int crossover = pathSpec.indexOf(':');
+ if (crossover >= 0)
+ throw new Mix3BadArgumentsIllegalPathSpecException("Path is not a valid path: crossover point specified in single leg path.");
+ } else {
+ /* full paths may have up to one specified crossover point */
+ int crossover = pathSpec.indexOf(':');
+ if (crossover >= 0)
+ if (pathSpec.indexOf(':', crossover+1) >= 0)
+ throw new Mix3BadArgumentsIllegalPathSpecException("Path is not a valid path: more than one crossover points specified.");
+ }
+
+ this.pathComponents = parsePath(dir, pathSpec);
+ }
+
+ private class ServerWithCrossover {
+ public Server[] servers;
+ public int crossoverPoint;
+
+ public Server getLastServer() {
+ return (servers[servers.length - 1]);
+ }
+
+ public void setLastServer(Server s) {
+ servers[servers.length - 1] = s;
+ }
+
+ public Server getSecondToLastServer() {
+ return (servers[servers.length - 2]);
+ }
+
+ private void fillInRandoms() throws Mix3PathProblemException {
+ Server[] recommended = dir.getRecommendedServers();
+ for (int i=servers.length-1; i>=0 ; i--) {
+ if (servers[i] != null)
+ continue;
+ ArrayList s = new ArrayList();
+ for (int r=0; r<recommended.length; r++)
+ if (
+ /* last hop or */
+ ((i == servers.length-1) || (
+ /* next hop is different */
+ (recommended[r] != servers[i+1]) &&
+ /* and can talk to next hop */
+ dir.areFriends(recommended[r], servers[i+1]) )) &&
+ /* first hop, or previos hop is random, or */
+ ((i == 0) || (servers[i-1] == null) || (
+ /* previous hop is different */
+ (recommended[r] != servers[i-1]) &&
+ /* and prev hop can talk to this */
+ dir.areFriends(servers[i-1], recommended[r]) ))
+ )
+ s.add(recommended[r]);
+ if (s.size() == 0)
+ throw new Mix3PathProblemException("Cannot find useable servers for random hop.");
+ servers[i] = (Server) s.get(CryptoPrimitives.randInt(s.size()));
+ }
+ }
+
+ public Path getPath() throws Mix3PathProblemException {
+ fillInRandoms();
+ Hop[] hops = new Hop[servers.length];
+ for (int i=0; i<hops.length ; i++)
+ hops[i] = new Hop(servers[i]);
+
+ if (crossoverPoint == -1)
+ crossoverPoint = (hops.length+1)/2;
+ int len1 = crossoverPoint;
+ int len2 = hops.length - len1;
+ Hop[] l1 = new Hop[len1];
+ Hop[] l2 = new Hop[len2];
+ System.arraycopy(hops, 0, l1, 0, len1);
+ System.arraycopy(hops, len1, l2, 0, len2);
+ return new Path(l1, l2);
+ }
+ }
+
+ /**
+ * Concat path components, getting random amount of hops where requested.
+ */
+ private ServerWithCrossover concatComponents() throws Mix3PathProblemException {
+ Server[][] components = new Server[pathComponents.length][];
+ int length = 0;
+ int crossoverBefore = -1;
+ for (int i=0; i<pathComponents.length ; i++) {
+ if (pathComponents[i].isCrossover())
+ crossoverBefore = length;
+ else {
+ components[i] = pathComponents[i].getHops();
+ length += components[i].length;
+ }
+ }
+ Server[] servers = new Server[length];
+ int c = 0;
+ for (int i=0; i<pathComponents.length ; i++) {
+ if (components[i] != null) {
+ System.arraycopy(components[i], 0, servers, c, components[i].length);
+ c += components[i].length;
+ }
+ }
+ if (c != length)
+ throw new Error ("Did not fill in length hops ("+c+" vs "+length+")");
+
+ ServerWithCrossover result = new ServerWithCrossover();
+ result.servers = servers;
+ result.crossoverPoint = crossoverBefore;
+ return result;
+ }
+
+ /**
+ * get one instance of this path spec.
+ *
+ * Also we filter acceptable exit nodes according to the payload's
+ * constraints.
+ *
+ * @return one path constructed from the PathSpec
+ */
+ /*
+ private Object getPathInstance() throws Mix3PathProblemException {
- int crossover = pathSpec.indexOf(':');
- if (crossover < 0)
- throw new Mix3Exception("Path is not a valid path: no crossover point specified.");
+ ServerWithCrossover path = concatComponents();
+ fillInRandoms(path.components);
- Hop[] leg1 = parseHalfPath(dir, pathSpec.substring(0, crossover));
- Hop[] leg2 = parseHalfPath(dir, pathSpec.substring(crossover+1));
- singlePath = new Path(leg1, leg2);
+ if (singleLeg)
+ throw new Error("not implemented yet"); // FIXME
+ else
+ return path.getPath();
}
+ */
/**
- * Return a path constructed from this PathSpec
+ * Return paths constructed from this PathSpec.
+ *
+ * Build paths from this pathspec that are able to deliver the payload
+ * in <code>payload</code>.
*
- * @param dir a directory
- * @return path
+ * We build as many paths as <code>payload.numPackets()</code> requires.
+ *
+ * Also we filter acceptable exit nodes according to the payload's
+ * constraints.
+ *
+ * @param payload the payload
+ * @return paths constructed from the PathSpec
*/
- public Path getPath() throws Mix3Exception {
- return singlePath;
+ public Path[] getPath(Payload payload) throws Mix3PathProblemException {
+ if (singleLeg)
+ throw new IllegalArgumentException("getPath() may not be called for single leg path specs.");
+
+
+ ServerWithCrossover[] paths = new ServerWithCrossover[payload.numPackets()];
+ for (int i=0; i<paths.length; i++) {
+ paths[i] = concatComponents();
+ if (paths[i].servers.length < 2)
+ throw new Mix3PathProblemException("Path too short.");
+ }
+
+ Server lastHop = paths[0].getLastServer();
+ for (int i=1; i<paths.length; i++)
+ if (lastHop != paths[i].getLastServer())
+ throw new Mix3PathProblemException("Exit hop must be the same in all paths (random or fixed)");
+
+ Server[] possibleExitHops = payload.filterExithops( dir.getRecommendedServers() );
+ if (lastHop == null) {
+ boolean[] unuseable = new boolean[possibleExitHops.length];
+ for (int i=0; i<paths.length; i++) {
+ Server stls = paths[i].getSecondToLastServer();
+ if (stls == null)
+ continue;
+ for (int j=0; j<unuseable.length; j++)
+ if (unuseable[j])
+ continue;
+ else
+ if (! dir.areFriends(stls, possibleExitHops[j] ))
+ unuseable[j] = true;
+ }
+ ArrayList list = new ArrayList();
+ for (int j=0; j<unuseable.length; j++)
+ if (! unuseable[j])
+ list.add(possibleExitHops[j]);
+
+ if (list.size() == 0)
+ throw new Mix3PathProblemException("No useable exit hops found");
+
+ lastHop = (Server) list.get( CryptoPrimitives.randInt(list.size()) );
+ for (int i=0; i<paths.length; i++)
+ paths[i].setLastServer(lastHop);
+ } else {
+ boolean exitHopOK = false;
+ for (int j=0; j<possibleExitHops.length; j++)
+ if (possibleExitHops[j] == lastHop) {
+ exitHopOK = true;
+ break;
+ }
+ if (! exitHopOK)
+ throw new Mix3PathProblemException("Exit hop "+lastHop.getNickname()+" does not meet constraints.");
+ }
+
+ Path[] result = new Path[paths.length];
+ for (int i=0; i<paths.length; i++)
+ result[i] = paths[i].getPath();
+
+ return result;
}
}
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 07:39:43 +0000