// Copyright 2015, Joe Tsai. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.

// Package hashmerge provides functionality for merging hashes.
package hashmerge

// The origin of the CombineAdler32, CombineCRC32, and CombineCRC64 functions
// in this package is the adler32_combine, crc32_combine, gf2_matrix_times,
// and gf2_matrix_square functions found in the zlib library and was translated
// from C to Go. Thanks goes to the authors of zlib:
//	Mark Adler and Jean-loup Gailly.
//
// See the following:
//	http://www.zlib.net/
//	https://github.com/madler/zlib/blob/master/adler32.c
//	https://github.com/madler/zlib/blob/master/crc32.c
//	https://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream/23126768#23126768
//
// ====================================================
// Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
//
// This software is provided 'as-is', without any express or implied
// warranty.  In no event will the authors be held liable for any damages
// arising from the use of this software.
//
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    in a product, an acknowledgment in the product documentation would be
//    appreciated but is not required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//
// Jean-loup Gailly        Mark Adler
// jloup@gzip.org          madler@alumni.caltech.edu
// ====================================================

// CombineAdler32 combines two Adler-32 checksums together.
// Let AB be the string concatenation of two strings A and B. Then Combine
// computes the checksum of AB given only the checksum of A, the checksum of B,
// and the length of B:
//	adler32.Checksum(AB) == CombineAdler32(adler32.Checksum(A), adler32.Checksum(B), len(B))
func CombineAdler32(adler1, adler2 uint32, len2 int64) uint32 {
	if len2 < 0 {
		panic("hashmerge: negative length")
	}

	const mod = 65521
	var sum1, sum2, rem uint32
	rem = uint32(len2 % mod)
	sum1 = adler1 & 0xffff
	sum2 = rem * sum1
	sum2 %= mod
	sum1 += (adler2 & 0xffff) + mod - 1
	sum2 += (adler1 >> 16) + (adler2 >> 16) + mod - rem
	if sum1 >= mod {
		sum1 -= mod
	}
	if sum1 >= mod {
		sum1 -= mod
	}
	if sum2 >= mod<<1 {
		sum2 -= mod << 1
	}
	if sum2 >= mod {
		sum2 -= mod
	}
	return sum1 | (sum2 << 16)
}

// CombineCRC32 combines two CRC-32 checksums together.
// Let AB be the string concatenation of two strings A and B. Then Combine
// computes the checksum of AB given only the checksum of A, the checksum of B,
// and the length of B:
//	tab := crc32.MakeTable(poly)
//	crc32.Checksum(AB, tab) == CombineCRC32(poly, crc32.Checksum(A, tab), crc32.Checksum(B, tab), len(B))
func CombineCRC32(poly, crc1, crc2 uint32, len2 int64) uint32 {
	if len2 < 0 {
		panic("hashmerge: negative length")
	}

	// Translation of gf2_matrix_times from zlib.
	var matrixMult = func(mat *[32]uint32, vec uint32) uint32 {
		var sum uint32
		for n := 0; n < 32 && vec > 0; n++ {
			if vec&1 > 0 {
				sum ^= mat[n]
			}
			vec >>= 1
		}
		return sum
	}

	// Translation of gf2_matrix_square from zlib.
	var matrixSquare = func(square, mat *[32]uint32) {
		for n := 0; n < 32; n++ {
			square[n] = matrixMult(mat, mat[n])
		}
	}

	// Even and odd power-of-two zeros operators.
	var even, odd [32]uint32

	// Put operator for one zero bit in odd.
	var row uint32 = 1
	odd[0] = poly
	for n := 1; n < 32; n++ {
		odd[n] = row
		row <<= 1
	}

	// Put operator for two zero bits in even.
	matrixSquare(&even, &odd)

	// Put operator for four zero bits in odd.
	matrixSquare(&odd, &even)

	// Apply len2 zeros to crc1 (first square will put the operator for one
	// zero byte, eight zero bits, in even).
	for {
		// Apply zeros operator for this bit of len2.
		matrixSquare(&even, &odd)
		if len2&1 > 0 {
			crc1 = matrixMult(&even, crc1)
		}
		len2 >>= 1
		if len2 == 0 {
			break
		}

		// Another iteration of the loop with odd and even swapped.
		matrixSquare(&odd, &even)
		if len2&1 > 0 {
			crc1 = matrixMult(&odd, crc1)
		}
		len2 >>= 1
		if len2 == 0 {
			break
		}
	}
	return crc1 ^ crc2
}

// CombineCRC64 combines two CRC-64 checksums together.
// Let AB be the string concatenation of two strings A and B. Then Combine
// computes the checksum of AB given only the checksum of A, the checksum of B,
// and the length of B:
//	tab := crc64.MakeTable(poly)
//	crc64.Checksum(AB, tab) == CombineCRC64(poly, crc64.Checksum(A, tab), crc64.Checksum(B, tab), len(B))
func CombineCRC64(poly, crc1, crc2 uint64, len2 int64) uint64 {
	if len2 < 0 {
		panic("hashmerge: negative length")
	}

	// Translation of gf2_matrix_times from zlib.
	var matrixMult = func(mat *[64]uint64, vec uint64) uint64 {
		var sum uint64
		for n := 0; n < 64 && vec > 0; n++ {
			if vec&1 > 0 {
				sum ^= mat[n]
			}
			vec >>= 1
		}
		return sum
	}

	// Translation of gf2_matrix_square from zlib.
	var matrixSquare = func(square, mat *[64]uint64) {
		for n := 0; n < 64; n++ {
			square[n] = matrixMult(mat, mat[n])
		}
	}

	// Even and odd power-of-two zeros operators.
	var even, odd [64]uint64

	// Put operator for one zero bit in odd.
	var row uint64 = 1
	odd[0] = poly
	for n := 1; n < 64; n++ {
		odd[n] = row
		row <<= 1
	}

	// Put operator for two zero bits in even.
	matrixSquare(&even, &odd)

	// Put operator for four zero bits in odd.
	matrixSquare(&odd, &even)

	// Apply len2 zeros to crc1 (first square will put the operator for one
	// zero byte, eight zero bits, in even).
	for {
		// Apply zeros operator for this bit of len2.
		matrixSquare(&even, &odd)
		if len2&1 > 0 {
			crc1 = matrixMult(&even, crc1)
		}
		len2 >>= 1
		if len2 == 0 {
			break
		}

		// Another iteration of the loop with odd and even swapped.
		matrixSquare(&odd, &even)
		if len2&1 > 0 {
			crc1 = matrixMult(&odd, crc1)
		}
		len2 >>= 1
		if len2 == 0 {
			break
		}
	}
	return crc1 ^ crc2
}