1 /*
2 * Copyright (C) 2010, Google Inc. and others
3 *
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Distribution License v. 1.0 which is available at
6 * https://www.eclipse.org/org/documents/edl-v10.php.
7 *
8 * SPDX-License-Identifier: BSD-3-Clause
9 */
10
11 package org.eclipse.jgit.internal.storage.pack;
12
13 import java.io.IOException;
14 import java.io.OutputStream;
15
16 import org.eclipse.jgit.lib.Constants;
17
18 /**
19 * Encodes an instruction stream for
20 * {@link org.eclipse.jgit.internal.storage.pack.BinaryDelta}.
21 */
22 public class DeltaEncoder {
23 /**
24 * Maximum number of bytes to be copied in pack v2 format.
25 * <p>
26 * Historical limitations have this at 64k, even though current delta
27 * decoders recognize larger copy instructions.
28 */
29 private static final int MAX_V2_COPY = 0x10000;
30
31 /*
32 * Maximum number of bytes to be copied in pack v3 format.
33 *
34 * Current delta decoders can recognize a copy instruction with a count that
35 * is this large, but the historical limitation of {@link MAX_V2_COPY} is
36 * still used.
37 */
38 // private static final int MAX_V3_COPY = (0xff << 16) | (0xff << 8) | 0xff;
39
40 /** Maximum number of bytes used by a copy instruction. */
41 private static final int MAX_COPY_CMD_SIZE = 8;
42
43 /** Maximum length that an insert command can encode at once. */
44 private static final int MAX_INSERT_DATA_SIZE = 127;
45
46 private final OutputStream out;
47
48 private final byte[] buf = new byte[MAX_COPY_CMD_SIZE * 4];
49
50 private final int limit;
51
52 private int size;
53
54 /**
55 * Create an encoder with no upper bound on the instruction stream size.
56 *
57 * @param out
58 * buffer to store the instructions written.
59 * @param baseSize
60 * size of the base object, in bytes.
61 * @param resultSize
62 * size of the resulting object, after applying this instruction
63 * stream to the base object, in bytes.
64 * @throws java.io.IOException
65 * the output buffer cannot store the instruction stream's
66 * header with the size fields.
67 */
68 public DeltaEncoder(OutputStream out, long baseSize, long resultSize)
69 throws IOException {
70 this(out, baseSize, resultSize, 0);
71 }
72
73 /**
74 * Create an encoder with an upper limit on the instruction size.
75 *
76 * @param out
77 * buffer to store the instructions written.
78 * @param baseSize
79 * size of the base object, in bytes.
80 * @param resultSize
81 * size of the resulting object, after applying this instruction
82 * stream to the base object, in bytes.
83 * @param limit
84 * maximum number of bytes to write to the out buffer declaring
85 * the stream is over limit and should be discarded. May be 0 to
86 * specify an infinite limit.
87 * @throws java.io.IOException
88 * the output buffer cannot store the instruction stream's
89 * header with the size fields.
90 */
91 public DeltaEncoder(OutputStream out, long baseSize, long resultSize,
92 int limit) throws IOException {
93 this.out = out;
94 this.limit = limit;
95 writeVarint(baseSize);
96 writeVarint(resultSize);
97 }
98
99 private void writeVarint(long sz) throws IOException {
100 int p = 0;
101 while (sz >= 0x80) {
102 buf[p++] = (byte) (0x80 | (((int) sz) & 0x7f));
103 sz >>>= 7;
104 }
105 buf[p++] = (byte) (((int) sz) & 0x7f);
106 size += p;
107 if (limit == 0 || size < limit)
108 out.write(buf, 0, p);
109 }
110
111 /**
112 * Get current size of the delta stream, in bytes.
113 *
114 * @return current size of the delta stream, in bytes.
115 */
116 public int getSize() {
117 return size;
118 }
119
120 /**
121 * Insert a literal string of text, in UTF-8 encoding.
122 *
123 * @param text
124 * the string to insert.
125 * @return true if the insert fits within the limit; false if the insert
126 * would cause the instruction stream to exceed the limit.
127 * @throws java.io.IOException
128 * the instruction buffer can't store the instructions.
129 */
130 public boolean insert(String text) throws IOException {
131 return insert(Constants.encode(text));
132 }
133
134 /**
135 * Insert a literal binary sequence.
136 *
137 * @param text
138 * the binary to insert.
139 * @return true if the insert fits within the limit; false if the insert
140 * would cause the instruction stream to exceed the limit.
141 * @throws java.io.IOException
142 * the instruction buffer can't store the instructions.
143 */
144 public boolean insert(byte[] text) throws IOException {
145 return insert(text, 0, text.length);
146 }
147
148 /**
149 * Insert a literal binary sequence.
150 *
151 * @param text
152 * the binary to insert.
153 * @param off
154 * offset within {@code text} to start copying from.
155 * @param cnt
156 * number of bytes to insert.
157 * @return true if the insert fits within the limit; false if the insert
158 * would cause the instruction stream to exceed the limit.
159 * @throws java.io.IOException
160 * the instruction buffer can't store the instructions.
161 */
162 public boolean insert(byte[] text, int off, int cnt)
163 throws IOException {
164 if (cnt <= 0)
165 return true;
166 if (limit != 0) {
167 int hdrs = cnt / MAX_INSERT_DATA_SIZE;
168 if (cnt % MAX_INSERT_DATA_SIZE != 0)
169 hdrs++;
170 if (limit < size + hdrs + cnt)
171 return false;
172 }
173 do {
174 int n = Math.min(MAX_INSERT_DATA_SIZE, cnt);
175 out.write((byte) n);
176 out.write(text, off, n);
177 off += n;
178 cnt -= n;
179 size += 1 + n;
180 } while (0 < cnt);
181 return true;
182 }
183
184 /**
185 * Create a copy instruction to copy from the base object.
186 *
187 * @param offset
188 * position in the base object to copy from. This is absolute,
189 * from the beginning of the base.
190 * @param cnt
191 * number of bytes to copy.
192 * @return true if the copy fits within the limit; false if the copy
193 * would cause the instruction stream to exceed the limit.
194 * @throws java.io.IOException
195 * the instruction buffer cannot store the instructions.
196 */
197 public boolean copy(long offset, int cnt) throws IOException {
198 if (cnt == 0)
199 return true;
200
201 int p = 0;
202
203 // We cannot encode more than MAX_V2_COPY bytes in a single
204 // command, so encode that much and start a new command.
205 // This limit is imposed by the pack file format rules.
206 //
207 while (MAX_V2_COPY < cnt) {
208 p = encodeCopy(p, offset, MAX_V2_COPY);
209 offset += MAX_V2_COPY;
210 cnt -= MAX_V2_COPY;
211
212 if (buf.length < p + MAX_COPY_CMD_SIZE) {
213 if (limit != 0 && limit < size + p)
214 return false;
215 out.write(buf, 0, p);
216 size += p;
217 p = 0;
218 }
219 }
220
221 p = encodeCopy(p, offset, cnt);
222 if (limit != 0 && limit < size + p)
223 return false;
224 out.write(buf, 0, p);
225 size += p;
226 return true;
227 }
228
229 private int encodeCopy(int p, long offset, int cnt) {
230 int cmd = 0x80;
231 final int cmdPtr = p++; // save room for the command
232 byte b;
233
234 if ((b = (byte) (offset & 0xff)) != 0) {
235 cmd |= 0x01;
236 buf[p++] = b;
237 }
238 if ((b = (byte) ((offset >>> 8) & 0xff)) != 0) {
239 cmd |= 0x02;
240 buf[p++] = b;
241 }
242 if ((b = (byte) ((offset >>> 16) & 0xff)) != 0) {
243 cmd |= 0x04;
244 buf[p++] = b;
245 }
246 if ((b = (byte) ((offset >>> 24) & 0xff)) != 0) {
247 cmd |= 0x08;
248 buf[p++] = b;
249 }
250
251 if (cnt != MAX_V2_COPY) {
252 if ((b = (byte) (cnt & 0xff)) != 0) {
253 cmd |= 0x10;
254 buf[p++] = b;
255 }
256 if ((b = (byte) ((cnt >>> 8) & 0xff)) != 0) {
257 cmd |= 0x20;
258 buf[p++] = b;
259 }
260 if ((b = (byte) ((cnt >>> 16) & 0xff)) != 0) {
261 cmd |= 0x40;
262 buf[p++] = b;
263 }
264 }
265
266 buf[cmdPtr] = (byte) cmd;
267 return p;
268 }
269 }