001    /**
002     * Copyright (c) 2000-2013 Liferay, Inc. All rights reserved.
003     *
004     * This library is free software; you can redistribute it and/or modify it under
005     * the terms of the GNU Lesser General Public License as published by the Free
006     * Software Foundation; either version 2.1 of the License, or (at your option)
007     * any later version.
008     *
009     * This library is distributed in the hope that it will be useful, but WITHOUT
010     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
011     * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
012     * details.
013     */
014    
015    package com.liferay.portal.kernel.io.delta;
016    
017    import java.io.IOException;
018    
019    import java.nio.ByteBuffer;
020    import java.nio.channels.ReadableByteChannel;
021    
022    import java.security.MessageDigest;
023    
024    import java.util.HashMap;
025    import java.util.Map;
026    
027    /**
028     * @author Connor McKay
029     */
030    public class Differ {
031    
032            public void delta(
033                            ReadableByteChannel modifiedReadableByteChannel,
034                            ByteChannelReader checksumsByteChannelReader,
035                            ByteChannelWriter deltaByteChannelWriter)
036                    throws IOException {
037    
038                    _modifiedReadableByteChannel = modifiedReadableByteChannel;
039                    _checksumsByteChannelReader = checksumsByteChannelReader;
040                    _deltaByteChannelWriter = deltaByteChannelWriter;
041    
042                    _checksumsByteChannelReader.resizeBuffer(DeltaUtil.BUFFER_FACTOR * 20);
043    
044                    _checksumsByteBuffer = _checksumsByteChannelReader.getBuffer();
045    
046                    readChecksumsHeader();
047                    readChecksums();
048    
049                    _rollingChecksum = new RollingChecksum(
050                            _modifiedReadableByteChannel, _blockLength);
051    
052                    _deltaByteChannelWriter.resizeBuffer(
053                            _blockLength * DeltaUtil.BUFFER_FACTOR + 5);
054    
055                    _deltaByteBuffer = _deltaByteChannelWriter.getBuffer();
056    
057                    if ((_dataByteBuffer == null) ||
058                            (_dataByteBuffer.capacity() <
059                                    (_blockLength * DeltaUtil.BUFFER_FACTOR))) {
060    
061                            _dataByteBuffer = ByteBuffer.allocate(
062                                    _blockLength * DeltaUtil.BUFFER_FACTOR);
063                    }
064    
065                    writeDeltaHeader();
066                    writeDeltaBlocks();
067            }
068    
069            protected void readChecksums() throws IOException {
070                    _blockDatas = new HashMap<Integer, BlockData>(_blocksCount);
071    
072                    for (int blockNumber = 0; blockNumber < _blocksCount; blockNumber++) {
073                            _checksumsByteChannelReader.ensureData(20);
074    
075                            int weakChecksum = _checksumsByteBuffer.getInt();
076    
077                            byte[] strongChecksum = new byte[16];
078    
079                            _checksumsByteBuffer.get(strongChecksum);
080    
081                            // It is possible that there are two or more blocks with the same
082                            // weak checksum, in which case the map will only contain the strong
083                            // checksum of the last one. In some cases, this may cause a data
084                            // block to be sent when a reference block could have been sent, but
085                            // it doesn't really matter.
086    
087                            _blockDatas.put(
088                                    weakChecksum, new BlockData(blockNumber, strongChecksum));
089                    }
090            }
091    
092            protected void readChecksumsHeader() throws IOException {
093                    _checksumsByteChannelReader.ensureData(9);
094    
095                    if (DeltaUtil.PROTOCOL_VERSION != _checksumsByteBuffer.get()) {
096                            throw new IOException("Unknown protocol version");
097                    }
098    
099                    _blockLength = _checksumsByteBuffer.getInt();
100                    _blocksCount = _checksumsByteBuffer.getInt();
101            }
102    
103            protected void writeDataBlock() throws IOException {
104                    if (_dataByteBuffer.position() == 0) {
105    
106                            // There's nothing in the data buffer
107    
108                            return;
109                    }
110    
111                    _deltaByteChannelWriter.ensureSpace(_dataByteBuffer.position() + 5);
112    
113                    _deltaByteBuffer.put(DeltaUtil.DATA_KEY);
114                    _deltaByteBuffer.putInt(_dataByteBuffer.position());
115    
116                    _dataByteBuffer.flip();
117    
118                    _deltaByteBuffer.put(_dataByteBuffer);
119    
120                    _dataByteBuffer.clear();
121            }
122    
123            protected void writeDeltaBlocks() throws IOException {
124                    _firstBlockNumber = -1;
125                    _lastBlockNumber = -1;
126    
127                    while (_rollingChecksum.hasNext()) {
128                            BlockData blockData = _blockDatas.get(
129                                    _rollingChecksum.weakChecksum());
130    
131                            if ((blockData != null) &&
132                                    MessageDigest.isEqual(
133                                            blockData.getStrongChecksum(),
134                                            _rollingChecksum.strongChecksum())) {
135    
136                                    int blockNumber = blockData.getBlockNumber();
137    
138                                    if (_firstBlockNumber == -1) {
139                                            writeDataBlock();
140    
141                                            _firstBlockNumber = blockNumber;
142                                            _lastBlockNumber = blockNumber;
143                                    }
144                                    else if ((_lastBlockNumber + 1) == blockNumber) {
145    
146                                            // The blocks must be sequential in a reference range block
147    
148                                            _lastBlockNumber = blockNumber;
149                                    }
150                                    else {
151                                            writeReferenceBlock();
152    
153                                            _firstBlockNumber = blockNumber;
154                                            _lastBlockNumber = blockNumber;
155                                    }
156    
157                                    _rollingChecksum.nextBlock();
158                            }
159                            else {
160                                    writeReferenceBlock();
161    
162                                    if (!_dataByteBuffer.hasRemaining()) {
163                                            writeDataBlock();
164                                    }
165    
166                                    _dataByteBuffer.put(_rollingChecksum.getFirstByte());
167    
168                                    _rollingChecksum.nextByte();
169                            }
170                    }
171    
172                    // Only one of these should ever actually do something, but it's simpler
173                    // to call them both than choose between them.
174    
175                    writeReferenceBlock();
176                    writeDataBlock();
177    
178                    _deltaByteChannelWriter.ensureSpace(1);
179    
180                    _deltaByteBuffer.put(DeltaUtil.EOF_KEY);
181            }
182    
183            protected void writeDeltaHeader() throws IOException {
184                    _deltaByteChannelWriter.ensureSpace(5);
185    
186                    _deltaByteBuffer.put(DeltaUtil.PROTOCOL_VERSION);
187                    _deltaByteBuffer.putInt(_blockLength);
188            }
189    
190            protected void writeReferenceBlock() throws IOException {
191                    if (_firstBlockNumber == -1) {
192                            return;
193                    }
194    
195                    if (_lastBlockNumber == _firstBlockNumber) {
196                            _deltaByteChannelWriter.ensureSpace(5);
197    
198                            _deltaByteBuffer.put(DeltaUtil.REFERENCE_KEY);
199                            _deltaByteBuffer.putInt(_firstBlockNumber);
200                    }
201                    else {
202                            _deltaByteChannelWriter.ensureSpace(9);
203    
204                            _deltaByteBuffer.put(DeltaUtil.REFERENCE_RANGE_KEY);
205                            _deltaByteBuffer.putInt(_firstBlockNumber);
206                            _deltaByteBuffer.putInt(_lastBlockNumber);
207                    }
208    
209                    _firstBlockNumber = -1;
210                    _lastBlockNumber = -1;
211            }
212    
213            private Map<Integer, BlockData> _blockDatas;
214            private int _blockLength;
215            private int _blocksCount;
216            private ByteBuffer _checksumsByteBuffer;
217            private ByteChannelReader _checksumsByteChannelReader;
218            private ByteBuffer _dataByteBuffer;
219            private ByteBuffer _deltaByteBuffer;
220            private ByteChannelWriter _deltaByteChannelWriter;
221            private int _firstBlockNumber;
222            private int _lastBlockNumber;
223            private ReadableByteChannel _modifiedReadableByteChannel;
224            private RollingChecksum _rollingChecksum;
225    
226            private class BlockData {
227    
228                    public BlockData(int blockNumber, byte[] strongChecksum) {
229                            _blockNumber = blockNumber;
230                            _strongChecksum = strongChecksum;
231                    }
232    
233                    public int getBlockNumber() {
234                            return _blockNumber;
235                    }
236    
237                    public byte[] getStrongChecksum() {
238                            return _strongChecksum;
239                    }
240    
241                    private int _blockNumber;
242                    private byte[] _strongChecksum;
243    
244            }
245    
246    }