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.io.ByteArrayInputStream;
015: import java.io.IOException;
016: import java.nio.ByteBuffer;
017: import java.util.Iterator;
018: import java.util.zip.InflaterInputStream;
019:
020: import org.tmatesoft.svn.core.SVNErrorCode;
021: import org.tmatesoft.svn.core.SVNErrorMessage;
022: import org.tmatesoft.svn.core.SVNException;
023: import org.tmatesoft.svn.core.internal.delta.SVNRangeTree.SVNRangeListNode;
024: import org.tmatesoft.svn.core.internal.io.fs.FSFile;
025: import org.tmatesoft.svn.core.internal.wc.SVNErrorManager;
026: import org.tmatesoft.svn.core.io.diff.SVNDiffInstruction;
027: import org.tmatesoft.svn.core.io.diff.SVNDiffWindow;
028: import org.tmatesoft.svn.util.SVNDebugLog;
029:
030: /**
031: * @version 1.1.1
032: * @author TMate Software Ltd.
033: */
034: public class SVNDeltaCombiner {
035:
036: private SVNDiffWindow myWindow;
037:
038: private ByteBuffer myWindowData;
039: private ByteBuffer myNextWindowInstructions;
040: private ByteBuffer myNextWindowData;
041: private ByteBuffer myTarget;
042: private ByteBuffer myRealTarget;
043: private ByteBuffer myReadWindowBuffer;
044:
045: private SVNRangeTree myRangeTree;
046: private SVNOffsetsIndex myOffsetsIndex;
047: private SVNDiffInstruction[] myWindowInstructions;
048: private SVNDiffInstruction myInstructionTemplate;
049:
050: public SVNDeltaCombiner() {
051: myRangeTree = new SVNRangeTree();
052: myWindowInstructions = new SVNDiffInstruction[10];
053: myInstructionTemplate = new SVNDiffInstruction(0, 0, 0);
054: myOffsetsIndex = new SVNOffsetsIndex();
055:
056: myNextWindowData = ByteBuffer.allocate(1024 * 20);
057: }
058:
059: public void reset() {
060: myWindow = null;
061: myWindowData = null;
062: myReadWindowBuffer = null;
063: myNextWindowData = clearBuffer(myNextWindowData);
064: myNextWindowInstructions = null;
065: myTarget = null;
066: myRealTarget = null;
067:
068: myRangeTree.dispose();
069: }
070:
071: public SVNDiffWindow readWindow(FSFile file, int version)
072: throws SVNException {
073: myReadWindowBuffer = clearBuffer(myReadWindowBuffer);
074: myReadWindowBuffer = ensureBufferSize(myReadWindowBuffer, 4096);
075: long position = 0;
076: try {
077: position = file.position();
078: file.read(myReadWindowBuffer);
079: } catch (IOException e) {
080: SVNErrorMessage err = SVNErrorMessage
081: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
082: SVNErrorManager.error(err, e);
083: }
084: myReadWindowBuffer.flip();
085: long sourceOffset = readLongOffset(myReadWindowBuffer);
086: int sourceLength = readOffset(myReadWindowBuffer);
087: int targetLength = readOffset(myReadWindowBuffer);
088: int instructionsLength = readOffset(myReadWindowBuffer);
089: int dataLength = readOffset(myReadWindowBuffer);
090: if (sourceOffset < 0 || sourceLength < 0 || targetLength < 0
091: || instructionsLength < 0 || dataLength < 0) {
092: SVNErrorMessage err = SVNErrorMessage
093: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
094: SVNErrorManager.error(err);
095: }
096: position += myReadWindowBuffer.position();
097: file.seek(position);
098:
099: myReadWindowBuffer = clearBuffer(myReadWindowBuffer);
100: myReadWindowBuffer = ensureBufferSize(myReadWindowBuffer,
101: instructionsLength + dataLength);
102: myReadWindowBuffer.limit(instructionsLength + dataLength);
103: try {
104: file.read(myReadWindowBuffer);
105: } catch (IOException e) {
106: SVNDebugLog.getDefaultLog().error(e);
107: SVNErrorMessage err = SVNErrorMessage
108: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
109: SVNErrorManager.error(err, e);
110: }
111: myReadWindowBuffer.position(0);
112: myReadWindowBuffer.limit(myReadWindowBuffer.capacity());
113: if (version == 1) {
114: // decompress instructions and new data, put back to the buffer.
115: try {
116: int[] lenghts = decompress(instructionsLength,
117: dataLength);
118: instructionsLength = lenghts[0];
119: dataLength = lenghts[1];
120: } catch (IOException e) {
121: SVNErrorMessage err = SVNErrorMessage
122: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
123: SVNErrorManager.error(err, e);
124: }
125: }
126: SVNDiffWindow window = new SVNDiffWindow(sourceOffset,
127: sourceLength, targetLength, instructionsLength,
128: dataLength);
129: window.setData(myReadWindowBuffer);
130: return window;
131: }
132:
133: private int[] decompress(int instructionsLength, int dataLength)
134: throws IOException {
135: int originalPosition = myReadWindowBuffer.position();
136: int realInstructionsLength = readOffset(myReadWindowBuffer);
137: byte[] instructionsData = new byte[realInstructionsLength];
138: byte[] data = null;
139: int realDataLength = 0;
140: int compressedLength = instructionsLength
141: - (myReadWindowBuffer.position() - originalPosition);
142: if (realInstructionsLength == compressedLength) {
143: System.arraycopy(myReadWindowBuffer.array(),
144: myReadWindowBuffer.arrayOffset()
145: + myReadWindowBuffer.position(),
146: instructionsData, 0, realInstructionsLength);
147: myReadWindowBuffer.position(myReadWindowBuffer.position()
148: + realInstructionsLength);
149: } else {
150: byte[] compressedData = new byte[compressedLength];
151: System.arraycopy(myReadWindowBuffer.array(),
152: myReadWindowBuffer.arrayOffset()
153: + myReadWindowBuffer.position(),
154: compressedData, 0, compressedLength);
155: myReadWindowBuffer.position(myReadWindowBuffer.position()
156: + compressedLength);
157: InflaterInputStream is = new InflaterInputStream(
158: new ByteArrayInputStream(compressedData));
159: int read = 0;
160: while (read < realInstructionsLength) {
161: read += is.read(instructionsData, read,
162: realInstructionsLength - read);
163: }
164: }
165: if (dataLength > 0) {
166: originalPosition = myReadWindowBuffer.position();
167: realDataLength = readOffset(myReadWindowBuffer);
168: compressedLength = dataLength
169: - (myReadWindowBuffer.position() - originalPosition);
170: data = new byte[realDataLength];
171: if (compressedLength == realDataLength) {
172: System.arraycopy(myReadWindowBuffer.array(),
173: myReadWindowBuffer.arrayOffset()
174: + myReadWindowBuffer.position(), data,
175: 0, realDataLength);
176: myReadWindowBuffer.position(myReadWindowBuffer
177: .position()
178: + realDataLength);
179: } else {
180: byte[] compressedData = new byte[compressedLength];
181: System.arraycopy(myReadWindowBuffer.array(),
182: myReadWindowBuffer.arrayOffset()
183: + myReadWindowBuffer.position(),
184: compressedData, 0, compressedLength);
185: myReadWindowBuffer.position(myReadWindowBuffer
186: .position()
187: + compressedLength);
188: InflaterInputStream is = new InflaterInputStream(
189: new ByteArrayInputStream(compressedData));
190: int read = 0;
191: while (read < realDataLength) {
192: read += is.read(data, read, realDataLength - read);
193: }
194: }
195: }
196: myReadWindowBuffer = clearBuffer(myReadWindowBuffer);
197: myReadWindowBuffer = ensureBufferSize(myReadWindowBuffer,
198: realInstructionsLength + realDataLength);
199: myReadWindowBuffer.put(instructionsData);
200: if (data != null) {
201: myReadWindowBuffer.put(data);
202: }
203: myReadWindowBuffer.position(0);
204: myReadWindowBuffer.limit(myReadWindowBuffer.capacity());
205: return new int[] { realInstructionsLength, realDataLength };
206: }
207:
208: public void skipWindow(FSFile file) throws SVNException {
209: myReadWindowBuffer = clearBuffer(myReadWindowBuffer);
210: myReadWindowBuffer = ensureBufferSize(myReadWindowBuffer, 4096);
211: long position = 0;
212: try {
213: position = file.position();
214: file.read(myReadWindowBuffer);
215: } catch (IOException e) {
216: SVNErrorMessage err = SVNErrorMessage
217: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
218: SVNErrorManager.error(err, e);
219: }
220: myReadWindowBuffer.flip();
221: if (readLongOffset(myReadWindowBuffer) < 0) {
222: SVNErrorMessage err = SVNErrorMessage
223: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
224: SVNErrorManager.error(err);
225: }
226: if (readOffset(myReadWindowBuffer) < 0) {
227: SVNErrorMessage err = SVNErrorMessage
228: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
229: SVNErrorManager.error(err);
230: }
231: if (readOffset(myReadWindowBuffer) < 0) {
232: SVNErrorMessage err = SVNErrorMessage
233: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
234: SVNErrorManager.error(err);
235: }
236: int instructionsLength = readOffset(myReadWindowBuffer);
237: int dataLength = readOffset(myReadWindowBuffer);
238: if (instructionsLength < 0 || dataLength < 0) {
239: SVNErrorMessage err = SVNErrorMessage
240: .create(SVNErrorCode.SVNDIFF_CORRUPT_WINDOW);
241: SVNErrorManager.error(err);
242: }
243: position += myReadWindowBuffer.position();
244: file.seek(position + dataLength + instructionsLength);
245: myReadWindowBuffer = clearBuffer(myReadWindowBuffer);
246: }
247:
248: // when true, there is a target and my window.
249: public ByteBuffer addWindow(SVNDiffWindow window) {
250: // 1.
251: // if window doesn't has cpfrom source apply it to empty file and save results to the target.
252: // and we're done.
253: if (window.getSourceViewLength() == 0
254: || !window.hasCopyFromSourceInstructions()) {
255: // apply window, make sure target not less then getTargetViewLength.
256: myTarget = clearBuffer(myTarget);
257: myTarget = ensureBufferSize(myTarget, window
258: .getTargetViewLength());
259: window.apply(new byte[0], myTarget.array());
260: // and then apply myWindow if any.
261: ByteBuffer result = null;
262: if (myWindow != null) {
263: myRealTarget = clearBuffer(myRealTarget);
264: myRealTarget = ensureBufferSize(myRealTarget, myWindow
265: .getTargetViewLength());
266: myWindow.apply(myTarget.array(), myRealTarget.array());
267: result = myRealTarget;
268: } else {
269: result = myTarget;
270: }
271: result.position(0);
272: int tLength = myWindow != null ? myWindow
273: .getTargetViewLength() : window
274: .getTargetViewLength();
275: result.limit(tLength);
276: return result;
277: }
278:
279: // 2.
280: // otherwise combine window with myWindow, and save it in place of myWindow.
281: // we're not done.
282: if (myWindow != null) {
283: myWindow = combineWindows(window);
284: return null;
285: }
286:
287: // 3.
288: // if we do not have myWindow yet, just save window as myWindow.
289: // make sure window is 'copied', so that its full data goes to our buffer.
290: // and also make sure that myWindowData has enough free space for that window.
291: // we're not done.
292: myWindowData = clearBuffer(myWindowData);
293: myWindowData = ensureBufferSize(myWindowData, window
294: .getDataLength());
295: myWindow = window.clone(myWindowData);
296: return null;
297: }
298:
299: private SVNDiffWindow combineWindows(SVNDiffWindow window /* A, B - myWindow */) {
300: myNextWindowInstructions = clearBuffer(myNextWindowInstructions);
301: myNextWindowData = clearBuffer(myNextWindowData);
302:
303: int targetOffset = 0;
304: myWindowInstructions = window
305: .loadDiffInstructions(myWindowInstructions);
306: createOffsetsIndex(myWindowInstructions, window
307: .getInstructionsCount());
308:
309: SVNRangeTree rangeIndexTree = myRangeTree;
310: rangeIndexTree.dispose();
311:
312: for (Iterator instructions = myWindow.instructions(true); instructions
313: .hasNext();) {
314: SVNDiffInstruction instruction = (SVNDiffInstruction) instructions
315: .next();
316: if (instruction.type != SVNDiffInstruction.COPY_FROM_SOURCE) {
317: myNextWindowInstructions = ensureBufferSize(
318: myNextWindowInstructions, 10);
319: instruction.writeTo(myNextWindowInstructions);
320: if (instruction.type == SVNDiffInstruction.COPY_FROM_NEW_DATA) {
321: myNextWindowData = ensureBufferSize(
322: myNextWindowData, instruction.length);
323: myWindow.writeNewData(myNextWindowData,
324: instruction.offset, instruction.length);
325: }
326: } else {
327: int offset = instruction.offset;
328: int limit = instruction.offset + instruction.length;
329: int tgt_off = targetOffset;
330: rangeIndexTree.splay(offset);
331: SVNRangeListNode listTail = rangeIndexTree
332: .buildRangeList(offset, limit);
333: SVNRangeListNode listHead = listTail.head;
334: for (SVNRangeListNode range = listHead; range != null; range = range.next) {
335: if (range.kind == SVNRangeListNode.FROM_TARGET) {
336: myInstructionTemplate.type = SVNDiffInstruction.COPY_FROM_TARGET;
337: myInstructionTemplate.length = range.limit
338: - range.offset;
339: myInstructionTemplate.offset = range.targetOffset;
340: myNextWindowInstructions = ensureBufferSize(
341: myNextWindowInstructions, 10);
342: myInstructionTemplate
343: .writeTo(myNextWindowInstructions);
344: } else {
345: copySourceInstructions(range.offset,
346: range.limit, tgt_off, window,
347: myWindowInstructions);
348: }
349: tgt_off += range.limit - range.offset;
350: }
351: assertCondition(tgt_off == targetOffset
352: + instruction.length, "assert #1");
353: rangeIndexTree.insert(offset, limit, targetOffset);
354: rangeIndexTree.disposeList(listHead);
355: }
356: targetOffset += instruction.length;
357: }
358: // build window from 'next' buffers and replace myWindow with the new one.
359: myNextWindowData.flip();
360: myNextWindowInstructions.flip();
361: int instrLength = myNextWindowInstructions.limit();
362: int newDataLength = myNextWindowData.limit();
363: myWindowData = clearBuffer(myWindowData);
364: myWindowData = ensureBufferSize(myWindowData, instrLength
365: + newDataLength);
366: myWindowData.put(myNextWindowInstructions);
367: myWindowData.put(myNextWindowData);
368: myWindowData.position(0); // no need to set 'limit'...
369:
370: myWindow = new SVNDiffWindow(window.getSourceViewOffset(),
371: window.getSourceViewLength(), myWindow
372: .getTargetViewLength(), instrLength,
373: newDataLength);
374: myWindow.setData(myWindowData);
375:
376: myNextWindowInstructions = clearBuffer(myNextWindowInstructions);
377: myNextWindowData = clearBuffer(myNextWindowData);
378: return myWindow;
379: }
380:
381: private void copySourceInstructions(int offset, int limit,
382: int targetOffset, SVNDiffWindow window,
383: SVNDiffInstruction[] windowInsructions) {
384: int firstInstuctionIndex = findInstructionIndex(myOffsetsIndex,
385: offset);
386: int lastInstuctionIndex = findInstructionIndex(myOffsetsIndex,
387: limit - 1);
388:
389: for (int i = firstInstuctionIndex; i <= lastInstuctionIndex; i++) {
390: SVNDiffInstruction instruction = windowInsructions[i];
391: int off0 = myOffsetsIndex.offsets[i];
392: int off1 = myOffsetsIndex.offsets[i + 1];
393:
394: int fix_offset = offset > off0 ? offset - off0 : 0;
395: int fix_limit = off1 > limit ? off1 - limit : 0;
396: assertCondition(
397: fix_offset + fix_limit < instruction.length,
398: "assert #7");
399:
400: if (instruction.type != SVNDiffInstruction.COPY_FROM_TARGET) {
401: int oldOffset = instruction.offset;
402: int oldLength = instruction.length;
403:
404: instruction.offset += fix_offset;
405: instruction.length = oldLength - fix_offset - fix_limit;
406:
407: myNextWindowInstructions = ensureBufferSize(
408: myNextWindowInstructions, 10);
409: instruction.writeTo(myNextWindowInstructions);
410: if (instruction.type == SVNDiffInstruction.COPY_FROM_NEW_DATA) {
411: myNextWindowData = ensureBufferSize(
412: myNextWindowData, instruction.length);
413: window.writeNewData(myNextWindowData,
414: instruction.offset, instruction.length);
415: }
416: instruction.offset = oldOffset;
417: instruction.length = oldLength;
418: } else {
419: assertCondition(instruction.offset < off0, "assert #8");
420: if (instruction.offset + instruction.length - fix_limit <= off0) {
421: copySourceInstructions(instruction.offset
422: + fix_offset, instruction.offset
423: + instruction.length - fix_limit,
424: targetOffset, window, windowInsructions);
425: } else {
426: int patternLength = off0 - instruction.offset;
427: int patternOverlap = fix_offset % patternLength;
428: assertCondition(patternLength > patternOverlap,
429: "assert #9");
430: int fix_off = fix_offset;
431: int tgt_off = targetOffset;
432:
433: if (patternOverlap >= 0) {
434: int length = Math.min(instruction.length
435: - fix_offset - fix_limit, patternLength
436: - patternOverlap);
437: copySourceInstructions(instruction.offset
438: + patternOverlap, instruction.offset
439: + patternOverlap + length, tgt_off,
440: window, windowInsructions);
441: tgt_off += length;
442: fix_off += length;
443: }
444: assertCondition(
445: fix_off + fix_limit <= instruction.length,
446: "assert #A");
447: if (patternOverlap > 0
448: && fix_off + fix_limit < instruction.length) {
449: int length = Math.min(instruction.length
450: - fix_offset - fix_limit,
451: patternOverlap);
452: copySourceInstructions(instruction.offset,
453: instruction.offset + length, tgt_off,
454: window, windowInsructions);
455: tgt_off += length;
456: fix_off += length;
457: }
458: assertCondition(
459: fix_off + fix_limit <= instruction.length,
460: "assert #B");
461: if (fix_off + fix_limit < instruction.length) {
462: myInstructionTemplate.type = SVNDiffInstruction.COPY_FROM_TARGET;
463: myInstructionTemplate.length = instruction.length
464: - fix_off - fix_limit;
465: myInstructionTemplate.offset = tgt_off
466: - patternLength;
467: myNextWindowInstructions = ensureBufferSize(
468: myNextWindowInstructions, 10);
469: myInstructionTemplate
470: .writeTo(myNextWindowInstructions);
471: }
472:
473: }
474: }
475: targetOffset += instruction.length - fix_offset - fix_limit;
476: }
477:
478: }
479:
480: private void createOffsetsIndex(SVNDiffInstruction[] instructions,
481: int length) {
482: if (myOffsetsIndex == null) {
483: myOffsetsIndex = new SVNOffsetsIndex();
484: }
485: myOffsetsIndex.clear();
486: int offset = 0;
487: for (int i = 0; i < length; i++) {
488: SVNDiffInstruction instruction = instructions[i];
489: myOffsetsIndex.addOffset(offset);
490: offset += instruction.length;
491: }
492: myOffsetsIndex.addOffset(offset);
493: }
494:
495: private int findInstructionIndex(SVNOffsetsIndex offsets, int offset) {
496: int lo = 0;
497: int hi = offsets.length - 1;
498: int op = (lo + hi) / 2;
499:
500: assertCondition(offset < offsets.offsets[offsets.length - 1],
501: "assert #2");
502:
503: for (; lo < hi; op = (lo + hi) / 2) {
504: int this Offset = offsets.offsets[op];
505: int nextOffset = offsets.offsets[op + 1];
506: if (offset < this Offset) {
507: hi = op;
508: } else if (offset > nextOffset) {
509: lo = op;
510: } else {
511: if (offset == nextOffset) {
512: op++;
513: }
514: break;
515: }
516: }
517: assertCondition(offsets.offsets[op] <= offset
518: && offset < offsets.offsets[op + 1], "assert #3");
519: return op;
520: }
521:
522: private ByteBuffer clearBuffer(ByteBuffer b) {
523: if (b != null) {
524: b.clear();
525: }
526: return b;
527: }
528:
529: private ByteBuffer ensureBufferSize(ByteBuffer buffer,
530: int dataLength) {
531: if (buffer == null || buffer.remaining() < dataLength) {
532: ByteBuffer data = buffer != null ? ByteBuffer
533: .allocate((buffer.position() + dataLength) * 3 / 2)
534: : ByteBuffer.allocate(dataLength * 3 / 2);
535: data.clear();
536: if (buffer != null) {
537: data.put(buffer.array(), 0, buffer.position());
538: }
539: buffer = data;
540: }
541: return buffer;
542: }
543:
544: private int readOffset(ByteBuffer buffer) {
545: buffer.mark();
546: int offset = 0;
547: byte b;
548: while (buffer.hasRemaining()) {
549: b = buffer.get();
550: offset = (offset << 7) | (b & 0x7F);
551: if ((b & 0x80) != 0) {
552: continue;
553: }
554: return offset;
555: }
556: buffer.reset();
557: return -1;
558: }
559:
560: private long readLongOffset(ByteBuffer buffer) {
561: buffer.mark();
562: long offset = 0;
563: byte b;
564: while (buffer.hasRemaining()) {
565: b = buffer.get();
566: offset = (offset << 7) | (b & 0x7F);
567: if ((b & 0x80) != 0) {
568: continue;
569: }
570: return offset;
571: }
572: buffer.reset();
573: return -1;
574: }
575:
576: static void assertCondition(boolean condition, String message) {
577: if (!condition) {
578: SVNDebugLog.getDefaultLog().error(message);
579: SVNDebugLog.getDefaultLog().error(new Exception(message));
580: }
581: }
582:
583: private static class SVNOffsetsIndex {
584:
585: public int length;
586: public int[] offsets;
587:
588: public SVNOffsetsIndex() {
589: offsets = new int[10];
590: }
591:
592: public void clear() {
593: length = 0;
594: }
595:
596: public void addOffset(int offset) {
597: if (length >= offsets.length) {
598: int[] newOffsets = new int[length * 3 / 2];
599: System.arraycopy(offsets, 0, newOffsets, 0, length);
600: offsets = newOffsets;
601: }
602: offsets[length] = offset;
603: length++;
604: }
605: }
606:
607: }
|