และพอดีไปเจอว่าเกมนึงเค้าใช้ ก็เลยแวะมาพิมพ์เล่นๆ พอขำๆ
Adler-32 คืออะไร
วิกิ เค้าว่า
Adler-32 is a checksum algorithm which was invented by Mark Adler.
Compared to a cyclic redundancy check of the same length it trades reliability for speed.
Compared to a cyclic redundancy check of the same length it trades reliability for speed.
ข้อดี rfc 1950 เค้าบอก
The Adler-32 algorithm is much faster than the CRC32 algorithm
yet still provides an extremely low probability of undetected errors.
yet still provides an extremely low probability of undetected errors.
หลักการคิด
ให้ C คือ Adler-32 checksum หาได้จาก
calculating two 16-bit checksums A and B and concatenating their bits into a 32-bit integer
จะได้ว่า
C=(B*(2^16))+A
ให้ A คือผลรวมของทุกๆ D จำนวน n แล้วบวกด้วย 1 เสร็จแล้วหารเอาเศษด้วย 65521
เหตุที่ต้องบวกหนึ่ง rfc บอกว่า
The sum A is initialized to 1 instead of zero to make the length
of the sequence part of B, so that the length does not have to be
checked separately.
ส่วน 65521 คือจำนวนเฉพาะที่มากที่สุดของจำนวน 2^16
ที่ต้องหาร เพราะว่า
That 65521 is prime is important to avoid a possible
large class of two-byte errors that leave the check unchanged.
จึงได้ว่า
A=(1+D1+D2+...+Dn)%65521
ให้ B คือผลรวมของทุกๆ A เสร็จแล้วหารเอาเศษด้วย 65521 จึงได้ว่า
B=((1+D1)+(1+D1+D2)+...+(1+D1+D2+...+Dn))%65521
ให้ D คือข้อมูลใดๆ โดยที่ D มีขนาด 8 บิต จะได้ว่า
0<=D<=255
ให้ n คือความยาวของข้อมูล จะได้ว่า
n>=0
เมื่อนำมาเขียนเป็นโค้ด(ระดับประถม)จะได้ว่า
uint32_t Adler32(uint8_t *D,size_t n)
{
uint32_t A=1,B=0;
for(size_t i=0;i<n;++i)
{
A=(A+D[i])%65521;
B=(B+A)%65521;
}
return (B*2^16)+A;
}
{
uint32_t A=1,B=0;
for(size_t i=0;i<n;++i)
{
A=(A+D[i])%65521;
B=(B+A)%65521;
}
return (B*2^16)+A;
}
ส่วนอันนี้โค้ดระดับมหา'ลัย(หรือสูงกว่าู^^)
*ผมเปลี่ยนชื่อตัวแปรเพื่อให้พ้องกับคำจำกัดความข้างต้น
/* adler32.c -- compute the Adler-32 checksum of a data stream
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* @(#) $Id$ */
#include "zlib.h"
#define BASE 65521L /* largest prime smaller than 65536 */
#define NMAX 5552
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
#define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
#define DO16(buf) DO8(buf,0); DO8(buf,8);
/* ========================================================================= */
uint32_t ZEXPORT adler32(uint32_t C, uint8_t *D, size_t n)
{
uint32_t A = C & 0xffff;
uint32_t B = (C >> 16) & 0xffff;
size_t k;
if (D == Z_NULL) return 1L;
while (n > 0)
{
k = n < NMAX ? n : NMAX;
n -= k;
while (k >= 16)
{
DO16(D);
D += 16;
k -= 16;
}
if (k != 0)
{
do
{
A += *buf++;
B += A;
} while (--k);
}
A %= BASE;
B %= BASE;
}
return (B << 16) | A;
}
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* @(#) $Id$ */
#include "zlib.h"
#define BASE 65521L /* largest prime smaller than 65536 */
#define NMAX 5552
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
#define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
#define DO16(buf) DO8(buf,0); DO8(buf,8);
/* ========================================================================= */
uint32_t ZEXPORT adler32(uint32_t C, uint8_t *D, size_t n)
{
uint32_t A = C & 0xffff;
uint32_t B = (C >> 16) & 0xffff;
size_t k;
if (D == Z_NULL) return 1L;
while (n > 0)
{
k = n < NMAX ? n : NMAX;
n -= k;
while (k >= 16)
{
DO16(D);
D += 16;
k -= 16;
}
if (k != 0)
{
do
{
A += *buf++;
B += A;
} while (--k);
}
A %= BASE;
B %= BASE;
}
return (B << 16) | A;
}
หากใครถลำอ่านมาถึงตรงนี้ ขอบอกว่าความมันยังไม่เกิด
สำหรับผม ความมัน มันอยู่ที่ จากประถม มันไปมหา'ลัย ได้อย่างไร
เช่นว่า 5552 มันมาได้อย่างไร แล้วมาทำไม เพื่ออะไร
ไว้โอกาสหน้าจะมาเล่าให้ฟัง ช้าเร็ว แล้วแต่อารมณ์
*ผิดพลาด ตกหล่น ตรงไหน โปรดท้วงติงด้วยนะ เผื่อตาลาย
