001: // kelondroBase64Order.java
002: // -----------------------
003: // part of The Kelondro Database
004: // (C) by Michael Peter Christen; mc@anomic.de
005: // first published on http://www.anomic.de
006: // Frankfurt, Germany, 2005
007: // created 03.01.2006
008: //
009: // $LastChangedDate: 2008-02-03 02:23:04 +0000 (So, 03 Feb 2008) $
010: // $LastChangedRevision: 4431 $
011: // $LastChangedBy: orbiter $
012: //
013: // This program is free software; you can redistribute it and/or modify
014: // it under the terms of the GNU General Public License as published by
015: // the Free Software Foundation; either version 2 of the License, or
016: // (at your option) any later version.
017: //
018: // This program is distributed in the hope that it will be useful,
019: // but WITHOUT ANY WARRANTY; without even the implied warranty of
020: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
021: // GNU General Public License for more details.
022: //
023: // You should have received a copy of the GNU General Public License
024: // along with this program; if not, write to the Free Software
025: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
026: //
027: // Using this software in any meaning (reading, learning, copying, compiling,
028: // running) means that you agree that the Author(s) is (are) not responsible
029: // for cost, loss of data or any harm that may be caused directly or indirectly
030: // by usage of this softare or this documentation. The usage of this software
031: // is on your own risk. The installation and usage (starting/running) of this
032: // software may allow other people or application to access your computer and
033: // any attached devices and is highly dependent on the configuration of the
034: // software which must be done by the user of the software; the author(s) is
035: // (are) also not responsible for proper configuration and usage of the
036: // software, even if provoked by documentation provided together with
037: // the software.
038: //
039: // Any changes to this file according to the GPL as documented in the file
040: // gpl.txt aside this file in the shipment you received can be done to the
041: // lines that follows this copyright notice here, but changes must not be
042: // done inside the copyright notive above. A re-distribution must contain
043: // the intact and unchanged copyright notice.
044: // Contributions and changes to the program code must be marked as such.
045:
046: package de.anomic.kelondro;
047:
048: import java.io.UnsupportedEncodingException;
049: import java.util.Comparator;
050:
051: import de.anomic.server.logging.serverLog;
052:
053: public class kelondroBase64Order extends kelondroAbstractOrder<byte[]>
054: implements kelondroByteOrder, kelondroCoding,
055: Comparator<byte[]> {
056:
057: protected static final char[] alpha_standard = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
058: .toCharArray();
059: protected static final char[] alpha_enhanced = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
060: .toCharArray();
061: protected static final byte[] ahpla_standard = new byte[128];
062: protected static final byte[] ahpla_enhanced = new byte[128];
063:
064: static {
065: for (int i = 0; i < 128; i++) {
066: ahpla_standard[i] = -1;
067: ahpla_enhanced[i] = -1;
068: }
069: for (int i = 0; i < alpha_standard.length; i++) {
070: ahpla_standard[alpha_standard[i]] = (byte) i;
071: ahpla_enhanced[alpha_enhanced[i]] = (byte) i;
072: }
073: }
074:
075: private final serverLog log;
076:
077: public static final kelondroBase64Order standardCoder = new kelondroBase64Order(
078: true, true);
079: public static final kelondroBase64Order enhancedCoder = new kelondroBase64Order(
080: true, false);
081: public static final Comparator<String> standardComparator = new kelondroByteOrder.StringOrder(
082: standardCoder);
083: public static final Comparator<String> enhancedComparator = new kelondroByteOrder.StringOrder(
084: enhancedCoder);
085:
086: private boolean rfc1113compliant;
087: private final char[] alpha;
088: private final byte[] ahpla;
089:
090: public kelondroBase64Order(boolean up, boolean rfc1113compliant) {
091: // if we choose not to be rfc1113compliant,
092: // then we get shorter base64 results which are also filename-compatible
093: this .rfc1113compliant = rfc1113compliant;
094: this .asc = up;
095: alpha = (rfc1113compliant) ? alpha_standard : alpha_enhanced;
096: ahpla = (rfc1113compliant) ? ahpla_standard : ahpla_enhanced;
097:
098: this .log = new serverLog("BASE64");
099: }
100:
101: public static byte[] zero(int length) {
102: byte[] z = new byte[length];
103: while (length > 0) {
104: length--;
105: z[length] = (byte) alpha_standard[0];
106: }
107: return z;
108: }
109:
110: public kelondroOrder<byte[]> clone() {
111: kelondroBase64Order o = new kelondroBase64Order(this .asc,
112: this .rfc1113compliant);
113: o.rotate(zero);
114: return o;
115: }
116:
117: public final boolean wellformed(byte[] a) {
118: return wellformed(a, 0, a.length);
119: }
120:
121: public final boolean wellformed(byte[] a, int astart, int alength) {
122: assert (astart + alength <= a.length) : "astart = " + astart
123: + ", alength = " + alength + ", a.length = " + a.length;
124: int b;
125: for (int i = astart + alength - 1; i >= astart; i--) {
126: b = a[i];
127: if ((b < 0) || (b >= 128) || (ahpla[b] == -1))
128: return false;
129: }
130: return true;
131: }
132:
133: public final static kelondroByteOrder bySignature(String signature) {
134: if (signature.equals("Bd"))
135: return new kelondroBase64Order(false, false);
136: if (signature.equals("bd"))
137: return new kelondroBase64Order(false, true);
138: if (signature.equals("Bu"))
139: return new kelondroBase64Order(true, false);
140: if (signature.equals("bu"))
141: return new kelondroBase64Order(true, true);
142: return null;
143: }
144:
145: public final String signature() {
146: if ((!asc) && (!rfc1113compliant))
147: return "Bd";
148: if ((!asc) && (rfc1113compliant))
149: return "bd";
150: if ((asc) && (!rfc1113compliant))
151: return "Bu";
152: if ((asc) && (rfc1113compliant))
153: return "bu";
154: return null;
155: }
156:
157: public final char encodeByte(byte b) {
158: return (char) alpha[b];
159: }
160:
161: public final byte decodeByte(char b) {
162: return ahpla[b];
163: }
164:
165: public final String encodeLongSmart(long c, int length) {
166: if (c >= max(length)) {
167: StringBuffer s = new StringBuffer(length);
168: s.setLength(length);
169: while (length > 0)
170: s.setCharAt(--length, alpha[63]);
171: return new String(s);
172: }
173: return encodeLong(c, length);
174: }
175:
176: public final String encodeLong(long c, int length) {
177: StringBuffer s = new StringBuffer(length);
178: s.setLength(length);
179: while (length > 0) {
180: s.setCharAt(--length, alpha[(byte) (c & 0x3F)]);
181: c >>= 6;
182: }
183: return new String(s);
184: }
185:
186: public final void encodeLong(long c, byte[] b, int offset,
187: int length) {
188: assert offset + length <= b.length;
189: while (length > 0) {
190: b[--length + offset] = (byte) alpha[(byte) (c & 0x3F)];
191: c >>= 6;
192: }
193: }
194:
195: public final long decodeLong(String s) {
196: while (s.endsWith("="))
197: s = s.substring(0, s.length() - 1);
198: long c = 0;
199: for (int i = 0; i < s.length(); i++)
200: c = (c << 6) | ahpla[s.charAt(i)];
201: return c;
202: }
203:
204: public final long decodeLong(byte[] s, int offset, int length) {
205: while ((length > 0) && (s[offset + length - 1] == '='))
206: length--;
207: long c = 0;
208: for (int i = 0; i < length; i++)
209: c = (c << 6) | ahpla[s[offset + i]];
210: return c;
211: }
212:
213: public static long max(int len) {
214: // computes the maximum number that can be coded with a base64-encoded
215: // String of base len
216: long c = 0;
217: for (int i = 0; i < len; i++)
218: c = (c << 6) | 63;
219: return c;
220: }
221:
222: public final String encodeString(String in) {
223: try {
224: return encode(in.getBytes("UTF-8"));
225: } catch (UnsupportedEncodingException e) {
226: return "";
227: }
228: }
229:
230: // we will use this encoding to encode strings with 2^8 values to
231: // b64-Strings
232: // we will do that by grouping each three input bytes to four output bytes.
233: public final String encode(byte[] in) {
234: if (in.length == 0)
235: return "";
236: StringBuffer out = new StringBuffer(in.length / 3 * 4 + 3);
237: int pos = 0;
238: long l;
239: while (in.length - pos >= 3) {
240: l = ((((0XffL & (long) in[pos]) << 8) + (0XffL & (long) in[pos + 1])) << 8)
241: + (0XffL & (long) in[pos + 2]);
242: pos += 3;
243: out = out.append(encodeLong(l, 4));
244: }
245: // now there may be remaining bytes
246: if (in.length % 3 != 0)
247: out = out
248: .append((in.length % 3 == 2) ? encodeLong(
249: (((0XffL & (long) in[pos]) << 8) + (0XffL & (long) in[pos + 1])) << 8,
250: 4).substring(0, 3)
251: : encodeLong(
252: (((0XffL & (long) in[pos])) << 8) << 8,
253: 4).substring(0, 2));
254: if (rfc1113compliant)
255: while (out.length() % 4 > 0)
256: out.append("=");
257: // return result
258: return new String(out);
259: }
260:
261: public final String decodeString(String in, String info) {
262: try {
263: //return new String(decode(in), "ISO-8859-1");
264: return new String(decode(in, info), "UTF-8");
265: } catch (java.io.UnsupportedEncodingException e) {
266: System.out.println("internal error in base64: "
267: + e.getMessage());
268: return null;
269: }
270: }
271:
272: public final byte[] decode(String in, String info) {
273: if ((in == null) || (in.length() == 0))
274: return new byte[0];
275: try {
276: int posIn = 0;
277: int posOut = 0;
278: if (rfc1113compliant)
279: while (in.charAt(in.length() - 1) == '=')
280: in = in.substring(0, in.length() - 1);
281: byte[] out = new byte[in.length()
282: / 4
283: * 3
284: + (((in.length() % 4) == 0) ? 0
285: : in.length() % 4 - 1)];
286: long l;
287: while (posIn + 3 < in.length()) {
288: l = decodeLong(in.substring(posIn, posIn + 4));
289: out[posOut + 2] = (byte) (l % 256);
290: l = l / 256;
291: out[posOut + 1] = (byte) (l % 256);
292: l = l / 256;
293: out[posOut] = (byte) (l % 256);
294: l = l / 256;
295: posIn += 4;
296: posOut += 3;
297: }
298: if (posIn < in.length()) {
299: if (in.length() - posIn == 3) {
300: l = decodeLong(in.substring(posIn) + "A");
301: l = l / 256;
302: out[posOut + 1] = (byte) (l % 256);
303: l = l / 256;
304: out[posOut] = (byte) (l % 256);
305: l = l / 256;
306: } else {
307: l = decodeLong(in.substring(posIn) + "AA");
308: l = l / 256 / 256;
309: out[posOut] = (byte) (l % 256);
310: l = l / 256;
311: }
312: }
313: return out;
314: } catch (ArrayIndexOutOfBoundsException e) {
315: // maybe the input was not base64
316: // throw new RuntimeException("input probably not base64");
317: this .log.logFine("wrong string receive: " + in + ", call: "
318: + info);
319: return new byte[0];
320: }
321: }
322:
323: private final long cardinalI(byte[] key) {
324: // returns a cardinal number in the range of 0 .. Long.MAX_VALUE
325: long c = 0;
326: int p = 0;
327: while ((p < 10) && (p < key.length))
328: c = (c << 6) | ahpla[key[p++]];
329: while (p++ < 10)
330: c = (c << 6);
331: c = c << 3;
332: return c;
333: }
334:
335: public final long cardinal(byte[] key) {
336: if (this .zero == null)
337: return cardinalI(key);
338: long zeroCardinal = cardinalI(this .zero);
339: long keyCardinal = cardinalI(key);
340: if (keyCardinal > zeroCardinal)
341: return keyCardinal - zeroCardinal;
342: return Long.MAX_VALUE - keyCardinal + zeroCardinal;
343: }
344:
345: private static final int sig(int x) {
346: return (x > 0) ? 1 : (x < 0) ? -1 : 0;
347: }
348:
349: public final int compare(byte[] a, byte[] b) {
350: return (asc) ? compare0(a, 0, a.length, b, 0, b.length)
351: : compare0(b, 0, b.length, a, 0, a.length);
352: }
353:
354: public final int compare(byte[] a, int aoffset, int alength,
355: byte[] b, int boffset, int blength) {
356: return (asc) ? compare0(a, aoffset, alength, b, boffset,
357: blength) : compare0(b, boffset, blength, a, aoffset,
358: alength);
359: }
360:
361: public final int compare0(byte[] a, int aoffset, int alength,
362: byte[] b, int boffset, int blength) {
363: if (zero == null)
364: return compares(a, aoffset, alength, b, boffset, blength);
365: // we have an artificial start point. check all combinations
366: int az = compares(a, aoffset, alength, zero, 0, Math.min(
367: alength, zero.length)); // -1 if a < z; 0 if a == z; 1 if a > z
368: int bz = compares(b, boffset, blength, zero, 0, Math.min(
369: blength, zero.length)); // -1 if b < z; 0 if b == z; 1 if b > z
370: if (az == bz)
371: return compares(a, aoffset, alength, b, boffset, blength);
372: return sig(az - bz);
373: }
374:
375: public final int compares(byte[] a, int aoffset, int alength,
376: byte[] b, int boffset, int blength) {
377: assert (aoffset + alength <= a.length) : "a.length = "
378: + a.length + ", aoffset = " + aoffset + ", alength = "
379: + alength;
380: assert (boffset + blength <= b.length) : "b.length = "
381: + b.length + ", boffset = " + boffset + ", blength = "
382: + blength;
383: assert (ahpla.length == 128);
384: int i = 0;
385: final int al = Math.min(alength, a.length - aoffset);
386: final int bl = Math.min(blength, b.length - boffset);
387: byte ac, bc;
388: byte acc, bcc;
389: while ((i < al) && (i < bl)) {
390: assert (i + aoffset < a.length) : "i = " + i
391: + ", aoffset = " + aoffset + ", a.length = "
392: + a.length + ", a = "
393: + serverLog.arrayList(a, aoffset, al);
394: assert (i + boffset < b.length) : "i = " + i
395: + ", boffset = " + boffset + ", b.length = "
396: + b.length + ", b = "
397: + serverLog.arrayList(b, boffset, al);
398: ac = a[aoffset + i];
399: assert (ac >= 0) && (ac < 128) : "ac = " + ac + ", a = "
400: + serverLog.arrayList(a, aoffset, al);
401: bc = b[boffset + i];
402: if ((ac == 0) && (bc == 0))
403: return 0; // zero-terminated length
404: assert (bc >= 0) && (bc < 128) : "bc = " + bc + ", b = "
405: + serverLog.arrayList(b, boffset, al);
406: acc = ahpla[ac];
407: assert (acc >= 0) : "acc = " + acc + ", a = "
408: + serverLog.arrayList(a, aoffset, al) + "/"
409: + new String(a, aoffset, al) + ", aoffset = 0x"
410: + Integer.toHexString(aoffset) + ", i = " + i
411: + "\n" + serverLog.table(a, 16, aoffset);
412: bcc = ahpla[bc];
413: assert (bcc >= 0) : "bcc = " + bcc + ", b = "
414: + serverLog.arrayList(b, boffset, al) + "/"
415: + new String(b, boffset, al) + ", boffset = 0x"
416: + Integer.toHexString(boffset) + ", i = " + i
417: + "\n" + serverLog.table(b, 16, boffset);
418: if (acc > bcc)
419: return 1;
420: if (acc < bcc)
421: return -1;
422: // else the bytes are equal and it may go on yet undecided
423: i++;
424: }
425: // compare length
426: if (al > bl)
427: return 1;
428: if (al < bl)
429: return -1;
430: // they are equal
431: return 0;
432: }
433:
434: public final int comparePivot(byte[] compiledPivot, byte[] b,
435: int boffset, int blength) {
436: assert zero == null;
437: assert asc;
438: assert (boffset + blength <= b.length) : "b.length = "
439: + b.length + ", boffset = " + boffset + ", blength = "
440: + blength;
441: int i = 0;
442: final int bl = Math.min(blength, b.length - boffset);
443: byte acc, bcc;
444: while ((i < compiledPivot.length) && (i < bl)) {
445: acc = compiledPivot[i];
446: bcc = ahpla[b[boffset + i]];
447: if (acc > bcc)
448: return 1;
449: if (acc < bcc)
450: return -1;
451: // else the bytes are equal and it may go on yet undecided
452: i++;
453: }
454: // compare length
455: if (compiledPivot.length > bl)
456: return 1;
457: if (compiledPivot.length < bl)
458: return -1;
459: // they are equal
460: return 0;
461: }
462:
463: public final byte[] compilePivot(byte[] a, int aoffset, int alength) {
464: assert (aoffset + alength <= a.length) : "a.length = "
465: + a.length + ", aoffset = " + aoffset + ", alength = "
466: + alength;
467: byte[] cp = new byte[Math.min(alength, a.length - aoffset)];
468: for (int i = cp.length - 1; i >= 0; i--) {
469: cp[i] = ahpla[a[aoffset + i]];
470: assert cp[i] != -1;
471: }
472: return cp;
473: }
474:
475: public static void main(String[] s) {
476: kelondroBase64Order b64 = new kelondroBase64Order(true, true);
477: if (s.length == 0) {
478: System.out.println("usage: -[ec|dc|es|ds|s2m] <arg>");
479: System.exit(0);
480: }
481: if (s[0].equals("-ec")) {
482: // generate a b64 encoding from a given cardinal
483: System.out.println(b64.encodeLong(Long.parseLong(s[1]), 4));
484: }
485: if (s[0].equals("-dc")) {
486: // generate a b64 decoding from a given cardinal
487: System.out.println(b64.decodeLong(s[1]));
488: }
489: if (s[0].equals("-es")) {
490: // generate a b64 encoding from a given string
491: System.out.println(b64.encodeString(s[1]));
492: }
493: if (s[0].equals("-ds")) {
494: // generate a b64 decoding from a given string
495: System.out.println(b64.decodeString(s[1], ""));
496: }
497: }
498: }
|