1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#include <toku_stdlib.h>
40#include <portability/toku_portability.h>
41
42#include "x1764.h"
43
44#define PRINT 0
45
46uint32_t toku_x1764_memory_simple (const void *buf, int len)
47{
48 const uint64_t *CAST_FROM_VOIDP(lbuf, buf);
49 uint64_t c=0;
50 while (len>=8) {
51 c = c*17 + *lbuf;
52 if (PRINT) printf("%d: c=%016" PRIx64 " sum=%016" PRIx64 "\n", __LINE__, *lbuf, c);
53 lbuf++;
54 len-=8;
55 }
56 if (len>0) {
57 const uint8_t *cbuf=(uint8_t*)lbuf;
58 int i;
59 uint64_t input=0;
60 for (i=0; i<len; i++) {
61 input |= ((uint64_t)(cbuf[i]))<<(8*i);
62 }
63 c = c*17 + input;
64 }
65 return ~((c&0xFFFFFFFF) ^ (c>>32));
66}
67
68uint32_t toku_x1764_memory (const void *vbuf, int len)
69{
70 const uint8_t *CAST_FROM_VOIDP(buf, vbuf);
71 int len_4_words = 4*sizeof(uint64_t);
72 uint64_t suma=0, sumb=0, sumc=0, sumd=0;
73 while (len >= len_4_words) {
74 suma = suma*(17LL*17LL*17LL*17LL) + *(uint64_t*)(buf +0*sizeof(uint64_t));
75 sumb = sumb*(17LL*17LL*17LL*17LL) + *(uint64_t*)(buf +1*sizeof(uint64_t));
76 sumc = sumc*(17LL*17LL*17LL*17LL) + *(uint64_t*)(buf +2*sizeof(uint64_t));
77 sumd = sumd*(17LL*17LL*17LL*17LL) + *(uint64_t*)(buf +3*sizeof(uint64_t));
78 buf += len_4_words;
79 len -= len_4_words;
80 }
81 uint64_t sum = suma*17L*17L*17L + sumb*17L*17L + sumc*17L + sumd;
82 assert(len>=0);
83 while ((uint64_t)len>=sizeof(uint64_t)) {
84 sum = sum*17 + *(uint64_t*)buf;
85 buf+=sizeof(uint64_t);
86 len-=sizeof(uint64_t);
87 }
88 if (len>0) {
89 uint64_t tailsum = 0;
90 for (int i=0; i<len; i++) {
91 tailsum |= ((uint64_t)(buf[i]))<<(8*i);
92 }
93 sum = sum*17 + tailsum;
94 }
95 return ~((sum&0xFFFFFFFF) ^ (sum>>32));
96}
97
98
99void toku_x1764_init(struct x1764 *l) {
100 l->sum=0;
101 l->input=0;
102 l->n_input_bytes=0;
103}
104
105void toku_x1764_add (struct x1764 *l, const void *vbuf, int len) {
106 if (PRINT) printf("%d: n_input_bytes=%d len=%d\n", __LINE__, l->n_input_bytes, len);
107 int n_input_bytes = l->n_input_bytes;
108 const unsigned char *CAST_FROM_VOIDP(cbuf, vbuf);
109 // Special case short inputs
110 if (len==1) {
111 uint64_t input = l->input | ((uint64_t)(*cbuf))<<(8*n_input_bytes);
112 n_input_bytes++;
113 if (n_input_bytes==8) {
114 l->sum = l->sum*17 + input;
115 l->n_input_bytes = 0;
116 l->input = 0;
117 } else {
118 l->input = input;
119 l->n_input_bytes = n_input_bytes;
120 }
121 return;
122 } else if (len==2) {
123 uint64_t input = l->input;
124 uint64_t thisv = ((uint64_t)(*(uint16_t*)cbuf));
125 if (n_input_bytes==7) {
126 l->sum = l->sum*17 + (input | (thisv<<(8*7)));
127 l->input = thisv>>8;
128 l->n_input_bytes = 1;
129 } else if (n_input_bytes==6) {
130 l->sum = l->sum*17 + (input | (thisv<<(8*6)));
131 l->input = 0;
132 l->n_input_bytes = 0;
133 } else {
134 l->input = input | (thisv<<(8*n_input_bytes));
135 l->n_input_bytes += 2;
136 }
137 return;
138 }
139
140 uint64_t sum;
141 //assert(len>=0);
142 if (n_input_bytes) {
143 uint64_t input = l->input;
144 if (len>=8) {
145 sum = l->sum;
146 while (len>=8) {
147 uint64_t thisv = *(uint64_t*)cbuf;
148 input |= thisv<<(8*n_input_bytes);
149 sum = sum*17 + input;
150 if (PRINT) printf("%d: input=%016" PRIx64 " sum=%016" PRIx64 "\n", __LINE__, input, sum);
151 input = thisv>>(8*(8-n_input_bytes));
152 if (PRINT) printf("%d: input=%016" PRIx64 "\n", __LINE__, input);
153 len-=8;
154 cbuf+=8;
155 // n_input_bytes remains unchanged
156 if (PRINT) printf("%d: n_input_bytes=%d len=%d\n", __LINE__, l->n_input_bytes, len);
157 }
158 l->sum = sum;
159 }
160 if (len>=4) {
161 uint64_t thisv = *(uint32_t*)cbuf;
162 if (n_input_bytes<4) {
163 input |= thisv<<(8*n_input_bytes);
164 if (PRINT) printf("%d: input=%016" PRIx64 "\n", __LINE__, input);
165 n_input_bytes+=4;
166 } else {
167 input |= thisv<<(8*n_input_bytes);
168 l->sum = l->sum*17 + input;
169 if (PRINT) printf("%d: input=%016" PRIx64 " sum=%016" PRIx64 "\n", __LINE__, input, l->sum);
170 input = thisv>>(8*(8-n_input_bytes));
171 n_input_bytes-=4;
172 if (PRINT) printf("%d: input=%016" PRIx64 " n_input_bytes=%d\n", __LINE__, input, n_input_bytes);
173 }
174 len-=4;
175 cbuf+=4;
176 if (PRINT) printf("%d: len=%d\n", __LINE__, len);
177 }
178 //assert(n_input_bytes<=8);
179 while (n_input_bytes<8 && len) {
180 input |= ((uint64_t)(*cbuf))<<(8*n_input_bytes);
181 n_input_bytes++;
182 cbuf++;
183 len--;
184 }
185 //assert(len>=0);
186 if (n_input_bytes<8) {
187 //assert(len==0);
188 l->input = input;
189 l->n_input_bytes = n_input_bytes;
190 if (PRINT) printf("%d: n_input_bytes=%d\n", __LINE__, l->n_input_bytes);
191 return;
192 }
193 sum = l->sum*17 + input;
194 } else {
195 //assert(len>=0);
196 sum = l->sum;
197 }
198 //assert(len>=0);
199 while (len>=8) {
200 sum = sum*17 + *(uint64_t*)cbuf;
201 cbuf+=8;
202 len -=8;
203 }
204 l->sum = sum;
205 n_input_bytes = 0;
206 uint64_t input;
207 l->n_input_bytes = len;
208 // Surprisingly, the loop is the fastest on bradley's laptop.
209 if (1) {
210 int i;
211 input=0;
212 for (i=0; i<len; i++) {
213 input |= ((uint64_t)(cbuf[i]))<<(8*i);
214 }
215 } else if (0) {
216 switch (len) {
217 case 7: input = ((uint64_t)(*(uint32_t*)(cbuf))) | (((uint64_t)(*(uint16_t*)(cbuf+4)))<<32) | (((uint64_t)(*(cbuf+4)))<<48); break;
218 case 6: input = ((uint64_t)(*(uint32_t*)(cbuf))) | (((uint64_t)(*(uint16_t*)(cbuf+4)))<<32); break;
219 case 5: input = ((uint64_t)(*(uint32_t*)(cbuf))) | (((uint64_t)(*(cbuf+4)))<<32); break;
220 case 4: input = ((uint64_t)(*(uint32_t*)(cbuf))); break;
221 case 3: input = ((uint64_t)(*(uint16_t*)(cbuf))) | (((uint64_t)(*(cbuf+2)))<<16); break;
222 case 2: input = ((uint64_t)(*(uint16_t*)(cbuf))); break;
223 case 1: input = ((uint64_t)(*cbuf)); break;
224 case 0: input = 0; break;
225 default: abort();
226 }
227 } else {
228 input=0;
229 int i=0;
230 if (len>=4) { input = ((uint64_t)(*(uint32_t*)(cbuf))); cbuf+=4; len-=4; i=4;}
231 if (len>=2) { input |= ((uint64_t)(*(uint16_t*)(cbuf)))<<(i*8); cbuf+=2; len-=2; i+=2; }
232 if (len>=1) { input |= ((uint64_t)(*(uint8_t *)(cbuf)))<<(i*8); /*cbuf+=1; len-=1; i++;*/ }
233 }
234 l->input = input;
235 if (PRINT) printf("%d: n_input_bytes=%d\n", __LINE__, l->n_input_bytes);
236}
237uint32_t toku_x1764_finish (struct x1764 *l) {
238 if (PRINT) printf("%d: n_input_bytes=%d\n", __LINE__, l->n_input_bytes);
239 int len = l->n_input_bytes;
240 if (len>0) {
241 l->sum = l->sum*17 + l->input;
242 }
243 return ~((l->sum &0xffffffff) ^ (l->sum>>32));
244}
245