`4185 New hash algorithm support`

```   1 /*
3  *
4  * The contents of this file are subject to the terms of the
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
18  *
20  */
21 /*
23  * Use is subject to license terms.
24  */
25 /*
27  */
28
29 /*
30  * Fletcher Checksums
31  * ------------------
32  *
33  * ZFS's 2nd and 4th order Fletcher checksums are defined by the following
34  * recurrence relations:
35  *
36  *      a  = a    + f
37  *       i    i-1    i-1
38  *
39  *      b  = b    + a
40  *       i    i-1    i
41  *
42  *      c  = c    + b           (fletcher-4 only)
43  *       i    i-1    i
44  *
45  *      d  = d    + c           (fletcher-4 only)
46  *       i    i-1    i
47  *
48  * Where
49  *      a_0 = b_0 = c_0 = d_0 = 0
50  * and
51  *      f_0 .. f_(n-1) are the input data.
52  *
53  * Using standard techniques, these translate into the following series:
54  *
55  *           __n_                            __n_
56  *           \   |                           \   |
57  *      a  =  >     f                        b  =  >     i * f
58  *       n   /___|   n - i               n   /___|       n - i
59  *           i = 1                           i = 1
60  *
61  *
62  *           __n_                            __n_
63  *           \   |  i*(i+1)                  \   |  i*(i+1)*(i+2)
64  *      c  =  >     ------- f                d  =  >     ------------- f
65  *       n   /___|     2     n - i       n   /___|        6        n - i
66  *           i = 1                           i = 1
67  *
68  * For fletcher-2, the f_is are 64-bit, and [ab]_i are 64-bit accumulators.
69  * Since the additions are done mod (2^64), errors in the high bits may not
70  * be noticed.  For this reason, fletcher-2 is deprecated.
71  *
72  * For fletcher-4, the f_is are 32-bit, and [abcd]_i are 64-bit accumulators.
73  * A conservative estimate of how big the buffer can get before we overflow
74  * can be estimated using f_i = 0xffffffff for all i:
75  *
76  * % bc
77  *  f=2^32-1;d=0; for (i = 1; d<2^64; i++) { d += f*i*(i+1)*(i+2)/6 }; (i-1)*4
78  * 2264
79  *  quit
80  * %
81  *
82  * So blocks of up to 2k will not overflow.  Our largest block size is
83  * 128k, which has 32k 4-byte words, so we can compute the largest possible
84  * accumulators, then divide by 2^64 to figure the max amount of overflow:
85  *
86  * % bc
87  *  a=b=c=d=0; f=2^32-1; for (i=1; i<=32*1024; i++) { a+=f; b+=a; c+=b; d+=c }
88  *  a/2^64;b/2^64;c/2^64;d/2^64
89  * 0
90  * 0
91  * 1365
92  * 11186858
93  *  quit
94  * %
95  *
96  * So a and b cannot overflow.  To make sure each bit of input has some
97  * effect on the contents of c and d, we can look at what the factors of
98  * the coefficients in the equations for c_n and d_n are.  The number of 2s
99  * in the factors determines the lowest set bit in the multiplier.  Running
100  * through the cases for n*(n+1)/2 reveals that the highest power of 2 is
101  * 2^14, and for n*(n+1)*(n+2)/6 it is 2^15.  So while some data may overflow
102  * the 64-bit accumulators, every bit of every f_i effects every accumulator,
103  * even for 128k blocks.
104  *
105  * If we wanted to make a stronger version of fletcher4 (fletcher4c?),
106  * we could do our calculations mod (2^32 - 1) by adding in the carries
107  * periodically, and store the number of carries in the top 32-bits.
108  *
109  * --------------------
110  * Checksum Performance
111  * --------------------
112  *
113  * There are two interesting components to checksum performance: cached and
114  * uncached performance.  With cached data, fletcher-2 is about four times
115  * faster than fletcher-4.  With uncached data, the performance difference is
116  * negligible, since the cost of a cache fill dominates the processing time.
117  * Even though fletcher-4 is slower than fletcher-2, it is still a pretty
118  * efficient pass over the data.
119  *
120  * In normal operation, the data which is being checksummed is in a buffer
121  * which has been filled either by:
122  *
123  *      1. a compression step, which will be mostly cached, or
124  *      2. a bcopy() or copyin(), which will be uncached (because the
125  *         copy is cache-bypassing).
126  *
127  * For both cached and uncached data, both fletcher checksums are much faster
128  * than sha-256, and slower than 'off', which doesn't touch the data at all.
129  */
130
131 #include <sys/types.h>
132 #include <sys/sysmacros.h>
133 #include <sys/byteorder.h>
134 #include <sys/zio.h>
135 #include <sys/spa.h>
136
137 /*ARGSUSED*/
138 void
139 fletcher_2_native(const void *buf, uint64_t size, const zio_cksum_salt_t *salt,
140     const void *ctx_template, zio_cksum_t *zcp)
141 {
142         const uint64_t *ip = buf;
143         const uint64_t *ipend = ip + (size / sizeof (uint64_t));
144         uint64_t a0, b0, a1, b1;
145
146         for (a0 = b0 = a1 = b1 = 0; ip < ipend; ip += 2) {
147                 a0 += ip[0];
148                 a1 += ip[1];
149                 b0 += a0;
150                 b1 += a1;
151         }
152
153         ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
154 }
155
156 /*ARGSUSED*/
157 void
158 fletcher_2_byteswap(const void *buf, uint64_t size,
159     const zio_cksum_salt_t *salt, const void *ctx_template, zio_cksum_t *zcp)
160 {
161         const uint64_t *ip = buf;
162         const uint64_t *ipend = ip + (size / sizeof (uint64_t));
163         uint64_t a0, b0, a1, b1;
164
165         for (a0 = b0 = a1 = b1 = 0; ip < ipend; ip += 2) {
166                 a0 += BSWAP_64(ip[0]);
167                 a1 += BSWAP_64(ip[1]);
168                 b0 += a0;
169                 b1 += a1;
170         }
171
172         ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
173 }
174
175 /*ARGSUSED*/
176 void
177 fletcher_4_native(const void *buf, uint64_t size, const zio_cksum_salt_t *salt,
178     const void *ctx_template, zio_cksum_t *zcp)
179 {
180         const uint32_t *ip = buf;
181         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
182         uint64_t a, b, c, d;
183
184         for (a = b = c = d = 0; ip < ipend; ip++) {
185                 a += ip[0];
186                 b += a;
187                 c += b;
188                 d += c;
189         }
190
191         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
192 }
193
194 /*ARGSUSED*/
195 void
196 fletcher_4_byteswap(const void *buf, uint64_t size,
197     const zio_cksum_salt_t *salt, const void *ctx_template, zio_cksum_t *zcp)
198 {
199         const uint32_t *ip = buf;
200         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
201         uint64_t a, b, c, d;
202
203         for (a = b = c = d = 0; ip < ipend; ip++) {
204                 a += BSWAP_32(ip[0]);
205                 b += a;
206                 c += b;
207                 d += c;
208         }
209
210         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
211 }
212
213 void
214 fletcher_4_incremental_native(const void *buf, uint64_t size,
215     zio_cksum_t *zcp)
216 {
217         const uint32_t *ip = buf;
218         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
219         uint64_t a, b, c, d;
220
221         a = zcp->zc_word[0];
222         b = zcp->zc_word[1];
223         c = zcp->zc_word[2];
224         d = zcp->zc_word[3];
225
226         for (; ip < ipend; ip++) {
227                 a += ip[0];
228                 b += a;
229                 c += b;
230                 d += c;
231         }
232
233         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
234 }
235
236 void
237 fletcher_4_incremental_byteswap(const void *buf, uint64_t size,
238     zio_cksum_t *zcp)
239 {
240         const uint32_t *ip = buf;
241         const uint32_t *ipend = ip + (size / sizeof (uint32_t));
242         uint64_t a, b, c, d;
243
244         a = zcp->zc_word[0];
245         b = zcp->zc_word[1];
246         c = zcp->zc_word[2];
247         d = zcp->zc_word[3];
248
249         for (; ip < ipend; ip++) {
250                 a += BSWAP_32(ip[0]);
251                 b += a;
252                 c += b;
253                 d += c;
254         }
255
256         ZIO_SET_CHECKSUM(zcp, a, b, c, d);
257 }
--- EOF ---

```