0000: 2f 2a 20 54 68 69 73 20 53 6f 75 72 63 65 20 43 /* This Source C
0010: 6f 64 65 20 46 6f 72 6d 20 69 73 20 73 75 62 6a ode Form is subj
0020: 65 63 74 20 74 6f 20 74 68 65 20 74 65 72 6d 73 ect to the terms
0030: 20 6f 66 20 74 68 65 20 4d 6f 7a 69 6c 6c 61 20 of the Mozilla
0040: 50 75 62 6c 69 63 0a 20 2a 20 4c 69 63 65 6e 73 Public. * Licens
0050: 65 2c 20 76 2e 20 32 2e 30 2e 20 49 66 20 61 20 e, v. 2.0. If a
0060: 63 6f 70 79 20 6f 66 20 74 68 65 20 4d 50 4c 20 copy of the MPL
0070: 77 61 73 20 6e 6f 74 20 64 69 73 74 72 69 62 75 was not distribu
0080: 74 65 64 20 77 69 74 68 20 74 68 69 73 0a 20 2a ted with this. *
0090: 20 66 69 6c 65 2c 20 59 6f 75 20 63 61 6e 20 6f file, You can o
00a0: 62 74 61 69 6e 20 6f 6e 65 20 61 74 20 68 74 74 btain one at htt
00b0: 70 3a 2f 2f 6d 6f 7a 69 6c 6c 61 2e 6f 72 67 2f p://mozilla.org/
00c0: 4d 50 4c 2f 32 2e 30 2f 2e 20 2a 2f 0a 0a 23 69 MPL/2.0/. */..#i
00d0: 6e 63 6c 75 64 65 20 22 63 6f 6d 70 61 74 69 62 nclude "compatib
00e0: 69 6c 69 74 79 2e 68 22 0a 0a 74 79 70 65 64 65 ility.h"..typede
00f0: 66 20 75 69 6e 74 38 5f 74 20 54 6f 6b 65 6e 3b f uint8_t Token;
0100: 20 2f 2f 20 61 6c 6c 20 74 6f 6b 65 6e 73 20 61 // all tokens a
0110: 72 65 20 62 79 74 65 73 0a 74 79 70 65 64 65 66 re bytes.typedef
0120: 20 69 6e 74 36 34 5f 74 20 70 6f 73 3b 20 20 20 int64_t pos;
0130: 2f 2f 20 70 6f 73 69 74 69 6f 6e 73 20 61 72 65 // positions are
0140: 20 36 34 20 62 69 74 0a 0a 23 69 6e 63 6c 75 64 64 bit..#includ
0150: 65 20 3c 73 74 64 69 6f 2e 68 3e 0a 23 69 6e 63 e <stdio.h>.#inc
0160: 6c 75 64 65 20 22 62 64 65 6c 74 61 2e 68 22 0a lude "bdelta.h".
0170: 23 69 6e 63 6c 75 64 65 20 22 63 68 65 63 6b 73 #include "checks
0180: 75 6d 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 3c um.h".#include <
0190: 6c 69 73 74 3e 0a 23 69 6e 63 6c 75 64 65 20 3c list>.#include <
01a0: 6c 69 6d 69 74 73 3e 0a 23 69 6e 63 6c 75 64 65 limits>.#include
01b0: 20 3c 61 6c 67 6f 72 69 74 68 6d 3e 0a 63 6f 6e <algorithm>.con
01c0: 73 74 20 62 6f 6f 6c 20 76 65 72 62 6f 73 65 20 st bool verbose
01d0: 3d 20 66 61 6c 73 65 3b 0a 73 74 72 75 63 74 20 = false;.struct
01e0: 63 68 65 63 6b 73 75 6d 5f 65 6e 74 72 79 20 7b checksum_entry {
01f0: 0a 09 48 61 73 68 3a 3a 56 61 6c 75 65 20 63 6b ..Hash::Value ck
0200: 73 75 6d 3b 20 2f 2f 52 6f 6c 6c 69 6e 67 20 63 sum; //Rolling c
0210: 68 65 63 6b 73 75 6d 73 0a 09 70 6f 73 20 6c 6f hecksums..pos lo
0220: 63 3b 0a 09 63 68 65 63 6b 73 75 6d 5f 65 6e 74 c;..checksum_ent
0230: 72 79 28 29 20 7b 7d 0a 09 63 68 65 63 6b 73 75 ry() {}..checksu
0240: 6d 5f 65 6e 74 72 79 28 48 61 73 68 3a 3a 56 61 m_entry(Hash::Va
0250: 6c 75 65 20 63 6b 73 75 6d 2c 20 70 6f 73 20 6c lue cksum, pos l
0260: 6f 63 29 0a 09 09 7b 74 68 69 73 2d 3e 63 6b 73 oc)...{this->cks
0270: 75 6d 20 3d 20 63 6b 73 75 6d 3b 20 74 68 69 73 um = cksum; this
0280: 2d 3e 6c 6f 63 20 3d 20 6c 6f 63 3b 7d 0a 7d 3b ->loc = loc;}.};
0290: 0a 0a 73 74 72 75 63 74 20 52 61 6e 67 65 20 7b ..struct Range {
02a0: 0a 09 70 6f 73 20 70 2c 20 6e 75 6d 3b 0a 09 52 ..pos p, num;..R
02b0: 61 6e 67 65 28 29 20 7b 7d 0a 09 52 61 6e 67 65 ange() {}..Range
02c0: 28 70 6f 73 20 70 2c 20 70 6f 73 20 6e 75 6d 29 (pos p, pos num)
02d0: 20 7b 74 68 69 73 2d 3e 70 20 3d 20 70 3b 20 74 {this->p = p; t
02e0: 68 69 73 2d 3e 6e 75 6d 20 3d 20 6e 75 6d 3b 7d his->num = num;}
02f0: 0a 7d 3b 0a 0a 73 74 72 75 63 74 20 4d 61 74 63 .};..struct Matc
0300: 68 20 7b 0a 09 70 6f 73 20 70 31 2c 20 70 32 2c h {..pos p1, p2,
0310: 20 6e 75 6d 3b 0a 09 4d 61 74 63 68 28 70 6f 73 num;..Match(pos
0320: 20 70 31 2c 20 70 6f 73 20 70 32 2c 20 70 6f 73 p1, pos p2, pos
0330: 20 6e 75 6d 29 20 0a 09 09 7b 74 68 69 73 2d 3e num) ...{this->
0340: 70 31 20 3d 20 70 31 3b 20 74 68 69 73 2d 3e 70 p1 = p1; this->p
0350: 32 20 3d 20 70 32 3b 20 74 68 69 73 2d 3e 6e 75 2 = p2; this->nu
0360: 6d 20 3d 20 6e 75 6d 3b 7d 0a 7d 3b 0a 0a 73 74 m = num;}.};..st
0370: 72 75 63 74 20 5f 42 44 65 6c 74 61 5f 49 6e 73 ruct _BDelta_Ins
0380: 74 61 6e 63 65 20 7b 0a 20 20 76 6f 69 64 20 2a tance {. void *
0390: 68 61 6e 64 6c 65 31 2c 20 2a 68 61 6e 64 6c 65 handle1, *handle
03a0: 32 3b 0a 20 20 70 6f 73 20 64 61 74 61 31 5f 73 2;. pos data1_s
03b0: 69 7a 65 2c 20 64 61 74 61 32 5f 73 69 7a 65 3b ize, data2_size;
03c0: 0a 20 20 73 74 64 3a 3a 6c 69 73 74 3c 4d 61 74 . std::list<Mat
03d0: 63 68 3e 20 6d 61 74 63 68 65 73 3b 0a 20 20 73 ch> matches;. s
03e0: 74 64 3a 3a 6c 69 73 74 3c 4d 61 74 63 68 3e 3a td::list<Match>:
03f0: 3a 69 74 65 72 61 74 6f 72 20 61 63 63 65 73 73 :iterator access
0400: 70 6c 61 63 65 3b 0a 20 20 69 6e 74 20 61 63 63 place;. int acc
0410: 65 73 73 5f 69 6e 74 3b 0a 20 20 69 6e 74 20 65 ess_int;. int e
0420: 72 72 6f 72 63 6f 64 65 3b 0a 20 20 0a 20 20 63 rrorcode;. . c
0430: 6f 6e 73 74 20 54 6f 6b 65 6e 20 2a 72 65 61 64 onst Token *read
0440: 31 28 70 6f 73 20 70 6c 61 63 65 29 20 7b 0a 20 1(pos place) {.
0450: 20 20 20 72 65 74 75 72 6e 20 28 63 6f 6e 73 74 return (const
0460: 20 54 6f 6b 65 6e 2a 29 28 28 54 6f 6b 65 6e 2a Token*)((Token*
0470: 29 68 61 6e 64 6c 65 31 2b 70 6c 61 63 65 29 3b )handle1+place);
0480: 0a 20 20 7d 0a 20 20 63 6f 6e 73 74 20 54 6f 6b . }. const Tok
0490: 65 6e 20 2a 72 65 61 64 32 28 70 6f 73 20 70 6c en *read2(pos pl
04a0: 61 63 65 29 20 7b 0a 20 20 20 20 72 65 74 75 72 ace) {. retur
04b0: 6e 20 28 63 6f 6e 73 74 20 54 6f 6b 65 6e 2a 29 n (const Token*)
04c0: 28 28 54 6f 6b 65 6e 2a 29 68 61 6e 64 6c 65 32 ((Token*)handle2
04d0: 2b 70 6c 61 63 65 29 3b 0a 20 20 7d 0a 7d 3b 0a +place);. }.};.
04e0: 0a 73 74 72 75 63 74 20 43 68 65 63 6b 73 75 6d .struct Checksum
04f0: 73 5f 49 6e 73 74 61 6e 63 65 20 7b 0a 09 75 6e s_Instance {..un
0500: 73 69 67 6e 65 64 20 62 6c 6f 63 6b 73 69 7a 65 signed blocksize
0510: 3b 0a 09 75 6e 73 69 67 6e 65 64 20 68 74 61 62 ;..unsigned htab
0520: 6c 65 73 69 7a 65 3b 0a 09 63 68 65 63 6b 73 75 lesize;..checksu
0530: 6d 5f 65 6e 74 72 79 20 2a 2a 68 74 61 62 6c 65 m_entry **htable
0540: 3b 20 2f 2f 20 50 6f 69 6e 74 73 20 74 6f 20 66 ; // Points to f
0550: 69 72 73 74 20 6d 61 74 63 68 20 69 6e 20 63 68 irst match in ch
0560: 65 63 6b 73 75 6d 73 0a 09 63 68 65 63 6b 73 75 ecksums..checksu
0570: 6d 5f 65 6e 74 72 79 20 2a 63 68 65 63 6b 73 75 m_entry *checksu
0580: 6d 73 3b 20 20 2f 2f 20 53 6f 72 74 65 64 20 6c ms; // Sorted l
0590: 69 73 74 20 6f 66 20 61 6c 6c 20 63 68 65 63 6b ist of all check
05a0: 73 75 6d 73 0a 09 75 6e 73 69 67 6e 65 64 20 6e sums..unsigned n
05b0: 75 6d 63 68 65 63 6b 73 75 6d 73 3b 0a 0a 09 43 umchecksums;...C
05c0: 68 65 63 6b 73 75 6d 73 5f 49 6e 73 74 61 6e 63 hecksums_Instanc
05d0: 65 28 75 6e 73 69 67 6e 65 64 20 62 6c 6f 63 6b e(unsigned block
05e0: 73 69 7a 65 29 20 7b 74 68 69 73 2d 3e 62 6c 6f size) {this->blo
05f0: 63 6b 73 69 7a 65 20 3d 20 62 6c 6f 63 6b 73 69 cksize = blocksi
0600: 7a 65 3b 7d 0a 09 76 6f 69 64 20 61 64 64 28 63 ze;}..void add(c
0610: 68 65 63 6b 73 75 6d 5f 65 6e 74 72 79 20 63 6b hecksum_entry ck
0620: 29 20 7b 0a 09 09 63 68 65 63 6b 73 75 6d 73 5b ) {...checksums[
0630: 6e 75 6d 63 68 65 63 6b 73 75 6d 73 5d 20 3d 20 numchecksums] =
0640: 63 6b 3b 0a 09 09 2b 2b 6e 75 6d 63 68 65 63 6b ck;...++numcheck
0650: 73 75 6d 73 3b 0a 09 7d 0a 09 75 6e 73 69 67 6e sums;..}..unsign
0660: 65 64 20 74 61 62 6c 65 49 6e 64 65 78 28 48 61 ed tableIndex(Ha
0670: 73 68 3a 3a 56 61 6c 75 65 20 68 61 73 68 56 61 sh::Value hashVa
0680: 6c 75 65 29 20 7b 0a 09 09 72 65 74 75 72 6e 20 lue) {...return
0690: 48 61 73 68 3a 3a 6d 6f 64 75 6c 6f 28 68 61 73 Hash::modulo(has
06a0: 68 56 61 6c 75 65 2c 20 68 74 61 62 6c 65 73 69 hValue, htablesi
06b0: 7a 65 29 3b 0a 09 7d 0a 7d 3b 0a 0a 0a 70 6f 73 ze);..}.};...pos
06c0: 20 6d 61 74 63 68 5f 62 75 66 5f 66 6f 72 77 61 match_buf_forwa
06d0: 72 64 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 62 rd(const void *b
06e0: 75 66 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 uf1, const void
06f0: 2a 62 75 66 32 2c 20 70 6f 73 20 6e 75 6d 29 20 *buf2, pos num)
0700: 7b 20 0a 09 70 6f 73 20 69 20 3d 20 30 3b 0a 09 { ..pos i = 0;..
0710: 77 68 69 6c 65 20 28 69 20 3c 20 6e 75 6d 20 26 while (i < num &
0720: 26 20 28 28 63 6f 6e 73 74 20 54 6f 6b 65 6e 2a & ((const Token*
0730: 29 62 75 66 31 29 5b 69 5d 3d 3d 28 28 63 6f 6e )buf1)[i]==((con
0740: 73 74 20 54 6f 6b 65 6e 2a 29 62 75 66 32 29 5b st Token*)buf2)[
0750: 69 5d 29 20 2b 2b 69 3b 0a 09 72 65 74 75 72 6e i]) ++i;..return
0760: 20 69 3b 0a 7d 0a 70 6f 73 20 6d 61 74 63 68 5f i;.}.pos match_
0770: 62 75 66 5f 62 61 63 6b 77 61 72 64 28 63 6f 6e buf_backward(con
0780: 73 74 20 76 6f 69 64 20 2a 62 75 66 31 2c 20 63 st void *buf1, c
0790: 6f 6e 73 74 20 76 6f 69 64 20 2a 62 75 66 32 2c onst void *buf2,
07a0: 20 70 6f 73 20 6e 75 6d 29 20 7b 20 0a 09 70 6f pos num) { ..po
07b0: 73 20 69 20 3d 20 6e 75 6d 3b 0a 09 64 6f 20 2d s i = num;..do -
07c0: 2d 69 3b 0a 09 77 68 69 6c 65 20 28 69 20 3e 3d -i;..while (i >=
07d0: 20 30 20 26 26 20 28 28 63 6f 6e 73 74 20 54 6f 0 && ((const To
07e0: 6b 65 6e 2a 29 62 75 66 31 29 5b 69 5d 20 3d 3d ken*)buf1)[i] ==
07f0: 20 28 28 63 6f 6e 73 74 20 54 6f 6b 65 6e 2a 29 ((const Token*)
0800: 62 75 66 32 29 5b 69 5d 29 3b 0a 09 72 65 74 75 buf2)[i]);..retu
0810: 72 6e 20 6e 75 6d 20 2d 20 69 20 2d 20 31 3b 0a rn num - i - 1;.
0820: 7d 0a 70 6f 73 20 6d 61 74 63 68 5f 66 6f 72 77 }.pos match_forw
0830: 61 72 64 28 42 44 65 6c 74 61 5f 49 6e 73 74 61 ard(BDelta_Insta
0840: 6e 63 65 20 2a 62 2c 20 70 6f 73 20 70 31 2c 20 nce *b, pos p1,
0850: 70 6f 73 20 70 32 29 20 7b 20 0a 20 20 20 20 20 pos p2) { .
0860: 20 20 20 70 6f 73 20 6e 75 6d 20 3d 20 30 2c 20 pos num = 0,
0870: 6d 61 74 63 68 2c 20 6e 75 6d 74 6f 72 65 61 64 match, numtoread
0880: 3b 0a 09 64 6f 20 7b 0a 09 09 6e 75 6d 74 6f 72 ;..do {...numtor
0890: 65 61 64 20 3d 20 73 74 64 3a 3a 6d 69 6e 28 62 ead = std::min(b
08a0: 2d 3e 64 61 74 61 31 5f 73 69 7a 65 20 2d 20 70 ->data1_size - p
08b0: 31 2c 20 62 2d 3e 64 61 74 61 32 5f 73 69 7a 65 1, b->data2_size
08c0: 20 2d 20 70 32 29 3b 0a 09 09 69 66 20 28 6e 75 - p2);...if (nu
08d0: 6d 74 6f 72 65 61 64 20 3e 20 34 30 39 36 29 20 mtoread > 4096)
08e0: 6e 75 6d 74 6f 72 65 61 64 20 3d 20 34 30 39 36 numtoread = 4096
08f0: 3b 0a 09 09 63 6f 6e 73 74 20 54 6f 6b 65 6e 20 ;...const Token
0900: 2a 72 65 61 64 31 20 3d 20 62 2d 3e 72 65 61 64 *read1 = b->read
0910: 31 28 70 31 29 2c 0a 09 09 20 20 20 20 20 20 20 1(p1),...
0920: 20 20 20 20 20 2a 72 65 61 64 32 20 3d 20 62 2d *read2 = b-
0930: 3e 72 65 61 64 32 28 70 32 29 3b 0a 09 09 70 31 >read2(p2);...p1
0940: 20 2b 3d 20 6e 75 6d 74 6f 72 65 61 64 3b 20 70 += numtoread; p
0950: 32 20 2b 3d 20 6e 75 6d 74 6f 72 65 61 64 3b 0a 2 += numtoread;.
0960: 09 09 6d 61 74 63 68 20 3d 20 6d 61 74 63 68 5f ..match = match_
0970: 62 75 66 5f 66 6f 72 77 61 72 64 28 72 65 61 64 buf_forward(read
0980: 31 2c 20 72 65 61 64 32 2c 20 6e 75 6d 74 6f 72 1, read2, numtor
0990: 65 61 64 29 3b 0a 09 09 6e 75 6d 20 2b 3d 20 6d ead);...num += m
09a0: 61 74 63 68 3b 0a 09 7d 20 77 68 69 6c 65 20 28 atch;..} while (
09b0: 6d 61 74 63 68 20 26 26 20 6d 61 74 63 68 20 3d match && match =
09c0: 3d 20 6e 75 6d 74 6f 72 65 61 64 29 3b 0a 09 72 = numtoread);..r
09d0: 65 74 75 72 6e 20 6e 75 6d 3b 0a 7d 0a 0a 70 6f eturn num;.}..po
09e0: 73 20 6d 61 74 63 68 5f 62 61 63 6b 77 61 72 64 s match_backward
09f0: 28 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e 63 65 (BDelta_Instance
0a00: 20 2a 62 2c 20 70 6f 73 20 70 31 2c 20 70 6f 73 *b, pos p1, pos
0a10: 20 70 32 2c 20 70 6f 73 20 62 6c 6f 63 6b 73 69 p2, pos blocksi
0a20: 7a 65 29 20 7b 0a 09 70 6f 73 20 6e 75 6d 20 3d ze) {..pos num =
0a30: 20 30 2c 20 6d 61 74 63 68 2c 20 6e 75 6d 74 6f 0, match, numto
0a40: 72 65 61 64 3b 0a 09 64 6f 20 7b 0a 09 09 6e 75 read;..do {...nu
0a50: 6d 74 6f 72 65 61 64 20 3d 20 73 74 64 3a 3a 6d mtoread = std::m
0a60: 69 6e 28 70 31 2c 20 70 32 29 3b 0a 09 09 69 66 in(p1, p2);...if
0a70: 20 28 6e 75 6d 74 6f 72 65 61 64 20 3e 20 62 6c (numtoread > bl
0a80: 6f 63 6b 73 69 7a 65 29 20 6e 75 6d 74 6f 72 65 ocksize) numtore
0a90: 61 64 20 3d 20 62 6c 6f 63 6b 73 69 7a 65 3b 0a ad = blocksize;.
0aa0: 09 09 69 66 20 28 6e 75 6d 74 6f 72 65 61 64 20 ..if (numtoread
0ab0: 3e 20 34 30 39 36 29 20 6e 75 6d 74 6f 72 65 61 > 4096) numtorea
0ac0: 64 20 3d 20 34 30 39 36 3b 0a 09 09 70 31 20 2d d = 4096;...p1 -
0ad0: 3d 20 6e 75 6d 74 6f 72 65 61 64 3b 20 70 32 20 = numtoread; p2
0ae0: 2d 3d 20 6e 75 6d 74 6f 72 65 61 64 3b 0a 09 09 -= numtoread;...
0af0: 63 6f 6e 73 74 20 54 6f 6b 65 6e 20 2a 72 65 61 const Token *rea
0b00: 64 31 20 3d 20 62 2d 3e 72 65 61 64 31 28 70 31 d1 = b->read1(p1
0b10: 29 2c 0a 09 09 20 20 20 20 20 20 20 20 20 20 20 ),...
0b20: 20 2a 72 65 61 64 32 20 3d 20 62 2d 3e 72 65 61 *read2 = b->rea
0b30: 64 32 28 70 32 29 3b 0a 09 09 6d 61 74 63 68 20 d2(p2);...match
0b40: 3d 20 6d 61 74 63 68 5f 62 75 66 5f 62 61 63 6b = match_buf_back
0b50: 77 61 72 64 28 72 65 61 64 31 2c 20 72 65 61 64 ward(read1, read
0b60: 32 2c 20 6e 75 6d 74 6f 72 65 61 64 29 3b 0a 09 2, numtoread);..
0b70: 09 6e 75 6d 20 2b 3d 20 6d 61 74 63 68 3b 0a 09 .num += match;..
0b80: 7d 20 77 68 69 6c 65 20 28 6d 61 74 63 68 20 26 } while (match &
0b90: 26 20 6d 61 74 63 68 20 3d 3d 20 6e 75 6d 74 6f & match == numto
0ba0: 72 65 61 64 29 3b 0a 09 72 65 74 75 72 6e 20 6e read);..return n
0bb0: 75 6d 3b 0a 7d 0a 0a 2f 2f 20 49 74 65 72 61 74 um;.}..// Iterat
0bc0: 6f 72 20 68 65 6c 70 65 72 20 66 75 6e 63 74 69 or helper functi
0bd0: 6f 6e 0a 74 65 6d 70 6c 61 74 65 20 3c 63 6c 61 on.template <cla
0be0: 73 73 20 54 3e 0a 69 6e 6c 69 6e 65 20 54 20 70 ss T>.inline T p
0bf0: 72 69 6f 72 28 54 20 69 29 20 7b 72 65 74 75 72 rior(T i) {retur
0c00: 6e 20 2d 2d 69 3b 7d 0a 74 65 6d 70 6c 61 74 65 n --i;}.template
0c10: 20 3c 63 6c 61 73 73 20 54 3e 0a 69 6e 6c 69 6e <class T>.inlin
0c20: 65 20 54 20 6e 65 78 74 69 28 54 20 69 29 20 7b e T nexti(T i) {
0c30: 72 65 74 75 72 6e 20 2b 2b 69 3b 7d 0a 0a 0a 73 return ++i;}...s
0c40: 74 72 75 63 74 20 55 6e 75 73 65 64 52 61 6e 67 truct UnusedRang
0c50: 65 20 7b 0a 09 70 6f 73 20 70 2c 20 6e 75 6d 3b e {..pos p, num;
0c60: 0a 09 73 74 64 3a 3a 6c 69 73 74 3c 4d 61 74 63 ..std::list<Matc
0c70: 68 3e 3a 3a 69 74 65 72 61 74 6f 72 20 6d 6c 2c h>::iterator ml,
0c80: 20 6d 72 3b 0a 09 55 6e 75 73 65 64 52 61 6e 67 mr;..UnusedRang
0c90: 65 28 29 20 7b 7d 0a 09 55 6e 75 73 65 64 52 61 e() {}..UnusedRa
0ca0: 6e 67 65 28 70 6f 73 20 70 2c 20 70 6f 73 20 6e nge(pos p, pos n
0cb0: 75 6d 2c 20 73 74 64 3a 3a 6c 69 73 74 3c 4d 61 um, std::list<Ma
0cc0: 74 63 68 3e 3a 3a 69 74 65 72 61 74 6f 72 20 6d tch>::iterator m
0cd0: 6c 2c 20 73 74 64 3a 3a 6c 69 73 74 3c 4d 61 74 l, std::list<Mat
0ce0: 63 68 3e 3a 3a 69 74 65 72 61 74 6f 72 20 6d 72 ch>::iterator mr
0cf0: 29 20 7b 0a 09 09 74 68 69 73 2d 3e 70 20 3d 20 ) {...this->p =
0d00: 70 3b 20 74 68 69 73 2d 3e 6e 75 6d 20 3d 20 6e p; this->num = n
0d10: 75 6d 3b 20 74 68 69 73 2d 3e 6d 6c 20 3d 20 6d um; this->ml = m
0d20: 6c 3b 20 74 68 69 73 2d 3e 6d 72 20 3d 20 6d 72 l; this->mr = mr
0d30: 3b 0a 09 7d 0a 7d 3b 0a 0a 2f 2f 20 53 6f 72 74 ;..}.};..// Sort
0d40: 20 66 69 72 73 74 20 62 79 20 6c 6f 63 61 74 69 first by locati
0d50: 6f 6e 2c 20 73 65 63 6f 6e 64 20 62 79 20 6d 61 on, second by ma
0d60: 74 63 68 20 6c 65 6e 67 74 68 20 28 6c 61 72 67 tch length (larg
0d70: 65 72 20 6d 61 74 63 68 65 73 20 66 69 72 73 74 er matches first
0d80: 29 0a 62 6f 6f 6c 20 63 6f 6d 70 61 72 65 70 28 ).bool comparep(
0d90: 55 6e 75 73 65 64 52 61 6e 67 65 20 72 31 2c 20 UnusedRange r1,
0da0: 55 6e 75 73 65 64 52 61 6e 67 65 20 72 32 29 20 UnusedRange r2)
0db0: 7b 0a 09 69 66 20 28 72 31 2e 70 20 21 3d 20 72 {..if (r1.p != r
0dc0: 32 2e 70 29 0a 09 09 72 65 74 75 72 6e 20 72 31 2.p)...return r1
0dd0: 2e 70 20 3c 20 72 32 2e 70 3b 0a 09 72 65 74 75 .p < r2.p;..retu
0de0: 72 6e 20 72 31 2e 6e 75 6d 20 3e 20 72 32 2e 6e rn r1.num > r2.n
0df0: 75 6d 3b 0a 7d 0a 62 6f 6f 6c 20 63 6f 6d 70 61 um;.}.bool compa
0e00: 72 65 6d 72 70 32 28 55 6e 75 73 65 64 52 61 6e remrp2(UnusedRan
0e10: 67 65 20 72 31 2c 20 55 6e 75 73 65 64 52 61 6e ge r1, UnusedRan
0e20: 67 65 20 72 32 29 20 7b 0a 09 69 66 20 28 72 31 ge r2) {..if (r1
0e30: 2e 6d 72 2d 3e 70 32 20 21 3d 20 72 32 2e 6d 72 .mr->p2 != r2.mr
0e40: 2d 3e 70 32 29 0a 09 09 72 65 74 75 72 6e 20 72 ->p2)...return r
0e50: 31 2e 6d 72 2d 3e 70 32 20 3c 20 72 32 2e 6d 72 1.mr->p2 < r2.mr
0e60: 2d 3e 70 32 3b 0a 09 72 65 74 75 72 6e 20 72 31 ->p2;..return r1
0e70: 2e 6d 72 2d 3e 6e 75 6d 20 3e 20 72 32 2e 6d 72 .mr->num > r2.mr
0e80: 2d 3e 6e 75 6d 3b 0a 7d 0a 62 6f 6f 6c 20 63 6f ->num;.}.bool co
0e90: 6d 70 61 72 65 4d 61 74 63 68 50 32 28 4d 61 74 mpareMatchP2(Mat
0ea0: 63 68 20 72 31 2c 20 4d 61 74 63 68 20 72 32 29 ch r1, Match r2)
0eb0: 20 7b 0a 09 69 66 20 28 72 31 2e 70 32 20 21 3d {..if (r1.p2 !=
0ec0: 20 72 32 2e 70 32 29 0a 09 09 72 65 74 75 72 6e r2.p2)...return
0ed0: 20 72 31 2e 70 32 20 3c 20 72 32 2e 70 32 3b 0a r1.p2 < r2.p2;.
0ee0: 09 72 65 74 75 72 6e 20 72 31 2e 6e 75 6d 20 3e .return r1.num >
0ef0: 20 72 32 2e 6e 75 6d 3b 0a 7d 0a 0a 76 6f 69 64 r2.num;.}..void
0f00: 20 61 64 64 4d 61 74 63 68 28 42 44 65 6c 74 61 addMatch(BDelta
0f10: 5f 49 6e 73 74 61 6e 63 65 20 2a 62 2c 20 70 6f _Instance *b, po
0f20: 73 20 70 31 2c 20 70 6f 73 20 70 32 2c 20 70 6f s p1, pos p2, po
0f30: 73 20 6e 75 6d 2c 20 73 74 64 3a 3a 6c 69 73 74 s num, std::list
0f40: 3c 4d 61 74 63 68 3e 3a 3a 69 74 65 72 61 74 6f <Match>::iterato
0f50: 72 20 70 6c 61 63 65 29 20 7b 0a 09 4d 61 74 63 r place) {..Matc
0f60: 68 20 6e 65 77 4d 61 74 63 68 20 3d 20 4d 61 74 h newMatch = Mat
0f70: 63 68 28 70 31 2c 20 70 32 2c 20 6e 75 6d 29 3b ch(p1, p2, num);
0f80: 0a 09 77 68 69 6c 65 20 28 70 6c 61 63 65 20 21 ..while (place !
0f90: 3d 20 62 2d 3e 6d 61 74 63 68 65 73 2e 62 65 67 = b->matches.beg
0fa0: 69 6e 28 29 20 26 26 20 21 20 63 6f 6d 70 61 72 in() && ! compar
0fb0: 65 4d 61 74 63 68 50 32 28 2a 70 6c 61 63 65 2c eMatchP2(*place,
0fc0: 20 6e 65 77 4d 61 74 63 68 29 29 0a 09 09 2d 2d newMatch))...--
0fd0: 70 6c 61 63 65 3b 0a 09 77 68 69 6c 65 20 28 70 place;..while (p
0fe0: 6c 61 63 65 20 21 3d 20 62 2d 3e 6d 61 74 63 68 lace != b->match
0ff0: 65 73 2e 65 6e 64 28 29 20 26 26 20 63 6f 6d 70 es.end() && comp
1000: 61 72 65 4d 61 74 63 68 50 32 28 2a 70 6c 61 63 areMatchP2(*plac
1010: 65 2c 20 6e 65 77 4d 61 74 63 68 29 29 0a 09 09 e, newMatch))...
1020: 2b 2b 70 6c 61 63 65 3b 0a 09 62 2d 3e 6d 61 74 ++place;..b->mat
1030: 63 68 65 73 2e 69 6e 73 65 72 74 28 70 6c 61 63 ches.insert(plac
1040: 65 2c 20 6e 65 77 4d 61 74 63 68 29 3b 0a 7d 0a e, newMatch);.}.
1050: 0a 74 65 6d 70 6c 61 74 65 3c 63 6c 61 73 73 20 .template<class
1060: 54 3e 0a 54 20 61 62 73 6f 6c 75 74 65 44 69 66 T>.T absoluteDif
1070: 66 65 72 65 6e 63 65 28 54 20 61 2c 20 54 20 62 ference(T a, T b
1080: 29 20 7b 0a 09 72 65 74 75 72 6e 20 73 74 64 3a ) {..return std:
1090: 3a 6d 61 78 28 61 2c 20 62 29 20 2d 20 73 74 64 :max(a, b) - std
10a0: 3a 3a 6d 69 6e 28 61 2c 20 62 29 3b 0a 7d 0a 0a ::min(a, b);.}..
10b0: 76 6f 69 64 20 66 69 6e 64 4d 61 74 63 68 65 73 void findMatches
10c0: 28 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e 63 65 (BDelta_Instance
10d0: 20 2a 62 2c 20 43 68 65 63 6b 73 75 6d 73 5f 49 *b, Checksums_I
10e0: 6e 73 74 61 6e 63 65 20 2a 68 2c 20 75 6e 73 69 nstance *h, unsi
10f0: 67 6e 65 64 20 6d 69 6e 4d 61 74 63 68 53 69 7a gned minMatchSiz
1100: 65 2c 20 70 6f 73 20 73 74 61 72 74 2c 20 70 6f e, pos start, po
1110: 73 20 65 6e 64 2c 20 70 6f 73 20 70 6c 61 63 65 s end, pos place
1120: 2c 20 73 74 64 3a 3a 6c 69 73 74 3c 4d 61 74 63 , std::list<Matc
1130: 68 3e 3a 3a 69 74 65 72 61 74 6f 72 20 69 74 65 h>::iterator ite
1140: 72 50 6c 61 63 65 29 20 7b 0a 09 63 6f 6e 73 74 rPlace) {..const
1150: 20 75 6e 73 69 67 6e 65 64 20 62 6c 6f 63 6b 73 unsigned blocks
1160: 69 7a 65 20 3d 20 68 2d 3e 62 6c 6f 63 6b 73 69 ize = h->blocksi
1170: 7a 65 3b 0a 0a 09 70 6f 73 20 62 65 73 74 31 2c ze;...pos best1,
1180: 20 62 65 73 74 32 2c 20 62 65 73 74 6e 75 6d 20 best2, bestnum
1190: 3d 20 30 3b 0a 09 70 6f 73 20 70 72 6f 63 65 73 = 0;..pos proces
11a0: 73 4d 61 74 63 68 65 73 50 6f 73 3b 0a 09 63 6f sMatchesPos;..co
11b0: 6e 73 74 20 54 6f 6b 65 6e 20 2a 69 6e 62 75 66 nst Token *inbuf
11c0: 20 3d 20 62 2d 3e 72 65 61 64 32 28 73 74 61 72 = b->read2(star
11d0: 74 29 2c 0a 09 20 20 20 20 20 20 20 20 20 20 20 t),..
11e0: 20 2a 6f 75 74 62 75 66 3b 0a 09 48 61 73 68 20 *outbuf;..Hash
11f0: 68 61 73 68 20 3d 20 48 61 73 68 28 69 6e 62 75 hash = Hash(inbu
1200: 66 2c 20 62 6c 6f 63 6b 73 69 7a 65 29 3b 0a 09 f, blocksize);..
1210: 70 6f 73 20 62 75 66 5f 6c 6f 63 20 3d 20 62 6c pos buf_loc = bl
1220: 6f 63 6b 73 69 7a 65 3b 0a 09 66 6f 72 20 28 70 ocksize;..for (p
1230: 6f 73 20 6a 20 3d 20 73 74 61 72 74 20 2b 20 62 os j = start + b
1240: 6c 6f 63 6b 73 69 7a 65 3b 20 3b 20 2b 2b 6a 29 locksize; ; ++j)
1250: 20 7b 0a 09 09 75 6e 73 69 67 6e 65 64 20 74 68 {...unsigned th
1260: 69 73 54 61 62 6c 65 49 6e 64 65 78 20 3d 20 68 isTableIndex = h
1270: 2d 3e 74 61 62 6c 65 49 6e 64 65 78 28 68 61 73 ->tableIndex(has
1280: 68 2e 67 65 74 56 61 6c 75 65 28 29 29 3b 0a 09 h.getValue());..
1290: 09 63 68 65 63 6b 73 75 6d 5f 65 6e 74 72 79 20 .checksum_entry
12a0: 2a 63 20 3d 20 68 2d 3e 68 74 61 62 6c 65 5b 74 *c = h->htable[t
12b0: 68 69 73 54 61 62 6c 65 49 6e 64 65 78 5d 3b 0a hisTableIndex];.
12c0: 09 09 69 66 20 28 63 29 20 7b 0a 09 09 09 64 6f ..if (c) {....do
12d0: 20 7b 0a 09 09 09 09 69 66 20 28 63 2d 3e 63 6b {.....if (c->ck
12e0: 73 75 6d 20 3d 3d 20 68 61 73 68 2e 67 65 74 56 sum == hash.getV
12f0: 61 6c 75 65 28 29 29 20 7b 0a 09 09 09 09 09 70 alue()) {......p
1300: 6f 73 20 70 31 20 3d 20 63 2d 3e 6c 6f 63 2c 20 os p1 = c->loc,
1310: 70 32 20 3d 20 6a 20 2d 20 62 6c 6f 63 6b 73 69 p2 = j - blocksi
1320: 7a 65 3b 0a 09 09 09 09 09 70 6f 73 20 66 6e 75 ze;......pos fnu
1330: 6d 20 3d 20 6d 61 74 63 68 5f 66 6f 72 77 61 72 m = match_forwar
1340: 64 28 62 2c 20 70 31 2c 20 70 32 29 3b 0a 09 09 d(b, p1, p2);...
1350: 09 09 09 69 66 20 28 66 6e 75 6d 20 3e 3d 20 62 ...if (fnum >= b
1360: 6c 6f 63 6b 73 69 7a 65 29 20 7b 0a 09 09 09 09 locksize) {.....
1370: 09 09 70 6f 73 20 62 6e 75 6d 20 3d 20 6d 61 74 ..pos bnum = mat
1380: 63 68 5f 62 61 63 6b 77 61 72 64 28 62 2c 20 70 ch_backward(b, p
1390: 31 2c 20 70 32 2c 20 62 6c 6f 63 6b 73 69 7a 65 1, p2, blocksize
13a0: 29 3b 0a 09 09 09 09 09 09 70 6f 73 20 6e 75 6d );.......pos num
13b0: 20 3d 20 66 6e 75 6d 20 2b 20 62 6e 75 6d 3b 0a = fnum + bnum;.
13c0: 09 09 09 09 09 09 69 66 20 28 6e 75 6d 20 3e 3d ......if (num >=
13d0: 20 6d 69 6e 4d 61 74 63 68 53 69 7a 65 29 20 7b minMatchSize) {
13e0: 0a 09 09 09 09 09 09 09 70 31 20 2d 3d 20 62 6e ........p1 -= bn
13f0: 75 6d 3b 20 70 32 20 2d 3d 20 62 6e 75 6d 3b 0a um; p2 -= bnum;.
1400: 09 09 09 09 09 09 09 62 6f 6f 6c 20 66 6f 75 6e .......bool foun
1410: 64 42 65 74 74 65 72 3b 0a 09 09 09 09 09 09 09 dBetter;........
1420: 69 66 20 28 62 65 73 74 6e 75 6d 29 20 7b 0a 09 if (bestnum) {..
1430: 09 09 09 09 09 09 09 64 6f 75 62 6c 65 20 6f 6c .......double ol
1440: 64 56 61 6c 75 65 20 3d 20 64 6f 75 62 6c 65 28 dValue = double(
1450: 62 65 73 74 6e 75 6d 29 20 2f 20 28 61 62 73 6f bestnum) / (abso
1460: 6c 75 74 65 44 69 66 66 65 72 65 6e 63 65 28 70 luteDifference(p
1470: 6c 61 63 65 2c 20 62 65 73 74 31 29 20 2b 20 62 lace, best1) + b
1480: 6c 6f 63 6b 73 69 7a 65 20 2a 20 32 29 2c 0a 09 locksize * 2),..
1490: 09 09 09 09 09 09 09 09 20 20 20 6e 65 77 56 61 ........ newVa
14a0: 6c 75 65 20 3d 20 64 6f 75 62 6c 65 28 6e 75 6d lue = double(num
14b0: 29 20 2f 20 28 61 62 73 6f 6c 75 74 65 44 69 66 ) / (absoluteDif
14c0: 66 65 72 65 6e 63 65 28 70 6c 61 63 65 2c 20 70 ference(place, p
14d0: 31 29 20 2b 20 62 6c 6f 63 6b 73 69 7a 65 20 2a 1) + blocksize *
14e0: 20 32 29 3b 0a 09 09 09 09 09 09 09 09 66 6f 75 2);.........fou
14f0: 6e 64 42 65 74 74 65 72 20 3d 20 6e 65 77 56 61 ndBetter = newVa
1500: 6c 75 65 20 3e 20 6f 6c 64 56 61 6c 75 65 3b 0a lue > oldValue;.
1510: 09 09 09 09 09 09 09 7d 20 65 6c 73 65 20 7b 0a .......} else {.
1520: 09 09 09 09 09 09 09 09 66 6f 75 6e 64 42 65 74 ........foundBet
1530: 74 65 72 20 3d 20 74 72 75 65 3b 0a 09 09 09 09 ter = true;.....
1540: 09 09 09 09 70 72 6f 63 65 73 73 4d 61 74 63 68 ....processMatch
1550: 65 73 50 6f 73 20 3d 20 73 74 64 3a 3a 6d 69 6e esPos = std::min
1560: 28 6a 20 2b 20 62 6c 6f 63 6b 73 69 7a 65 20 2d (j + blocksize -
1570: 20 31 2c 20 65 6e 64 29 3b 0a 09 09 09 09 09 09 1, end);.......
1580: 09 7d 0a 09 09 09 09 09 09 09 69 66 20 28 66 6f .}........if (fo
1590: 75 6e 64 42 65 74 74 65 72 29 20 7b 0a 09 09 09 undBetter) {....
15a0: 09 09 09 09 09 62 65 73 74 31 20 3d 20 70 31 3b .....best1 = p1;
15b0: 0a 09 09 09 09 09 09 09 09 62 65 73 74 32 20 3d .........best2 =
15c0: 20 70 32 3b 0a 09 09 09 09 09 09 09 09 62 65 73 p2;.........bes
15d0: 74 6e 75 6d 20 3d 20 6e 75 6d 3b 0a 09 09 09 09 tnum = num;.....
15e0: 09 09 09 7d 0a 0a 09 09 09 09 09 09 7d 0a 09 09 ...}........}...
15f0: 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 09 2b ...}.....}.....+
1600: 2b 63 3b 0a 09 09 09 7d 20 77 68 69 6c 65 20 28 +c;....} while (
1610: 68 2d 3e 74 61 62 6c 65 49 6e 64 65 78 28 63 2d h->tableIndex(c-
1620: 3e 63 6b 73 75 6d 29 20 3d 3d 20 74 68 69 73 54 >cksum) == thisT
1630: 61 62 6c 65 49 6e 64 65 78 29 3b 0a 09 09 7d 0a ableIndex);...}.
1640: 0a 09 09 69 66 20 28 62 65 73 74 6e 75 6d 20 26 ...if (bestnum &
1650: 26 20 6a 20 3e 3d 20 70 72 6f 63 65 73 73 4d 61 & j >= processMa
1660: 74 63 68 65 73 50 6f 73 29 20 7b 0a 09 09 09 61 tchesPos) {....a
1670: 64 64 4d 61 74 63 68 28 62 2c 20 62 65 73 74 31 ddMatch(b, best1
1680: 2c 20 62 65 73 74 32 2c 20 62 65 73 74 6e 75 6d , best2, bestnum
1690: 2c 20 69 74 65 72 50 6c 61 63 65 29 3b 0a 09 09 , iterPlace);...
16a0: 09 70 6c 61 63 65 20 3d 20 62 65 73 74 31 20 2b .place = best1 +
16b0: 20 62 65 73 74 6e 75 6d 3b 0a 09 09 09 70 6f 73 bestnum;....pos
16c0: 20 6d 61 74 63 68 45 6e 64 20 3d 20 62 65 73 74 matchEnd = best
16d0: 32 20 2b 20 62 65 73 74 6e 75 6d 3b 0a 09 09 09 2 + bestnum;....
16e0: 69 66 20 28 6d 61 74 63 68 45 6e 64 20 3e 20 6a if (matchEnd > j
16f0: 29 20 7b 0a 09 09 09 09 69 66 20 28 6d 61 74 63 ) {.....if (matc
1700: 68 45 6e 64 20 3e 3d 20 65 6e 64 29 0a 09 09 09 hEnd >= end)....
1710: 09 09 6a 20 3d 20 65 6e 64 3b 0a 09 09 09 09 65 ..j = end;.....e
1720: 6c 73 65 20 7b 0a 09 09 09 09 09 2f 2f 20 46 61 lse {......// Fa
1730: 73 74 20 66 6f 72 77 61 72 64 20 6f 76 65 72 20 st forward over
1740: 6d 61 74 63 68 65 64 20 61 72 65 61 2e 0a 09 09 matched area....
1750: 09 09 09 6a 20 3d 20 6d 61 74 63 68 45 6e 64 20 ...j = matchEnd
1760: 2d 20 62 6c 6f 63 6b 73 69 7a 65 3b 0a 09 09 09 - blocksize;....
1770: 09 09 69 6e 62 75 66 20 3d 20 62 2d 3e 72 65 61 ..inbuf = b->rea
1780: 64 32 28 6a 29 3b 0a 09 09 09 09 09 68 61 73 68 d2(j);......hash
1790: 20 3d 20 48 61 73 68 28 69 6e 62 75 66 2c 20 62 = Hash(inbuf, b
17a0: 6c 6f 63 6b 73 69 7a 65 29 3b 0a 09 09 09 09 09 locksize);......
17b0: 62 75 66 5f 6c 6f 63 20 3d 20 62 6c 6f 63 6b 73 buf_loc = blocks
17c0: 69 7a 65 3b 0a 09 09 09 09 09 6a 20 2b 3d 20 62 ize;......j += b
17d0: 6c 6f 63 6b 73 69 7a 65 3b 0a 09 09 09 09 7d 0a locksize;.....}.
17e0: 09 09 09 7d 0a 09 09 09 62 65 73 74 6e 75 6d 20 ...}....bestnum
17f0: 3d 20 30 3b 0a 09 09 7d 0a 0a 09 09 69 66 20 28 = 0;...}....if (
1800: 62 75 66 5f 6c 6f 63 20 3d 3d 20 62 6c 6f 63 6b buf_loc == block
1810: 73 69 7a 65 29 20 7b 0a 09 09 09 62 75 66 5f 6c size) {....buf_l
1820: 6f 63 20 3d 20 30 3b 0a 09 09 09 73 74 64 3a 3a oc = 0;....std::
1830: 73 77 61 70 28 69 6e 62 75 66 2c 20 6f 75 74 62 swap(inbuf, outb
1840: 75 66 29 3b 0a 09 09 09 69 6e 62 75 66 20 3d 20 uf);....inbuf =
1850: 62 2d 3e 72 65 61 64 32 28 6a 29 3b 0a 09 09 7d b->read2(j);...}
1860: 0a 0a 09 09 69 66 20 28 6a 20 3e 3d 20 65 6e 64 ....if (j >= end
1870: 29 0a 09 09 09 62 72 65 61 6b 3b 0a 0a 09 09 68 )....break;....h
1880: 61 73 68 2e 61 64 76 61 6e 63 65 28 6f 75 74 62 ash.advance(outb
1890: 75 66 5b 62 75 66 5f 6c 6f 63 5d 2c 20 69 6e 62 uf[buf_loc], inb
18a0: 75 66 5b 62 75 66 5f 6c 6f 63 5d 29 3b 0a 09 09 uf[buf_loc]);...
18b0: 2b 2b 62 75 66 5f 6c 6f 63 3b 0a 09 7d 0a 7d 0a ++buf_loc;..}.}.
18c0: 0a 73 74 72 75 63 74 20 43 68 65 63 6b 73 75 6d .struct Checksum
18d0: 73 5f 43 6f 6d 70 61 72 65 20 7b 0a 09 43 68 65 s_Compare {..Che
18e0: 63 6b 73 75 6d 73 5f 49 6e 73 74 61 6e 63 65 20 cksums_Instance
18f0: 26 63 69 3b 0a 09 43 68 65 63 6b 73 75 6d 73 5f &ci;..Checksums_
1900: 43 6f 6d 70 61 72 65 28 43 68 65 63 6b 73 75 6d Compare(Checksum
1910: 73 5f 49 6e 73 74 61 6e 63 65 20 26 68 29 20 3a s_Instance &h) :
1920: 20 63 69 28 68 29 20 7b 7d 0a 09 62 6f 6f 6c 20 ci(h) {}..bool
1930: 6f 70 65 72 61 74 6f 72 28 29 20 28 63 68 65 63 operator() (chec
1940: 6b 73 75 6d 5f 65 6e 74 72 79 20 63 31 2c 20 63 ksum_entry c1, c
1950: 68 65 63 6b 73 75 6d 5f 65 6e 74 72 79 20 63 32 hecksum_entry c2
1960: 29 20 7b 0a 09 09 75 6e 73 69 67 6e 65 64 20 74 ) {...unsigned t
1970: 69 31 20 3d 20 63 69 2e 74 61 62 6c 65 49 6e 64 i1 = ci.tableInd
1980: 65 78 28 63 31 2e 63 6b 73 75 6d 29 2c 20 74 69 ex(c1.cksum), ti
1990: 32 20 3d 20 63 69 2e 74 61 62 6c 65 49 6e 64 65 2 = ci.tableInde
19a0: 78 28 63 32 2e 63 6b 73 75 6d 29 3b 0a 09 09 69 x(c2.cksum);...i
19b0: 66 20 28 74 69 31 20 3d 3d 20 74 69 32 29 0a 09 f (ti1 == ti2)..
19c0: 09 09 69 66 20 28 63 31 2e 63 6b 73 75 6d 20 3d ..if (c1.cksum =
19d0: 3d 20 63 32 2e 63 6b 73 75 6d 29 0a 09 09 09 09 = c2.cksum).....
19e0: 72 65 74 75 72 6e 20 63 31 2e 6c 6f 63 20 3c 20 return c1.loc <
19f0: 63 32 2e 6c 6f 63 3b 0a 09 09 09 65 6c 73 65 0a c2.loc;....else.
1a00: 09 09 09 09 72 65 74 75 72 6e 20 63 31 2e 63 6b ....return c1.ck
1a10: 73 75 6d 20 3c 20 63 32 2e 63 6b 73 75 6d 3b 0a sum < c2.cksum;.
1a20: 09 09 65 6c 73 65 0a 09 09 09 72 65 74 75 72 6e ..else....return
1a30: 20 74 69 31 20 3c 20 74 69 32 3b 0a 09 7d 0a 7d ti1 < ti2;..}.}
1a40: 3b 0a 0a 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e ;..BDelta_Instan
1a50: 63 65 20 2a 62 64 65 6c 74 61 5f 69 6e 69 74 5f ce *bdelta_init_
1a60: 61 6c 67 28 76 6f 69 64 20 2a 68 61 6e 64 6c 65 alg(void *handle
1a70: 31 2c 20 70 6f 73 20 64 61 74 61 31 5f 73 69 7a 1, pos data1_siz
1a80: 65 2c 0a 09 09 09 09 20 76 6f 69 64 20 2a 68 61 e,..... void *ha
1a90: 6e 64 6c 65 32 2c 20 70 6f 73 20 64 61 74 61 32 ndle2, pos data2
1aa0: 5f 73 69 7a 65 29 20 7b 0a 09 42 44 65 6c 74 61 _size) {..BDelta
1ab0: 5f 49 6e 73 74 61 6e 63 65 20 2a 62 20 3d 20 6e _Instance *b = n
1ac0: 65 77 20 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e ew BDelta_Instan
1ad0: 63 65 3b 0a 09 69 66 20 28 21 62 29 20 72 65 74 ce;..if (!b) ret
1ae0: 75 72 6e 20 30 3b 0a 09 62 2d 3e 64 61 74 61 31 urn 0;..b->data1
1af0: 5f 73 69 7a 65 20 3d 20 64 61 74 61 31 5f 73 69 _size = data1_si
1b00: 7a 65 3b 0a 09 62 2d 3e 64 61 74 61 32 5f 73 69 ze;..b->data2_si
1b10: 7a 65 20 3d 20 64 61 74 61 32 5f 73 69 7a 65 3b ze = data2_size;
1b20: 0a 09 62 2d 3e 68 61 6e 64 6c 65 31 20 3d 20 68 ..b->handle1 = h
1b30: 61 6e 64 6c 65 31 3b 0a 09 62 2d 3e 68 61 6e 64 andle1;..b->hand
1b40: 6c 65 32 20 3d 20 68 61 6e 64 6c 65 32 3b 0a 09 le2 = handle2;..
1b50: 62 2d 3e 61 63 63 65 73 73 5f 69 6e 74 20 3d 20 b->access_int =
1b60: 2d 31 3b 0a 09 72 65 74 75 72 6e 20 62 3b 0a 7d -1;..return b;.}
1b70: 0a 0a 76 6f 69 64 20 62 64 65 6c 74 61 5f 64 6f ..void bdelta_do
1b80: 6e 65 5f 61 6c 67 28 42 44 65 6c 74 61 5f 49 6e ne_alg(BDelta_In
1b90: 73 74 61 6e 63 65 20 2a 62 29 20 7b 0a 09 62 2d stance *b) {..b-
1ba0: 3e 6d 61 74 63 68 65 73 2e 63 6c 65 61 72 28 29 >matches.clear()
1bb0: 3b 0a 09 64 65 6c 65 74 65 20 62 3b 0a 7d 0a 0a ;..delete b;.}..
1bc0: 0a 2f 2f 20 41 64 61 70 74 65 64 20 66 72 6f 6d .// Adapted from
1bd0: 20 68 74 74 70 3a 2f 2f 67 72 61 70 68 69 63 73 http://graphics
1be0: 2e 73 74 61 6e 66 6f 72 64 2e 65 64 75 2f 7e 73 .stanford.edu/~s
1bf0: 65 61 6e 64 65 72 2f 62 69 74 68 61 63 6b 73 2e eander/bithacks.
1c00: 68 74 6d 6c 23 52 6f 75 6e 64 55 70 50 6f 77 65 html#RoundUpPowe
1c10: 72 4f 66 32 0a 75 6e 73 69 67 6e 65 64 20 72 6f rOf2.unsigned ro
1c20: 75 6e 64 55 70 50 6f 77 65 72 4f 66 32 28 75 6e undUpPowerOf2(un
1c30: 73 69 67 6e 65 64 20 76 29 20 7b 0a 09 2d 2d 76 signed v) {..--v
1c40: 3b 0a 09 66 6f 72 20 28 69 6e 74 20 69 20 3d 20 ;..for (int i =
1c50: 31 3b 20 69 20 3c 3d 20 31 36 3b 20 69 20 2a 3d 1; i <= 16; i *=
1c60: 20 32 29 0a 09 09 76 20 7c 3d 20 76 20 3e 3e 20 2)...v |= v >>
1c70: 69 3b 0a 09 72 65 74 75 72 6e 20 76 20 2b 20 31 i;..return v + 1
1c80: 3b 0a 7d 0a 0a 76 6f 69 64 20 62 64 65 6c 74 61 ;.}..void bdelta
1c90: 5f 70 61 73 73 5f 32 28 42 44 65 6c 74 61 5f 49 _pass_2(BDelta_I
1ca0: 6e 73 74 61 6e 63 65 20 2a 62 2c 20 75 6e 73 69 nstance *b, unsi
1cb0: 67 6e 65 64 20 62 6c 6f 63 6b 73 69 7a 65 2c 20 gned blocksize,
1cc0: 75 6e 73 69 67 6e 65 64 20 6d 69 6e 4d 61 74 63 unsigned minMatc
1cd0: 68 53 69 7a 65 2c 20 55 6e 75 73 65 64 52 61 6e hSize, UnusedRan
1ce0: 67 65 20 2a 75 6e 75 73 65 64 2c 20 75 6e 73 69 ge *unused, unsi
1cf0: 67 6e 65 64 20 6e 75 6d 75 6e 75 73 65 64 2c 20 gned numunused,
1d00: 55 6e 75 73 65 64 52 61 6e 67 65 20 2a 75 6e 75 UnusedRange *unu
1d10: 73 65 64 32 2c 20 75 6e 73 69 67 6e 65 64 20 6e sed2, unsigned n
1d20: 75 6d 75 6e 75 73 65 64 32 29 20 7b 0a 09 43 68 umunused2) {..Ch
1d30: 65 63 6b 73 75 6d 73 5f 49 6e 73 74 61 6e 63 65 ecksums_Instance
1d40: 20 68 28 62 6c 6f 63 6b 73 69 7a 65 29 3b 0a 09 h(blocksize);..
1d50: 62 2d 3e 61 63 63 65 73 73 5f 69 6e 74 20 3d 20 b->access_int =
1d60: 2d 31 3b 0a 0a 09 75 6e 73 69 67 6e 65 64 20 6e -1;...unsigned n
1d70: 75 6d 62 6c 6f 63 6b 73 20 3d 20 30 3b 0a 09 66 umblocks = 0;..f
1d80: 6f 72 20 28 75 6e 73 69 67 6e 65 64 20 69 20 3d or (unsigned i =
1d90: 20 30 3b 20 69 20 3c 20 6e 75 6d 75 6e 75 73 65 0; i < numunuse
1da0: 64 3b 20 2b 2b 69 29 20 7b 0a 09 09 6e 75 6d 62 d; ++i) {...numb
1db0: 6c 6f 63 6b 73 20 2b 3d 20 75 6e 75 73 65 64 5b locks += unused[
1dc0: 69 5d 2e 6e 75 6d 20 2f 20 62 6c 6f 63 6b 73 69 i].num / blocksi
1dd0: 7a 65 3b 0a 09 7d 0a 0a 09 2f 2f 20 6e 75 6d 62 ze;..}...// numb
1de0: 6c 6f 63 6b 73 20 3d 20 73 69 7a 65 20 2f 20 62 locks = size / b
1df0: 6c 6f 63 6b 73 69 7a 65 3b 0a 09 68 2e 68 74 61 locksize;..h.hta
1e00: 62 6c 65 73 69 7a 65 20 3d 20 73 74 64 3a 3a 6d blesize = std::m
1e10: 61 78 28 28 75 6e 73 69 67 6e 65 64 29 32 2c 20 ax((unsigned)2,
1e20: 72 6f 75 6e 64 55 70 50 6f 77 65 72 4f 66 32 28 roundUpPowerOf2(
1e30: 6e 75 6d 62 6c 6f 63 6b 73 29 29 3b 0a 09 68 2e numblocks));..h.
1e40: 68 74 61 62 6c 65 20 3d 20 6e 65 77 20 63 68 65 htable = new che
1e50: 63 6b 73 75 6d 5f 65 6e 74 72 79 2a 5b 68 2e 68 cksum_entry*[h.h
1e60: 74 61 62 6c 65 73 69 7a 65 5d 3b 0a 09 69 66 20 tablesize];..if
1e70: 28 21 68 2e 68 74 61 62 6c 65 29 20 7b 62 2d 3e (!h.htable) {b->
1e80: 65 72 72 6f 72 63 6f 64 65 20 3d 20 42 44 45 4c errorcode = BDEL
1e90: 54 41 5f 4d 45 4d 5f 45 52 52 4f 52 3b 20 72 65 TA_MEM_ERROR; re
1ea0: 74 75 72 6e 3b 7d 0a 09 68 2e 63 68 65 63 6b 73 turn;}..h.checks
1eb0: 75 6d 73 20 3d 20 6e 65 77 20 63 68 65 63 6b 73 ums = new checks
1ec0: 75 6d 5f 65 6e 74 72 79 5b 6e 75 6d 62 6c 6f 63 um_entry[numbloc
1ed0: 6b 73 20 2b 20 32 5d 3b 0a 09 69 66 20 28 21 68 ks + 2];..if (!h
1ee0: 2e 63 68 65 63 6b 73 75 6d 73 29 20 7b 62 2d 3e .checksums) {b->
1ef0: 65 72 72 6f 72 63 6f 64 65 20 3d 20 42 44 45 4c errorcode = BDEL
1f00: 54 41 5f 4d 45 4d 5f 45 52 52 4f 52 3b 20 72 65 TA_MEM_ERROR; re
1f10: 74 75 72 6e 3b 7d 0a 0a 09 68 2e 6e 75 6d 63 68 turn;}...h.numch
1f20: 65 63 6b 73 75 6d 73 20 3d 20 30 3b 0a 09 2f 2f ecksums = 0;..//
1f30: 20 75 6e 73 69 67 6e 65 64 20 6e 75 6d 63 68 65 unsigned numche
1f40: 63 6b 73 75 6d 73 20 3d 20 30 3b 0a 09 53 54 41 cksums = 0;..STA
1f50: 43 4b 5f 41 4c 4c 4f 43 28 62 75 66 2c 20 54 6f CK_ALLOC(buf, To
1f60: 6b 65 6e 2c 20 62 6c 6f 63 6b 73 69 7a 65 29 3b ken, blocksize);
1f70: 0a 09 66 6f 72 20 28 75 6e 73 69 67 6e 65 64 20 ..for (unsigned
1f80: 69 20 3d 20 30 3b 20 69 20 3c 20 6e 75 6d 75 6e i = 0; i < numun
1f90: 75 73 65 64 3b 20 2b 2b 69 29 20 7b 0a 09 09 70 used; ++i) {...p
1fa0: 6f 73 20 66 69 72 73 74 20 3d 20 75 6e 75 73 65 os first = unuse
1fb0: 64 5b 69 5d 2e 70 2c 20 6c 61 73 74 20 3d 20 75 d[i].p, last = u
1fc0: 6e 75 73 65 64 5b 69 5d 2e 70 20 2b 20 75 6e 75 nused[i].p + unu
1fd0: 73 65 64 5b 69 5d 2e 6e 75 6d 3b 0a 09 09 66 6f sed[i].num;...fo
1fe0: 72 20 28 70 6f 73 20 6c 6f 63 20 3d 20 66 69 72 r (pos loc = fir
1ff0: 73 74 3b 20 6c 6f 63 20 2b 20 62 6c 6f 63 6b 73 st; loc + blocks
2000: 69 7a 65 20 3c 3d 20 6c 61 73 74 3b 20 6c 6f 63 ize <= last; loc
2010: 20 2b 3d 20 62 6c 6f 63 6b 73 69 7a 65 29 20 7b += blocksize) {
2020: 0a 09 09 09 63 6f 6e 73 74 20 54 6f 6b 65 6e 20 ....const Token
2030: 2a 72 65 61 64 20 3d 20 62 2d 3e 72 65 61 64 31 *read = b->read1
2040: 28 6c 6f 63 29 3b 0a 09 09 09 48 61 73 68 3a 3a (loc);....Hash::
2050: 56 61 6c 75 65 20 62 6c 6f 63 6b 73 75 6d 20 3d Value blocksum =
2060: 20 48 61 73 68 28 72 65 61 64 2c 20 62 6c 6f 63 Hash(read, bloc
2070: 6b 73 69 7a 65 29 2e 67 65 74 56 61 6c 75 65 28 ksize).getValue(
2080: 29 3b 0a 09 09 09 2f 2f 20 41 64 6a 61 63 65 6e );....// Adjacen
2090: 74 20 63 68 65 63 6b 73 75 6d 73 20 61 72 65 20 t checksums are
20a0: 6e 65 76 65 72 20 72 65 70 65 61 74 65 64 2e 0a never repeated..
20b0: 09 09 09 2f 2f 69 66 20 28 21 20 68 2e 6e 75 6d ...//if (! h.num
20c0: 63 68 65 63 6b 73 75 6d 73 20 7c 7c 20 62 6c 6f checksums || blo
20d0: 63 6b 73 75 6d 20 21 3d 20 68 2e 63 68 65 63 6b cksum != h.check
20e0: 73 75 6d 73 5b 68 2e 6e 75 6d 63 68 65 63 6b 73 sums[h.numchecks
20f0: 75 6d 73 20 2d 20 31 5d 2e 63 6b 73 75 6d 29 0a ums - 1].cksum).
2100: 09 09 09 09 68 2e 61 64 64 28 63 68 65 63 6b 73 ....h.add(checks
2110: 75 6d 5f 65 6e 74 72 79 28 62 6c 6f 63 6b 73 75 um_entry(blocksu
2120: 6d 2c 20 6c 6f 63 29 29 3b 0a 09 09 7d 0a 09 7d m, loc));...}..}
2130: 0a 0a 09 69 66 20 28 68 2e 6e 75 6d 63 68 65 63 ...if (h.numchec
2140: 6b 73 75 6d 73 29 20 7b 0a 09 09 73 74 64 3a 3a ksums) {...std::
2150: 73 6f 72 74 28 68 2e 63 68 65 63 6b 73 75 6d 73 sort(h.checksums
2160: 2c 20 68 2e 63 68 65 63 6b 73 75 6d 73 20 2b 20 , h.checksums +
2170: 68 2e 6e 75 6d 63 68 65 63 6b 73 75 6d 73 2c 20 h.numchecksums,
2180: 43 68 65 63 6b 73 75 6d 73 5f 43 6f 6d 70 61 72 Checksums_Compar
2190: 65 28 68 29 29 3b 0a 09 09 63 6f 6e 73 74 20 75 e(h));...const u
21a0: 6e 73 69 67 6e 65 64 20 6d 61 78 49 64 65 6e 74 nsigned maxIdent
21b0: 69 63 61 6c 43 68 65 63 6b 73 75 6d 73 20 3d 20 icalChecksums =
21c0: 32 3b 0a 09 09 70 6f 73 20 77 72 69 74 65 4c 6f 2;...pos writeLo
21d0: 63 20 3d 20 30 2c 20 72 65 61 64 4c 6f 63 2c 20 c = 0, readLoc,
21e0: 74 65 73 74 41 68 65 61 64 3b 0a 09 09 66 6f 72 testAhead;...for
21f0: 20 28 72 65 61 64 4c 6f 63 20 3d 20 30 3b 20 72 (readLoc = 0; r
2200: 65 61 64 4c 6f 63 20 3c 20 68 2e 6e 75 6d 63 68 eadLoc < h.numch
2210: 65 63 6b 73 75 6d 73 3b 20 72 65 61 64 4c 6f 63 ecksums; readLoc
2220: 20 3d 20 74 65 73 74 41 68 65 61 64 29 20 7b 0a = testAhead) {.
2230: 09 09 09 66 6f 72 20 28 74 65 73 74 41 68 65 61 ...for (testAhea
2240: 64 20 3d 20 72 65 61 64 4c 6f 63 3b 20 74 65 73 d = readLoc; tes
2250: 74 41 68 65 61 64 20 3c 20 68 2e 6e 75 6d 63 68 tAhead < h.numch
2260: 65 63 6b 73 75 6d 73 20 26 26 20 68 2e 63 68 65 ecksums && h.che
2270: 63 6b 73 75 6d 73 5b 72 65 61 64 4c 6f 63 5d 2e cksums[readLoc].
2280: 63 6b 73 75 6d 20 3d 3d 20 68 2e 63 68 65 63 6b cksum == h.check
2290: 73 75 6d 73 5b 74 65 73 74 41 68 65 61 64 5d 2e sums[testAhead].
22a0: 63 6b 73 75 6d 3b 20 2b 2b 74 65 73 74 41 68 65 cksum; ++testAhe
22b0: 61 64 29 0a 09 09 09 09 3b 0a 09 09 09 69 66 20 ad).....;....if
22c0: 28 74 65 73 74 41 68 65 61 64 20 2d 20 72 65 61 (testAhead - rea
22d0: 64 4c 6f 63 20 3c 3d 20 6d 61 78 49 64 65 6e 74 dLoc <= maxIdent
22e0: 69 63 61 6c 43 68 65 63 6b 73 75 6d 73 29 0a 09 icalChecksums)..
22f0: 09 09 09 66 6f 72 20 28 70 6f 73 20 69 20 3d 20 ...for (pos i =
2300: 72 65 61 64 4c 6f 63 3b 20 69 20 3c 20 74 65 73 readLoc; i < tes
2310: 74 41 68 65 61 64 3b 20 2b 2b 69 29 0a 09 09 09 tAhead; ++i)....
2320: 09 09 68 2e 63 68 65 63 6b 73 75 6d 73 5b 77 72 ..h.checksums[wr
2330: 69 74 65 4c 6f 63 2b 2b 5d 20 3d 20 68 2e 63 68 iteLoc++] = h.ch
2340: 65 63 6b 73 75 6d 73 5b 69 5d 3b 0a 09 09 7d 0a ecksums[i];...}.
2350: 09 09 68 2e 6e 75 6d 63 68 65 63 6b 73 75 6d 73 ..h.numchecksums
2360: 20 3d 20 77 72 69 74 65 4c 6f 63 3b 0a 09 7d 0a = writeLoc;..}.
2370: 09 68 2e 63 68 65 63 6b 73 75 6d 73 5b 68 2e 6e .h.checksums[h.n
2380: 75 6d 63 68 65 63 6b 73 75 6d 73 5d 2e 63 6b 73 umchecksums].cks
2390: 75 6d 20 3d 20 73 74 64 3a 3a 6e 75 6d 65 72 69 um = std::numeri
23a0: 63 5f 6c 69 6d 69 74 73 3c 48 61 73 68 3a 3a 56 c_limits<Hash::V
23b0: 61 6c 75 65 3e 3a 3a 6d 61 78 28 29 3b 20 2f 2f alue>::max(); //
23c0: 20 49 66 20 74 68 65 72 65 27 73 20 6f 6e 6c 79 If there's only
23d0: 20 6f 6e 65 20 63 68 65 63 6b 73 75 6d 2c 20 77 one checksum, w
23e0: 65 20 6d 69 67 68 74 20 68 69 74 20 74 68 69 73 e might hit this
23f0: 20 61 6e 64 20 6e 6f 74 20 6b 6e 6f 77 20 69 74 and not know it
2400: 2c 0a 09 68 2e 63 68 65 63 6b 73 75 6d 73 5b 68 ,..h.checksums[h
2410: 2e 6e 75 6d 63 68 65 63 6b 73 75 6d 73 5d 2e 6c .numchecksums].l
2420: 6f 63 20 3d 20 30 3b 20 2f 2f 20 53 6f 20 77 65 oc = 0; // So we
2430: 27 6c 6c 20 6a 75 73 74 20 72 65 61 64 20 66 72 'll just read fr
2440: 6f 6d 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 om the beginning
2450: 20 6f 66 20 74 68 65 20 66 69 6c 65 20 74 6f 20 of the file to
2460: 70 72 65 76 65 6e 74 20 63 72 61 73 68 65 73 2e prevent crashes.
2470: 0a 09 68 2e 63 68 65 63 6b 73 75 6d 73 5b 68 2e ..h.checksums[h.
2480: 6e 75 6d 63 68 65 63 6b 73 75 6d 73 20 2b 20 31 numchecksums + 1
2490: 5d 2e 63 6b 73 75 6d 20 3d 20 30 3b 0a 0a 09 66 ].cksum = 0;...f
24a0: 6f 72 20 28 75 6e 73 69 67 6e 65 64 20 69 20 3d or (unsigned i =
24b0: 20 30 3b 20 69 20 3c 20 68 2e 68 74 61 62 6c 65 0; i < h.htable
24c0: 73 69 7a 65 3b 20 2b 2b 69 29 20 68 2e 68 74 61 size; ++i) h.hta
24d0: 62 6c 65 5b 69 5d 20 3d 20 30 3b 0a 09 66 6f 72 ble[i] = 0;..for
24e0: 20 28 69 6e 74 20 69 20 3d 20 68 2e 6e 75 6d 63 (int i = h.numc
24f0: 68 65 63 6b 73 75 6d 73 20 2d 20 31 3b 20 69 20 hecksums - 1; i
2500: 3e 3d 20 30 3b 20 2d 2d 69 29 0a 09 09 68 2e 68 >= 0; --i)...h.h
2510: 74 61 62 6c 65 5b 68 2e 74 61 62 6c 65 49 6e 64 table[h.tableInd
2520: 65 78 28 68 2e 63 68 65 63 6b 73 75 6d 73 5b 69 ex(h.checksums[i
2530: 5d 2e 63 6b 73 75 6d 29 5d 20 3d 20 26 68 2e 63 ].cksum)] = &h.c
2540: 68 65 63 6b 73 75 6d 73 5b 69 5d 3b 0a 0a 09 66 hecksums[i];...f
2550: 6f 72 20 28 75 6e 73 69 67 6e 65 64 20 69 20 3d or (unsigned i =
2560: 20 30 3b 20 69 20 3c 20 6e 75 6d 75 6e 75 73 65 0; i < numunuse
2570: 64 32 3b 20 2b 2b 69 29 0a 09 09 69 66 20 28 75 d2; ++i)...if (u
2580: 6e 75 73 65 64 32 5b 69 5d 2e 6e 75 6d 20 3e 3d nused2[i].num >=
2590: 20 62 6c 6f 63 6b 73 69 7a 65 29 0a 09 09 09 66 blocksize)....f
25a0: 69 6e 64 4d 61 74 63 68 65 73 28 62 2c 20 26 68 indMatches(b, &h
25b0: 2c 20 6d 69 6e 4d 61 74 63 68 53 69 7a 65 2c 20 , minMatchSize,
25c0: 75 6e 75 73 65 64 32 5b 69 5d 2e 70 2c 20 75 6e unused2[i].p, un
25d0: 75 73 65 64 32 5b 69 5d 2e 70 20 2b 20 75 6e 75 used2[i].p + unu
25e0: 73 65 64 32 5b 69 5d 2e 6e 75 6d 2c 20 75 6e 75 sed2[i].num, unu
25f0: 73 65 64 5b 69 5d 2e 70 2c 20 75 6e 75 73 65 64 sed[i].p, unused
2600: 32 5b 69 5d 2e 6d 72 29 3b 0a 0a 09 64 65 6c 65 2[i].mr);...dele
2610: 74 65 20 5b 5d 20 68 2e 68 74 61 62 6c 65 3b 0a te [] h.htable;.
2620: 09 64 65 6c 65 74 65 20 5b 5d 20 68 2e 63 68 65 .delete [] h.che
2630: 63 6b 73 75 6d 73 3b 0a 7d 0a 0a 76 6f 69 64 20 cksums;.}..void
2640: 62 64 65 6c 74 61 5f 73 77 61 70 5f 69 6e 70 75 bdelta_swap_inpu
2650: 74 73 28 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e ts(BDelta_Instan
2660: 63 65 20 2a 62 29 20 7b 0a 09 66 6f 72 20 28 73 ce *b) {..for (s
2670: 74 64 3a 3a 6c 69 73 74 3c 4d 61 74 63 68 3e 3a td::list<Match>:
2680: 3a 69 74 65 72 61 74 6f 72 20 6c 20 3d 20 62 2d :iterator l = b-
2690: 3e 6d 61 74 63 68 65 73 2e 62 65 67 69 6e 28 29 >matches.begin()
26a0: 3b 20 6c 20 21 3d 20 62 2d 3e 6d 61 74 63 68 65 ; l != b->matche
26b0: 73 2e 65 6e 64 28 29 3b 20 2b 2b 6c 29 0a 09 09 s.end(); ++l)...
26c0: 73 74 64 3a 3a 73 77 61 70 28 6c 2d 3e 70 31 2c std::swap(l->p1,
26d0: 20 6c 2d 3e 70 32 29 3b 0a 09 73 74 64 3a 3a 73 l->p2);..std::s
26e0: 77 61 70 28 62 2d 3e 64 61 74 61 31 5f 73 69 7a wap(b->data1_siz
26f0: 65 2c 20 62 2d 3e 64 61 74 61 32 5f 73 69 7a 65 e, b->data2_size
2700: 29 3b 0a 09 73 74 64 3a 3a 73 77 61 70 28 62 2d );..std::swap(b-
2710: 3e 68 61 6e 64 6c 65 31 2c 20 62 2d 3e 68 61 6e >handle1, b->han
2720: 64 6c 65 32 29 3b 0a 09 62 2d 3e 6d 61 74 63 68 dle2);..b->match
2730: 65 73 2e 73 6f 72 74 28 63 6f 6d 70 61 72 65 4d es.sort(compareM
2740: 61 74 63 68 50 32 29 3b 0a 7d 0a 0a 76 6f 69 64 atchP2);.}..void
2750: 20 62 64 65 6c 74 61 5f 63 6c 65 61 6e 5f 6d 61 bdelta_clean_ma
2760: 74 63 68 65 73 28 42 44 65 6c 74 61 5f 49 6e 73 tches(BDelta_Ins
2770: 74 61 6e 63 65 20 2a 62 2c 20 75 6e 73 69 67 6e tance *b, unsign
2780: 65 64 20 66 6c 61 67 73 29 20 7b 0a 09 73 74 64 ed flags) {..std
2790: 3a 3a 6c 69 73 74 3c 4d 61 74 63 68 3e 3a 3a 69 ::list<Match>::i
27a0: 74 65 72 61 74 6f 72 20 6e 65 78 74 4c 20 3d 20 terator nextL =
27b0: 62 2d 3e 6d 61 74 63 68 65 73 2e 62 65 67 69 6e b->matches.begin
27c0: 28 29 3b 0a 09 69 66 20 28 6e 65 78 74 4c 20 3d ();..if (nextL =
27d0: 3d 20 62 2d 3e 6d 61 74 63 68 65 73 2e 65 6e 64 = b->matches.end
27e0: 28 29 29 20 72 65 74 75 72 6e 3b 0a 09 77 68 69 ()) return;..whi
27f0: 6c 65 20 28 74 72 75 65 29 20 7b 0a 09 09 73 74 le (true) {...st
2800: 64 3a 3a 6c 69 73 74 3c 4d 61 74 63 68 3e 3a 3a d::list<Match>::
2810: 69 74 65 72 61 74 6f 72 20 6c 20 3d 20 6e 65 78 iterator l = nex
2820: 74 4c 3b 0a 09 09 69 66 20 28 2b 2b 6e 65 78 74 tL;...if (++next
2830: 4c 20 3d 3d 20 62 2d 3e 6d 61 74 63 68 65 73 2e L == b->matches.
2840: 65 6e 64 28 29 29 0a 09 09 09 62 72 65 61 6b 3b end())....break;
2850: 0a 0a 09 09 69 6e 74 20 6f 76 65 72 6c 61 70 20 ....int overlap
2860: 3d 20 6c 2d 3e 70 32 20 2b 20 6c 2d 3e 6e 75 6d = l->p2 + l->num
2870: 20 2d 20 6e 65 78 74 4c 2d 3e 70 32 3b 0a 09 09 - nextL->p2;...
2880: 69 66 20 28 6f 76 65 72 6c 61 70 20 3e 3d 20 30 if (overlap >= 0
2890: 29 20 7b 0a 09 09 09 69 66 20 28 6f 76 65 72 6c ) {....if (overl
28a0: 61 70 20 3e 3d 20 6e 65 78 74 4c 2d 3e 6e 75 6d ap >= nextL->num
28b0: 29 20 7b 0a 09 09 09 09 62 2d 3e 6d 61 74 63 68 ) {.....b->match
28c0: 65 73 2e 65 72 61 73 65 28 6e 65 78 74 4c 29 3b es.erase(nextL);
28d0: 0a 09 09 09 09 6e 65 78 74 4c 20 3d 20 6c 3b 0a .....nextL = l;.
28e0: 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 ....continue;...
28f0: 09 7d 0a 09 09 09 69 66 20 28 66 6c 61 67 73 20 .}....if (flags
2900: 26 20 42 44 45 4c 54 41 5f 52 45 4d 4f 56 45 5f & BDELTA_REMOVE_
2910: 4f 56 45 52 4c 41 50 29 0a 09 09 09 09 6c 2d 3e OVERLAP).....l->
2920: 6e 75 6d 20 2d 3d 20 6f 76 65 72 6c 61 70 3b 0a num -= overlap;.
2930: 09 09 7d 0a 09 7d 0a 7d 0a 0a 76 6f 69 64 20 62 ..}..}.}..void b
2940: 64 65 6c 74 61 5f 73 68 6f 77 4d 61 74 63 68 65 delta_showMatche
2950: 73 28 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e 63 s(BDelta_Instanc
2960: 65 20 2a 62 29 20 7b 0a 09 66 6f 72 20 28 73 74 e *b) {..for (st
2970: 64 3a 3a 6c 69 73 74 3c 4d 61 74 63 68 3e 3a 3a d::list<Match>::
2980: 69 74 65 72 61 74 6f 72 20 6c 20 3d 20 62 2d 3e iterator l = b->
2990: 6d 61 74 63 68 65 73 2e 62 65 67 69 6e 28 29 3b matches.begin();
29a0: 20 6c 20 21 3d 20 62 2d 3e 6d 61 74 63 68 65 73 l != b->matches
29b0: 2e 65 6e 64 28 29 3b 20 2b 2b 6c 29 0a 09 09 70 .end(); ++l)...p
29c0: 72 69 6e 74 66 28 22 28 25 6c 6c 64 2c 20 25 6c rintf("(%lld, %l
29d0: 6c 64 2c 20 25 6c 6c 64 29 2c 20 22 2c 20 6c 2d ld, %lld), ", l-
29e0: 3e 70 31 2c 20 6c 2d 3e 70 32 2c 20 6c 2d 3e 6e >p1, l->p2, l->n
29f0: 75 6d 29 3b 0a 09 70 72 69 6e 74 66 20 28 22 5c um);..printf ("\
2a00: 6e 5c 6e 22 29 3b 0a 7d 0a 0a 76 6f 69 64 20 67 n\n");.}..void g
2a10: 65 74 5f 75 6e 75 73 65 64 5f 62 6c 6f 63 6b 73 et_unused_blocks
2a20: 28 55 6e 75 73 65 64 52 61 6e 67 65 20 2a 75 6e (UnusedRange *un
2a30: 75 73 65 64 2c 20 75 6e 73 69 67 6e 65 64 20 2a used, unsigned *
2a40: 6e 75 6d 75 6e 75 73 65 64 70 74 72 29 20 7b 0a numunusedptr) {.
2a50: 09 75 6e 73 69 67 6e 65 64 20 6e 65 78 74 53 74 .unsigned nextSt
2a60: 61 72 74 50 6f 73 20 3d 20 30 3b 0a 09 66 6f 72 artPos = 0;..for
2a70: 20 28 75 6e 73 69 67 6e 65 64 20 69 20 3d 20 31 (unsigned i = 1
2a80: 3b 20 69 20 3c 20 2a 6e 75 6d 75 6e 75 73 65 64 ; i < *numunused
2a90: 70 74 72 3b 20 2b 2b 69 29 20 7b 0a 09 09 70 6f ptr; ++i) {...po
2aa0: 73 20 73 74 61 72 74 50 6f 73 20 3d 20 6e 65 78 s startPos = nex
2ab0: 74 53 74 61 72 74 50 6f 73 3b 0a 09 09 6e 65 78 tStartPos;...nex
2ac0: 74 53 74 61 72 74 50 6f 73 20 3d 20 73 74 64 3a tStartPos = std:
2ad0: 3a 6d 61 78 28 73 74 61 72 74 50 6f 73 2c 20 75 :max(startPos, u
2ae0: 6e 75 73 65 64 5b 69 5d 2e 70 20 2b 20 75 6e 75 nused[i].p + unu
2af0: 73 65 64 5b 69 5d 2e 6e 75 6d 29 3b 0a 09 09 75 sed[i].num);...u
2b00: 6e 75 73 65 64 5b 69 5d 20 3d 20 55 6e 75 73 65 nused[i] = Unuse
2b10: 64 52 61 6e 67 65 28 73 74 61 72 74 50 6f 73 2c dRange(startPos,
2b20: 20 75 6e 75 73 65 64 5b 69 5d 2e 70 20 3c 20 73 unused[i].p < s
2b30: 74 61 72 74 50 6f 73 20 3f 20 30 20 3a 20 75 6e tartPos ? 0 : un
2b40: 75 73 65 64 5b 69 5d 2e 70 20 2d 20 73 74 61 72 used[i].p - star
2b50: 74 50 6f 73 2c 20 75 6e 75 73 65 64 5b 69 2d 31 tPos, unused[i-1
2b60: 5d 2e 6d 72 2c 20 75 6e 75 73 65 64 5b 69 5d 2e ].mr, unused[i].
2b70: 6d 72 29 3b 0a 09 7d 0a 7d 0a 0a 62 6f 6f 6c 20 mr);..}.}..bool
2b80: 69 73 5a 65 72 6f 4d 61 74 63 68 28 4d 61 74 63 isZeroMatch(Matc
2b90: 68 20 26 6d 29 20 7b 72 65 74 75 72 6e 20 6d 2e h &m) {return m.
2ba0: 6e 75 6d 20 3d 3d 20 30 3b 7d 0a 0a 76 6f 69 64 num == 0;}..void
2bb0: 20 62 64 65 6c 74 61 5f 70 61 73 73 28 42 44 65 bdelta_pass(BDe
2bc0: 6c 74 61 5f 49 6e 73 74 61 6e 63 65 20 2a 62 2c lta_Instance *b,
2bd0: 20 75 6e 73 69 67 6e 65 64 20 62 6c 6f 63 6b 73 unsigned blocks
2be0: 69 7a 65 2c 20 75 6e 73 69 67 6e 65 64 20 6d 69 ize, unsigned mi
2bf0: 6e 4d 61 74 63 68 53 69 7a 65 2c 20 70 6f 73 20 nMatchSize, pos
2c00: 6d 61 78 48 6f 6c 65 53 69 7a 65 2c 20 75 6e 73 maxHoleSize, uns
2c10: 69 67 6e 65 64 20 66 6c 61 67 73 29 20 7b 0a 09 igned flags) {..
2c20: 2f 2f 20 50 6c 61 63 65 20 61 6e 20 65 6d 70 74 // Place an empt
2c30: 79 20 4d 61 74 63 68 20 61 74 20 62 65 67 69 6e y Match at begin
2c40: 6e 69 6e 67 20 73 6f 20 77 65 20 63 61 6e 20 61 ning so we can a
2c50: 73 73 75 6d 65 20 74 68 65 72 65 27 73 20 61 20 ssume there's a
2c60: 4d 61 74 63 68 20 74 6f 20 74 68 65 20 6c 65 66 Match to the lef
2c70: 74 20 6f 66 20 65 76 65 72 79 20 68 6f 6c 65 2e t of every hole.
2c80: 0a 09 62 2d 3e 6d 61 74 63 68 65 73 2e 70 75 73 ..b->matches.pus
2c90: 68 5f 66 72 6f 6e 74 28 4d 61 74 63 68 28 30 2c h_front(Match(0,
2ca0: 20 30 2c 20 30 29 29 3b 0a 09 2f 2f 20 54 72 69 0, 0));..// Tri
2cb0: 63 6b 20 66 6f 72 20 69 6e 63 6c 75 64 69 6e 67 ck for including
2cc0: 20 74 68 65 20 66 72 65 65 20 72 61 6e 67 65 20 the free range
2cd0: 61 74 20 74 68 65 20 65 6e 64 2e 0a 09 62 2d 3e at the end...b->
2ce0: 6d 61 74 63 68 65 73 2e 70 75 73 68 5f 62 61 63 matches.push_bac
2cf0: 6b 28 4d 61 74 63 68 28 62 2d 3e 64 61 74 61 31 k(Match(b->data1
2d00: 5f 73 69 7a 65 2c 20 62 2d 3e 64 61 74 61 32 5f _size, b->data2_
2d10: 73 69 7a 65 2c 20 30 29 29 3b 0a 0a 09 55 6e 75 size, 0));...Unu
2d20: 73 65 64 52 61 6e 67 65 20 2a 75 6e 75 73 65 64 sedRange *unused
2d30: 20 3d 20 6e 65 77 20 55 6e 75 73 65 64 52 61 6e = new UnusedRan
2d40: 67 65 5b 62 2d 3e 6d 61 74 63 68 65 73 2e 73 69 ge[b->matches.si
2d50: 7a 65 28 29 20 2b 20 31 5d 2c 0a 09 09 09 20 20 ze() + 1],....
2d60: 20 20 2a 75 6e 75 73 65 64 32 20 3d 20 6e 65 77 *unused2 = new
2d70: 20 55 6e 75 73 65 64 52 61 6e 67 65 5b 62 2d 3e UnusedRange[b->
2d80: 6d 61 74 63 68 65 73 2e 73 69 7a 65 28 29 20 2b matches.size() +
2d90: 20 31 5d 3b 0a 09 75 6e 73 69 67 6e 65 64 20 6e 1];..unsigned n
2da0: 75 6d 75 6e 75 73 65 64 20 3d 20 30 2c 20 6e 75 umunused = 0, nu
2db0: 6d 75 6e 75 73 65 64 32 20 3d 20 30 3b 0a 09 66 munused2 = 0;..f
2dc0: 6f 72 20 28 73 74 64 3a 3a 6c 69 73 74 3c 4d 61 or (std::list<Ma
2dd0: 74 63 68 3e 3a 3a 69 74 65 72 61 74 6f 72 20 6c tch>::iterator l
2de0: 20 3d 20 62 2d 3e 6d 61 74 63 68 65 73 2e 62 65 = b->matches.be
2df0: 67 69 6e 28 29 3b 20 6c 20 21 3d 20 62 2d 3e 6d gin(); l != b->m
2e00: 61 74 63 68 65 73 2e 65 6e 64 28 29 3b 20 2b 2b atches.end(); ++
2e10: 6c 29 20 7b 0a 09 09 75 6e 75 73 65 64 5b 6e 75 l) {...unused[nu
2e20: 6d 75 6e 75 73 65 64 2b 2b 5d 20 3d 20 55 6e 75 munused++] = Unu
2e30: 73 65 64 52 61 6e 67 65 28 6c 2d 3e 70 31 2c 20 sedRange(l->p1,
2e40: 6c 2d 3e 6e 75 6d 2c 20 6c 2c 20 6c 29 3b 0a 09 l->num, l, l);..
2e50: 09 75 6e 75 73 65 64 32 5b 6e 75 6d 75 6e 75 73 .unused2[numunus
2e60: 65 64 32 2b 2b 5d 20 3d 20 55 6e 75 73 65 64 52 ed2++] = UnusedR
2e70: 61 6e 67 65 28 6c 2d 3e 70 32 2c 20 6c 2d 3e 6e ange(l->p2, l->n
2e80: 75 6d 2c 20 6c 2c 20 6c 29 3b 0a 09 7d 0a 0a 09 um, l, l);..}...
2e90: 73 74 64 3a 3a 73 6f 72 74 28 75 6e 75 73 65 64 std::sort(unused
2ea0: 20 2b 20 31 2c 20 75 6e 75 73 65 64 20 2b 20 6e + 1, unused + n
2eb0: 75 6d 75 6e 75 73 65 64 2c 20 63 6f 6d 70 61 72 umunused, compar
2ec0: 65 70 29 3b 20 2f 2f 20 4c 65 61 76 65 20 65 6d ep); // Leave em
2ed0: 70 74 79 20 6d 61 74 63 68 20 61 74 20 62 65 67 pty match at beg
2ee0: 69 6e 6e 69 6e 67 0a 09 2f 2f 73 74 64 3a 3a 73 inning..//std::s
2ef0: 6f 72 74 28 75 6e 75 73 65 64 32 2c 20 75 6e 75 ort(unused2, unu
2f00: 73 65 64 32 20 2b 20 6e 75 6d 75 6e 75 73 65 64 sed2 + numunused
2f10: 32 2c 20 63 6f 6d 70 61 72 65 70 29 3b 0a 0a 09 2, comparep);...
2f20: 67 65 74 5f 75 6e 75 73 65 64 5f 62 6c 6f 63 6b get_unused_block
2f30: 73 28 75 6e 75 73 65 64 2c 20 20 26 6e 75 6d 75 s(unused, &numu
2f40: 6e 75 73 65 64 29 3b 0a 09 67 65 74 5f 75 6e 75 nused);..get_unu
2f50: 73 65 64 5f 62 6c 6f 63 6b 73 28 75 6e 75 73 65 sed_blocks(unuse
2f60: 64 32 2c 20 26 6e 75 6d 75 6e 75 73 65 64 32 29 d2, &numunused2)
2f70: 3b 0a 09 2f 2f 73 74 64 3a 3a 73 6f 72 74 28 75 ;..//std::sort(u
2f80: 6e 75 73 65 64 32 2c 20 75 6e 75 73 65 64 32 20 nused2, unused2
2f90: 2b 20 6e 75 6d 75 6e 75 73 65 64 32 2c 20 63 6f + numunused2, co
2fa0: 6d 70 61 72 65 6d 72 70 32 29 3b 0a 0a 09 69 66 mparemrp2);...if
2fb0: 20 28 66 6c 61 67 73 20 26 20 42 44 45 4c 54 41 (flags & BDELTA
2fc0: 5f 47 4c 4f 42 41 4c 29 0a 09 09 62 64 65 6c 74 _GLOBAL)...bdelt
2fd0: 61 5f 70 61 73 73 5f 32 28 62 2c 20 62 6c 6f 63 a_pass_2(b, bloc
2fe0: 6b 73 69 7a 65 2c 20 6d 69 6e 4d 61 74 63 68 53 ksize, minMatchS
2ff0: 69 7a 65 2c 20 75 6e 75 73 65 64 2c 20 6e 75 6d ize, unused, num
3000: 75 6e 75 73 65 64 2c 20 75 6e 75 73 65 64 32 2c unused, unused2,
3010: 20 6e 75 6d 75 6e 75 73 65 64 32 29 3b 0a 09 65 numunused2);..e
3020: 6c 73 65 20 7b 0a 09 09 73 74 64 3a 3a 73 6f 72 lse {...std::sor
3030: 74 28 75 6e 75 73 65 64 20 2b 20 31 2c 20 75 6e t(unused + 1, un
3040: 75 73 65 64 20 2b 20 6e 75 6d 75 6e 75 73 65 64 used + numunused
3050: 2c 20 63 6f 6d 70 61 72 65 6d 72 70 32 29 3b 0a , comparemrp2);.
3060: 09 09 66 6f 72 20 28 75 6e 73 69 67 6e 65 64 20 ..for (unsigned
3070: 69 20 3d 20 31 3b 20 69 20 3c 20 6e 75 6d 75 6e i = 1; i < numun
3080: 75 73 65 64 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 used; ++i) {....
3090: 55 6e 75 73 65 64 52 61 6e 67 65 20 75 31 20 3d UnusedRange u1 =
30a0: 20 75 6e 75 73 65 64 5b 69 5d 2c 20 75 32 20 3d unused[i], u2 =
30b0: 20 75 6e 75 73 65 64 32 5b 69 5d 3b 0a 09 09 09 unused2[i];....
30c0: 69 66 20 28 75 31 2e 6e 75 6d 20 3e 3d 20 62 6c if (u1.num >= bl
30d0: 6f 63 6b 73 69 7a 65 20 26 26 20 75 32 2e 6e 75 ocksize && u2.nu
30e0: 6d 20 3e 3d 20 62 6c 6f 63 6b 73 69 7a 65 29 0a m >= blocksize).
30f0: 09 09 09 09 69 66 20 28 21 20 6d 61 78 48 6f 6c ....if (! maxHol
3100: 65 53 69 7a 65 20 7c 7c 20 28 75 31 2e 6e 75 6d eSize || (u1.num
3110: 20 3c 3d 20 6d 61 78 48 6f 6c 65 53 69 7a 65 20 <= maxHoleSize
3120: 26 26 20 75 32 2e 6e 75 6d 20 3c 3d 20 6d 61 78 && u2.num <= max
3130: 48 6f 6c 65 53 69 7a 65 29 29 0a 09 09 09 09 09 HoleSize))......
3140: 69 66 20 28 21 20 28 66 6c 61 67 73 20 26 20 42 if (! (flags & B
3150: 44 45 4c 54 41 5f 53 49 44 45 53 5f 4f 52 44 45 DELTA_SIDES_ORDE
3160: 52 45 44 29 20 7c 7c 20 28 6e 65 78 74 69 28 75 RED) || (nexti(u
3170: 31 2e 6d 6c 29 20 3d 3d 20 75 31 2e 6d 72 20 26 1.ml) == u1.mr &
3180: 26 20 6e 65 78 74 69 28 75 32 2e 6d 6c 29 20 3d & nexti(u2.ml) =
3190: 3d 20 75 32 2e 6d 72 29 29 0a 09 09 09 09 09 09 = u2.mr)).......
31a0: 62 64 65 6c 74 61 5f 70 61 73 73 5f 32 28 62 2c bdelta_pass_2(b,
31b0: 20 62 6c 6f 63 6b 73 69 7a 65 2c 20 6d 69 6e 4d blocksize, minM
31c0: 61 74 63 68 53 69 7a 65 2c 20 26 75 31 2c 20 31 atchSize, &u1, 1
31d0: 2c 20 26 75 32 2c 20 31 29 3b 0a 09 09 7d 0a 09 , &u2, 1);...}..
31e0: 7d 0a 0a 09 69 66 20 28 76 65 72 62 6f 73 65 29 }...if (verbose)
31f0: 20 70 72 69 6e 74 66 28 22 70 61 73 73 20 28 62 printf("pass (b
3200: 6c 6f 63 6b 73 69 7a 65 3a 20 25 75 2c 20 6d 61 locksize: %u, ma
3210: 74 63 68 65 73 3a 20 25 6c 75 29 5c 6e 22 2c 20 tches: %lu)\n",
3220: 62 6c 6f 63 6b 73 69 7a 65 2c 20 28 75 6e 73 69 blocksize, (unsi
3230: 67 6e 65 64 20 6c 6f 6e 67 29 62 2d 3e 6d 61 74 gned long)b->mat
3240: 63 68 65 73 2e 73 69 7a 65 28 29 29 3b 0a 0a 09 ches.size());...
3250: 2f 2f 20 47 65 74 20 72 69 64 20 6f 66 20 74 68 // Get rid of th
3260: 65 20 64 75 6d 6d 79 20 76 61 6c 75 65 73 20 77 e dummy values w
3270: 65 20 70 6c 61 63 65 64 20 61 74 20 74 68 65 20 e placed at the
3280: 65 6e 64 73 2e 0a 09 62 2d 3e 6d 61 74 63 68 65 ends...b->matche
3290: 73 2e 65 72 61 73 65 28 73 74 64 3a 3a 66 69 6e s.erase(std::fin
32a0: 64 5f 69 66 28 62 2d 3e 6d 61 74 63 68 65 73 2e d_if(b->matches.
32b0: 62 65 67 69 6e 28 29 2c 20 62 2d 3e 6d 61 74 63 begin(), b->matc
32c0: 68 65 73 2e 65 6e 64 28 29 2c 20 69 73 5a 65 72 hes.end(), isZer
32d0: 6f 4d 61 74 63 68 29 29 3b 0a 09 62 2d 3e 6d 61 oMatch));..b->ma
32e0: 74 63 68 65 73 2e 70 6f 70 5f 62 61 63 6b 28 29 tches.pop_back()
32f0: 3b 0a 0a 09 64 65 6c 65 74 65 20 5b 5d 20 75 6e ;...delete [] un
3300: 75 73 65 64 3b 0a 09 64 65 6c 65 74 65 20 5b 5d used;..delete []
3310: 20 75 6e 75 73 65 64 32 3b 0a 7d 0a 0a 75 6e 73 unused2;.}..uns
3320: 69 67 6e 65 64 20 62 64 65 6c 74 61 5f 6e 75 6d igned bdelta_num
3330: 4d 61 74 63 68 65 73 28 42 44 65 6c 74 61 5f 49 Matches(BDelta_I
3340: 6e 73 74 61 6e 63 65 20 2a 62 29 20 7b 0a 09 72 nstance *b) {..r
3350: 65 74 75 72 6e 20 62 2d 3e 6d 61 74 63 68 65 73 eturn b->matches
3360: 2e 73 69 7a 65 28 29 3b 0a 7d 0a 0a 76 6f 69 64 .size();.}..void
3370: 20 62 64 65 6c 74 61 5f 67 65 74 4d 61 74 63 68 bdelta_getMatch
3380: 28 42 44 65 6c 74 61 5f 49 6e 73 74 61 6e 63 65 (BDelta_Instance
3390: 20 2a 62 2c 20 75 6e 73 69 67 6e 65 64 20 6d 61 *b, unsigned ma
33a0: 74 63 68 4e 75 6d 2c 0a 09 09 70 6f 73 20 2a 70 tchNum,...pos *p
33b0: 31 2c 20 70 6f 73 20 2a 70 32 2c 20 70 6f 73 20 1, pos *p2, pos
33c0: 2a 6e 75 6d 29 20 7b 0a 09 69 6e 74 20 26 61 63 *num) {..int &ac
33d0: 63 65 73 73 5f 69 6e 74 20 3d 20 62 2d 3e 61 63 cess_int = b->ac
33e0: 63 65 73 73 5f 69 6e 74 3b 0a 09 73 74 64 3a 3a cess_int;..std::
33f0: 6c 69 73 74 3c 4d 61 74 63 68 3e 3a 3a 69 74 65 list<Match>::ite
3400: 72 61 74 6f 72 20 26 61 63 63 65 73 73 70 6c 61 rator &accesspla
3410: 63 65 20 3d 20 62 2d 3e 61 63 63 65 73 73 70 6c ce = b->accesspl
3420: 61 63 65 3b 0a 09 69 66 20 28 61 63 63 65 73 73 ace;..if (access
3430: 5f 69 6e 74 20 3d 3d 20 2d 31 29 20 7b 61 63 63 _int == -1) {acc
3440: 65 73 73 5f 69 6e 74 20 3d 20 30 3b 20 61 63 63 ess_int = 0; acc
3450: 65 73 73 70 6c 61 63 65 20 3d 20 62 2d 3e 6d 61 essplace = b->ma
3460: 74 63 68 65 73 2e 62 65 67 69 6e 28 29 3b 7d 0a tches.begin();}.
3470: 09 77 68 69 6c 65 20 28 28 75 6e 73 69 67 6e 65 .while ((unsigne
3480: 64 29 61 63 63 65 73 73 5f 69 6e 74 20 3c 20 6d d)access_int < m
3490: 61 74 63 68 4e 75 6d 29 20 7b 0a 09 09 2b 2b 61 atchNum) {...++a
34a0: 63 63 65 73 73 70 6c 61 63 65 3b 0a 09 09 2b 2b ccessplace;...++
34b0: 61 63 63 65 73 73 5f 69 6e 74 3b 0a 09 7d 0a 09 access_int;..}..
34c0: 77 68 69 6c 65 20 28 28 75 6e 73 69 67 6e 65 64 while ((unsigned
34d0: 29 61 63 63 65 73 73 5f 69 6e 74 20 3e 20 6d 61 )access_int > ma
34e0: 74 63 68 4e 75 6d 29 20 7b 0a 09 09 2d 2d 61 63 tchNum) {...--ac
34f0: 63 65 73 73 70 6c 61 63 65 3b 0a 09 09 2d 2d 61 cessplace;...--a
3500: 63 63 65 73 73 5f 69 6e 74 3b 0a 09 7d 0a 09 2a ccess_int;..}..*
3510: 70 31 20 3d 20 61 63 63 65 73 73 70 6c 61 63 65 p1 = accessplace
3520: 2d 3e 70 31 3b 0a 09 2a 70 32 20 3d 20 61 63 63 ->p1;..*p2 = acc
3530: 65 73 73 70 6c 61 63 65 2d 3e 70 32 3b 0a 09 2a essplace->p2;..*
3540: 6e 75 6d 20 3d 20 61 63 63 65 73 73 70 6c 61 63 num = accessplac
3550: 65 2d 3e 6e 75 6d 3b 0a 7d 0a 0a 69 6e 74 20 62 e->num;.}..int b
3560: 64 65 6c 74 61 5f 67 65 74 45 72 72 6f 72 28 42 delta_getError(B
3570: 44 65 6c 74 61 5f 49 6e 73 74 61 6e 63 65 20 2a Delta_Instance *
3580: 69 6e 73 74 61 6e 63 65 29 20 7b 0a 09 72 65 74 instance) {..ret
3590: 75 72 6e 20 69 6e 73 74 61 6e 63 65 2d 3e 65 72 urn instance->er
35a0: 72 6f 72 63 6f 64 65 3b 0a 7d 0a rorcode;.}.