Diskussion:Adler-32

Noch ein C-Typ Hinweis: unsigned char* ist zwar für die Berechnung notwendig, aber als Parameter als Pointer meist unhandlich. void* ist hier sicher eine bessere Wahl.

Vorschlag:

/* Beispielcode zur Berechnung der Adler-32-Prüfsumme */
 
uint32_t adler32(const void* buffer, size_t buflength)
{
  const unsigned char* pBuffer = (const unsigned char*)buffer;
  uint32_t s1 = 1;
  uint32_t s2 = 0;
  
  for (size_t n=0; n<buflength; n++)
  {
     s1 = (s1 + pBuffer[n]) % 65521;
     s2 = (s2 + s1)     % 65521;
  }

  return (s2 << 16) + s1;
}

-- stsz 14:03, 10. Jul. 2008 (CEST)

---

Begründung, warum 4096:

Angenommen, s1 und s2 haben bereits den Wert 65536=2^16 (obere Schranke, tatsächlicher Wert ist maximal 65519). Weiterhin angenommen, bei jeder Iteration wird der Wert 256=2^8 hinzuaddiert (ebenfalls obere Schranke, tatsächlicher Wert<=255).

Dann werden in s1 die Werte 2^16+n*2^8 kumuliert; in s2 jedoch die Werte (n+1)*2^16+n*(n+1)/2*2^8. Dieser Wert muß geringer sein als 2^32.

${\begin{matrix}2^{8}\cdot {\frac {n^{2}}{2}}&+2^{8}\cdot {\frac {n}{2}}&+2^{16}\cdot n+2^{16}<2^{32}\\2^{7}\cdot n^{2}&+2^{7}\cdot n&+2^{16}\cdot n+2^{16}<2^{32}\end{matrix}}$

Es ergibt sich, daß n=2^12=4096 diese Bedingung gerade noch erfüllt, 2^13 jedoch nicht mehr.

Diese Abschätzung gilt für s2. Die Modulo-Häufigkeit für s1 dürfte noch geringer gewählt werden; aus Symmetriegründen empfiehlt es sich jedoch, die beiden Häufigkeiten parallel zu halten.

Des weiteren wäre es möglich, s1 und s2 nach jeder Iteration auf >=65521 zu testen und ggf. 65521 abzuziehen. --84.165.231.154 20:16, 12. Feb 2006 (CET)

---

Der im RFC1950 angegebene Wert von 5552 ist der richtige:

• Die Modulo-Häufigkeit von s1 darf nicht geringer gewählt werden, sondern muss mit der Modulo-Operation von s2 durchgeführt werden, sonst stimmt hinterher die Voraussetzung nicht mehr dass s1<=65520 ist. Die Abschätzung wäre also nur für den ersten Modulo-Durchlauf richtig. Auch wäre es recht sinnfrei die Modulo-Operation von s1 häufiger durchzuführen als die von s2, da man - um die Voraussetzung wieder zu erhalten - den Modulo ja sowieso mit dem von s2 durchführen muss. Es sind also nicht Symmetriegründe die dafür sprechen, sondern eine korrekte Implementierung muss den Modulo von s1 und s2 gleichzeitig durchzuführen.

• Die Abschätzung hat für die Werte eine zu hohe Annahme. Auf Bytes bezogen (im Gegensatz zu Unicodes) addiert man höchstens den Byte-Wert 255. s1 und s2 sind am Anfang der Iteration maximal 65520. Rechnet man das durch ergibt sich die im RFC1950 angegebene Länge zwischen den Modulo-Schritten von 5552.

Den Wert im RFC kann man wie folgt einsehen:

${\begin{array}{lrl}s1(0)&:=&65520\\s1(n)&:=&s1(n-1)+255=65520+\sum _{k=1}^{n}{255}=65520+n\cdot 255\\s2(0)&:=&65520\\s2(n)&:=&s2(n-1)+s1(n)=65520+\sum _{k=1}^{n}{s1(k)}=65520+\sum _{k=1}^{n}{(65520+k\cdot 255)}\\&=&65520+\sum _{k=1}^{n}{65520}+\sum _{k=1}^{n}{k\cdot 255}=65520+n\cdot 65520+255\cdot \sum _{k=1}^{n}{k}\\&=&65520+n\cdot 65520+255\cdot {\frac {n\cdot (n+1)}{2}}=65520+n\cdot 65520+127{,}5\cdot (n^{2}+n)\\&=&{\frac {255}{2}}n^{2}+{\frac {131295}{2}}n+65520\end{array}}$

Mit der Bedingung $s2(n)<2^{32}$ ergibt sich dann folgende Gleichung:

${\frac {255}{2}}x^{2}+{\frac {131295}{2}}x+65520-2^{32}=0$

So, jetzt packen wir die Formelsammlung aus und finden heraus:

${\begin{array}{lrl}x_{1,2}&=&{\frac {-{\frac {131295}{2}}\pm {\sqrt {({\frac {131295}{2}})^{2}-4{\frac {255}{2}}(65520-2^{32})}}}{2{\frac {255}{2}}}}\\&=&{\frac {-{\frac {131295}{2}}\pm {\sqrt {{\frac {17238377025}{4}}+510(4294901776)}}}{255}}\\&=&{\frac {-65647{,}5\pm {\sqrt {2194709500016{,}25}}}{255}}\\&=&-257{,}44117647\pm 5809{,}6282226\end{array}}$

Damit erhält man eine Nullstelle bei ca. 5552,187 und somit den im RFC angegebenen Wert. Ich habe den Artikel entsprechend korrigiert.

Tino, 91.64.104.56 17:26, 27. Aug. 2007 (CEST)

Hinweise zu weiteren Optimierungsmöglichkeiten:

• Wenn man mit der Prüfsumme startet, also s1(0)=1 und s2(0)=0, dann ergibt sich der erste Zwang zum Modulo erst nach 5803 Byte.
• Spart man sich den Modulo von s1, läuft s2 im 5803er Fall frühestens wieder bei Position 8207 über, danach wieder bei 10051 bzw. 11606. Per 5552er-Regel lässt sich mit 4 Modulos bereits Byte 11104 erreichen, somit kann man im Intervall 5553..5803 zwei und im Intervall 5804..8207 sowie 11105..11606 eine Modulo-Operation durch das Auslassen der Modulos von s1 sparen. Dagegen steht eine gestiegene Programmkomplexität.
• Wenn man mit signed 32 Bit rechnet (also nur 31 Bit hat) sind die entsprechenden Grenzen (s1(0)=1, s2(0)=0) 4103 bzw. (modulo von s1 ausgelassen) 5803 (kein Tippfehler) bzw. 7107 und 8206 Byte.
• Wenn man mit signed 32 Bit rechnet und der Startwert für s1(0) und s2(0) beliebig ist (das bedeutet <=65520), muss man den Modulo alle 3854 Byte durchführen. Eine Optimierung durch vorherigen Fall ergibt sich also in den Intervallen 3855..4103 bzw. 4104..5803 und 7709..8206.

Die Werte wurden übrigens von mir per Excel berechnet, deshalb sollte man ihnen erst trauen, wenn irgendwer das nochmals mit anderen Mitteln verifiziert hat.

Tino, 91.64.74.131 22:33, 5. Sep. 2007 (CEST)

Anmerkung zur Anmerkung zur Beispielimplementierung

Wenn man schon auf die Typen von C99 verweist, sollte man die Puffergröße auch als size_t und nicht als unsigned int nehmen ;-)

Ich habs mal schnell geändert

Chloch 00:35, 17. Dez. 2007 (CET)

Vielen Dank Herr Lehrer!

"Obwohl der Algorithmus sehr einfach ist, sei hier eine Beispielimplementierung in C angegeben:" . Sollte man das wirklich so stehen lassen? (nicht signierter Beitrag von 84.180.114.54 (Diskussion) 21:48, 7. Dez. 2015 (CET))