| 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 |
} |