rsync-এর Rolling Checksum Algorithm এবং Modulo Trap

Adler32-এর "Rolling" Part Mathematically Brilliant কারণ এটা O(1) Time-এ New Hash Calculate করতে পারে শুধু Window থেকে Leave করা Byte Subtract করে আর New Byte Add করে। Magic Number হলো 65521 (2^16-এর নিচে Largest Prime), যেটা Sums a আর b-কে 16 Bits-এর মধ্যে রাখে।

Math-টা Go-তে Translate করলে এমন দেখায়:

const mod = 65521

func (r *RollSum) Rotate(b byte) {
    if len(r.window) == 0 {
        return
    }

    leave, enter := r.circle(b)
    r.a = (((r.a + enter - leave) % mod) + mod) % mod
    r.b = (((r.b - r.windowLen*leave - 1 + r.a) % mod) + mod) % mod
}const mod = 65521

func (r *RollSum) Rotate(b byte) {
    if len(r.window) == 0 {
        return
    }

    leave, enter := r.circle(b)
    r.a = (((r.a + enter - leave) % mod) + mod) % mod
    r.b = (((r.b - r.windowLen*leave - 1 + r.a) % mod) + mod) % mod
}

এখানেই এক ঘন্টা Loss করেছিলাম Completely Avoidable Bug-এ। Go-তে (আর C-তে, এবং অনেক অন্যতে), % Operator আসলে Mathematical Modulo নয়—এটা Remainder Operator। Dividend Negative হলে leave Byte Subtract করার পর, % Negative Value Return করতে পারে।

True Mathematical Modulo পেতে ((n % mod) + mod) % mod Pattern Use করতে হয়েছিল। এটা Ugly, Verbose Little Detail যেটা Completely Checksum Ruin করে দেয় ভুললে। Assumed করেছিলাম Standard Library hash/adler32-এর কিছু Magic Helper থাকবে, কিন্তু এটা Rolling Out of the box করে না, তাই নিজেই করতে হলো।

Manual Window Management

Actually Hash Roll করতে Window-এর কোন Byte বের হয়ে যাচ্ছে জানতে হয়। এটা Simple Slice Use করে Implement করেছিলাম:

func (r *RollSum) circle(b byte) (leave, enter uint32) {
    r.removed = r.window[0]
    r.window = append(r.window[1:], b)
    enter = uint32(b)
    leave = uint32(r.removed)
    return
}func (r *RollSum) circle(b byte) (leave, enter uint32) {
    r.removed = r.window[0]
    r.window = append(r.window[1:], b)
    enter = uint32(b)
    leave = uint32(r.removed)
    return
}

এটা কাজ করে, কিন্তু Performance-এর জন্য Honestly Terrible। প্রতিটা Byte-এ append আর Slice Shift করলে Garbage Collector Field Day পাবে। Toy Weekend Project-এর জন্য Slice Readability-এর জন্য Fine, কিন্তু যদি Actually Gigabytes of Data Process করতে চাইতাম, পুরোটা Re-write করতে হতো Pre-allocated Circular Buffer Use করে।

Go-এর Standard Library নিয়ে আমার একটা বড় কমপ্লেইন আছে। কেন তারা hash/adler32 এ একটা সিম্পল Roll() মেথড রাখল না? rsync এর মতো Tools এত জনপ্রিয়, অথচ এই বেসিক Algorithm-টা স্ক্র্যাচ থেকে লিখতে হয়।

Proving ভাঙিনি

Math এতো Finicky বলে, Go-এর Standard (Non-rolling) hash/adler32 Implementation-এর Against-এ Battery of Tests লিখতে হয়েছিল শুধু Prove করতে আমার Math Hallucinate করছে না।

package rollsum

import (
	"fmt"
	"hash/adler32"
	"testing"
	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func classic(data []byte) uint32 {
	a := adler32.New()
	a.Write(data)
	return a.Sum32()
}

func TestRollInAndOut(t *testing.T) {
	a := []byte("Adler-32 is a checksum")
	roll := New(1 << 16)
	for _, x := range a {
		roll.In(x)
	}
	require.Equal(t, classic(a), roll.Sum32())

	// Testing the actual roll
	roll.Out()
	a = a[1:]
	assert.Equal(t, classic(a), roll.Sum32())
}package rollsum

import (
	"fmt"
	"hash/adler32"
	"testing"
	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func classic(data []byte) uint32 {
	a := adler32.New()
	a.Write(data)
	return a.Sum32()
}

func TestRollInAndOut(t *testing.T) {
	a := []byte("Adler-32 is a checksum")
	roll := New(1 << 16)
	for _, x := range a {
		roll.In(x)
	}
	require.Equal(t, classic(a), roll.Sum32())

	// Testing the actual roll
	roll.Out()
	a = a[1:]
	assert.Equal(t, classic(a), roll.Sum32())
}