Debian Codegraph @

hashmerge/combine.go

raw
1 // Copyright 2015, Joe Tsai. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE.md file.
4
5 // Package hashmerge provides functionality for merging hashes.
6 package hashmerge
7
8 // The origin of the CombineAdler32, CombineCRC32, and CombineCRC64 functions
9 // in this package is the adler32_combine, crc32_combine, gf2_matrix_times,
10 // and gf2_matrix_square functions found in the zlib library and was translated
11 // from C to Go. Thanks goes to the authors of zlib:
12 // Mark Adler and Jean-loup Gailly.
13 //
14 // See the following:
15 // http://www.zlib.net/
16 // https://github.com/madler/zlib/blob/master/adler32.c
17 // https://github.com/madler/zlib/blob/master/crc32.c
18 // https://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream/23126768#23126768
19 //
20 // ====================================================
21 // Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
22 //
23 // This software is provided 'as-is', without any express or implied
24 // warranty. In no event will the authors be held liable for any damages
25 // arising from the use of this software.
26 //
27 // Permission is granted to anyone to use this software for any purpose,
28 // including commercial applications, and to alter it and redistribute it
29 // freely, subject to the following restrictions:
30 //
31 // 1. The origin of this software must not be misrepresented; you must not
32 // claim that you wrote the original software. If you use this software
33 // in a product, an acknowledgment in the product documentation would be
34 // appreciated but is not required.
35 // 2. Altered source versions must be plainly marked as such, and must not be
36 // misrepresented as being the original software.
37 // 3. This notice may not be removed or altered from any source distribution.
38 //
39 // Jean-loup Gailly Mark Adler
40 // [email protected] [email protected]
41 // ====================================================
42
43 // CombineAdler32 combines two Adler-32 checksums together.
44 // Let AB be the string concatenation of two strings A and B. Then Combine
45 // computes the checksum of AB given only the checksum of A, the checksum of B,
46 // and the length of B:
47 // adler32.Checksum(AB) == CombineAdler32(adler32.Checksum(A), adler32.Checksum(B), len(B))
48 func CombineAdler32(adler1, adler2 uint32, len2 int64) uint32 {
49 if len2 < 0 {
50 panic("hashmerge: negative length")
51 }
52
53 const mod = 65521
54 var sum1, sum2, rem uint32
55 rem = uint32(len2 % mod)
56 sum1 = adler1 & 0xffff
57 sum2 = rem * sum1
58 sum2 %= mod
59 sum1 += (adler2 & 0xffff) + mod - 1
60 sum2 += (adler1 >> 16) + (adler2 >> 16) + mod - rem
61 if sum1 >= mod {
62 sum1 -= mod
63 }
64 if sum1 >= mod {
65 sum1 -= mod
66 }
67 if sum2 >= mod<<1 {
68 sum2 -= mod << 1
69 }
70 if sum2 >= mod {
71 sum2 -= mod
72 }
73 return sum1 | (sum2 << 16)
74 }
75
76 // CombineCRC32 combines two CRC-32 checksums together.
77 // Let AB be the string concatenation of two strings A and B. Then Combine
78 // computes the checksum of AB given only the checksum of A, the checksum of B,
79 // and the length of B:
80 // tab := crc32.MakeTable(poly)
81 // crc32.Checksum(AB, tab) == CombineCRC32(poly, crc32.Checksum(A, tab), crc32.Checksum(B, tab), len(B))
82 func CombineCRC32(poly, crc1, crc2 uint32, len2 int64) uint32 {
83 if len2 < 0 {
84 panic("hashmerge: negative length")
85 }
86
87 // Translation of gf2_matrix_times from zlib.
88 var matrixMult = func(mat *[32]uint32, vec uint32) uint32 {
89 var sum uint32
90 for n := 0; n < 32 && vec > 0; n++ {
91 if vec&1 > 0 {
92 sum ^= mat[n]
93 }
94 vec >>= 1
95 }
96 return sum
97 }
98
99 // Translation of gf2_matrix_square from zlib.
100 var matrixSquare = func(square, mat *[32]uint32) {
101 for n := 0; n < 32; n++ {
102 square[n] = matrixMult(mat, mat[n])
103 }
104 }
105
106 // Even and odd power-of-two zeros operators.
107 var even, odd [32]uint32
108
109 // Put operator for one zero bit in odd.
110 var row uint32 = 1
111 odd[0] = poly
112 for n := 1; n < 32; n++ {
113 odd[n] = row
114 row <<= 1
115 }
116
117 // Put operator for two zero bits in even.
118 matrixSquare(&even, &odd)
119
120 // Put operator for four zero bits in odd.
121 matrixSquare(&odd, &even)
122
123 // Apply len2 zeros to crc1 (first square will put the operator for one
124 // zero byte, eight zero bits, in even).
125 for {
126 // Apply zeros operator for this bit of len2.
127 matrixSquare(&even, &odd)
128 if len2&1 > 0 {
129 crc1 = matrixMult(&even, crc1)
130 }
131 len2 >>= 1
132 if len2 == 0 {
133 break
134 }
135
136 // Another iteration of the loop with odd and even swapped.
137 matrixSquare(&odd, &even)
138 if len2&1 > 0 {
139 crc1 = matrixMult(&odd, crc1)
140 }
141 len2 >>= 1
142 if len2 == 0 {
143 break
144 }
145 }
146 return crc1 ^ crc2
147 }
148
149 // CombineCRC64 combines two CRC-64 checksums together.
150 // Let AB be the string concatenation of two strings A and B. Then Combine
151 // computes the checksum of AB given only the checksum of A, the checksum of B,
152 // and the length of B:
153 // tab := crc64.MakeTable(poly)
154 // crc64.Checksum(AB, tab) == CombineCRC64(poly, crc64.Checksum(A, tab), crc64.Checksum(B, tab), len(B))
155 func CombineCRC64(poly, crc1, crc2 uint64, len2 int64) uint64 {
156 if len2 < 0 {
157 panic("hashmerge: negative length")
158 }
159
160 // Translation of gf2_matrix_times from zlib.
161 var matrixMult = func(mat *[64]uint64, vec uint64) uint64 {
162 var sum uint64
163 for n := 0; n < 64 && vec > 0; n++ {
164 if vec&1 > 0 {
165 sum ^= mat[n]
166 }
167 vec >>= 1
168 }
169 return sum
170 }
171
172 // Translation of gf2_matrix_square from zlib.
173 var matrixSquare = func(square, mat *[64]uint64) {
174 for n := 0; n < 64; n++ {
175 square[n] = matrixMult(mat, mat[n])
176 }
177 }
178
179 // Even and odd power-of-two zeros operators.
180 var even, odd [64]uint64
181
182 // Put operator for one zero bit in odd.
183 var row uint64 = 1
184 odd[0] = poly
185 for n := 1; n < 64; n++ {
186 odd[n] = row
187 row <<= 1
188 }
189
190 // Put operator for two zero bits in even.
191 matrixSquare(&even, &odd)
192
193 // Put operator for four zero bits in odd.
194 matrixSquare(&odd, &even)
195
196 // Apply len2 zeros to crc1 (first square will put the operator for one
197 // zero byte, eight zero bits, in even).
198 for {
199 // Apply zeros operator for this bit of len2.
200 matrixSquare(&even, &odd)
201 if len2&1 > 0 {
202 crc1 = matrixMult(&even, crc1)
203 }
204 len2 >>= 1
205 if len2 == 0 {
206 break
207 }
208
209 // Another iteration of the loop with odd and even swapped.
210 matrixSquare(&odd, &even)
211 if len2&1 > 0 {
212 crc1 = matrixMult(&odd, crc1)
213 }
214 len2 >>= 1
215 if len2 == 0 {
216 break
217 }
218 }
219 return crc1 ^ crc2
220 }