I've attached what I have of the code so far. So far, I only have a bunch of
static methods that work with formatting the BinaryTreeDBR itself, not the
URL. Next, I want to get this to work with URLs and make a format for the
index file (the one without the DBR applied to it yet) that is backwards
compatible with the other DBR format and future compatible with new things.
After that, the actual handlers for responding to theese DBRs can be written.
Hopefully by then I can figure out a good way to attach this to Freenet
(like in FCP or as a client itself).
Scott Young
-------------- next part --------------
/**
* Provides support for powerful time redirection. A BinaryTreeDBR,
* like a regular DBR, redirects users to the most up-to-date page.
* Unlike regular DBRs, a BinaryTreeDBR allows users to insert
* updates whenever they want.
*
* <h3>Format</h3>
*
* <pre>(epoch).(length)(data)</pre>
*
* <p>The first part is the Epoch. This is for future proofing
* BinaryTreeDBRs with time rollovers. The epoch is multiplied by
* 2^32 seconds and then added to the rest of the value. It is
* encoded in big-endian ASCII hexadecimal, and can expand to whatever
* length is needed. The period seperates this from the rest of it.
*
* <p>The second part is the length of the data in bits. It takes two
* nibbles (hex characters) of data, which is the same as one byte.
* The first two bits are reserved for for future use. They are set
* to zero. The next 6 bits represent a big-endian unsigned integer
* (0 to 63). This is more than enough for the rest of the message.
*
* <p>The third part is the actual data. This expands depending on
* the depth of the tree (all bits in the data after the length
* specified above are truncated). The data is in big-endian order,
* with the first bit representing 2^31 seconds, the second bit
* representing 2^30 seconds, ..., the 31st representing 1 second, the
* 32nd representing half a second, the 33rd representing a quarter
* second, etc. With a max of 63 bits, inserts may be as frequent as
* 2^32 times a second. For daily inserting, a total of 8 bytes are
* needed. For example, lets take the time this documentation was
* written (December 13, 2001, or 1008294506 seconds UTC):
*
* <pre>
* Nearest Second: 0.203c195a74
* Nearest Day: 0.103c19
* Nearest Year: 0.073c
* Nearest Decade: 0.047
* Nearest Century: 0.020</pre>
*
* <h3>Inserting</h3>
*
* <p>The node looks at the last BinaryTreeDBR time value inserted,
* and a precise BinaryTreeDBR time representation of the current
* time. It then takes all similar data bits of the two, then adds
* the next uncommon bit of the new time. The rest of the time format
* changes accordingly, and the file is inserted with that time. For
* example:
*
* <pre>
* Previous Insert Time: 0.093ca Data: 0011 1100 101
* Current Time: 0.203cecfade Data: 0011 1100 1110 1100 ...
* Next Insert Time: 0.083cc Data: 0011 1100 11
*
* Previous Insert Time: 0.063c Data: 0011 11
* Current Time: 0.203cecfade Data: 0011 1100 0001 1110 ...
* Next Insert Time: 0.073c Data: 0011 110
* </pre>
*
*
*
* <h3>Requesting</h3>
*
* <p>Like with a DBR, an index file tells the client to get the most
* recent version of the document. For a BinaryTreeDBR, the client
* takes the most accurate time it has, then searches "up" by
* decreasing that accuracy. For example, if the time is 1008294506
* UTC (<code>0.203c194a74</code> in BinaryTreeDBR format), the
* following values would be requested, in order (the data in binary
* has been included to help show what is actually happening):
*
* <pre>
* 0.203c194a74 data: 0011 1100 0001 1001 0010 1010 0111 0010
* 0.1f3c194a74 data: 0011 1100 0001 1001 0010 1010 0111 001
* 0.1e3c194a7 data: 0011 1100 0001 1001 0010 1010 0111 00
* 0.1d3c194a7 data: 0011 1100 0001 1001 0010 1010 0111 0
* 0.1c3c194a7 data: 0011 1100 0001 1001 0010 1010 0111
* 0.1b3c194a6 data: 0011 1100 0001 1001 0010 1010 011
* 0.1a3c194a4 data: 0011 1100 0001 1001 0010 1010 01
* 0.193c194a data: 0011 1100 0001 1001 0010 1010 0
* 0.183c194a data: 0011 1100 0001 1001 0010 1010
* 0.173c194a data: 0011 1100 0001 1001 0010 101
* 0.163c1948 data: 0011 1100 0001 1001 0010 10
* 0.153c1948 data: 0011 1100 0001 1001 0010 1
* 0.143c194 data: 0011 1100 0001 1001 0010</pre>
*
* <p>and so forth, until a key actually returns. When a key is
* found, the data is downloaded and displayed to the user. While the
* user is looking at the slightly older page, Freenet continues to
* download the data but traversing the tree downward. For example,
* if <code>0.1c3c194a7</code> is the most recent one retrieved in the
* above path, the node would then look for <code>0.1dc194a78</code>
* and <code>0.1dc194a7</code>. It takes the more recent time that is
* found (in this case, <code>0.1dc194a78</code> if it is found). It
* then takes that time and looks at the next time below it. For
* consistent site insert intervals, this downward traversal does not
* take more than two iterations.
*
*
*
* @author Scott Young
*
* @see java.util.Date
* @see java.util.Calendar
* @see Freenet.key
* @see #isValidFormat(String)
* */
public class BinaryTreeDBR {
/**
* Currently, the "root" branch does not support the epoch. This
* will have to be modified before Jan. 11 2038.
* */
private Branch root;
public BinaryTreeDBR(Key root) {
}
private static Key request(String time) {
return null;
}
public Branch getMostRecent() {
Branch current=root;
while(true) {
if(current.right!=null) current=current.right;
else if(current.left!=null) current=current.left;
else return current;
}
}
/**
* Used for debugging.
* */
public static void main(String[] args) {
}
/**
* Gives the current time formatted in the BinaryTreeDBR format.
* It is accurate to the nearest millisecond.
* */
public static String getCurrentTime() {
return getTime(System.currentTimeMillis(),43);
}
/**
* Encodes <code>time</code> in the BinaryTreeDBR format with the
* specified epoch.
*
* @param time an big-endian binary encoding of the time.
* @param epoch adds <code>epoch * 2^32</code> seconds to the returned
string.
* @see #getTime(long,int)
* @see #getTimeFromSeconds(long,int)
*
* */
public static String getTime(int epoch,boolean[] time) {
checkPrecision(time.length);
StringBuffer s=new StringBuffer(Integer.toString(epoch,16)+".");
s.append(Integer.toString((time.length>>4)&15,16)
+Integer.toString((time.length&15),16));
int i=3;
for(;i<time.length;i+=4)
s.append(toHex(time[i-3],time[i-2],time[i-1],time[i]));
int val=time.length%4;
if(val!=0)
s.append(toHex(val>0?time[i-3]:false,val>1?time[i-2]:
false,val>2?time[i-1]:false,val>3?time[i]:false));
return s.toString();
}
/**
* Encodes <code>time</code>, in milliseconds in the BinaryTreeDBR
* format, with the specified <code>precision</code>.
*
* @param precision the number of significant bits for the BinaryTreeDBR
* @see #getTimeFromSeconds(long,int)
* @see #getTime(int,boolean[])
* @see #getPrecision(String)
* @see #getEpoch(String)
* @see #getTime(String)
* @see #getTimeInSeconds(String)
* */
public static String getTime(long time,int precision) {
checkPrecision(precision);
// this allows for 48 bits of precision for representing the
// milliseconds, although only a maximum of 31 are needed
// because of the 63-bit prcision limit
long millis=((time%1000L)<<48)/1000L;
time=time/1000L;
long seconds=time%(0x100000000L);
StringBuffer b=new StringBuffer();
b.append(Long.toString(time>>32,16)); // add epoch
b.append(".");
b.append(Integer.toString((precision>>4)&3,16)+Integer.toString(precision&15,16));
int milliPrecision=precision>0?precision-32:0;
if(precision>32) precision=32;
long mask=((1L<<precision)-1L)<<(32-precision);
// ORing with 1L<<32 ensures that lefthand zeros are added.
b.append(Long.toString((1L<<32)|(mask&seconds),16).substring(1));
if(milliPrecision>0) {
if(milliPrecision>48) milliPrecision=48;
// this might need checking. I'm not sure if this
// correctly converts decimal to binary, but several tests
// seem to work.
mask=((1L<<milliPrecision)-1L)<<(48-milliPrecision);
b.append(Long.toString((1L<<48)|(mask&millis),16).substring(1));
}
return trim0s(b.toString());
}
/**
* Returns a BinaryTreeDBR String value with a new precision.
* @see #changePrecision(boolean[],int)
* */
public static String changePrecision(String s,int newPrecision) {
return getTime(getEpoch(s),
changePrecision(getBooleanTime(s),newPrecision));
}
/**
* Returns a BinaryTreeDBR boolean array whith a new precision.
* If <code>newPrecision</code> is less than b's length/precision,
* the extra values in b are truncated. If
* <code>newPrecision</code> is more than b's precision, falses
* are appended to the end.
* @see #changePrecision(String,int)
* */
public static boolean[] changePrecision(boolean[] b,int newPrecision) {
boolean[] result=new boolean[newPrecision];
System.arraycopy(b,0,result,0,Math.min(b.length,newPrecision));
return result;
}
/**
* Returns a BinaryTreeDBR String with the precision increased by
* one and the bit <code>b</code> added at that place. For
* example, 0.06a4 (101001) pushed with 1 would give 0.07a6
* (1010011).
*
* @see #pop(String)
* */
public static String push(String s,boolean b) {
boolean[] time=getBooleanTime(s);
boolean[] result=new boolean[time.length+1];
System.arraycopy(time,0,result,0,time.length);
result[time.length]=b;
return getTime(getEpoch(s),result);
}
/**
* Returns a BinarytreeDBR String with the precision decreased by
* one.
*
* @see #push(String,boolean)
* */
public static String pop(String s) {
return getTime(getEpoch(s),changePrecision(
getBooleanTime(s),getPrecision(s)-1));
}
/**
* Encodes <code>time</code>, in seconds in the BinaryTreeDBR
* format, with the specified <code>precision</code>.
*
* @param precision the number of significant bits for the BinaryTreeDBR
* @see #getTime(long,int)
* */
public static String getTimeFromSeconds(long seconds,int precision) {
checkPrecision(precision);
StringBuffer b=new StringBuffer();
b.append(Long.toString(seconds>>32,16)); // add epoch
b.append(".");
b.append(Integer.toString((precision>>4)&3,16));
b.append(Integer.toString(precision&15,16));
int milliPrecision=precision>0?precision-0x20:0;
if(precision>0x20) precision=0x20; // max precision for seconds
long mask=((1L<<precision)-1L)<<(32-precision);
b.append(trim0s(Long.toString((1L<<32)|(mask&seconds),16).substring(1)));
return b.toString();
}
/**
* Gets a boolean array representing the data in the specified
* BinaryTreeDBR String. The length of the returned value is
* equal to the precision of <code>s</code>. The values of the
* returned array are sorted from most significant (2^31 seconds)
* to least significant. The epoch in <code>s</code> is ignored.
*
* @see #getPrecision(String)
* @see #getEpoch(String)
* @see #getTime(int,boolean[])
* */
public static boolean[] getBooleanTime(String s) {
checkValidFormat(s);
int startIndex=s.indexOf(".")+3;
boolean[] b=new boolean[getPrecision(s)];
String data=s.substring(startIndex,s.length());
for(int i=0;i<data.length();i++) {
int digit=Character.digit(data.charAt(i),16);
for(int j=0;j<4;j++)
if(3+4*i-j<b.length)
b[3+4*i-j]=((digit>>j)&1)==1;
}
return b;
}
/**
* Gets the time, in milliseconds, represented by the sepecified
* BinaryTreeDBR String.
* @see #getTimeInSeconds(String)
* */
public static long getTimeInMillis(String s) {
checkValidFormat(s);
long seconds=((long)getEpoch(s))<<32;
boolean[] time=getBooleanTime(s);
int i=0;
for(;i<Math.min(31,time.length);i++)
if(time[i]) seconds|=1L<<(31-i);
float millis=0;
if(i==31) // this block needs checking
for(float k=500.0f;i<time.length && k>=1;i++,k/=2.0f)
if(time[i]) millis+=k;
return (seconds*1000)+((long)Math.round(Math.floor(millis)));
}
/**
* Gets the time, in seconds, represented by the specified
* BinaryTreeDBR String. If <code>s</code> is more accurate than
* a second, the greatest integer time less than that is returned.
* @see #getTimeInMillis(String)
* */
public static long getTimeInSeconds(String s) {
checkValidFormat(s);
long seconds=((long)getEpoch(s))<<32;
boolean[] time=getBooleanTime(s);
for(int i=0;i<Math.min(31,time.length);i++)
if(time[i]) seconds|=1L<<(31-i);
return seconds;
}
/**
* Extracts the bit precision value from the specified
* BinaryTreeDBR value.
* @exception IllegalArgumentException if <code>s</code> is malformed.
* @see #checkPrecision(int)
* */
public static int getPrecision(String s) {
checkValidFormat(s);
int startIndex=s.indexOf(".")+1;
return Integer.parseInt(s.substring(startIndex,startIndex+2),16);
}
/**
* Extracts and parses the epoch field in the specified String.
* */
public static int getEpoch(String s) {
checkValidFormat(s);
return Integer.parseInt(s.substring(0,s.indexOf(".")),16);
}
/**
* Determines wether the specified string is in a valid
* BinaryTreeDBR format. The format has the following rules:
*
* <ol>
*
* <li>It must only contain hex characters, except for one period.
*
* <li>The epoch must not have any leading 0s, unless it
* represents the value 0 itself, in which case only one 0 is
* used. For example, use 34.12345 instead of 034.12345.
*
* <li>There must be a period seperating the epoch from the rest
* of the BinaryTreeDBR.
*
* <li>There must be at least 2 hex chars after the period.
* Theese two are for the precision.
*
* <li>The first hex char after the period must be less than 4.
* This is because the first two bits are reserved.
*
* <li>The data must not have any more precision than specified by
* the precision field. The precision refers to the individual
* bits, so any bit after that length must be zero. For example,
* 0.028 is valid because the data represents 10 (the trailing 0
* bits after the precision are ignored), but 0.022 is not valid
* because the data represents 001, which is more than 2 bits of
* precision.
*
* <li>The data may not end with the hex digit 0; the trailing
* hex 0s should be stripped. If there is no significant value in
* the data, no value for the data is appended (e.g. 0.05 is 00000
* in binary).
*
* </ol>
*
* @return true if <code>s</code> is a valid BinaryTreeDBR.
* @see #checkValidFormat(String)
* */
public static boolean isValidFormat(String s) {
try {
checkValidFormat(s);
return true;
} catch(IllegalArgumentException i) {
return false;
}
}
/**
* Throws an exception if the specified string is not in a valid
* BinaryTreeDBR format. See {@link #isValidFormat(String)} for
* details.
* FIXME: this should be rewritten to check for errors in the
* order specifed in {@link #isValidFormat(String)}. This would
* help the error reporting.
*
* @exception IllegalArgumentException if <code>s</code> is not a valid
BinaryTreeDBR strng.
* @see #isValidFormat(String)
* */
public static void checkValidFormat(String s) {
int i=0;
int length=s.length();
char ch;
if(length<4) throw new IllegalArgumentException(
"Min size for a BinaryTreeDBR is 4 characters.\nValue: "+s);
if(s.charAt(0)=='0' && s.charAt(1)!='.')
throw new IllegalArgumentException("No leading 0s allowed.\nValue:
"+s);
while(Character.digit(ch=s.charAt(i++),16)!=-1);
if(i==1) throw new IllegalArgumentException(
"Illegal start of BinaryTreeDBR. Must start with a "+
"valid hex character.\nValue: "+s);
if((ch=s.charAt(i-1))!='.') throw new
IllegalArgumentException("Expected '.' at index"+(i-1)+
". Found "+ch+".\nValue: "+s);
if(i+2>length) throw new IllegalArgumentException("Minimum of"+
"2 bytes required after period.\nValue: "+s);
int precision=Integer.parseInt(s.substring(i,i+2),16);
i+=2;
if(precision>=0x40 || precision<=0) throw new
IllegalArgumentException("Invalid precision: "+
precision+". Must be be between 0 and 64 exclusive."
+"\nValue: "+s);
precision-=(length-i)*4; // precision changes to extra precision
if(precision<-3) throw new IllegalArgumentException(
"Too many hex chars of precision\nValue: "+s);
while(i<length && Character.digit(ch=s.charAt(i++),16)!=-1);
if(ch=='0') throw new IllegalArgumentException(
"Trailing zeros not allowed\nValue: "+s);
int digit=Character.digit(ch,16);
if(precision<0 && !(digit%(1<<-precision)==0))
throw new IllegalArgumentException(
"Extra precision in last hex character.\nValue: "+s);
}
/**
* Ensures that the specified <code>precision</code> within the
* accepted range for BinaryTreeDBRs. The accepted range is
* between 0 and 64 exclusive. If it is not in the accepted
* range, an IllegalArgumentException is thrown. This is useful
* in other code that handles precisions.
* @exception IllegalArgumentException if <code>precision</code> is not a
valid value
* */
public static void checkPrecision(int precision) {
if(precision>=0x40 || precision<=0)
throw new IllegalArgumentException("Invalid Precision: "+precision);
}
/**
* Removes trailing zeros from a string.
*/
private static String trim0s(String s) {
int i;
for(i=s.length()-1;i>=0 && (s.charAt(i)=='0');i--);
return s.substring(0,i+1);
}
/**
* Returns a corresponding hex digit with </code>a</code> as the
* MSB and <code>d</code> as the LSB.
* */
private static char toHex(boolean a,boolean b,boolean c,boolean d) {
return Character.forDigit((a?8:0)+(b?4:0)+(c?2:0)+(d?1:0),16);
}
/**
* Represents a branch in the tree.
*/
public class Branch {
private Branch left; // lower sub-value
private Branch right; // upper sub-vaue
private Branch parent;
private Key key;
private Branch(Branch parent,Key key) {
this.parent=parent;
this.key=key;
}
// Constructor for implied branches
private Branch(Branch parent) {
this.parent=parent;
}
public int getDepth() {
return isRoot()?0:parent.getDepth()+1;
}
public boolean isRoot() {
return parent==null;
}
public Branch getLeft(long timeout) {
if(left!=null) return left;
left=new Branch(this,BinaryTreeDBR.request(long timeout));
return left;
}
public Branch getRight(long timeout) {
if(right!=null) return right;
}
public boolean[] getValue() {
boolean[] bool=new boolean[getDepth()];
Branch branch=this;
for(int i=bool.length;!branch.isRoot();i--)
bool[i]=branch.parent.right.equals(branch);
return bool;
}
public String toString() {
return BinaryTreeDBR.getTime(0,getValue());
}
}
// temporary holder until real keys are used
private static class Key { }
}
