1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.pack;
12
13 import java.io.IOException;
14 import java.io.OutputStream;
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 public class DeltaIndex {
38
39 static final int BLKSZ = 16;
40
41
42
43
44
45
46
47
48
49
50 public static long estimateIndexSize(int sourceLength) {
51 return sourceLength + (sourceLength * 3 / 4);
52 }
53
54
55
56
57
58
59
60
61 private static final int MAX_CHAIN_LENGTH = 64;
62
63
64 private final byte[] src;
65
66
67
68
69
70
71
72
73
74
75
76
77 private final int[] table;
78
79
80
81
82
83
84
85
86
87 private final long[] entries;
88
89
90 private final int tableMask;
91
92
93
94
95
96
97
98
99
100 public DeltaIndex(byte[] sourceBuffer) {
101 src = sourceBuffer;
102
103 DeltaIndexScanner scan = new DeltaIndexScanner(src, src.length);
104
105
106
107
108 table = scan.table;
109 tableMask = scan.tableMask;
110
111
112
113
114 entries = new long[1 + countEntries(scan)];
115 copyEntries(scan);
116 }
117
118 private int countEntries(DeltaIndexScanner scan) {
119
120
121
122
123
124 int cnt = 0;
125 for (int element : table) {
126 int h = element;
127 if (h == 0)
128 continue;
129
130 int len = 0;
131 do {
132 if (++len == MAX_CHAIN_LENGTH) {
133 scan.next[h] = 0;
134 break;
135 }
136 h = scan.next[h];
137 } while (h != 0);
138 cnt += len;
139 }
140 return cnt;
141 }
142
143 private void copyEntries(DeltaIndexScanner scan) {
144
145
146
147
148 int next = 1;
149 for (int i = 0; i < table.length; i++) {
150 int h = table[i];
151 if (h == 0)
152 continue;
153
154 table[i] = next;
155 do {
156 entries[next++] = scan.entries[h];
157 h = scan.next[h];
158 } while (h != 0);
159 }
160 }
161
162
163
164
165
166
167 public long getSourceSize() {
168 return src.length;
169 }
170
171
172
173
174
175
176
177
178
179 public long getIndexSize() {
180 long sz = 8 ;
181 sz += 4 * 4 ;
182 sz += sizeOf(src);
183 sz += sizeOf(table);
184 sz += sizeOf(entries);
185 return sz;
186 }
187
188 private static long sizeOf(byte[] b) {
189 return sizeOfArray(1, b.length);
190 }
191
192 private static long sizeOf(int[] b) {
193 return sizeOfArray(4, b.length);
194 }
195
196 private static long sizeOf(long[] b) {
197 return sizeOfArray(8, b.length);
198 }
199
200 private static int sizeOfArray(int entSize, int len) {
201 return 12 + (len * entSize);
202 }
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222 public void encode(OutputStream out, byte[] res) throws IOException {
223 encode(out, res, 0 );
224 }
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252 public boolean encode(OutputStream out, byte[] res, int deltaSizeLimit)
253 throws IOException {
254 final int end = res.length;
255 final DeltaEncoder enc = newEncoder(out, end, deltaSizeLimit);
256
257
258
259
260
261
262 if (end < BLKSZ || table.length == 0)
263 return enc.insert(res);
264
265
266
267
268 int blkPtr = 0;
269 int blkEnd = BLKSZ;
270 int hash = hashBlock(res, 0);
271
272 int resPtr = 0;
273 while (blkEnd < end) {
274 final int tableIdx = hash & tableMask;
275 int entryIdx = table[tableIdx];
276 if (entryIdx == 0) {
277
278
279 hash = step(hash, res[blkPtr++], res[blkEnd++]);
280 continue;
281 }
282
283
284
285
286 int bestLen = -1;
287 int bestPtr = -1;
288 int bestNeg = 0;
289 do {
290 long ent = entries[entryIdx++];
291 if (keyOf(ent) == hash) {
292 int neg = 0;
293 if (resPtr < blkPtr) {
294
295
296
297
298
299
300
301 neg = blkPtr - resPtr;
302 neg = negmatch(res, blkPtr, src, valOf(ent), neg);
303 }
304
305 int len = neg + fwdmatch(res, blkPtr, src, valOf(ent));
306 if (bestLen < len) {
307 bestLen = len;
308 bestPtr = valOf(ent);
309 bestNeg = neg;
310 }
311 } else if ((keyOf(ent) & tableMask) != tableIdx)
312 break;
313 } while (bestLen < 4096 && entryIdx < entries.length);
314
315 if (bestLen < BLKSZ) {
316
317
318
319
320
321 hash = step(hash, res[blkPtr++], res[blkEnd++]);
322 continue;
323 }
324
325 blkPtr -= bestNeg;
326
327 if (resPtr < blkPtr) {
328
329
330
331
332
333 int cnt = blkPtr - resPtr;
334 if (!enc.insert(res, resPtr, cnt))
335 return false;
336 }
337
338 if (!enc.copy(bestPtr - bestNeg, bestLen))
339 return false;
340
341 blkPtr += bestLen;
342 resPtr = blkPtr;
343 blkEnd = blkPtr + BLKSZ;
344
345
346
347 if (end <= blkEnd)
348 break;
349
350
351
352 hash = hashBlock(res, blkPtr);
353 }
354
355 if (resPtr < end) {
356
357
358
359 int cnt = end - resPtr;
360 return enc.insert(res, resPtr, cnt);
361 }
362 return true;
363 }
364
365 private DeltaEncoder newEncoder(OutputStream out, long resSize, int limit)
366 throws IOException {
367 return new DeltaEncoder(out, getSourceSize(), resSize, limit);
368 }
369
370 private static int fwdmatch(byte[] res, int resPtr, byte[] src, int srcPtr) {
371 int start = resPtr;
372 for (; resPtr < res.length && srcPtr < src.length; resPtr++, srcPtr++) {
373 if (res[resPtr] != src[srcPtr])
374 break;
375 }
376 return resPtr - start;
377 }
378
379 private static int negmatch(byte[] res, int resPtr, byte[] src, int srcPtr,
380 int limit) {
381 if (srcPtr == 0)
382 return 0;
383
384 resPtr--;
385 srcPtr--;
386 int start = resPtr;
387 do {
388 if (res[resPtr] != src[srcPtr])
389 break;
390 resPtr--;
391 srcPtr--;
392 } while (0 <= srcPtr && 0 < --limit);
393 return start - resPtr;
394 }
395
396
397 @Override
398 @SuppressWarnings("nls")
399 public String toString() {
400 String[] units = { "bytes", "KiB", "MiB", "GiB" };
401 long sz = getIndexSize();
402 int u = 0;
403 while (1024 <= sz && u < units.length - 1) {
404 int rem = (int) (sz % 1024);
405 sz /= 1024;
406 if (rem != 0)
407 sz++;
408 u++;
409 }
410 return "DeltaIndex[" + sz + " " + units[u] + "]";
411 }
412
413 static int hashBlock(byte[] raw, int ptr) {
414 int hash;
415
416
417
418
419 hash = ((raw[ptr] & 0xff) << 24)
420 | ((raw[ptr + 1] & 0xff) << 16)
421 | ((raw[ptr + 2] & 0xff) << 8)
422 | (raw[ptr + 3] & 0xff);
423 hash ^= T[hash >>> 31];
424
425 hash = ((hash << 8) | (raw[ptr + 4] & 0xff)) ^ T[hash >>> 23];
426 hash = ((hash << 8) | (raw[ptr + 5] & 0xff)) ^ T[hash >>> 23];
427 hash = ((hash << 8) | (raw[ptr + 6] & 0xff)) ^ T[hash >>> 23];
428 hash = ((hash << 8) | (raw[ptr + 7] & 0xff)) ^ T[hash >>> 23];
429
430 hash = ((hash << 8) | (raw[ptr + 8] & 0xff)) ^ T[hash >>> 23];
431 hash = ((hash << 8) | (raw[ptr + 9] & 0xff)) ^ T[hash >>> 23];
432 hash = ((hash << 8) | (raw[ptr + 10] & 0xff)) ^ T[hash >>> 23];
433 hash = ((hash << 8) | (raw[ptr + 11] & 0xff)) ^ T[hash >>> 23];
434
435 hash = ((hash << 8) | (raw[ptr + 12] & 0xff)) ^ T[hash >>> 23];
436 hash = ((hash << 8) | (raw[ptr + 13] & 0xff)) ^ T[hash >>> 23];
437 hash = ((hash << 8) | (raw[ptr + 14] & 0xff)) ^ T[hash >>> 23];
438 hash = ((hash << 8) | (raw[ptr + 15] & 0xff)) ^ T[hash >>> 23];
439
440 return hash;
441 }
442
443 private static int step(int hash, byte toRemove, byte toAdd) {
444 hash ^= U[toRemove & 0xff];
445 return ((hash << 8) | (toAdd & 0xff)) ^ T[hash >>> 23];
446 }
447
448 private static int keyOf(long ent) {
449 return (int) (ent >>> 32);
450 }
451
452 private static int valOf(long ent) {
453 return (int) ent;
454 }
455
456 private static final int[] T = { 0x00000000, 0xd4c6b32d, 0x7d4bd577,
457 0xa98d665a, 0x2e5119c3, 0xfa97aaee, 0x531accb4, 0x87dc7f99,
458 0x5ca23386, 0x886480ab, 0x21e9e6f1, 0xf52f55dc, 0x72f32a45,
459 0xa6359968, 0x0fb8ff32, 0xdb7e4c1f, 0x6d82d421, 0xb944670c,
460 0x10c90156, 0xc40fb27b, 0x43d3cde2, 0x97157ecf, 0x3e981895,
461 0xea5eabb8, 0x3120e7a7, 0xe5e6548a, 0x4c6b32d0, 0x98ad81fd,
462 0x1f71fe64, 0xcbb74d49, 0x623a2b13, 0xb6fc983e, 0x0fc31b6f,
463 0xdb05a842, 0x7288ce18, 0xa64e7d35, 0x219202ac, 0xf554b181,
464 0x5cd9d7db, 0x881f64f6, 0x536128e9, 0x87a79bc4, 0x2e2afd9e,
465 0xfaec4eb3, 0x7d30312a, 0xa9f68207, 0x007be45d, 0xd4bd5770,
466 0x6241cf4e, 0xb6877c63, 0x1f0a1a39, 0xcbcca914, 0x4c10d68d,
467 0x98d665a0, 0x315b03fa, 0xe59db0d7, 0x3ee3fcc8, 0xea254fe5,
468 0x43a829bf, 0x976e9a92, 0x10b2e50b, 0xc4745626, 0x6df9307c,
469 0xb93f8351, 0x1f8636de, 0xcb4085f3, 0x62cde3a9, 0xb60b5084,
470 0x31d72f1d, 0xe5119c30, 0x4c9cfa6a, 0x985a4947, 0x43240558,
471 0x97e2b675, 0x3e6fd02f, 0xeaa96302, 0x6d751c9b, 0xb9b3afb6,
472 0x103ec9ec, 0xc4f87ac1, 0x7204e2ff, 0xa6c251d2, 0x0f4f3788,
473 0xdb8984a5, 0x5c55fb3c, 0x88934811, 0x211e2e4b, 0xf5d89d66,
474 0x2ea6d179, 0xfa606254, 0x53ed040e, 0x872bb723, 0x00f7c8ba,
475 0xd4317b97, 0x7dbc1dcd, 0xa97aaee0, 0x10452db1, 0xc4839e9c,
476 0x6d0ef8c6, 0xb9c84beb, 0x3e143472, 0xead2875f, 0x435fe105,
477 0x97995228, 0x4ce71e37, 0x9821ad1a, 0x31accb40, 0xe56a786d,
478 0x62b607f4, 0xb670b4d9, 0x1ffdd283, 0xcb3b61ae, 0x7dc7f990,
479 0xa9014abd, 0x008c2ce7, 0xd44a9fca, 0x5396e053, 0x8750537e,
480 0x2edd3524, 0xfa1b8609, 0x2165ca16, 0xf5a3793b, 0x5c2e1f61,
481 0x88e8ac4c, 0x0f34d3d5, 0xdbf260f8, 0x727f06a2, 0xa6b9b58f,
482 0x3f0c6dbc, 0xebcade91, 0x4247b8cb, 0x96810be6, 0x115d747f,
483 0xc59bc752, 0x6c16a108, 0xb8d01225, 0x63ae5e3a, 0xb768ed17,
484 0x1ee58b4d, 0xca233860, 0x4dff47f9, 0x9939f4d4, 0x30b4928e,
485 0xe47221a3, 0x528eb99d, 0x86480ab0, 0x2fc56cea, 0xfb03dfc7,
486 0x7cdfa05e, 0xa8191373, 0x01947529, 0xd552c604, 0x0e2c8a1b,
487 0xdaea3936, 0x73675f6c, 0xa7a1ec41, 0x207d93d8, 0xf4bb20f5,
488 0x5d3646af, 0x89f0f582, 0x30cf76d3, 0xe409c5fe, 0x4d84a3a4,
489 0x99421089, 0x1e9e6f10, 0xca58dc3d, 0x63d5ba67, 0xb713094a,
490 0x6c6d4555, 0xb8abf678, 0x11269022, 0xc5e0230f, 0x423c5c96,
491 0x96faefbb, 0x3f7789e1, 0xebb13acc, 0x5d4da2f2, 0x898b11df,
492 0x20067785, 0xf4c0c4a8, 0x731cbb31, 0xa7da081c, 0x0e576e46,
493 0xda91dd6b, 0x01ef9174, 0xd5292259, 0x7ca44403, 0xa862f72e,
494 0x2fbe88b7, 0xfb783b9a, 0x52f55dc0, 0x8633eeed, 0x208a5b62,
495 0xf44ce84f, 0x5dc18e15, 0x89073d38, 0x0edb42a1, 0xda1df18c,
496 0x739097d6, 0xa75624fb, 0x7c2868e4, 0xa8eedbc9, 0x0163bd93,
497 0xd5a50ebe, 0x52797127, 0x86bfc20a, 0x2f32a450, 0xfbf4177d,
498 0x4d088f43, 0x99ce3c6e, 0x30435a34, 0xe485e919, 0x63599680,
499 0xb79f25ad, 0x1e1243f7, 0xcad4f0da, 0x11aabcc5, 0xc56c0fe8,
500 0x6ce169b2, 0xb827da9f, 0x3ffba506, 0xeb3d162b, 0x42b07071,
501 0x9676c35c, 0x2f49400d, 0xfb8ff320, 0x5202957a, 0x86c42657,
502 0x011859ce, 0xd5deeae3, 0x7c538cb9, 0xa8953f94, 0x73eb738b,
503 0xa72dc0a6, 0x0ea0a6fc, 0xda6615d1, 0x5dba6a48, 0x897cd965,
504 0x20f1bf3f, 0xf4370c12, 0x42cb942c, 0x960d2701, 0x3f80415b,
505 0xeb46f276, 0x6c9a8def, 0xb85c3ec2, 0x11d15898, 0xc517ebb5,
506 0x1e69a7aa, 0xcaaf1487, 0x632272dd, 0xb7e4c1f0, 0x3038be69,
507 0xe4fe0d44, 0x4d736b1e, 0x99b5d833 };
508
509 private static final int[] U = { 0x00000000, 0x12c6e90f, 0x258dd21e,
510 0x374b3b11, 0x4b1ba43c, 0x59dd4d33, 0x6e967622, 0x7c509f2d,
511 0x42f1fb55, 0x5037125a, 0x677c294b, 0x75bac044, 0x09ea5f69,
512 0x1b2cb666, 0x2c678d77, 0x3ea16478, 0x51254587, 0x43e3ac88,
513 0x74a89799, 0x666e7e96, 0x1a3ee1bb, 0x08f808b4, 0x3fb333a5,
514 0x2d75daaa, 0x13d4bed2, 0x011257dd, 0x36596ccc, 0x249f85c3,
515 0x58cf1aee, 0x4a09f3e1, 0x7d42c8f0, 0x6f8421ff, 0x768c3823,
516 0x644ad12c, 0x5301ea3d, 0x41c70332, 0x3d979c1f, 0x2f517510,
517 0x181a4e01, 0x0adca70e, 0x347dc376, 0x26bb2a79, 0x11f01168,
518 0x0336f867, 0x7f66674a, 0x6da08e45, 0x5aebb554, 0x482d5c5b,
519 0x27a97da4, 0x356f94ab, 0x0224afba, 0x10e246b5, 0x6cb2d998,
520 0x7e743097, 0x493f0b86, 0x5bf9e289, 0x655886f1, 0x779e6ffe,
521 0x40d554ef, 0x5213bde0, 0x2e4322cd, 0x3c85cbc2, 0x0bcef0d3,
522 0x190819dc, 0x39dec36b, 0x2b182a64, 0x1c531175, 0x0e95f87a,
523 0x72c56757, 0x60038e58, 0x5748b549, 0x458e5c46, 0x7b2f383e,
524 0x69e9d131, 0x5ea2ea20, 0x4c64032f, 0x30349c02, 0x22f2750d,
525 0x15b94e1c, 0x077fa713, 0x68fb86ec, 0x7a3d6fe3, 0x4d7654f2,
526 0x5fb0bdfd, 0x23e022d0, 0x3126cbdf, 0x066df0ce, 0x14ab19c1,
527 0x2a0a7db9, 0x38cc94b6, 0x0f87afa7, 0x1d4146a8, 0x6111d985,
528 0x73d7308a, 0x449c0b9b, 0x565ae294, 0x4f52fb48, 0x5d941247,
529 0x6adf2956, 0x7819c059, 0x04495f74, 0x168fb67b, 0x21c48d6a,
530 0x33026465, 0x0da3001d, 0x1f65e912, 0x282ed203, 0x3ae83b0c,
531 0x46b8a421, 0x547e4d2e, 0x6335763f, 0x71f39f30, 0x1e77becf,
532 0x0cb157c0, 0x3bfa6cd1, 0x293c85de, 0x556c1af3, 0x47aaf3fc,
533 0x70e1c8ed, 0x622721e2, 0x5c86459a, 0x4e40ac95, 0x790b9784,
534 0x6bcd7e8b, 0x179de1a6, 0x055b08a9, 0x321033b8, 0x20d6dab7,
535 0x73bd86d6, 0x617b6fd9, 0x563054c8, 0x44f6bdc7, 0x38a622ea,
536 0x2a60cbe5, 0x1d2bf0f4, 0x0fed19fb, 0x314c7d83, 0x238a948c,
537 0x14c1af9d, 0x06074692, 0x7a57d9bf, 0x689130b0, 0x5fda0ba1,
538 0x4d1ce2ae, 0x2298c351, 0x305e2a5e, 0x0715114f, 0x15d3f840,
539 0x6983676d, 0x7b458e62, 0x4c0eb573, 0x5ec85c7c, 0x60693804,
540 0x72afd10b, 0x45e4ea1a, 0x57220315, 0x2b729c38, 0x39b47537,
541 0x0eff4e26, 0x1c39a729, 0x0531bef5, 0x17f757fa, 0x20bc6ceb,
542 0x327a85e4, 0x4e2a1ac9, 0x5cecf3c6, 0x6ba7c8d7, 0x796121d8,
543 0x47c045a0, 0x5506acaf, 0x624d97be, 0x708b7eb1, 0x0cdbe19c,
544 0x1e1d0893, 0x29563382, 0x3b90da8d, 0x5414fb72, 0x46d2127d,
545 0x7199296c, 0x635fc063, 0x1f0f5f4e, 0x0dc9b641, 0x3a828d50,
546 0x2844645f, 0x16e50027, 0x0423e928, 0x3368d239, 0x21ae3b36,
547 0x5dfea41b, 0x4f384d14, 0x78737605, 0x6ab59f0a, 0x4a6345bd,
548 0x58a5acb2, 0x6fee97a3, 0x7d287eac, 0x0178e181, 0x13be088e,
549 0x24f5339f, 0x3633da90, 0x0892bee8, 0x1a5457e7, 0x2d1f6cf6,
550 0x3fd985f9, 0x43891ad4, 0x514ff3db, 0x6604c8ca, 0x74c221c5,
551 0x1b46003a, 0x0980e935, 0x3ecbd224, 0x2c0d3b2b, 0x505da406,
552 0x429b4d09, 0x75d07618, 0x67169f17, 0x59b7fb6f, 0x4b711260,
553 0x7c3a2971, 0x6efcc07e, 0x12ac5f53, 0x006ab65c, 0x37218d4d,
554 0x25e76442, 0x3cef7d9e, 0x2e299491, 0x1962af80, 0x0ba4468f,
555 0x77f4d9a2, 0x653230ad, 0x52790bbc, 0x40bfe2b3, 0x7e1e86cb,
556 0x6cd86fc4, 0x5b9354d5, 0x4955bdda, 0x350522f7, 0x27c3cbf8,
557 0x1088f0e9, 0x024e19e6, 0x6dca3819, 0x7f0cd116, 0x4847ea07,
558 0x5a810308, 0x26d19c25, 0x3417752a, 0x035c4e3b, 0x119aa734,
559 0x2f3bc34c, 0x3dfd2a43, 0x0ab61152, 0x1870f85d, 0x64206770,
560 0x76e68e7f, 0x41adb56e, 0x536b5c61 };
561 }