diff options
Diffstat (limited to 'jeu-test/Lemmini/0.84/src/Extract/Diff.java')
| -rw-r--r-- | jeu-test/Lemmini/0.84/src/Extract/Diff.java | 641 |
1 files changed, 641 insertions, 0 deletions
diff --git a/jeu-test/Lemmini/0.84/src/Extract/Diff.java b/jeu-test/Lemmini/0.84/src/Extract/Diff.java new file mode 100644 index 0000000..8936128 --- /dev/null +++ b/jeu-test/Lemmini/0.84/src/Extract/Diff.java @@ -0,0 +1,641 @@ +package Extract;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.zip.Adler32;
+
+/*
+ * Copyright 2009 Volker Oth
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Simple diff/patch algorithm for text or binary files
+ * In contrast to common line based diff utilities, this algorithm
+ * works byte based to create small binary difference files.
+ * However this very simple approach is only sensible for small files.
+ * It is by no way meant as rival to full featured approaches like XDelta.
+ *
+ * @author Volker Oth
+ */
+public class Diff {
+ /** insert n bytes */
+ private final static byte INSERT = 0;
+ /** delete n bytes */
+ private final static byte DELETE = 1;
+ /** replace n bytes with n bytes */
+ private final static byte REPLACE = 2;
+ /** substitute n bytes with m bytes */
+ private final static byte SUBSTITUTE = 3;
+
+ /** magic number for header ID */
+ private final static int HEADER_ID = 0xdeadbeef;
+ /** magic number for data ID */
+ private final static int DATA_ID = 0xfade0ff;
+
+ /** print info to System.out */
+ private static boolean verbatim = false;
+
+ /** re-synchronization length */
+ private static int resyncLength = 4;
+ /** re-synchronization window length */
+ private static int windowLength = 512;
+
+ /** target CRC */
+ public static int targetCRC = 0;
+
+ /**
+ * Set diff parameters
+ * @param winLen Length of windows to search for re-synchronization
+ * @param resyncLen Number of equal bytes needed for re-synchronization
+ */
+ public static void setParameters(final int winLen, final int resyncLen) {
+ resyncLength = resyncLen;
+ windowLength = winLen;
+ }
+
+ /**
+ * Create diff buffer from the differences between source and target buffer
+ * @param bsrc source buffer (the file to be patched)
+ * @param btrg target buffer (the file as it should be)
+ * @return buffer of differences
+ */
+ public static byte[] diffBuffers(final byte bsrc[], final byte btrg[]) {
+ ArrayList<Byte> patch = new ArrayList<Byte>();
+ Buffer src = new Buffer(bsrc);
+ Buffer trg = new Buffer(btrg);
+
+ // compare crcs
+ Adler32 crcSrc = new Adler32();
+ crcSrc.update(src.getData());
+ Adler32 crcTrg = new Adler32();
+ crcTrg.update(trg.getData());
+ targetCRC = (int)crcTrg.getValue();
+ if (crcTrg.getValue() == crcSrc.getValue())
+ return null;
+
+ // write header
+ setDWord(patch,HEADER_ID);
+ // write lengths to patch list
+ setLen(patch,src.length());
+ setLen(patch,trg.length());
+ // write crcs to patch list
+ setDWord(patch,(int)crcSrc.getValue());
+ setDWord(patch,(int)crcTrg.getValue());
+ setDWord(patch,DATA_ID);
+
+ // examine source buffer
+ int ofs = 0;
+ while (src.getIndex() < src.length()) {
+ // search for difference
+ int s = src.getByte();
+ int t = trg.getByte();
+ if (s == t) {
+ ofs++;
+ continue;
+ }
+ // reset indeces
+ src.setIndex(src.getIndex()-1);
+ trg.setIndex(trg.getIndex()-1);
+ // write offset
+ setLen(patch,ofs);
+ out("Offset: "+ofs);
+ ofs = 0;
+ // check for insert, delete, replace
+ int len, leni, lend, lenr, lens[];
+ int state = -1;
+
+ leni = checkInsert(src,trg);
+ lend = checkDelete(src,trg);
+ lenr = checkReplace(src,trg);
+ lens = checkSubstitute(src,trg);
+ len = Math.min(leni,lend);
+ len = Math.min(len,lenr);
+ len = Math.min(len,lens[1]);
+ if (len > windowLength) {
+ // completely lost synchronisation
+ int rs = src.length() - src.getIndex();
+ int rt = trg.length() - trg.getIndex();
+ if (rs==rt) {
+ len = rs;
+ state = REPLACE;
+ } else {
+ len = rt;
+ state = INSERT;
+ }
+ break;
+ }
+ if (len == leni)
+ state = INSERT;
+ else if (len == lend)
+ state = DELETE;
+ else if (len == lenr)
+ state = REPLACE;
+ else if (len == lens[1])
+ state = SUBSTITUTE;
+
+ switch (state) {
+ case INSERT :
+ // insert
+ out("Insert: "+len);
+ patch.add(new Byte(INSERT));
+ setLen(patch,len);
+ for (int i = 0; i<len; i++)
+ patch.add(new Byte((byte)trg.getByte()));
+ break;
+ case DELETE:
+ // delete
+ out("Delete: "+len);
+ patch.add(new Byte(DELETE));
+ setLen(patch,len);
+ src.setIndex(src.getIndex()+len);
+ break;
+ case REPLACE:
+ // replace
+ out("Replace: "+len);
+ patch.add(new Byte(REPLACE));
+ setLen(patch,len);
+ for (int i = 0; i<len; i++)
+ patch.add(new Byte((byte)trg.getByte()));
+ src.setIndex(src.getIndex()+len);
+ break;
+ case SUBSTITUTE:
+ // replace
+ out("Substitute: "+lens[0]+"/"+lens[1]);
+ patch.add(new Byte(SUBSTITUTE));
+ setLen(patch,lens[0]);
+ setLen(patch,lens[1]);
+ for (int i = 0; i<lens[1]; i++)
+ patch.add(new Byte((byte)trg.getByte()));
+ src.setIndex(src.getIndex()+lens[0]);
+ break;
+ }
+ }
+
+ // if the files end identically, the offset needs to be written
+ if (ofs != 0) {
+ out("Offset: "+ofs);
+ setLen(patch,ofs);
+ }
+
+ // check for stuff to insert in target
+ if (trg.getIndex() < trg.length()) {
+ patch.add(new Byte(INSERT));
+ int len = trg.length() - trg.getIndex();
+ out("Insert (End): "+len);
+ setLen(patch,len);
+ for (int i = 0; i<len; i++)
+ patch.add(new Byte((byte)trg.getByte()));
+ }
+
+ if (patch.size() == 0)
+ return null;
+
+ out("Patch length: "+patch.size());
+
+ // convert patch list to output byte array
+ byte retVal[] = new byte[patch.size()];
+ for (int i =0; i<retVal.length;i++)
+ retVal[i] = patch.get(i).byteValue();
+ return retVal;
+ }
+
+ /**
+ * Create a target buffer from a source buffer and a buffer of differences
+ * @param bsrc source buffer
+ * @param bpatch buffer containing differences
+ * @return target buffer created from a source buffer and a buffer of differences
+ * @throws DiffException
+ */
+ public static byte[] patchbuffers(final byte bsrc[], final byte bpatch[]) throws DiffException {
+ Buffer src = new Buffer(bsrc);
+ Buffer patch = new Buffer(bpatch);
+ // calculate src crc
+ Adler32 crc = new Adler32();
+ crc.update(src.getData());
+ // analyze header
+ if (patch.getDWord() != Diff.HEADER_ID)
+ throw new DiffException("No header id found in patch");
+ int lenSrc = getLen(patch);
+ if (lenSrc != src.length())
+ throw new DiffException("Size of source differs from that in patch header");
+ int lenTrg = getLen(patch);
+ int crcPatchSrc = patch.getDWord();
+ if (crcPatchSrc != (int)crc.getValue())
+ throw new DiffException("CRC of source (0x"+Integer.toHexString((int)crc.getValue())+
+ ") differs from that in patch header (0x"+Integer.toHexString(crcPatchSrc)+")");
+ int crcTrg = patch.getDWord();
+ if (patch.getDWord() != Diff.DATA_ID)
+ throw new DiffException("No data id found in patch header");
+
+ Buffer trg = new Buffer(lenTrg);
+
+ // step through patch buffer
+ try {
+ while (patch.getIndex()<patch.length()) {
+ int ofs = getLen(patch);
+ out("Offset: "+ofs);
+ // copy bytes from source buffer
+ for (int i=0; i<ofs; i++)
+ trg.setByte((byte)src.getByte());
+ // check for patch buffer empty
+ if (patch.getIndex()==patch.length())
+ break;
+ // now there must follow a command followed by a
+ int cmdIdx = patch.getIndex(); // just for exception
+ int cmd = patch.getByte();
+ int len = getLen(patch);
+ switch (cmd) {
+ case Diff.DELETE:
+ out("Delete: "+len);
+ src.setIndex(src.getIndex()+len);
+ break;
+ case Diff.REPLACE:
+ out("Replace/");
+ src.setIndex(src.getIndex()+len);
+ //$FALL-THROUGH$
+ case Diff.INSERT:
+ out("Insert: "+len);
+ for (int r=0; r<len;r++)
+ trg.setByte((byte)patch.getByte());
+ break;
+ case Diff.SUBSTITUTE: {
+ int lenT = getLen(patch);
+ out("Substitute: "+len+"/"+lenT);
+ src.setIndex(src.getIndex()+len);
+ for (int r=0; r<lenT;r++)
+ trg.setByte((byte)patch.getByte());
+ break; }
+ default:
+ throw new DiffException("Unknown command "+cmd+" at patch offset "+cmdIdx);
+ }
+ }
+ } catch (ArrayIndexOutOfBoundsException ex) {
+ throw new DiffException("Array index exceeds bounds. Patch file corrupt...");
+ }
+
+ // check length
+ if (trg.getIndex() != lenTrg)
+ throw new DiffException("Size of target differs from that in patch header");
+
+ // compare crc
+ crc.reset();
+ crc.update(trg.getData());
+ if (crcTrg != (int)crc.getValue())
+ throw new DiffException("CRC of target differs from that in patch");
+
+ return trg.getData();
+ }
+
+ /**
+ * Lengths/Offset are stored as 7bit values. The 8th bit is used as marker if the number
+ * is continued in the next byte.
+ * @param b Buffer from which to read the length/offset
+ * @return integer value of length/offset
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ private static int getLen(final Buffer b) throws ArrayIndexOutOfBoundsException {
+ int val = 0;
+ int v;
+ int shift = 0;
+ do {
+ v = b.getByte();
+ if ((v & 0x80) == 0) {
+ // no continue bit set
+ val += (v<<shift);
+ break;
+ }
+ // erase contine marker bit
+ v &= 0x7f;
+ val += (v<<shift);
+ shift += 7;
+ } while (true);
+ return val;
+ }
+
+ /**
+ * Store length/offset information in 7bit encoding. A set 8th bit means: continued in next byte
+ * So 127 is stored as 0x7f, but 128 is stored as 0x80 0x01 (where 0x80 means 0, highest bit is marker)
+ * @param l Patch list to add length/offset in 7bit encoding
+ * @param value Value to add in 7bit encoding
+ */
+ private static void setLen(final List<Byte> l, final int value) {
+ int val = value;
+ while ( val > 0x7f) {
+ l.add(new Byte((byte)(val & 0x7f | 0x80)));
+ val >>>= 7;
+ }
+ l.add(new Byte((byte)val));
+ }
+
+ /**
+ * Check for "insert" difference
+ * @param src source buffer
+ * @param trg target buffer
+ * @return number of bytes inserted
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ private static int checkInsert(final Buffer src, final Buffer trg) throws ArrayIndexOutOfBoundsException {
+ byte[] bs = src.getData();
+ int is = src.getIndex();
+ byte[] bt = trg.getData();
+ int it = trg.getIndex();
+ int len = windowLength;
+ if (is+len+resyncLength >= bs.length)
+ len = bs.length - is - resyncLength;
+ if (it+len+resyncLength >= bt.length)
+ len = bt.length - it - resyncLength;
+ for (int w=1; w<len; w++) {
+ int r;
+ for (r = 0; r<resyncLength; r++)
+ if (bs[is+r] != bt[it+w+r])
+ break;
+ if (r == resyncLength)
+ return w;
+ }
+ return Integer.MAX_VALUE;
+ }
+
+ /**
+ * Check for "delete" difference
+ * @param src source buffer
+ * @param trg target buffer
+ * @return number of bytes deleted
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ private static int checkDelete(final Buffer src, final Buffer trg) throws ArrayIndexOutOfBoundsException {
+ byte[] bs = src.getData();
+ int is = src.getIndex();
+ byte[] bt = trg.getData();
+ int it = trg.getIndex();
+ int len = windowLength;
+ if (is+len+resyncLength >= bs.length)
+ len = bs.length - is - resyncLength;
+ if (it+len+resyncLength >= bt.length)
+ len = bt.length - it - resyncLength;
+ for (int w=1; w<len; w++) {
+ int r;
+ for (r = 0; r<resyncLength; r++)
+ if (bs[is+w+r] != bt[it+r])
+ break;
+ if (r == resyncLength)
+ return w;
+ }
+ return Integer.MAX_VALUE;
+ }
+
+ /**
+ * Check for "replace" difference
+ * @param src source buffer
+ * @param trg target buffer
+ * @return number of bytes replaced
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ private static int checkReplace(final Buffer src, final Buffer trg) throws ArrayIndexOutOfBoundsException {
+ byte[] bs = src.getData();
+ int is = src.getIndex();
+ byte[] bt = trg.getData();
+ int it = trg.getIndex();
+ int len = windowLength;
+ if (is+len+resyncLength >= bs.length)
+ len = bs.length - is - resyncLength;
+ if (it+len+resyncLength >= bt.length)
+ len = bt.length - it - resyncLength;
+ for (int w=1; w<len; w++) {
+ int r;
+ for (r = 0; r<resyncLength; r++)
+ if (bs[is+w+r] != bt[it+w+r])
+ break;
+ if (r == resyncLength)
+ return w;
+ }
+ return Integer.MAX_VALUE;
+ }
+
+ /**
+ * Check for "substitute" difference
+ * @param src source buffer
+ * @param trg target buffer
+ * @return integer array: [0]: number of bytes to delete in source, [1]: number of bytes to insert in target
+ * @throws ArrayIndexOutOfBoundsException
+
+ */
+ private static int[] checkSubstitute(final Buffer src, final Buffer trg) throws ArrayIndexOutOfBoundsException {
+ byte[] bs = src.getData();
+ int is = src.getIndex();
+ byte[] bt = trg.getData();
+ int it = trg.getIndex();
+ int len = windowLength;
+ if (is+len+resyncLength >= bs.length)
+ len = bs.length - is - resyncLength;
+ if (it+len+resyncLength >= bt.length)
+ len = bt.length - it - resyncLength;
+
+ ArrayList<int[]> solutions = new ArrayList<int[]>();
+
+ for (int ws=1; ws<len; ws++) {
+ for (int wt=1; wt<len; wt++) {
+ int r;
+ for (r = 0; r<resyncLength; r++)
+ if (bs[is+ws+r] != bt[it+wt+r])
+ break;
+ if (r == resyncLength) {
+ int retVal[] = new int[2];
+ retVal[0] = ws;
+ retVal[1] = wt;
+ solutions.add(retVal);
+ }
+ }
+ }
+
+ if (solutions.size() == 0) {
+ // nothing found
+ int retVal[] = new int[2];
+ retVal[0] = Integer.MAX_VALUE;
+ retVal[1] = Integer.MAX_VALUE;
+ return retVal;
+ }
+
+ // search best solution
+ int sMinIdx = 0;
+ for (int i=1; i<solutions.size(); i++) {
+ int s[] = solutions.get(i);
+ int sMin[] = solutions.get(sMinIdx);
+ if (s[0]+s[1] < sMin[0]+sMin[1])
+ sMinIdx = i;
+ }
+ return solutions.get(sMinIdx);
+ }
+
+ /**
+ * Write DWord to difference list
+ * @param l difference list
+ * @param val DWord value
+ */
+ private static void setDWord(final List<Byte> l, final int val) {
+ l.add(new Byte((byte)val));
+ l.add(new Byte((byte)(val>>8)));
+ l.add(new Byte((byte)(val>>16)));
+ l.add(new Byte((byte)(val>>24)));
+ }
+
+ private static void out(final String s) {
+ if (verbatim)
+ System.out.println(s);
+ }
+}
+
+
+/**
+ * Buffer class that manages reading/writing from/to a byte buffer
+ *
+ * @author Volker Oth
+ */
+class Buffer {
+ /** array of byte which defines the data buffer */
+ private byte buffer[];
+ /** byte index in buffer */
+ private int index;
+
+ /**
+ * Constructor.
+ * @param size buffer size in bytes
+ */
+ Buffer(final int size) {
+ index = 0;
+ buffer = new byte[size];
+ }
+
+ /**
+ * Constructor.
+ * @param b array of byte to use as buffer
+ */
+ Buffer(final byte b[]) {
+ index = 0;
+ buffer = b;
+ }
+
+ /**
+ * Get size of buffer.
+ * @return size of buffer in bytes
+ */
+ int length() {
+ return buffer.length;
+ }
+
+ /**
+ * Get current byte index.
+ * @return current byte index
+ */
+ int getIndex() {
+ return index;
+ }
+
+ /**
+ * Get data buffer.
+ * @return data buffer
+ */
+ byte[] getData() {
+ return buffer;
+ }
+
+ /**
+ * Set index to new byte position.
+ * @param idx index to new byte position
+ */
+ void setIndex(final int idx) {
+ index = idx;
+ }
+
+ /**
+ * Get byte at current position.
+ * @return byte at current position
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ int getByte() throws ArrayIndexOutOfBoundsException {
+ return buffer[index++] & 0xff;
+ }
+
+ /**
+ * Set byte at current position, increase index by 1.
+ * @param val byte value to write
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ void setByte(final byte val) throws ArrayIndexOutOfBoundsException {
+ buffer[index++] = val;
+ }
+
+ /**
+ * Get word (2 bytes, little endian) at current position.
+ * @return word at current position
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ int getWord() throws ArrayIndexOutOfBoundsException {
+ return getByte() | (getByte()<<8);
+ }
+
+ /**
+ * Set word (2 bytes, little endian) at current position, increase index by 2.
+ * @param val word to write at current position
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ void setWord(final int val) throws ArrayIndexOutOfBoundsException {
+ setByte((byte)val);
+ setByte((byte)(val>>8));
+ }
+
+ /**
+ * Get double word (4 bytes, little endian) at current position.
+ * @return dword at current position
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ int getDWord() throws ArrayIndexOutOfBoundsException {
+ return getByte() | (getByte()<<8) | (getByte()<<16) | (getByte()<<24);
+ }
+
+ /**
+ * Set double word (4 bytes, little endian) at current position, increase index by 4.
+ * @param val dword to write at current position
+ * @throws ArrayIndexOutOfBoundsException
+ */
+ void setDWord(final int val) throws ArrayIndexOutOfBoundsException {
+ setByte((byte)val);
+ setByte((byte)(val>>8));
+ setByte((byte)(val>>16));
+ setByte((byte)(val>>24));
+ }
+}
+
+/**
+ * Generic Exception for Diff.
+ * @author Volker Oth
+ */
+class DiffException extends Exception {
+ private final static long serialVersionUID = 0x000000001;
+
+ /**
+ * Constructor.
+ */
+ public DiffException() {
+ super();
+ }
+
+ /**
+ * Constructor.
+ * @param s Exception string
+ */
+ public DiffException(String s) {
+ super(s);
+ }
+}
\ No newline at end of file |