[Java] RSync Rolling Checksum

[Hu5eL]

Hallo zusammen,

ich versuche die fortlaufende Prüfsumme in rsync nachzubauen.
https://rsync.samba.org/tech_report/node3.html
(https://rsync.samba.org/tech_report/node3.html)
Es geht mir nicht um Geschwindigkeit, sondern um Verständnis.
Mein Code:

public static int[] calcPruef(int k,int l, int x[], int M) {
int result_a = 0, result_b = 0, result_s = 0;

for(int i = k; i <= l; i++) { result_a += x[i-1]; }
result_a = result_a % M;

for(int i = k; i <= l; i++) { result_b = (l-i+1)*x[i-1]; }
result_b = result_b % M;

result_s = result_a + M*result_b;
return new int[] {result_a,result_b,result_s};
}

public static int[] calcPruefNext(int k,int l, int x[], int M,int result_a, int result_b) {
int result_a_new = 0, result_b_new = 0, result_s = 0;
result_a_new = (result_a-x[k-1]+x[l-1+1]) % M;
result_b_new = (result_b - (l-k+1)*x[k-1] + result_a_new) % M;
result_s = result_a_new + M*result_b_new;
return new int[] {result_a_new,result_b_new,result_s};
}


Die Berechnung der Funktion calcPruef scheint zu passen:

x = new int[] {9,8,7,6,5};
k = 1;
l = 5;
result = calcPruef(k,l,x,M);
System.out.println("Result " + Arrays.stream(Arrays.copyOfRange(x,k-1,l-1)).mapToObj(String::valueOf).collect(Collectors.j oining(",")) + " = " + result[0] + " | " + result[1] + " | " + result[2]);

x = new int[]{4,2,5,9,8,7,6,5};
k = 4;
l = 8;
result = calcPruef(k,l,x,M);
System.out.println("Result " + Arrays.stream(Arrays.copyOfRange(x,k-1,l-1)).mapToObj(String::valueOf).collect(Collectors.j oining(",")) + " = " + result[0] + " | " + result[1] + " | " + result[2]);

Ergebnis:


Result 9,8,7,6 = 3 | 5 | 163
Result 9,8,7,6 = 3 | 5 | 163
Jetzt mein Problem. Wenn ich folgende Ausführe:

x = new int[] {9,8,7,6,5};
k = 1;
l = 5;
result = calcPruef(k,l,x,M);
System.out.println("Result " + Arrays.stream(Arrays.copyOfRange(x,k-1,l-1)).mapToObj(String::valueOf).collect(Collectors.j oining(",")) + " = " + result[0] + " | " + result[1] + " | " + result[2]);

x = new int[]{3,9,8,7,6,5};
k = 1;
l = 5;
result = calcPruef(k,l,x,M);
System.out.println("Result " + Arrays.stream(Arrays.copyOfRange(x,k-1,l-1)).mapToObj(String::valueOf).collect(Collectors.j oining(",")) + " = " + result[0] + " | " + result[1] + " | " + result[2]);

//Über Fortlaufende Prüfsumme
result = calcPruefNext(k,l,x,M,result[0],result[1]);
l += 1;
k += 1;
System.out.println("Result " + Arrays.stream(Arrays.copyOfRange(x,k-1,l-1)).mapToObj(String::valueOf).collect(Collectors.j oining(",")) + " = " + result[0] + " | " + result[1] + " | " + result[2]);
Hätte ich erwartet, dass die das Ergebnis von "calcPruefNext" die Prüfsumme 163 ergibt (und a=3 , b=5)
Ich erhalte jedoch

Result 9,8,7,6 = 3 | -6 | -189

Leider finde ich den Fehler nicht. Die Berechnung von "result_a_new" scheint zu passen (ergibt 3). Aber das "result_b_new" ist -6, erwartet hätte ich aber eine 5.

Kann mir jemand helfen?

[Hu5eL]

Fehler war hier:


for(int i = k; i <= l; i++) { result_b += (l-i+1)*x[i-1]; }

Das "+" hat gefehlt.