librsync  2.3.4
Data Structures | Macros | Typedefs | Functions
rabinkarp.h File Reference

The rabinkarp class implementation of the RabinKarp rollsum. More...

Include dependency graph for rabinkarp.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  rabinkarp
 The rabinkarp_t state type. More...


#define RABINKARP_SEED   1
 The RabinKarp seed value. More...
#define RABINKARP_MULT   0x08104225U
 The RabinKarp multiplier. More...
#define RABINKARP_INVM   0x98f009adU
 The RabinKarp inverse multiplier. More...
#define RABINKARP_ADJ   0x08104224U
 The RabinKarp seed adjustment. More...


typedef struct rabinkarp rabinkarp_t
 The rabinkarp_t state type. More...


static void rabinkarp_init (rabinkarp_t *sum)
void rabinkarp_update (rabinkarp_t *sum, const unsigned char *buf, size_t len)
static void rabinkarp_rotate (rabinkarp_t *sum, unsigned char out, unsigned char in)
static void rabinkarp_rollin (rabinkarp_t *sum, unsigned char in)
static void rabinkarp_rollout (rabinkarp_t *sum, unsigned char out)
static uint32_t rabinkarp_digest (rabinkarp_t *sum)

Detailed Description

The rabinkarp class implementation of the RabinKarp rollsum.

Definition in file rabinkarp.h.

Macro Definition Documentation


#define RABINKARP_SEED   1

The RabinKarp seed value.

The seed ensures different length zero blocks have different hashes. It effectively encodes the length into the hash.

Definition at line 34 of file rabinkarp.h.


#define RABINKARP_MULT   0x08104225U

The RabinKarp multiplier.

This multiplier has a bit pattern of 1's getting sparser with significance, is the product of 2 large primes, and matches the characterstics for a good LCG multiplier.

Definition at line 41 of file rabinkarp.h.


#define RABINKARP_INVM   0x98f009adU

The RabinKarp inverse multiplier.

This is the inverse of RABINKARP_MULT modular 2^32. Multiplying by this is equivalent to dividing by RABINKARP_MULT.

Definition at line 47 of file rabinkarp.h.


#define RABINKARP_ADJ   0x08104224U

The RabinKarp seed adjustment.

This is a factor used to adjust for the seed when rolling out values. It's equal to; (RABINKARP_MULT - 1) * RABINKARP_SEED

Definition at line 53 of file rabinkarp.h.

Typedef Documentation

◆ rabinkarp_t

typedef struct rabinkarp rabinkarp_t

The rabinkarp_t state type.

Function Documentation

◆ rabinkarp_init()

static void rabinkarp_init ( rabinkarp_t sum)

Definition at line 62 of file rabinkarp.h.

◆ rabinkarp_update()

void rabinkarp_update ( rabinkarp_t sum,
const unsigned char *  buf,
size_t  len 

Definition at line 88 of file rabinkarp.c.

◆ rabinkarp_rotate()

static void rabinkarp_rotate ( rabinkarp_t sum,
unsigned char  out,
unsigned char  in 

Definition at line 71 of file rabinkarp.h.

◆ rabinkarp_rollin()

static void rabinkarp_rollin ( rabinkarp_t sum,
unsigned char  in 

Definition at line 78 of file rabinkarp.h.

◆ rabinkarp_rollout()

static void rabinkarp_rollout ( rabinkarp_t sum,
unsigned char  out 

Definition at line 85 of file rabinkarp.h.

◆ rabinkarp_digest()

static uint32_t rabinkarp_digest ( rabinkarp_t sum)

Definition at line 92 of file rabinkarp.h.