001: /*
002: * ====================================================================
003: * Copyright (c) 2004-2008 TMate Software Ltd. All rights reserved.
004: *
005: * This software is licensed as described in the file COPYING, which
006: * you should have received as part of this distribution. The terms
007: * are also available at http://svnkit.com/license.html
008: * If newer versions of this license are posted there, you may use a
009: * newer version instead, at your option.
010: * ====================================================================
011: */
012: package org.tmatesoft.svn.core.internal.delta;
013:
014: import java.util.HashMap;
015: import java.util.Map;
016:
017: /**
018: * @version 1.1.1
019: * @author TMate Software Ltd.
020: */
021: public class SVNXDeltaAlgorithm extends SVNDeltaAlgorithm {
022:
023: private static final int MATCH_BLOCK_SIZE = 64;
024:
025: public void computeDelta(byte[] a, int aLength, byte[] b,
026: int bLength) {
027: if (bLength < MATCH_BLOCK_SIZE) {
028: copyFromNewData(b, 0, bLength);
029: return;
030: }
031: PseudoAdler32 bAdler = new PseudoAdler32();
032: Map aMatchesTable = createMatchesTable(a, aLength,
033: MATCH_BLOCK_SIZE, bAdler);
034: bAdler.reset();
035: bAdler.add(b, 0, MATCH_BLOCK_SIZE);
036:
037: int lo = 0;
038: int size = bLength;
039: Match previousInsertion = null;
040:
041: while (lo < size) {
042: Match match = findMatch(aMatchesTable, bAdler, a, aLength,
043: b, bLength, lo, previousInsertion);
044: if (match == null) {
045: if (previousInsertion != null
046: && previousInsertion.length > 0) {
047: previousInsertion.length++;
048: } else {
049: previousInsertion = new Match(lo, 1);
050: }
051: } else {
052: if (previousInsertion != null
053: && previousInsertion.length > 0) {
054: copyFromNewData(b, previousInsertion.position,
055: previousInsertion.length);
056: previousInsertion = null;
057: }
058: copyFromSource(match.position, match.length);
059: }
060: int advance = match != null ? match.advance : 1;
061: for (int next = lo; next < lo + advance; next++) {
062: bAdler.remove(b[next]);
063: if (next + MATCH_BLOCK_SIZE < bLength) {
064: bAdler.add(b[next + MATCH_BLOCK_SIZE]);
065: }
066: }
067: lo += advance;
068: }
069: if (previousInsertion != null && previousInsertion.length > 0) {
070: copyFromNewData(b, previousInsertion.position,
071: previousInsertion.length);
072: previousInsertion = null;
073: }
074: }
075:
076: private static Match findMatch(Map matchesTable,
077: PseudoAdler32 checksum, byte[] a, int aLength, byte[] b,
078: int bLength, int bPos, Match previousInsertion) {
079: Match existingMatch = (Match) matchesTable.get(new Integer(
080: checksum.getValue()));
081: if (existingMatch == null) {
082: return null;
083: }
084: if (!equals(a, aLength, existingMatch.position,
085: existingMatch.length, b, bLength, bPos)) {
086: return null;
087: }
088: existingMatch = new Match(existingMatch.position,
089: existingMatch.length);
090: existingMatch.advance = existingMatch.length;
091:
092: // extend forward
093: while (existingMatch.position + existingMatch.length < aLength
094: && bPos + existingMatch.advance < bLength
095: && a[existingMatch.position + existingMatch.length] == b[bPos
096: + existingMatch.advance]) {
097: existingMatch.length++;
098: existingMatch.advance++;
099: }
100: // extend backward
101: if (previousInsertion != null) {
102: while (existingMatch.position > 0 && bPos > 0
103: && a[existingMatch.position - 1] == b[bPos - 1]
104: && previousInsertion.length != 0) {
105: previousInsertion.length--;
106: bPos--;
107: existingMatch.position--;
108: existingMatch.length++;
109: }
110: }
111: return existingMatch;
112: }
113:
114: private static Map createMatchesTable(byte[] data, int dataLength,
115: int blockLength, PseudoAdler32 adler32) {
116: Map matchesTable = new HashMap();
117: for (int i = 0; i < dataLength; i += blockLength) {
118: int length = i + blockLength >= dataLength ? dataLength - i
119: : blockLength;
120: adler32.add(data, i, length);
121: Integer checksum = new Integer(adler32.getValue());
122: if (!matchesTable.containsKey(checksum)) {
123: matchesTable.put(checksum, new Match(i, length));
124: }
125: adler32.reset();
126: }
127: return matchesTable;
128: }
129:
130: private static boolean equals(byte[] a, int aLength, int aPos,
131: int length, byte[] b, int bLength, int bPos) {
132: if (aPos + length - 1 > aLength || bPos + length > bLength) {
133: return false;
134: }
135: for (int i = 0; i < length; i++) {
136: if (a[aPos + i] != b[bPos + i]) {
137: return false;
138: }
139: }
140: return true;
141: }
142:
143: private static class Match {
144:
145: public Match(int p, int l) {
146: position = p;
147: length = l;
148: }
149:
150: public int position;
151: public int length;
152: public int advance;
153: }
154:
155: private static int ADLER32_MASK = 0x0000FFFF;
156:
157: private static class PseudoAdler32 {
158:
159: private int myS1;
160: private int myS2;
161: private int myLength;
162:
163: public PseudoAdler32() {
164: reset();
165: }
166:
167: public void add(byte b) {
168: int z = b & 0x000000FF;
169: myS1 = myS1 + z;
170: myS1 = myS1 & ADLER32_MASK;
171: myS2 = myS2 + myS1;
172: myS2 = myS2 & ADLER32_MASK;
173: myLength++;
174: }
175:
176: public void remove(byte b) {
177: int z = b & 0x000000FF;
178: myS1 = myS1 - z;
179: myS1 = myS1 & ADLER32_MASK;
180: myS2 = myS2 - (myLength * z + 1);
181: myS2 = myS2 & ADLER32_MASK;
182: myLength--;
183: }
184:
185: public void add(byte[] data, int offset, int length) {
186: for (int i = offset; i < offset + length; i++) {
187: add(data[i]);
188: }
189: }
190:
191: public int getValue() {
192: return (myS2 << 16) | myS1;
193: }
194:
195: public void reset() {
196: myS1 = 1;
197: myS2 = 0;
198: myLength = 0;
199: }
200: }
201: }
|