Rolling Checksums: rsync-এর Adler32 নিয়ে একটা Weekend

rsync-এর rolling checksum অ্যালগরিদম এবং 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
}

...আর এখানেই এক ঘন্টা 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
}

এটা কাজ করে, কিন্তু 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-এর স্ট্যান্ডার্ড লাইব্রেরি নিয়ে আমার একটা বড় কমপ্লেইন আছে। কেন তারা hash/adler32 এ একটা সিম্পল Roll() মেথড রাখল না? rsync এর মত টুলস এত জনপ্রিয়, অথচ এই বেসিক অ্যালগরিদমটা স্ক্র্যাচ থেকে লিখতে হয়।

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())
}

Meta Description: rsync-এর rolling checksum অ্যালগরিদম কিভাবে কাজ করে? এই উইকেন্ড প্রজেক্টে শিখুন Adler32 রোলিং চেকসাম ইমপ্লিমেন্টেশন এবং এর পেছনের ম্যাথমেটিক্যাল চ্যালেঞ্জগুলো।