Repository navigation
Expand file tree
/
Copy pathHash.h
More file actions
134 lines (131 loc) · 4.59 KB
/
Copy pathHash.h
File metadata and controls
134 lines (131 loc) · 4.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
* Fletcher Checksums
* ------------------
*
* ZFS's 2nd and 4th order Fletcher checksums are defined by the following
* recurrence relations:
*
* a = a + f
* i i-1 i-1
*
* b = b + a
* i i-1 i
*
* c = c + b (fletcher-4 only)
* i i-1 i
*
* d = d + c (fletcher-4 only)
* i i-1 i
*
* Where
* a_0 = b_0 = c_0 = d_0 = 0
* and
* f_0 .. f_(n-1) are the input data.
*
* Using standard techniques, these translate into the following series:
*
* __n_ __n_
* \ | \ |
* a = > f b = > i * f
* n /___| n - i n /___| n - i
* i = 1 i = 1
*
*
* __n_ __n_
* \ | i*(i+1) \ | i*(i+1)*(i+2)
* c = > ------- f d = > ------------- f
* n /___| 2 n - i n /___| 6 n - i
* i = 1 i = 1
*
* For fletcher-2, the f_is are 64-bit, and [ab]_i are 64-bit accumulators.
* Since the additions are done mod (2^64), errors in the high bits may not
* be noticed. For this reason, fletcher-2 is deprecated.
*
* For fletcher-4, the f_is are 32-bit, and [abcd]_i are 64-bit accumulators.
* A conservative estimate of how big the buffer can get before we overflow
* can be estimated using f_i = 0xffffffff for all i:
*
* % bc
* f=2^32-1;d=0; for (i = 1; d<2^64; i++) { d += f*i*(i+1)*(i+2)/6 }; (i-1)*4
* 2264
* quit
* %
*
* So blocks of up to 2k will not overflow. Our largest block size is
* 128k, which has 32k 4-byte words, so we can compute the largest possible
* accumulators, then divide by 2^64 to figure the max amount of overflow:
*
* % bc
* a=b=c=d=0; f=2^32-1; for (i=1; i<=32*1024; i++) { a+=f; b+=a; c+=b; d+=c }
* a/2^64;b/2^64;c/2^64;d/2^64
* 0
* 0
* 1365
* 11186858
* quit
* %
*
* So a and b cannot overflow. To make sure each bit of input has some
* effect on the contents of c and d, we can look at what the factors of
* the coefficients in the equations for c_n and d_n are. The number of 2s
* in the factors determines the lowest set bit in the multiplier. Running
* through the cases for n*(n+1)/2 reveals that the highest power of 2 is
* 2^14, and for n*(n+1)*(n+2)/6 it is 2^15. So while some data may overflow
* the 64-bit accumulators, every bit of every f_i effects every accumulator,
* even for 128k blocks.
*
* If we wanted to make a stronger version of fletcher4 (fletcher4c?),
* we could do our calculations mod (2^32 - 1) by adding in the carries
* periodically, and store the number of carries in the top 32-bits.
*
* --------------------
* Checksum Performance
* --------------------
*
* There are two interesting components to checksum performance: cached and
* uncached performance. With cached data, fletcher-2 is about four times
* faster than fletcher-4. With uncached data, the performance difference is
* negligible, since the cost of a cache fill dominates the processing time.
* Even though fletcher-4 is slower than fletcher-2, it is still a pretty
* efficient pass over the data.
*
* In normal operation, the data which is being checksummed is in a buffer
* which has been filled either by:
*
* 1. a compression step, which will be mostly cached, or
* 2. a bcopy() or copyin(), which will be uncached (because the
* copy is cache-bypassing).
*
* For both cached and uncached data, both fletcher checksums are much faster
* than sha-256, and slower than 'off', which doesn't touch the data at all.
*/
#include "stdafx.h"
#include "zfs.h"
namespace ZFS
{
extern void hash(const void* buf, uint64_t size, cksum_t* zcp, uint8_t cksum_type);
}