sidef-scripts/Digest/binomial_hash_function.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 28 October 2022
# https://github.com/trizen

# A very simple hash function (most likely, not secure), using the binomial function to create the avalanche effect.

# See also:
#   https://oeis.org/A014062
#   https://yewtu.be/watch?v=KqqOXndnvic
#   https://en.wikipedia.org/wiki/Avalanche_effect

define (
    BLOCK_SIZE = 16,            # in bytes
    MODULO     = 2**128,
)

func process_block(str) {

    func f(bits) {
        bits.sum_kv {|k,v|
            binomial(k*k + v, k)
        } % MODULO
    }

    while (str.len < BLOCK_SIZE) {
        var arr = str.bytes.map{.inc}
        str += arr.sum
        str += arr.prod
    }

    var A = f(str.ascii2bits)
    var B = f(str.reverse.ascii2bits)

    mulmod(A, B, MODULO)
}

func prepare_result(num) {
    sprintf('%0*s', 2*BLOCK_SIZE, num % MODULO -> as_hex)
}

func binomial_hash_string(str) {
    prepare_result(str.encode_utf8.split(BLOCK_SIZE).map(process_block).sum)
}

func binomial_hash_file(filename) {
    var total = 0
    var fh = File(filename).open('<:raw') || return nil
    while (fh.read(\var block, BLOCK_SIZE)) {
        total += process_block(block)
    }
    prepare_result(total)
}

var tests = [
    '',
    "\0",
    'a',
    'b',
    'ab',
    'ba',
    'abc',
    'acb',
    'message digest',
    'abcdefghijklmnopqrstuvwxyz',
    'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789',
    '12345678901234567890123456789012345678901234567890123456789012345678901234567890',
]

for msg in tests {
    var hash = binomial_hash_string(msg)
    say "#{hash} : #{msg.dump}"
}

printf("\nBinomial hash of this script: %s\n\n", binomial_hash_file(__FILE__))

#
## Run some special tests
#

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(50.chr).join),
    binomial_hash_string(BLOCK_SIZE.dec.of(50.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(16.chr).join),
    binomial_hash_string(BLOCK_SIZE.dec.of(8.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(16.chr).join),
    binomial_hash_string(BLOCK_SIZE.dec.of(16.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.dec.of(15.chr).join),
    binomial_hash_string(BLOCK_SIZE.dec.dec.of(15.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.inc.of(2.chr).join),
    binomial_hash_string(BLOCK_SIZE.inc.inc.of(2.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(15.chr).join),
    binomial_hash_string(BLOCK_SIZE.dec.of(15.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.dec.of(14.chr).join),
    binomial_hash_string(BLOCK_SIZE.dec.dec.of(14.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.inc.of(1.chr).join),
    binomial_hash_string(BLOCK_SIZE.inc.inc.of(1.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(126.chr).join),
    binomial_hash_string(BLOCK_SIZE.of(63.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(254.chr).join),
    binomial_hash_string(BLOCK_SIZE.of(191.chr).join)
)

assert_ne(
    binomial_hash_string(BLOCK_SIZE.of(124.chr).join),
    binomial_hash_string(BLOCK_SIZE.of(62.chr).join)
)

assert_ne(
    binomial_hash_string("1"),
    binomial_hash_string("149"),
)

for n in (48..52) {
    assert_ne(
        binomial_hash_string(BLOCK_SIZE.inc.of(n.chr).join),
        binomial_hash_string(BLOCK_SIZE.inc.inc.of(n.chr).join),
        "Collision for n = #{n}"
    )
}

__END__
00000000000000000000000000000000 : ""
fea891fdc54930fd39620fcc478299f0 : "\0"
e1a06e532bba0bcf2ef6115e06f6e410 : "a"
004cac7e4dcb9c4129aa7748278626f2 : "b"
82eb8712eb98d42f187531a7eb3f32b2 : "ab"
c8f774efd7bc079c0b749703106346c2 : "ba"
23c44e458e6e4b79109b9a0417499796 : "abc"
643c218207789c53e40d246912feb456 : "acb"
d55aee8c85258c85ed4a866bf4891014 : "message digest"
82a9f92413c1b3cac57f28488d61836b : "abcdefghijklmnopqrstuvwxyz"
c4c22251fd0388692867eefe8af04b99 : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
bfcdbe7ba1ae8243902eee55226f3a0c : "12345678901234567890123456789012345678901234567890123456789012345678901234567890"