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...

Macros
#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...

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

Functions
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

RABINKARP_SEED

#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.

RABINKARP_MULT

#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.

RABINKARP_INVM

#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.

RABINKARP_ADJ

#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 )

inlinestatic

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  )

inlinestatic

Definition at line 71 of file rabinkarp.h.

rabinkarp_rollin()

static void rabinkarp_rollin ( rabinkarp_t *  sum, unsigned char  in  )

inlinestatic

Definition at line 78 of file rabinkarp.h.

rabinkarp_rollout()

static void rabinkarp_rollout ( rabinkarp_t *  sum, unsigned char  out  )

inlinestatic

Definition at line 85 of file rabinkarp.h.

rabinkarp_digest()

static uint32_t rabinkarp_digest ( rabinkarp_t *  sum )

inlinestatic

Definition at line 92 of file rabinkarp.h.