// Roller32.h

#ifndef Roller32h
#define Roller32h

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

/*<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Fast Rolling Checksum <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

The following algorithm is from a program which compares blocks of data using this very fast, rollable checksum.
Blocks of data are compared using their checksums.
This is a weak checksum and is used as a first pass before using a stronger checksum to ensure that any two blocks are identical.
Having got the checksum of a block of data, you can scroll the block one Byte by telling the Roller what character to remove from the beginning of the block and what character to append to the end (if any).
The data block does not need rescanning - the checksum updates itself using just the two changed Bytes.
As with Adler32, it gives better results the larger the block size and 128 Bytes is a good minimum.

Here's an example:
All you know of the "OtherFile" is a Roller (weak) checksum and an MD5 (strong) checksum for each 512 Byte block...
    CFile File;
    if(!File.Open(Path, CFile::modeRead)) return;
    BYTE Buffer[512];
    CRoller32 Roller;
    DWORD Bytes;
    do {
      Bytes=File.Read(Buffer, sizeof(Buffer));
      Roller.Set(Buffer, Bytes);
      while(Bytes && !OtherFile.Find(Roller.Get()) { // Try to find a block with this checksum
        char Old=Buffer[0]; //If we didn't find a matching block, move 1 Byte and retry
        memcpy(Buffer, Buffer+1, --Bytes); // Scroll the Buffer 1 Byte:
        Bytes+=File.Read(Buffer+Bytes, 1);
        Roller.Roll(Old, Bytes, Bytes==sizeof(Buffer), Buffer[Bytes-1]);
      }
      ... // Either finished the file (Bytes==0) or found a block.
    }while(Bytes);
*/

class CRoller32 {
  DWORD s1,s2;
public:
  CRoller32() {}
  CRoller32(const BYTE* Buffer, DWORD Bytes) {Set(Buffer, Bytes);}
  virtual ~CRoller32() {}
  DWORD Get() const {return (s1 & 0xFFFF)+(s2<<16);}
  void Set(const BYTE* Buffer, DWORD Bytes) {for(DWORD i=s1=s2=0; i++<Bytes; s2+=s1+=13+*Buffer++);}
  void Set(DWORD Roller) {
    s1=Roller & 0xFFFF;
    s2=Roller>>16;
  }
  void Trim(BYTE Old, DWORD Bytes) { // Bytes is Current Length (before Trim).
    s1-=Old+=13;
    s2-=Old*Bytes;
  }
  void Append(BYTE New) {s2+=s1+=13+New;}
  void Roll(BYTE Old, DWORD Bytes, bool append=false, BYTE New=0) { // Bytes is Current Length (before Trim).
    Trim(Old, Bytes);
    if(append) Append(New);
  }
};

#ifdef Assert // Run tests if Tester.h is included in stdafx.h
namespace { // namespace prevents multiple definitions if instantiating in the header like this:
  struct Roller32Tester : Tester, CRoller32 {
    Roller32Tester() {
      Set((BYTE*)"resume",6);
      Assert(Get()==0x0A2002DF);
      Set((BYTE*)"resumé",6);
      Assert(Get()==0x0AA40363);
      Set((BYTE*)"aaaa",4);
      Assert(Get()==0x044C01B8);
      Roll('a',4,true,'a'); // Add and remove the same data: the checksum shouldn't change:
      Assert(Get()==0x044C01B8);
      Roll('a',4,true,'b');  // Roll the buffer to "aaab"
      Assert(Get()==0x044D01B9);
      Set((BYTE*)"aaab",4);  // ...Make sure that's the same as if initially set to "aaab"
      Assert(Get()==0x044D01B9);
      Roll('a',4);  // Roll the buffer to "aab" (just trim the first Byte)
      Assert(Get()==0x0295014B);
      Set((BYTE*)"aab",3);  // ...Make sure that's the same as if initially set to "aab"
      Assert(Get()==0x0295014B);
      Roll('a',3);  // Roll the buffer to "ab" (just trim the first Byte)
      Assert(Get()==0x014B00DD);
      Set((BYTE*)"ab",2);  // ...Make sure that's the same as if initially set to "ab"
      Assert(Get()==0x014B00DD);
    }
  } _Roller32Tester;
}
#endif // def Assert

#endif //ndef Roller32h