Experiment – Turning the SDBM mixing algorithm into a hash function

From this page: http://www.cse.yorku.ca/~oz/hash.html

import os,sys

def tt(ll):
	return (ll & 0xffffffff)

def sdbm(inpt, leng):
	hshs = 0
	for x in range(0, leng):
		hshs = tt(ord(inpt[x]) + tt(hshs << 6) + tt(hshs << 16) - hshs)
	return hshs

def sdbm_hash(inpt, leng):
	mixs = [1, 6, 16, 13, 33, 27, 67, 55, 123]
	hshs = [0, 0, 0, 0, 0, 0, 0, 0, 0]
	more = 0
	rnds = len(hshs)
	for z in range(0, rnds*3):
		hshs[0] = tt((hshs[0] + mixs[z%rnds]) * mixs[z%rnds])
		for x in range(0, leng):
			hshs[0] = (hshs[0] & 0xffff)
			hshs[0] = tt(ord(inpt[x]) + (hshs[0] << 6) + (hshs[0] << 16) - hshs[0])
			more = (more ^ (hshs[rnds-1] >> 16))
			for y in range(rnds-1, 0, -1):
				hshs[y] = tt((hshs[y] << 16) | (hshs[y-1] >> 16))
				hshs[y-1] = (hshs[y-1] & 0xffff)
			hshs[0] = (hshs[0] ^ more)
	o = ""
	for h in hshs[1:]:
		for x in range(3, -1, -1):
			o += chr((h>>(x*8))&0xff)
	return o

def stoh(s):
	return "".join([hex(ord(c))[2:].rjust(2, '0') for c in s])

m = sys.argv[1] ; l = len(m)
print(stoh(sdbm_hash(m, l)), sdbm(m, l), m, l)

$ python hash.py "b" 
('197f907989061db579beba252025bfbf7f4848a47da0e5a9bc8eb73c6fdb8904', 98, 'b', 1)

$ python hash.py "c" 
('f39b31f66506067376f8f88f620e731cd4292a6aeb71da43d297fffc3f5f92c4', 99, 'c', 1)

$ python hash.py "bb" 
('d427d6ba1edaabab2ba3c6ddd70ccf3d0ceff23fcd6de3d2c0af7d0ac95dd62d', 6428800, 'bb', 2)

$ python hash.py "bc" 
('4bfdd409d3de82913ba7405894f444d8858a539abe98e312d64474abf6b68e3a', 6428801, 'bc', 2)

$ ./hash "this is a test"
[dc053c4426ce396ace93a2817b388c465bb5188336d5f8816384a1cef0a2039d] [1655286693] [this is a test] [14]

$ ./hash "this is a tesu"
[cfbb3301ae39658cf1a1874dd48d8dbf9da4aee0831f781e30066be5f67eb819] [1655286694] [this is a tesu] [14]
#include <stdio.h>
#include <string.h>

unsigned int sdbm(char *inpt, int leng) {
	unsigned int hshs = 0;
	for (int x = 0; x < leng; ++x) {
		hshs = (inpt[x] + (hshs << 6) + (hshs << 16) - hshs);
	}
	return hshs;
}

void sdbm_hash(unsigned char *outp, unsigned char *inpt, int leng) {
	unsigned int mixs[] = {1, 6, 16, 13, 33, 27, 67, 55, 123};
	unsigned int hshs[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
	unsigned int more = 0;
	int rnds = 9;
	for (int z = 0; z < rnds*3; ++z) {
		hshs[0] = ((hshs[0] + mixs[z%rnds]) * mixs[z%rnds]);
		for (int x = 0; x < leng; ++x) {
			hshs[0] = (hshs[0] & 0xffff);
			hshs[0] = (inpt[x] + (hshs[0] << 6) + (hshs[0] << 16) - hshs[0]);
			more = (more ^ (hshs[rnds-1] >> 16));
			for (int y = rnds-1; y > 0; --y) {
				hshs[y] = ((hshs[y] << 16) | (hshs[y-1] >> 16));
				hshs[y-1] = (hshs[y-1] & 0xffff);
			}
			hshs[0] = (hshs[0] ^ more);
		}
	}
	for (int x = 1, y = 0; x < rnds; ++x) {
		for (int z = 3; z > -1; --z, ++y) { 
			outp[y] = ((hshs[x] >> (z * 8)) & 0xff);
		}
	}
}

void stoh(char *outp, unsigned char *inpt) {
	char *hexs = "0123456789abcdef";
	for (int x = 0, y = 0; x < 32; ++x) {
		outp[y] = hexs[(inpt[x] >> 4) & 0xf]; ++y;
		outp[y] = hexs[inpt[x] & 0xf]; ++y;
	}
}

int main(int argc, char *argv[]) {
	char *m = argv[1]; int l = strlen(m);
	unsigned char h[32]; char o[65]; bzero(o, 65);
	sdbm_hash(h, (unsigned char *)m, l); stoh(o, h);
	printf("[%s] [%u] [%s] [%d]\n", o, sdbm(m, l), m, l);
	return 0;
}

Experiment – Turning the SDBM mixing algorithm into a hash function

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s