\doxysubsection{rabinkarp.\+c}
\label{rabinkarp_8c_source}\index{rabinkarp.c@{rabinkarp.c}}

\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{preprocessor}{\#include "{}config.h"{}}             \textcolor{comment}{/* IWYU pragma: keep */}}
\DoxyCodeLine{00022 \textcolor{preprocessor}{\#include "{}rabinkarp.h"{}}}
\DoxyCodeLine{00023 }
\DoxyCodeLine{00024 \textcolor{comment}{/* Constant for RABINKARP\_MULT\string^2. */}}
\DoxyCodeLine{00025 \textcolor{preprocessor}{\#define RABINKARP\_MULT2 0xa5b71959U}}
\DoxyCodeLine{00026 }
\DoxyCodeLine{00027 \textcolor{comment}{/* Macros for doing 16 bytes with 2 mults that can be done in parallel. Testing}}
\DoxyCodeLine{00028 \textcolor{comment}{   showed this as a performance sweet spot vs 16x1, 8x2, 4x4 1x16 alternative}}
\DoxyCodeLine{00029 \textcolor{comment}{   arrangements. */}}
\DoxyCodeLine{00030 \textcolor{preprocessor}{\#define PAR2X1(hash,buf,i) (RABINKARP\_MULT2*(hash) + \(\backslash\)}}
\DoxyCodeLine{00031 \textcolor{preprocessor}{                            RABINKARP\_MULT*buf[i] + \(\backslash\)}}
\DoxyCodeLine{00032 \textcolor{preprocessor}{                            buf[i+1])}}
\DoxyCodeLine{00033 \textcolor{preprocessor}{\#define PAR2X2(hash,buf,i) PAR2X1(PAR2X1(hash,buf,i),buf,i+2)}}
\DoxyCodeLine{00034 \textcolor{preprocessor}{\#define PAR2X4(hash,buf,i) PAR2X2(PAR2X2(hash,buf,i),buf,i+4)}}
\DoxyCodeLine{00035 \textcolor{preprocessor}{\#define PAR2X8(hash,buf) PAR2X4(PAR2X4(hash,buf,0),buf,8)}}
\DoxyCodeLine{00036 }
\DoxyCodeLine{00037 \textcolor{comment}{/* Table of RABINKARP\_MULT\string^(2\string^(i+1)) for power lookups. */}}
\DoxyCodeLine{00038 \textcolor{keyword}{const} \textcolor{keyword}{static} uint32\_t RABINKARP\_MULT\_POW2[32] = \{}
\DoxyCodeLine{00039     0x08104225U,}
\DoxyCodeLine{00040     0xa5b71959U,}
\DoxyCodeLine{00041     0xf9c080f1U,}
\DoxyCodeLine{00042     0x7c71e2e1U,}
\DoxyCodeLine{00043     0x0bb409c1U,}
\DoxyCodeLine{00044     0x4dc72381U,}
\DoxyCodeLine{00045     0xd17a8701U,}
\DoxyCodeLine{00046     0x96260e01U,}
\DoxyCodeLine{00047     0x55101c01U,}
\DoxyCodeLine{00048     0x2d303801U,}
\DoxyCodeLine{00049     0x66a07001U,}
\DoxyCodeLine{00050     0xfe40e001U,}
\DoxyCodeLine{00051     0xc081c001U,}
\DoxyCodeLine{00052     0x91038001U,}
\DoxyCodeLine{00053     0x62070001U,}
\DoxyCodeLine{00054     0xc40e0001U,}
\DoxyCodeLine{00055     0x881c0001U,}
\DoxyCodeLine{00056     0x10380001U,}
\DoxyCodeLine{00057     0x20700001U,}
\DoxyCodeLine{00058     0x40e00001U,}
\DoxyCodeLine{00059     0x81c00001U,}
\DoxyCodeLine{00060     0x03800001U,}
\DoxyCodeLine{00061     0x07000001U,}
\DoxyCodeLine{00062     0x0e000001U,}
\DoxyCodeLine{00063     0x1c000001U,}
\DoxyCodeLine{00064     0x38000001U,}
\DoxyCodeLine{00065     0x70000001U,}
\DoxyCodeLine{00066     0xe0000001U,}
\DoxyCodeLine{00067     0xc0000001U,}
\DoxyCodeLine{00068     0x80000001U,}
\DoxyCodeLine{00069     0x00000001U,}
\DoxyCodeLine{00070     0x00000001U}
\DoxyCodeLine{00071 \};}
\DoxyCodeLine{00072 }
\DoxyCodeLine{00073 \textcolor{comment}{/* Get the value of RABINKARP\_MULT\string^n. */}}
\DoxyCodeLine{00074 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t rabinkarp\_pow(uint32\_t n)}
\DoxyCodeLine{00075 \{}
\DoxyCodeLine{00076     \textcolor{keyword}{const} uint32\_t *m = RABINKARP\_MULT\_POW2;}
\DoxyCodeLine{00077     uint32\_t ans = 1;}
\DoxyCodeLine{00078     \textcolor{keywordflow}{while} (n) \{}
\DoxyCodeLine{00079         \textcolor{keywordflow}{if} (n \& 1) \{}
\DoxyCodeLine{00080             ans *= *m;}
\DoxyCodeLine{00081         \}}
\DoxyCodeLine{00082         m++;}
\DoxyCodeLine{00083         n >>= 1;}
\DoxyCodeLine{00084     \}}
\DoxyCodeLine{00085     \textcolor{keywordflow}{return} ans;}
\DoxyCodeLine{00086 \}}
\DoxyCodeLine{00087 }
\DoxyCodeLine{00088 \textcolor{keywordtype}{void} rabinkarp\_update(rabinkarp\_t *sum, \textcolor{keyword}{const} \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} *buf, \textcolor{keywordtype}{size\_t} len)}
\DoxyCodeLine{00089 \{}
\DoxyCodeLine{00090     \textcolor{keywordtype}{size\_t} n = len;}
\DoxyCodeLine{00091     uint32\_t hash = sum-\/>hash;}
\DoxyCodeLine{00092 }
\DoxyCodeLine{00093     \textcolor{keywordflow}{while} (n >= 16) \{}
\DoxyCodeLine{00094         hash = PAR2X8(hash, buf);}
\DoxyCodeLine{00095         buf += 16;}
\DoxyCodeLine{00096         n -\/= 16;}
\DoxyCodeLine{00097     \}}
\DoxyCodeLine{00098     \textcolor{keywordflow}{while} (n) \{}
\DoxyCodeLine{00099         hash = RABINKARP\_MULT * hash + *buf++;}
\DoxyCodeLine{00100         n-\/-\/;}
\DoxyCodeLine{00101     \}}
\DoxyCodeLine{00102     sum-\/>hash = hash;}
\DoxyCodeLine{00103     sum-\/>count += len;}
\DoxyCodeLine{00104     sum-\/>mult *= rabinkarp\_pow((uint32\_t)len);}
\DoxyCodeLine{00105 \}}

\end{DoxyCode}
