\doxysubsection{rabinkarp.\+h}
\label{rabinkarp_8h_source}\index{rabinkarp.h@{rabinkarp.h}}
\mbox{\hyperlink{rabinkarp_8h}{Go to the documentation of this file.}}
\begin{DoxyCode}{0}
\DoxyCodeLine{00001 \textcolor{comment}{/*= -\/*-\/ c-\/basic-\/offset: 4; indent-\/tabs-\/mode: nil; -\/*-\/}}
\DoxyCodeLine{00002 \textcolor{comment}{ *}}
\DoxyCodeLine{00003 \textcolor{comment}{ * rabinkarp -\/-\/ The RabinKarp rolling checksum.}}
\DoxyCodeLine{00004 \textcolor{comment}{ *}}
\DoxyCodeLine{00005 \textcolor{comment}{ * Copyright (C) 2019 by Donovan Baarda <abo@minkirri.apana.org.au>}}
\DoxyCodeLine{00006 \textcolor{comment}{ *}}
\DoxyCodeLine{00007 \textcolor{comment}{ * This program is free software; you can redistribute it and/or modify}}
\DoxyCodeLine{00008 \textcolor{comment}{ * it under the terms of the GNU Lesser General Public License as published by}}
\DoxyCodeLine{00009 \textcolor{comment}{ * the Free Software Foundation; either version 2.1 of the License, or}}
\DoxyCodeLine{00010 \textcolor{comment}{ * (at your option) any later version.}}
\DoxyCodeLine{00011 \textcolor{comment}{ *}}
\DoxyCodeLine{00012 \textcolor{comment}{ * This program is distributed in the hope that it will be useful,}}
\DoxyCodeLine{00013 \textcolor{comment}{ * but WITHOUT ANY WARRANTY; without even the implied warranty of}}
\DoxyCodeLine{00014 \textcolor{comment}{ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the}}
\DoxyCodeLine{00015 \textcolor{comment}{ * GNU Lesser General Public License for more details.}}
\DoxyCodeLine{00016 \textcolor{comment}{ *}}
\DoxyCodeLine{00017 \textcolor{comment}{ * You should have received a copy of the GNU Lesser General Public License}}
\DoxyCodeLine{00018 \textcolor{comment}{ * along with this program; if not, write to the Free Software}}
\DoxyCodeLine{00019 \textcolor{comment}{ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.}}
\DoxyCodeLine{00020 \textcolor{comment}{ */}}
\DoxyCodeLine{00021 \textcolor{comment}{}}
\DoxyCodeLine{00022 \textcolor{comment}{/** \(\backslash\)file rabinkarp.h}}
\DoxyCodeLine{00023 \textcolor{comment}{ * The rabinkarp class implementation of the RabinKarp rollsum. */}}
\DoxyCodeLine{00024 \textcolor{preprocessor}{\#ifndef RABINKARP\_H}}
\DoxyCodeLine{00025 \textcolor{preprocessor}{\#  define RABINKARP\_H}}
\DoxyCodeLine{00026 }
\DoxyCodeLine{00027 \textcolor{preprocessor}{\#  include <stddef.h>}}
\DoxyCodeLine{00028 \textcolor{preprocessor}{\#  include <stdint.h>}}
\DoxyCodeLine{00029 \textcolor{comment}{}}
\DoxyCodeLine{00030 \textcolor{comment}{/** The RabinKarp seed value.}}
\DoxyCodeLine{00031 \textcolor{comment}{ *}}
\DoxyCodeLine{00032 \textcolor{comment}{ * The seed ensures different length zero blocks have different hashes. It}}
\DoxyCodeLine{00033 \textcolor{comment}{ * effectively encodes the length into the hash. */}}
\DoxyCodeLine{00034 \textcolor{preprocessor}{\#  define RABINKARP\_SEED 1}}
\DoxyCodeLine{00035 \textcolor{comment}{}}
\DoxyCodeLine{00036 \textcolor{comment}{/** The RabinKarp multiplier.}}
\DoxyCodeLine{00037 \textcolor{comment}{ *}}
\DoxyCodeLine{00038 \textcolor{comment}{ * This multiplier has a bit pattern of 1's getting sparser with significance,}}
\DoxyCodeLine{00039 \textcolor{comment}{ * is the product of 2 large primes, and matches the characterstics for a good}}
\DoxyCodeLine{00040 \textcolor{comment}{ * LCG multiplier. */}}
\DoxyCodeLine{00041 \textcolor{preprocessor}{\#  define RABINKARP\_MULT 0x08104225U}}
\DoxyCodeLine{00042 \textcolor{comment}{}}
\DoxyCodeLine{00043 \textcolor{comment}{/** The RabinKarp inverse multiplier.}}
\DoxyCodeLine{00044 \textcolor{comment}{ *}}
\DoxyCodeLine{00045 \textcolor{comment}{ * This is the inverse of RABINKARP\_MULT modular 2\string^32. Multiplying by this is}}
\DoxyCodeLine{00046 \textcolor{comment}{ * equivalent to dividing by RABINKARP\_MULT. */}}
\DoxyCodeLine{00047 \textcolor{preprocessor}{\#  define RABINKARP\_INVM 0x98f009adU}}
\DoxyCodeLine{00048 \textcolor{comment}{}}
\DoxyCodeLine{00049 \textcolor{comment}{/** The RabinKarp seed adjustment.}}
\DoxyCodeLine{00050 \textcolor{comment}{ *}}
\DoxyCodeLine{00051 \textcolor{comment}{ * This is a factor used to adjust for the seed when rolling out values. It's}}
\DoxyCodeLine{00052 \textcolor{comment}{ * equal to; (RABINKARP\_MULT -\/ 1) * RABINKARP\_SEED */}}
\DoxyCodeLine{00053 \textcolor{preprocessor}{\#  define RABINKARP\_ADJ 0x08104224U}}
\DoxyCodeLine{00054 \textcolor{comment}{}}
\DoxyCodeLine{00055 \textcolor{comment}{/** The rabinkarp\_t state type. */}}
\DoxyCodeLine{00056 \textcolor{keyword}{typedef} \textcolor{keyword}{struct }rabinkarp \{}
\DoxyCodeLine{00057     \textcolor{keywordtype}{size\_t} count;               \textcolor{comment}{/**< Count of bytes included in sum. */}}
\DoxyCodeLine{00058     uint32\_t hash;              \textcolor{comment}{/**< The accumulated hash value. */}}
\DoxyCodeLine{00059     uint32\_t mult;              \textcolor{comment}{/**< The value of RABINKARP\_MULT\string^count. */}}
\DoxyCodeLine{00060 \} rabinkarp\_t;}
\DoxyCodeLine{00061 }
\DoxyCodeLine{00062 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rabinkarp\_init(rabinkarp\_t *sum)}
\DoxyCodeLine{00063 \{}
\DoxyCodeLine{00064     sum-\/>count = 0;}
\DoxyCodeLine{00065     sum-\/>hash = RABINKARP\_SEED;}
\DoxyCodeLine{00066     sum-\/>mult = 1;}
\DoxyCodeLine{00067 \}}
\DoxyCodeLine{00068 }
\DoxyCodeLine{00069 \textcolor{keywordtype}{void} rabinkarp\_update(rabinkarp\_t *sum, \textcolor{keyword}{const} \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} *buf, \textcolor{keywordtype}{size\_t} len);}
\DoxyCodeLine{00070 }
\DoxyCodeLine{00071 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rabinkarp\_rotate(rabinkarp\_t *sum, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} out,}
\DoxyCodeLine{00072                                     \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} in)}
\DoxyCodeLine{00073 \{}
\DoxyCodeLine{00074     sum-\/>hash =}
\DoxyCodeLine{00075         sum-\/>hash * RABINKARP\_MULT + in -\/ sum-\/>mult * (out + RABINKARP\_ADJ);}
\DoxyCodeLine{00076 \}}
\DoxyCodeLine{00077 }
\DoxyCodeLine{00078 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rabinkarp\_rollin(rabinkarp\_t *sum, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} in)}
\DoxyCodeLine{00079 \{}
\DoxyCodeLine{00080     sum-\/>hash = sum-\/>hash * RABINKARP\_MULT + in;}
\DoxyCodeLine{00081     sum-\/>count++;}
\DoxyCodeLine{00082     sum-\/>mult *= RABINKARP\_MULT;}
\DoxyCodeLine{00083 \}}
\DoxyCodeLine{00084 }
\DoxyCodeLine{00085 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} rabinkarp\_rollout(rabinkarp\_t *sum, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} out)}
\DoxyCodeLine{00086 \{}
\DoxyCodeLine{00087     sum-\/>count-\/-\/;}
\DoxyCodeLine{00088     sum-\/>mult *= RABINKARP\_INVM;}
\DoxyCodeLine{00089     sum-\/>hash -\/= sum-\/>mult * (out + RABINKARP\_ADJ);}
\DoxyCodeLine{00090 \}}
\DoxyCodeLine{00091 }
\DoxyCodeLine{00092 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t rabinkarp\_digest(rabinkarp\_t *sum)}
\DoxyCodeLine{00093 \{}
\DoxyCodeLine{00094     \textcolor{keywordflow}{return} sum-\/>hash;}
\DoxyCodeLine{00095 \}}
\DoxyCodeLine{00096 }
\DoxyCodeLine{00097 \textcolor{preprocessor}{\#endif                          }\textcolor{comment}{/* !RABINKARP\_H */}\textcolor{preprocessor}{}}

\end{DoxyCode}
