Блог

Я использую функцию adler32 из zlib для вычисления минимальной контрольной суммы фрагмента памяти x (длиной 4096). Все в порядке, но теперь я хотел бы выполнить переходящую контрольную сумму, если фрагменты из другого файла не совпадают. Однако я не уверен, как написать функцию, которая выполнит это для значения, возвращаемого adler32 в zlib. Итак, если контрольная сумма не совпадает, как мне вычислить переходящую контрольную сумму, используя исходную контрольную сумму, x 1 байт и x 4096 1? В основном пытаюсь создать реализацию rsync.

Pysync внедрил развертывание поверх zlib Adler32 следующим образом:

 _BASE=65521      # largest prime smaller than 65536
_NMAX=5552       # largest n such that 255n(n 1)/2   (n 1)(BASE-1) <= 2^32-1
_OFFS=1          # default initial s1 offset   
import zlib
class adler32:
    def __init__(self,data=''):
        value = zlib.adler32(data,_OFFS)
        self.s2, self.s1 = (value >> 16) amp; 0xffff, value amp; 0xffff
        self.count=len(data)
    def update(self,data):
        value = zlib.adler32(data, (self.s2<<16) | self.s1)
        self.s2, self.s1 = (value >> 16) amp; 0xffff, value amp; 0xffff
        self.count = self.count len(data)
    def rotate(self,x1,xn):
        x1,xn=ord(x1),ord(xn)
        self.s1=(self.s1 - x1   xn) % _BASE
        self.s2=(self.s2 - self.count*x1   self.s1 - _OFFS) % _BASE
    def digest(self):
        return (self.s2<<16) | self.s1
    def copy(self):
        n=adler32()
        n.count,n.s1,n.s2=self.count,self.s1,self.s2
        return n
  

Но, как заявил Питер, rsync использует Adler32 не напрямую, а его более быстрый вариант.

Код инструмента rsync немного сложен для чтения, но проверьте librsync. Это совершенно отдельный проект, и он намного более удобочитаем. Взгляните на rollsum.c и rollsum.h . Существует эффективная реализация варианта в макросах C:

 /* the Rollsum struct type*/
typedef struct _Rollsum {
    unsigned long count;               /* count of bytes included in sum */
    unsigned long s1;                  /* s1 part of sum */
    unsigned long s2;                  /* s2 part of sum */
} Rollsum;

#define ROLLSUM_CHAR_OFFSET 31

#define RollsumInit(sum) { 
    (sum)->count=(sum)->s1=(sum)->s2=0; 
}

#define RollsumRotate(sum,out,in) { 
    (sum)->s1  = (unsigned char)(in) - (unsigned char)(out); 
    (sum)->s2  = (sum)->s1 - (sum)->count*((unsigned char)(out) ROLLSUM_CHAR_OFFSET); 
}

#define RollsumRollin(sum,c) { 
    (sum)->s1  = ((unsigned char)(c) ROLLSUM_CHAR_OFFSET); 
    (sum)->s2  = (sum)->s1; 
    (sum)->count  ; 
}

#define RollsumRollout(sum,c) { 
    (sum)->s1 -= ((unsigned char)(c) ROLLSUM_CHAR_OFFSET); 
    (sum)->s2 -= (sum)->count*((unsigned char)(c) ROLLSUM_CHAR_OFFSET); 
    (sum)->count--; 
}

#define RollsumDigest(sum) (((sum)->s2 << 16) | ((sum)->s1 amp; 0xffff))