chunker

package module
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 20, 2026 License: BSD-2-Clause Imports: 8 Imported by: 72

README

GoDoc Build Status

The package chunker implements content-defined-chunking (CDC) based on a rolling Rabin Hash. The library is part of the restic backup program.

An introduction to Content Defined Chunking can be found in the restic blog post Foundation - Introducing Content Defined Chunking (CDC).

You can find the API documentation at https://godoc.org/github.com/restic/chunker

Documentation

Overview

Package chunker implements Content Defined Chunking (CDC) based on a rolling Rabin Checksum.

Choosing a Random Irreducible Polynomial

The function RandomPolynomial() returns a new random polynomial of degree 53 for use with the chunker. The degree 53 is chosen because it is the largest prime below 64-8 = 56, so that the top 8 bits of an uint64 can be used for optimising calculations in the chunker.

A random polynomial is chosen selecting 64 random bits, masking away bits 64..54 and setting bit 53 to one (otherwise the polynomial is not of the desired degree) and bit 0 to one (otherwise the polynomial is trivially reducible), so that 51 bits are chosen at random.

This process is repeated until Irreducible() returns true, then this polynomials is returned. If this doesn't happen after 1 million tries, the function returns an error. The probability for selecting an irreducible polynomial at random is about 7.5% ( (2^53-2)/53 / 2^51), so the probability that no irreducible polynomial has been found after 100 tries is lower than 0.04%.

Verifying Irreducible Polynomials

During development the results have been verified using the computational discrete algebra system GAP, which can be obtained from the website at http://www.gap-system.org/.

For filtering a given list of polynomials in hexadecimal coefficient notation, the following script can be used: 

# create x over F_2 = GF(2)
x := Indeterminate(GF(2), "x");

# test if polynomial is irreducible, i.e. the number of factors is one
IrredPoly := function (poly)
	return (Length(Factors(poly)) = 1);
end;;

# create a polynomial in x from the hexadecimal representation of the
# coefficients
Hex2Poly := function (s)
	return ValuePol(CoefficientsQadic(IntHexString(s), 2), x);
end;;

# list of candidates, in hex
candidates := [ "3DA3358B4DC173" ];

# create real polynomials
L := List(candidates, Hex2Poly);

# filter and display the list of irreducible polynomials contained in L
Display(Filtered(L, x -> (IrredPoly(x))));

All irreducible polynomials from the list are written to the output.

Background Literature

An introduction to Rabin Fingerprints/Checksums can be found in the following articles:

Michael O. Rabin (1981): "Fingerprinting by Random Polynomials" http://www.xmailserver.org/rabin.pdf

Ross N. Williams (1993): "A Painless Guide to CRC Error Detection Algorithms" http://www.zlib.net/crc_v3.txt

Andrei Z. Broder (1993): "Some Applications of Rabin's Fingerprinting Method" http://www.xmailserver.org/rabin_apps.pdf

Shuhong Gao and Daniel Panario (1997): "Tests and Constructions of Irreducible Polynomials over Finite Fields" http://www.math.clemson.edu/~sgao/papers/GP97a.pdf

Andrew Kadatch, Bob Jenkins (2007): "Everything we know about CRC but afraid to forget" http://crcutil.googlecode.com/files/crc-doc.1.0.pdf

Index

Examples

Constants

View Source 
const (

	// MinSize is the default minimal size of a chunk.
	MinSize = 512 * kiB
	// MaxSize is the default maximal size of a chunk.
	MaxSize = 8 * miB
)

Variables

This section is empty.

Functions

func WithAverageBits added in v0.5.0 

func WithAverageBits(averageBits int) option

WithAverageBits allows to control the frequency of chunk discovery: the lower averageBits, the higher amount of chunks will be identified. The default value is 20 bits, so chunks will be of 1MiB size on average.

func WithBaseAverageBits added in v0.5.0 

func WithBaseAverageBits(averageBits int) baseOption

WithAverageBits allows to control the frequency of chunk discovery: the lower averageBits, the higher amount of chunks will be identified. The default value is 20 bits, so chunks will be of 1MiB size on average.

func WithBaseBoundaries added in v0.5.0 

func WithBaseBoundaries(min, max uint) baseOption

WithBoundaries allows to set custom min and max size boundaries.

func WithBoundaries added in v0.5.0 

func WithBoundaries(min, max uint) option

WithBoundaries allows to set custom min and max size boundaries.

func WithBuffer added in v0.5.0 

func WithBuffer(buf []byte) option

WithBuffer allows to set custom buffer for chunker.

Types

type BaseChunker added in v0.5.0 

type BaseChunker struct {
	// contains filtered or unexported fields
}

Chunker splits content with Rabin Fingerprints.

func NewBase added in v0.5.0 

func NewBase(pol Pol, opts ...baseOption) *BaseChunker

func (*BaseChunker) NextSplitPoint added in v0.5.0 

func (c *BaseChunker) NextSplitPoint(buf []byte) int

NextSplitPoint scans buf for a chunk boundary. Returns index before which to split buf, or -1 if no boundary found in this buffer. This operation is stateful. All buffers passed to it until a split point is found then form a single chunk.

func (*BaseChunker) Reset added in v0.5.0 

func (c *BaseChunker) Reset(pol Pol, opts ...baseOption)

Reset reinitializes the chunker with a new reader, polynomial, and options.

type Chunk 

type Chunk struct {
	Start  uint
	Length uint
	Cut    uint64
	Data   []byte
}

Chunk is one content-dependent chunk of bytes whose end was cut when the Rabin Fingerprint had the value stored in Cut.

type Chunker 

type Chunker struct {
	BaseChunker
	// contains filtered or unexported fields
}

Chunker splits content with Rabin Fingerprints.

Example 
package main

import (
	"bytes"
	"crypto/sha256"
	"fmt"
	"io"
	"math/rand"

	"github.com/restic/chunker"
)

func main() {
	// generate 32MiB of deterministic pseudo-random data
	rng := rand.New(rand.NewSource(23))
	data := make([]byte, 32*1024*1024)

	_, err := rng.Read(data)
	if err != nil {
		panic(err)
	}

	// create a chunker
	chnkr := chunker.New(bytes.NewReader(data), chunker.Pol(0x3DA3358B4DC173))

	// reuse this buffer
	buf := make([]byte, 8*1024*1024)

	for i := 0; i < 5; i++ {
		chunk, err := chnkr.Next(buf)
		if err == io.EOF {
			break
		}

		if err != nil {
			panic(err)
		}

		fmt.Printf("%d %02x\n", chunk.Length, sha256.Sum256(chunk.Data))
	}

}

Output:
1015370 615e8851030f318751f3c8baf8fbfa9958e2dd7f25dc1a87dcf6d6f79d1f1a9f
1276199 f1cb038c558d3a2093049815cc45f80cd367712634a28f6dd36642f905d35c37
1124437 a8e19dcd4224b58eb2b480ae42bb1a4a3b0c91c074f4745dbe3f8e4ec1a926e7
3580969 2b3a3fe65ce9d689599c3b26375c40c22955bf92b170b24258e54dee91e3c2af
3709129 47672502d75db244cb3dc3098eed87ffd537c9f0d66fb82a0198b6f6994409f2

func New 

func New(rd io.Reader, pol Pol, opts ...option) *Chunker

New returns a new Chunker based on polynomial p that reads from rd. Chunker behavior can be customized by passing options, see With* functions.

func NewWithBoundaries deprecated added in v0.2.0 

func NewWithBoundaries(rd io.Reader, pol Pol, min, max uint) *Chunker

NewWithBoundaries returns a new Chunker based on polynomial p that reads from rd and custom min and max size boundaries.

Deprecated: NewWithBoundaries uses should be replaced by New(rd, pol, WithBoundaries(min, max)).

func (*Chunker) Next 

func (c *Chunker) Next(data []byte) (Chunk, error)

Next returns the position and length of the next chunk of data. If an error occurs while reading, the error is returned. Afterwards, the state of the current chunk is undefined. When the last chunk has been returned, all subsequent calls yield an io.EOF error.

func (*Chunker) Reset 

func (c *Chunker) Reset(rd io.Reader, pol Pol, opts ...option)

Reset reinitializes the chunker with a new reader, polynomial, and options.

func (*Chunker) ResetWithBoundaries deprecated added in v0.2.0 

func (c *Chunker) ResetWithBoundaries(rd io.Reader, pol Pol, min, max uint)

Deprecated: ResetWithBoundaries uses should be replaced by Reset(rd, pol, WithBoundaries(min, max)).

func (*Chunker) SetAverageBits deprecated added in v0.2.0 

func (c *Chunker) SetAverageBits(averageBits int)

SetAverageBits allows to control the frequency of chunk discovery: the lower averageBits, the higher amount of chunks will be identified. The default value is 20 bits, so chunks will be of 1MiB size on average.

Deprecated: SetAverageBits uses should be replaced by New(rd, pol, WithAverageBits(averageBits)).

type Pol 

type Pol uint64

Pol is a polynomial from F_2[X].

func DerivePolynomial 

func DerivePolynomial(source io.Reader) (Pol, error)

DerivePolynomial returns an irreducible polynomial of degree 53 (largest prime number below 64-8) by reading bytes from source. There are (2^53-2/53) irreducible polynomials of degree 53 in F_2[X], c.f. Michael O. Rabin (1981): "Fingerprinting by Random Polynomials", page 4. If no polynomial could be found in one million tries, an error is returned.

func RandomPolynomial 

func RandomPolynomial() (Pol, error)

RandomPolynomial returns a new random irreducible polynomial of degree 53 using the default System CSPRNG as source. It is equivalent to calling DerivePolynomial(rand.Reader).

func (Pol) Add 

func (x Pol) Add(y Pol) Pol

Add returns x+y.

func (Pol) Deg 

func (x Pol) Deg() int

Deg returns the degree of the polynomial x. If x is zero, -1 is returned.

func (Pol) Div 

func (x Pol) Div(d Pol) Pol

Div returns the integer division result x / d.

func (Pol) DivMod 

func (x Pol) DivMod(d Pol) (Pol, Pol)

DivMod returns x / d = q, and remainder r, see https://en.wikipedia.org/wiki/Division_algorithm

func (Pol) Expand 

func (x Pol) Expand() string

Expand returns the string representation of the polynomial x.

func (Pol) GCD 

func (x Pol) GCD(f Pol) Pol

GCD computes the Greatest Common Divisor x and f.

func (Pol) Irreducible 

func (x Pol) Irreducible() bool

Irreducible returns true iff x is irreducible over F_2. This function uses Ben Or's reducibility test.

For details see "Tests and Constructions of Irreducible Polynomials over Finite Fields".

func (Pol) MarshalJSON 

func (x Pol) MarshalJSON() ([]byte, error)

MarshalJSON returns the JSON representation of the Pol.

func (Pol) Mod 

func (x Pol) Mod(d Pol) Pol

Mod returns the remainder of x / d

func (Pol) Mul 

func (x Pol) Mul(y Pol) Pol

Mul returns x*y. When an overflow occurs, Mul panics.

func (Pol) MulMod 

func (x Pol) MulMod(f, g Pol) Pol

MulMod computes x*f mod g

func (Pol) String 

func (x Pol) String() string

String returns the coefficients in hex.

func (*Pol) UnmarshalJSON 

func (x *Pol) UnmarshalJSON(data []byte) error

UnmarshalJSON parses a Pol from the JSON data.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.