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.Arrays;
015:
016: /**
017: * @version 1.1.1
018: * @author TMate Software Ltd.
019: */
020: public class SVNVDeltaAlgorithm extends SVNDeltaAlgorithm {
021:
022: private static final int VD_KEY_SIZE = 4;
023:
024: private SlotsTable mySlotsTable;
025:
026: public void computeDelta(byte[] a, int aLength, byte[] b,
027: int bLength) {
028: int dataLength;
029: byte[] data;
030: if (aLength > 0 && bLength > 0) {
031: // both are non-empty (reuse some local array).
032: data = new byte[(aLength + bLength)];
033: System.arraycopy(a, 0, data, 0, aLength);
034: System.arraycopy(b, 0, data, aLength, bLength);
035: dataLength = aLength + bLength;
036: } else if (aLength == 0) {
037: // a is empty
038: data = b;
039: dataLength = bLength;
040: } else {
041: // b is empty
042: data = a;
043: dataLength = aLength;
044: }
045: SlotsTable slotsTable = getSlotsTable(dataLength);
046: vdelta(slotsTable, data, 0, aLength, false);
047: vdelta(slotsTable, data, aLength, dataLength, true);
048: }
049:
050: private SlotsTable getSlotsTable(int dataLength) {
051: if (mySlotsTable == null) {
052: mySlotsTable = new SlotsTable();
053: }
054: mySlotsTable.reset(dataLength);
055: return mySlotsTable;
056: }
057:
058: private void vdelta(SlotsTable table, byte[] data, int start,
059: int end, boolean doOutput) {
060: int here = start;
061: int insertFrom = -1;
062:
063: while (true) {
064:
065: if (end - here < VD_KEY_SIZE) {
066: int from = insertFrom >= 0 ? insertFrom : here;
067: if (doOutput && from < end) {
068: copyFromNewData(data, from, end - from);
069: }
070: return;
071: }
072:
073: int currentMatch = -1;
074: int currentMatchLength = 0;
075: int key;
076: int slot;
077: boolean progress = false;
078:
079: key = here;
080:
081: do {
082: progress = false;
083: for (slot = table.getBucket(table.getBucketIndex(data,
084: key)); slot >= 0; slot = table.mySlots[slot]) {
085:
086: if (slot < key - here) {
087: continue;
088: }
089: int match = slot - (key - here);
090: int matchLength = findMatchLength(data, match,
091: here, end);
092: if (match < start && match + matchLength > start) {
093: matchLength = start - match;
094: }
095: if (matchLength >= VD_KEY_SIZE
096: && matchLength > currentMatchLength) {
097: currentMatch = match;
098: currentMatchLength = matchLength;
099: progress = true;
100: }
101: }
102: if (progress) {
103: key = here + currentMatchLength - (VD_KEY_SIZE - 1);
104: }
105: } while (progress && end - key >= VD_KEY_SIZE);
106:
107: if (currentMatchLength < VD_KEY_SIZE) {
108: table.storeSlot(data, here);
109: if (insertFrom < 0) {
110: insertFrom = here;
111: }
112: here++;
113: continue;
114: } else if (doOutput) {
115: if (insertFrom >= 0) {
116: copyFromNewData(data, insertFrom, here - insertFrom);
117: insertFrom = -1;
118: }
119: if (currentMatch < start) {
120: copyFromSource(currentMatch, currentMatchLength);
121: } else {
122: copyFromTarget(currentMatch - start,
123: currentMatchLength);
124: }
125: }
126: here += currentMatchLength;
127: if (end - here >= VD_KEY_SIZE) {
128: int last = here - (VD_KEY_SIZE - 1);
129: for (; last < here; ++last) {
130: table.storeSlot(data, last);
131: }
132: }
133: }
134:
135: }
136:
137: private int findMatchLength(byte[] data, int match, int from,
138: int end) {
139: int here = from;
140: while (here < end && data[match] == data[here]) {
141: match++;
142: here++;
143: }
144: return here - from;
145: }
146:
147: private static class SlotsTable {
148:
149: private int[] mySlots;
150: private int[] myBuckets;
151: private int myBucketsCount;
152:
153: public SlotsTable() {
154: }
155:
156: public void reset(int dataLength) {
157: mySlots = allocate(mySlots, dataLength);
158: myBucketsCount = (dataLength / 3) | 1;
159: myBuckets = allocate(myBuckets, myBucketsCount);
160:
161: Arrays.fill(mySlots, 0, dataLength, -1);
162: Arrays.fill(myBuckets, 0, myBucketsCount, -1);
163: }
164:
165: public int getBucketIndex(byte[] data, int index) {
166: int hash = 0;
167: hash += (data[index] & 0xFF);
168: hash += hash * 127 + (data[index + 1] & 0xFF);
169: hash += hash * 127 + (data[index + 2] & 0xFF);
170: hash += hash * 127 + (data[index + 3] & 0xFF);
171: hash = hash % myBucketsCount;
172: return hash < 0 ? -hash : hash;
173: }
174:
175: public int getBucket(int bucketIndex) {
176: return myBuckets[bucketIndex];
177: }
178:
179: public void storeSlot(byte[] data, int slotIndex) {
180: int bucketIndex = getBucketIndex(data, slotIndex);
181: mySlots[slotIndex] = myBuckets[bucketIndex];
182: myBuckets[bucketIndex] = slotIndex;
183: }
184:
185: private static int[] allocate(int[] array, int length) {
186: if (array == null || array.length < length) {
187: return new int[length * 3 / 2];
188: }
189: return array;
190: }
191: }
192: }
|