1 /* 2 * Copyright (C) 2010, Google Inc. 3 * and other copyright owners as documented in the project's IP log. 4 * 5 * This program and the accompanying materials are made available 6 * under the terms of the Eclipse Distribution License v1.0 which 7 * accompanies this distribution, is reproduced below, and is 8 * available at http://www.eclipse.org/org/documents/edl-v10.php 9 * 10 * All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or 13 * without modification, are permitted provided that the following 14 * conditions are met: 15 * 16 * - Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 19 * - Redistributions in binary form must reproduce the above 20 * copyright notice, this list of conditions and the following 21 * disclaimer in the documentation and/or other materials provided 22 * with the distribution. 23 * 24 * - Neither the name of the Eclipse Foundation, Inc. nor the 25 * names of its contributors may be used to endorse or promote 26 * products derived from this software without specific prior 27 * written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 42 */ 43 44 package org.eclipse.jgit.internal.storage.pack; 45 46 import java.io.IOException; 47 import java.io.OutputStream; 48 49 import org.eclipse.jgit.lib.Constants; 50 51 /** 52 * Encodes an instruction stream for 53 * {@link org.eclipse.jgit.internal.storage.pack.BinaryDelta}. 54 */ 55 public class DeltaEncoder { 56 /** 57 * Maximum number of bytes to be copied in pack v2 format. 58 * <p> 59 * Historical limitations have this at 64k, even though current delta 60 * decoders recognize larger copy instructions. 61 */ 62 private static final int MAX_V2_COPY = 0x10000; 63 64 /* 65 * Maximum number of bytes to be copied in pack v3 format. 66 * 67 * Current delta decoders can recognize a copy instruction with a count that 68 * is this large, but the historical limitation of {@link MAX_V2_COPY} is 69 * still used. 70 */ 71 // private static final int MAX_V3_COPY = (0xff << 16) | (0xff << 8) | 0xff; 72 73 /** Maximum number of bytes used by a copy instruction. */ 74 private static final int MAX_COPY_CMD_SIZE = 8; 75 76 /** Maximum length that an an insert command can encode at once. */ 77 private static final int MAX_INSERT_DATA_SIZE = 127; 78 79 private final OutputStream out; 80 81 private final byte[] buf = new byte[MAX_COPY_CMD_SIZE * 4]; 82 83 private final int limit; 84 85 private int size; 86 87 /** 88 * Create an encoder with no upper bound on the instruction stream size. 89 * 90 * @param out 91 * buffer to store the instructions written. 92 * @param baseSize 93 * size of the base object, in bytes. 94 * @param resultSize 95 * size of the resulting object, after applying this instruction 96 * stream to the base object, in bytes. 97 * @throws java.io.IOException 98 * the output buffer cannot store the instruction stream's 99 * header with the size fields. 100 */ 101 public DeltaEncoder(OutputStream out, long baseSize, long resultSize) 102 throws IOException { 103 this(out, baseSize, resultSize, 0); 104 } 105 106 /** 107 * Create an encoder with an upper limit on the instruction size. 108 * 109 * @param out 110 * buffer to store the instructions written. 111 * @param baseSize 112 * size of the base object, in bytes. 113 * @param resultSize 114 * size of the resulting object, after applying this instruction 115 * stream to the base object, in bytes. 116 * @param limit 117 * maximum number of bytes to write to the out buffer declaring 118 * the stream is over limit and should be discarded. May be 0 to 119 * specify an infinite limit. 120 * @throws java.io.IOException 121 * the output buffer cannot store the instruction stream's 122 * header with the size fields. 123 */ 124 public DeltaEncoder(OutputStream out, long baseSize, long resultSize, 125 int limit) throws IOException { 126 this.out = out; 127 this.limit = limit; 128 writeVarint(baseSize); 129 writeVarint(resultSize); 130 } 131 132 private void writeVarint(long sz) throws IOException { 133 int p = 0; 134 while (sz >= 0x80) { 135 buf[p++] = (byte) (0x80 | (((int) sz) & 0x7f)); 136 sz >>>= 7; 137 } 138 buf[p++] = (byte) (((int) sz) & 0x7f); 139 size += p; 140 if (limit == 0 || size < limit) 141 out.write(buf, 0, p); 142 } 143 144 /** 145 * Get current size of the delta stream, in bytes. 146 * 147 * @return current size of the delta stream, in bytes. 148 */ 149 public int getSize() { 150 return size; 151 } 152 153 /** 154 * Insert a literal string of text, in UTF-8 encoding. 155 * 156 * @param text 157 * the string to insert. 158 * @return true if the insert fits within the limit; false if the insert 159 * would cause the instruction stream to exceed the limit. 160 * @throws java.io.IOException 161 * the instruction buffer can't store the instructions. 162 */ 163 public boolean insert(String text) throws IOException { 164 return insert(Constants.encode(text)); 165 } 166 167 /** 168 * Insert a literal binary sequence. 169 * 170 * @param text 171 * the binary to insert. 172 * @return true if the insert fits within the limit; false if the insert 173 * would cause the instruction stream to exceed the limit. 174 * @throws java.io.IOException 175 * the instruction buffer can't store the instructions. 176 */ 177 public boolean insert(byte[] text) throws IOException { 178 return insert(text, 0, text.length); 179 } 180 181 /** 182 * Insert a literal binary sequence. 183 * 184 * @param text 185 * the binary to insert. 186 * @param off 187 * offset within {@code text} to start copying from. 188 * @param cnt 189 * number of bytes to insert. 190 * @return true if the insert fits within the limit; false if the insert 191 * would cause the instruction stream to exceed the limit. 192 * @throws java.io.IOException 193 * the instruction buffer can't store the instructions. 194 */ 195 public boolean insert(byte[] text, int off, int cnt) 196 throws IOException { 197 if (cnt <= 0) 198 return true; 199 if (limit != 0) { 200 int hdrs = cnt / MAX_INSERT_DATA_SIZE; 201 if (cnt % MAX_INSERT_DATA_SIZE != 0) 202 hdrs++; 203 if (limit < size + hdrs + cnt) 204 return false; 205 } 206 do { 207 int n = Math.min(MAX_INSERT_DATA_SIZE, cnt); 208 out.write((byte) n); 209 out.write(text, off, n); 210 off += n; 211 cnt -= n; 212 size += 1 + n; 213 } while (0 < cnt); 214 return true; 215 } 216 217 /** 218 * Create a copy instruction to copy from the base object. 219 * 220 * @param offset 221 * position in the base object to copy from. This is absolute, 222 * from the beginning of the base. 223 * @param cnt 224 * number of bytes to copy. 225 * @return true if the copy fits within the limit; false if the copy 226 * would cause the instruction stream to exceed the limit. 227 * @throws java.io.IOException 228 * the instruction buffer cannot store the instructions. 229 */ 230 public boolean copy(long offset, int cnt) throws IOException { 231 if (cnt == 0) 232 return true; 233 234 int p = 0; 235 236 // We cannot encode more than MAX_V2_COPY bytes in a single 237 // command, so encode that much and start a new command. 238 // This limit is imposed by the pack file format rules. 239 // 240 while (MAX_V2_COPY < cnt) { 241 p = encodeCopy(p, offset, MAX_V2_COPY); 242 offset += MAX_V2_COPY; 243 cnt -= MAX_V2_COPY; 244 245 if (buf.length < p + MAX_COPY_CMD_SIZE) { 246 if (limit != 0 && limit < size + p) 247 return false; 248 out.write(buf, 0, p); 249 size += p; 250 p = 0; 251 } 252 } 253 254 p = encodeCopy(p, offset, cnt); 255 if (limit != 0 && limit < size + p) 256 return false; 257 out.write(buf, 0, p); 258 size += p; 259 return true; 260 } 261 262 private int encodeCopy(int p, long offset, int cnt) { 263 int cmd = 0x80; 264 final int cmdPtr = p++; // save room for the command 265 byte b; 266 267 if ((b = (byte) (offset & 0xff)) != 0) { 268 cmd |= 0x01; 269 buf[p++] = b; 270 } 271 if ((b = (byte) ((offset >>> 8) & 0xff)) != 0) { 272 cmd |= 0x02; 273 buf[p++] = b; 274 } 275 if ((b = (byte) ((offset >>> 16) & 0xff)) != 0) { 276 cmd |= 0x04; 277 buf[p++] = b; 278 } 279 if ((b = (byte) ((offset >>> 24) & 0xff)) != 0) { 280 cmd |= 0x08; 281 buf[p++] = b; 282 } 283 284 if (cnt != MAX_V2_COPY) { 285 if ((b = (byte) (cnt & 0xff)) != 0) { 286 cmd |= 0x10; 287 buf[p++] = b; 288 } 289 if ((b = (byte) ((cnt >>> 8) & 0xff)) != 0) { 290 cmd |= 0x20; 291 buf[p++] = b; 292 } 293 if ((b = (byte) ((cnt >>> 16) & 0xff)) != 0) { 294 cmd |= 0x40; 295 buf[p++] = b; 296 } 297 } 298 299 buf[cmdPtr] = (byte) cmd; 300 return p; 301 } 302 }