main
1// Copyright 2014-2022 Ulrich Kunitz. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package hash
6
7// CyclicPoly provides a cyclic polynomial rolling hash.
8type CyclicPoly struct {
9 h uint64
10 p []uint64
11 i int
12}
13
14// ror rotates the unsigned 64-bit integer to right. The argument s must be
15// less than 64.
16func ror(x uint64, s uint) uint64 {
17 return (x >> s) | (x << (64 - s))
18}
19
20// NewCyclicPoly creates a new instance of the CyclicPoly structure. The
21// argument n gives the number of bytes for which a hash will be executed.
22// This number must be positive; the method panics if this isn't the case.
23func NewCyclicPoly(n int) *CyclicPoly {
24 if n < 1 {
25 panic("argument n must be positive")
26 }
27 return &CyclicPoly{p: make([]uint64, 0, n)}
28}
29
30// Len returns the length of the byte sequence for which a hash is generated.
31func (r *CyclicPoly) Len() int {
32 return cap(r.p)
33}
34
35// RollByte hashes the next byte and returns a hash value. The complete becomes
36// available after at least Len() bytes have been hashed.
37func (r *CyclicPoly) RollByte(x byte) uint64 {
38 y := hash[x]
39 if len(r.p) < cap(r.p) {
40 r.h = ror(r.h, 1) ^ y
41 r.p = append(r.p, y)
42 } else {
43 r.h ^= ror(r.p[r.i], uint(cap(r.p)-1))
44 r.h = ror(r.h, 1) ^ y
45 r.p[r.i] = y
46 r.i = (r.i + 1) % cap(r.p)
47 }
48 return r.h
49}
50
51// Stores the hash for the individual bytes.
52var hash = [256]uint64{
53 0x2e4fc3f904065142, 0xc790984cfbc99527,
54 0x879f95eb8c62f187, 0x3b61be86b5021ef2,
55 0x65a896a04196f0a5, 0xc5b307b80470b59e,
56 0xd3bff376a70df14b, 0xc332f04f0b3f1701,
57 0x753b5f0e9abf3e0d, 0xb41538fdfe66ef53,
58 0x1906a10c2c1c0208, 0xfb0c712a03421c0d,
59 0x38be311a65c9552b, 0xfee7ee4ca6445c7e,
60 0x71aadeded184f21e, 0xd73426fccda23b2d,
61 0x29773fb5fb9600b5, 0xce410261cd32981a,
62 0xfe2848b3c62dbc2d, 0x459eaaff6e43e11c,
63 0xc13e35fc9c73a887, 0xf30ed5c201e76dbc,
64 0xa5f10b3910482cea, 0x2945d59be02dfaad,
65 0x06ee334ff70571b5, 0xbabf9d8070f44380,
66 0xee3e2e9912ffd27c, 0x2a7118d1ea6b8ea7,
67 0x26183cb9f7b1664c, 0xea71dac7da068f21,
68 0xea92eca5bd1d0bb7, 0x415595862defcd75,
69 0x248a386023c60648, 0x9cf021ab284b3c8a,
70 0xfc9372df02870f6c, 0x2b92d693eeb3b3fc,
71 0x73e799d139dc6975, 0x7b15ae312486363c,
72 0xb70e5454a2239c80, 0x208e3fb31d3b2263,
73 0x01f563cabb930f44, 0x2ac4533d2a3240d8,
74 0x84231ed1064f6f7c, 0xa9f020977c2a6d19,
75 0x213c227271c20122, 0x09fe8a9a0a03d07a,
76 0x4236dc75bcaf910c, 0x460a8b2bead8f17e,
77 0xd9b27be1aa07055f, 0xd202d5dc4b11c33e,
78 0x70adb010543bea12, 0xcdae938f7ea6f579,
79 0x3f3d870208672f4d, 0x8e6ccbce9d349536,
80 0xe4c0871a389095ae, 0xf5f2a49152bca080,
81 0x9a43f9b97269934e, 0xc17b3753cb6f475c,
82 0xd56d941e8e206bd4, 0xac0a4f3e525eda00,
83 0xa06d5a011912a550, 0x5537ed19537ad1df,
84 0xa32fe713d611449d, 0x2a1d05b47c3b579f,
85 0x991d02dbd30a2a52, 0x39e91e7e28f93eb0,
86 0x40d06adb3e92c9ac, 0x9b9d3afde1c77c97,
87 0x9a3f3f41c02c616f, 0x22ecd4ba00f60c44,
88 0x0b63d5d801708420, 0x8f227ca8f37ffaec,
89 0x0256278670887c24, 0x107e14877dbf540b,
90 0x32c19f2786ac1c05, 0x1df5b12bb4bc9c61,
91 0xc0cac129d0d4c4e2, 0x9fdb52ee9800b001,
92 0x31f601d5d31c48c4, 0x72ff3c0928bcaec7,
93 0xd99264421147eb03, 0x535a2d6d38aefcfe,
94 0x6ba8b4454a916237, 0xfa39366eaae4719c,
95 0x10f00fd7bbb24b6f, 0x5bd23185c76c84d4,
96 0xb22c3d7e1b00d33f, 0x3efc20aa6bc830a8,
97 0xd61c2503fe639144, 0x30ce625441eb92d3,
98 0xe5d34cf359e93100, 0xa8e5aa13f2b9f7a5,
99 0x5c2b8d851ca254a6, 0x68fb6c5e8b0d5fdf,
100 0xc7ea4872c96b83ae, 0x6dd5d376f4392382,
101 0x1be88681aaa9792f, 0xfef465ee1b6c10d9,
102 0x1f98b65ed43fcb2e, 0x4d1ca11eb6e9a9c9,
103 0x7808e902b3857d0b, 0x171c9c4ea4607972,
104 0x58d66274850146df, 0x42b311c10d3981d1,
105 0x647fa8c621c41a4c, 0xf472771c66ddfedc,
106 0x338d27e3f847b46b, 0x6402ce3da97545ce,
107 0x5162db616fc38638, 0x9c83be97bc22a50e,
108 0x2d3d7478a78d5e72, 0xe621a9b938fd5397,
109 0x9454614eb0f81c45, 0x395fb6e742ed39b6,
110 0x77dd9179d06037bf, 0xc478d0fee4d2656d,
111 0x35d9d6cb772007af, 0x83a56e92c883f0f6,
112 0x27937453250c00a1, 0x27bd6ebc3a46a97d,
113 0x9f543bf784342d51, 0xd158f38c48b0ed52,
114 0x8dd8537c045f66b4, 0x846a57230226f6d5,
115 0x6b13939e0c4e7cdf, 0xfca25425d8176758,
116 0x92e5fc6cd52788e6, 0x9992e13d7a739170,
117 0x518246f7a199e8ea, 0xf104c2a71b9979c7,
118 0x86b3ffaabea4768f, 0x6388061cf3e351ad,
119 0x09d9b5295de5bbb5, 0x38bf1638c2599e92,
120 0x1d759846499e148d, 0x4c0ff015e5f96ef4,
121 0xa41a94cfa270f565, 0x42d76f9cb2326c0b,
122 0x0cf385dd3c9c23ba, 0x0508a6c7508d6e7a,
123 0x337523aabbe6cf8d, 0x646bb14001d42b12,
124 0xc178729d138adc74, 0xf900ef4491f24086,
125 0xee1a90d334bb5ac4, 0x9755c92247301a50,
126 0xb999bf7c4ff1b610, 0x6aeeb2f3b21e8fc9,
127 0x0fa8084cf91ac6ff, 0x10d226cf136e6189,
128 0xd302057a07d4fb21, 0x5f03800e20a0fcc3,
129 0x80118d4ae46bd210, 0x58ab61a522843733,
130 0x51edd575c5432a4b, 0x94ee6ff67f9197f7,
131 0x765669e0e5e8157b, 0xa5347830737132f0,
132 0x3ba485a69f01510c, 0x0b247d7b957a01c3,
133 0x1b3d63449fd807dc, 0x0fdc4721c30ad743,
134 0x8b535ed3829b2b14, 0xee41d0cad65d232c,
135 0xe6a99ed97a6a982f, 0x65ac6194c202003d,
136 0x692accf3a70573eb, 0xcc3c02c3e200d5af,
137 0x0d419e8b325914a3, 0x320f160f42c25e40,
138 0x00710d647a51fe7a, 0x3c947692330aed60,
139 0x9288aa280d355a7a, 0xa1806a9b791d1696,
140 0x5d60e38496763da1, 0x6c69e22e613fd0f4,
141 0x977fc2a5aadffb17, 0xfb7bd063fc5a94ba,
142 0x460c17992cbaece1, 0xf7822c5444d3297f,
143 0x344a9790c69b74aa, 0xb80a42e6cae09dce,
144 0x1b1361eaf2b1e757, 0xd84c1e758e236f01,
145 0x88e0b7be347627cc, 0x45246009b7a99490,
146 0x8011c6dd3fe50472, 0xc341d682bffb99d7,
147 0x2511be93808e2d15, 0xd5bc13d7fd739840,
148 0x2a3cd030679ae1ec, 0x8ad9898a4b9ee157,
149 0x3245fef0a8eaf521, 0x3d6d8dbbb427d2b0,
150 0x1ed146d8968b3981, 0x0c6a28bf7d45f3fc,
151 0x4a1fd3dbcee3c561, 0x4210ff6a476bf67e,
152 0xa559cce0d9199aac, 0xde39d47ef3723380,
153 0xe5b69d848ce42e35, 0xefa24296f8e79f52,
154 0x70190b59db9a5afc, 0x26f166cdb211e7bf,
155 0x4deaf2df3c6b8ef5, 0xf171dbdd670f1017,
156 0xb9059b05e9420d90, 0x2f0da855c9388754,
157 0x611d5e9ab77949cc, 0x2912038ac01163f4,
158 0x0231df50402b2fba, 0x45660fc4f3245f58,
159 0xb91cc97c7c8dac50, 0xb72d2aafe4953427,
160 0xfa6463f87e813d6b, 0x4515f7ee95d5c6a2,
161 0x1310e1c1a48d21c3, 0xad48a7810cdd8544,
162 0x4d5bdfefd5c9e631, 0xa43ed43f1fdcb7de,
163 0xe70cfc8fe1ee9626, 0xef4711b0d8dda442,
164 0xb80dd9bd4dab6c93, 0xa23be08d31ba4d93,
165 0x9b37db9d0335a39c, 0x494b6f870f5cfebc,
166 0x6d1b3c1149dda943, 0x372c943a518c1093,
167 0xad27af45e77c09c4, 0x3b6f92b646044604,
168 0xac2917909f5fcf4f, 0x2069a60e977e5557,
169 0x353a469e71014de5, 0x24be356281f55c15,
170 0x2b6d710ba8e9adea, 0x404ad1751c749c29,
171 0xed7311bf23d7f185, 0xba4f6976b4acc43e,
172 0x32d7198d2bc39000, 0xee667019014d6e01,
173 0x494ef3e128d14c83, 0x1f95a152baecd6be,
174 0x201648dff1f483a5, 0x68c28550c8384af6,
175 0x5fc834a6824a7f48, 0x7cd06cb7365eaf28,
176 0xd82bbd95e9b30909, 0x234f0d1694c53f6d,
177 0xd2fb7f4a96d83f4a, 0xff0d5da83acac05e,
178 0xf8f6b97f5585080a, 0x74236084be57b95b,
179 0xa25e40c03bbc36ad, 0x6b6e5c14ce88465b,
180 0x4378ffe93e1528c5, 0x94ca92a17118e2d2,
181}