Author: infinity0
Date: 2009-03-31 13:09:45 +0000 (Tue, 31 Mar 2009)
New Revision: 26281
Added:
trunk/contrib/fec/lib/fec.properties
trunk/contrib/fec/src/com/
trunk/contrib/fec/src/com/onionnetworks/
trunk/contrib/fec/src/com/onionnetworks/fec/
trunk/contrib/fec/src/com/onionnetworks/fec/DefaultFECCodeFactory.java
trunk/contrib/fec/src/com/onionnetworks/fec/FECCode.java
trunk/contrib/fec/src/com/onionnetworks/fec/FECCodeFactory.java
trunk/contrib/fec/src/com/onionnetworks/fec/FECMath.java
trunk/contrib/fec/src/com/onionnetworks/fec/Native16Code.java
trunk/contrib/fec/src/com/onionnetworks/fec/Native8Code.java
trunk/contrib/fec/src/com/onionnetworks/fec/Pure16Code.java
trunk/contrib/fec/src/com/onionnetworks/fec/PureCode.java
Removed:
trunk/contrib/fec/fec_src/
Modified:
trunk/contrib/freenet_ext/build.xml
Log:
Cleaner directory structure (git commit summary follows:)
On branch master
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
renamed: contrib/fec/fec_src/lib/fec.properties ->
contrib/fec/lib/fec.properties
renamed:
contrib/fec/fec_src/com/onionnetworks/fec/DefaultFECCodeFactory.java ->
contrib/fec/src/com/onionnetworks/fec/DefaultFECCodeFactory.java
renamed: contrib/fec/fec_src/com/onionnetworks/fec/FECCode.java ->
contrib/fec/src/com/onionnetworks/fec/FECCode.java
renamed:
contrib/fec/fec_src/com/onionnetworks/fec/FECCodeFactory.java ->
contrib/fec/src/com/onionnetworks/fec/FECCodeFactory.java
renamed: contrib/fec/fec_src/com/onionnetworks/fec/FECMath.java ->
contrib/fec/src/com/onionnetworks/fec/FECMath.java
renamed: contrib/fec/fec_src/com/onionnetworks/fec/Native16Code.java
-> contrib/fec/src/com/onionnetworks/fec/Native16Code.java
renamed: contrib/fec/fec_src/com/onionnetworks/fec/Native8Code.java
-> contrib/fec/src/com/onionnetworks/fec/Native8Code.java
renamed: contrib/fec/fec_src/com/onionnetworks/fec/Pure16Code.java
-> contrib/fec/src/com/onionnetworks/fec/Pure16Code.java
renamed: contrib/fec/fec_src/com/onionnetworks/fec/PureCode.java ->
contrib/fec/src/com/onionnetworks/fec/PureCode.java
modified: contrib/freenet_ext/build.xml
Copied: trunk/contrib/fec/lib/fec.properties (from rev 26280,
trunk/contrib/fec/fec_src/lib/fec.properties)
===================================================================
--- trunk/contrib/fec/lib/fec.properties (rev 0)
+++ trunk/contrib/fec/lib/fec.properties 2009-03-31 13:09:45 UTC (rev
26281)
@@ -0,0 +1,17 @@
+# Order is very important because it defines the preffered order to try
+# the various codes. So faster performing codes should be at the front of the
+# list.
+
+com.onionnetworks.fec.keys=native8,pure8,native16,pure16
+
+com.onionnetworks.fec.native8.class=com.onionnetworks.fec.Native8Code
+com.onionnetworks.fec.native8.bits=8
+
+com.onionnetworks.fec.pure8.class=com.onionnetworks.fec.PureCode
+com.onionnetworks.fec.pure8.bits=8
+
+com.onionnetworks.fec.native16.class=com.onionnetworks.fec.Native16Code
+com.onionnetworks.fec.native16.bits=16
+
+com.onionnetworks.fec.pure16.class=com.onionnetworks.fec.Pure16Code
+com.onionnetworks.fec.pure16.bits=16
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/DefaultFECCodeFactory.java
(from rev 26280,
trunk/contrib/fec/fec_src/com/onionnetworks/fec/DefaultFECCodeFactory.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/DefaultFECCodeFactory.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/DefaultFECCodeFactory.java
2009-03-31 13:09:45 UTC (rev 26281)
@@ -0,0 +1,139 @@
+package com.onionnetworks.fec;
+
+import java.util.*;
+import java.io.IOException;
+import java.lang.reflect.*;
+import com.onionnetworks.util.Tuple;
+import com.onionnetworks.util.TimedSoftHashMap;
+
+/**
+ * This is the default FECCodeFactory that wraps all of the FECCode
+ * implementations. It provides a way to customize the codes through
+ * a properties file specified by the property
+ * "com.onionnetworks.fec.defaultfeccodefactorypropertiesfile". By default
+ * it will use the "lib/fec.properties" file distributed with the JAR.
+ * Please consult this file for an example of how this should be done.
+ *
+ * The properties in this file can also be passed manually to the
+ * System properties. Again, consult the provided properties file for an
+ * example. This given, if you are adding new codes to this stuff please
+ * let me know because I worked my ass of to provide this for you, so do me
+ * a favor and at least let me know what you're using this for.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public class DefaultFECCodeFactory extends FECCodeFactory {
+
+ public static final int DEFAULT_CACHE_TIME = 2*60*1000;
+
+ //protected TimedSoftHashMap codeCache = new HashMap();
+ protected ArrayList eightBitCodes = new ArrayList();
+ protected ArrayList sixteenBitCodes = new ArrayList();
+ protected Properties fecProperties;
+
+ public DefaultFECCodeFactory() {
+ // Load in the properties file.
+ try {
+ fecProperties = new Properties();
+ fecProperties.load
+ (ClassLoader.getSystemClassLoader().
+ getResourceAsStream
+ (System.getProperty
+ ("com.onionnetworks.fec.defaultfeccodefactorypropertiesfile",
+ "lib/fec.properties")));
+
+// fecProperties.load
+// (DefaultFECCodeFactory.class.getClassLoader().
+// getResourceAsStream
+// (System.getProperty
+//
("com.onionnetworks.fec.defaultfeccodefactorypropertiesfile",
+// "lib/fec.properties")));
+
+ } catch (IOException e) {
+ e.printStackTrace();
+ throw new IllegalStateException
+ ("Unable to load /lib/fec.properties");
+ }
+
+ // Parse the keys
+ StringTokenizer st = new StringTokenizer
+ (getProperty("com.onionnetworks.fec.keys"),",");
+
+ // Load the codes into the HashMaps.
+ while (st.hasMoreTokens()) {
+ String key = st.nextToken();
+ try {
+ Constructor con = Class.forName
+ (getProperty("com.onionnetworks.fec."+key+".class")).
+ getConstructor(new Class[] {int.class, int.class});
+ String numBits =
getProperty("com.onionnetworks.fec."+key+".bits");
+ if ("8".equals(numBits)) {
+ eightBitCodes.add(con);
+ } else if ("16".equals(numBits)) {
+ sixteenBitCodes.add(con);
+ } else {
+ throw new IllegalArgumentException
+ ("Only 8 and 16 bit codes are currently supported");
+ }
+ } catch (Throwable t) {
+ System.out.println(t.getMessage());
+ }
+ }
+ }
+
+ /**
+ * Get a value, trying the System properties first and then checking
+ * the fecProperties.
+ */
+ protected synchronized String getProperty(String key) {
+ String result = System.getProperty(key);
+ if (result == null) {
+ result = fecProperties.getProperty(key);
+ }
+ return result;
+ }
+
+ /**
+ * If you're only asking for an 8 bit code we will NOT give you a 16 bit
+ * one.
+ */
+ public synchronized FECCode createFECCode(int k, int n) {
+ Integer K = new Integer(k);
+ Integer N = new Integer(n);
+ Tuple t = new Tuple(K,N);
+
+ // See if there is a cached code.
+ FECCode result = null; //(FECCode) codeCache.get(t);
+ if (result == null) {
+ if (k < 1 || k > 65536 || n < k || n > 65536) {
+ throw new IllegalArgumentException
+ ("k and n must be between 1 and 65536 and n must not be "+
+ "smaller than k: k="+k+",n="+n);
+ }
+
+ Iterator it;
+ if (n <= 256 && !eightBitCodes.isEmpty()) {
+ it = eightBitCodes.iterator();
+ } else {
+ it = sixteenBitCodes.iterator();
+ }
+ while (it.hasNext()) {
+ try {
+ result = (FECCode) ((Constructor) it.next()).newInstance
+ (new Object[] {K, N});
+ break;
+ } catch (Throwable doh) {
+ //doh.printStackTrace();
+ }
+ }
+
+ //if (result != null) {
+ // codeCache.put(t,result,DEFAULT_CACHE_TIME);
+ // }
+ }
+ return result;
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/FECCode.java (from rev
26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/FECCode.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/FECCode.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/FECCode.java 2009-03-31
13:09:45 UTC (rev 26281)
@@ -0,0 +1,275 @@
+package com.onionnetworks.fec;
+
+import com.onionnetworks.util.Util;
+import com.onionnetworks.util.Buffer;
+
+/**
+ *
+ * This class provides the main API/SPI for the FEC library. You cannot
+ * construct an FECCode directly, rather you must use an FECCodeFactory.
+ *
+ * For example:
+ * <code>
+ * int k = 32;
+ * int n = 256;
+ * FECCode code = FECCodeFactory.getDefault().createFECCode(k,n);
+ * </code>
+ *
+ * All FEC
+ * implementations will sublcass FECCode and implement the encode/decode
+ * methods. All codes implemented by this interface are assumed to be
+ * systematic codes which means that the first k repair packets will be
+ * the same as the original source packets.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public abstract class FECCode {
+
+ protected int k,n;
+
+ /**
+ * Construct a new FECCode given <code>k</code> and <code>n</code>
+ *
+ * @param k The number of source packets to be encoded/decoded.
+ * @param n The number of packets that the source packets will be encoded
+ * to.
+ */
+ protected FECCode(int k, int n) {
+ this.k = k;
+ this.n = n;
+ }
+
+ /**
+ * This method takes an array of source packets and generates a number
+ * of repair packets from them. This method could have taken in only
+ * one repair packet to be generated, but in many cases it is more
+ * efficient (and convenient) to encode multiple packets at once. This
+ * is especially true of the NativeCode implementation where data must
+ * be copied and the Java->Native->Java transition is expensive.
+ *
+ * @param src An array of <code>k</code> byte[]'s that contain the source
+ * packets to be encoded. Often these byte[]'s are actually references
+ * to a single byte[] that contains the entire source block, then you must
+ * simply vary the srcOff's to pass it in in this fashion. src[0] will
+ * point to the 1st packet, src[1] to the second, etc.
+ *
+ * @param srcOff An array of integers which specifies the offset of each
+ * each packet within its associated byte[].
+ *
+ * @param repair Much like src, variable points to a number of buffers
+ * to which the encoded repair packets will be written. This array should
+ * be the same length as repairOff and index.
+ *
+ * @param repairOff This is the repair analog to srcOff.
+ *
+ * @param index This int[] specifies the indexes of the packets to be
+ * encoded and written to <code>repair</code>. These indexes must be
+ * between 0..n (should probably be k..n, because encoding < k is a NOP)
+ *
+ * @param packetLength the packetLength in bytes. All of the buffers
+ * in src and repair are assumed to be this long.
+ */
+ protected abstract void encode(byte[][] src, int[] srcOff, byte[][] repair,
+ int[] repairOff, int[] index,
+ int packetLength);
+
+ /**
+ * This method takes an array of encoded packets and decodes them. Before
+ * the packets are decoded, they are shuffled so that packets that are
+ * original source packets (index < k) are positioned so that their
+ * index within the byte[][] is the same as their packet index. If the
+ * <code>shuffled</code> flag is set to true then it is assumed that
+ * the packets are already in the proper order. If not then they will
+ * have the references of the byte[]'s shuffled within the byte[][]. No
+ * data will be copied, only references swapped. This means that if the
+ * byte[][] is wrapping an underlying byte[] then the shuffling proceedure
+ * may bring the byte[][] out of sync with the underlying data structure.
+ * From an SPI perspective this means that the implementation is expected
+ * to follow the exact same behavior as the shuffle() method in this class
+ * which means that you should simply call shuffle() if the flag is false.
+ *
+ * @param pkts An array of <code>k</code> byte[]'s that contain the repair
+ * packets to be decoded. The decoding proceedure will copy the decoded
+ * data into the byte[]'s that are provided and will place them in order
+ * within the byte[][]. If the byte[][] is already properly shuffled
+ * then the byte[]'s will not be moved around in the byte[][].
+ *
+ * @param pktsOff An array of integers which specifies the offset of each
+ * each packet within its associated byte[].
+ *
+ * @param index This int[] specifies the indexes of the packets to be
+ * decoded. These indexes must be between 0..n
+ *
+ * @param packetLength the packetLength in bytes. All of the buffers
+ * in pkts are assumed to be this long.
+ */
+ protected abstract void decode(byte[][] pkts, int[] pktsOff,
+ int[] index, int packetLength,
+ boolean shuffled);
+
+ /**
+ * This method takes an array of source packets and generates a number
+ * of repair packets from them. This method could have taken in only
+ * one repair packet to be generated, but in many cases it is more
+ * efficient (and convenient) to encode multiple packets at once. This
+ * is especially true of the NativeCode implementation where data must
+ * be copied and the Java->Native->Java transition is expensive.
+ *
+ * @param src An array of <code>k</code> Buffers that contain the source
+ * packets to be encoded. Often these Buffers are actually references
+ * to a single byte[] that contains the entire source block.
+ *
+ * @param repair Much like src, variable points to a number of Buffers
+ * to which the encoded repair packets will be written. This array should
+ * be the same length as index.
+ *
+ * @param index This int[] specifies the indexes of the packets to be
+ * encoded and written to <code>repair</code>. These indexes must be
+ * between 0..n (should probably be k..n, because encoding < k is a NOP)
+ *
+ */
+ public void encode(Buffer[] src, Buffer[] repair, int[] index) {
+ byte[][] srcBufs = new byte[src.length][];
+ int[] srcOffs = new int[src.length];
+ byte[][] repairBufs = new byte[repair.length][];
+ int[] repairOffs = new int[repair.length];
+ for (int i=0;i<srcBufs.length;i++) {
+ srcBufs[i] = src[i].b;
+ srcOffs[i] = src[i].off;
+ }
+ for (int i=0;i<repairBufs.length;i++) {
+ repairBufs[i] = repair[i].b;
+ repairOffs[i] = repair[i].off;
+ }
+
+ encode(srcBufs,srcOffs,repairBufs,repairOffs,index,src[0].len);
+ }
+
+ /*
+ protected void checkArguments() {
+ if (index < 0 || index >= n) {
+ throw new IllegalArgumentException("Invalid index "+index+
+ " (max "+(n-1)+")");
+ }
+ if (buf.len != repair.len) {
+ throw new IllegalArgumentException
+ ("Source buffer and output buffer not same length");
+ }
+
+ if (pkts.length != k || index.length != k) {
+ throw new IllegalArgumentException("Must be exactly k packets "+
+ "and index entries.");
+ }
+ }*/
+
+ /**
+ * This method takes an array of encoded packets and decodes them. Before
+ * the packets are decoded, they are shuffled so that packets that are
+ * original source packets (index < k) are positioned so that their
+ * index within the byte[][] is the same as their packet index.
+ *
+ * We shuffle the packets using the copy mechanism to allow API users to
+ * be guarenteed that the Buffer[] references will not be shuffled around.
+ * This allows the Buffer[] to wrap an underlying byte[], and once
+ * decoding is complete the entire block will be in the proper order
+ * in the underlying byte[]. If the packets are already in the proper
+ * position then no copying will take place.
+ *
+ * @param pkts An array of <code>k</code> Buffers that contain the repair
+ * packets to be decoded. The decoding proceedure will copy the decoded
+ * data into the Buffers that are provided and will place them in order
+ * within the Buffer[]. If the Buffers are already properly shuffled
+ * then no data will be copied around during the shuffle proceedure.
+ *
+ * @param index This int[] specifies the indexes of the packets to be
+ * decoded. These indexes must be between 0..n
+ *
+ */
+ public void decode(Buffer[] pkts, int[] index) {
+ // Must pre-shuffle so that no future shuffles bring the byte[]'s
+ // out of sync with the Buffer[]'s. We use copyShuffle so that
+ // the Buffer[]'s don't have their references shuffled around and
+ // therefore we can have the Buffer[]'s wrapping one large byte[]
+ // that will be decoded with all of the data in order in that block.
+ copyShuffle(pkts,index,k);
+
+ byte[][] bufs = new byte[pkts.length][];
+ int[] offs = new int[pkts.length];
+ for (int i=0;i<bufs.length;i++) {
+ bufs[i] = pkts[i].b;
+ offs[i] = pkts[i].off;
+ }
+ decode(bufs,offs,index,pkts[0].len,true);
+ }
+
+ /**
+ * Move packets with index < k into their position. This method
+ * copies the data using System.arraycopy rather than modifying the
+ * Buffer[].
+ */
+ protected static final void copyShuffle(Buffer[] pkts, int index[], int k){
+ byte[] b = null;
+ for (int i = 0;i < k ;) {
+ if (index[i] >= k || index[i] == i) {
+ i++;
+ } else {
+ // put pkts in the right position (first check for conflicts).
+ int c = index[i];
+
+ if (index[c] == c) {
+ throw new IllegalArgumentException
+ ("Shuffle Error: Duplicate indexes at "+i);
+ }
+ // swap(index[c],index[i])
+ int tmp = index[i];
+ index[i] = index[c];
+ index[c] = tmp;
+
+ // swap(pkts[c],pkts[i])
+ if (b == null) {
+ b = new byte[pkts[0].len];
+ }
+ System.arraycopy(pkts[i].b,pkts[i].off,b,0,b.length);
+ System.arraycopy(pkts[c].b,pkts[c].off,pkts[i].b,pkts[i].off,
+ b.length);
+ System.arraycopy(b,0,pkts[c].b,pkts[c].off,b.length);
+ }
+ }
+ }
+
+ /**
+ * shuffle move src packets in their position
+ */
+ protected static final void shuffle(byte[][] pkts, int[] pktsOff,
+ int[] index, int k) {
+ for (int i=0; i<k;) {
+ if (index[i] >= k || index[i] == i) {
+ i++;
+ } else {
+ // put pkts in the right position (first check for conflicts).
+ int c = index[i] ;
+
+ if (index[c] == c) {
+ throw new IllegalArgumentException("Shuffle error at "+i);
+ }
+ // swap(pkts[c],pkts[i])
+ byte[] tmp = pkts[i];
+ pkts[i] = pkts[c];
+ pkts[c] = tmp;
+
+ // swap(pktsOff[c],pktsOff[i])
+ int tmp2 = pktsOff[i];
+ pktsOff[i] = pktsOff[c];
+ pktsOff[c] = tmp2;
+
+ // swap(index[c],index[i])
+ tmp2 = index[i];
+ index[i] = index[c];
+ index[c] = tmp2;
+ }
+ }
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/FECCodeFactory.java (from
rev 26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/FECCodeFactory.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/FECCodeFactory.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/FECCodeFactory.java
2009-03-31 13:09:45 UTC (rev 26281)
@@ -0,0 +1,51 @@
+package com.onionnetworks.fec;
+
+/**
+ * This is the abstract class is subclassed in order to plug in new FEC
+ * implementations. If you wish to use the default implementation defined by
+ * the property "com.onionnetworks.fec.defaultcodefactoryclass" you should
+ * simply call:
+ *
+ * <code>
+ * FECCodeFactory factory = FECCodeFactory.getDefault();
+ * </code>
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public abstract class FECCodeFactory {
+
+ protected static FECCodeFactory def;
+
+ protected FECCodeFactory() {}
+
+ /**
+ * @return An FECCode for the appropriate <code>k</code> and <code>n</code>
+ * values.
+ */
+ public abstract FECCode createFECCode(int k, int n);
+
+ /**
+ * @return The default FECCodeFactory which is defined by the property
+ * "com.onionnetworks.fec.defaultcodefactoryclass". If this property is
+ * not defined then DefaultFECCodeFactory will be used by default.
+ */
+ public synchronized static FECCodeFactory getDefault() {
+ if (def == null) {
+ try {
+ Class clazz = Class.forName
+ (System.getProperty
+ ("com.onionnetworks.fec.defaultcodefactoryclass",
+ "com.onionnetworks.fec.DefaultFECCodeFactory"));
+ def = (FECCodeFactory) clazz.newInstance();
+ } catch (Exception e) {
+ // krunky structure, but the easiest way to deal with the
+ // exception.
+ def = new DefaultFECCodeFactory();
+ }
+ }
+ return def;
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/FECMath.java (from rev
26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/FECMath.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/FECMath.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/FECMath.java 2009-03-31
13:09:45 UTC (rev 26281)
@@ -0,0 +1,665 @@
+package com.onionnetworks.fec;
+
+import com.onionnetworks.util.Util;
+
+/**
+ * This class provides the majority of the logic for the pure Java
+ * implementation of the vandermonde FEC codes. This code is heavily derived
+ * from Luigi Rizzo's original C implementation. Copyright information can
+ * be found in the 'LICENSE' file that comes with this distribution.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public class FECMath {
+
+ /**
+ * The following parameter defines how many bits are used for
+ * field elements. This probably only supports 8 and 16 bit codes
+ * at this time because Java lacks a typedef construct. This code
+ * should perhaps be redone with some sort of template language/
+ * precompiler for Java.
+ */
+
+ // code over GF(2**gfBits) - change to suit
+ public int gfBits;
+
+ /*
+ * You should not need to change anything beyond this point.
+ * The first part of the file implements linear algebra in GF.
+ *
+ * gf is the type used to store an element of the Galois Field.
+ * Must constain at least gfBits bits.
+ */
+ // 2^n-1 = the number of elements in this extension field
+ public int gfSize; // powers of alpha
+
+ /**
+ * Primitive polynomials - see Lin & Costello, Appendix A,
+ * and Lee & Messerschmitt, p. 453.
+ */
+ public static final String[] prim_polys = {
+ // gfBits polynomial
+ null, // 0 no code
+ null, // 1 no code
+ "111", // 2 1+x+x^2
+ "1101", // 3 1+x+x^3
+ "11001", // 4 1+x+x^4
+ "101001", // 5 1+x^2+x^5
+ "1100001", // 6 1+x+x^6
+ "10010001", // 7 1 + x^3 + x^7
+ "101110001", // 8 1+x^2+x^3+x^4+x^8
+ "1000100001", // 9 1+x^4+x^9
+ "10010000001", // 10 1+x^3+x^10
+ "101000000001", // 11 1+x^2+x^11
+ "1100101000001", // 12 1+x+x^4+x^6+x^12
+ "11011000000001", // 13 1+x+x^3+x^4+x^13
+ "110000100010001", // 14 1+x+x^6+x^10+x^14
+ "1100000000000001", // 15 1+x+x^15
+ "11010000000010001" // 16 1+x+x^3+x^12+x^16
+ };
+
+
+ /**
+ * To speed up computations, we have tables for logarithm, exponent
+ * and inverse of a number. If gfBits <= 8, we use a table for
+ * multiplication as well (it takes 64K, no big deal even on a PDA,
+ * especially because it can be pre-initialized an put into a ROM!),
+ * otherwhise we use a table of logarithms.
+ */
+
+ // index->poly form conversion table
+ public char[] gf_exp;
+ // Poly->index form conversion table
+ public int[] gf_log;
+ // inverse of field elem.
+ public char[] inverse;
+
+ // inv[\alpha**i]=\alpha**(gfSize-i-1)
+
+ /**
+ * gf_mul(x,y) multiplies two numbers. If gfBits<=8, it is much
+ * faster to use a multiplication table.
+ *
+ * USE_GF_MULC, GF_MULC0(c) and GF_ADDMULC(x) can be used when multiplying
+ * many numbers by the same constant. In this case the first
+ * call sets the constant, and others perform the multiplications.
+ * A value related to the multiplication is held in a local variable
+ * declared with USE_GF_MULC . See usage in addMul1().
+ */
+ public char[][] gf_mul_table;
+
+ public FECMath() {
+ this(8);
+ }
+
+ public FECMath(int gfBits) {
+ this.gfBits = gfBits;
+ this.gfSize = ((1 << gfBits) - 1);
+
+ gf_exp = new char[2*gfSize];
+ gf_log = new int[gfSize+1];
+ inverse = new char[gfSize+1];
+
+ if (gfBits < 2 || gfBits > 16) {
+ throw new IllegalArgumentException("gfBits must be 2 .. 16");
+ }
+ generateGF();
+ if (gfBits <= 8) {
+ initMulTable();
+ }
+ }
+
+ public final void generateGF() {
+ int i;
+
+ String primPoly = prim_polys[gfBits];
+
+ char mask = 1; // x ** 0 = 1
+ gf_exp[gfBits] = 0; // will be updated at the end of the 1st loop
+ /*
+ * first, generate the (polynomial representation of) powers of \alpha,
+ * which are stored in gf_exp[i] = \alpha ** i .
+ * At the same time build gf_log[gf_exp[i]] = i .
+ * The first gfBits powers are simply bits shifted to the left.
+ */
+ for (i = 0; i < gfBits; i++, mask <<= 1 ) {
+ gf_exp[i] = mask;
+ gf_log[gf_exp[i]] = i;
+ /*
+ * If primPoly[i] == 1 then \alpha ** i occurs in poly-repr
+ * gf_exp[gfBits] = \alpha ** gfBits
+ */
+ if (primPoly.charAt(i) == '1') {
+ gf_exp[gfBits] ^= mask;
+ }
+ }
+ /*
+ * now gf_exp[gfBits] = \alpha ** gfBits is complete, so can als
+ * compute its inverse.
+ */
+ gf_log[gf_exp[gfBits]] = gfBits;
+ /*
+ * Poly-repr of \alpha ** (i+1) is given by poly-repr of
+ * \alpha ** i shifted left one-bit and accounting for any
+ * \alpha ** gfBits term that may occur when poly-repr of
+ * \alpha ** i is shifted.
+ */
+ mask = (char) (1 << (gfBits - 1)) ;
+ for (i = gfBits + 1; i < gfSize; i++) {
+ if (gf_exp[i-1] >= mask) {
+ gf_exp[i] = (char) (gf_exp[gfBits] ^
+ ((gf_exp[i-1] ^ mask) << 1));
+ } else {
+ gf_exp[i] = (char) (gf_exp[i-1] << 1);
+ }
+ gf_log[gf_exp[i]] = i;
+ }
+ /*
+ * log(0) is not defined, so use a special value
+ */
+ gf_log[0] = gfSize;
+ // set the extended gf_exp values for fast multiply
+ for (i = 0 ; i < gfSize ; i++) {
+ gf_exp[i + gfSize] = gf_exp[i];
+ }
+
+ /*
+ * again special cases. 0 has no inverse. This used to
+ * be initialized to gfSize, but it should make no difference
+ * since noone is supposed to read from here.
+ */
+ inverse[0] = 0 ;
+ inverse[1] = 1;
+ for (i=2; i<=gfSize; i++) {
+ inverse[i] = gf_exp[gfSize-gf_log[i]];
+ }
+ }
+
+ public final void initMulTable() {
+ if (gfBits <= 8) {
+ gf_mul_table = new char[gfSize + 1][gfSize + 1];
+
+ int i, j;
+ for (i=0; i< gfSize+1; i++) {
+ for (j=0; j< gfSize+1; j++) {
+ gf_mul_table[i][j] = gf_exp[modnn(gf_log[i] + gf_log[j])];
+ }
+ }
+ for (j=0; j< gfSize+1; j++) {
+ gf_mul_table[0][j] = gf_mul_table[j][0] = 0;
+ }
+ }
+ }
+
+ /**
+ * modnn(x) computes x % gfSize, where gfSize is 2**gfBits - 1,
+ * without a slow divide.
+ */
+ public final char modnn(int x) {
+ while (x >= gfSize) {
+ x -= gfSize;
+ x = (x >> gfBits) + (x & gfSize);
+ }
+ return (char) x;
+ }
+
+ public final char mul(char x, char y) {
+ if (gfBits <= 8) {
+ return gf_mul_table[x][y];
+ } else {
+ if (x == 0 || y == 0) {
+ return 0;
+ }
+
+ return gf_exp[gf_log[x] + gf_log[y]] ;
+ }
+ }
+
+ /**
+ * Generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m]
+ * Lookup tables:
+ * index->polynomial form gf_exp[] contains j= \alpha^i;
+ * polynomial form -> index form gf_log[ j = \alpha^i ] = i
+ * \alpha=x is the primitive element of GF(2^m)
+ *
+ * For efficiency, gf_exp[] has size 2*gfSize, so that a simple
+ * multiplication of two numbers can be resolved without calling modnn
+ */
+ public static final char[] createGFMatrix(int rows, int cols) {
+ return new char[rows * cols];
+ }
+
+ /*
+ * addMul() computes dst[] = dst[] + c * src[]
+ * This is used often, so better optimize it! Currently the loop is
+ * unrolled 16 times, a good value for 486 and pentium-class machines.
+ * The case c=0 is also optimized, whereas c=1 is not. These
+ * calls are unfrequent in my typical apps so I did not bother.
+ *
+ */
+ public final void addMul(char[] dst, int dstPos, char[] src,
+ int srcPos, char c, int len) {
+ // nop, optimize
+ if (c == 0) {
+ return;
+ }
+
+ int unroll = 16; // unroll the loop 16 times.
+ int i = dstPos;
+ int j = srcPos;
+ int lim = dstPos + len;
+
+ if (gfBits <= 8) { // use our multiplication table.
+ // Instead of doing gf_mul_table[c,x] for multiply, we'll save
+ // the gf_mul_table[c] to a local variable since it is going to
+ // be used many times.
+ char[] gf_mulc = gf_mul_table[c];
+
+ // Not sure if loop unrolling has any real benefit in Java, but
+ // what the hey.
+ for (;i < lim && (lim-i) > unroll; i += unroll, j += unroll) {
+ // dst ^= gf_mulc[x] is equal to mult then add (xor == add)
+
+ dst[i] ^= gf_mulc[src[j]];
+ dst[i+1] ^= gf_mulc[src[j+1]];
+ dst[i+2] ^= gf_mulc[src[j+2]];
+ dst[i+3] ^= gf_mulc[src[j+3]];
+ dst[i+4] ^= gf_mulc[src[j+4]];
+ dst[i+5] ^= gf_mulc[src[j+5]];
+ dst[i+6] ^= gf_mulc[src[j+6]];
+ dst[i+7] ^= gf_mulc[src[j+7]];
+ dst[i+8] ^= gf_mulc[src[j+8]];
+ dst[i+9] ^= gf_mulc[src[j+9]];
+ dst[i+10] ^= gf_mulc[src[j+10]];
+ dst[i+11] ^= gf_mulc[src[j+11]];
+ dst[i+12] ^= gf_mulc[src[j+12]];
+ dst[i+13] ^= gf_mulc[src[j+13]];
+ dst[i+14] ^= gf_mulc[src[j+14]];
+ dst[i+15] ^= gf_mulc[src[j+15]];
+ }
+
+ // final components
+ for (;i < lim; i++, j++) {
+ dst[i] ^= gf_mulc[src[j]];
+ }
+
+ } else { // gfBits > 8, no multiplication table
+ int mulcPos = gf_log[c];
+
+ // unroll your own damn loop.
+ int y;
+ for (;i < lim;i++,j++) {
+ if ((y=src[j]) != 0) {
+ dst[i] ^= gf_exp[mulcPos+gf_log[y]];
+ }
+ }
+ }
+ }
+
+ /*
+ * addMul() computes dst[] = dst[] + c * src[]
+ * This is used often, so better optimize it! Currently the loop is
+ * unrolled 16 times, a good value for 486 and pentium-class machines.
+ * The case c=0 is also optimized, whereas c=1 is not. These
+ * calls are unfrequent in my typical apps so I did not bother.
+ *
+ */
+ public final void addMul(byte[] dst, int dstPos, byte[] src,
+ int srcPos, byte c, int len) {
+ // nop, optimize
+ if (c == 0) {
+ return;
+ }
+
+ int unroll = 16; // unroll the loop 16 times.
+ int i = dstPos;
+ int j = srcPos;
+ int lim = dstPos + len;
+
+ // use our multiplication table.
+ // Instead of doing gf_mul_table[c,x] for multiply, we'll save
+ // the gf_mul_table[c] to a local variable since it is going to
+ // be used many times.
+ char[] gf_mulc = gf_mul_table[c & 0xff];
+
+ // Not sure if loop unrolling has any real benefit in Java, but
+ // what the hey.
+ for (;i < lim && (lim-i) > unroll; i += unroll, j += unroll) {
+ // dst ^= gf_mulc[x] is equal to mult then add (xor == add)
+
+ dst[i] ^= gf_mulc[src[j] & 0xff];
+ dst[i+1] ^= gf_mulc[src[j+1] & 0xff];
+ dst[i+2] ^= gf_mulc[src[j+2] & 0xff];
+ dst[i+3] ^= gf_mulc[src[j+3] & 0xff];
+ dst[i+4] ^= gf_mulc[src[j+4] & 0xff];
+ dst[i+5] ^= gf_mulc[src[j+5] & 0xff];
+ dst[i+6] ^= gf_mulc[src[j+6] & 0xff];
+ dst[i+7] ^= gf_mulc[src[j+7] & 0xff];
+ dst[i+8] ^= gf_mulc[src[j+8] & 0xff];
+ dst[i+9] ^= gf_mulc[src[j+9] & 0xff];
+ dst[i+10] ^= gf_mulc[src[j+10] & 0xff];
+ dst[i+11] ^= gf_mulc[src[j+11] & 0xff];
+ dst[i+12] ^= gf_mulc[src[j+12] & 0xff];
+ dst[i+13] ^= gf_mulc[src[j+13] & 0xff];
+ dst[i+14] ^= gf_mulc[src[j+14] & 0xff];
+ dst[i+15] ^= gf_mulc[src[j+15] & 0xff];
+ }
+
+ // final components
+ for (;i < lim; i++, j++) {
+ dst[i] ^= gf_mulc[src[j] & 0xff];
+ }
+ }
+
+ /*
+ * computes C = AB where A is n*k, B is k*m, C is n*m
+ */
+ public final void matMul(char[] a, char[] b, char[] c,
+ int n, int k, int m) {
+ matMul(a,0,b,0,c,0,n,k,m);
+ }
+
+ /*
+ * computes C = AB where A is n*k, B is k*m, C is n*m
+ */
+ public final void matMul(char[] a, int aStart, char[] b, int bStart,
+ char[] c, int cStart, int n, int k, int m){
+
+ for (int row = 0; row < n ; row++) {
+ for (int col = 0; col < m ; col++) {
+ int posA = row * k;
+ int posB = col;
+ char acc = 0 ;
+ for (int i = 0; i < k ; i++, posA++, posB += m) {
+ acc ^= mul(a[aStart+posA],b[bStart+posB]);
+ }
+ c[cStart+(row * m + col)] = acc ;
+ }
+ }
+ }
+
+ /*
+ * Checks to see if the square matrix is identiy
+ * @return whether it is an identity matrix or not
+ */
+ public static final boolean isIdentity(char[] m, int k) {
+ int pos = 0;
+ for (int row=0; row<k; row++) {
+ for (int col=0; col<k; col++) {
+ if ((row==col && m[pos] != 1) ||
+ (row!=col && m[pos] != 0)) {
+ return false;
+ } else {
+ pos++ ;
+ }
+ }
+ }
+ return true;
+ }
+
+
+ /*
+ * invertMatrix() takes a matrix and produces its inverse
+ * k is the size of the matrix.
+ * (Gauss-Jordan, adapted from Numerical Recipes in C)
+ * Return non-zero if singular.
+ */
+ public final void invertMatrix(char[] src, int k)
+ throws IllegalArgumentException {
+
+ int[] indxc = new int[k];
+ int[] indxr = new int[k];
+
+ // ipiv marks elements already used as pivots.
+ int[] ipiv = new int[k];
+
+ char[] id_row = createGFMatrix(1, k);
+ char[] temp_row = createGFMatrix(1, k);
+
+ for (int col = 0; col < k ; col++) {
+ /*
+ * Zeroing column 'col', look for a non-zero element.
+ * First try on the diagonal, if it fails, look elsewhere.
+ */
+ int irow = -1;
+ int icol = -1;
+ boolean foundPiv = false;
+
+ if (ipiv[col] != 1 && src[col*k + col] != 0) {
+ irow = col ;
+ icol = col ;
+ foundPiv = true;
+ }
+ if (!foundPiv) {
+ loop1: for (int row = 0 ; row < k ; row++) {
+ if (ipiv[row] != 1) {
+ for (int ix = 0 ; ix < k ; ix++) {
+ if (ipiv[ix] == 0) {
+ if (src[row*k + ix] != 0) {
+ irow = row ;
+ icol = ix ;
+ foundPiv = true;
+ break loop1;
+ }
+ } else if (ipiv[ix] > 1) {
+ throw new IllegalArgumentException
+ ("singular matrix");
+ }
+ }
+ }
+ }
+ }
+
+ // redundant??? I'm too lazy to figure it out -Justin
+ if (!foundPiv && icol == -1) {
+ throw new IllegalArgumentException("XXX pivot not found!");
+ }
+
+ // Ok, we've found a pivot by this point, so we can set the
+ // foundPiv variable back to false. The reason that this is
+ // so shittily laid out is that the original code had goto's :(
+ foundPiv = false;
+
+ ipiv[icol] = ipiv[icol] + 1;
+ /*
+ * swap rows irow and icol, so afterwards the diagonal
+ * element will be correct. Rarely done, not worth
+ * optimizing.
+ */
+ if (irow != icol) {
+ for (int ix = 0 ; ix < k ; ix++ ) {
+ // swap 'em
+ char tmp = src[irow*k + ix];
+ src[irow*k + ix] = src[icol*k + ix];
+ src[icol*k + ix] = tmp;
+ }
+ }
+ indxr[col] = irow;
+ indxc[col] = icol;
+
+ int pivotRowPos = icol*k;
+ char c = src[pivotRowPos + icol];
+ if (c == 0) {
+ throw new IllegalArgumentException("singular matrix 2");
+ }
+ if (c != 1) { /* otherwhise this is a NOP */
+ /*
+ * this is done often , but optimizing is not so
+ * fruitful, at least in the obvious ways (unrolling)
+ */
+ c = inverse[c];
+ src[pivotRowPos+icol] = 1;
+ for (int ix = 0 ; ix < k ; ix++ ) {
+ src[pivotRowPos+ix] = mul(c, src[pivotRowPos+ix]);
+ }
+ }
+ /*
+ * from all rows, remove multiples of the selected row
+ * to zero the relevant entry (in fact, the entry is not zero
+ * because we know it must be zero).
+ * (Here, if we know that the pivotRowPos is the identity,
+ * we can optimize the addMul).
+ */
+ id_row[icol] = 1;
+ if (!Util.arraysEqual(src,pivotRowPos,id_row,0,k)) {
+ for (int p = 0, ix = 0 ; ix < k ; ix++, p += k) {
+ if (ix != icol) {
+ c = src[p+icol];
+ src[p+icol] = 0;
+ addMul(src,p,src,pivotRowPos, c, k);
+ }
+ }
+ }
+ id_row[icol] = 0;
+ } // done all columns
+
+ for (int col = k-1 ; col >= 0 ; col--) {
+ if (indxr[col] <0 || indxr[col] >= k) {
+ System.err.println("AARGH, indxr[col] "+indxr[col]);
+ } else if (indxc[col] <0 || indxc[col] >= k) {
+ System.err.println("AARGH, indxc[col] "+indxc[col]);
+ } else {
+ if (indxr[col] != indxc[col] ) {
+ for (int row = 0 ; row < k ; row++ ) {
+ // swap 'em
+ char tmp = src[row*k + indxc[col]];
+ src[row*k + indxc[col]] = src[row*k + indxr[col]];
+ src[row*k + indxr[col]] = tmp;
+ }
+ }
+ }
+ }
+ }
+
+ /*
+ * fast code for inverting a vandermonde matrix.
+ * XXX NOTE: It assumes that the matrix
+ * is not singular and _IS_ a vandermonde matrix. Only uses
+ * the second column of the matrix, containing the p_i's.
+ *
+ * Algorithm borrowed from "Numerical recipes in C" -- sec.2.8, but
+ * largely revised for my purposes.
+ * p = coefficients of the matrix (p_i)
+ * q = values of the polynomial (known)
+ */
+
+ public final void invertVandermonde(char[] src, int k) {
+
+ if (k == 1) { // degenerate case, matrix must be p^0 = 1
+ return;
+ }
+
+ /*
+ * c holds the coefficient of P(x) = Prod (x - p_i), i=0..k-1
+ * b holds the coefficient for the matrix inversion
+ */
+ char[] c = createGFMatrix(1, k);
+ char[] b = createGFMatrix(1, k);
+ char[] p = createGFMatrix(1, k);
+
+ for (int j=1,i=0; i < k ; i++, j+=k) {
+ c[i] = 0;
+ p[i] = src[j]; /* p[i] */
+ }
+ /*
+ * construct coeffs. recursively. We know c[k] = 1 (implicit)
+ * and start P_0 = x - p_0, then at each stage multiply by
+ * x - p_i generating P_i = x P_{i-1} - p_i P_{i-1}
+ * After k steps we are done.
+ */
+ c[k-1] = p[0]; /* really -p(0), but x = -x in GF(2^m) */
+ for (int i = 1 ; i < k ; i++) {
+ char p_i = p[i]; /* see above comment */
+ for (int j = k-1 - ( i - 1 ) ; j < k-1 ; j++ ) {
+ c[j] ^= mul( p_i, c[j+1] );
+ }
+ c[k-1] ^= p_i;
+ }
+
+ for (int row = 0 ; row < k ; row++ ) {
+ /*
+ * synthetic division etc.
+ */
+ char xx = p[row] ;
+ char t = 1 ;
+ b[k-1] = 1 ; /* this is in fact c[k] */
+ for (int i = k-2 ; i >= 0 ; i-- ) {
+ b[i] = (char) (c[i+1] ^ mul(xx, b[i+1])) ;
+ t = (char) (mul(xx, t) ^ b[i]) ;
+ }
+ for (int col = 0 ; col < k ; col++ ) {
+ src[col*k + row] = mul(inverse[t], b[col]);
+ }
+ }
+ }
+
+ public final char[] createEncodeMatrix(int k, int n) {
+ if (k > gfSize + 1 || n > gfSize + 1 ||
+ k > n ) {
+ throw new IllegalArgumentException
+ ("Invalid parameters n="+n+",k="+k+",gfSize="+
+ gfSize);
+ }
+
+
+ char[] encMatrix = createGFMatrix(n,k);
+
+ /*
+ * The encoding matrix is computed starting with a Vandermonde matrix,
+ * and then transforming it into a systematic matrix.
+ *
+ * fill the matrix with powers of field elements, starting from 0.
+ * The first row is special, cannot be computed with exp. table.
+ */
+ char[] tmpMatrix = createGFMatrix(n, k);
+
+ tmpMatrix[0] = 1;
+ // first row should be 0's, fill in the rest.
+ for (int pos = k, row = 0; row < n-1 ; row++, pos += k) {
+ for (int col = 0 ; col < k ; col ++ ) {
+ tmpMatrix[pos+col] = gf_exp[modnn
+ (row*col)];
+ }
+ }
+
+ /*
+ * quick code to build systematic matrix: invert the top
+ * k*k vandermonde matrix, multiply right the bottom n-k rows
+ * by the inverse, and construct the identity matrix at the top.
+ */
+ // much faster than invertMatrix
+ invertVandermonde(tmpMatrix, k);
+ matMul(tmpMatrix,k*k, tmpMatrix,0,encMatrix,k*k, n - k,
+ k, k);
+
+ /*
+ * the upper matrix is I so do not bother with a slow multiply
+ */
+ Util.bzero(encMatrix, 0, k*k);
+ for (int i = 0, col = 0; col < k ; col++, i += k+1 ) {
+ encMatrix[i] = 1;
+ }
+
+ return encMatrix;
+ }
+
+ /**
+ * createDecodeMatrix constructs the encoding matrix given the
+ * indexes.
+ */
+ protected final char[] createDecodeMatrix(char[] encMatrix, int[] index,
+ int k, int n) {
+
+ char[] matrix = createGFMatrix(k, k);
+ for (int i = 0, pos = 0; i < k ; i++, pos += k) {
+ System.arraycopy(encMatrix,index[i]*k,matrix,pos,k);
+ }
+
+ invertMatrix(matrix, k);
+
+ return matrix;
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/Native16Code.java (from rev
26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/Native16Code.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/Native16Code.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/Native16Code.java
2009-03-31 13:09:45 UTC (rev 26281)
@@ -0,0 +1,79 @@
+package com.onionnetworks.fec;
+
+//import java.security.AccessController;
+//import sun.security.action.*;
+import com.onionnetworks.util.*;
+
+/**
+ * This class is the frontend for the JNI wrapper for the C implementation of
+ * the FEC Codes.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public class Native16Code extends FECCode {
+
+ // One must be very very careful not to let code escape, it stores the
+ // memory address of a fec_parms struct and if modified could give an
+ // attacker the ability to point to anything in memory.
+ private final long code;
+
+ static {
+ String path = NativeDeployer.getLibraryPath
+ (Native8Code.class.getClassLoader(),"fec16");
+ if (path != null) {
+ System.load(path);
+ } else {
+ System.out.println("Unable to find native library for fec16 for
platform "+NativeDeployer.OS_ARCH);
+ System.out.println(path);
+ }
+ }
+
+ public Native16Code(int k, int n) {
+ super(k,n);
+ code = nativeNewFEC(k,n);
+ }
+
+ protected void encode(byte[][] src, int[] srcOff, byte[][] repair,
+ int[] repairOff, int[] index, int packetLength) {
+
+ if (packetLength % 2 != 0) {
+ throw new IllegalArgumentException("For 16 bit codes, buffers "+
+ "must be 16 bit aligned.");
+ }
+ nativeEncode(code,src,srcOff,index,repair,repairOff,k,packetLength);
+ }
+
+ protected void decode(byte[][] pkts, int[] pktsOff,
+ int[] index, int packetLength, boolean inOrder) {
+ if (packetLength % 2 != 0) {
+ throw new IllegalArgumentException("For 16 bit codes, buffers "+
+ "must be 16 bit aligned.");
+ }
+ if (!inOrder) {
+ shuffle(pkts,pktsOff,index,k);
+ }
+ nativeDecode(code,pkts,pktsOff,index,k,packetLength);
+ }
+
+ protected native void nativeEncode
+ (long code, byte[][] src, int[] srcOff, int[] index, byte[][] repair,
+ int[] repairOff, int k, int packetLength);
+
+ protected native void nativeDecode(long code, byte[][] pkts, int[] pktsOff,
+ int[] index, int k, int packetLength);
+
+ protected synchronized native long nativeNewFEC(int k, int n);
+
+ protected synchronized native void nativeFreeFEC(long code);
+
+ protected void finalize() throws Throwable {
+ nativeFreeFEC(code);
+ }
+
+ public String toString() {
+ return new String("Native16Code[k="+k+",n="+n+"]");
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/Native8Code.java (from rev
26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/Native8Code.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/Native8Code.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/Native8Code.java
2009-03-31 13:09:45 UTC (rev 26281)
@@ -0,0 +1,73 @@
+package com.onionnetworks.fec;
+
+//import java.security.AccessController;
+//import sun.security.action.*;
+import com.onionnetworks.util.*;
+
+/**
+ * This class is the frontend for the JNI wrapper for the C implementation of
+ * the FEC Codes.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public class Native8Code extends FECCode {
+
+ // One must be very very careful not to let code escape, it stores the
+ // memory address of a fec_parms struct and if modified could give an
+ // attacker the ability to point to anything in memory.
+ private final long code;
+
+ static {
+ String path = NativeDeployer.getLibraryPath
+ (Native8Code.class.getClassLoader(),"fec8");
+ if (path != null) {
+ System.load(path);
+ } else {
+ System.out.println("Unable to find native library for fec8 for
platform "+NativeDeployer.OS_ARCH);
+ System.out.println(path);
+ }
+ }
+
+ public Native8Code(int k, int n) {
+ super(k,n);
+ code = nativeNewFEC(k,n);
+ }
+
+ protected void encode(byte[][] src, int[] srcOff, byte[][] repair,
+ int[] repairOff, int[] index, int packetLength) {
+
+ nativeEncode(code,src,srcOff,index,repair,repairOff,k,packetLength);
+ }
+
+ protected void decode(byte[][] pkts, int[] pktsOff,
+ int[] index, int packetLength, boolean inOrder) {
+ // We need to shuffle at this point so that the Java byte[][] stays
+ // in sync with what happens in native land.
+ if (!inOrder) {
+ shuffle(pkts,pktsOff,index,k);
+ }
+ nativeDecode(code,pkts,pktsOff,index,k,packetLength);
+ }
+
+ protected native void nativeEncode
+ (long code, byte[][] src, int[] srcOff, int[] index, byte[][] repair,
+ int[] repairOff, int k, int packetLength);
+
+ protected native void nativeDecode(long code, byte[][] pkts, int[] pktsOff,
+ int[] index, int k, int packetLength);
+
+ protected synchronized native long nativeNewFEC(int k, int n);
+
+ protected synchronized native void nativeFreeFEC(long code);
+
+ protected void finalize() throws Throwable {
+ nativeFreeFEC(code);
+ }
+
+ public String toString() {
+ return new String("Native8Code[k="+k+",n="+n+"]");
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/Pure16Code.java (from rev
26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/Pure16Code.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/Pure16Code.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/Pure16Code.java 2009-03-31
13:09:45 UTC (rev 26281)
@@ -0,0 +1,134 @@
+package com.onionnetworks.fec;
+
+import com.onionnetworks.util.Util;
+import com.onionnetworks.util.Buffer;
+/**
+ * This class, along with FECMath, provides the implementation of the pure
+ * Java 16 bit FEC codes. This is heavily dervied from Luigi Rizzos original
+ * C implementation. See the file "LICENSE" along with this distribution for
+ * additional copyright information.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public class Pure16Code extends PureCode {
+
+ protected static final FECMath fecMath = new FECMath(16);
+
+
+ /** Notes about large N support:
+ you can just generate the top k*k vandermonde matrix, call it V,
+ then invert it, then when you have k blocks generate a matrix M
+ with the k rows you need <r_i> and E = M* V^{-1} is the encoding matrix
+ for the systematic code which you then need to invert to perform
+ the decoding. Probably there is a fast way to invert E given that M
+ is also a vandermonde matrix so it is "easy" to compute M^{-1}
+ */
+
+ public Pure16Code(int k, int n) {
+ super(k,n,fecMath.createEncodeMatrix(k,n));
+ }
+
+ /**
+ * encode accepts as input pointers to n data packets of size sz,
+ * and produces as output a packet pointed to by fec, computed
+ * with index "index".
+ */
+ protected void encode(byte[][] src, int[] srcOff, byte[][] repair,
+ int[] repairOff, int[] index, int packetLength) {
+ if (packetLength % 2 != 0) {
+ throw new IllegalArgumentException("For 16 bit codes, buffers "+
+ "must be 16 bit aligned.");
+ }
+ char[][] srcChars = new char[src.length][];
+ int[] srcCharsOff = new int[src.length];
+ int numChars = packetLength/2;
+ char[] repairChars = new char[numChars];
+ for (int i=0;i<srcChars.length;i++) {
+ srcChars[i] = new char[numChars];
+ Util.arraycopy(src[i], srcOff[i], srcChars[i], 0, packetLength);
+ srcCharsOff[i] = 0;
+ }
+
+ for (int i=0;i<repair.length;i++) {
+ if (index[i] < k) { // < k, systematic so direct copy.
+ System.arraycopy(src[index[i]],srcOff[index[i]],repair[i],
+ repairOff[i], packetLength);
+ } else {
+ encode(srcChars,srcCharsOff,repairChars,0,index[i],numChars);
+ Util.arraycopy(repairChars,0,repair[i],repairOff[i],
+ packetLength);
+ }
+ }
+ }
+
+ /**
+ * ASSERT: index >= k && index < n
+ */
+ protected void encode(char[][] src, int[] srcOff, char[] repair,
+ int repairOff, int index, int numChars) {
+ int pos = index*k;
+ Util.bzero(repair,repairOff,numChars);
+ for (int i=0; i<k ; i++) {
+ fecMath.addMul(repair,repairOff,src[i],srcOff[i],
+ encMatrix[pos+i],numChars);
+ }
+ }
+
+ protected void decode(byte[][] pkts, int[] pktsOff, int[] index,
+ int packetLength, boolean inOrder) {
+ if (packetLength % 2 != 0) {
+ throw new IllegalArgumentException("For 16 bit codes, buffers "+
+ "must be 16 bit aligned.");
+ }
+
+ if (!inOrder) {
+ shuffle(pkts, pktsOff, index, k);
+ }
+
+ char[][] pktsChars = new char[pkts.length][];
+ int[] pktsCharsOff = new int[pkts.length];
+ int numChars = packetLength/2;
+ for (int i=0;i<pktsChars.length;i++) {
+ pktsChars[i] = new char[numChars];
+ Util.arraycopy(pkts[i], pktsOff[i], pktsChars[i], 0, packetLength);
+ pktsCharsOff[i] = 0;
+ }
+
+ char[][] result = decode(pktsChars, pktsCharsOff, index, numChars);
+
+ for (int i=0;i<result.length;i++) {
+ if (result[i] != null) {
+ Util.arraycopy(result[i], 0, pkts[i], pktsOff[i],
+ packetLength);
+ index[i] = i;
+ }
+ }
+ }
+
+ protected char[][] decode(char[][] pkts, int[] pktsOff, int[] index,
+ int numChars) {
+
+ char[] decMatrix = fecMath.createDecodeMatrix(encMatrix,index,k,n);
+
+ // do the actual decoding
+ char[][] tmpPkts = new char[k][];
+ for (int row=0; row<k; row++) {
+ if (index[row] >= k) {
+ tmpPkts[row] = new char[numChars];
+ for (int col=0 ; col<k ; col++) {
+ fecMath.addMul(tmpPkts[row],0,pkts[col],pktsOff[col],
+ decMatrix[row*k + col], numChars);
+ }
+ }
+ }
+
+ return tmpPkts;
+ }
+
+ public String toString() {
+ return new String("Pure16Code[k="+k+",n="+n+"]");
+ }
+}
Copied: trunk/contrib/fec/src/com/onionnetworks/fec/PureCode.java (from rev
26280, trunk/contrib/fec/fec_src/com/onionnetworks/fec/PureCode.java)
===================================================================
--- trunk/contrib/fec/src/com/onionnetworks/fec/PureCode.java
(rev 0)
+++ trunk/contrib/fec/src/com/onionnetworks/fec/PureCode.java 2009-03-31
13:09:45 UTC (rev 26281)
@@ -0,0 +1,99 @@
+package com.onionnetworks.fec;
+
+import com.onionnetworks.util.Util;
+import com.onionnetworks.util.Buffer;
+/**
+ * This class, along with FECMath, provides the implementation of the pure
+ * Java 8 bit FEC codes. This is heavily dervied from Luigi Rizzos original
+ * C implementation. See the file "LICENSE" along with this distribution for
+ * additional copyright information.
+ *
+ * (c) Copyright 2001 Onion Networks
+ * (c) Copyright 2000 OpenCola
+ *
+ * @author Justin F. Chapweske (justin at chapweske.com)
+ */
+public class PureCode extends FECCode {
+
+ // Keeping this around because it amuses me.
+ public static final int FEC_MAGIC = 0xFECC0DEC;
+ protected static final FECMath fecMath = new FECMath(8);
+ protected char[] encMatrix;
+
+ //create a new encoder. This contains n,k and the encoding matrix.
+ public PureCode(int k, int n) {
+ this(k,n,fecMath.createEncodeMatrix(k,n));
+ }
+
+ public PureCode(int k, int n, char[] encMatrix) {
+ super(k,n);
+ this.encMatrix = encMatrix;
+ }
+
+ /**
+ * encode accepts as input pointers to n data packets of size sz,
+ * and produces as output a packet pointed to by fec, computed
+ * with index "index".
+ */
+ protected void encode(byte[][] src, int[] srcOff, byte[][] repair,
+ int[] repairOff, int[] index, int packetLength) {
+ for (int i=0;i<repair.length;i++) {
+ encode(src,srcOff,repair[i],repairOff[i],index[i],packetLength);
+ }
+ }
+
+ protected void encode(byte[][] src, int[] srcOff, byte[] repair,
+ int repairOff, int index, int packetLength) {
+ // *remember* indices start at 0, k starts at 1.
+ if (index < k) { // < k, systematic so direct copy.
+ System.arraycopy(src[index],srcOff[index],repair,repairOff,
+ packetLength);
+ } else { // index >= k && index < n
+ int pos = index*k;
+ Util.bzero(repair,repairOff,packetLength);
+ for (int i=0; i<k ; i++) {
+ fecMath.addMul(repair,repairOff,src[i],srcOff[i],
+ (byte) encMatrix[pos+i],packetLength);
+ }
+ }
+ }
+
+ protected void decode(byte[][] pkts, int[] pktsOff, int[] index,
+ int packetLength, boolean shuffled) {
+ // This may be the second time shuffle has been called, if so
+ // this is ok because it will quickly determine that things are in
+ // order. The previous shuffles may have been necessary to keep
+ // another data structure in sync with the byte[]'s
+ if (!shuffled) {
+ shuffle(pkts, pktsOff, index, k);
+ }
+
+ char[] decMatrix = fecMath.createDecodeMatrix(encMatrix,index,k,n);
+
+ // do the actual decoding..
+ byte[][] tmpPkts = new byte[k][];
+ for (int row=0; row<k; row++) {
+ if (index[row] >= k) {
+ tmpPkts[row] = new byte[packetLength];
+ for (int col=0 ; col<k ; col++) {
+ fecMath.addMul(tmpPkts[row],0,pkts[col],pktsOff[col],
+ (byte) decMatrix[row*k + col],
+ packetLength);
+ }
+ }
+ }
+
+ // move pkts to their final destination
+ for (int row=0;row < k;row++) {
+ if (index[row] >= k) { // only copy those actually decoded.
+ System.arraycopy(tmpPkts[row],0, pkts[row],pktsOff[row],
+ packetLength);
+ index[row] = row;
+ }
+ }
+ }
+
+ public String toString() {
+ return new String("PureCode[k="+k+",n="+n+"]");
+ }
+}
Modified: trunk/contrib/freenet_ext/build.xml
===================================================================
--- trunk/contrib/freenet_ext/build.xml 2009-03-31 12:36:13 UTC (rev 26280)
+++ trunk/contrib/freenet_ext/build.xml 2009-03-31 13:09:45 UTC (rev 26281)
@@ -27,15 +27,13 @@
<target name="fec" depends="fec-common" description="build the
fecencoder/decoder plugins for fproxy.">
<javac destdir="${build}" optimize="on"
source="${javac.target.version}">
- <src path="../fec/fec_src"/>
+ <src path="../fec/src"/>
<classpath path="../fec/common/lib/onion-common.jar"/>
+ <exclude name="csrc/*.java"/>
</javac>
<copy file="../fec/onion_LICENSE" todir="${build}"/>
<copy todir="${build}">
- <fileset dir="../fec/fec_src">
- <include name="**/*.properties"/>
- </fileset>
<fileset dir="../fec/">
<include name="lib/"/>
</fileset>
