summaryrefslogtreecommitdiffstats
path: root/lib/hamming.go
blob: 229fb7f348f8cbc825aea4b3ecbd18958d8d3edc (plain) (blame)
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
// Copyright © 2021 siddharth <s@ricketyspace.net>
// SPDX-License-Identifier: ISC

package lib

func HammingDistance(a, b []byte) int {
	if len(a) != len(b) {
		return -1 // Fail.
	}

	d := 0
	for i := 0; i < len(a); i++ {
		c := a[i] ^ b[i]
		d += setBits(c)
	}
	return d
}

// Returns number of set bits.
func setBits(b byte) int {
	var c byte = 0
	for i := 0; i < 8; i++ {
		c += b & 0x1
		b = b >> 1
	}
	return int(c)
}

// Returns key size with minimum normalized hamming distance
// 'keyMin' is the minimum key size
// 'keyMax' is the maximum key size
func KeySizeWithMinDistance(keyMin, keyMax int, bs []byte) int {
	var mk int = 0         // Key size with min distance.
	var md float64 = 100.0 // Distance for key size 'mk'.
	for k := keyMin; k <= keyMax; k++ {
		p := bs[0 : k*8]     // K bytes.
		q := bs[k*8 : k*8*2] // Next K bytes.

		// Compute distance.
		d := HammingDistance(p, q)

		nd := float64(d) / float64(k)
		if nd < md {
			mk = k
			md = nd
		}
	}
	return mk
}