rollinghash

README

This package contains several various rolling checksums for you to play with crazy ideas. The API design philosophy was to stick as closely as possible to the interface provided by the builtin hash package, while providing simultaneously the highest speed and simplicity.

The Hash32 and Hash64 interfaces both implement the builtin Hash32 and Hash64, so that you can use them as drop in replacements. On top of the builtin methods, these interfaces also implement Roller, which consists in the single method Roll(b byte), designed to update the rolling checksum with the byte entering the rolling window.

The rolling window MUST be initialized by calling Write first (which saves a copy). Several calls to Write will overwrite this window every time. The byte leaving the rolling window is inferred from the internal copy of the rolling window, which is updated with every call to Roll.

Be aware that Roll never fails: whenever no Rolling window has been initialized, the implementation assumes a rolling window of 1 byte, initialized with the null byte. As a consequence, rolling an empty window returns an incorrect answer. In previous versions of this library, Roll would return an error for this particular case. This change was made in the interest of speed, so that we don't have to check whether a window exists for every call, sparing an operation that is useless when the hash is correctly used, in a function likely to be called millions of times per second.

In terms of LICENSING, be aware that the RabinKarp64 subpackage has a different license from the rest of this package (BSD 2-clause "Simplified" License)

Documentation

Overview

Package rollinghash implements rolling versions of some hashes

Example

package main

import (
	"hash"
	"log"

	_adler32 "github.com/chmduquesne/rollinghash/adler32"
)

func main() {
	s := []byte("The quick brown fox jumps over the lazy dog")

	// You can substitute _adler32 for any other subpackage
	classic := hash.Hash32(_adler32.New())
	rolling := _adler32.New()

	// Window len
	n := 16

	// You MUST load an initial window into the rolling hash before being
	// able to roll bytes
	rolling.Write(s[:n])

	// Roll it and compare the result with full re-calculus every time
	for i := n; i < len(s); i++ {

		// Reset and write the window in classic
		classic.Reset()
		classic.Write(s[i-n+1 : i+1])

		// Roll the incoming byte in rolling
		rolling.Roll(s[i])

		// Compare the hashes
		if classic.Sum32() != rolling.Sum32() {
			log.Fatalf("%v: expected %s, got %s",
				s[i-n+1:i+1], classic.Sum32(), rolling.Sum32())
		}
	}

}

Index

• Constants
• type Hash
• type Hash32
• type Hash64
• type Roller

Examples

• Package

Constants

const DefaultWindowCap = 64

DefaultWindowCap is the default capacity of the internal window of a new Hash.

Types

type Hash

type Hash interface {
	hash.Hash
	Roller
}

rollinghash.Hash extends hash.Hash by adding the method Roll. A rollinghash.Hash can be updated byte by byte, by specifying which byte enters the window.

type Hash32

type Hash32 interface {
	hash.Hash32
	Roller
}

rollinghash.Hash32 extends hash.Hash by adding the method Roll. A rollinghash.Hash32 can be updated byte by byte, by specifying which byte enters the window.

type Hash64

type Hash64 interface {
	hash.Hash64
	Roller
}

rollinghash.Hash64 extends hash.Hash by adding the method Roll. A rollinghash.Hash64 can be updated byte by byte, by specifying which byte enters the window.

type Roller

type Roller interface {
	Roll(b byte)
}

A Roller is a type that has the method Roll. Roll updates the hash of a rolling window from just the entering byte. You MUST call Write() BEFORE using this method and provide it with an initial window of size at least 1 byte. You can then call this method for every new byte entering the window. The byte leaving the window is automatically computed from a copy of the window internally kept in the checksum. This window is updated along with the internal state of the checksum every time Roll() is called.