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