--- /dev/null
+package org.ibex.util;
+
+import java.io.*;
+
+public class AccessibleCharArrayWriter extends CharArrayWriter {
+ public char[] getBuf() { return buf; }
+ public AccessibleCharArrayWriter(int i) { super(i); }
+}
+
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+// FEATURE: private void intersection() { }
+// FEATURE: private void union() { }
+// FEATURE: private void subset() { }
+// FEATURE: grow if we run out of slots
+
+/** a weight-balanced tree with fake leaves */
+public class BalancedTree {
+
+
+ // Instance Variables ///////////////////////////////////////////////////////////////////
+
+ private int root = 0; ///< the slot of the root element
+
+ private int cached_index = -1;
+ private int cached_slot = -1;
+
+ // Public API //////////////////////////////////////////////////////////////////////////
+
+ /** the number of elements in the tree */
+ public final int treeSize() {
+ synchronized(BalancedTree.class) {
+ return root == 0 ? 0 : size[root];
+ }
+ }
+
+ /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
+ public final void insertNode(int index, Object o) {
+ synchronized(BalancedTree.class) {
+ if(o == null) throw new Error("can't insert nulls in the balanced tree");
+ cached_slot = cached_index = -1;
+ if (index < 0) index = 0;
+ if (index > treeSize()) index = treeSize();
+ int arg = allocateSlot(o);
+ if (root != 0) {
+ insert(index, arg, root, 0, false, false);
+ } else {
+ root = arg;
+ left[arg] = right[arg] = parent[arg] = 0;
+ size[arg] = 1;
+ }
+ }
+ }
+
+ /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
+ public final void replaceNode(int index, Object o) {
+ synchronized(BalancedTree.class) {
+ if(o == null) throw new Error("can't insert nulls in the balanced tree");
+ cached_slot = cached_index = -1;
+ if(root == 0) throw new Error("called replaceNode() on an empty tree");
+ if (index < 0) index = 0;
+ if (index >= treeSize()) index = treeSize() - 1;
+ int arg = allocateSlot(o);
+ insert(index, arg, root, 0, true, false);
+ }
+ }
+
+ /** returns the index of o; runs in O((log n)^2) time unless cache hit */
+ public final int indexNode(Object o) {
+ synchronized(BalancedTree.class) {
+ if(o == null) return -1;
+ if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
+
+ int slot = getSlot(o);
+ if(slot == -1) return -1;
+
+ int index = 0;
+ while(true) {
+ // everything to the left is before us so add that to the index
+ index += sizeof(left[slot]);
+ // we are before anything on the right
+ while(left[parent[slot]] == slot) slot = parent[slot];
+ // we end of the first node who isn't on the left, go to the node that has as its child
+ slot = parent[slot];
+ // if we just processed the root we're done
+ if(slot == 0) break;
+ // count the node we're currently on towards the index
+ index++;
+ }
+ return index;
+ }
+ }
+
+ /** returns the object at index; runs in O(log n) time unless cache hit */
+ public final Object getNode(int index) {
+ synchronized(BalancedTree.class) {
+ if (index == cached_index) return objects[cached_slot];
+
+ if (cached_index != -1) {
+ int distance = Math.abs(index - cached_index);
+ // if the in-order distance between the cached node and the
+ // target node is less than log(n), it's probably faster to
+ // search directly.
+ if ((distance < 16) && ((2 << distance) < treeSize())) {
+ while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
+ while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
+ return objects[cached_slot];
+ }
+ }
+ /*
+ cached_index = index;
+ cached_slot = get(index, root);
+ return objects[cached_slot];
+ */
+ return objects[get(index, root)];
+ }
+ }
+
+ /** deletes the object at index, returning the deleted object */
+ public final Object deleteNode(int index) {
+ synchronized(BalancedTree.class) {
+ cached_slot = cached_index = -1;
+ // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
+ int del = delete(index, root, 0);
+ left[del] = right[del] = size[del] = parent[del] = 0;
+ Object ret = objects[del];
+ objects[del] = null;
+ return ret;
+ }
+ }
+
+ public final void clear() {
+ synchronized(BalancedTree.class) {
+ if(root == 0) return;
+ int i = leftmost(root);
+ do {
+ int next = next(i);
+ objects[i] = null;
+ left[i] = right[i] = size[i] = parent[i] = 0;
+ i = next;
+ } while(i != 0);
+ root = 0;
+ }
+ }
+
+ protected void finalize() { clear(); }
+
+
+ // Node Data /////////////////////////////////////////////////////////////////////////
+
+ private final static int NUM_SLOTS = 64 * 1024;
+ // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
+
+ /**
+ * Every object inserted into *any* tree gets a "slot" in this
+ * array. The slot is determined by hashcode modulo the length of
+ * the array, with quadradic probing to resolve collisions. NOTE
+ * that the "slot" of a node is NOT the same as its index.
+ * Furthermore, if an object is inserted into multiple trees, that
+ * object will have multiple slots.
+ */
+ private static Object[] objects = new Object[NUM_SLOTS];
+
+ /// These two arrays hold the left and right children of each
+ /// slot; in other words, left[x] is the *slot* of the left child
+ /// of the node in slot x.
+ ///
+ /// If x has no left child, then left[x] is -1 multiplied by the
+ /// slot of the node that precedes x; if x is the first node, then
+ /// left[x] is 0. The right[] array works the same way.
+ ///
+ private static int[] left = new int[NUM_SLOTS];
+ private static int[] right = new int[NUM_SLOTS];
+
+ /// The parent of this node (0 if it is the root node)
+ private static int[] parent = new int[NUM_SLOTS];
+
+ ///< the number of descendants of this node *including the node itself*
+ private static int[] size = new int[NUM_SLOTS];
+
+
+ // Slot Management //////////////////////////////////////////////////////////////////////
+
+ /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
+ private int getSlot(Object o, boolean alloc) {
+ // we XOR with our own hashcode so that we don't get tons of
+ // collisions when a single Object is inserted into multiple
+ // trees
+ int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
+ Object search = alloc ? null : o;
+ int odest = dest;
+ boolean plus = true;
+ int tries = 1;
+ if(dest == 0) dest=1;
+ while (objects[dest] != search || !(alloc || root(dest) == root)) {
+ dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
+ if (dest == 0) dest=1;
+ if (plus) tries++;
+ plus = !plus;
+ // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
+ }
+ return dest;
+ }
+
+ /** returns the slots holding object o */
+ private int getSlot(Object o) { return getSlot(o,false); }
+
+ /** allocates a new slot holding object o*/
+ private int allocateSlot(Object o) {
+ int slot = getSlot(o, true);
+ // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
+ objects[slot] = o;
+ return slot;
+ }
+
+
+
+ // Helpers /////////////////////////////////////////////////////////////////////////
+
+ private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
+ private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
+ private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
+ private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
+ private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
+ private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
+
+
+ // Rotation and Balancing /////////////////////////////////////////////////////////////
+
+ // p p
+ // | |
+ // b d
+ // / \ / \
+ // a d < == > b e
+ // / \ / \
+ // c e a c
+ // FIXME might be doing too much work here
+ private void rotate(boolean toTheLeft, int b, int p) {
+ int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
+ int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
+ int d = right[b];
+ int c = left[d];
+ if (d <= 0) throw new Error("rotation error");
+ left[d] = b;
+ right[b] = c <= 0 ? -d : c;
+
+ parent[b] = d;
+ parent[d] = p;
+ if(c > 0) parent[c] = b;
+ if (p == 0) root = d;
+ else if (left[p] == b) left[p] = d;
+ else if (right[p] == b) right[p] = d;
+ else throw new Error("rotate called with invalid parent");
+ size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
+ size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
+ }
+
+ private void balance(int slot, int p) {
+ if (slot <= 0) return;
+ size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
+ if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
+ else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
+ }
+
+
+
+ // Insert /////////////////////////////////////////////////////////////////////////
+
+ private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
+ int diff = slot <= 0 ? 0 : index - sizeof(left[slot]);
+ if (slot > 0 && diff != 0) {
+ if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
+ else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
+ balance(slot, p);
+ return;
+ }
+
+ if (size[arg] != 0) throw new Error("double insertion");
+
+ // we are replacing an existing node
+ if (replace) {
+ if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
+ if (p == 0) root = arg;
+ else if (left[p] == slot) left[p] = arg;
+ else if (right[p] == slot) right[p] = arg;
+ left[arg] = left[slot];
+ right[arg] = right[slot];
+ size[arg] = size[slot];
+ parent[arg] = parent[slot];
+ if(left[slot] > 0) parent[left[slot]] = arg;
+ if(right[slot] > 0) parent[right[slot]] = arg;
+ objects[slot] = null;
+ left[slot] = right[slot] = size[slot] = parent[slot] = 0;
+
+ // we become the child of a former leaf
+ } else if (slot <= 0) {
+ int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
+ int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
+ left[arg] = slot;
+ left[p] = arg;
+ right[arg] = -1 * p;
+ parent[arg] = p;
+ balance(arg, p);
+
+ // we take the place of a preexisting node
+ } else {
+ left[arg] = left[slot]; // steal slot's left subtree
+ left[slot] = -1 * arg;
+ right[arg] = slot; // make slot our right subtree
+ parent[arg] = parent[slot];
+ parent[slot] = arg;
+ if (slot == root) {
+ root = arg;
+ balance(slot, arg);
+ balance(arg, 0);
+ } else {
+ if (left[p] == slot) left[p] = arg;
+ else if (right[p] == slot) right[p] = arg;
+ else throw new Error("should never happen");
+ balance(slot, arg);
+ balance(arg, p);
+ }
+ }
+ }
+
+
+ // Retrieval //////////////////////////////////////////////////////////////////////
+
+ private int get(int index, int slot) {
+ int diff = index - sizeof(left[slot]);
+ if (diff > 0) return get(diff - 1, right[slot]);
+ else if (diff < 0) return get(index, left[slot]);
+ else return slot;
+ }
+
+
+ // Deletion //////////////////////////////////////////////////////////////////////
+
+ private int delete(int index, int slot, int p) {
+ int diff = index - sizeof(left[slot]);
+ if (diff < 0) {
+ int ret = delete(index, left[slot], slot);
+ balance(slot, p);
+ return ret;
+
+ } else if (diff > 0) {
+ int ret = delete(diff - 1, right[slot], slot);
+ balance(slot, p);
+ return ret;
+
+ // we found the node to delete
+ } else {
+
+ // fast path: it has no children
+ if (left[slot] <= 0 && right[slot] <= 0) {
+ if (p == 0) root = 0;
+ else {
+ int[] side = left[p] == slot ? left : right;
+ side[p] = side[slot]; // fix parent's pointer
+ }
+
+ // fast path: it has no left child, so we replace it with its right child
+ } else if (left[slot] <= 0) {
+ if (p == 0) root = right[slot];
+ else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer
+ parent[right[slot]] = p;
+ left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
+ balance(right[slot], p);
+
+ // fast path; it has no right child, so we replace it with its left child
+ } else if (right[slot] <= 0) {
+ if (p == 0) root = left[slot];
+ else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer
+ parent[left[slot]] = p;
+ right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
+ balance(left[slot], p);
+
+ // node to be deleted has two children, so we replace it with its left child's rightmost descendant
+ } else {
+ int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
+ left[left_childs_rightmost] = left[slot];
+ right[left_childs_rightmost] = right[slot];
+ if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
+ if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
+ parent[left_childs_rightmost] = parent[slot];
+ if (p == 0) root = left_childs_rightmost;
+ else (left[p] == slot ? left : right)[p] = left_childs_rightmost; // fix parent's pointer
+ balance(left_childs_rightmost, p);
+ }
+
+ return slot;
+ }
+ }
+
+ // Debugging ///////////////////////////////////////////////////////////////////////////
+
+ public void printTree() {
+ if(root == 0) System.err.println("Tree is empty");
+ else printTree(root,0,false);
+ }
+ private void printTree(int node,int indent,boolean l) {
+ for(int i=0;i<indent;i++) System.err.print(" ");
+ if(node < 0) System.err.println((l?"Prev: " : "Next: ") + -node);
+ else if(node == 0) System.err.println(l ? "Start" : "End");
+ else {
+ System.err.print("" + node + ": " + objects[node]);
+ System.err.println(" Parent: " + parent[node]);
+ printTree(left[node],indent+1,true);
+ printTree(right[node],indent+1,false);
+ }
+ }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+import java.io.*;
+import java.util.*;
+import java.util.zip.*;
+
+/** Reads a CAB file structure */
+public class CAB {
+
+ /** reads a CAB file, parses it, and returns an InputStream representing the named file */
+ public static InputStream getFileInputStream(InputStream is, String fileName) throws IOException, EOFException {
+ return getFileInputStream(is, 0, fileName);
+ }
+
+ public static InputStream getFileInputStream(InputStream is, int skipHeaders, String fileName) throws IOException, EOFException {
+ DataInputStream dis = new DataInputStream(is);
+ CFHEADER h = new CFHEADER();
+
+ while (skipHeaders > 0) { CFHEADER.seekMSCF(dis); skipHeaders--; }
+
+ try {
+ h.read(dis);
+ } catch (CFHEADER.BogusHeaderException bhe) {
+ throw new EOFException();
+ }
+
+ for(int i=0; i<h.folders.length; i++) {
+ CFFOLDER f = new CFFOLDER(h);
+ try {
+ f.read(dis);
+ } catch (CFFOLDER.UnsupportedCompressionTypeException ucte) {
+ throw ucte;
+ }
+ }
+
+ for(int i=0; i<h.files.length; i++) {
+ CFFILE f = new CFFILE(h);
+ f.read(dis);
+ }
+
+ for(int i=0; i<h.folders.length; i++) {
+ InputStream is2 = new CFFOLDERInputStream(h.folders[i], dis);
+ for(int j=0; j<h.folders[i].files.size(); j++) {
+ CFFILE file = (CFFILE)h.folders[i].files.elementAt(j);
+ if (file.fileName.equals(fileName)) return new LimitStream(is2, file.fileSize);
+ byte[] b = new byte[file.fileSize];
+ }
+ }
+
+ return null;
+ }
+
+ private static class LimitStream extends FilterInputStream {
+ int limit;
+ public LimitStream(InputStream is, int limit) {
+ super(is);
+ this.limit = limit;
+ }
+ public int read() throws IOException {
+ if (limit == 0) return -1;
+ int ret = super.read();
+ if (ret != -1) limit--;
+ return ret;
+ }
+ public int read(byte[] b, int off, int len) throws IOException {
+ if (len > limit) len = limit;
+ if (limit == 0) return -1;
+ int ret = super.read(b, off, len);
+ limit -= ret;
+ return ret;
+ }
+ }
+
+ /** Encapsulates a CFHEADER entry */
+ public static class CFHEADER {
+ byte[] reserved1 = new byte[4]; // reserved
+ int fileSize = 0; // size of this cabinet file in bytes
+ byte[] reserved2 = new byte[4]; // reserved
+ int offsetOfFirstCFFILEEntry; // offset of the first CFFILE entry
+ byte[] reserved3 = new byte[4]; // reserved
+ byte versionMinor = 3; // cabinet file format version, minor
+ byte versionMajor = 1; // cabinet file format version, major
+ boolean prevCAB = false; // true iff there is a cabinet before this one in a sequence
+ boolean nextCAB = false; // true iff there is a cabinet after this one in a sequence
+ boolean hasReserved = false; // true iff the cab has per-{cabinet, folder, block} reserved areas
+ int setID = 0; // must be the same for all cabinets in a set
+ int indexInCabinetSet = 0; // number of this cabinet file in a set
+ byte perCFFOLDERReservedSize = 0; // (optional) size of per-folder reserved area
+ byte perDatablockReservedSize = 0; // (optional) size of per-datablock reserved area
+ byte[] perCabinetReservedArea = null; // per-cabinet reserved area
+ String previousCabinet = null; // name of previous cabinet file in a set
+ String previousDisk = null; // name of previous disk in a set
+ String nextCabinet = null; // name of next cabinet in a set
+ String nextDisk = null; // name of next disk in a set
+
+ CFFOLDER[] folders = new CFFOLDER[0];
+ CFFILE[] files = new CFFILE[0];
+
+ int readCFFOLDERs = 0; // the number of folders read in so far
+ int readCFFILEs = 0; // the number of folders read in so far
+
+ public void print(PrintStream ps) {
+ ps.println("CAB CFFILE CFHEADER v" + ((int)versionMajor) + "." + ((int)versionMinor));
+ ps.println(" total file size = " + fileSize);
+ ps.println(" offset of first file = " + offsetOfFirstCFFILEEntry);
+ ps.println(" total folders = " + folders.length);
+ ps.println(" total files = " + files.length);
+ ps.println(" flags = 0x" +
+ Integer.toString((prevCAB ? 0x1 : 0x0) |
+ (nextCAB ? 0x2 : 0x0) |
+ (hasReserved ? 0x4 : 0x0), 16) + " [ " +
+ (prevCAB ? "prev " : "") +
+ (nextCAB ? "next " : "") +
+ (hasReserved ? "reserve_present " : "") + "]");
+ ps.println(" set id = " + setID);
+ ps.println(" index in set = " + indexInCabinetSet);
+ ps.println(" header reserved area #1 =" +
+ " 0x" + Integer.toString(reserved1[0], 16) +
+ " 0x" + Integer.toString(reserved1[1], 16) +
+ " 0x" + Integer.toString(reserved1[2], 16) +
+ " 0x" + Integer.toString(reserved1[3], 16));
+ ps.println(" header reserved area #2 =" +
+ " 0x" + Integer.toString(reserved2[0], 16) +
+ " 0x" + Integer.toString(reserved2[1], 16) +
+ " 0x" + Integer.toString(reserved2[2], 16) +
+ " 0x" + Integer.toString(reserved2[3], 16));
+ ps.println(" header reserved area #3 =" +
+ " 0x" + Integer.toString(reserved3[0], 16) +
+ " 0x" + Integer.toString(reserved3[1], 16) +
+ " 0x" + Integer.toString(reserved3[2], 16) +
+ " 0x" + Integer.toString(reserved3[3], 16));
+ if (hasReserved) {
+ if (perCabinetReservedArea != null) {
+ ps.print(" per-cabinet reserved area = ");
+ for(int i=0; i<perCabinetReservedArea.length; i++)
+ ps.print(((perCabinetReservedArea[i] & 0xff) < 16 ? "0" : "") +
+ Integer.toString(perCabinetReservedArea[i] & 0xff, 16) + " ");
+ ps.println();
+ }
+ ps.println(" per folder reserved area = " + perCFFOLDERReservedSize + " bytes");
+ ps.println(" per block reserved area = " + perDatablockReservedSize + " bytes");
+ }
+ }
+
+ public String toString() {
+ return
+ "[ CAB CFFILE CFHEADER v" +
+ ((int)versionMajor) + "." + ((int)versionMinor) + ", " +
+ fileSize + " bytes, " +
+ folders.length + " folders, " +
+ files.length + " files] ";
+ }
+
+ /** fills in all fields in the header and positions the stream at the first folder */
+ public void read(DataInputStream dis) throws IOException, BogusHeaderException {
+ seekMSCF(dis);
+ dis.readFully(reserved1);
+
+ byte[] headerHashable = new byte[28];
+ dis.readFully(headerHashable);
+ DataInputStream hhis = new DataInputStream(new ByteArrayInputStream(headerHashable));
+
+ fileSize = readLittleInt(hhis);
+ hhis.readFully(reserved2);
+ offsetOfFirstCFFILEEntry = readLittleInt(hhis);
+ hhis.readFully(reserved3);
+ versionMinor = hhis.readByte();
+ versionMajor = hhis.readByte();
+ folders = new CFFOLDER[readLittleShort(hhis)];
+ files = new CFFILE[readLittleShort(hhis)];
+ int flags = readLittleShort(hhis);
+ prevCAB = (flags & 0x0001) != 0;
+ nextCAB = (flags & 0x0002) != 0;
+ hasReserved = (flags & 0x0004) != 0;
+ setID = readLittleShort(hhis);
+ indexInCabinetSet = readLittleShort(hhis);
+
+ if (offsetOfFirstCFFILEEntry < 0 || fileSize < 0) {
+ throw new BogusHeaderException();
+ }
+
+ if (hasReserved) {
+ perCabinetReservedArea = new byte[readLittleShort(dis)];
+ perCFFOLDERReservedSize = dis.readByte();
+ perDatablockReservedSize = dis.readByte();
+ if (perCabinetReservedArea.length > 0)
+ dis.readFully(perCabinetReservedArea);
+ }
+
+ try {
+ if (prevCAB) {
+ previousCabinet = readZeroTerminatedString(dis);
+ previousDisk = readZeroTerminatedString(dis);
+ }
+ if (nextCAB) {
+ nextCabinet = readZeroTerminatedString(dis);
+ nextDisk = readZeroTerminatedString(dis);
+ }
+ } catch (ArrayIndexOutOfBoundsException e) {
+ throw new BogusHeaderException();
+ }
+ }
+
+ public static void seekMSCF(DataInputStream dis) throws EOFException, IOException
+ {
+ int state;
+ // skip up to and including the 'MSCF' signature
+ state = 0;
+ while (state != 4) {
+ // M
+ while (state == 0 && dis.readByte() != 0x4D) { }
+ state = 1;
+ // S
+ switch (dis.readByte()) {
+ case 0x53 : state = 2; break;
+ case 0x4D : state = 1; continue;
+ default : state = 0; continue;
+ }
+ // C
+ if (dis.readByte() == 0x43) { state = 3; }
+ else { state = 0; continue; }
+ // F
+ if (dis.readByte() == 0x46) { state = 4; }
+ else { state = 0; }
+ }
+ }
+
+ public static class BogusHeaderException extends IOException {}
+ }
+
+ /** Encapsulates a CFFOLDER entry */
+ public static class CFFOLDER {
+ public static final int COMPRESSION_NONE = 0;
+ public static final int COMPRESSION_MSZIP = 1;
+ public static final int COMPRESSION_QUANTUM = 2;
+ public static final int COMPRESSION_LZX = 3;
+
+ int firstBlockOffset = 0; // offset of first data block within this folder
+ int numBlocks = 0; // number of data blocks
+ int compressionType = 0; // compression type for this folder
+ byte[] reservedArea = null; // per-folder reserved area
+ int indexInCFHEADER = 0; // our index in CFHEADER.folders
+ Vector files = new Vector();
+
+ private CFHEADER header = null;
+
+ public CFFOLDER(CFHEADER header) { this.header = header; }
+
+ public String toString() {
+ return "[ CAB CFFOLDER, " + numBlocks + " data blocks, compression type " +
+ compressionName(compressionType) +
+ ", " + reservedArea.length + " bytes of reserved data ]";
+ }
+
+ public void read(DataInputStream dis) throws IOException, UnsupportedCompressionTypeException {
+ firstBlockOffset = readLittleInt(dis);
+ numBlocks = readLittleShort(dis);
+ compressionType = readLittleShort(dis) & 0x000F;
+ if (compressionType != COMPRESSION_MSZIP) {
+ throw new UnsupportedCompressionTypeException(compressionType);
+ }
+ reservedArea = new byte[header.perCFFOLDERReservedSize];
+ if (reservedArea.length > 0) dis.readFully(reservedArea);
+ indexInCFHEADER = header.readCFFOLDERs++;
+ header.folders[indexInCFHEADER] = this;
+ }
+
+ public static String compressionName(int type) {
+ switch (type) {
+ case COMPRESSION_NONE:
+ return "NONE";
+ case COMPRESSION_MSZIP:
+ return "MSZIP";
+ case COMPRESSION_QUANTUM:
+ return "QUANTUM";
+ case COMPRESSION_LZX:
+ return "LZX";
+ default:
+ return "<Unknown type " + type + ">";
+ }
+ }
+
+ public static class UnsupportedCompressionTypeException extends IOException {
+ private int compressionType;
+
+ UnsupportedCompressionTypeException(int type) {
+ compressionType = type;
+ }
+ public String toString() {
+ return "UnsupportedCompressionTypeException: no support for compression type " + compressionName(compressionType);
+ }
+ }
+ }
+
+ /** Encapsulates a CFFILE entry */
+ public static class CFFILE {
+ int fileSize = 0; // size of this file
+ int uncompressedOffsetInCFFOLDER = 0; // offset of this file within the folder, not accounting for compression
+ int folderIndex = 0; // index of the CFFOLDER we belong to
+ Date date = null; // modification date
+ int attrs = 0; // attrs
+ boolean readOnly = false; // read-only flag
+ boolean hidden = false; // hidden flag
+ boolean system = false; // system flag
+ boolean arch = false; // archive flag
+ boolean runAfterExec = false; // true if file should be run during extraction
+ boolean UTFfileName = false; // true if filename is UTF-encoded
+ String fileName = null; // filename
+ int indexInCFHEADER = 0; // our index in CFHEADER.files
+ CFFOLDER folder = null; // the folder we belong to
+ private CFHEADER header = null;
+ File myFile;
+
+ public CFFILE(CFHEADER header) { this.header = header; }
+
+ public CFFILE(File f, String pathName) throws IOException {
+ fileSize = (int)f.length();
+ folderIndex = 0;
+ date = new java.util.Date(f.lastModified());
+ fileName = pathName;
+ myFile = f;
+ }
+
+ public String toString() {
+ return "[ CAB CFFILE: " + fileName + ", " + fileSize + " bytes [ " +
+ (readOnly ? "readonly " : "") +
+ (system ? "system " : "") +
+ (hidden ? "hidden " : "") +
+ (arch ? "arch " : "") +
+ (runAfterExec ? "run_after_exec " : "") +
+ (UTFfileName ? "UTF_filename " : "") +
+ "]";
+ }
+
+ public void read(DataInputStream dis) throws IOException {
+ fileSize = readLittleInt(dis);
+ uncompressedOffsetInCFFOLDER = readLittleInt(dis);
+ folderIndex = readLittleShort(dis);
+ readLittleShort(dis); // date
+ readLittleShort(dis); // time
+ attrs = readLittleShort(dis);
+ readOnly = (attrs & 0x1) != 0;
+ hidden = (attrs & 0x2) != 0;
+ system = (attrs & 0x4) != 0;
+ arch = (attrs & 0x20) != 0;
+ runAfterExec = (attrs & 0x40) != 0;
+ UTFfileName = (attrs & 0x80) != 0;
+ fileName = readZeroTerminatedString(dis);
+
+ indexInCFHEADER = header.readCFFILEs++;
+ header.files[indexInCFHEADER] = this;
+ folder = header.folders[folderIndex];
+ folder.files.addElement(this);
+ }
+ }
+
+
+
+
+ // Compressing Input and Output Streams ///////////////////////////////////////////////
+
+ /** an InputStream that decodes CFDATA blocks belonging to a CFFOLDER */
+ private static class CFFOLDERInputStream extends InputStream {
+ CFFOLDER folder;
+ DataInputStream dis;
+ InputStream iis = null;
+
+ byte[] compressed = new byte[128 * 1024];
+ byte[] uncompressed = new byte[256 * 1024];
+
+ public CFFOLDERInputStream(CFFOLDER f, DataInputStream dis) {
+ this.folder = f;
+ this.dis = dis;
+ }
+
+ InputStream readBlock() throws IOException {
+ int compressedBytes = readLittleShort(dis);
+ int unCompressedBytes = readLittleShort(dis);
+ byte[] reserved = new byte[/*folder.header.perDatablockReservedSize*/0];
+ if (reserved.length > 0) dis.readFully(reserved);
+ if (dis.readByte() != 0x43) throw new CABException("malformed block header");
+ if (dis.readByte() != 0x4B) throw new CABException("malformed block header");
+
+ dis.readFully(compressed, 0, compressedBytes - 2);
+
+ Inflater i = new Inflater(true);
+ i.setInput(compressed, 0, compressedBytes - 2);
+
+ if (unCompressedBytes > uncompressed.length) uncompressed = new byte[unCompressedBytes];
+ try { i.inflate(uncompressed, 0, uncompressed.length);
+ } catch (DataFormatException dfe) {
+ dfe.printStackTrace();
+ throw new CABException(dfe.toString());
+ }
+ return new ByteArrayInputStream(uncompressed, 0, unCompressedBytes);
+ }
+
+ public int available() throws IOException { return iis == null ? 0 : iis.available(); }
+ public void close() throws IOException { iis.close(); }
+ public void mark(int i) { }
+ public boolean markSupported() { return false; }
+ public void reset() { }
+
+ public long skip(long l) throws IOException {
+ if (iis == null) iis = readBlock();
+ int ret = 0;
+ while (l > ret) {
+ long numread = iis.skip(l - ret);
+ if (numread == 0 || numread == -1) iis = readBlock();
+ else ret += numread;
+ }
+ return ret;
+ }
+
+ public int read(byte[] b, int off, int len) throws IOException {
+ if (iis == null) iis = readBlock();
+ int ret = 0;
+ while (len > ret) {
+ int numread = iis.read(b, off + ret, len - ret);
+ if (numread == 0 || numread == -1) iis = readBlock();
+ else ret += numread;
+ }
+ return ret;
+ }
+
+ public int read() throws IOException {
+ if (iis == null) iis = readBlock();
+ int ret = iis.read();
+ if (ret == -1) {
+ iis = readBlock();
+ ret = iis.read();
+ }
+ return ret;
+ }
+ }
+
+
+
+ // Misc Stuff //////////////////////////////////////////////////////////////
+
+ public static String readZeroTerminatedString(DataInputStream dis) throws IOException {
+ int numBytes = 0;
+ byte[] b = new byte[256];
+ while(true) {
+ byte next = dis.readByte();
+ if (next == 0x0) return new String(b, 0, numBytes);
+ b[numBytes++] = next;
+ }
+ }
+
+ public static int readLittleInt(DataInputStream dis) throws IOException {
+ int lowest = (int)(dis.readByte() & 0xff);
+ int low = (int)(dis.readByte() & 0xff);
+ int high = (int)(dis.readByte() & 0xff);
+ int highest = (int)(dis.readByte() & 0xff);
+ return (highest << 24) | (high << 16) | (low << 8) | lowest;
+ }
+
+ public static int readLittleShort(DataInputStream dis) throws IOException {
+ int low = (int)(dis.readByte() & 0xff);
+ int high = (int)(dis.readByte() & 0xff);
+ return (high << 8) | low;
+ }
+
+ public static class CABException extends IOException {
+ public CABException(String s) { super(s); }
+ }
+
+
+ /** scratch space for isToByteArray() */
+ static byte[] workspace = new byte[16 * 1024];
+
+ /** Trivial method to completely read an InputStream */
+ public static synchronized byte[] isToByteArray(InputStream is) throws IOException {
+ int pos = 0;
+ while (true) {
+ int numread = is.read(workspace, pos, workspace.length - pos);
+ if (numread == -1) break;
+ else if (pos + numread < workspace.length) pos += numread;
+ else {
+ pos += numread;
+ byte[] temp = new byte[workspace.length * 2];
+ System.arraycopy(workspace, 0, temp, 0, workspace.length);
+ workspace = temp;
+ }
+ }
+ byte[] ret = new byte[pos];
+ System.arraycopy(workspace, 0, ret, 0, pos);
+ return ret;
+ }
+
+
+}
+
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+/*
+
+Bug report from a user:
+
+I looked at your Cache.java and tried to make good use of it, but I was
+out of luck - it wouldn't run here. Digging deeper into the code, I came
+across something that might be considered a bug. But maybe it's just a
+feature :-)
+
+
+Starting with an empty cache, Cache.put() immediately followed by
+Cache.get() on same keys / same object will set Node lru back to null in
+Node.remove() which is called in get().
+
+Assuming this put()-get() sequence is fixed, it will fill the cache, but
+lru will remain null.
+
+When cache is filled 100%, we have, at the end of the get(), where
+size>maxSize is checked, a state that mru == lru == n (from
+if(lru==null) thus deleteting the newly inserted object. Oops.
+
+
+Hope I made this clear enough. Maybe it's not a problem in xwt due to a
+different usage scheme of the cache.
+
+
+
+*/
+
+package org.ibex.util;
+
+// FIXME needs to be a weak hash
+
+/**
+ * A Hash table with a fixed size; drops extraneous elements. Uses
+ * LRU strategy.
+ */
+public class Cache extends Hash {
+
+ /** head of list is the mru; tail is the lru */
+ Node mru = null;
+ Node lru = null;
+
+ private int maxSize;
+ private Cache() { }
+ public Cache(int maxSize) {
+ super(maxSize * 2, 3);
+ this.maxSize = maxSize;
+ }
+
+ /** A doubly-linked list */
+ private class Node {
+ final Object val;
+ final Object k1;
+ final Object k2;
+ public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; }
+ Node next = null;
+ Node prev = null;
+ void remove() {
+ if (this == lru) lru = prev;
+ if (this == mru) mru = next;
+ if (next != null) next.prev = prev;
+ if (prev != null) prev.next = next;
+ next = prev = null;
+ }
+ void placeAfter(Node n) {
+ remove();
+ if (n == null) return;
+ next = n.next;
+ if (n.next != null) n.next.prev = this;
+ n.next = this;
+ prev = n;
+ }
+ void placeBefore(Node n) {
+ remove();
+ if (n == null) return;
+ next = n;
+ prev = n.prev;
+ n.prev = this;
+ if (prev != null) prev.next = this;
+ }
+ }
+
+ public void clear() {
+ lru = null;
+ super.clear();
+ }
+
+ public void remove(Object k1, Object k2) {
+ Object o = super.get(k1, k2);
+ if (o != null) ((Node)o).remove();
+ super.remove(k1, k2);
+ }
+
+ public Object get(Object k1, Object k2) {
+ Node n = (Node)super.get(k1, k2);
+ if (n == null) return null;
+ n.remove();
+ n.placeBefore(mru);
+ mru = n;
+ return n.val;
+ }
+
+ public void put(Object k1, Object k2, Object v) {
+ Node n = new Node(k1, k2, v);
+ if (lru == null) {
+ lru = mru = n;
+ } else {
+ n.placeBefore(mru);
+ mru = n;
+ }
+ if (super.get(k1, k2) != null) remove(k1, k2);
+ super.put(k1, k2, n);
+ if (size > maxSize) remove(lru.k1, lru.k2);
+ }
+
+}
+
+
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+import java.io.*;
+
+// FEATURE: don't use a byte[] if we have a diskCache file
+/**
+ * Wraps around an InputStream, caching the stream in a byte[] as it
+ * is read and permitting multiple simultaneous readers
+ */
+public class CachedInputStream {
+
+ boolean filling = false; ///< true iff some thread is blocked on us waiting for input
+ boolean eof = false; ///< true iff end of stream has been reached
+ byte[] cache = new byte[1024 * 128];
+ int size = 0;
+ final InputStream is;
+ File diskCache;
+
+ public CachedInputStream(InputStream is) { this(is, null); }
+ public CachedInputStream(InputStream is, File diskCache) {
+ this.is = is;
+ this.diskCache = diskCache;
+ }
+ public InputStream getInputStream() throws IOException {
+ if (diskCache != null && diskCache.exists()) return new FileInputStream(diskCache);
+ return new SubStream();
+ }
+
+ public void grow(int newLength) {
+ if (newLength < cache.length) return;
+ byte[] newCache = new byte[cache.length + 2 * (newLength - cache.length)];
+ System.arraycopy(cache, 0, newCache, 0, size);
+ cache = newCache;
+ }
+
+ synchronized void fillCache(int howMuch) throws IOException {
+ if (filling) { try { wait(); } catch (InterruptedException e) { }; return; }
+ filling = true;
+ grow(size + howMuch);
+ int ret = is.read(cache, size, howMuch);
+ if (ret == -1) {
+ eof = true;
+ // FIXME: probably a race here
+ if (diskCache != null && !diskCache.exists())
+ try {
+ File cacheFile = new File(diskCache + ".incomplete");
+ FileOutputStream cacheFileStream = new FileOutputStream(cacheFile);
+ cacheFileStream.write(cache, 0, size);
+ cacheFileStream.close();
+ cacheFile.renameTo(diskCache);
+ } catch (IOException e) {
+ Log.info(this, "exception thrown while writing disk cache");
+ Log.info(this, e);
+ }
+ }
+ else size += ret;
+ filling = false;
+ notifyAll();
+ }
+
+ private class SubStream extends InputStream implements KnownLength {
+ int pos = 0;
+ public int available() { return Math.max(0, size - pos); }
+ public long skip(long n) throws IOException { pos += (int)n; return n; } // FEATURE: don't skip past EOF
+ public int getLength() { return eof ? size : is instanceof KnownLength ? ((KnownLength)is).getLength() : 0; }
+ public int read() throws IOException { // FEATURE: be smarter here
+ byte[] b = new byte[1];
+ int ret = read(b, 0, 1);
+ return ret == -1 ? -1 : b[0]&0xff;
+ }
+ public int read(byte[] b, int off, int len) throws IOException {
+ synchronized(CachedInputStream.this) {
+ while (pos >= size && !eof) fillCache(pos + len - size);
+ if (eof && pos == size) return -1;
+ int count = Math.min(size - pos, len);
+ System.arraycopy(cache, pos, b, off, count);
+ pos += count;
+ return count;
+ }
+ }
+ }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+/** a simple interface for callbacks*/
+public interface Callback {
+
+ public abstract Object call(Object arg);
+
+}
--- /dev/null
+// Copyright (C) 2004 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+package org.ibex.util;
+import java.util.*;
+
+public class CounterEnumeration implements Enumeration {
+ public final int max;
+ private int cur = 0;
+ public CounterEnumeration(int i) { max = i; }
+ public void reset() { cur = 0; }
+ public boolean hasMoreElements() { return cur < max; }
+ public Object nextElement() { return new Integer(cur++); }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+/**
+ * A general-purpose data structure for holding a list of rectangular
+ * regions that need to be repainted, with intelligent coalescing.
+ *
+ * DirtyList will unify two regions A and B if the smallest rectangle
+ * enclosing both A and B occupies no more than epsilon + Area_A +
+ * Area_B. Failing this, if two corners of A fall within B, A will be
+ * shrunk to exclude the union of A and B.
+ */
+public class DirtyList {
+
+ /** The dirty regions (each one is an int[4]). */
+ private int[][] dirties = new int[10][];
+
+ /** The number of dirty regions */
+ private int numdirties = 0;
+
+ /** See class comment */
+ private static final int epsilon = 50 * 50;
+
+ public int num() { return numdirties; }
+
+ /** grows the array */
+ private void grow() {
+ int[][] newdirties = new int[dirties.length * 2][];
+ System.arraycopy(dirties, 0, newdirties, 0, numdirties);
+ dirties = newdirties;
+ }
+
+ /** Add a new rectangle to the dirty list; returns false if the
+ * region fell completely within an existing rectangle or set of
+ * rectangles (ie did not expand the dirty area)
+ */
+ public synchronized boolean dirty(int x, int y, int w, int h) {
+ if (numdirties == dirties.length) grow();
+
+ // we attempt the "lossless" combinations first
+ for(int i=0; i<numdirties; i++) {
+ int[] cur = dirties[i];
+
+ // new region falls completely within existing region
+ if (x >= cur[0] && y >= cur[1] && x + w <= cur[0] + cur[2] && y + h <= cur[1] + cur[3]) {
+ return false;
+
+ // existing region falls completely within new region
+ } else if (x <= cur[0] && y <= cur[1] && x + w >= cur[0] + cur[2] && y + h >= cur[1] + cur[3]) {
+ dirties[i][2] = 0;
+ dirties[i][3] = 0;
+
+ // left end of new region falls within existing region
+ } else if (x >= cur[0] && x < cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
+ w = x + w - (cur[0] + cur[2]);
+ x = cur[0] + cur[2];
+ i = -1; continue;
+
+ // right end of new region falls within existing region
+ } else if (x + w > cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
+ w = cur[0] - x;
+ i = -1; continue;
+
+ // top end of new region falls within existing region
+ } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y < cur[1] + cur[3]) {
+ h = y + h - (cur[1] + cur[3]);
+ y = cur[1] + cur[3];
+ i = -1; continue;
+
+ // bottom end of new region falls within existing region
+ } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y + h > cur[1] && y + h <= cur[1] + cur[3]) {
+ h = cur[1] - y;
+ i = -1; continue;
+
+ // left end of existing region falls within new region
+ } else if (dirties[i][0] >= x && dirties[i][0] < x + w && dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
+ dirties[i][2] = dirties[i][2] - (x + w - dirties[i][0]);
+ dirties[i][0] = x + w;
+ i = -1; continue;
+
+ // right end of existing region falls within new region
+ } else if (dirties[i][0] + dirties[i][2] > x && dirties[i][0] + dirties[i][2] <= x + w &&
+ dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
+ dirties[i][2] = x - dirties[i][0];
+ i = -1; continue;
+
+ // top end of existing region falls within new region
+ } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && dirties[i][1] >= y && dirties[i][1] < y + h) {
+ dirties[i][3] = dirties[i][3] - (y + h - dirties[i][1]);
+ dirties[i][1] = y + h;
+ i = -1; continue;
+
+ // bottom end of existing region falls within new region
+ } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w &&
+ dirties[i][1] + dirties[i][3] > y && dirties[i][1] + dirties[i][3] <= y + h) {
+ dirties[i][3] = y - dirties[i][1];
+ i = -1; continue;
+ }
+
+ }
+
+ // then we attempt the "lossy" combinations
+ for(int i=0; i<numdirties; i++) {
+ int[] cur = dirties[i];
+ if (w > 0 && h > 0 && cur[2] > 0 && cur[3] > 0 &&
+ ((max(x + w, cur[0] + cur[2]) - min(x, cur[0])) *
+ (max(y + h, cur[1] + cur[3]) - min(y, cur[1])) <
+ w * h + cur[2] * cur[3] + epsilon)) {
+ int a = min(cur[0], x);
+ int b = min(cur[1], y);
+ int c = max(x + w, cur[0] + cur[2]) - min(cur[0], x);
+ int d = max(y + h, cur[1] + cur[3]) - min(cur[1], y);
+ dirties[i][2] = 0;
+ dirties[i][3] = 0;
+ return dirty(a, b, c, d);
+ }
+ }
+
+ dirties[numdirties++] = new int[] { x, y, w, h };
+ return true;
+ }
+
+ /** Returns true if there are no regions that need repainting */
+ public boolean empty() { return (numdirties == 0); }
+
+ /**
+ * Atomically returns the list of dirty rectangles as an array of
+ * four-int arrays and clears the internal dirty-rectangle
+ * list. Note that some of the regions returned may be null, or
+ * may have zero height or zero width, and do not need to be
+ * repainted.
+ */
+ public synchronized int[][] flush() {
+ if (numdirties == 0) return null;
+ int[][] ret = dirties;
+ for(int i=numdirties; i<ret.length; i++) ret[i] = null;
+ dirties = new int[dirties.length][];
+ numdirties = 0;
+ return ret;
+ }
+
+ /** included here so that it can be inlined */
+ private static final int min(int a, int b) {
+ if (a<b) return a;
+ else return b;
+ }
+
+ /** included here so that it can be inlined */
+ private static final int max(int a, int b) {
+ if (a>b) return a;
+ else return b;
+ }
+
+ /** included here so that it can be inlined */
+ private static final int min(int a, int b, int c) {
+ if (a<=b && a<=c) return a;
+ else if (b<=c && b<=a) return b;
+ else return c;
+ }
+
+ /** included here so that it can be inlined */
+ private static final int max(int a, int b, int c) {
+ if (a>=b && a>=c) return a;
+ else if (b>=c && b>=a) return b;
+ else return c;
+ }
+
+ /** included here so that it can be inlined */
+ private static final int bound(int a, int b, int c) {
+ if (a > b) return a;
+ if (c < b) return c;
+ return b;
+ }
+
+}
--- /dev/null
+package org.ibex.util;
+
+import java.io.File;
+import java.io.IOException;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.Field;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+
+/**
+ * BrowserLauncher is a class that provides one static method, openURL, which opens the default
+ * web browser for the current user of the system to the given URL. It may support other
+ * protocols depending on the system -- mailto, ftp, etc. -- but that has not been rigorously
+ * tested and is not guaranteed to work.
+ * <p>
+ * Yes, this is platform-specific code, and yes, it may rely on classes on certain platforms
+ * that are not part of the standard JDK. What we're trying to do, though, is to take something
+ * that's frequently desirable but inherently platform-specific -- opening a default browser --
+ * and allow programmers (you, for example) to do so without worrying about dropping into native
+ * code or doing anything else similarly evil.
+ * <p>
+ * Anyway, this code is completely in Java and will run on all JDK 1.1-compliant systems without
+ * modification or a need for additional libraries. All classes that are required on certain
+ * platforms to allow this to run are dynamically loaded at runtime via reflection and, if not
+ * found, will not cause this to do anything other than returning an error when opening the
+ * browser.
+ * <p>
+ * There are certain system requirements for this class, as it's running through Runtime.exec(),
+ * which is Java's way of making a native system call. Currently, this requires that a Macintosh
+ * have a Finder which supports the GURL event, which is true for Mac OS 8.0 and 8.1 systems that
+ * have the Internet Scripting AppleScript dictionary installed in the Scripting Additions folder
+ * in the Extensions folder (which is installed by default as far as I know under Mac OS 8.0 and
+ * 8.1), and for all Mac OS 8.5 and later systems. On Windows, it only runs under Win32 systems
+ * (Windows 95, 98, and NT 4.0, as well as later versions of all). On other systems, this drops
+ * back from the inherently platform-sensitive concept of a default browser and simply attempts
+ * to launch Netscape via a shell command.
+ * <p>
+ * This code is Copyright 1999-2001 by Eric Albert (ejalbert@cs.stanford.edu) and may be
+ * redistributed or modified in any form without restrictions as long as the portion of this
+ * comment from this paragraph through the end of the comment is not removed. The author
+ * requests that he be notified of any application, applet, or other binary that makes use of
+ * this code, but that's more out of curiosity than anything and is not required. This software
+ * includes no warranty. The author is not repsonsible for any loss of data or functionality
+ * or any adverse or unexpected effects of using this software.
+ * <p>
+ * Credits:
+ * <br>Steven Spencer, JavaWorld magazine (<a href="http://www.javaworld.com/javaworld/javatips/jw-javatip66.html">Java Tip 66</a>)
+ * <br>Thanks also to Ron B. Yeh, Eric Shapiro, Ben Engber, Paul Teitlebaum, Andrea Cantatore,
+ * Larry Barowski, Trevor Bedzek, Frank Miedrich, and Ron Rabakukk
+ *
+ * @author Eric Albert (<a href="mailto:ejalbert@cs.stanford.edu">ejalbert@cs.stanford.edu</a>)
+ * @version 1.4b1 (Released June 20, 2001)
+ */
+public class EjAlbertBrowserLauncher {
+
+ /**
+ * The Java virtual machine that we are running on. Actually, in most cases we only care
+ * about the operating system, but some operating systems require us to switch on the VM. */
+ private static int jvm;
+
+ /** The browser for the system */
+ private static Object browser;
+
+ /**
+ * Caches whether any classes, methods, and fields that are not part of the JDK and need to
+ * be dynamically loaded at runtime loaded successfully.
+ * <p>
+ * Note that if this is <code>false</code>, <code>openURL()</code> will always return an
+ * IOException.
+ */
+ private static boolean loadedWithoutErrors;
+
+ /** The com.apple.mrj.MRJFileUtils class */
+ private static Class mrjFileUtilsClass;
+
+ /** The com.apple.mrj.MRJOSType class */
+ private static Class mrjOSTypeClass;
+
+ /** The com.apple.MacOS.AEDesc class */
+ private static Class aeDescClass;
+
+ /** The <init>(int) method of com.apple.MacOS.AETarget */
+ private static Constructor aeTargetConstructor;
+
+ /** The <init>(int, int, int) method of com.apple.MacOS.AppleEvent */
+ private static Constructor appleEventConstructor;
+
+ /** The <init>(String) method of com.apple.MacOS.AEDesc */
+ private static Constructor aeDescConstructor;
+
+ /** The findFolder method of com.apple.mrj.MRJFileUtils */
+ private static Method findFolder;
+
+ /** The getFileCreator method of com.apple.mrj.MRJFileUtils */
+ private static Method getFileCreator;
+
+ /** The getFileType method of com.apple.mrj.MRJFileUtils */
+ private static Method getFileType;
+
+ /** The openURL method of com.apple.mrj.MRJFileUtils */
+ private static Method openURLm;
+
+ /** The makeOSType method of com.apple.MacOS.OSUtils */
+ private static Method makeOSType;
+
+ /** The putParameter method of com.apple.MacOS.AppleEvent */
+ private static Method putParameter;
+
+ /** The sendNoReply method of com.apple.MacOS.AppleEvent */
+ private static Method sendNoReply;
+
+ /** Actually an MRJOSType pointing to the System Folder on a Macintosh */
+ private static Object kSystemFolderType;
+
+ /** The keyDirectObject AppleEvent parameter type */
+ private static Integer keyDirectObject;
+
+ /** The kAutoGenerateReturnID AppleEvent code */
+ private static Integer kAutoGenerateReturnID;
+
+ /** The kAnyTransactionID AppleEvent code */
+ private static Integer kAnyTransactionID;
+
+ /** The linkage object required for JDirect 3 on Mac OS X. */
+ private static Object linkage;
+
+ /** The framework to reference on Mac OS X */
+ private static final String JDirect_MacOSX = "/System/Library/Frameworks/Carbon.framework/Frameworks/HIToolbox.framework/HIToolbox";
+
+ /** JVM constant for MRJ 2.0 */
+ private static final int MRJ_2_0 = 0;
+
+ /** JVM constant for MRJ 2.1 or later */
+ private static final int MRJ_2_1 = 1;
+
+ /** JVM constant for Java on Mac OS X 10.0 (MRJ 3.0) */
+ private static final int MRJ_3_0 = 3;
+
+ /** JVM constant for MRJ 3.1 */
+ private static final int MRJ_3_1 = 4;
+
+ /** JVM constant for any Windows NT JVM */
+ private static final int WINDOWS_NT = 5;
+
+ /** JVM constant for any Windows 9x JVM */
+ private static final int WINDOWS_9x = 6;
+
+ /** JVM constant for any other platform */
+ private static final int OTHER = -1;
+
+ /**
+ * The file type of the Finder on a Macintosh. Hardcoding "Finder" would keep non-U.S. English
+ * systems from working properly.
+ */
+ private static final String FINDER_TYPE = "FNDR";
+
+ /**
+ * The creator code of the Finder on a Macintosh, which is needed to send AppleEvents to the
+ * application.
+ */
+ private static final String FINDER_CREATOR = "MACS";
+
+ /** The name for the AppleEvent type corresponding to a GetURL event. */
+ private static final String GURL_EVENT = "GURL";
+
+ /**
+ * The first parameter that needs to be passed into Runtime.exec() to open the default web
+ * browser on Windows.
+ */
+ private static final String FIRST_WINDOWS_PARAMETER = "/c";
+
+ /** The second parameter for Runtime.exec() on Windows. */
+ private static final String SECOND_WINDOWS_PARAMETER = "start";
+
+ /**
+ * The third parameter for Runtime.exec() on Windows. This is a "title"
+ * parameter that the command line expects. Setting this parameter allows
+ * URLs containing spaces to work.
+ */
+ private static final String THIRD_WINDOWS_PARAMETER = "\"\"";
+
+ /**
+ * The shell parameters for Netscape that opens a given URL in an already-open copy of Netscape
+ * on many command-line systems.
+ */
+ private static final String NETSCAPE_REMOTE_PARAMETER = "-remote";
+ private static final String NETSCAPE_OPEN_PARAMETER_START = "'openURL(";
+ private static final String NETSCAPE_OPEN_PARAMETER_END = ")'";
+
+ /**
+ * The message from any exception thrown throughout the initialization process.
+ */
+ private static String errorMessage;
+
+ /**
+ * An initialization block that determines the operating system and loads the necessary
+ * runtime data.
+ */
+ static {
+ loadedWithoutErrors = true;
+ String osName = System.getProperty("os.name");
+ if (osName.startsWith("Mac OS")) {
+ String mrjVersion = System.getProperty("mrj.version");
+ String majorMRJVersion = mrjVersion.substring(0, 3);
+ try {
+ double version = Double.valueOf(majorMRJVersion).doubleValue();
+ if (version == 2) {
+ jvm = MRJ_2_0;
+ } else if (version >= 2.1 && version < 3) {
+ // Assume that all 2.x versions of MRJ work the same. MRJ 2.1 actually
+ // works via Runtime.exec() and 2.2 supports that but has an openURL() method
+ // as well that we currently ignore.
+ jvm = MRJ_2_1;
+ } else if (version == 3.0) {
+ jvm = MRJ_3_0;
+ } else if (version >= 3.1) {
+ // Assume that all 3.1 and later versions of MRJ work the same.
+ jvm = MRJ_3_1;
+ } else {
+ loadedWithoutErrors = false;
+ errorMessage = "Unsupported MRJ version: " + version;
+ }
+ } catch (NumberFormatException nfe) {
+ loadedWithoutErrors = false;
+ errorMessage = "Invalid MRJ version: " + mrjVersion;
+ }
+ } else if (osName.startsWith("Windows")) {
+ if (osName.indexOf("9") != -1) {
+ jvm = WINDOWS_9x;
+ } else {
+ jvm = WINDOWS_NT;
+ }
+ } else {
+ jvm = OTHER;
+ }
+
+ if (loadedWithoutErrors) { // if we haven't hit any errors yet
+ loadedWithoutErrors = loadClasses();
+ }
+ }
+
+ /**
+ * This class should be never be instantiated; this just ensures so.
+ */
+ private EjAlbertBrowserLauncher() { }
+
+ /**
+ * Called by a static initializer to load any classes, fields, and methods required at runtime
+ * to locate the user's web browser.
+ * @return <code>true</code> if all intialization succeeded
+ * <code>false</code> if any portion of the initialization failed
+ */
+ private static boolean loadClasses() {
+ switch (jvm) {
+ case MRJ_2_0:
+ try {
+ Class aeTargetClass = Class.forName("com.apple.MacOS.AETarget");
+ Class osUtilsClass = Class.forName("com.apple.MacOS.OSUtils");
+ Class appleEventClass = Class.forName("com.apple.MacOS.AppleEvent");
+ Class aeClass = Class.forName("com.apple.MacOS.ae");
+ aeDescClass = Class.forName("com.apple.MacOS.AEDesc");
+
+ aeTargetConstructor = aeTargetClass.getDeclaredConstructor(new Class [] { int.class });
+ appleEventConstructor = appleEventClass.getDeclaredConstructor(new Class[] { int.class, int.class, aeTargetClass, int.class, int.class });
+ aeDescConstructor = aeDescClass.getDeclaredConstructor(new Class[] { String.class });
+
+ makeOSType = osUtilsClass.getDeclaredMethod("makeOSType", new Class [] { String.class });
+ putParameter = appleEventClass.getDeclaredMethod("putParameter", new Class[] { int.class, aeDescClass });
+ sendNoReply = appleEventClass.getDeclaredMethod("sendNoReply", new Class[] { });
+
+ Field keyDirectObjectField = aeClass.getDeclaredField("keyDirectObject");
+ keyDirectObject = (Integer) keyDirectObjectField.get(null);
+ Field autoGenerateReturnIDField = appleEventClass.getDeclaredField("kAutoGenerateReturnID");
+ kAutoGenerateReturnID = (Integer) autoGenerateReturnIDField.get(null);
+ Field anyTransactionIDField = appleEventClass.getDeclaredField("kAnyTransactionID");
+ kAnyTransactionID = (Integer) anyTransactionIDField.get(null);
+ } catch (ClassNotFoundException cnfe) {
+ errorMessage = cnfe.getMessage();
+ return false;
+ } catch (NoSuchMethodException nsme) {
+ errorMessage = nsme.getMessage();
+ return false;
+ } catch (NoSuchFieldException nsfe) {
+ errorMessage = nsfe.getMessage();
+ return false;
+ } catch (IllegalAccessException iae) {
+ errorMessage = iae.getMessage();
+ return false;
+ }
+ break;
+ case MRJ_2_1:
+ try {
+ mrjFileUtilsClass = Class.forName("com.apple.mrj.MRJFileUtils");
+ mrjOSTypeClass = Class.forName("com.apple.mrj.MRJOSType");
+ Field systemFolderField = mrjFileUtilsClass.getDeclaredField("kSystemFolderType");
+ kSystemFolderType = systemFolderField.get(null);
+ findFolder = mrjFileUtilsClass.getDeclaredMethod("findFolder", new Class[] { mrjOSTypeClass });
+ getFileCreator = mrjFileUtilsClass.getDeclaredMethod("getFileCreator", new Class[] { File.class });
+ getFileType = mrjFileUtilsClass.getDeclaredMethod("getFileType", new Class[] { File.class });
+ } catch (ClassNotFoundException cnfe) {
+ errorMessage = cnfe.getMessage();
+ return false;
+ } catch (NoSuchFieldException nsfe) {
+ errorMessage = nsfe.getMessage();
+ return false;
+ } catch (NoSuchMethodException nsme) {
+ errorMessage = nsme.getMessage();
+ return false;
+ } catch (SecurityException se) {
+ errorMessage = se.getMessage();
+ return false;
+ } catch (IllegalAccessException iae) {
+ errorMessage = iae.getMessage();
+ return false;
+ }
+ break;
+ case MRJ_3_0:
+ try {
+ Class linker = Class.forName("com.apple.mrj.jdirect.Linker");
+ Constructor constructor = linker.getConstructor(new Class[]{ Class.class });
+ linkage = constructor.newInstance(new Object[] { EjAlbertBrowserLauncher.class });
+ } catch (ClassNotFoundException cnfe) {
+ errorMessage = cnfe.getMessage();
+ return false;
+ } catch (NoSuchMethodException nsme) {
+ errorMessage = nsme.getMessage();
+ return false;
+ } catch (InvocationTargetException ite) {
+ errorMessage = ite.getMessage();
+ return false;
+ } catch (InstantiationException ie) {
+ errorMessage = ie.getMessage();
+ return false;
+ } catch (IllegalAccessException iae) {
+ errorMessage = iae.getMessage();
+ return false;
+ }
+ break;
+ case MRJ_3_1:
+ try {
+ mrjFileUtilsClass = Class.forName("com.apple.mrj.MRJFileUtils");
+ openURLm = mrjFileUtilsClass.getDeclaredMethod("openURL", new Class[] { String.class });
+ } catch (ClassNotFoundException cnfe) {
+ errorMessage = cnfe.getMessage();
+ return false;
+ } catch (NoSuchMethodException nsme) {
+ errorMessage = nsme.getMessage();
+ return false;
+ }
+ break;
+ default:
+ break;
+ }
+ return true;
+ }
+
+ /**
+ * Attempts to locate the default web browser on the local system. Caches results so it
+ * only locates the browser once for each use of this class per JVM instance.
+ * @return The browser for the system. Note that this may not be what you would consider
+ * to be a standard web browser; instead, it's the application that gets called to
+ * open the default web browser. In some cases, this will be a non-String object
+ * that provides the means of calling the default browser.
+ */
+ private static Object locateBrowser() {
+ if (browser != null) {
+ return browser;
+ }
+ switch (jvm) {
+ case MRJ_2_0:
+ try {
+ Integer finderCreatorCode = (Integer) makeOSType.invoke(null, new Object[] { FINDER_CREATOR });
+ Object aeTarget = aeTargetConstructor.newInstance(new Object[] { finderCreatorCode });
+ Integer gurlType = (Integer) makeOSType.invoke(null, new Object[] { GURL_EVENT });
+ Object appleEvent = appleEventConstructor.newInstance(new Object[] { gurlType, gurlType, aeTarget, kAutoGenerateReturnID, kAnyTransactionID });
+ // Don't set browser = appleEvent because then the next time we call
+ // locateBrowser(), we'll get the same AppleEvent, to which we'll already have
+ // added the relevant parameter. Instead, regenerate the AppleEvent every time.
+ // There's probably a way to do this better; if any has any ideas, please let
+ // me know.
+ return appleEvent;
+ } catch (IllegalAccessException iae) {
+ browser = null;
+ errorMessage = iae.getMessage();
+ return browser;
+ } catch (InstantiationException ie) {
+ browser = null;
+ errorMessage = ie.getMessage();
+ return browser;
+ } catch (InvocationTargetException ite) {
+ browser = null;
+ errorMessage = ite.getMessage();
+ return browser;
+ }
+ case MRJ_2_1:
+ File systemFolder;
+ try {
+ systemFolder = (File) findFolder.invoke(null, new Object[] { kSystemFolderType });
+ } catch (IllegalArgumentException iare) {
+ browser = null;
+ errorMessage = iare.getMessage();
+ return browser;
+ } catch (IllegalAccessException iae) {
+ browser = null;
+ errorMessage = iae.getMessage();
+ return browser;
+ } catch (InvocationTargetException ite) {
+ browser = null;
+ errorMessage = ite.getTargetException().getClass() + ": " + ite.getTargetException().getMessage();
+ return browser;
+ }
+ String[] systemFolderFiles = systemFolder.list();
+ // Avoid a FilenameFilter because that can't be stopped mid-list
+ for(int i = 0; i < systemFolderFiles.length; i++) {
+ try {
+ File file = new File(systemFolder, systemFolderFiles[i]);
+ if (!file.isFile()) {
+ continue;
+ }
+ // We're looking for a file with a creator code of 'MACS' and
+ // a type of 'FNDR'. Only requiring the type results in non-Finder
+ // applications being picked up on certain Mac OS 9 systems,
+ // especially German ones, and sending a GURL event to those
+ // applications results in a logout under Multiple Users.
+ Object fileType = getFileType.invoke(null, new Object[] { file });
+ if (FINDER_TYPE.equals(fileType.toString())) {
+ Object fileCreator = getFileCreator.invoke(null, new Object[] { file });
+ if (FINDER_CREATOR.equals(fileCreator.toString())) {
+ browser = file.toString(); // Actually the Finder, but that's OK
+ return browser;
+ }
+ }
+ } catch (IllegalArgumentException iare) {
+ browser = browser;
+ errorMessage = iare.getMessage();
+ return null;
+ } catch (IllegalAccessException iae) {
+ browser = null;
+ errorMessage = iae.getMessage();
+ return browser;
+ } catch (InvocationTargetException ite) {
+ browser = null;
+ errorMessage = ite.getTargetException().getClass() + ": " + ite.getTargetException().getMessage();
+ return browser;
+ }
+ }
+ browser = null;
+ break;
+ case MRJ_3_0:
+ case MRJ_3_1:
+ browser = ""; // Return something non-null
+ break;
+ case WINDOWS_NT:
+ browser = "cmd.exe";
+ break;
+ case WINDOWS_9x:
+ browser = "command.com";
+ break;
+ case OTHER:
+ default:
+ browser = "netscape";
+ break;
+ }
+ return browser;
+ }
+
+ /**
+ * Attempts to open the default web browser to the given URL.
+ * @param url The URL to open
+ * @throws IOException If the web browser could not be located or does not run
+ */
+ public static void openURL(String url) throws IOException {
+ if (!loadedWithoutErrors) {
+ throw new IOException("Exception in finding browser: " + errorMessage);
+ }
+ Object browser = locateBrowser();
+ if (browser == null) {
+ throw new IOException("Unable to locate browser: " + errorMessage);
+ }
+
+ switch (jvm) {
+ case MRJ_2_0:
+ Object aeDesc = null;
+ try {
+ aeDesc = aeDescConstructor.newInstance(new Object[] { url });
+ putParameter.invoke(browser, new Object[] { keyDirectObject, aeDesc });
+ sendNoReply.invoke(browser, new Object[] { });
+ } catch (InvocationTargetException ite) {
+ throw new IOException("InvocationTargetException while creating AEDesc: " + ite.getMessage());
+ } catch (IllegalAccessException iae) {
+ throw new IOException("IllegalAccessException while building AppleEvent: " + iae.getMessage());
+ } catch (InstantiationException ie) {
+ throw new IOException("InstantiationException while creating AEDesc: " + ie.getMessage());
+ } finally {
+ aeDesc = null; // Encourage it to get disposed if it was created
+ browser = null; // Ditto
+ }
+ break;
+ case MRJ_2_1:
+ Runtime.getRuntime().exec(new String[] { (String) browser, url } );
+ break;
+ case MRJ_3_0:
+ int[] instance = new int[1];
+ int result = ICStart(instance, 0);
+ if (result == 0) {
+ int[] selectionStart = new int[] { 0 };
+ byte[] urlBytes = url.getBytes();
+ int[] selectionEnd = new int[] { urlBytes.length };
+ result = ICLaunchURL(instance[0], new byte[] { 0 }, urlBytes,
+ urlBytes.length, selectionStart,
+ selectionEnd);
+ if (result == 0) {
+ // Ignore the return value; the URL was launched successfully
+ // regardless of what happens here.
+ ICStop(instance);
+ } else {
+ throw new IOException("Unable to launch URL: " + result);
+ }
+ } else {
+ throw new IOException("Unable to create an Internet Config instance: " + result);
+ }
+ break;
+ case MRJ_3_1:
+ try {
+ openURLm.invoke(null, new Object[] { url });
+ } catch (InvocationTargetException ite) {
+ throw new IOException("InvocationTargetException while calling openURL: " + ite.getMessage());
+ } catch (IllegalAccessException iae) {
+ throw new IOException("IllegalAccessException while calling openURL: " + iae.getMessage());
+ }
+ break;
+ case WINDOWS_NT:
+ case WINDOWS_9x:
+ // Add quotes around the URL to allow ampersands and other special
+ // characters to work.
+ Process process = Runtime.getRuntime().exec(new String[] { (String) browser,
+ FIRST_WINDOWS_PARAMETER,
+ SECOND_WINDOWS_PARAMETER,
+ THIRD_WINDOWS_PARAMETER,
+ '"' + url + '"' });
+ // This avoids a memory leak on some versions of Java on Windows.
+ // That's hinted at in <http://developer.java.sun.com/developer/qow/archive/68/>.
+ try {
+ process.waitFor();
+ process.exitValue();
+ } catch (InterruptedException ie) {
+ throw new IOException("InterruptedException while launching browser: " + ie.getMessage());
+ }
+ break;
+ case OTHER:
+ // Assume that we're on Unix and that Netscape is installed
+
+ // First, attempt to open the URL in a currently running session of Netscape
+ process = Runtime.getRuntime().exec(new String[] { (String) browser,
+ NETSCAPE_REMOTE_PARAMETER,
+ NETSCAPE_OPEN_PARAMETER_START +
+ url +
+ NETSCAPE_OPEN_PARAMETER_END });
+ try {
+ int exitCode = process.waitFor();
+ if (exitCode != 0) { // if Netscape was not open
+ Runtime.getRuntime().exec(new String[] { (String) browser, url });
+ }
+ } catch (InterruptedException ie) {
+ throw new IOException("InterruptedException while launching browser: " + ie.getMessage());
+ }
+ break;
+ default:
+ // This should never occur, but if it does, we'll try the simplest thing possible
+ Runtime.getRuntime().exec(new String[] { (String) browser, url });
+ break;
+ }
+ }
+
+ /**
+ * Methods required for Mac OS X. The presence of native methods does not cause
+ * any problems on other platforms.
+ */
+ /*
+ private native static int ICStart(int[] instance, int signature);
+ private native static int ICStop(int[] instance);
+ private native static int ICLaunchURL(int instance, byte[] hint, byte[] data, int len,
+ int[] selectionStart, int[] selectionEnd);
+ */
+ private static int ICStart(int[] instance, int signature) { return 0; }
+ private static int ICStop(int[] instance) { return 0; }
+ private static int ICLaunchURL(int instance, byte[] hint, byte[] data, int len,
+ int[] selectionStart, int[] selectionEnd) { return 0; }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+import java.util.*;
+import java.io.*;
+
+/** provides commands to urlencode and urldecode strings, making sure
+ * to escape sequences which have special meanings in filenames */
+public class FileNameEncoder {
+
+ private static final char[] hex =
+ new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
+
+ public static String encode(String s) {
+ StringBuffer sb = new StringBuffer();
+ try {
+ byte[] b = s.getBytes("UTF-8");
+ for(int i=0; i<b.length; i++) {
+ char c = (char)(b[i] & 0xff);
+ if (c == File.separatorChar || c < 32 || c > 126 || c == '%' || (i == 0 && c == '.'))
+ sb.append("%" + hex[(b[i] & 0xf0) >> 8] + hex[b[i] & 0xf]);
+ else sb.append(c);
+ }
+ return sb.toString();
+ } catch (UnsupportedEncodingException uee) {
+ throw new Error("this should never happen; Java spec mandates UTF-8 support");
+ }
+ }
+
+ public static String decode(String s) {
+ StringBuffer sb = new StringBuffer();
+ byte[] b = new byte[s.length() * 2];
+ int bytes = 0;
+ for(int i=0; i<s.length(); i++) {
+ char c = s.charAt(i);
+ if (c == '%') b[bytes++] = (byte)Integer.parseInt(("" + s.charAt(++i) + s.charAt(++i)), 16);
+ else b[bytes++] = (byte)c;
+ }
+ try {
+ return new String(b, 0, bytes, "UTF-8");
+ } catch (UnsupportedEncodingException uee) {
+ throw new Error("this should never happen; Java spec mandates UTF-8 support");
+ }
+ }
+}
--- /dev/null
+package org.ibex.util;
+
+import org.ibex.js.*;
+
+public abstract class Grammar extends JS {
+
+ public JS action = null;
+
+ // means we call()ed a Grammar that hasn't been bound to a scope yet
+ public Object call(Object a0, Object a1, Object a2, Object[] rest, int nargs) throws JSExn {
+ throw new Error("this should never happen");
+ }
+
+ private static Object NULL = new Object();
+
+ public abstract int match(String s, int start, Hash v, JSScope scope) throws JSExn;
+ public int matchAndWrite(final String s, final int start, Hash v, JSScope scope, String key) throws JSExn {
+ final Hash v2 = new Hash();
+ final int ret = match(s, start, v2, scope);
+ Object result = ret == -1 ? NULL : action == null ?
+ s.substring(start, ret) :
+ JS.cloneWithNewParentScope(action, new JSScope(scope) {
+ public Object get(Object key) throws JSExn {
+ Object val = v2.get(key);
+ if (val == NULL) return null;
+ if (val != null) return val;
+ if (key.equals("whole")) return s.substring(start, ret);
+ return super.get(key);
+ }
+ }).call(null, null, null, null, 0);
+ if (key != null) {
+ Object old = v.get(key);
+ if (old == null || old == NULL) { }
+ else if (old instanceof JSArray) { if (result != NULL) { ((JSArray)old).addElement(result); result = old; } }
+ else if (result != NULL) { JSArray j = new JSArray(); j.addElement(old); j.addElement(result); result = j; }
+ v.put(key, result);
+ }
+ return ret;
+ }
+
+ public static class Alternative extends Grammar {
+ private Grammar r1, r2;
+ public Alternative(Grammar r1, Grammar r2) { this.r1 = r1; this.r2 = r2; }
+ public int match(String s, int start, Hash v, JSScope r) throws JSExn {
+ int s1 = r1.match(s, start, v, r);
+ if (s1 != -1) return s1;
+ int s2 = r2.match(s, start, v, r);
+ if (s2 != -1) return s2;
+ return -1;
+ }
+ }
+
+ public static class Juxtaposition extends Grammar {
+ private Grammar r1, r2;
+ public Juxtaposition(Grammar r1, Grammar r2) { this.r1 = r1; this.r2 = r2; }
+ public int match(String s, int start, Hash v, JSScope r) throws JSExn {
+ int s1 = r1.match(s, start, v, r);
+ if (s1 == -1) return -1;
+ int s2 = r2.match(s, s1, v, r);
+ if (s2 == -1) return -1;
+ return s2;
+ }
+ }
+
+ public static class Repetition extends Grammar {
+ private Grammar r1;
+ private int min, max;
+ public Repetition(Grammar r1, int min, int max) { this.r1 = r1; this.min = min; this.max = max; }
+ public int match(String s, int start, Hash v, JSScope r) throws JSExn {
+ int i;
+ for(i=0; i<max; i++) {
+ start = r1.match(s, start, v, r);
+ if (start == -1) return -1;
+ }
+ if (i < min) return -1;
+ return start;
+ }
+ }
+
+ public static class Literal extends Grammar {
+ String str;
+ public Literal(String str) { this.str = str; }
+ public int match(String s, int start, Hash v, JSScope r) {
+ if (!s.regionMatches(start, str, 0, str.length())) return -1;
+ return start + str.length();
+ }
+ }
+
+ public static class Range extends Grammar {
+ char min, max;
+ public Range(char min, char max) { this.min = min; this.max = max; }
+ public int match(String s, int start, Hash v, JSScope r) throws JSExn {
+ if (!(s.charAt(start) >= min && s.charAt(start) <= max)) return -1;
+ return start + 1;
+ }
+ }
+
+ public static class Reference extends Grammar {
+ String key;
+ public Reference(String key) { this.key = key; }
+ public int match(String s, int start, Hash v, JSScope scope) throws JSExn {
+ return ((Grammar)scope.get(key)).matchAndWrite(s, start, v, scope, key);
+ }
+ }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+import java.util.*;
+
+/** Implementation of an unsynchronized hash table, with one or two
+ * keys, using Radke's quadradic residue linear probing instead of
+ * buckets to minimize object count (less allocations, faster GC).
+ * See C. Radke, Communications of the ACM, 1970, 103-105
+ *
+ * Not threadsafe.
+ */
+public class Hash {
+ /** this object is inserted as key in a slot when the
+ * corresponding value is removed -- this ensures that the
+ * probing sequence for any given key remains the same even if
+ * other keys are removed.
+ */
+ private static Object placeholder = new Object();
+
+ /** the number of entries with at least one non-null key */
+ private int usedslots = 0;
+
+ /** the number of entries with non-null values */
+ protected int size = 0;
+
+ /** when num_slots < loadFactor * size, rehash into a bigger table */
+ private final int loadFactor;
+
+ /** primary keys */
+ private Object[] keys1 = null;
+
+ /** secondary keys; null if no secondary key has ever been added */
+ private Object[] keys2 = null;
+
+ /** the values for the table */
+ private Object[] vals = null;
+
+ /** the number of entries with a non-null value */
+ public int size() { return size; }
+
+ /** empties the table */
+ public void clear() {
+ size = 0;
+ usedslots = 0;
+ for(int i=0; i<vals.length; i++) {
+ vals[i] = null;
+ keys1[i] = null;
+ if (keys2 != null) keys2[i] = null;
+ }
+ }
+
+ /** returns all the primary keys in the table */
+ public Enumeration keys() { return new HashEnum(); }
+
+ public Hash() { this(25, 3); }
+ public Hash(int initialcapacity, int loadFactor) {
+ // using a pseudoprime in the form 4x+3 ensures full coverage
+ initialcapacity = initialcapacity / 4;
+ initialcapacity = 4 * initialcapacity + 3;
+ keys1 = new Object[initialcapacity];
+ vals = new Object[initialcapacity];
+ this.loadFactor = loadFactor;
+ }
+
+ public void remove(Object k1) { remove(k1, null); }
+ public void remove(Object k1, Object k2) { put_(k1, k2, null); }
+
+ private void rehash() {
+ Object[] oldkeys1 = keys1;
+ Object[] oldkeys2 = keys2;
+ Object[] oldvals = vals;
+ keys1 = new Object[oldvals.length * 2];
+ keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
+ vals = new Object[oldvals.length * 2];
+ size = 0;
+ usedslots = 0;
+ for(int i=0; i<oldvals.length; i++)
+ if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
+ put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
+ }
+
+ public Object get(Object k1) { return get(k1, null); }
+ public Object get(Object k1, Object k2) {
+ if (k2 != null && keys2 == null) return null;
+ int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
+ int dest = Math.abs(hash) % vals.length;
+ int odest = dest;
+ int tries = 1;
+ boolean plus = true;
+ while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
+ Object hk1 = keys1[dest];
+ Object hk2 = keys2 == null ? null : keys2[dest];
+ if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
+ (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
+ return vals[dest];
+ }
+ dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
+ if (plus) tries++;
+ plus = !plus;
+ }
+ return null;
+ }
+
+ public void put(Object k1, Object v) { put(k1, null, v); }
+ public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
+ private void put_(Object k1, Object k2, Object v) {
+ if (usedslots * loadFactor > vals.length) rehash();
+ int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
+ int dest = Math.abs(hash) % vals.length;
+ int odest = dest;
+ boolean plus = true;
+ int tries = 1;
+ while (true) {
+ Object hk1 = keys1[dest];
+ Object hk2 = keys2 == null ? null : keys2[dest];
+ if (hk1 == null && hk2 == null) { // empty slot
+ if (v == null) return;
+ size++;
+ usedslots++;
+ break;
+ }
+
+ if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) && // replacing former entry
+ (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
+
+ // we don't actually remove things from the table; rather, we insert a placeholder
+ if (v == null) {
+ k1 = placeholder;
+ k2 = null;
+ size--;
+ }
+ break;
+ }
+
+ dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
+ if (plus) tries++;
+ plus = !plus;
+ }
+
+ keys1[dest] = k1;
+ if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
+ if (keys2 != null) keys2[dest] = k2;
+ vals[dest] = v;
+ }
+
+ private class HashEnum implements java.util.Enumeration {
+ private int iterator = 0;
+ private int found = 0;
+
+ public boolean hasMoreElements() {
+ return found < usedslots;
+ }
+
+ public Object nextElement() {
+ if (!hasMoreElements()) throw new java.util.NoSuchElementException();
+
+ Object o = null;
+ while (o == null) o = keys1[iterator++];
+ if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");
+ found++;
+
+ return o;
+ }
+ }
+}
+
+
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+import java.io.*;
+
+public class InputStreamToByteArray {
+
+ /** scratch space for isToByteArray() */
+ private static byte[] workspace = new byte[16 * 1024];
+
+ /** Trivial method to completely read an InputStream */
+ public static synchronized byte[] convert(InputStream is) throws IOException {
+ int pos = 0;
+ while (true) {
+ int numread = is.read(workspace, pos, workspace.length - pos);
+ if (numread == -1) break;
+ else if (pos + numread < workspace.length) pos += numread;
+ else {
+ pos += numread;
+ byte[] temp = new byte[workspace.length * 2];
+ System.arraycopy(workspace, 0, temp, 0, workspace.length);
+ workspace = temp;
+ }
+ }
+ byte[] ret = new byte[pos];
+ System.arraycopy(workspace, 0, ret, 0, pos);
+ return ret;
+ }
+
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+import java.io.*;
+
+/** a generic interface for things that "know" their length */
+public interface KnownLength {
+
+ public abstract int getLength();
+
+ public static class KnownLengthInputStream extends FilterInputStream implements KnownLength {
+ int length;
+ public int getLength() { return length; }
+ public KnownLengthInputStream(java.io.InputStream parent, int length) {
+ super(parent);
+ this.length = length;
+ }
+ }
+
+}
--- /dev/null
+package org.ibex.util;
+import java.io.*;
+
+public class LineReader {
+
+ private int MAXBUF = 1024 * 16;
+ char[] buf = new char[MAXBUF];
+ int buflen = 0;
+ Reader r;
+ Vec pushback = new Vec();
+
+ public LineReader(Reader r) { this.r = r; }
+
+ public void pushback(String s) { pushback.push(s); }
+
+ public String readLine() throws IOException {
+ while(true) {
+ if (pushback.size() > 0) return (String)pushback.pop();
+ for(int i=0; i<buflen; i++) {
+ if (buf[i] == '\n') {
+ String ret;
+ if (buf[i-1] == '\r') ret = new String(buf, 0, i-1);
+ else ret = new String(buf, 0, i);
+ System.arraycopy(buf, i+1, buf, 0, buflen - (i+1));
+ buflen -= i+1;
+ return ret;
+ }
+ }
+ if (buflen == MAXBUF) {
+ char[] buf2 = new char[MAXBUF*2];
+ System.arraycopy(buf, 0, buf2, 0, buflen);
+ buf = buf2;
+ MAXBUF *= 2;
+ }
+ int numread = r.read(buf, buflen, MAXBUF - buflen);
+ if (numread == -1) {
+ if (buflen == 0) return null;
+ String ret = new String(buf, 0, buflen);
+ buflen = 0;
+ return ret;
+ } else {
+ buflen += numread;
+ }
+ }
+ }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+import org.ibex.js.*;
+import java.io.*;
+import java.util.*;
+import java.net.*;
+
+/** easy to use logger */
+public class Log {
+
+ public static boolean on = System.getProperty("ibex.log.on", "true").equals("true");
+ public static boolean color = System.getProperty("ibex.log.color", "true").equals("true");
+ public static boolean verbose = System.getProperty("ibex.log.verbose", "false").equals("true");
+ public static boolean logDates = System.getProperty("ibex.log.dates", "false").equals("true");
+ public static boolean notes = System.getProperty("ibex.log.notes.on", "true").equals("true");
+ public static int maximumNoteLength = Integer.parseInt(System.getProperty("ibex.log.notes.maximumLength", (1024 * 32)+""));
+ public static boolean rpc = false;
+ public static Date lastDate = null;
+
+ public static PrintStream logstream = System.err;
+
+ public static void flush() { logstream.flush(); }
+ public static void email(String address) { throw new Error("FIXME not supported"); }
+ public static void file(String filename) throws IOException {
+ // FIXME security
+ logstream = new PrintStream(new FileOutputStream(filename));
+ }
+ public static void tcp(String host, int port) throws IOException {
+ // FIXME security
+ logstream = new PrintStream(new Socket(InetAddress.getByName(host), port).getOutputStream());
+ }
+
+ private static Hashtable threadAnnotations = new Hashtable();
+ public static void setThreadAnnotation(String s) { threadAnnotations.put(Thread.currentThread(), s); }
+
+ /**
+ * Notes can be used to attach log messages to the current thread
+ * if you're not sure you want them in the log just yet.
+ * Originally designed for retroactively logging socket-level
+ * conversations only if an error is encountered
+ */
+ public static void note(String s) {
+ if (!notes) return;
+ StringBuffer notebuf = notebuf();
+ notebuf.append(s);
+ if (notebuf.length() > maximumNoteLength) {
+ notebuf.reverse();
+ notebuf.setLength(maximumNoteLength * 3 / 4);
+ notebuf.reverse();
+ }
+ }
+ public static void clearnotes() { if (!notes) return; notebuf().setLength(0); }
+ private static Hashtable notebufs = new Hashtable();
+ private static StringBuffer notebuf() {
+ StringBuffer ret = (StringBuffer)notebufs.get(Thread.currentThread());
+ if (ret == null) {
+ ret = new StringBuffer(16 * 1024);
+ notebufs.put(Thread.currentThread(), ret);
+ }
+ return ret;
+ }
+
+ /** true iff nothing has yet been logged */
+ public static boolean firstMessage = true;
+
+ /** message can be a String or a Throwable */
+ public static synchronized void echo(Object o, Object message) { log(o, message, ECHO); }
+ public static synchronized void diag(Object o, Object message) { log(o, message, DIAGNOSTIC); }
+ public static synchronized void debug(Object o, Object message) { log(o, message, DEBUG); }
+ public static synchronized void info(Object o, Object message) { log(o, message, INFO); }
+ public static synchronized void warn(Object o, Object message) { log(o, message, WARN); }
+ public static synchronized void error(Object o, Object message) { log(o, message, ERROR); }
+
+ // these two logging levels serve ONLY to change the color; semantically they are the same as DEBUG
+ private static final int DIAGNOSTIC = -2;
+ private static final int ECHO = -1;
+
+ // the usual log4j levels, minus FAIL (we just throw an Error in that case)
+ public static final int DEBUG = 0;
+ public static final int INFO = 1;
+ public static final int WARN = 2;
+ public static final int ERROR = 3;
+ public static final int SILENT = Integer.MAX_VALUE;
+ public static int level = INFO;
+
+ private static final int BLUE = 34;
+ private static final int GREEN = 32;
+ private static final int CYAN = 36;
+ private static final int RED = 31;
+ private static final int PURPLE = 35;
+ private static final int BROWN = 33;
+ private static final int GRAY = 37;
+
+ private static String colorize(int color, boolean bright, String s) {
+ if (!Log.color) return s;
+ return
+ "\033[40;" + (bright?"1;":"") + color + "m" +
+ s +
+ "\033[0m";
+ }
+
+ private static String lastClassName = null;
+ private static synchronized void log(Object o, Object message, int level) {
+ if (level < Log.level) return;
+ if (firstMessage && !logDates) {
+ firstMessage = false;
+ logstream.println(colorize(GREEN, false, "==========================================================================="));
+
+ // FIXME later: causes problems with method pruning
+ //diag(Log.class, "Logging enabled at " + new java.util.Date());
+
+ if (color) diag(Log.class, "logging messages in " +
+ colorize(BLUE, true, "c") +
+ colorize(RED, true, "o") +
+ colorize(CYAN, true, "l") +
+ colorize(GREEN, true, "o") +
+ colorize(PURPLE, true, "r"));
+ }
+
+ String classname;
+ if (o instanceof Class) {
+ classname = ((Class)o).getName();
+ if (classname.indexOf('.') != -1) classname = classname.substring(classname.lastIndexOf('.') + 1);
+ }
+ else if (o instanceof String) classname = (String)o;
+ else classname = o.getClass().getName();
+
+ if (classname.equals(lastClassName)) classname = "";
+ else lastClassName = classname;
+
+ if (classname.length() > (logDates ? 14 : 20)) classname = classname.substring(0, (logDates ? 14 : 20));
+ while (classname.length() < (logDates ? 14 : 20)) classname = " " + classname;
+ classname = classname + (classname.trim().length() == 0 ? " " : ": ");
+ classname = colorize(GRAY, true, classname);
+ classname = classname.replace('$', '.');
+
+ if (logDates) {
+ Date d = new Date();
+ if (lastDate == null || d.getYear() != lastDate.getYear() || d.getMonth() != lastDate.getMonth() || d.getDay() != lastDate.getDay()) {
+ String now = new java.text.SimpleDateFormat("EEE dd MMM yyyy").format(d);
+ logstream.println();
+ logstream.println(colorize(GRAY, false, "=== " + now + " =========================================================="));
+ }
+ java.text.DateFormat df = new java.text.SimpleDateFormat("[EEE HH:mm:ss] ");
+ classname = df.format(d) + classname;
+ lastDate = d;
+ }
+
+ String annot = (String)threadAnnotations.get(Thread.currentThread());
+ if (annot != null) classname += annot;
+
+ if (message instanceof Throwable) {
+ if (level < ERROR) level = WARN;
+ ByteArrayOutputStream baos = new ByteArrayOutputStream();
+ ((Throwable)message).printStackTrace(new PrintStream(baos));
+ if (notes && notebuf().length() > 0) {
+ PrintWriter pw = new PrintWriter(baos);
+ pw.println();
+ pw.println("Thread notes:");
+ pw.println(notebuf().toString());
+ clearnotes();
+ pw.flush();
+ }
+ byte[] b = baos.toByteArray();
+ BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(b)));
+ String s = null;
+ try {
+ String m = "";
+ while((s = br.readLine()) != null) m += s + "\n";
+ if (m.length() > 0) log(o, m.substring(0, m.length() - 1), level);
+ } catch (IOException e) {
+ // FEATURE: use org.ibex.io.Stream's here
+ logstream.println(colorize(RED, true, "Logger: exception thrown by ByteArrayInputStream; this should not happen"));
+ }
+ lastClassName = "";
+ return;
+ }
+
+ String str = message.toString();
+ if (str.indexOf('\n') != -1) lastClassName = "";
+ while(str.indexOf('\t') != -1)
+ str = str.substring(0, str.indexOf('\t')) + " " + str.substring(str.indexOf('\t') + 1);
+
+ classname = colorize(GRAY, false, classname);
+ int levelcolor = GRAY;
+ boolean bright = true;
+ switch (level) {
+ case DIAGNOSTIC: levelcolor = GREEN; bright = false; break;
+ case ECHO: levelcolor = BLUE; bright = true; break;
+ case DEBUG: levelcolor = BROWN; bright = true; break;
+ case INFO: levelcolor = GRAY; bright = false; break;
+ case WARN: levelcolor = BROWN; bright = false; break;
+ case ERROR: levelcolor = RED; bright = true; break;
+ }
+
+ while(str.indexOf('\n') != -1) {
+ logstream.println(classname + colorize(levelcolor, bright, str.substring(0, str.indexOf('\n'))));
+ classname = logDates ? " " : " ";
+ classname = colorize(GRAY,false,classname);
+ str = str.substring(str.indexOf('\n') + 1);
+ }
+ logstream.println(classname + colorize(levelcolor, bright, str));
+ }
+
+ public static void recursiveLog(String indent, String name, Object o) throws JSExn {
+ if (!name.equals("")) name += " : ";
+
+ if (o == null) {
+ JS.log(indent + name + "<null>");
+
+ } else if (o instanceof JSArray) {
+ JS.log(indent + name + "<array>");
+ JSArray na = (JSArray)o;
+ for(int i=0; i<na.length(); i++)
+ recursiveLog(indent + " ", i + "", na.elementAt(i));
+
+ } else if (o instanceof JS) {
+ JS.log(indent + name + "<object>");
+ JS s = (JS)o;
+ Enumeration e = s.keys();
+ while(e.hasMoreElements()) {
+ Object key = e.nextElement();
+ if (key != null)
+ recursiveLog(indent + " ", key.toString(),
+ (key instanceof Integer) ?
+ s.get(((Integer)key)) : s.get(key.toString()));
+ }
+ } else {
+ JS.log(indent + name + o);
+
+ }
+ }
+
+}
--- /dev/null
+/*
+UserInfo:
+ On start:
+ 0: Addr of CAB/EXE
+ 1: Length of CAB/EXE
+ On Edit:
+ 2: Addr of output_table array
+
+Exit codes:
+ 0: Success
+ 1: Internal Error
+ 2: Invalid CAB
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include <sys/fcntl.h>
+
+#include "mspack.h"
+
+#define MAX(a,b) (((a)>(b))?(a):(b))
+#define MIN(a,b) (((a)<(b))?(a):(b))
+#define MAX_MEMBERS 64
+
+char *xstrdup(const char *s) {
+ char *ret = strdup(s);
+ if(ret == NULL) exit(1);
+ return ret;
+}
+
+typedef struct {
+ char *addr;
+ int pos;
+ int size;
+ int length;
+ int writable;
+} mem_buf_t;
+
+static mem_buf_t *cab_mem_buf = NULL;
+
+static void mem_buf_grow(mem_buf_t *buf,size_t newsize) {
+ size_t new_len;
+ char *p;
+ if(buf->length < 0) exit(1);
+ if(newsize <= buf->length) return;
+ new_len = MAX(buf->length ? buf->length*2 : 65536,newsize);
+ p = realloc(buf->addr,new_len);
+ if(p == NULL) exit(1);
+ buf->addr = p;
+ buf->length = new_len;
+}
+
+static struct {
+ char *filename;
+ mem_buf_t buf;
+} write_buf_table[MAX_MEMBERS];
+
+static struct {
+ char *filename;
+ char *data;
+ int length;
+} output_table[MAX_MEMBERS+1];
+
+static struct mspack_file *my_open(struct mspack_system *sys, char *filename, int mode) {
+ mem_buf_t *buf = NULL;
+ int i;
+ if(strcmp(filename,"/dev/cab")==0) {
+ if(mode != MSPACK_SYS_OPEN_READ) return NULL;
+ buf = cab_mem_buf;
+ } else {
+ if(mode != MSPACK_SYS_OPEN_WRITE) return NULL;
+
+ for(i=0;i<MAX_MEMBERS;i++) {
+ if(write_buf_table[i].filename == NULL) {
+ write_buf_table[i].filename = xstrdup(filename);
+ buf = &write_buf_table[i].buf;
+ buf->writable = 1;
+ break;
+ }
+ }
+ }
+
+ return (struct mspack_file *) buf;
+}
+
+static void my_close(struct mspack_file *buf_) {
+ mem_buf_t *buf = (mem_buf_t*) buf_;
+ /* NO OP */
+}
+
+static int my_read(struct mspack_file *buf_, void *out, int count) {
+ mem_buf_t *buf = (mem_buf_t*) buf_;
+ count = MIN(buf->size - buf->pos, count);
+ memcpy(out,buf->addr + buf->pos,count);
+ buf->pos += count;
+ return count;
+}
+
+static int my_write(struct mspack_file *buf_, void *in, int count) {
+ mem_buf_t *buf = (mem_buf_t*) buf_;
+ if(!buf->writable) return -1;
+ if(buf->length < buf->pos + count) mem_buf_grow(buf,buf->pos + count);
+ memcpy(buf->addr+buf->pos,in,count);
+ buf->pos += count;
+ buf->size = MAX(buf->size,buf->pos);
+ return count;
+}
+
+static int my_seek(struct mspack_file *buf_, off_t off, int mode) {
+ mem_buf_t *buf = (mem_buf_t*) buf_;
+ int newpos;
+ switch(mode) {
+ case MSPACK_SYS_SEEK_START: newpos = off; break;
+ case MSPACK_SYS_SEEK_CUR: newpos = buf->pos + off; break;
+ case MSPACK_SYS_SEEK_END: newpos = buf->size - off; break;
+ default: return -1;
+ }
+ if(newpos < 0) return -1;
+ if(newpos > buf->size) {
+ if(!buf->writable) return -1;
+ if(newpos > buf->length)
+ mem_buf_grow(buf,newpos);
+ }
+ buf->pos = newpos;
+ return 0;
+}
+
+static off_t my_tell(struct mspack_file *buf_) {
+ mem_buf_t *buf = (mem_buf_t*) buf_;
+ return buf ? buf->pos : 0;
+}
+
+// FEATURE: Remove this to possibly avoid pulling in stdio from libc
+// (it may be getting pulled in anyway from malloc or something)
+static void my_message(struct mspack_file *file, char *format, ...) {
+ va_list ap;
+ va_start(ap, format);
+ vfprintf(stderr, format, ap);
+ va_end(ap);
+ fputc((int) '\n', stderr);
+ fflush(stderr);
+}
+
+static void *my_alloc(struct mspack_system *sys, size_t size) { return malloc(size); }
+static void my_free(void *p) { free(p); }
+static void my_copy(void *src, void *dest, size_t bytes) { memcpy(dest, src, bytes); }
+
+static struct mspack_system my_system = {
+ &my_open,
+ &my_close,
+ &my_read,
+ &my_write,
+ &my_seek,
+ &my_tell,
+ &my_message,
+ &my_alloc,
+ &my_free,
+ &my_copy,
+ NULL
+};
+
+extern char *user_info[1024];
+
+int mspack_main() {
+ struct mscab_decompressor *decomp;
+ struct mscabd_cabinet *cab;
+ struct mscabd_file *file;
+ mem_buf_t mem_buf;
+ size_t size = (size_t)user_info[1];
+ int i;
+
+ mem_buf.addr = user_info[0];
+ mem_buf.pos = mem_buf.writable = 0;
+ mem_buf.length = -1;
+ mem_buf.size = size;
+
+ cab_mem_buf = &mem_buf;
+
+ decomp = mspack_create_cab_decompressor(&my_system);
+ if(!decomp) exit(1);
+
+ cab = decomp->search(decomp,"/dev/cab");
+ if(!cab) exit(2);
+
+ for(file = cab->files;file;file=file->next)
+ decomp->extract(decomp,file,file->filename);
+
+ decomp->close(decomp,cab);
+ mspack_destroy_cab_decompressor(decomp);
+
+ for(i=0;i<MAX_MEMBERS && write_buf_table[i].filename;i++) {
+ output_table[i].filename = write_buf_table[i].filename;
+ output_table[i].data = write_buf_table[i].buf.addr;
+ output_table[i].length = write_buf_table[i].buf.size;
+ }
+
+ user_info[2] = (char*) output_table;
+
+ return 0;
+}
--- /dev/null
+package org.ibex.util;
+
+import org.ibex.core.Main;
+import org.ibex.util.*;
+import java.io.*;
+import org.ibex.nestedvm.*;
+import org.ibex.nestedvm.Runtime;
+
+public class MSPack {
+ private static byte[] image;
+
+ private String[] fileNames;
+ private int[] lengths;
+ private byte[][] data;
+
+ public static class MSPackException extends IOException { public MSPackException(String s) { super(s); } }
+
+ public MSPack(InputStream cabIS) throws IOException {
+ try {
+ Runtime vm = (Runtime)Class.forName("org.ibex.util.MIPSApps").newInstance();
+ byte[] cab = InputStreamToByteArray.convert(cabIS);
+ int cabAddr = vm.sbrk(cab.length);
+ if(cabAddr < 0) throw new MSPackException("sbrk failed");
+
+ vm.copyout(cab,cabAddr,cab.length);
+
+ vm.setUserInfo(0,cabAddr);
+ vm.setUserInfo(1,cab.length);
+
+ int status = vm.run(new String[]{ "mspack"} );
+ if(status != 0) throw new MSPackException("mspack.mips failed (" + status + ")");
+
+ /*static struct {
+ char *filename;
+ char *data;
+ int length;
+ } output_table[MAX_MEMBERS+1]; */
+
+ int filesTable = vm.getUserInfo(2);
+ int count=0;
+ while(vm.memRead(filesTable+count*12) != 0) count++;
+
+ fileNames = new String[count];
+ data = new byte[count][];
+ lengths = new int[count];
+
+ for(int i=0,addr=filesTable;i<count;i++,addr+=12) {
+ int length = vm.memRead(addr+8);
+ data[i] = new byte[length];
+ lengths[i] = length;
+ fileNames[i] = vm.cstring(vm.memRead(addr));
+ System.out.println("" + fileNames[i]);
+ vm.copyin(vm.memRead(addr+4),data[i],length);
+ }
+ } catch(Runtime.ExecutionException e) {
+ e.printStackTrace();
+ throw new MSPackException("mspack.mips crashed");
+ } catch(Exception e) {
+ throw new MSPackException(e.toString());
+ }
+ }
+
+ public String[] getFileNames() { return fileNames; }
+ public int[] getLengths() { return lengths; }
+ public InputStream getInputStream(int index) {
+ return new KnownLength.KnownLengthInputStream(new ByteArrayInputStream(data[index]), data[index].length);
+ }
+ public InputStream getInputStream(String fileName) {
+ for(int i=0;i<fileNames.length;i++) {
+ if(fileName.equalsIgnoreCase(fileNames[i])) return getInputStream(i);
+ }
+ return null;
+ }
+
+ public static void main(String[] args) throws IOException {
+ MSPack pack = new MSPack(new FileInputStream(args[0]));
+ String[] files = pack.getFileNames();
+ for(int i=0;i<files.length;i++)
+ System.out.println(i + ": " + files[i] + ": " + pack.getLengths()[i]);
+ System.out.println("Writing " + files[files.length-1]);
+ InputStream is = pack.getInputStream(files.length-1);
+ OutputStream os = new FileOutputStream(files[files.length-1]);
+ int n;
+ byte[] buf = new byte[4096];
+ while((n = is.read(buf)) != -1) os.write(buf,0,n);
+ os.close();
+ is.close();
+ }
+}
+
--- /dev/null
+package org.ibex.util;
+import java.util.*;
+import java.io.*;
+import java.util.zip.*;
+import org.apache.bcel.*;
+import org.apache.bcel.generic.*;
+import org.apache.bcel.classfile.*;
+import org.apache.bcel.util.*;
+
+public class NanoGoat {
+
+ public static final boolean deleteMethods = false;
+ public static SyntheticRepository repo = null;
+ public static HashSet dest = new HashSet();
+ public static HashSet constructed = new HashSet();
+ public static String outdir = ".";
+ public static Hashtable subclasses = new Hashtable();
+ public static Hashtable uponconstruction = new Hashtable();
+ public static Hashtable mark_if_constructed = new Hashtable();
+ public static int level = 0;
+
+ public NanoGoat() { }
+
+ public void loadAllMethods(String classname) throws Exception {
+ visitJavaClass(repo.loadClass(classname));
+ Method[] meths = getMethods(repo.loadClass(classname));
+ for(int i=0; i<meths.length; i++)
+ visitJavaMethod(repo.loadClass(classname), meths[i]);
+ }
+
+ public void loadAllStaticMethods(String classname) throws Exception {
+ visitJavaClass(repo.loadClass(classname));
+ Method[] meths = getMethods(repo.loadClass(classname));
+ for(int i=0; i<meths.length; i++)
+ if (meths[i].isStatic())
+ visitJavaMethod(repo.loadClass(classname), meths[i]);
+ }
+
+ public void loadMethod(String classAndMethodName) throws Exception {
+ String classname = classAndMethodName.substring(0, classAndMethodName.lastIndexOf('.'));
+ String methodname = classAndMethodName.substring(classAndMethodName.lastIndexOf('.') + 1);
+ if (classname.endsWith("." + methodname)) methodname = "<init>";
+ visitJavaClass(repo.loadClass(classname));
+ Method[] meths = getMethods(repo.loadClass(classname));
+ for(int i=0; i<meths.length; i++)
+ if (meths[i].getName().equals(methodname))
+ visitJavaMethod(repo.loadClass(classname), meths[i]);
+ }
+ public static void main(String[] args) throws Exception {
+ int start = 1;
+ repo = SyntheticRepository.getInstance(new ClassPath(args[0]));
+
+ NanoGoat bcp = new NanoGoat();
+ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+ for(String s = br.readLine(); s != null; s = br.readLine()) {
+ s = s.trim();
+ if (s.length() == 0) continue;
+ try {
+ if (s.endsWith("$")) s = s.substring(0, s.length() - 1);
+ if (s.endsWith(".class")) {
+ bcp.visitJavaClass(repo.loadClass(s.substring(0, s.length() - 6)));
+ } else {
+ JavaClass cl = repo.loadClass(s.substring(0, s.lastIndexOf('.')));;
+ bcp.visitJavaClass(cl);
+ bcp.loadMethod(s);
+ Field[] fields = cl.getFields();
+ for(int j=0; j<fields.length; j++) {
+ if (fields[j].getName().equals(s.substring(s.lastIndexOf('.') + 1)))
+ bcp.visitJavaField(fields[j], cl);
+ }
+ }
+ } catch (Exception e) {
+ System.out.println("WARNING: couldn't load class for " + s);
+ e.printStackTrace();
+ }
+ }
+
+ System.out.println("\n\n======================================================================\n");
+
+ // we call start(), but the VM calls run()...
+ bcp.loadMethod("java.lang.Thread.run");
+ bcp.loadAllMethods("java.lang.SecurityContext");
+ bcp.loadAllMethods("java.lang.ThreadDeath");
+ bcp.loadMethod("java.lang.Thread.run"); // we call start(), but the VM calls run()...
+ bcp.loadMethod("java.lang.ref.Reference.enqueue"); // the GC calls this directly
+ bcp.loadAllMethods("gnu.gcj.runtime.StringBuffer"); // the compiler emits calls directly to this class
+ bcp.loadAllMethods("gnu.gcj.convert.Input_UTF8"); // retrieved via reflection
+ bcp.loadAllMethods("gnu.gcj.convert.Output_UTF8"); // retrieved via reflection
+ bcp.loadMethod("gnu.gcj.convert.BytesToUnicode.done"); // called by natString
+ bcp.loadAllStaticMethods("java.lang.reflect.Modifier"); // used all over natClass...
+
+ // the Interpreter.run() method's switchblock is too complex...
+ bcp.loadAllMethods("org.ibex.js.Interpreter$TryMarker");
+ bcp.loadAllMethods("org.ibex.js.Interpreter$CatchMarker");
+ bcp.loadAllMethods("org.ibex.js.Interpreter$LoopMarker");
+ bcp.loadAllMethods("org.ibex.js.Interpreter$FinallyData");
+ bcp.loadAllMethods("org.ibex.js.Interpreter$CallMarker");
+ bcp.loadAllMethods("org.ibex.js.Interpreter");
+ bcp.loadAllMethods("org.ibex.js.Interpreter$1");
+ bcp.loadAllMethods("org.ibex.js.Interpreter$Stub");
+ bcp.loadAllMethods("org.ibex.js.Trap$TrapScope");
+ bcp.loadMethod("org.ibex.js.JSScope.top");
+ bcp.loadAllMethods("org.ibex.Picture$1");
+ bcp.loadAllMethods("org.ibex.Ibex$Blessing");
+ bcp.loadAllMethods("org.ibex.util.SSL$entropySpinner");
+ bcp.loadAllMethods("org.ibex.HTTP$HTTPInputStream");
+ bcp.visitJavaClass(repo.loadClass("org.ibex.util.SSL"));
+
+ bcp.loadAllMethods("java.util.Hashtable$HashIterator");
+ bcp.loadMethod("java.util.SimpleTimeZone.useDaylightTime");
+ bcp.visitJavaClass(repo.loadClass("gnu.gcj.runtime.FinalizerThread"));
+ bcp.visitJavaClass(repo.loadClass("gnu.gcj.runtime.FirstThread"));
+
+ // to ensure we get all the stuff that might be called from CNI
+ bcp.loadAllMethods("org.ibex.plat.Linux");
+ bcp.loadAllMethods("org.ibex.plat.X11");
+ bcp.loadAllMethods("org.ibex.plat.GCJ");
+ bcp.loadAllMethods("org.ibex.plat.POSIX");
+ bcp.loadAllMethods("org.ibex.plat.X11$X11Surface");
+ bcp.loadAllMethods("org.ibex.plat.X11$X11PixelBuffer");
+ bcp.loadAllMethods("org.ibex.plat.X11$X11Picture");
+ bcp.loadAllMethods("org.ibex.Surface");
+ bcp.loadAllMethods("org.ibex.Picture");
+ bcp.loadAllMethods("org.ibex.PixelBuffer");
+
+ // primary entry point
+ bcp.loadMethod("org.ibex.plat.Linux.main");
+ System.out.println();
+
+ System.out.println("Dumping...");
+ ZipFile zf = new ZipFile(args[0]);
+ ZipOutputStream zos = new ZipOutputStream(new FileOutputStream(args[0] + ".tmp"));
+ Enumeration e = zf.entries();
+ while(e.hasMoreElements()) {
+ ZipEntry ze = ((ZipEntry)e.nextElement());
+ String ss = ze.getName();
+ if (!ss.endsWith(".class")) continue;
+ ss = ss.substring(0, ss.length() - 6);
+ ss = ss.replace('/', '.');
+ dump(repo.loadClass(ss), zos);
+ }
+ zos.close();
+ zf.close();
+ new File(args[0] + ".tmp").renameTo(new File(args[0] + ".pruned"));
+ }
+
+ public static void dump(JavaClass clazz, ZipOutputStream zos) throws Exception {
+ if (!dest.contains(clazz)) return;
+
+ ConstantPoolGen newcpg = new ConstantPoolGen(clazz.getConstantPool());
+ ClassGen cg = new ClassGen(clazz);
+ InstructionFactory factory = new InstructionFactory(cg, newcpg);
+ cg.setMajor(46);
+ cg.setMinor(0);
+ cg.setConstantPool(newcpg);
+
+ boolean isconstructed = false;
+ Method[] methods = getMethods(clazz);
+ for(int i=0; i<methods.length; i++)
+ if (dest.contains(methods[i]) && methods[i].getName().equals("<init>"))
+ isconstructed = true;
+
+ // we can only prune static fields (to avoid altering object layout, which is hardcoded into
+ // CNI code), but that's okay since instance fields don't contribute to binary size
+ Field[] fields = clazz.getFields();
+ for(int i=0; i<fields.length; i++) {
+ if ((!dest.contains(fields[i]) && fields[i].isStatic()) ||
+ ((!(constructed.contains(clazz))) && !fields[i].isStatic())) {
+ System.out.println(" pruning field " + clazz.getClassName() + "." + fields[i].getName());
+ // FIXME this confuses gcj in jar-at-a-time mode
+ //cg.removeField(fields[i]);
+ }
+ }
+
+ int numMethods = 0;
+ boolean good = false;
+ for(int i=0; i<methods.length; i++) {
+ if (dest.contains(methods[i]) && (isconstructed || methods[i].isStatic())) {
+ good = true;
+ } else {
+ if (methods[i].getCode() == null) {
+ System.out.println(" empty codeblock: " + clazz.getClassName() + "." + methods[i].getName());
+ } else {
+ System.out.println(" pruning " +(isconstructed?"":"unconstructed")+ " method " +
+ clazz.getClassName() + "." + methods[i].getName());
+ if (deleteMethods) { cg.removeMethod(methods[i]); continue; }
+ MethodGen mg = new MethodGen(methods[i], clazz.getClassName(), newcpg);
+ mg.removeExceptions();
+ InstructionList il = new InstructionList();
+ mg.setInstructionList(il);
+ InstructionHandle ih_0 = il.append(factory.createNew("java.lang.UnsatisfiedLinkError"));
+ il.append(InstructionConstants.DUP);
+ il.append(factory.createInvoke("java.lang.UnsatisfiedLinkError",
+ "<init>", Type.VOID, Type.NO_ARGS, Constants.INVOKESPECIAL));
+ il.append(InstructionConstants.ATHROW);
+ mg.setMaxStack();
+ mg.setMaxLocals();
+ mg.removeExceptions();
+ mg.removeLocalVariables();
+ mg.removeExceptionHandlers();
+ mg.removeLineNumbers();
+ cg.replaceMethod(methods[i], mg.getMethod());
+ il.dispose();
+ }
+ }
+ }
+
+ // FIXME: chain up to superclass' <clinit>... that might remove the need for this hack
+ // FIXME: gcj compiling in jar-at-a-time mode can't be convinced to let classes outside the jar override
+ // the ones inside the jar
+ good = true;
+
+ if (!good && !clazz.isAbstract() && !clazz.isInterface()) {
+ System.out.println("DROPPING " + clazz.getClassName());
+ JavaClass[] ifaces = clazz.getInterfaces();
+ String[] ifacestrings = new String[ifaces.length];
+ for(int i=0; i<ifaces.length; i++) ifacestrings[i] = ifaces[i].getClassName();
+ cg = new ClassGen(clazz.getClassName(),
+ clazz.getSuperClass().getClassName(),
+ clazz.getFileName(),
+ clazz.getAccessFlags(),
+ ifacestrings,
+ newcpg);
+ } else {
+ System.out.println("dumping " + clazz.getClassName());
+ }
+ FilterOutputStream noclose = new FilterOutputStream(zos) { public void close() throws IOException { flush(); } };
+ zos.putNextEntry(new ZipEntry(clazz.getClassName().replace('.', '/')+".class"));
+ cg.getJavaClass().dump(noclose);
+ noclose.flush();
+ }
+
+ public JavaClass sig2class(String sig) throws Exception {
+ if (sig == null) return null;
+ while (sig.length() > 0 && (sig.charAt(0) == 'L' || sig.charAt(0) == '[')) {
+ if (sig.charAt(0) == 'L') sig = sig.substring(1, sig.length() - 1);
+ else if (sig.charAt(0) == '[') sig = sig.substring(1, sig.length());
+ }
+ if (sig.length() <= 1) return null;
+ if (sig.equals("<null object>")) return null;
+ if (sig.startsWith("<return address")) return null;
+ return repo.loadClass(sig);
+ }
+ public void load(String sig) throws Exception {
+ if (sig == null) return;
+ while (sig.length() > 0 && (sig.charAt(0) == 'L' || sig.charAt(0) == '[')) {
+ if (sig.charAt(0) == 'L') sig = sig.substring(1, sig.length() - 1);
+ else if (sig.charAt(0) == '[') sig = sig.substring(1, sig.length());
+ }
+ if (sig.length() <= 1) return;
+ if (sig.equals("<null object>")) return;
+ if (sig.startsWith("<return address")) return;
+ visitJavaClass(repo.loadClass(sig));
+ }
+ public void load(Type t) throws Exception {
+ if (t == null) return;
+ if (t instanceof ArrayType) load(((ArrayType)t).getElementType());
+ if (!(t instanceof ObjectType)) return;
+ load(((ObjectType)t).getClassName());
+ }
+
+ public String getMethodSignature(Method m, ConstantPoolGen cpg) throws Exception { return m.getName() + m.getSignature(); }
+ public String getMethodSignature(InvokeInstruction ii, ConstantPoolGen cpg) throws Exception {
+ String sig = "";
+ Type[] argtypes = ii.getArgumentTypes(cpg);
+ for(int j=0; j<argtypes.length; j++) sig += argtypes[j].getSignature();
+ return ii.getMethodName(cpg) + "(" + sig + ")" + ii.getReturnType(cpg).getSignature();
+ }
+
+ public void visitJavaMethod(JavaClass jc, Method method) throws Exception {
+ visitJavaClass(jc);
+ if (jc.getClassName().indexOf("SharedLib") != -1) return;
+ if (jc.getClassName().indexOf("Datagram") != -1) return;
+ if (jc.getClassName().startsWith("java.io.Object")) return;
+ if (jc.getClassName().startsWith("java.util.jar.")) return;
+ if (jc.getClassName().startsWith("java.net.Inet6")) return;
+
+ // gcj bug; gcj can't compile this method from a .class file input; I have no idea why
+ if (jc.getClassName().equals("java.lang.System") && method.getName().equals("runFinalizersOnExit")) return;
+
+ // we know these can't be constructed
+ if (method.getName().equals("<init>") && jc.getClassName().startsWith("java.lang.reflect.")) return;
+
+ if (dest.contains(method)) return;
+ dest.add(method);
+
+ if (method.getName().equals("<clinit>") && jc.getSuperClass() != null)
+ loadMethod(jc.getSuperClass().getClassName() + ".<clinit>");
+
+ if (method.isStatic() || method.getName().equals("<init>")) loadMethod(jc.getClassName() + ".<clinit>");
+ if (method.getName().equals("<init>")) {
+ // FIXME: generalize to all perinstancemethods
+ constructed.add(jc);
+ HashSet hs = (HashSet)uponconstruction.get(jc);
+ if (hs != null) {
+ Iterator it = hs.iterator();
+ while(it.hasNext()) visitJavaMethod(jc, (Method)it.next());
+ }
+ loadMethod(jc.getClassName() + ".equals");
+ loadMethod(jc.getClassName() + ".hashCode");
+ loadMethod(jc.getClassName() + ".toString");
+ loadMethod(jc.getClassName() + ".finalize");
+ loadMethod(jc.getClassName() + ".clone");
+ }
+
+ ConstantPoolGen cpg = new ConstantPoolGen(method.getConstantPool());
+ if (!method.isStatic() && !constructed.contains(jc)) {
+ HashSet hs = (HashSet)uponconstruction.get(jc);
+ if (hs == null) uponconstruction.put(jc, hs = new HashSet());
+ hs.add(method);
+ markMethodInSubclasses(jc, method, cpg);
+ dest.remove(method);
+ return;
+ }
+
+ level += 2;
+ for(int i=0; i<level; i++) System.out.print(" ");
+ System.out.print(jc.getClassName() + "." + getMethodSignature(method, cpg));
+ markMethodInSubclasses(jc, method, cpg);
+ if (method.getCode() == null) { System.out.println(); level -= 2; return; }
+ byte[] code = method.getCode().getCode();
+ InstructionList il = new InstructionList(code);
+ InstructionHandle[] instructions = il.getInstructionHandles();
+ System.out.println(" [" + instructions.length + " instructions]");
+ for(int i=0; i<instructions.length; i++){
+ Instruction instr = instructions[i].getInstruction();;
+ if (instr instanceof Select) {
+ InstructionHandle[] ih2 = ((Select)instr).getTargets();
+ InstructionHandle[] ih3 = new InstructionHandle[instructions.length + ih2.length];
+ System.arraycopy(instructions, 0, ih3, 0, instructions.length);
+ System.arraycopy(ih2, 0, ih3, instructions.length, ih2.length);
+ instructions = ih3;
+ }
+ if (instr instanceof LoadClass) {
+ ObjectType ot = (ObjectType)((LoadClass)instr).getLoadClassType(cpg);
+ if (ot != null) loadMethod(ot.getClassName() + ".<clinit>");
+ }
+ if (instr instanceof CPInstruction) load(((CPInstruction)instr).getType(cpg));
+ if (instr instanceof TypedInstruction) load(((TypedInstruction)instr).getType(cpg));
+ if (instr instanceof NEW) loadMethod(((NEW)instr).getLoadClassType(cpg).getClassName() + ".<init>");
+ if (instr instanceof org.apache.bcel.generic.FieldOrMethod)
+ load(((org.apache.bcel.generic.FieldOrMethod)instr).getClassType(cpg));
+ if (instr instanceof org.apache.bcel.generic.FieldInstruction) {
+ load(((org.apache.bcel.generic.FieldInstruction)instr).getFieldType(cpg));
+ load(((org.apache.bcel.generic.FieldInstruction)instr).getType(cpg));
+ String fieldName = ((org.apache.bcel.generic.FieldInstruction)instr).getFieldName(cpg);
+ JavaClass jc2 = repo.loadClass(((ObjectType)((org.apache.bcel.generic.FieldInstruction)instr).
+ getLoadClassType(cpg)).getClassName());
+ Field[] fields = jc2.getFields();
+ for(int j=0; j<fields.length; j++) if (fields[j].getName().equals(fieldName)) visitJavaField(fields[j], jc2);
+ }
+ if (instr instanceof InvokeInstruction) {
+ InvokeInstruction ii = (InvokeInstruction)instr;
+ String ii_sig = getMethodSignature(ii, cpg);
+ JavaClass c = sig2class(ii.getLoadClassType(cpg).getSignature());
+
+ load(ii.getType(cpg));
+ Method[] meths = getMethods(c);
+ boolean good = false;
+ for(int i2=0; i2<meths.length; i2++) {
+ if (getMethodSignature(meths[i2], cpg).equals(ii_sig)) {
+ visitJavaMethod(c, meths[i2]);
+ good = true;
+ break;
+ }
+ }
+ if (!good) throw new Exception("couldn't find method " + getMethodSignature(ii, cpg) + " in " + c.getClassName());
+ }
+ }
+ Type[] argtypes = method.getArgumentTypes();
+ for(int i=0; i<argtypes.length; i++) load(argtypes[i]);
+ if (method.getExceptionTable() != null) {
+ String[] exntypes = method.getExceptionTable().getExceptionNames();
+ for(int i=0; i<exntypes.length; i++) load(exntypes[i]);
+ }
+ level -= 2;
+ }
+
+ public void visitJavaField(Field field, JavaClass clazz) throws Exception {
+ if (dest.contains(field)) return;
+ dest.add(field);
+ if (field.isStatic()) loadMethod(clazz.getClassName() + ".<clinit>");
+ }
+
+ public void visitJavaClass(JavaClass clazz) throws Exception {
+ if (dest.contains(clazz)) return;
+ dest.add(clazz);
+
+ ConstantPoolGen cpg = new ConstantPoolGen(clazz.getConstantPool());
+ level += 2;
+ for(int i=0; i<level; i++) System.out.print(" ");
+ System.out.println(clazz.getClassName() + ".class");
+
+ JavaClass superclass = clazz.getSuperClass();
+ for(JavaClass sup = superclass; sup != null; sup = sup.getSuperClass()) {
+ if (subclasses.get(sup) == null) subclasses.put(sup, new HashSet());
+ ((HashSet)subclasses.get(sup)).add(clazz);
+ }
+ JavaClass[] interfaces = clazz.getAllInterfaces();
+ for(int i=0; i<interfaces.length; i++) {
+ if (subclasses.get(interfaces[i]) == null) subclasses.put(interfaces[i], new HashSet());
+ ((HashSet)subclasses.get(interfaces[i])).add(clazz);
+ }
+
+ for(JavaClass sup = superclass; sup != null; sup = sup.getSuperClass()) {
+ visitJavaClass(sup);
+ remarkMethods(sup, clazz, cpg);
+ }
+ for(int i=0; i<interfaces.length; i++) {
+ visitJavaClass(interfaces[i]);
+ remarkMethods(interfaces[i], clazz, cpg);
+ }
+
+ Field[] fields = clazz.getFields();
+ for(int i=0; i<fields.length; i++) {
+ if (!fields[i].isStatic()) visitJavaField(fields[i], clazz);
+ else {
+ Type t = fields[i].getType();
+ if (t instanceof ObjectType) load(t);
+ }
+ }
+ level -= 2;
+ }
+
+ public void markMethodInSubclasses(JavaClass c, Method m, JavaClass subclass, ConstantPoolGen cpg) throws Exception {
+ if (m.isStatic()) return;
+ if (m.getName().equals("<init>")) return;
+ if (m.getName().equals("equals")) return;
+ if (m.getName().equals("hashCode")) return;
+ if (m.getName().equals("clone")) return;
+ if (m.getName().equals("finalize")) return;
+ if (m.getName().equals("toString")) return;
+ String sig = getMethodSignature(m, cpg);
+ Method[] submethods = getMethods(subclass);
+ for(int j=0; j<submethods.length; j++)
+ if (getMethodSignature(submethods[j], cpg).equals(sig))
+ visitJavaMethod(subclass, submethods[j]);
+ }
+ public void markMethodInSubclasses(JavaClass c, Method m, ConstantPoolGen cpg) throws Exception {
+ if (m.isStatic()) return;
+ if (m.getName().equals("<init>")) return;
+ HashSet s = (HashSet)subclasses.get(c);
+ if (s == null) return;
+ Object[] subclasses = s.toArray();
+ for(int i=0; i<subclasses.length; i++) {
+ JavaClass subclass = (JavaClass)subclasses[i];
+ if (subclass == c) continue;
+ markMethodInSubclasses(c, m, subclass, cpg);
+ }
+ }
+
+ public void remarkMethods(JavaClass c, ConstantPoolGen cpg) throws Exception {
+ Method[] meths =getMethods(c);
+ for(int j=0; j<meths.length; j++)
+ if (dest.contains(meths[j]) ||
+ (uponconstruction.get(c) != null && ((HashSet)uponconstruction.get(c)).contains(meths[j])))
+ markMethodInSubclasses(c, meths[j], cpg);
+ }
+
+ public void remarkMethods(JavaClass c, JavaClass target, ConstantPoolGen cpg) throws Exception {
+ Method[] meths = getMethods(c);
+ for(int j=0; j<meths.length; j++)
+ if (dest.contains(meths[j]) ||
+ (uponconstruction.get(c) != null && ((HashSet)uponconstruction.get(c)).contains(meths[j])))
+ markMethodInSubclasses(c, meths[j], target, cpg);
+ }
+
+ public static Hashtable methodsHashtable = new Hashtable();
+ public static Method[] getMethods(JavaClass c) {
+ Method[] ret = (Method[])methodsHashtable.get(c);
+ if (ret == null) methodsHashtable.put(c, ret = c.getMethods());
+ return ret;
+ }
+
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+/** packs 8-bit bytes into a String of 7-bit chars (to avoid the UTF-8 non-ASCII penalty) */
+public class PackBytesIntoString {
+
+ public static String pack(byte[] b, int off, int len) throws IllegalArgumentException {
+ if (len % 7 != 0) throw new IllegalArgumentException("len must be a multiple of 7");
+ StringBuffer ret = new StringBuffer();
+ for(int i=off; i<off+len; i += 7) {
+ long l = 0;
+ for(int j=6; j>=0; j--) {
+ l <<= 8;
+ l |= (b[i + j] & 0xff);
+ }
+ for(int j=0; j<8; j++) {
+ ret.append((char)(l & 0x7f));
+ l >>= 7;
+ }
+ }
+ return ret.toString();
+ }
+
+ public static byte[] unpack(String s) throws IllegalArgumentException {
+ if (s.length() % 8 != 0) throw new IllegalArgumentException("string length must be a multiple of 8");
+ byte[] ret = new byte[(s.length() / 8) * 7];
+ for(int i=0; i<s.length(); i += 8) {
+ long l = 0;
+ for(int j=7; j>=0; j--) {
+ l <<= 7;
+ l |= (s.charAt(i + j) & 0x7fL);
+ }
+ for(int j=0; j<7; j++) {
+ ret[(i / 8) * 7 + j] = (byte)(l & 0xff);
+ l >>= 8;
+ }
+ }
+ return ret;
+ }
+}
+
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+import gnu.regexp.*;
+import java.util.*;
+import java.io.*;
+
+/**
+ * A VERY crude, inefficient Java preprocessor
+ *
+ * //#define FOO bar baz -- replace all instances of token FOO with "bar baz"
+ * //#replace foo/bar baz/bop -- DUPLICATE everything between here and //#end,
+ * replacing foo with bar and baz with bop in the *second* copy
+ * //#switch(EXPR) -- switch on strings
+ * case "case1":
+ * //#end
+ *
+ * Replacements are done on a token basis. Tokens are defined as a
+ * sequence of characters which all belong to a single class. The
+ * two character classes are:
+ *
+ * - [a-zA-Z0-9_]
+ * - all other non-whitespace characters
+ */
+public class Preprocessor {
+
+ public static String replaceAll(String source, String regexp, String replaceWith) {
+ try {
+ RE re = new RE(regexp, 0, RESyntax.RE_SYNTAX_PERL5);
+ return (String)re.substituteAll(source, replaceWith);
+ } catch (Exception e) {
+ e.printStackTrace();
+ return null;
+ }
+ }
+
+ public static void main(String[] args) throws Exception {
+ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+ BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
+
+ // process stdin to stdout
+ Preprocessor cc = new Preprocessor(br, bw);
+ Vector err = cc.process();
+ bw.flush();
+
+ // handle errors
+ boolean errors = false;
+ for (int i=0; i < err.size(); i++) { if (err.get(i) instanceof Error) errors = true; System.err.println(err.get(i)); }
+ if (errors) throw new Exception();
+ }
+
+ private Reader r;
+ private Writer w;
+ private LineNumberReader in;
+ private PrintWriter out;
+
+ private Hashtable replace = new Hashtable();
+ private Hashtable repeatreplace = null;
+ private Vector sinceLastRepeat = null;
+ private Vector err = new Vector();
+
+ private int enumSwitch = 0; // number appended to variable used in switch implementation
+
+
+ public Preprocessor(Reader reader, Writer writer) {
+ setReader(reader);
+ setWriter(writer);
+ }
+
+ public void setReader(Reader reader) { r = reader; if (r != null) in = new LineNumberReader(r); }
+ public Reader getReader() { return r; }
+
+ public void setWriter(Writer writer) { w = writer; if (w != null) out = new PrintWriter(w); }
+ public Writer getWriter() { return w; }
+
+
+ /** process data from reader, write to writer, return vector of errors */
+ public Vector process() throws IOException {
+ err.clear();
+
+ String s = null;
+PROCESS:
+ while((s = in.readLine()) != null) {
+ if (sinceLastRepeat != null) sinceLastRepeat.addElement(s);
+ String trimmed = s.trim();
+
+ if (trimmed.startsWith("//#define ")) {
+ if (trimmed.length() == 9 || trimmed.charAt(9) != ' ') {
+ err.add(new Error("#define badly formed, ignored")); continue PROCESS;
+ }
+ int keyStart = indexOfNotWS(trimmed, 9);
+ if (keyStart == -1) {
+ err.add(new Error("#define requires KEY")); continue PROCESS;
+ }
+ int keyEnd = indexOfWS(trimmed, keyStart);
+
+ int macroStart = trimmed.indexOf('(');
+ int macroEnd = trimmed.indexOf(')');
+ if (macroStart > keyEnd) {
+ // no macro is defined, just make sure something dumb like KEYNA)ME hasn't been done
+ if (macroEnd < keyEnd) { err.add(new Error("#define key contains invalid char: ')'")); continue PROCESS; }
+ macroStart = macroEnd = -1;
+ }
+
+ if (macroStart == 0) {
+ err.add(new Error("#define macro requires name")); continue PROCESS;
+ } else if (macroStart > 0) {
+ if (macroStart > macroEnd) { err.add(new Error("#define macro badly formed")); continue PROCESS; }
+ if (macroStart+1 == macroEnd) { err.add(new Error("#define macro requires property name")); continue PROCESS; }
+
+ JSFunctionMacro fm = new JSFunctionMacro();
+ String key = trimmed.substring(keyStart, macroStart);
+ String unbound = trimmed.substring(macroStart +1, macroEnd);
+ int unboundDiv = unbound.indexOf(',');
+ if (unboundDiv == -1) {
+ fm.unbound1 = unbound;
+ } else {
+ fm.unbound1 = unbound.substring(0, unboundDiv);
+ fm.unbound2 = unbound.substring(unboundDiv +1);
+ if (fm.unbound1.length() == 0) { err.add(new Error("#define macro property 1 requires name")); continue PROCESS; }
+ if (fm.unbound2.length() == 0) { err.add(new Error("#define macro property 1 requires name")); continue PROCESS; }
+ }
+ fm.expression = trimmed.substring(keyEnd).trim();
+ replace.put(key, fm);
+ } else {
+ String key = trimmed.substring(keyStart, keyEnd);
+ String val = trimmed.substring(keyEnd).trim();
+ replace.put(key, val);
+ }
+ out.print("\n"); // preserve line numbers
+
+ } else if (trimmed.startsWith("//#repeat ")) {
+ trimmed = trimmed.substring(9);
+ while(trimmed.charAt(trimmed.length() - 1) == '\\') {
+ String s2 = in.readLine().trim();
+ if (s2.startsWith("//")) s2 = s2.substring(2).trim();
+ trimmed = trimmed.substring(0, trimmed.length() - 1) + " " + s2;
+ out.print("\n"); // preserve line numbers
+ }
+ StringTokenizer st = new StringTokenizer(trimmed, " ");
+ repeatreplace = (Hashtable)replace.clone();
+ while (st.hasMoreTokens()) {
+ String tok = st.nextToken().trim();
+ String key = tok.substring(0, tok.indexOf('/'));
+ String val = tok.substring(tok.indexOf('/') + 1);
+ repeatreplace.put(key, val);
+ }
+ sinceLastRepeat = new Vector();
+ out.print("\n"); // preserve line numbers
+
+ } else if (trimmed.startsWith("//#end")) {
+ if (sinceLastRepeat == null) { err.add(new Warning("#end orphaned")); continue PROCESS; }
+ Hashtable save = replace;
+ replace = repeatreplace;
+ out.print("\n");
+ for(int i=0; i<sinceLastRepeat.size() - 1; i++) out.print(processLine((String)sinceLastRepeat.elementAt(i), true));
+ sinceLastRepeat = null;
+ replace = save;
+
+ } else if (trimmed.startsWith("//#switch")) {
+ int expStart = trimmed.indexOf('(') +1;
+ if (expStart < 1) { err.add(new Error("expected ( in #switch")); continue PROCESS; }
+ int expEnd = trimmed.lastIndexOf(')');
+ if (expEnd == -1) { err.add(new Error("expected ) in #switch")); continue PROCESS; }
+ if (expEnd - expStart <= 1) { err.add(new Error("badly formed #switch statement")); continue PROCESS; }
+ String expr = trimmed.substring(expStart, expEnd);
+
+ out.print("final String ccSwitch"+enumSwitch+" = (String)("+expr+"); ");
+ out.print("SUCCESS:do { switch(ccSwitch"+enumSwitch+".length()) {\n");
+
+ Hashtable[] byLength = new Hashtable[255];
+ String key = null;
+ String Default = null;
+ for(trimmed = in.readLine().trim(); !trimmed.startsWith("//#end"); trimmed = in.readLine().trim()) {
+ if (trimmed.startsWith("default:")) {
+ Default = processLine(trimmed.substring(8), false);
+ continue;
+ }
+ if (trimmed.startsWith("case ")) {
+ // find key
+ int strStart = trimmed.indexOf('\"') +1;
+ if (strStart < 1) { err.add(new Error("expected opening of String literal")); continue PROCESS; }
+ int strEnd = trimmed.indexOf('\"', strStart);
+ if (strEnd == -1) { err.add(new Error("expected closing of String literal")); continue PROCESS; }
+ key = trimmed.substring(strStart, strEnd);
+
+ Hashtable thisCase = (Hashtable)byLength[key.length()];
+ if (thisCase == null) byLength[key.length()] = thisCase = new Hashtable();
+ thisCase.put(key, "");
+
+ // find end of case definition
+ int caseEnd = trimmed.indexOf(':', strEnd) +1;
+ if (caseEnd < 1) { err.add(new Error("expected :")); continue PROCESS; }
+ trimmed = trimmed.substring(caseEnd);
+ }
+
+ if (key != null) {
+ Hashtable hash = byLength[key.length()];
+ hash.put(key, (String)hash.get(key) + replaceAll(processLine(trimmed, false), "//[^\"]*$", "").trim() + "\n");
+ } else {
+ out.print(processLine(trimmed, false));
+ }
+ }
+
+ for(int i=0; i<255; i++) {
+ if (byLength[i] == null) continue;
+ out.print("case " + i + ": { switch(ccSwitch"+enumSwitch+".charAt(0)) { ");
+ buildTrie("", byLength[i]);
+ out.print("}; break; } ");
+ }
+ out.print("} /* switch */ ");
+ if (Default != null) out.print(" " + Default);
+ out.print(" } while(false); /* OUTER */\n");
+ enumSwitch++;
+
+ } else {
+ out.print(processLine(s, false));
+ }
+ }
+
+ return err;
+ }
+
+ private void buildTrie(String prefix, Hashtable cases) {
+ Enumeration caseKeys = cases.keys();
+ Vec keys = new Vec();
+ while(caseKeys.hasMoreElements()) keys.addElement(caseKeys.nextElement());
+ keys.sort(new Vec.CompareFunc() { public int compare(Object a, Object b) {
+ return ((String)a).compareTo((String)b);
+ } } );
+
+ for(int i=0; i<keys.size(); i++) {
+ if (!((String)keys.elementAt(i)).startsWith(prefix)) continue;
+ String prefixPlusOne = ((String)keys.elementAt(i)).substring(0, prefix.length() + 1);
+ if (i<keys.size()-1 && prefixPlusOne.equals((((String)keys.elementAt(i + 1)).substring(0, prefix.length() + 1)))) {
+ out.print("case \'" + prefixPlusOne.charAt(prefixPlusOne.length() - 1) + "\': { ");
+ out.print("switch(ccSwitch"+enumSwitch+".charAt(" + (prefix.length()+1) + ")) { ");
+ buildTrie(prefixPlusOne, cases);
+ out.print("} break; } ");
+ while(i<keys.size() && prefixPlusOne.equals(((String)keys.elementAt(i)).substring(0, prefix.length() + 1))) i++;
+ if (i<keys.size()) { i--; continue; }
+ } else {
+ out.print("case \'" + prefixPlusOne.charAt(prefixPlusOne.length() - 1) + "\': ");
+ String code = (String)cases.get(keys.elementAt(i));
+ code = code.substring(0, code.length());
+ String key = (String)keys.elementAt(i);
+ out.print("if (\""+key+"\".equals(ccSwitch"+enumSwitch+")) { if (true) do { " + code + " } while(false); break SUCCESS; } break; ");
+ }
+ }
+ }
+
+ private String processLine(String s, boolean deleteLineEndings) throws IOException {
+ if (deleteLineEndings && s.indexOf("//") != -1) s = s.substring(0, s.indexOf("//"));
+ String ret = "";
+ for(int i=0; i<s.length(); i++) {
+ char c = s.charAt(i);
+ if (!Character.isLetter(c) && !Character.isDigit(c) && c != '_') {
+ ret += c;
+ continue;
+ }
+ int j;
+ for(j = i; j < s.length(); j++) {
+ c = s.charAt(j);
+ if (!Character.isLetter(c) && !Character.isDigit(c) && c != '_') break;
+ }
+ String tok = s.substring(i, j);
+ Object val = replace.get(tok);
+ if (val == null) {
+ ret += tok;
+ i = j - 1;
+ } else if (val instanceof JSFunctionMacro) {
+ if (s.charAt(j) != '(') { ret += tok; i = j - 1; continue; }
+ ret += ((JSFunctionMacro)val).process(s.substring(j+1, s.indexOf(')', j)));
+ i = s.indexOf(')', j);
+ } else {
+ ret += val;
+ i = j - 1;
+ }
+ }
+ if (!deleteLineEndings) ret += "\n";
+ return ret;
+ }
+
+ private static int indexOfWS(String s) { return indexOfWS(s, 0); }
+ private static int indexOfWS(String s, int beginIndex) {
+ if (s == null || beginIndex >= s.length()) return -1;
+ for (; beginIndex < s.length(); beginIndex++) {
+ if (s.charAt(beginIndex) == ' ') return beginIndex;
+ }
+ return s.length();
+ }
+
+ private static int indexOfNotWS(String s) { return indexOfWS(s, 0); }
+ private static int indexOfNotWS(String s, int beginIndex) {
+ if (s == null || beginIndex >= s.length()) return -1;
+ for (; beginIndex < s.length(); beginIndex++) {
+ if (s.charAt(beginIndex) != ' ') return beginIndex;
+ }
+ return -1;
+ }
+
+ public class Warning {
+ protected String msg;
+ protected int line;
+
+ public Warning() { msg = ""; }
+ public Warning(String m) { msg = m; if (in != null) line = in.getLineNumber(); }
+
+ public String toString() { return "WARNING Line "+line+": "+msg; }
+ }
+
+ public class Error extends Warning {
+ public Error() { super(); }
+ public Error(String m) { super(m); }
+ public String toString() { return "ERROR Line "+line+": "+msg; }
+ }
+
+ public static class JSFunctionMacro {
+ public String unbound1 = null;
+ public String unbound2 = null;
+ public String expression = null;
+ public String process(String args) {
+ String bound1 = null;
+ String bound2 = null;
+ if (unbound2 == null) {
+ bound1 = args;
+ return replaceAll(expression, unbound1, bound1);
+ } else {
+ bound1 = args.substring(0, args.indexOf(','));
+ bound2 = args.substring(args.indexOf(',') + 1);
+ return replaceAll(replaceAll(expression, unbound1, bound1), unbound2, bound2);
+ }
+ }
+ }
+}
+
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+/** A simple synchronized queue, implemented as an array */
+public class Queue {
+
+ public Queue(int initiallength) { vec = new Object[initiallength]; }
+
+ /** The store */
+ private Object[] vec;
+
+ /** The index of the first node in the queue */
+ private int first = 0;
+
+ /** The number of elements in the queue; INVARAINT: size <= vec.length */
+ private int size = 0;
+
+ /** Grow the queue, if needed */
+ private void grow(int newlength) {
+ Object[] newvec = new Object[newlength];
+ if (first + size > vec.length) {
+ System.arraycopy(vec, first, newvec, 0, vec.length - first);
+ System.arraycopy(vec, 0, newvec, vec.length - first, size - (vec.length - first));
+ } else {
+ System.arraycopy(vec, first, newvec, 0, size);
+ }
+ first = 0;
+ vec = newvec;
+ }
+
+ /** The number of elements in the queue */
+ public int size() { return size; }
+
+ /** Empties the queue */
+ public synchronized void flush() {
+ first = 0;
+ size = 0;
+ for(int i=0; i<vec.length; i++) vec[i] = null;
+ }
+
+ /** Add an element to the front of the queue */
+ public synchronized void prepend(Object o) {
+ if (size == vec.length) grow(vec.length * 2);
+ first--;
+ if (first < 0) first += vec.length;
+ vec[first] = o;
+ size++;
+ if (size == 1) notify();
+ }
+
+ /** Add an element to the back of the queue */
+ public synchronized void append(Object o) {
+ if (size == vec.length) grow(vec.length * 2);
+ if (first + size >= vec.length) vec[first + size - vec.length] = o;
+ else vec[first + size] = o;
+ size++;
+ if (size == 1) notify();
+ }
+
+ /** Remove and return and element from the queue, blocking if empty. */
+ public Object remove() { return remove(true); }
+
+ /** Remove and return an element from the queue, blocking if
+ <tt>block</tt> is true and the queue is empty. */
+ public synchronized Object remove(boolean block) {
+
+ while (size == 0 && block) {
+ try { wait(); } catch (InterruptedException e) { }
+ }
+
+ if (!block && size == 0) return null;
+ Object ret = vec[first];
+ first++;
+ size--;
+ if (first >= vec.length) first = 0;
+ return ret;
+ }
+
+ /** Returns the top element in the queue without removing it */
+ public synchronized Object peek() {
+ if (size == 0) return null;
+ return vec[first];
+ }
+
+}
--- /dev/null
+// Copyright 2004 Adam Megacz, see the COPYING file for licensing [GPL]
+package org.ibex.util;
+
+import java.io.IOException;
+
+import org.ibex.js.*;
+import org.ibex.util.*;
+import org.ibex.graphics.*;
+import org.ibex.plat.*;
+
+/** Implements cooperative multitasking */
+public class Scheduler {
+
+ // Public API Exposed to org.ibex /////////////////////////////////////////////////
+
+ private static Scheduler singleton;
+ public static void add(Task t) { Log.debug(Scheduler.class, "scheduling " + t); Scheduler.runnable.append(t); }
+ public static void init() { if (singleton == null) (singleton = Platform.getScheduler()).run(); }
+
+ private static Task current = null;
+
+ private static volatile boolean rendering = false;
+ private static volatile boolean again = false;
+
+ /** synchronizd so that we can safely call it from an event-delivery thread, in-context */
+ public static void renderAll() {
+ if (rendering) { again = true; return; }
+ synchronized(Scheduler.class) {
+ try {
+ rendering = true;
+ do {
+ // FEATURE: this could be cleaner
+ again = false;
+ for(int i=0; i<Surface.allSurfaces.size(); i++) {
+ Surface s = ((Surface)Surface.allSurfaces.elementAt(i));
+ do { s.render(); } while(s.abort);
+ }
+ } while(again);
+ } finally {
+ rendering = false;
+ }
+ }
+ }
+
+
+
+ // API which must be supported by subclasses /////////////////////////////////////
+
+ /**
+ * SCHEDULER INVARIANT: all scheduler implementations MUST invoke
+ * Surface.renderAll() after performing a Task if no tasks remain
+ * in the queue. A scheduler may choose to invoke
+ * Surface.renderAll() more often than that if it so chooses.
+ */
+ public void run() { defaultRun(); }
+ public Scheduler() { }
+
+
+ // Default Implementation //////////////////////////////////////////////////////
+
+ protected static Queue runnable = new Queue(50);
+ public void defaultRun() {
+ while(true) {
+ current = (Task)runnable.remove(true);
+ try {
+ // FIXME hideous
+ synchronized(this) {
+ for(int i=0; i<Surface.allSurfaces.size(); i++) {
+ Surface s = (Surface)Surface.allSurfaces.elementAt(i);
+ if (current instanceof JS) {
+ s._mousex = Integer.MAX_VALUE;
+ s._mousey = Integer.MAX_VALUE;
+ } else {
+ s._mousex = s.mousex;
+ s._mousey = s.mousey;
+ }
+ }
+ Log.debug(Scheduler.class, "performing " + current);
+ current.perform();
+ }
+ renderAll();
+ } catch (JSExn e) {
+ Log.info(Scheduler.class, "a JavaScript thread spawned with ibex.thread() threw an exception:");
+ Log.info(Scheduler.class,e);
+ } catch (Exception e) {
+ Log.info(Scheduler.class, "a Task threw an exception which was caught by the scheduler:");
+ Log.info(Scheduler.class, e);
+ } catch (Throwable t) {
+ t.printStackTrace();
+ }
+ // if an Error is thrown it will cause the engine to quit
+ }
+ }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+/** Simple implementation of a blocking, counting semaphore. */
+public class Semaphore {
+
+ private int val = 0;
+
+ /** Decrement the counter, blocking if zero. */
+ public synchronized void block() {
+ while(val == 0) {
+ try {
+ wait();
+ } catch (InterruptedException e) {
+ } catch (Throwable e) {
+ if (Log.on) Log.info(this, "Exception in Semaphore.block(); this should never happen");
+ if (Log.on) Log.info(this, e);
+ }
+ }
+ val--;
+ }
+
+ /** Incremenet the counter. */
+ public synchronized void release() {
+ val++;
+ notify();
+ }
+
+}
--- /dev/null
+package org.ibex.util;
+import java.io.* ;
+import java.util.* ;
+
+public class Simplex {
+
+ public final static short FAIL = -1;
+
+ public final static short NULL = 0;
+ public final static short FALSE = 0;
+ public final static short TRUE = 1;
+
+ public final static short DEFNUMINV = 50;
+
+ /* solve status values */
+ public final static short OPTIMAL = 0;
+ public final static short MILP_FAIL = 1;
+ public final static short INFEASIBLE = 2;
+ public final static short UNBOUNDED = 3;
+ public final static short FAILURE = 4;
+ public final static short RUNNING = 5;
+
+ /* lag_solve extra status values */
+ public final static short FEAS_FOUND = 6;
+ public final static short NO_FEAS_FOUND = 7;
+ public final static short BREAK_BB = 8;
+
+ public final static short FIRST_NI = 0;
+ public final static short RAND_NI = 1;
+
+ public final static short LE = 0;
+ public final static short EQ = 1;
+ public final static short GE = 2;
+ public final static short OF = 3;
+
+ public final static short MAX_WARN_COUNT = 20;
+
+ public final static float DEF_INFINITE = (float)1e24; /* limit for dynamic range */
+ public final static float DEF_EPSB = (float)5.01e-7; /* for rounding RHS values to 0 determine
+ infeasibility basis */
+ public final static float DEF_EPSEL = (float)1e-8; /* for rounding other values (vectors) to 0 */
+ public final static float DEF_EPSD = (float)1e-6; /* for rounding reduced costs to zero */
+ public final static float DEF_EPSILON = (float)1e-3; /* to determine if a float value is integer */
+
+ public final static float PREJ = (float)1e-3; /* pivot reject (try others first) */
+
+ public final static int ETA_START_SIZE = 10000; /* start size of array Eta. Realloced if needed */
+
+ static class Ref {
+ float value;
+ public Ref(float v) { value = v; }
+ }
+
+ //public static class Simplex {
+ /* Globals used by solver */
+ short JustInverted;
+ short Status;
+ short Doiter;
+ short DoInvert;
+ short Break_bb;
+
+ public short active; /*TRUE if the globals point to this structure*/
+ public short debug; /* ## Print B&B information */
+ public short trace; /* ## Print information on pivot selection */
+ public int rows; /* Nr of constraint rows in the problem */
+ int rows_alloc; /* The allocated memory for Rows sized data */
+ int columns_alloc;
+ int sum; /* The size of the variables + the slacks */
+ int sum_alloc;
+ int non_zeros; /* The number of elements in the sparce matrix*/
+ int mat_alloc; /* The allocated size for matrix sized
+ structures */
+ MatrixArray mat; /* mat_alloc :The sparse matrix */
+ MatrixArray alternate_mat; /* mat_alloc :The sparse matrix */
+ int[] col_end; /* columns_alloc+1 :Cend[i] is the index of the
+ first element after column i.
+ column[i] is stored in elements
+ col_end[i-1] to col_end[i]-1 */
+ int[] col_no; /* mat_alloc :From Row 1 on, col_no contains the
+ column nr. of the
+ nonzero elements, row by row */
+ short row_end_valid; /* true if row_end & col_no are valid */
+ int[] row_end; /* rows_alloc+1 :row_end[i] is the index of the
+ first element in Colno after row i */
+ float[] orig_rh; /* rows_alloc+1 :The RHS after scaling & sign
+ changing, but before `Bound transformation' */
+ float[] rh; /* rows_alloc+1 :As orig_rh, but after Bound
+ transformation */
+ float[] rhs; /* rows_alloc+1 :The RHS of the curent simplex
+ tableau */
+ float[] orig_upbo; /* sum_alloc+1 :Bound before transformations */
+ float[] orig_lowbo; /* " " */
+ float[] upbo; /* " " :Upper bound after transformation
+ & B&B work*/
+ float[] lowbo; /* " " :Lower bound after transformation
+ & B&B work */
+
+ short basis_valid; /* TRUE is the basis is still valid */
+ int[] bas; /* rows_alloc+1 :The basis column list */
+ short[] basis; /* sum_alloc+1 : basis[i] is TRUE if the column
+ is in the basis */
+ short[] lower; /* " " :TRUE is the variable is at its
+ lower bound (or in the basis), it is FALSE
+ if the variable is at its upper bound */
+
+ short eta_valid; /* TRUE if current Eta structures are valid */
+ int eta_alloc; /* The allocated memory for Eta */
+ int eta_size; /* The number of Eta columns */
+ int num_inv; /* The number of float pivots */
+ int max_num_inv; /* ## The number of float pivots between
+ reinvertions */
+ float[] eta_value; /* eta_alloc :The Structure containing the
+ values of Eta */
+ int[] eta_row_nr; /* " " :The Structure containing the Row
+ indexes of Eta */
+ int[] eta_col_end; /* rows_alloc + MaxNumInv : eta_col_end[i] is
+ the start index of the next Eta column */
+
+ short bb_rule; /* what rule for selecting B&B variables */
+
+ short break_at_int; /* TRUE if stop at first integer better than
+ break_value */
+ float break_value;
+
+ float obj_bound; /* ## Objective function bound for speedup of
+ B&B */
+ int iter; /* The number of iterations in the simplex
+ solver () */
+ int total_iter; /* The total number of iterations (B&B) (ILP)*/
+ int max_level; /* The Deepest B&B level of the last solution */
+ int total_nodes; /* total number of nodes processed in b&b */
+ public float[] solution; /* sum_alloc+1 :The Solution of the last LP,
+ 0 = The Optimal Value,
+ 1..rows The Slacks,
+ rows+1..sum The Variables */
+ public float[] best_solution; /* " " :The Best 'Integer' Solution */
+ float[] duals; /* rows_alloc+1 :The dual variables of the
+ last LP */
+
+ short maximise; /* TRUE if the goal is to maximise the
+ objective function */
+ short floor_first; /* TRUE if B&B does floor bound first */
+ short[] ch_sign; /* rows_alloc+1 :TRUE if the Row in the matrix
+ has changed sign
+ (a`x > b, x>=0) is translated to
+ s + -a`x = -b with x>=0, s>=0) */
+
+ int nr_lagrange; /* Nr. of Langrangian relaxation constraints */
+ float[][]lag_row; /* NumLagrange, columns+1:Pointer to pointer of
+ rows */
+ float[] lag_rhs; /* NumLagrange :Pointer to pointer of Rhs */
+ float[] lambda; /* NumLagrange :Lambda Values */
+ short[] lag_con_type; /* NumLagrange :TRUE if constraint type EQ */
+ float lag_bound; /* the lagrangian lower bound */
+
+ short valid; /* Has this lp pased the 'test' */
+ float infinite; /* ## numercal stuff */
+ float epsilon; /* ## */
+ float epsb; /* ## */
+ float epsd; /* ## */
+ float epsel; /* ## */
+
+ int Rows;
+ int columns;
+ int Sum;
+ int Non_zeros;
+ int Level;
+ MatrixArray Mat;
+ int[] Col_no;
+ int[] Col_end;
+ int[] Row_end;
+ float[] Orig_rh;
+ float[] Rh;
+ float[] Rhs;
+ float[] Orig_upbo;
+ float[] Orig_lowbo;
+ float[] Upbo;
+ float[] Lowbo;
+ int[] Bas;
+ short[] Basis;
+ short[] Lower;
+ int Eta_alloc;
+ int Eta_size;
+ float[] Eta_value;
+ int[] Eta_row_nr;
+ int[] Eta_col_end;
+ int Num_inv;
+ float[] Solution;
+ public float[] Best_solution;
+ float Infinite;
+ float Epsilon;
+ float Epsb;
+ float Epsd;
+ float Epsel;
+
+ float TREJ;
+ float TINV;
+
+ short Maximise;
+ short Floor_first;
+ float Extrad;
+
+ int Warn_count; /* used in CHECK version of rounding macro */
+
+ public Simplex (int nrows, int ncolumns, int matalloc) {
+ int nsum;
+ nsum=nrows+ncolumns;
+ rows=nrows;
+ columns=ncolumns;
+ sum=nsum;
+ rows_alloc=rows;
+ columns_alloc=columns;
+ sum_alloc=sum;
+ mat_alloc=matalloc;
+ eta_alloc=10000;
+ max_num_inv=DEFNUMINV;
+ col_no = new int[mat_alloc];
+ col_end = new int[columns + 1];
+ row_end = new int[rows + 1];
+ orig_rh = new float[rows + 1];
+ rh = new float[rows + 1];
+ rhs = new float[rows + 1];
+ orig_upbo = new float[sum + 1];
+ upbo = new float[sum + 1];
+ orig_lowbo = new float[sum + 1];
+ lowbo = new float[sum + 1];
+ bas = new int[rows+1];
+ basis = new short[sum + 1];
+ lower = new short[sum + 1];
+ eta_value = new float[eta_alloc];
+ eta_row_nr = new int[eta_alloc];
+ eta_col_end = new int[rows_alloc + max_num_inv];
+ solution = new float[sum + 1];
+ best_solution = new float[sum + 1];
+ duals = new float[rows + 1];
+ ch_sign = new short[rows + 1];
+ mat = new MatrixArray(mat_alloc);
+ alternate_mat = new MatrixArray(mat_alloc);
+ }
+
+ public void init(int ncolumns) {
+ int nsum;
+ int nrows = 0;
+ nsum=nrows+ncolumns;
+ active=FALSE;
+ debug=FALSE;
+ trace=FALSE;
+ rows=nrows;
+ columns=ncolumns;
+ sum=nsum;
+ obj_bound=DEF_INFINITE;
+ infinite=DEF_INFINITE;
+ epsilon=DEF_EPSILON;
+ epsb=DEF_EPSB;
+ epsd=DEF_EPSD;
+ epsel=DEF_EPSEL;
+ non_zeros=0;
+
+ for(int i = 0; i < col_end.length; i++) col_end[i] = 0;
+ for(int i = 0; i < rows + 1; i++) row_end[i] = 0;
+ for(int i = 0; i < rows + 1; i++) orig_rh[i] = 0;
+ for(int i = 0; i < rows + 1; i++) rh[i] = 0;
+ for(int i = 0; i < rows + 1; i++) rhs[i] = 0;
+ for(int i = 0; i <= sum; i++) orig_upbo[i]=infinite;
+ for(int i = 0; i < sum + 1; i++) upbo[i] = 0;
+ for(int i = 0; i < sum + 1; i++) orig_lowbo[i] = 0;
+ for(int i = 0; i < sum + 1; i++) lowbo[i] = 0;
+ for(int i = 0; i <= rows; i++) bas[i] = 0;
+ for(int i = 0; i <= sum; i++) basis[i] = 0;
+ for(int i = 0; i <= rows; i++) { bas[i]=i; basis[i]=TRUE; }
+ for(int i = rows + 1; i <= sum; i++) basis[i]=FALSE;
+ for(int i = 0 ; i <= sum; i++) lower[i]=TRUE;
+ for(int i = 0; i <= sum; i++) solution[i] = 0;
+ for(int i = 0; i <= sum; i++) best_solution[i] = 0;
+ for(int i = 0; i <= rows; i++) duals[i] = 0;
+ for(int i = 0; i <= rows; i++) ch_sign[i] = FALSE;
+
+ row_end_valid=FALSE;
+ bb_rule=FIRST_NI;
+ break_at_int=FALSE;
+ break_value=0;
+ iter=0;
+ total_iter=0;
+ basis_valid=TRUE;
+ eta_valid=TRUE;
+ eta_size=0;
+ nr_lagrange=0;
+ maximise = FALSE;
+ floor_first = TRUE;
+ valid = FALSE;
+ }
+
+ public void setObjective(float[] row, boolean maximize) {
+ for(int i=row.length-1; i>0; i--) row[i] = row[i-1];
+ row[0] = (float)0.0;
+ for(int j = 1; j <= columns; j++) {
+ int Row = 0;
+ int column = j;
+ float Value = row[j];
+ int elmnr, lastelm;
+
+ if(Row > rows || Row < 0) throw new Error("row out of range");
+ if(column > columns || column < 1) throw new Error("column out of range");
+
+ if (basis[column] == TRUE && Row > 0) basis_valid = FALSE;
+ eta_valid = FALSE;
+ elmnr = col_end[column-1];
+ while((elmnr < col_end[column]) ? (get_row_nr(mat, elmnr) != Row) : false) elmnr++;
+ if((elmnr != col_end[column]) ? (get_row_nr(mat, elmnr) == Row) : false ) {
+ if (ch_sign[Row] != FALSE) set_value(mat, elmnr, -Value);
+ else set_value(mat, elmnr, Value);
+ } else {
+ /* check if more space is needed for matrix */
+ if (non_zeros + 1 > mat_alloc) throw new Error("not enough mat space; this should not happen");
+ /* Shift the matrix */
+ lastelm=non_zeros;
+ for(int i = lastelm; i > elmnr ; i--) {
+ set_row_nr(mat,i,get_row_nr(mat,i-1));
+ set_value(mat,i,get_value(mat,i-1));
+ }
+ for(int i = column; i <= columns; i++) col_end[i]++;
+ /* Set new element */
+ set_row_nr(mat,elmnr, Row);
+ if (ch_sign[Row] != FALSE) set_value(mat, elmnr, -Value);
+ else set_value(mat, elmnr, Value);
+ row_end_valid=FALSE;
+ non_zeros++;
+ if (active != FALSE) Non_zeros=non_zeros;
+ }
+ }
+ if (maximize) {
+ if (maximise == FALSE) {
+ for(int i = 0; i < non_zeros; i++)
+ if(get_row_nr(mat, i)==0)
+ set_value(mat, i, get_value(mat,i)* (float)-1.0);
+ eta_valid=FALSE;
+ }
+ maximise=TRUE;
+ ch_sign[0]=TRUE;
+ if (active != FALSE) Maximise=TRUE;
+ } else {
+ if (maximise==TRUE) {
+ for(int i = 0; i < non_zeros; i++)
+ if(get_row_nr(mat, i)==0)
+ set_value(mat, i, get_value(mat,i) * (float)-1.0);
+ eta_valid=FALSE;
+ }
+ maximise=FALSE;
+ ch_sign[0]=FALSE;
+ if (active != FALSE) Maximise=FALSE;
+ }
+ }
+
+ public void add_constraint(float[] row, short constr_type, float rh) {
+ for(int i=row.length-1; i>0; i--) row[i] = row[i-1];
+ row[0] = (float)0.0;
+
+ MatrixArray newmat;
+ int elmnr;
+ int stcol;
+
+ newmat = alternate_mat;
+ for(int i = 0; i < non_zeros; i++) { set_row_nr(newmat,i, 0); set_value(newmat, i, 0); }
+ for(int i = 1; i <= columns; i++) if (row[i]!=0) non_zeros++;
+ if (non_zeros > mat_alloc) throw new Error("not enough mat space; this should not happen");
+ rows++;
+ sum++;
+ if(rows > rows_alloc) throw new Error("not enough rows; this should never happen");
+ if(constr_type==GE) ch_sign[rows] = TRUE;
+ else ch_sign[rows] = FALSE;
+
+ elmnr = 0;
+ stcol = 0;
+ for(int i = 1; i <= columns; i++) {
+ for(int j = stcol; j < col_end[i]; j++) {
+ set_row_nr(newmat,elmnr, get_row_nr(mat, j));
+ set_value(newmat, elmnr, get_value(mat,j));
+ elmnr++;
+ }
+ if(((i>=1 && i< columns && row[i]!=0)?TRUE:FALSE) != FALSE) {
+ if(ch_sign[rows] != FALSE) set_value(newmat, elmnr, -row[i]);
+ else set_value(newmat, elmnr, row[i]);
+ set_row_nr(newmat,elmnr, rows);
+ elmnr++;
+ }
+ stcol=col_end[i];
+ col_end[i]=elmnr;
+ }
+
+ alternate_mat = mat;
+ mat = newmat;
+
+ for(int i = sum ; i > rows; i--) {
+ orig_upbo[i]=orig_upbo[i-1];
+ orig_lowbo[i]=orig_lowbo[i-1];
+ basis[i]=basis[i-1];
+ lower[i]=lower[i-1];
+ }
+
+ for(int i = 1 ; i <= rows; i++) if(bas[i] >= rows) bas[i]++;
+
+ if(constr_type==LE || constr_type==GE) orig_upbo[rows]=infinite;
+ else if(constr_type==EQ) orig_upbo[rows]=0;
+ else throw new Error("Wrong constraint type\n");
+ orig_lowbo[rows]=0;
+
+ if(constr_type==GE && rh != 0) orig_rh[rows]=-rh;
+ else orig_rh[rows]=rh;
+
+ row_end_valid=FALSE;
+
+ bas[rows]=rows;
+ basis[rows]=TRUE;
+ lower[rows]=TRUE;
+
+ if (active != FALSE) set_globals();
+ eta_valid=FALSE;
+ }
+
+ public void bound_sum(int column1, int column2, float bound, short type, float[] scratch) {
+ for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
+ scratch[column1] = (float)1.0;
+ scratch[column2] = (float)1.0;
+ add_constraint(scratch, type, bound);
+ for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
+ }
+
+ public void bound_difference(int column1, int column2, float bound, short type, float[] scratch) {
+ for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
+ scratch[column1] = (float)1.0;
+ scratch[column2] = (float)-1.0;
+ add_constraint(scratch, type, bound);
+ for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
+ }
+
+ public void set_upbo(int column, float value) {
+ if(column > columns || column < 1) throw new Error("column out of range");
+ if(value < orig_lowbo[rows + column]) throw new Error("UpperBound must be >= lowerBound");
+ eta_valid = FALSE;
+ orig_upbo[rows+column] = value;
+ }
+
+ public void set_lowbo(int column, float value) {
+ if(column > columns || column < 1) throw new Error("column out of range");
+ if(value > orig_upbo[rows + column]) throw new Error("UpperBound must be >= lowerBound");
+ eta_valid = FALSE;
+ orig_lowbo[rows+column] = value;
+ }
+
+ public void set_rh(int row, float value) {
+ if(row > rows || row < 0) throw new Error("Row out of Range");
+ if(row == 0) throw new Error("Warning: attempt to set RHS of objective function, ignored");
+ if (ch_sign[row] != FALSE) orig_rh[row] = -value;
+ else orig_rh[row] = value;
+ eta_valid = FALSE;
+ }
+
+ public void set_rh_vec(float[] rh) {
+ for(int i=1; i <= rows; i++)
+ if (ch_sign[i] != FALSE) orig_rh[i]=-rh[i];
+ else orig_rh[i]=rh[i];
+ eta_valid=FALSE;
+ }
+
+
+ public void set_constr_type(int row, short con_type) {
+ if (row > rows || row < 1) throw new Error("Row out of Range");
+ switch(con_type) {
+ case EQ:
+ orig_upbo[row]=0;
+ basis_valid=FALSE;
+ if (ch_sign[row] != FALSE) {
+ for(int i = 0; i < non_zeros; i++)
+ if (get_row_nr(mat, i)==row) set_value(mat, i, get_value(mat,i) * (float)-1);
+ eta_valid=FALSE;
+ ch_sign[row]=FALSE;
+ if (orig_rh[row]!=0) orig_rh[row]*=-1;
+ }
+ break;
+ case LE:
+ orig_upbo[row]=infinite;
+ basis_valid=FALSE;
+ if (ch_sign[row] != FALSE) {
+ for(int i = 0; i < non_zeros; i++)
+ if (get_row_nr(mat, i)==row) set_value(mat, i, get_value(mat,i) * (float)-1);
+ eta_valid=FALSE;
+ ch_sign[row]=FALSE;
+ if (orig_rh[row]!=0) orig_rh[row]*=-1;
+ }
+ break;
+ case GE:
+ orig_upbo[row]=infinite;
+ basis_valid=FALSE;
+ if (ch_sign[row] == FALSE) {
+ for(int i = 0; i < non_zeros; i++)
+ if (get_row_nr(mat, i)==row) set_value(mat, i, get_value(mat,i) * (float)-1);
+ eta_valid=FALSE;
+ ch_sign[row]=TRUE;
+ if (orig_rh[row]!=0) orig_rh[row]*=-1;
+ }
+ break;
+ default: throw new Error("Constraint type not (yet) implemented");
+ }
+ }
+
+ void set_globals() {
+ Rows = rows;
+ columns = columns;
+ Sum = Rows + columns;
+ Non_zeros = non_zeros;
+ Mat = mat;
+ Col_no = col_no;
+ Col_end = col_end;
+ Row_end = row_end;
+ Rh = rh;
+ Rhs = rhs;
+ Orig_rh = orig_rh;
+ Orig_upbo = orig_upbo;
+ Orig_lowbo = orig_lowbo;
+ Upbo = upbo;
+ Lowbo = lowbo;
+ Bas = bas;
+ Basis = basis;
+ Lower = lower;
+ Eta_alloc = eta_alloc;
+ Eta_size = eta_size;
+ Num_inv = num_inv;
+ Eta_value = eta_value;
+ Eta_row_nr = eta_row_nr;
+ Eta_col_end = eta_col_end;
+ Solution = solution;
+ Best_solution = best_solution;
+ Infinite = infinite;
+ Epsilon = epsilon;
+ Epsb = epsb;
+ Epsd = epsd;
+ Epsel = epsel;
+ TREJ = TREJ;
+ TINV = TINV;
+ Maximise = maximise;
+ Floor_first = floor_first;
+ active = TRUE;
+ }
+
+ private void ftran(int start, int end, float[] pcol) {
+ int k, r;
+ float theta;
+ for(int i = start; i <= end; i++) {
+ k = Eta_col_end[i] - 1;
+ r = Eta_row_nr[k];
+ theta = pcol[r];
+ if (theta != 0) for(int j = Eta_col_end[i - 1]; j < k; j++)
+ pcol[Eta_row_nr[j]] += theta * Eta_value[j];
+ pcol[r] *= Eta_value[k];
+ }
+ for(int i = 0; i <= Rows; i++) round(pcol[i], Epsel);
+ }
+
+ private void btran(float[] row) {
+ int k;
+ float f;
+ for(int i = Eta_size; i >= 1; i--) {
+ f = 0;
+ k = Eta_col_end[i] - 1;
+ for(int j = Eta_col_end[i - 1]; j <= k; j++) f += row[Eta_row_nr[j]] * Eta_value[j];
+ f = round(f, Epsel);
+ row[Eta_row_nr[k]] = f;
+ }
+ }
+
+ static int[] num = new int[65535];
+ static int[] rownum = new int[65535];
+ static int[] colnum = new int[65535];
+
+ short Isvalid() {
+ int row_nr;
+ if (row_end_valid == FALSE) {
+ for(int i = 0; i <= rows; i++) { num[i] = 0; rownum[i] = 0; }
+ for(int i = 0; i < non_zeros; i++) rownum[get_row_nr(mat, i)]++;
+ row_end[0] = 0;
+ for(int i = 1; i <= rows; i++) row_end[i] = row_end[i - 1] + rownum[i];
+ for(int i = 1; i <= columns; i++)
+ for(int j = col_end[i - 1]; j < col_end[i]; j++) {
+ row_nr = get_row_nr(mat, j);
+ if (row_nr != 0) {
+ num[row_nr]++;
+ col_no[row_end[row_nr - 1] + num[row_nr]] = i;
+ }
+ }
+ row_end_valid = TRUE;
+ }
+ if (valid != FALSE) return(TRUE);
+ for(int i = 0; i <= rows; i++) rownum[i] = 0;
+ for(int i = 0; i <= columns; i++) colnum[i] = 0;
+ for(int i = 1 ; i <= columns; i++)
+ for(int j = col_end[i - 1]; j < col_end[i]; j++) {
+ colnum[i]++;
+ rownum[get_row_nr(mat, j)]++;
+ }
+ for(int i = 1; i <= columns; i++)
+ if (colnum[i] == 0)
+ throw new Error("Warning: Variable " + i + " not used in any constaints\n");
+ valid = TRUE;
+ return(TRUE);
+ }
+
+ private void resize_eta() {
+ Eta_alloc *= 2;
+ throw new Error("eta undersized; this should never happen");
+ /*
+ float[] db_ptr = Eta_value;
+ Eta_value = new float[Eta_alloc];
+ System.arraycopy(db_ptr, 0, Eta_value, 0, db_ptr.length);
+ eta_value = Eta_value;
+
+ int[] int_ptr = Eta_row_nr;
+ Eta_row_nr = new int[Eta_alloc];
+ System.arraycopy(int_ptr, 0, Eta_row_nr, 0, int_ptr.length);
+ eta_row_nr = Eta_row_nr;
+ */
+ }
+
+ private void condensecol(int row_nr, float[] pcol) {
+ int elnr;
+ elnr = Eta_col_end[Eta_size];
+ if (elnr + Rows + 2 > Eta_alloc) resize_eta();
+ for(int i = 0; i <= Rows; i++)
+ if (i != row_nr && pcol[i] != 0) {
+ Eta_row_nr[elnr] = i;
+ Eta_value[elnr] = pcol[i];
+ elnr++;
+ }
+ Eta_row_nr[elnr] = row_nr;
+ Eta_value[elnr] = pcol[row_nr];
+ elnr++;
+ Eta_col_end[Eta_size + 1] = elnr;
+ }
+
+ private void addetacol() {
+ int k;
+ float theta;
+ int j = Eta_col_end[Eta_size];
+ Eta_size++;
+ k = Eta_col_end[Eta_size];
+ theta = 1 / (float) Eta_value[k - 1];
+ Eta_value[k - 1] = theta;
+ for(int i = j; i < k - 1; i++) Eta_value[i] *= -theta;
+ JustInverted = FALSE;
+ }
+
+ private void setpivcol(short lower, int varin, float[] pcol) {
+ int colnr;
+ float f;
+ if (lower != FALSE) f = 1;
+ else f = -1;
+ for(int i = 0; i <= Rows; i++) pcol[i] = 0;
+ if (varin > Rows) {
+ colnr = varin - Rows;
+ for(int i = Col_end[colnr - 1]; i < Col_end[colnr]; i++) pcol[get_row_nr(Mat, i)] = get_value(Mat,i) * f;
+ pcol[0] -= Extrad * f;
+ } else {
+ if (lower != FALSE) pcol[varin] = 1;
+ else pcol[varin] = -1;
+ }
+ ftran(1, Eta_size, pcol);
+ }
+
+ private void minoriteration(int colnr, int row_nr) {
+ int k, wk, varin, varout, elnr;
+ float piv = 0, theta;
+ varin = colnr + Rows;
+ elnr = Eta_col_end[Eta_size];
+ wk = elnr;
+ Eta_size++;
+ if (Extrad != 0) {
+ Eta_row_nr[elnr] = 0;
+ Eta_value[elnr] = -Extrad;
+ elnr++;
+ }
+ for(int j = Col_end[colnr - 1] ; j < Col_end[colnr]; j++) {
+ k = get_row_nr(Mat, j);
+ if (k == 0 && Extrad != 0) Eta_value[Eta_col_end[Eta_size -1]] += get_value(Mat,j);
+ else if (k != row_nr) {
+ Eta_row_nr[elnr] = k;
+ Eta_value[elnr] = get_value(Mat,j);
+ elnr++;
+ } else {
+ piv = get_value(Mat,j);
+ }
+ }
+ Eta_row_nr[elnr] = row_nr;
+ Eta_value[elnr] = 1 / (float) piv;
+ elnr++;
+ theta = Rhs[row_nr] / (float) piv;
+ Rhs[row_nr] = theta;
+ for(int i = wk; i < elnr - 1; i++) Rhs[Eta_row_nr[i]] -= theta * Eta_value[i];
+ varout = Bas[row_nr];
+ Bas[row_nr] = varin;
+ Basis[varout] = FALSE;
+ Basis[varin] = TRUE;
+ for(int i = wk; i < elnr - 1; i++) Eta_value[i] /= - (float) piv;
+ Eta_col_end[Eta_size] = elnr;
+ }
+
+ private void rhsmincol(float theta, int row_nr, int varin) {
+ int varout;
+ float f;
+ if (row_nr > Rows + 1) {
+ System.err.println("Error: rhsmincol called with row_nr: " + row_nr + ", rows: " + Rows + "\n");
+ System.err.println("This indicates numerical instability\n");
+ }
+ int j = Eta_col_end[Eta_size];
+ int k = Eta_col_end[Eta_size + 1];
+ for(int i = j; i < k; i++) {
+ f = Rhs[Eta_row_nr[i]] - theta * Eta_value[i];
+ f = round(f, Epsb);
+ Rhs[Eta_row_nr[i]] = f;
+ }
+ Rhs[row_nr] = theta;
+ varout = Bas[row_nr];
+ Bas[row_nr] = varin;
+ Basis[varout] = FALSE;
+ Basis[varin] = TRUE;
+ }
+
+ private static int[] rownum_ = new int[65535];
+ private static int[] colnum_ = new int[65535];
+ private static int[] col = new int[65535];
+ private static int[] row = new int[65535];
+ private static float[] pcol = new float[65535];
+ private static short[] frow = new short[65535];
+ private static short[] fcol = new short[65535];
+
+ void invert() {
+ int v, wk, numit, varnr, row_nr, colnr, varin;
+ float theta;
+
+ for(int i = 0; i <= Rows; i++) rownum_[i] = 0;
+ for(int i = 0; i <= Rows; i++) col[i] = 0;
+ for(int i = 0; i <= Rows; i++) row[i] = 0;
+ for(int i = 0; i <= Rows; i++) pcol[i] = 0;
+ for(int i = 0; i <= Rows; i++) frow[i] = TRUE;
+ for(int i = 0; i < columns; i++) fcol[i] = FALSE;
+ for(int i = 0; i <= columns; i++) colnum_[i] = 0;
+
+ for(int i = 0; i <= Rows; i++)
+ if (Bas[i] > Rows) fcol[Bas[i] - Rows - 1] = TRUE;
+ else frow[Bas[i]] = FALSE;
+
+ for(int i = 1; i <= Rows; i++)
+ if (frow[i] != FALSE)
+ for(int j = Row_end[i - 1] + 1; j <= Row_end[i]; j++) {
+ wk = Col_no[j];
+ if (fcol[wk - 1] != FALSE) {
+ colnum_[wk]++;
+ rownum_[i - 1]++;
+ }
+ }
+
+ for(int i = 1; i <= Rows; i++) Bas[i] = i;
+ for(int i = 1; i <= Rows; i++) Basis[i] = TRUE;
+ for(int i = 1; i <= columns; i++) Basis[i + Rows] = FALSE;
+ for(int i = 0; i <= Rows; i++) Rhs[i] = Rh[i];
+ for(int i = 1; i <= columns; i++) {
+ varnr = Rows + i;
+ if (Lower[varnr] == FALSE) {
+ theta = Upbo[varnr];
+ for(int j = Col_end[i - 1]; j < Col_end[i]; j++)
+ Rhs[get_row_nr(Mat, j)] -= theta * get_value(Mat,j);
+ }
+ }
+ for(int i = 1; i <= Rows; i++) if (Lower[i] == FALSE) Rhs[i] -= Upbo[i];
+ Eta_size = 0;
+ v = 0;
+ row_nr = 0;
+ Num_inv = 0;
+ numit = 0;
+ while(v < Rows) {
+ int j;
+ row_nr++;
+ if (row_nr > Rows) row_nr = 1;
+ v++;
+ if (rownum_[row_nr - 1] == 1)
+ if (frow[row_nr] != FALSE) {
+ v = 0;
+ j = Row_end[row_nr - 1] + 1;
+ while(fcol[Col_no[j] - 1] == FALSE) j++;
+ colnr = Col_no[j];
+ fcol[colnr - 1] = FALSE;
+ colnum_[colnr] = 0;
+ for(j = Col_end[colnr - 1]; j < Col_end[colnr]; j++)
+ if (frow[get_row_nr(Mat, j)] != FALSE)
+ rownum_[get_row_nr(Mat, j) - 1]--;
+ frow[row_nr] = FALSE;
+ minoriteration(colnr, row_nr);
+ }
+ }
+ v = 0;
+ colnr = 0;
+ while(v < columns) {
+ int j;
+ colnr++;
+ if (colnr > columns) colnr = 1;
+ v++;
+ if (colnum_[colnr] == 1)
+ if (fcol[colnr - 1] != FALSE) {
+ v = 0;
+ j = Col_end[colnr - 1] + 1;
+ while(frow[get_row_nr(Mat, j - 1)] == FALSE) j++;
+ row_nr = get_row_nr(Mat, j - 1);
+ frow[row_nr] = FALSE;
+ rownum_[row_nr - 1] = 0;
+ for(j = Row_end[row_nr - 1] + 1; j <= Row_end[row_nr]; j++)
+ if (fcol[Col_no[j] - 1] != FALSE)
+ colnum_[Col_no[j]]--;
+ fcol[colnr - 1] = FALSE;
+ numit++;
+ col[numit - 1] = colnr;
+ row[numit - 1] = row_nr;
+ }
+ }
+ for(int j = 1; j <= columns; j++)
+ if (fcol[j - 1] != FALSE) {
+ fcol[j - 1] = FALSE;
+ setpivcol(Lower[Rows + j], j + Rows, pcol);
+ row_nr = 1;
+ while((frow[row_nr] == FALSE || pcol[row_nr] == FALSE) && row_nr <= Rows)
+ row_nr++; /* this sometimes sets row_nr to Rows + 1 and makes
+ rhsmincol crash. Solved in 2.0? MB */
+ if (row_nr == Rows + 1) throw new Error("Inverting failed");
+ frow[row_nr] = FALSE;
+ condensecol(row_nr, pcol);
+ theta = Rhs[row_nr] / (float) pcol[row_nr];
+ rhsmincol(theta, row_nr, Rows + j);
+ addetacol();
+ }
+ for(int i = numit - 1; i >= 0; i--) {
+ colnr = col[i];
+ row_nr = row[i];
+ varin = colnr + Rows;
+ for(int j = 0; j <= Rows; j++) pcol[j] = 0;
+ for(int j = Col_end[colnr - 1]; j < Col_end[colnr]; j++) pcol[get_row_nr(Mat, j)] = get_value(Mat,j);
+ pcol[0] -= Extrad;
+ condensecol(row_nr, pcol);
+ theta = Rhs[row_nr] / (float) pcol[row_nr];
+ rhsmincol(theta, row_nr, varin);
+ addetacol();
+ }
+ for(int i = 1; i <= Rows; i++) Rhs[i] = round(Rhs[i], Epsb);
+ JustInverted = TRUE;
+ DoInvert = FALSE;
+ }
+
+ private short colprim(Ref colnr, short minit, float[] drow) {
+ int varnr;
+ float f, dpiv;
+ dpiv = -Epsd;
+ colnr.value = 0;
+ if (minit == FALSE) {
+ for(int i = 1; i <= Sum; i++) drow[i] = 0;
+ drow[0] = 1;
+ btran(drow);
+ for(int i = 1; i <= columns; i++) {
+ varnr = Rows + i;
+ if (Basis[varnr] == FALSE)
+ if (Upbo[varnr] > 0) {
+ f = 0;
+ for(int j = Col_end[i - 1]; j < Col_end[i]; j++) f += drow[get_row_nr(Mat, j)] * get_value(Mat,j);
+ drow[varnr] = f;
+ }
+ }
+ for(int i = 1; i <= Sum; i++) drow[i] = round(drow[i], Epsd);
+ }
+ for(int i = 1; i <= Sum; i++)
+ if (Basis[i] == FALSE)
+ if (Upbo[i] > 0) {
+ if (Lower[i] != FALSE) f = drow[i];
+ else f = -drow[i];
+ if (f < dpiv) {
+ dpiv = f;
+ colnr.value = i;
+ }
+ }
+ if (colnr.value == 0) {
+ Doiter = FALSE;
+ DoInvert = FALSE;
+ Status = OPTIMAL;
+ }
+ return(colnr.value > 0 ? (short)1 : (short)0);
+ }
+
+ private short rowprim(int colnr, Ref row_nr, Ref theta, float[] pcol) {
+ float f = 0, quot;
+ row_nr.value = 0;
+ theta.value = Infinite;
+ for(int i = 1; i <= Rows; i++) {
+ f = pcol[i];
+ if (Math.abs(f) < TREJ) f = 0;
+ if (f != 0) {
+ quot = 2 * Infinite;
+ if (f > 0) quot = Rhs[i] / (float) f;
+ else if (Upbo[Bas[i]] < Infinite) quot = (Rhs[i] - Upbo[Bas[i]]) / (float) f;
+ round(quot, Epsel);
+ if (quot < theta.value) {
+ theta.value = quot;
+ row_nr.value = i;
+ }
+ }
+ }
+ if (row_nr.value == 0)
+ for(int i = 1; i <= Rows; i++) {
+ f = pcol[i];
+ if (f != 0) {
+ quot = 2 * Infinite;
+ if (f > 0) quot = Rhs[i] / (float) f;
+ else if (Upbo[Bas[i]] < Infinite) quot = (Rhs[i] - Upbo[Bas[i]]) / (float) f;
+ quot = round(quot, Epsel);
+ if (quot < theta.value) {
+ theta.value = quot;
+ row_nr.value = i;
+ }
+ }
+ }
+
+ if (theta.value < 0) throw new Error("Warning: Numerical instability, qout = " + theta.value);
+ if (row_nr.value == 0) {
+ if (Upbo[colnr] == Infinite) {
+ Doiter = FALSE;
+ DoInvert = FALSE;
+ Status = UNBOUNDED;
+ } else {
+ int i = 1;
+ while(pcol[i] >= 0 && i <= Rows) i++;
+ if (i > Rows) {
+ Lower[colnr] = FALSE;
+ Rhs[0] += Upbo[colnr]*pcol[0];
+ Doiter = FALSE;
+ DoInvert = FALSE;
+ } else if (pcol[i]<0) {
+ row_nr.value = i;
+ }
+ }
+ }
+ if (row_nr.value > 0) Doiter = TRUE;
+ return((row_nr.value > 0) ? (short)1 : (short)0);
+ }
+
+ private short rowdual(Ref row_nr) {
+ int i;
+ float f, g, minrhs;
+ short artifs;
+ row_nr.value = 0;
+ minrhs = -Epsb;
+ i = 0;
+ artifs = FALSE;
+ while(i < Rows && artifs == FALSE) {
+ i++;
+ f = Upbo[Bas[i]];
+ if (f == 0 && (Rhs[i] != 0)) {
+ artifs = TRUE;
+ row_nr.value = i;
+ } else {
+ if (Rhs[i] < f - Rhs[i]) g = Rhs[i];
+ else g = f - Rhs[i];
+ if (g < minrhs) {
+ minrhs = g;
+ row_nr.value = i;
+ }
+ }
+ }
+ return(row_nr.value > 0 ? (short)1 : (short)0);
+ }
+
+ private short coldual(int row_nr, Ref colnr, short minit, float[] prow, float[] drow) {
+ int r, varnr;
+ float theta, quot, pivot, d, f, g;
+ Doiter = FALSE;
+ if (minit == FALSE) {
+ for(int i = 0; i <= Rows; i++) {
+ prow[i] = 0;
+ drow[i] = 0;
+ }
+ drow[0] = 1;
+ prow[row_nr] = 1;
+ for(int i = Eta_size; i >= 1; i--) {
+ d = 0;
+ f = 0;
+ r = Eta_row_nr[Eta_col_end[i] - 1];
+ for(int j = Eta_col_end[i - 1]; j < Eta_col_end[i]; j++) {
+ /* this is where the program consumes most cpu time */
+ f += prow[Eta_row_nr[j]] * Eta_value[j];
+ d += drow[Eta_row_nr[j]] * Eta_value[j];
+ }
+ f = round(f, Epsel);
+ prow[r] = f;
+ d = round(d, Epsel);
+ drow[r] = d;
+ }
+ for(int i = 1; i <= columns; i++) {
+ varnr = Rows + i;
+ if (Basis[varnr] == FALSE) {
+ d = - Extrad * drow[0];
+ f = 0;
+ for(int j = Col_end[i - 1]; j < Col_end[i]; j++) {
+ d = d + drow[get_row_nr(Mat, j)] * get_value(Mat,j);
+ f = f + prow[get_row_nr(Mat, j)] * get_value(Mat,j);
+ }
+ drow[varnr] = d;
+ prow[varnr] = f;
+ }
+ }
+ for(int i = 0; i <= Sum; i++) {
+ prow[i] = round(prow[i], Epsel);
+ drow[i] = round(drow[i], Epsd);
+ }
+ }
+ if (Rhs[row_nr] > Upbo[Bas[row_nr]]) g = -1;
+ else g = 1;
+ pivot = 0;
+ colnr.value = 0;
+ theta = Infinite;
+ for(int i = 1; i <= Sum; i++) {
+ if (Lower[i] != FALSE) d = prow[i] * g;
+ else d = -prow[i] * g;
+ if ((d < 0) && (Basis[i] == FALSE) && (Upbo[i] > 0)) {
+ if (Lower[i] == FALSE) quot = -drow[i] / (float) d;
+ else quot = drow[i] / (float) d;
+ if (quot < theta) {
+ theta = quot;
+ pivot = d;
+ colnr.value = i;
+ } else if ((quot == theta) && (Math.abs(d) > Math.abs(pivot))) {
+ pivot = d;
+ colnr.value = i;
+ }
+ }
+ }
+ if (colnr.value > 0) Doiter = TRUE;
+ return(colnr.value > 0 ? (short)1 : (short)0);
+ }
+
+ private void iteration(int row_nr, int varin, Ref theta, float up, Ref minit, Ref low, short primal,float[] pcol) {
+ int k, varout;
+ float f;
+ float pivot;
+ iter++;
+ minit.value = theta.value > (up + Epsb) ? 1 : 0;
+ if (minit.value != 0) {
+ theta.value = up;
+ low.value = low.value == 0 ? 1 : 0;
+ }
+ k = Eta_col_end[Eta_size + 1];
+ pivot = Eta_value[k - 1];
+ for(int i = Eta_col_end[Eta_size]; i < k; i++) {
+ f = Rhs[Eta_row_nr[i]] - theta.value * Eta_value[i];
+ f = round(f, Epsb);
+ Rhs[Eta_row_nr[i]] = f;
+ }
+ if (minit.value == 0) {
+ Rhs[row_nr] = theta.value;
+ varout = Bas[row_nr];
+ Bas[row_nr] = varin;
+ Basis[varout] = FALSE;
+ Basis[varin] = TRUE;
+ if (primal != FALSE && pivot < 0) Lower[varout] = FALSE;
+ if (low.value == 0 && up < Infinite) {
+ low.value = TRUE;
+ Rhs[row_nr] = up - Rhs[row_nr];
+ for(int i = Eta_col_end[Eta_size]; i < k; i++) Eta_value[i] = -Eta_value[i];
+ }
+ addetacol();
+ Num_inv++;
+ }
+ }
+
+ static float[] drow = new float[65535];
+ static float[] prow = new float[65535];
+ static float[] Pcol = new float[65535];
+
+ private int solvelp() {
+ int varnr;
+ float f = 0, theta = 0;
+ short primal;
+ short minit;
+ int colnr, row_nr;
+ colnr = 0;
+ row_nr = 0;
+ short flag;
+ Ref ref1, ref2, ref3;
+ ref1 = new Ref(0);
+ ref2 = new Ref(0);
+ ref3 = new Ref(0);
+
+ for(int i = 0; i <= Sum; i++) { drow[i] = 0; prow[i] = 0; }
+ for(int i = 0; i <= Rows; i++) Pcol[i] = 0;
+ iter = 0;
+ minit = FALSE;
+ Status = RUNNING;
+ DoInvert = FALSE;
+ Doiter = FALSE;
+ primal = TRUE;
+ for(int i = 0; i != Rows && primal != FALSE;) {
+ i++;
+ primal = (Rhs[i] >= 0 && Rhs[i] <= Upbo[Bas[i]]) ? (short)1: (short)0;
+ }
+ if (primal == FALSE) {
+ drow[0] = 1;
+ for(int i = 1; i <= Rows; i++) drow[i] = 0;
+ Extrad = 0;
+ for(int i = 1; i <= columns; i++) {
+ varnr = Rows + i;
+ drow[varnr] = 0;
+ for(int j = Col_end[i - 1]; j < Col_end[i]; j++)
+ if (drow[get_row_nr(Mat, j)] != 0)
+ drow[varnr] += drow[get_row_nr(Mat, j)] * get_value(Mat,j);
+ if (drow[varnr] < Extrad) Extrad = drow[varnr];
+ }
+ } else {
+ Extrad = 0;
+ }
+ minit = FALSE;
+ while(Status == RUNNING) {
+ Doiter = FALSE;
+ DoInvert = FALSE;
+ construct_solution(Solution);
+ if (primal != FALSE) {
+ ref1.value = colnr;
+ flag = colprim(ref1, minit, drow);
+ colnr = (int)ref1.value;
+ if (flag != FALSE) {
+ setpivcol(Lower[colnr], colnr, Pcol);
+ ref1.value = row_nr;
+ ref2.value = theta;
+ flag = rowprim(colnr, ref1, ref2, Pcol);
+ row_nr = (int)ref1.value;
+ theta = ref2.value;
+ if (flag != FALSE) condensecol(row_nr, Pcol);
+ }
+ } else {
+ if (minit == FALSE) {
+ ref1.value = row_nr;
+ flag = rowdual(ref1);
+ row_nr = (int)ref1.value;
+ }
+ if (row_nr > 0) {
+ ref1.value = colnr;
+ flag = coldual(row_nr, ref1, minit, prow, drow);
+ colnr = (int)ref1.value;
+ if (flag != FALSE) {
+ setpivcol(Lower[colnr], colnr, Pcol);
+ /* getting div by zero here ... MB */
+ if (Pcol[row_nr] == 0) {
+ throw new Error("An attempt was made to divide by zero (Pcol[" + row_nr + "])");
+ } else {
+ condensecol(row_nr, Pcol);
+ f = Rhs[row_nr] - Upbo[Bas[row_nr]];
+ if (f > 0) {
+ theta = f / (float) Pcol[row_nr];
+ if (theta <= Upbo[colnr])
+ Lower[Bas[row_nr]] = (Lower[Bas[row_nr]] == FALSE)? (short)1:(short)0;
+ } else theta = Rhs[row_nr] / (float) Pcol[row_nr];
+ }
+ } else Status = INFEASIBLE;
+ } else {
+ primal = TRUE;
+ Doiter = FALSE;
+ Extrad = 0;
+ DoInvert = TRUE;
+ }
+ }
+ if (Doiter != FALSE) {
+ ref1.value = theta;
+ ref2.value = minit;
+ ref3.value = Lower[colnr];
+ iteration(row_nr, colnr, ref1, Upbo[colnr], ref2, ref3, primal, Pcol);
+ theta = ref1.value;
+ minit = (short)ref2.value;
+ Lower[colnr] = (short)ref3.value;
+ }
+ if (Num_inv >= max_num_inv) DoInvert = TRUE;
+ if (DoInvert != FALSE) invert();
+ }
+ total_iter += iter;
+ return(Status);
+ }
+
+ private void construct_solution(float[] sol) {
+ float f;
+ int basi;
+ for(int i = 0; i <= Rows; i++) sol[i] = 0;
+ for(int i = Rows + 1; i <= Sum; i++) sol[i] = Lowbo[i];
+ for(int i = 1; i <= Rows; i++) {
+ basi = Bas[i];
+ if (basi > Rows) sol[basi] += Rhs[i];
+ }
+ for(int i = Rows + 1; i <= Sum; i++)
+ if (Basis[i] == FALSE && Lower[i] == FALSE)
+ sol[i] += Upbo[i];
+ for(int j = 1; j <= columns; j++) {
+ f = sol[Rows + j];
+ if (f != 0)
+ for(int i = Col_end[j - 1]; i < Col_end[j]; i++)
+ sol[get_row_nr(Mat, i)] += f * get_value(Mat,i);
+ }
+ for(int i = 0; i <= Rows; i++) {
+ if (Math.abs(sol[i]) < Epsb) sol[i] = 0;
+ else if (ch_sign[i] != FALSE) sol[i] = -sol[i];
+ }
+ }
+
+ private void calculate_duals() {
+ for(int i = 1; i <= Rows; i++) duals[i] = 0;
+ duals[0] = 1;
+ btran(duals);
+ for(int i = 1; i <= Rows; i++) {
+ if (basis[i] != FALSE) duals[i] = 0;
+ else if ( ch_sign[0] == ch_sign[i]) duals[i] = -duals[i];
+ }
+ }
+
+ private static Random rdm = new Random();
+
+ private int milpsolve(float[] upbo, float[] lowbo, short[] sbasis, short[] slower, int[] sbas) {
+ int failure, notint, is_worse;
+ float theta, tmpfloat;
+ notint = 0;
+
+ if (Break_bb != FALSE) return(BREAK_BB);
+ Level++;
+ total_nodes++;
+ if (Level > max_level) max_level = Level;
+ System.arraycopy(upbo, 0, Upbo, 0, Sum + 1);
+ System.arraycopy(lowbo, 0, Lowbo, 0, Sum + 1);
+ System.arraycopy(sbasis, 0, Basis, 0, Sum + 1);
+ System.arraycopy(slower, 0, Lower, 0, Sum + 1);
+ System.arraycopy(sbas, 0, Bas, 0, Rows + 1);
+ System.arraycopy(Orig_rh, 0, Rh, 0, Rows + 1);
+ if (eta_valid == FALSE) {
+ for(int i = 1; i <= columns; i++)
+ if (Lowbo[Rows + i] != 0) {
+ theta = Lowbo[ Rows + i];
+ if (Upbo[Rows + i]<Infinite) Upbo[Rows + i] -= theta;
+ for(int j = Col_end[i - 1]; j < Col_end[i]; j++) Rh[get_row_nr(Mat, j)] -= theta * get_value(Mat,j);
+ }
+ invert();
+ eta_valid = TRUE;
+ }
+ failure = solvelp();
+ if (failure == OPTIMAL) {
+ construct_solution(Solution);
+ /* if this solution is worse than the best sofar, this branch must die */
+ if (Maximise != FALSE) is_worse = (Solution[0] <= Best_solution[0]) ? 1:0;
+ else is_worse = (Solution[0] >= Best_solution[0]) ? 1:0;
+ if (is_worse != FALSE) {
+ Level--;
+ return(MILP_FAIL);
+ }
+ /* check if solution contains enough ints */
+ if (bb_rule == FIRST_NI) {
+ notint = 0;
+ int i = Rows + 1;
+ while(i <= Sum && notint == 0) i++;
+ }
+ if (bb_rule == RAND_NI) {
+ int nr_not_int, select_not_int;
+ nr_not_int = 0;
+ for(int i = Rows + 1; i <= Sum; i++)
+ if (nr_not_int == 0) notint = 0;
+ else {
+ select_not_int=(rdm.nextInt() % nr_not_int) + 1;
+ i = Rows + 1;
+ while(select_not_int > 0) i++;
+ notint = i - 1;
+ }
+ }
+ if (notint != FALSE) throw new Error("integer linear programming not supported");
+ if (Maximise != FALSE) is_worse = (Solution[0] < Best_solution[0]) ? 1:0;
+ else is_worse = (Solution[0] > Best_solution[0]) ? 1:0;
+ if (is_worse == FALSE) {
+ System.arraycopy(Solution, 0, Best_solution, 0, Sum + 1);
+ calculate_duals();
+ if (break_at_int != FALSE) {
+ if (Maximise != FALSE && (Best_solution[0] > break_value)) Break_bb = TRUE;
+ if (Maximise == FALSE && (Best_solution[0] < break_value)) Break_bb = TRUE;
+ }
+ }
+ }
+ Level--;
+ return(failure);
+ }
+
+ public int solve() {
+ int result = FAILURE;
+ if (active == FALSE) set_globals();
+ total_iter = 0;
+ max_level = 1;
+ total_nodes = 0;
+ if (Isvalid() != FALSE) {
+ if (Maximise != FALSE && obj_bound == Infinite) Best_solution[0]=-Infinite;
+ else if (Maximise == FALSE && obj_bound==-Infinite) Best_solution[0] = Infinite;
+ else Best_solution[0] = obj_bound;
+ Level = 0;
+ if (basis_valid == FALSE) {
+ for(int i = 0; i <= rows; i++) {
+ basis[i] = TRUE;
+ bas[i] = i;
+ }
+ for(int i = rows+1; i <= sum; i++) basis[i] = FALSE;
+ for(int i = 0; i <= sum; i++) lower[i] = TRUE;
+ basis_valid = TRUE;
+ }
+ eta_valid = FALSE;
+ Break_bb = FALSE;
+ result = milpsolve(Orig_upbo, Orig_lowbo, Basis, Lower, Bas);
+ eta_size = Eta_size;
+ eta_alloc = Eta_alloc;
+ num_inv = Num_inv;
+ }
+ for(int i = 0; i < maxmat; i++) { set_row_nr(mat,i, 0); set_value(mat, i, 0); }
+ for(int i = 0; i < maxmat; i++) col_no[i] = 0;
+
+ // FIXME: not sure about this
+ for(int i = 0; i < Eta_size; i++) eta_value[i] = 0;
+ for(int i = 0; i < Eta_size; i++) eta_row_nr[i] = 0;
+ for(int i = 0; i < Eta_size; i++) eta_col_end[i] = 0;
+
+ maxmat = 0;
+ return(result);
+ }
+
+ private int maxmat = 0;
+ private final static float round( float val, float eps) { return (Math.abs(val) < eps) ? 0 : val; }
+ int get_row_nr(MatrixArray m, int i) { return m.row_nr[i]; }
+ void set_row_nr(MatrixArray m, int i, int val) { m.row_nr[i] = val; maxmat = Math.max(i, maxmat); }
+ float get_value(MatrixArray m, int i) { return m.value[i]; }
+ void set_value(MatrixArray m, int i, float val) { m.value[i] = val; maxmat = Math.max(i, maxmat); }
+ public static class MatrixArray {
+ public int[] row_nr;
+ public float[] value;
+ public final int length;
+ public MatrixArray(int length) { row_nr = new int[length]; value = new float[length]; this.length = length; }
+ }
+
+}
+
--- /dev/null
+// Copyright 2004 Adam Megacz, see the COPYING file for licensing [GPL]
+package org.ibex.util;
+import java.io.IOException;
+import org.ibex.js.*;
+
+public interface Task {
+ public abstract void perform() throws IOException, JSExn;
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+import java.io.*;
+
+/**
+ * An unsynchronized Vector implementation; same semantics as
+ * java.util.Vector. Useful for JDK1.1 platforms that don't have
+ * java.util.ArrayList.
+ *
+ * May contain nulls.
+ *
+ * @see java.util.Vector
+ */
+public final class Vec implements Serializable {
+
+ private Object[] store;
+ private int size = 0;
+
+ public Vec() { this(10); }
+ public Vec(int i) { store = new Object[i]; }
+ public Vec(int i, Object[] store) { size = i; this.store = store; }
+
+ private void grow() { grow(store.length * 2); }
+ private void grow(int newsize) {
+ Object[] newstore = new Object[newsize];
+ System.arraycopy(store, 0, newstore, 0, size);
+ store = newstore;
+ }
+
+ public void removeAllElements() {
+ for(int i=0; i<size; i++) store[i] = null;
+ size = 0;
+ }
+
+ public void toArray(Object[] o) {
+ for(int i=0; i<size; i++)
+ o[i] = store[i];
+ }
+
+ public int indexOf(Object o) {
+ for(int i=0; i<size; i++)
+ if (o == null ? store[i] == null : store[i].equals(o)) return i;
+
+ return -1;
+ }
+
+ public void addElement(Object o) {
+ if (size >= store.length - 1) grow();
+ store[size++] = o;
+ }
+
+ public Object peek() {
+ return lastElement();
+ }
+
+ public Object elementAt(int i) {
+ return store[i];
+ }
+
+ public Object lastElement() {
+ if (size == 0) return null;
+ return store[size - 1];
+ }
+
+ public void push(Object o) { addElement(o); }
+ public Object pop() {
+ Object ret = lastElement();
+ if (size > 0) store[size--] = null;
+ return ret;
+ }
+
+ public int size() { return size; }
+
+ public void setSize(int newSize) {
+ if (newSize < 0) throw new RuntimeException("tried to set size to negative value");
+ if (newSize > store.length) grow(newSize * 2);
+ if (newSize < size)
+ for(int i=newSize; i<size; i++)
+ store[i] = null;
+ size = newSize;
+ }
+
+ public void copyInto(Object[] out) {
+ for(int i=0; i<size; i++)
+ out[i] = store[i];
+ }
+
+ public void fromArray(Object[] in) {
+ setSize(in.length);
+ for(int i=0; i<size; i++)
+ store[i] = in[i];
+ }
+
+ public void removeElementAt(int i) {
+ if (i >= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits");
+ for(int j=i; j<size - 1; j++)
+ store[j] = store[j + 1];
+ setSize(size - 1);
+ }
+
+ public void setElementAt(Object o, int i) {
+ if (i >= size) setSize(i);
+ store[i] = o;
+ }
+
+ public void removeElement(Object o) {
+ int idx = indexOf(o);
+ if (idx != -1) removeElementAt(idx);
+ }
+
+ public void insertElementAt(Object o, int at) {
+ if (size == store.length) grow();
+ for(int i=size; i>at; i--)
+ store[i] = store[i-1];
+ store[at] = o;
+ size++;
+ }
+
+ public interface CompareFunc {
+ public int compare(Object a, Object b);
+ }
+
+ public void sort(CompareFunc c) {
+ sort(this, null, c, 0, size-1);
+ }
+
+ public static void sort(Vec a, Vec b, CompareFunc c) {
+ if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec a and b must be of equal size");
+ sort(a, b, c, 0, a.size-1);
+ }
+
+ private static final void sort(Vec a, Vec b, CompareFunc c, int start, int end) {
+ Object tmpa, tmpb = null;
+ if(start >= end) return;
+ if(end-start <= 6) {
+ for(int i=start+1;i<=end;i++) {
+ tmpa = a.store[i];
+ if (b != null) tmpb = b.store[i];
+ int j;
+ for(j=i-1;j>=start;j--) {
+ if(c.compare(a.store[j],tmpa) <= 0) break;
+ a.store[j+1] = a.store[j];
+ if (b != null) b.store[j+1] = b.store[j];
+ }
+ a.store[j+1] = tmpa;
+ if (b != null) b.store[j+1] = tmpb;
+ }
+ return;
+ }
+
+ Object pivot = a.store[end];
+ int lo = start - 1;
+ int hi = end;
+
+ do {
+ while(c.compare(a.store[++lo],pivot) < 0) { }
+ while((hi > lo) && c.compare(a.store[--hi],pivot) > 0) { }
+ swap(a, lo,hi);
+ if (b != null) swap(b, lo,hi);
+ } while(lo < hi);
+
+ swap(a, lo,end);
+ if (b != null) swap(b, lo,end);
+
+ sort(a, b, c, start, lo-1);
+ sort(a, b, c, lo+1, end);
+ }
+
+ private static final void swap(Vec vec, int a, int b) {
+ if(a != b) {
+ Object tmp = vec.store[a];
+ vec.store[a] = vec.store[b];
+ vec.store[b] = tmp;
+ }
+ }
+
+ public static final void sortInts(int[] a, int start, int end) {
+ int tmpa;
+ if(start >= end) return;
+ if(end-start <= 6) {
+ for(int i=start+1;i<=end;i++) {
+ tmpa = a[i];
+ int j;
+ for(j=i-1;j>=start;j--) {
+ if(a[j] <= tmpa) break;
+ a[j+1] = a[j];
+ }
+ a[j+1] = tmpa;
+ }
+ return;
+ }
+ int pivot = a[end];
+ int lo = start - 1;
+ int hi = end;
+ do {
+ while(a[++lo] < pivot) { }
+ while((hi > lo) && a[--hi] > pivot) { }
+ swapInts(a, lo, hi);
+ } while(lo < hi);
+ swapInts(a, lo, end);
+ sortInts(a, start, lo-1);
+ sortInts(a, lo+1, end);
+ }
+ private static final void swapInts(int[] vec, int a, int b) {
+ if(a != b) {
+ int tmp = vec[a];
+ vec[a] = vec[b];
+ vec[b] = tmp;
+ }
+ }
+
+
+
+ // just a cut-and-paste copy of Vec with int storage
+ public static class Int {
+ private int[] store;
+ private int size = 0;
+
+ public Int() { this(10); }
+ public Int(int i) { store = new int[i]; }
+ public Int(int i, int[] store) { size = i; this.store = store; }
+
+ private void grow() { grow(store.length * 2); }
+ private void grow(int newsize) {
+ int[] newstore = new int[newsize];
+ System.arraycopy(store, 0, newstore, 0, size);
+ store = newstore;
+ }
+
+ public void removeAllElements() {
+ for(int i=0; i<size; i++) store[i] = 0;
+ size = 0;
+ }
+
+ public void toArray(int[] o) {
+ for(int i=0; i<size; i++)
+ o[i] = store[i];
+ }
+
+ public int[] dump() { int[] o = new int[size]; toArray(o); return o; }
+
+ public int indexOf(int o) {
+ for(int i=0; i<size; i++)
+ if (o == store[i]) return i;
+
+ return -1;
+ }
+
+ public void addElement(int o) {
+ if (size >= store.length - 1) grow();
+ store[size++] = o;
+ }
+
+ public int peek() {
+ return lastElement();
+ }
+
+ public int elementAt(int i) {
+ return store[i];
+ }
+
+ public int lastElement() {
+ if (size == 0) return 0;
+ return store[size - 1];
+ }
+
+ public void push(int o) { addElement(o); }
+ public int pop() {
+ int ret = lastElement();
+ if (size > 0) store[size--] = 0;
+ return ret;
+ }
+
+ public int size() { return size; }
+
+ public void setSize(int newSize) {
+ if (newSize < 0) throw new RuntimeException("tried to set size to negative value");
+ if (newSize > store.length) grow(newSize * 2);
+ if (newSize < size)
+ for(int i=newSize; i<size; i++)
+ store[i] = 0;
+ size = newSize;
+ }
+
+ public void copyInto(int[] out) {
+ for(int i=0; i<size; i++)
+ out[i] = store[i];
+ }
+
+ public void fromArray(int[] in) {
+ setSize(in.length);
+ for(int i=0; i<size; i++)
+ store[i] = in[i];
+ }
+
+ public void removeElementAt(int i) {
+ if (i >= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits");
+ for(int j=i; j<size - 1; j++)
+ store[j] = store[j + 1];
+ setSize(size - 1);
+ }
+
+ public void setElementAt(int o, int i) {
+ if (i >= size) setSize(i);
+ store[i] = o;
+ }
+
+ public void removeElement(int o) {
+ int idx = indexOf(o);
+ if (idx != -1) removeElementAt(idx);
+ }
+
+ public void insertElementAt(int o, int at) {
+ if (size == store.length) grow();
+ for(int i=size; i>at; i--)
+ store[i] = store[i-1];
+ store[at] = o;
+ size++;
+ }
+
+ public void sort() { sort(this, null, 0, size-1); }
+
+ public static void sort(Vec.Int a, Vec.Int b) {
+ if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec.Int a and b must be of equal size");
+ sort(a, b, 0, a.size-1);
+ }
+
+ private static final void sort(Vec.Int a, Vec.Int b, int start, int end) {
+ int tmpa, tmpb = 0;
+ if(start >= end) return;
+ if(end-start <= 6) {
+ for(int i=start+1;i<=end;i++) {
+ tmpa = a.store[i];
+ if (b != null) tmpb = b.store[i];
+ int j;
+ for(j=i-1;j>=start;j--) {
+ if((a.store[j]-tmpa) <= 0) break;
+ a.store[j+1] = a.store[j];
+ if (b != null) b.store[j+1] = b.store[j];
+ }
+ a.store[j+1] = tmpa;
+ if (b != null) b.store[j+1] = tmpb;
+ }
+ return;
+ }
+
+ int pivot = a.store[end];
+ int lo = start - 1;
+ int hi = end;
+
+ do {
+ while((a.store[++lo]-pivot) < 0) { }
+ while((hi > lo) && (a.store[--hi]-pivot) > 0) { }
+ swap(a, lo,hi);
+ if (b != null) swap(b, lo,hi);
+ } while(lo < hi);
+
+ swap(a, lo,end);
+ if (b != null) swap(b, lo,end);
+
+ sort(a, b, start, lo-1);
+ sort(a, b, lo+1, end);
+ }
+
+ private static final void swap(Vec.Int vec, int a, int b) {
+ if(a != b) {
+ int tmp = vec.store[a];
+ vec.store[a] = vec.store[b];
+ vec.store[b] = tmp;
+ }
+ }
+
+ public static final void sortInts(int[] a, int start, int end) {
+ int tmpa;
+ if(start >= end) return;
+ if(end-start <= 6) {
+ for(int i=start+1;i<=end;i++) {
+ tmpa = a[i];
+ int j;
+ for(j=i-1;j>=start;j--) {
+ if(a[j] <= tmpa) break;
+ a[j+1] = a[j];
+ }
+ a[j+1] = tmpa;
+ }
+ return;
+ }
+
+ int pivot = a[end];
+ int lo = start - 1;
+ int hi = end;
+
+ do {
+ while(a[++lo] < pivot) { }
+ while((hi > lo) && a[--hi] > pivot) { }
+ swapInts(a, lo, hi);
+ } while(lo < hi);
+ swapInts(a, lo, end);
+ sortInts(a, start, lo-1);
+ sortInts(a, lo+1, end);
+ }
+
+ private static final void swapInts(int[] vec, int a, int b) {
+ if(a != b) {
+ int tmp = vec[a];
+ vec[a] = vec[b];
+ vec[b] = tmp;
+ }
+ }
+ }
+
+
+
+ public static final void sortFloats(float[] a, int start, int end) {
+ float tmpa;
+ if(start >= end) return;
+ if(end-start <= 6) {
+ for(int i=start+1;i<=end;i++) {
+ tmpa = a[i];
+ int j;
+ for(j=i-1;j>=start;j--) {
+ if(a[j] <= tmpa) break;
+ a[j+1] = a[j];
+ }
+ a[j+1] = tmpa;
+ }
+ return;
+ }
+ float pivot = a[end];
+ int lo = start - 1;
+ int hi = end;
+ do {
+ while(a[++lo] < pivot) { }
+ while((hi > lo) && a[--hi] > pivot) { }
+ swapFloats(a, lo, hi);
+ } while(lo < hi);
+ swapFloats(a, lo, end);
+ sortFloats(a, start, lo-1);
+ sortFloats(a, lo+1, end);
+ }
+ private static final void swapFloats(float[] vec, int a, int b) {
+ if(a != b) {
+ float tmp = vec[a];
+ vec[a] = vec[b];
+ vec[b] = tmp;
+ }
+ }
+}
--- /dev/null
+// Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
+package org.ibex.util;
+
+import java.io.Reader;
+import java.io.IOException;
+import java.io.EOFException;
+
+/**
+ * An Event-Driving, Non-Validating XML Parser with Namespace support.
+ *
+ * A subclass can implement the abstract functions for receiving details
+ * about an xml file as it is parsed. To initate a parse, use the parse()
+ * function.
+ *
+ * <h3>Implementation Notes</h3>
+ * <p>As the parser traverses into an element, it adds it to the linked list
+ * called <tt>elements</tt>. However, <tt>elements</tt> has been pre-filled
+ * with instances of the Element inner class. So in the vast majority of
+ * cases, the pointer current is moved along one, and the values for the
+ * new element are filled into the current object.</p>
+ *
+ * <p>This parser supports all the unicode ranges required by the XML
+ * Specification. However, it is optimised for well-formed ASCII documents.
+ * Documents containing unicode Names and Attributes will take much longer
+ * to process, and invalid documents (badly formed Names or invalid attributes)
+ * will be run through a test on every single unicode character range before
+ * being declared invalid.</p>
+ *
+ * <ul>
+ * <li>Each time the buffer offset <tt>off</tt> is moved, the length
+ * <tt>len</tt> must be decreased.</li>
+ * <li>Each time the buffer length is decreased, it must be checked to make
+ * sure it is >0.</li>
+ * <li><i>error</i> is defined as a Validity Constraint Violation and
+ * is recoverable</li>
+ * <li><i>fatal error</i> is defined as a Well-formedness Constraint
+ * Violation and is not recoverable</li>
+ * </ul>
+ *
+ * @author David Crawshaw
+ * @see <a href="http://w3.org/TR/REC-xml">XML Specification</a>
+ * @see <a href="http://w3.org/TR/REC-xml-names">XML Namespaces</a>
+ */
+public abstract class XML
+{
+ /////////////////////////////////////////////////////////////////////////////////////////////
+ // XML Parser
+ /////////////////////////////////////////////////////////////////////////////////////////////
+
+ public static final int BUFFER_SIZE = 255;
+
+ /** static pool of XML.Element instances shared by all XML Parsers. */
+ private static final Queue elements = new Queue(30);
+
+ private static final char[] single_amp = new char[] { '&' };
+ private static final char[] single_apos = new char[] { '\'' };
+ private static final char[] single_gt = new char[] { '>' };
+ private static final char[] single_lt = new char[] { '<' };
+ private static final char[] single_quot = new char[] { '"' };
+
+ private int line;
+ private int col;
+
+ private Reader in;
+ private char[] buf;
+ private int off;
+ private int base; // base+off == distance into the stream
+ private int len;
+
+ private Element current;
+
+ // used in readEntity() to process a single character without creating a new array
+ private char[] singlechar = new char[1];
+
+
+ public XML() { this(BUFFER_SIZE); }
+
+ public XML(int bSize) {
+ buf = new char[bSize];
+
+ current = (Element)elements.remove(false);
+ if (current == null) current = new Element();
+ }
+
+ /** Returns the line number at the beginning of the last process call. */
+ public int getLine() { return line; }
+
+ /** Returns the column number at the beginning of the last process call. */
+ public int getCol() { return col; }
+
+ /** Returns the global file offset at the beginning of the last process call. */
+ public int getGlobalOffset() { return base + off; }
+
+ /**
+ * Parse given input and call the abstract event functions.
+ *
+ * Careful with threading, as this function is not synchronized.
+ */
+ public final void parse(Reader reader) throws IOException, Exn {
+ in = reader;
+ off = len = 0;
+ line = col = 1;
+
+ clear(); // clean up possible mid-way linked-list element
+
+ try {
+ // process the stream
+ while (true) {
+ if (!buffer(1)) {
+ if (current.qName == null) break;
+ throw new Exn("reached eof without closing <"+current.qName+"> element", Exn.WFC, getLine(), getCol());
+ }
+
+ if (buf[off] == '<') readTag();
+ readChars(current.qName != null);
+ }
+ } finally { clear(); } // clean up elements
+ }
+
+ /** remove any leftover elements from the linked list and queue them */
+ private final void clear() {
+ for (Element last = current; current.parent != null; ) {
+ current = current.parent;
+ last.clear();
+ elements.append(last);
+ }
+ current.clear();
+ }
+
+ /** reads in a tag. expects <tt>buf[off] == '<'</tt> */
+ private final void readTag() throws IOException, Exn {
+ // Start Tag '<' Name (S Attribute)* S? '>'
+ boolean starttag = true;
+
+ // End Tag '</' Name S? '>'
+ boolean endtag = false;
+
+ // if (starttag & endtag) then: EmptyElemTag '<' Name (S Attribute)* S? '/>'
+
+ // Position in the name of the ':' namespace prefix
+ int prefix = -1;
+
+ int namelen = 0;
+
+ col++; off++; len--;
+ if (!buffer(1)) throw new EOFException("Unexpected EOF processing element tag");
+
+ // work out what we can from the beginning of the tag
+ char s = buf[off];
+ if (s == '!') {
+ // definitions here don't necessarily conform to xml spec (as DTDs not yet implemented)
+ col++; off++; len--;
+ if (!buffer(4)) throw new EOFException("Unexpected EOF processing <! element");
+
+ boolean bad = false;
+ switch (buf[off]) {
+ case '-':
+ if (buf[off+1] != '-') { bad = true; break; }
+ col += 2; off += 2; len -= 2;
+
+ // Comment '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'
+ readChars(false, "-->", false);
+ col += 3; off += 3; len -= 3;
+ break;
+
+ // we don't care about the following definitions
+
+ case 'A':
+ if (!buffer(7)
+ || buf[off+1] != 'T' || buf[off+2] != 'T' || buf[off+3] != 'L'
+ || buf[off+4] != 'I' || buf[off+5] != 'S' || buf[off+6] != 'T') {
+ bad = true; break;
+ }
+ col += 7; off += 7; len -= 7;
+
+ // ATTLIST '<!ATTLIST' (Char* - '>') '>'
+ readChars(false, ">", true);
+ col++; off++; len--;
+ break;
+ case 'D':
+ if (!buffer(7)
+ || buf[off+1] != 'O' || buf[off+2] != 'C' || buf[off+3] != 'T'
+ || buf[off+4] != 'Y' || buf[off+5] != 'P' || buf[off+6] != 'E') {
+ bad = true; break;
+ }
+ col += 7; off += 7; len -= 7;
+
+ // DTD '<!DOCTYPE' (Char* - '>') '>'
+ readChars(false, ">", true);
+ col++; off++; len--;
+ break;
+ case 'E':
+ if (!buffer(7)) {
+ bad = true;
+ } else if (buf[off+1] == 'L' && buf[off+2] == 'E' && buf[off+3] == 'M'
+ && buf[off+4] == 'E' && buf[off+5] == 'N' && buf[off+6] == 'T') {
+ // ELEMENT '<!ELEMENT' (Char* - '>') '>'
+ readChars(false, ">", true);
+ col++; off++; len--;
+
+ } else if (buf[off+1] == 'N' && buf[off+2] == 'T' && buf[off+3] == 'I'
+ && buf[off+4] == 'T' && buf[off+5] == 'Y') {
+ // ENTITY '<!ENTITY' (Char* - '>') '>'
+ readChars(false, ">", true);
+ col++; off++; len--;
+
+ } else {
+ bad = true;
+ }
+ break;
+
+ case 'N':
+ if (!buffer(8)
+ || buf[off+1] != 'O' || buf[off+2] != 'T' || buf[off+3] != 'A' || buf[off+4] != 'T'
+ || buf[off+5] != 'I' || buf[off+6] != 'O' || buf[off+7] != 'N') {
+ bad = true; break;
+ }
+ col += 8; off += 8; len -= 8;
+ // NOTATION '<!NOTATION' (Char* - '>') '>'
+ readChars(false, ">", true);
+ col++; off++; len--;
+
+ break;
+ default: bad = true;
+ }
+
+ if (bad) throw new Exn("element tag start character is invalid", Exn.MARKUP, getLine(), getCol());
+
+ } else if (s == '?') {
+ // PI (Ignored) '<?' (Char* - (Char* '?>' Char*)) '?>'
+ col++; off++; len--;
+ readChars(false, "?>", true);
+ if (!buffer(2)) throw new EOFException("Unexpected EOF at end of Processing Instruction");
+ col += 2; off += 2; len -= 2;
+
+ } else if (s == '[') {
+ if (!buffer(7)
+ || buf[off+1] != 'C' || buf[off+2] != 'D' || buf[off+3] != 'A'
+ || buf[off+4] != 'T' || buf[off+5] != 'A' || buf[off+6] != '[') {
+ col++; off--; len++;
+ // Conditional '<![' (Char* - (Char* ']]>' Char*)) ']]>'
+ readChars(false, "]]>", false);
+ } else {
+ col += 7; off += 7; len -=7;
+ // CDATA '<![CDATA[' (Char* - (Char* ']]>' Char*)) ']]>'
+ readChars(true, "]]>", false);
+ }
+ col += 3; off += 3; len -= 3;
+ } else {
+ if (s == '/') {
+ // End Tag '</' Name S? '>'
+ starttag = false;
+ endtag = true;
+
+ col++; off++; len--;
+ if (!buffer(1)) throw new EOFException("Unexpected EOF processing end tag");
+ s = buf[off];
+ }
+
+ if (!Name(s)) throw new Exn("invalid starting character in element name", Exn.MARKUP, getLine(), getCol());
+
+ // find the element name (defined in XML Spec: section 2.3)
+ for (namelen = 0; ; namelen++) {
+ if (!buffer(namelen+1)) throw new EOFException("Unexpected EOF in element tag name");
+
+ s = buf[off+namelen];
+
+ if (S(s) || s == '>') {
+ break;
+ } else if (s == '/') {
+ endtag = true;
+ break;
+ } else if (s == ':' && namelen > 0 && prefix < 1) {
+ // we have a definition of the prefix range available
+ prefix = namelen;
+ } else if (!NameChar(s)) {
+ throw new Exn("element name contains invalid character", Exn.MARKUP, getLine(), getCol());
+ }
+ }
+
+ // process name (based on calculated region)
+ if (namelen < 1) throw new Exn("element name is null", Exn.MARKUP, getLine(), getCol());
+
+ // we have marked out the name region, so turn it into a string and move on
+ String qName = new String(buf, off, namelen);
+
+ col += namelen; off += namelen; len -= namelen;
+
+ if (starttag) {
+ // create the in-memory element representation of this beast
+ // if current.qName == null then this is the root element we're dealing with
+ if (current.qName != null) {
+ Element next = (Element)elements.remove(false);
+ if (next == null) next = new Element();
+ //next.clear(); // TODO: remove as elements now checked as they're added to the queue
+ next.parent = current;
+ current = next;
+ }
+
+ current.qName = qName;
+
+ if (prefix > 0) {
+ current.prefix = current.qName.substring(0, prefix);
+ current.localName = current.qName.substring(prefix+1);
+ } else {
+ current.prefix = null;
+ current.localName = current.qName;
+ }
+
+ // process attributes
+ readWhitespace();
+ if (!buffer(1)) throw new EOFException("Unexpected EOF - processing attributes part 1");
+ while (buf[off] != '/' && buf[off] != '>') {
+ readAttribute();
+ if (!buffer(1)) throw new EOFException("Unexpected EOF - processing attributes part 2");
+ readWhitespace();
+ }
+
+ // work out the uri of this element
+ current.uri = current.getUri(current.getPrefix());
+ if (current.getUri().equals("") && current.getPrefix() != null)
+ current.addError(new Exn("undefined prefix '"+current.getPrefix()+"'", Exn.NC, getLine(), getCol()));
+
+ } else {
+ // this is an end-of-element tag
+ if (!qName.equals(current.getQName())) throw new Exn(
+ "end tag </"+qName+"> does not line up with start tag <"+current.getQName()+">", Exn.WFC, getLine(), getCol()
+ );
+ }
+
+ // deal with whitespace
+ readWhitespace();
+
+ // process tag close
+ if (!buffer(1)) throw new EOFException("Unexpected EOF before end of tag");
+ if (buf[off] == '/') {
+ endtag = true;
+ off++; len--; col++;
+ }
+ if (!buffer(1)) throw new EOFException("Unexpected EOF before end of endtag");
+ if (buf[off] == '>') {
+ off++; len--; col++;
+ } else {
+ throw new Exn("missing '>' character from element '"+qName+"'", Exn.MARKUP, getLine(), getCol());
+ }
+
+ // send element signals
+ if (starttag) startElement(current);
+ if (endtag) {
+ endElement(current);
+
+ // we just closed an element, so remove it from the element 'stack'
+ if (current.getParent() == null) {
+ // we just finished the root element
+ current.clear();
+ } else {
+ Element last = current;
+ current = current.parent;
+ last.clear();
+ elements.append(last);
+ }
+ }
+ }
+ }
+
+ /** reads in an attribute of an element. expects Name(buf[off]) */
+ private final void readAttribute() throws IOException, Exn {
+ int ref = 0;
+ int prefix = 0;
+ String n, v, p, u; // attribute name, value, prefix and uri respectively
+ n = v = p = u = null;
+ char s;
+
+ // find the element name (defined in XML Spec: section 2.3)
+ for (ref= 0; ; ref++) {
+ if (!buffer(ref+1)) throw new EOFException("Unexpected EOF in read attribute loop part 1");
+
+ s = buf[off+ref];
+
+ if (s == '=' || S(s)) {
+ break;
+ } else if (s == ':' && ref > 0 && prefix < 1) {
+ // we have a definition of the prefix range available
+ prefix = ref+1;
+ } else if (!NameChar(s)) {
+ throw new Exn("attribute name contains invalid characters", Exn.MARKUP, getLine(), getCol());
+ }
+ }
+
+ // determine prefix and key name
+ if (prefix > 0) {
+ p = new String(buf, off, prefix-1);
+ col += prefix; off += prefix; len -= prefix; ref -= prefix;
+ }
+ n = new String(buf, off, ref);
+ col += ref; off += ref; len -= ref;
+
+ // find name/value divider ('=')
+ readWhitespace();
+ if (!buffer(1)) throw new EOFException("Unexpected EOF before attribute '=' divider");
+ if (buf[off] != '=') throw new Exn("attribute name not followed by '=' sign", Exn.MARKUP, getLine(), getCol());
+
+ col++; off++; len--;
+ readWhitespace();
+
+ if (!buffer(1)) throw new EOFException("Unexpected EOF after attribute '=' divider");
+
+ char wrap;
+ if (buf[off] == '\'' || buf[off] == '"') {
+ wrap = buf[off];
+ } else {
+ throw new Exn("attribute '"+n+"' must have attribute wrapped in ' or \"", Exn.MARKUP, getLine(), getCol());
+ }
+ col++; off++; len--;
+
+ // find the attribute value
+ attval: for (ref = 0; ; ref++) {
+ if (!buffer(ref+1)) throw new EOFException("Unexpected EOF in attribute value");
+
+ if (buf[off+ref] == wrap) {
+ break attval;
+ } else if (buf[off+ref] == '<') {
+ throw new Exn("attribute value for '"+n+"' must not contain '<'", Exn.WFC, getLine(), getCol());
+ }
+ }
+
+ v = new String(buf, off, ref);
+ col += ref; off += ref; len -= ref;
+
+ // remove end wrapper character
+ col++; off++; len--;
+
+ // process attribute
+ if (p != null && p.equals("xmlns")) {
+ current.addUri(n, v);
+ } else if (n.equals("xmlns")) {
+ if (current.getUri().equals("")) {
+ current.addUri("", v);
+ } else {
+ current.addError(new Exn("default namespace definition repeated", Exn.NC, getLine(), getCol()));
+ }
+ } else {
+ // find attribute uri
+ u = current.getUri(p);
+ if (p != null && u.equals("")) current.addError(new Exn("undefined attribute prefix '"+p+"'", Exn.NC, getLine(), getCol()));
+
+ // check to see if attribute is a repeat
+ for (int i=0; current.len > i; i++) if (n.equals(current.getAttrKey(i)) && u.equals(current.getAttrUri(i))) throw new Exn(
+ "attribute name '"+n+"' may not appear more than once in the same element tag", Exn.WFC, getLine(), getCol()
+ );
+
+ current.addAttr(n, v, u);
+ }
+ }
+
+ /** reads an entity and processes out its value. expects buf[off] == '&' */
+ private final void readEntity() throws IOException, Exn {
+ off++; len--;
+ if (!buffer(2)) throw new EOFException("Unexpected EOF reading entity");
+
+ boolean unknown = false;
+ switch (buf[off]) {
+ case '#':
+ off++; len--;
+
+ int radix;
+ if (buf[off] == 'x') { off++; len--; radix = 16; } else { radix = 10; }
+ int c = 0;
+
+ // read in each char, then shift total value to the left and add the extra
+ // style of loop is slightly different from all the others, as this should run a limited number of times
+ findchar: while (true) {
+ if (!buffer(1)) throw new EOFException("Unexpected EOF reading entity");
+ int d = Character.digit(buf[off], radix);
+ if (d == -1) {
+ if (buf[off] != ';') throw new Exn("illegal characters in entity reference", Exn.WFC, getLine(), getCol());
+ off++; len--; col++;
+ break findchar;
+ }
+ c = (c * radix) + d;
+
+ off++; len--;
+ }
+
+ singlechar[0] = Character.forDigit(c, radix);
+ characters(singlechar, 0, 1);
+ break;
+
+ case 'a':
+ if (buffer(4) && buf[off+1] == 'm' && buf[off+2] == 'p' && buf[off+3] == ';') {
+ characters(single_amp, 0, 1); // &
+ off += 4; len -= 4; col++;
+ } else if (buffer(5) && buf[off+1] == 'p' && buf[off+2] == 'o' && buf[off+3] == 's' && buf[off+4] == ';') {
+ characters(single_apos, 0, 1); // '
+ off += 5; len -= 5; col++;
+ } else {
+ unknown = true;
+ }
+ break;
+
+ case 'g':
+ if (buffer(3) && buf[off+1] == 't' && buf[off+2] == ';') {
+ characters(single_gt, 0, 1); // >
+ off += 3; len -= 3; col++;
+ } else {
+ unknown = true;
+ }
+ break;
+
+ case 'l':
+ if (buffer(3) && buf[off+1] == 't' && buf[off+2] == ';') {
+ characters(single_lt, 0, 1); // <
+ off += 3; len -= 3; col++;
+ } else {
+ unknown = true;
+ }
+ break;
+
+ case 'q':
+ if (buffer(5) && buf[off+1] == 'u' && buf[off+2] == 'o' && buf[off+3] == 't' && buf[off+4] == ';') {
+ characters(single_quot, 0, 1); // "
+ off += 5; len -= 5; col++;
+ } else {
+ unknown = true;
+ }
+ break;
+
+ // TODO: check a parser-level Hash of defined entities
+ }
+
+ if (unknown) throw new Exn("unknown entity (<!ENTITY> not supported)", Exn.WFC, getLine(), getCol());
+ }
+
+ /** reads until the passed string is encountered. */
+ private final void readChars(boolean p, String match, boolean entities) throws IOException, Exn {
+ int ref;
+ char[] end = match.toCharArray();
+
+ for (boolean more = true; more;) {
+ if (!buffer(1)) return;
+
+ buf: for (ref = 0; ref < len; ref++) {
+ switch (buf[off+ref]) {
+ case '\r': // windows or macos9 newline
+ // normalise and process
+ buf[off+ref] = '\n'; ref++;
+ if (p) characters(buf, off, ref);
+ off += ref; len -= ref; ref = -1;
+ line++; col = 1;
+
+ // windows double-char newline; skip the next char
+ if (!buffer(1)) return;
+ if (buf[off] == '\n') { off++; len--; }
+ break;
+
+ case '\n': // unix newline
+ ref++;
+ if (p) characters(buf, off, ref);
+ off += ref; len -= ref; ref = -1;
+ line++; col = 1;
+ break;
+
+ case '&': // entity
+ if (entities) {
+ if (p) {
+ if (ref > 0) characters(buf, off, ref);
+ off += ref; len -= ref; ref = -1;
+ readEntity();
+ }
+ break;
+ }
+
+ default:
+ if (!buffer(ref+end.length)) continue buf;
+ for (int i=0; end.length > i; i++) if (end[i] != buf[off+ref+i]) continue buf;
+ more = false;
+ break buf;
+ }
+ }
+
+ if (p && ref > 0) characters(buf, off, ref);
+ off += ref; len -= ref; col += ref;
+ }
+ }
+
+ /**
+ * reads until a <tt><</tt> symbol is encountered
+ * @param p If true call the characters(char[],int,int) funciton for the processed characters
+ */
+ private final void readChars(boolean p) throws IOException, Exn {
+ int ref;
+
+ for (boolean more = true; more;) {
+ if (!buffer(1)) return;
+
+ buf: for (ref = 0; ref < len; ref++) {
+ switch (buf[off+ref]) {
+ case '\r': // windows or macos9 newline
+ // normalise and process
+ buf[off+ref] = '\n'; ref++;
+ if (p) characters(buf, off, ref);
+ off += ref; len -= ref; ref = -1;
+ line++; col = 1;
+
+ // windows double-char newline; skip the next char
+ if (!buffer(1)) return;
+ if (buf[off] == '\n') { off++; len--; }
+ break;
+
+ case '\n': // unix newline
+ ref++;
+ if (p) characters(buf, off, ref);
+ off += ref; len -= ref; ref = -1;
+ line++; col = 1;
+ break;
+
+ case '&': // entity
+ if (p) {
+ if (ref > 0) characters(buf, off, ref);
+ off += ref; len -= ref; ref = -1;
+ readEntity();
+ }
+ break;
+
+ case '<': // end of chars section
+ more = false;
+ break buf;
+ }
+ }
+
+ if (p && ref > 0) characters(buf, off, ref);
+ off += ref; len -= ref; col += ref;
+ }
+ }
+
+ /** reads until a non-whitespace symbol is encountered */
+ private final void readWhitespace() throws IOException, Exn {
+ int ref;
+
+ for (boolean more = true; more;) {
+ if (!buffer(1)) return;
+
+ buf: for (ref = 0; ref < len; ref++) {
+ switch (buf[off+ref]) {
+ case '\r': // windows or macos9 newline
+ // normalise and process
+ buf[off+ref] = '\n';
+ whitespace(buf, off, ++ref);
+ off += ref; len -= ref; ref = -1;
+ line++; col = 1;
+
+ // windows double-char newline; skip the next char
+ if (!buffer(1)) return;
+ if (buf[off] == '\n') { off++; len--; }
+ break;
+
+ case '\n': // unix newline
+ whitespace(buf, off, ++ref);
+ off += ref; len -= ref; ref = -1;
+ line++; col = 1;
+ break;
+
+ case ' ': // space
+ case '\t': // tab
+ break;
+
+ default: // end of whitespace
+ more = false;
+ break buf;
+ }
+ }
+
+ off += ref; len -= ref; col += ref;
+ }
+ }
+
+ /**
+ * attempt to fill the buffer.
+ *
+ * @param min Minimum number of characters to read (even if we have to block to do it).
+ * @return return false if min can't be reached.
+ */
+ private final boolean buffer(int min) throws IOException {
+ if (len > min) return true;
+
+ if (buf.length - (off+len) >= min) {
+ // plenty of space left on the end of the buffer
+ } else if (off >= min) {
+ // moving offset data to start will leave enough free space on the end
+ System.arraycopy(buf, off, buf, 0, len);
+ base += off;
+ off = 0;
+ } else {
+ // buffer size will have to be increased
+ char[] newbuf = new char[buf.length * 2];
+ System.arraycopy(buf, off, newbuf, 0, len);
+ buf = newbuf;
+ base += off;
+ off = 0;
+ }
+
+ while (min > len) {
+ int newlen = in.read(buf, off+len, buf.length-(off+len));
+ if (newlen < 0) return false;
+ len += newlen;
+ }
+
+ return true;
+ }
+
+
+ /////////////////////////////////////////////////////////////////////////////////////////////
+ // Abstract SAX-Like Interface
+ /////////////////////////////////////////////////////////////////////////////////////////////
+
+ /**
+ * Called when the start of an element is processed.
+ *
+ * <p><b>DO NOT</b> store a reference to the Element object, as
+ * they are reused by XML Parser.</p>
+ */
+ public abstract void startElement(Element e) throws Exn;
+
+ /**
+ * Represents up to a line of character data.
+ *
+ * <p>Newlines are all normalised to the Unix \n as per the XML Spec,
+ * and a newline will only appear as the last character in the passed
+ * array segment.</p>
+ *
+ * <p>XML.getLine() and XML.getCol() report the position at the
+ * beginning of this character segment, which can be processed in a
+ * line-by-line fashion due to the above newline restriction.</p>
+ */
+ public abstract void characters(char[] ch, int start, int length) throws Exn, IOException;
+
+ /** Represents up to a line of ignorable whitespace. */
+ public abstract void whitespace(char[] ch, int start, int length) throws Exn, IOException;
+
+ /** Represents the end of an Element. */
+ public abstract void endElement(Element e) throws Exn, IOException;
+
+
+ /////////////////////////////////////////////////////////////////////////////////////////////
+ // Inner Classes for Parser Support
+ /////////////////////////////////////////////////////////////////////////////////////////////
+
+ /**
+ * Represents an element in an XML document. Stores a reference to its
+ * parent, forming a one-way linked list.
+ *
+ * Element objects are reused, so client code making use of them must
+ * drop their references after the specific element process function
+ * has returned.
+ */
+ public static final class Element {
+
+ private static final int DEFAULT_ATTR_SIZE = 10;
+
+ protected Element parent = null;
+
+ protected String uri = null;
+ protected String localName = null;
+ protected String qName = null;
+ protected String prefix = null;
+
+ protected Hash urimap = new Hash(3,3);
+
+ protected String[] keys = new String[DEFAULT_ATTR_SIZE];
+ protected String[] vals = new String[DEFAULT_ATTR_SIZE];
+ protected String[] uris = new String[DEFAULT_ATTR_SIZE];
+ protected int len = 0;
+
+ protected Exn[] errors = new Exn[] {};
+
+ /** Parent of current element. */
+ public Element getParent() { return parent; }
+
+ /** Qualified Name of current element. XML Namespace Spec 14-Jan-1999 [6] */
+ public String getQName() { return qName; }
+
+ /** LocalPart of current element. XML Namespace Spec 14-Jan-1999 [8] */
+ public String getLocalName() { return localName; }
+
+ /** Prefix of current element. Substring of qName. XML Namespace Spec 14-Jan-1999 [7] */
+ public String getPrefix() { return prefix; }
+
+ // HACK
+ public Hash getUriMap() {
+ Hash map = new Hash();
+ for (Element e = this; e != null; e = e.getParent()) {
+ java.util.Enumeration en = e.urimap.keys();
+ while(en.hasMoreElements()) {
+ String key = (String)en.nextElement();
+ String val = getUri(key);
+ map.put(key, val);
+ }
+ }
+ return map;
+ }
+
+ /** URI of current tag. XML Namespace Spec 14-Jan-1999 section 1 */
+ public String getUri() { return getUri(prefix); }
+
+ /** URI of a given prefix. Never returns null, instead gives "". */
+ public String getUri(String p) {
+ String ret = null;
+ for (Element e = this; e != null && ret == null; e = e.getParent()) {
+ ret = (String)e.urimap.get(p == null ? "" : p);
+ }
+ return ret == null ? "" : ret;
+ }
+
+ /** An array of attribute names. */
+ public String getAttrKey(int pos) { return len > pos ? keys[pos] : null; }
+
+ /** An array of attribute values. */
+ public String getAttrVal(int pos) { return len > pos ? vals[pos] : null; }
+
+ /** An array of attribute uris. */
+ public String getAttrUri(int pos) { return len > pos ? uris[pos] : null; }
+
+ /** Current number of attributes in the element. */
+ public int getAttrLen() { return len; }
+
+ /** Poor performance, but easier to use when speed is not a concern */
+ public Hash getAttrHash() {
+ Hash ret = new Hash(getAttrLen() * 2, 3);
+ for(int i=0; i<len; i++)
+ ret.put(getAttrKey(i), getAttrVal(i));
+ return ret;
+ }
+
+ /** Poor performance, but easier to use */
+ public String getAttrVal(String key) {
+ for(int i=0; i<len; i++) if (keys[i].equals(key)) return vals[i];
+ return null;
+ }
+
+ /** An array of non-fatal errors related to this element. */
+ public Exn[] getErrors() { return errors; }
+
+ protected Element() { }
+
+ /** Add (replace if exists in current element) a Namespace prefix/uri map. */
+ public void addUri(String name, String value) {
+ urimap.put(name, value);
+ }
+
+ /** Add an attribute. */
+ protected void addAttr(String key, String val, String uri) {
+ if (len == keys.length) {
+ // increase the size of the attributes arrays
+ String[] newkeys = new String[keys.length*2];
+ String[] newvals = new String[vals.length*2];
+ String[] newuris = new String[uris.length*2];
+ System.arraycopy(keys, 0, newkeys, 0, keys.length);
+ System.arraycopy(vals, 0, newvals, 0, vals.length);
+ System.arraycopy(uris, 0, newuris, 0, uris.length);
+ keys = newkeys; vals = newvals; uris = newuris;
+ }
+
+ keys[len] = key;
+ vals[len] = val;
+ uris[len] = uri;
+ len++;
+ }
+
+ /** Add an error. */
+ protected void addError(Exn e) {
+ // it doesn't really matter about continually expanding the array, as this case is quite rare
+ Exn[] newe = new Exn[errors.length+1];
+ System.arraycopy(errors, 0, newe, 0, errors.length);
+ newe[errors.length] = e;
+ errors = newe;
+ }
+
+ /** Empty out all the data from the Element. */
+ protected void clear() {
+ parent = null;
+ uri = localName = qName = prefix = null;
+ urimap.clear();
+
+ if (keys.length != vals.length || vals.length != uris.length) {
+ keys = new String[DEFAULT_ATTR_SIZE];
+ vals = new String[DEFAULT_ATTR_SIZE];
+ uris = new String[DEFAULT_ATTR_SIZE];
+ } else {
+ for (int i=0; keys.length > i; i++) { keys[i] = null; vals[i] = null; uris[i] = null; };
+ }
+ len = 0;
+
+ errors = new Exn[] {};
+ }
+ }
+
+ /** Parse or Structural Error */
+ public static class Exn extends Exception {
+ /** Violation of Markup restrictions in XML Specification - Fatal Error */
+ public static final int MARKUP = 1;
+
+ /** Well-Formedness Constraint Violation - Fatal Error */
+ public static final int WFC = 2;
+
+ /** Namespace Constraint Violation - Recoverable Error */
+ public static final int NC = 3;
+
+ /** Schema Violation - Fatal Error */
+ public static final int SCHEMA = 4;
+
+ private String error;
+ private int type;
+ private int line;
+ private int col;
+
+ public Exn(String e) { this(e, MARKUP, -1, -1); }
+
+ public Exn(String e, int type, int line, int col) {
+ this.error = e;
+ this.type = type;
+ this.line = line;
+ this.col = col;
+ }
+
+ public int getType() { return this.type; }
+ public int getLine() { return this.line; }
+ public int getCol() { return this.col; }
+ public String getMessage() { return this.error + (line >= 0 && col >= 0 ? " at " + line + ":" + col: ""); }
+ }
+
+
+ /////////////////////////////////////////////////////////////////////////////////////////////
+ // Static Support Functions for the XML Specification
+ /////////////////////////////////////////////////////////////////////////////////////////////
+
+ // attempt to avoid these functions unless you *expect* the input to fall in the given range.
+
+ /** First Character of Name - XML Specification 1.0 [5] */
+ private static final boolean Name(char c) {
+ return BaseCharAscii(c) || c == '_' || c == ':' || Letter(c);
+ }
+
+ /** NameChar - XML Specification 1.0 [4] */
+ private static final boolean NameChar(char c) {
+ return BaseCharAscii(c) || c == '.' || c == '-' || c == '_' || c == ':'
+ || Digit(c) || Letter(c) || Extender(c); // TODO: || CombiningChar(c);
+ }
+
+ /** BaseChar - XMl Specification 1.0 [84] */
+ private static final boolean Letter(char c) {
+ return BaseChar(c) || Ideographic(c);
+ }
+
+ /** Elements of BaseChar that exist in ASCII. */
+ private static final boolean BaseCharAscii(char c) {
+ return (c >= '\u0041' && c <= '\u005A') || (c >= '\u0061' && c <= '\u007A');
+ }
+
+ /** Char - XML Specification 1.0 [2] */
+ private static final boolean Char(char c) {
+ // u000A == r and u000D == n, but the javac compiler can't handle the \ u form
+ return c == '\u0009' || c == '\r' || c == '\n'
+ || (c >= '\u0020' && c <= '\uD7FF')
+ || (c >= '\uE000' && c <= '\uFFFD');
+ }
+
+ /** BaseChar - XML Specification 1.0 [85] */
+ private static final boolean BaseChar(char c) {
+ return BaseCharAscii(c) || (c >= '\u00C0' && c <= '\u00D6')
+ || (c >= '\u00D8' && c <= '\u00F6') || (c >= '\u00F8' && c <= '\u00FF') || (c >= '\u0100' && c <= '\u0131')
+ || (c >= '\u0134' && c <= '\u013E') || (c >= '\u0141' && c <= '\u0148') || (c >= '\u014A' && c <= '\u017E')
+ || (c >= '\u0180' && c <= '\u01C3') || (c >= '\u01CD' && c <= '\u01F0') || (c >= '\u01F4' && c <= '\u01F5')
+ || (c >= '\u01FA' && c <= '\u0217') || (c >= '\u0250' && c <= '\u02A8') || (c >= '\u02BB' && c <= '\u02C1')
+ || (c == '\u0386') || (c >= '\u0388' && c <= '\u038A') || (c == '\u038C')
+ || (c >= '\u038E' && c <= '\u03A1') || (c >= '\u03A3' && c <= '\u03CE') || (c >= '\u03D0' && c <= '\u03D6')
+ || (c == '\u03DA') || (c == '\u03DC') || (c == '\u03DE')
+ || (c == '\u03E0')
+ || (c >= '\u03E2' && c <= '\u03F3') || (c >= '\u0401' && c <= '\u040C') || (c >= '\u040E' && c <= '\u044F')
+ || (c >= '\u0451' && c <= '\u045C') || (c >= '\u045E' && c <= '\u0481') || (c >= '\u0490' && c <= '\u04C4')
+ || (c >= '\u04C7' && c <= '\u04C8') || (c >= '\u04CB' && c <= '\u04CC') || (c >= '\u04D0' && c <= '\u04EB')
+ || (c >= '\u04EE' && c <= '\u04F5') || (c >= '\u04F8' && c <= '\u04F9') || (c >= '\u0531' && c <= '\u0556')
+ || (c == '\u0559')
+ || (c >= '\u0561' && c <= '\u0586') || (c >= '\u05D0' && c <= '\u05EA') || (c >= '\u05F0' && c <= '\u05F2')
+ || (c >= '\u0621' && c <= '\u063A') || (c >= '\u0641' && c <= '\u064A') || (c >= '\u0671' && c <= '\u06B7')
+ || (c >= '\u06BA' && c <= '\u06BE') || (c >= '\u06C0' && c <= '\u06CE') || (c >= '\u06D0' && c <= '\u06D3')
+ || (c == '\u06D5')
+ || (c >= '\u06E5' && c <= '\u06E6') || (c >= '\u0905' && c <= '\u0939')
+ || (c == '\u093D')
+ || (c >= '\u0958' && c <= '\u0961') || (c >= '\u0985' && c <= '\u098C') || (c >= '\u098F' && c <= '\u0990')
+ || (c >= '\u0993' && c <= '\u09A8') || (c >= '\u09AA' && c <= '\u09B0')
+ || (c == '\u09B2')
+ || (c >= '\u09B6' && c <= '\u09B9') || (c >= '\u09DF' && c <= '\u09E1') || (c >= '\u09F0' && c <= '\u09F1')
+ || (c >= '\u0A05' && c <= '\u0A0A') || (c >= '\u0A0F' && c <= '\u0A10') || (c >= '\u0A13' && c <= '\u0A28')
+ || (c >= '\u0A2A' && c <= '\u0A30') || (c >= '\u0A32' && c <= '\u0A33') || (c >= '\u0A35' && c <= '\u0A36')
+ || (c >= '\u0A38' && c <= '\u0A39') || (c >= '\u0A59' && c <= '\u0A5C')
+ || (c == '\u0A5E')
+ || (c >= '\u0A72' && c <= '\u0A74') || (c >= '\u0A85' && c <= '\u0A8B')
+ || (c == '\u0A8D')
+ || (c >= '\u0A8F' && c <= '\u0A91') || (c >= '\u0A93' && c <= '\u0AA8') || (c >= '\u0AAA' && c <= '\u0AB0')
+ || (c >= '\u0AB2' && c <= '\u0AB3') || (c >= '\u0AB5' && c <= '\u0AB9')
+ || (c == '\u0ABD')
+ || (c == '\u0AE0')
+ || (c >= '\u0B05' && c <= '\u0B0C') || (c >= '\u0B0F' && c <= '\u0B10') || (c >= '\u0B13' && c <= '\u0B28')
+ || (c >= '\u0B2A' && c <= '\u0B30') || (c >= '\u0B32' && c <= '\u0B33') || (c >= '\u0B36' && c <= '\u0B39')
+ || (c == '\u0B3D')
+ || (c >= '\u0B5C' && c <= '\u0B5D') || (c >= '\u0B5F' && c <= '\u0B61') || (c >= '\u0B85' && c <= '\u0B8A')
+ || (c >= '\u0B8E' && c <= '\u0B90') || (c >= '\u0B92' && c <= '\u0B95') || (c >= '\u0B99' && c <= '\u0B9A')
+ || (c == '\u0B9C')
+ || (c >= '\u0B9E' && c <= '\u0B9F') || (c >= '\u0BA3' && c <= '\u0BA4') || (c >= '\u0BA8' && c <= '\u0BAA')
+ || (c >= '\u0BAE' && c <= '\u0BB5') || (c >= '\u0BB7' && c <= '\u0BB9') || (c >= '\u0C05' && c <= '\u0C0C')
+ || (c >= '\u0C0E' && c <= '\u0C10') || (c >= '\u0C12' && c <= '\u0C28') || (c >= '\u0C2A' && c <= '\u0C33')
+ || (c >= '\u0C35' && c <= '\u0C39') || (c >= '\u0C60' && c <= '\u0C61') || (c >= '\u0C85' && c <= '\u0C8C')
+ || (c >= '\u0C8E' && c <= '\u0C90') || (c >= '\u0C92' && c <= '\u0CA8') || (c >= '\u0CAA' && c <= '\u0CB3')
+ || (c >= '\u0CB5' && c <= '\u0CB9')
+ || (c == '\u0CDE')
+ || (c >= '\u0CE0' && c <= '\u0CE1') || (c >= '\u0D05' && c <= '\u0D0C') || (c >= '\u0D0E' && c <= '\u0D10')
+ || (c >= '\u0D12' && c <= '\u0D28') || (c >= '\u0D2A' && c <= '\u0D39') || (c >= '\u0D60' && c <= '\u0D61')
+ || (c >= '\u0E01' && c <= '\u0E2E')
+ || (c == '\u0E30')
+ || (c >= '\u0E32' && c <= '\u0E33') || (c >= '\u0E40' && c <= '\u0E45') || (c >= '\u0E81' && c <= '\u0E82')
+ || (c == '\u0E84')
+ || (c >= '\u0E87' && c <= '\u0E88')
+ || (c == '\u0E8A')
+ || (c == '\u0E8D')
+ || (c >= '\u0E94' && c <= '\u0E97') || (c >= '\u0E99' && c <= '\u0E9F') || (c >= '\u0EA1' && c <= '\u0EA3')
+ || (c == '\u0EA5')
+ || (c == '\u0EA7')
+ || (c >= '\u0EAA' && c <= '\u0EAB') || (c >= '\u0EAD' && c <= '\u0EAE')
+ || (c == '\u0EB0')
+ || (c >= '\u0EB2' && c <= '\u0EB3')
+ || (c == '\u0EBD')
+ || (c >= '\u0EC0' && c <= '\u0EC4') || (c >= '\u0F40' && c <= '\u0F47') || (c >= '\u0F49' && c <= '\u0F69')
+ || (c >= '\u10A0' && c <= '\u10C5') || (c >= '\u10D0' && c <= '\u10F6')
+ || (c == '\u1100')
+ || (c >= '\u1102' && c <= '\u1103') || (c >= '\u1105' && c <= '\u1107')
+ || (c == '\u1109')
+ || (c >= '\u110B' && c <= '\u110C') || (c >= '\u110E' && c <= '\u1112')
+ || (c == '\u113C')
+ || (c == '\u113E')
+ || (c == '\u1140')
+ || (c == '\u114C')
+ || (c == '\u114E')
+ || (c == '\u1150')
+ || (c >= '\u1154' && c <= '\u1155')
+ || (c == '\u1159')
+ || (c >= '\u115F' && c <= '\u1161')
+ || (c == '\u1163')
+ || (c == '\u1165')
+ || (c == '\u1167')
+ || (c == '\u1169')
+ || (c >= '\u116D' && c <= '\u116E') || (c >= '\u1172' && c <= '\u1173')
+ || (c == '\u1175')
+ || (c == '\u119E')
+ || (c == '\u11A8')
+ || (c == '\u11AB')
+ || (c >= '\u11AE' && c <= '\u11AF') || (c >= '\u11B7' && c <= '\u11B8')
+ || (c == '\u11BA')
+ || (c >= '\u11BC' && c <= '\u11C2')
+ || (c == '\u11EB')
+ || (c == '\u11F0')
+ || (c == '\u11F9')
+ || (c >= '\u1E00' && c <= '\u1E9B') || (c >= '\u1EA0' && c <= '\u1EF9') || (c >= '\u1F00' && c <= '\u1F15')
+ || (c >= '\u1F18' && c <= '\u1F1D') || (c >= '\u1F20' && c <= '\u1F45') || (c >= '\u1F48' && c <= '\u1F4D')
+ || (c >= '\u1F50' && c <= '\u1F57')
+ || (c == '\u1F59')
+ || (c == '\u1F5B')
+ || (c == '\u1F5D')
+ || (c >= '\u1F5F' && c <= '\u1F7D') || (c >= '\u1F80' && c <= '\u1FB4') || (c >= '\u1FB6' && c <= '\u1FBC')
+ || (c == '\u1FBE')
+ || (c >= '\u1FC2' && c <= '\u1FC4') || (c >= '\u1FC6' && c <= '\u1FCC') || (c >= '\u1FD0' && c <= '\u1FD3')
+ || (c >= '\u1FD6' && c <= '\u1FDB') || (c >= '\u1FE0' && c <= '\u1FEC') || (c >= '\u1FF2' && c <= '\u1FF4')
+ || (c >= '\u1FF6' && c <= '\u1FFC')
+ || (c == '\u2126')
+ || (c >= '\u212A' && c <= '\u212B')
+ || (c == '\u212E')
+ || (c >= '\u2180' && c <= '\u2182') || (c >= '\u3041' && c <= '\u3094') || (c >= '\u30A1' && c <= '\u30FA')
+ || (c >= '\u3105' && c <= '\u312C') || (c >= '\uAC00' && c <= '\uD7A3');
+ }
+
+ /** BaseChar - XMl Specification 1.0 [86] */
+ private static final boolean Ideographic(char c) {
+ return (c >= '\u4E00' && c <= '\u9FA5') || c == '\u3007' || (c >= '\u3021' && c <= '\u3029');
+ }
+
+ /** CombiningChar - XMl Specification 1.0 [87] */
+ /*private static final boolean CombiningChar(char c) {
+ return (c >= '\u0300' && c <= '\u0345')
+ || (c >= '\u0360' && c <= '\u0361') || (c >= '\u0483' && c <= '\u0486') || (c >= '\u0591' && c <= '\u05A1')
+ || (c >= '\u05A3' && c <= '\u05B9') || (c >= '\u05BB' && c <= '\u05BD')
+ || (c == '\u05BF')
+ || (c >= '\u05C1' && c <= '\u05C2')
+ || (c == '\u05C4')
+ || (c >= '\u064B' && c <= '\u0652')
+ || (c == '\u0670')
+ || (c >= '\u06D6' && c <= '\u06DC') || (c >= '\u06DD' && c <= '\u06DF') || (c >= '\u06E0' && c <= '\u06E4')
+ || (c >= '\u06E7' && c <= '\u06E8') || (c >= '\u06EA' && c <= '\u06ED') || (c >= '\u0901' && c <= '\u0903')
+ || (c == '\u093C')
+ || (c >= '\u093E' && c <= '\u094C')
+ || (c == '\u094D')
+ || (c >= '\u0951' && c <= '\u0954') || (c >= '\u0962' && c <= '\u0963') || (c >= '\u0981' && c <= '\u0983')
+ || (c == '\u09BC')
+ || (c == '\u09BE')
+ || (c == '\u09BF')
+ || (c >= '\u09C0' && c <= '\u09C4') || (c >= '\u09C7' && c <= '\u09C8') || (c >= '\u09CB' && c <= '\u09CD')
+ || (c == '\u09D7')
+ || (c >= '\u09E2' && c <= '\u09E3')
+ || (c == '\u0A02')
+ || (c == '\u0A3C')
+ || (c == '\u0A3E')
+ || (c == '\u0A3F')
+ || (c >= '\u0A40' && c <= '\u0A42') || (c >= '\u0A47' && c <= '\u0A48') || (c >= '\u0A4B' && c <= '\u0A4D')
+ || (c >= '\u0A70' && c <= '\u0A71') || (c >= '\u0A81' && c <= '\u0A83')
+ || (c == '\u0ABC')
+ || (c >= '\u0ABE' && c <= '\u0AC5') || (c >= '\u0AC7' && c <= '\u0AC9') || (c >= '\u0ACB' && c <= '\u0ACD')
+ || (c >= '\u0B01' && c <= '\u0B03')
+ || (c == '\u0B3C')
+ || (c >= '\u0B3E' && c <= '\u0B43') || (c >= '\u0B47' && c <= '\u0B48') || (c >= '\u0B4B' && c <= '\u0B4D')
+ || (c >= '\u0B56' && c <= '\u0B57') || (c >= '\u0B82' && c <= '\u0B83') || (c >= '\u0BBE' && c <= '\u0BC2')
+ || (c >= '\u0BC6' && c <= '\u0BC8') || (c >= '\u0BCA' && c <= '\u0BCD')
+ || (c == '\u0BD7')
+ || (c >= '\u0C01' && c <= '\u0C03') || (c >= '\u0C3E' && c <= '\u0C44') || (c >= '\u0C46' && c <= '\u0C48')
+ || (c >= '\u0C4A' && c <= '\u0C4D') || (c >= '\u0C55' && c <= '\u0C56') || (c >= '\u0C82' && c <= '\u0C83')
+ || (c >= '\u0CBE' && c <= '\u0CC4') || (c >= '\u0CC6' && c <= '\u0CC8') || (c >= '\u0CCA' && c <= '\u0CCD')
+ || (c >= '\u0CD5' && c <= '\u0CD6') || (c >= '\u0D02' && c <= '\u0D03') || (c >= '\u0D3E' && c <= '\u0D43')
+ || (c >= '\u0D46' && c <= '\u0D48') || (c >= '\u0D4A' && c <= '\u0D4D')
+ || (c == '\u0D57')
+ || (c == '\u0E31')
+ || (c >= '\u0E34' && c <= '\u0E3A') || (c >= '\u0E47' && c <= '\u0E4E')
+ || (c == '\u0EB1')
+ || (c >= '\u0EB4' && c <= '\u0EB9') || (c >= '\u0EBB' && c <= '\u0EBC') || (c >= '\u0EC8' && c <= '\u0ECD')
+ || (c >= '\u0F18' && c <= '\u0F19')
+ || (c == '\u0F35')
+ || (c == '\u0F37')
+ || (c == '\u0F39')
+ || (c == '\u0F3E')
+ || (c == '\u0F3F')
+ || (c >= '\u0F71' && c <= '\u0F84') || (c >= '\u0F86' && c <= '\u0F8B') || (c >= '\u0F90' && c <= '\u0F95')
+ || (c == '\u0F97')
+ || (c >= '\u0F99' && c <= '\u0FAD') || (c >= '\u0FB1' && c <= '\u0FB7')
+ || (c == '\u0FB9')
+ || (c >= '\u20D0' && c <= '\u20DC')
+ || (c == '\u20E1')
+ || (c >= '\u302A' && c <= '\u302F')
+ || (c == '\u3099')
+ || (c == '\u309A');
+ }*/
+
+ /** Digit - XMl Specification 1.0 [88] */
+ private static final boolean Digit(char c) {
+ return (c >= '\u0030' && c <= '\u0039') || (c >= '\u0660' && c <= '\u0669') || (c >= '\u06F0' && c <= '\u06F9')
+ || (c >= '\u0966' && c <= '\u096F') || (c >= '\u09E6' && c <= '\u09EF') || (c >= '\u0A66' && c <= '\u0A6F')
+ || (c >= '\u0AE6' && c <= '\u0AEF') || (c >= '\u0B66' && c <= '\u0B6F') || (c >= '\u0BE7' && c <= '\u0BEF')
+ || (c >= '\u0C66' && c <= '\u0C6F') || (c >= '\u0CE6' && c <= '\u0CEF') || (c >= '\u0D66' && c <= '\u0D6F')
+ || (c >= '\u0E50' && c <= '\u0E59') || (c >= '\u0ED0' && c <= '\u0ED9') || (c >= '\u0F20' && c <= '\u0F29');
+ }
+
+ /** Extender - XMl Specification 1.0 [89] */
+ private static final boolean Extender(char c) {
+ return c == '\u00B7' || c == '\u02D0' || c == '\u02D1' || c == '\u0387'
+ || c == '\u0640' || c == '\u0E46' || c == '\u0EC6' || c == '\u3005'
+ || (c >= '\u3031' && c <= '\u3035') || (c >= '\u309D' && c <= '\u309E') || (c >= '\u30FC' && c <= '\u30FE');
+ }
+
+ /** Whitespace - XML Specification 1.0 [3] */
+ private static final boolean S(char c) {
+ return c == '\u0020' || c == '\u0009' || c == '\r' || c == '\n';
+ }
+}