quickhash.c

Calc Software Package for Number Calc

/*
 * quickhash - quickly hash a calc value using a quasi Fowler/Noll/Vo hash
 *
 * Copyright (C) 1999-2002  Landon Curt Noll
 *
 * Calc is open software; you can redistribute it and/or modify it under
 * the terms of the version 2.1 of the GNU Lesser General Public License
 * as published by the Free Software Foundation.
 *
 * Calc is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
 * Public License for more details.
 *
 * A copy of version 2.1 of the GNU Lesser General Public License is
 * distributed with calc under the filename COPYING-LGPL.  You should have
 * received a copy with calc; if not, write to Free Software Foundation, Inc.
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * @(#) $Revision: 29.13 $
 * @(#) $Id: quickhash.c,v 29.13 2006/06/25 23:24:16 chongo Exp $
 * @(#) $Source: /usr/local/src/cmd/calc/RCS/quickhash.c,v $
 *
 * Under source code control:	1995/03/04 11:34:23
 * File existed as early as:	1995
 *
 * chongo <was here> /\oo/\	http://www.isthe.com/chongo/
 * Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/
 */

/*
 * NOTE: This file does not contain a hash interface.  It is used by
 *	 associative arrays and other internal processes.
 */


#include "value.h"
#include "zrand.h"
#include "zrandom.h"

/*
 * forward declarations
 */
static QCKHASH assochash(ASSOC *ap, QCKHASH val);
static QCKHASH listhash(LIST *lp, QCKHASH val);
static QCKHASH mathash(MATRIX *m, QCKHASH val);
static QCKHASH objhash(OBJECT *op, QCKHASH val);
static QCKHASH randhash(RAND *r, QCKHASH val);
static QCKHASH randomhash(RANDOM *state, QCKHASH val);
static QCKHASH config_hash(CONFIG *cfg, QCKHASH val);
static QCKHASH fnv_strhash(char *ch, QCKHASH val);
static QCKHASH fnv_STRhash(STRING *str, QCKHASH val);
static QCKHASH fnv_fullhash(FULL *v, LEN len, QCKHASH val);
static QCKHASH fnv_zhash(ZVALUE z, QCKHASH val);
static QCKHASH hash_hash(HASH *hash, QCKHASH val);
static QCKHASH blk_hash(BLOCK *blk, QCKHASH val);


/*
 * quasi_fnv - quasi Fowler/Noll/Vo-0 32 bit hash
 *
 * The basis of this hash algorithm was taken from an idea sent
 * as reviewer comments to the IEEE POSIX P1003.2 committee by:
 *
 *	Phong Vo (http://www.research.att.com/info/kpv/)
 *	Glenn Fowler (http://www.research.att.com/~gsf/)
 *
 * In a subsequent ballot round:
 *
 *	Landon Curt Noll (http://www.isthe.com/chongo/)
 *
 * improved on their algorithm.	 Some people tried this hash
 * and found that it worked rather well.  In an EMail message
 * to Landon, they named it ``Fowler/Noll/Vo'' or the FNV hash.
 *
 * FNV hashes are architected to be fast while maintaining a low
 * collision rate. The FNV speed allows one to quickly hash lots
 * of data while maintaining a reasonable collision rate.  See:
 *
 *	http://www.isthe.com/chongo/tech/comp/fnv/index.html
 *
 * for more details as well as other forms of the FNV hash.
 *
 * given:
 *	x	the value to hash (must not be longer than 32 bits)
 *	val	previous QCKHASH value
 *
 * returns:
 *	the next 32 bit QCKHASH
 *
 * Example:
 * 	QCKHASH val;
 * 	int x;
 *
 * 	quasi_fnv(x, val);
 *
 * NOTE: The (x) argument may be an expression such as something with
 * 	 a ++ or --.  The macro must only use (x) once.
 *
 * NOTE: The (val) argument just be a lvalue / something to which
 * 	 a value can be assigned.
 *
 * The careful observer will note that (x) need not be a simple
 * octet.  This is not a bug, but a feature.  The FNV hash was
 * designed to operate on octets, not abstract objects such
 * as associations, file descriptors and PRNG states.
 * You will also notice that we sometimes add values directly
 * to the (val) hash state.  This is a simulation of hashing
 * a variable type.
 *
 * The Fowler/Noll/Vo hash does a very good job in producing
 * a 32 bit hash arrays of octets in a short amount of time.
 * It is not bad for hashing calc data as well.	 So doing a
 * quick and dirty job of hashing on a part of a calc value
 * is all that calc really needs.
 *
 * The core of the of the FNV hash has been adopted as the calc
 * quick hash with the provision that it operates on 32 bit
 * objects instead of octets.  For calc's internal purposes,
 * this is sufficent.  For general FNV hashing, this is not
 * recommended.
 *
 * It has been observed that gcc, when using -O, -O2, -O3 or
 * better on an AMD or AMD-like processor (such as i686) will
 * produce slightly faster code when using the shift/add
 * expression than when performing a multiply with a constant.
 */
#if defined(NO_HASH_CPU_OPTIMIZATION)
#define quasi_fnv(x,val) \
    ((val) = (((QCKHASH)(val)*(QCKHASH)16777619) ^ ((QCKHASH)(x))))
#else
#define quasi_fnv(x,val) ( \
    ((val) += (((QCKHASH)(val)<<1) + ((QCKHASH)(val)<<4) + \
	       ((QCKHASH)(val)<<7) + ((QCKHASH)(val)<<8) + \
	       ((QCKHASH)(val)<<24))), \
    ((val) ^= (QCKHASH)(x)) \
)
#endif


/*
 * fnv_qhash - compute the next Fowler/Noll/Vo hash given a NUMBER
 *
 * given:
 *	q	pointer to a NUMBER
 *	val	previous QCKHASH value
 *
 * returns:
 *	the next 32 bit QCKHASH
 */
#define fnv_qhash(q,val) \
  (qisint(q) ? fnv_zhash((q)->num, (val)) : \
   fnv_zhash((q)->num, fnv_zhash((q)->den, (val))))


/*
 * fnv_chash - compute the next Fowler/Noll/Vo hash given a COMPLEX
 *
 * given:
 *	c	pointer to a COMPLEX
 *	val	previous QCKHASH value
 *
 * returns:
 *	the next 32 bit QCKHASH
 */
#define fnv_chash(c,val) \
  (cisreal(c) ? fnv_qhash((c)->real, (val)) : \
   fnv_qhash((c)->real, fnv_qhash((c)->imag, (val))))


/*
 * hashvalue - calculate a hash value for a value.
 *
 * The hash does not have to be a perfect one, it is only used for
 * making associations faster.
 *
 * given:
 *	vp	pointer to a VALUE
 *	val	previous QCKHASH value
 *
 * returns:
 *	next QCKHASH value
 */
QCKHASH
hashvalue(VALUE *vp, QCKHASH val)
{
	switch (vp->v_type) {
	case V_INT:
		val += V_NUM;
		return quasi_fnv(vp->v_int, val);
	case V_NUM:
		return fnv_qhash(vp->v_num, val);
	case V_COM:
		return fnv_chash(vp->v_com, val);
	case V_STR:
		return fnv_STRhash(vp->v_str, val);
	case V_NULL:
		return val;
	case V_OBJ:
		return objhash(vp->v_obj, val);
	case V_LIST:
		return listhash(vp->v_list, val);
	case V_ASSOC:
		return assochash(vp->v_assoc, val);
	case V_MAT:
		return mathash(vp->v_mat, val);
	case V_FILE:
		val += V_FILE;
		return quasi_fnv(vp->v_file, val);
	case V_RAND:
		return randhash(vp->v_rand, val);
	case V_RANDOM:
		return randomhash(vp->v_random, val);
	case V_CONFIG:
		return config_hash(vp->v_config, val);
	case V_HASH:
		return hash_hash(vp->v_hash, val);
	case V_BLOCK:
		return blk_hash(vp->v_block, val);
	case V_OCTET:
		val += V_OCTET;
		return quasi_fnv((int)*vp->v_octet, val);
	case V_NBLOCK:
		return blk_hash(vp->v_nblock->blk, val);
	default:
		math_error("Hashing unknown value");
		/*NOTREACHED*/
	}
	return (QCKHASH)0;
}


/*
 * Return a trivial hash value for an association.
 */
static QCKHASH
assochash(ASSOC *ap, QCKHASH val)
{
	/*
	 * XXX - maybe we should hash the first few and last few values???
	 *	 Perhaps we should hash associations in a different but
	 *	 fast way?
	 */
        val += V_ASSOC;
	return quasi_fnv(ap->a_count, val);
}


/*
 * Return a trivial hash value for a list.
 */
static QCKHASH
listhash(LIST *lp, QCKHASH val)
{
	/*
	 * hash small lists
	 */
	switch (lp->l_count) {
	case 0:
		/* empty list hashes to just V_LIST */
		return V_LIST+val;
	case 1:
		/* single element list hashes just that element */
		return hashvalue(&lp->l_first->e_value, V_LIST+val);
	}

	/*
	 * multi element list hashes the first and last elements
	 */
	return hashvalue(&lp->l_first->e_value,
			 hashvalue(&lp->l_last->e_value, V_LIST+val));
}


/*
 * Return a trivial hash value for a matrix.
 */
static QCKHASH
mathash(MATRIX *m, QCKHASH val)
{
	long skip;
	long i;
	VALUE *vp;

	/*
	 * hash size parts of the matrix
	 */
	val += V_MAT;
	quasi_fnv(m->m_dim, val);
	quasi_fnv(m->m_size, val);

	/*
	 * hash the matrix index bounds
	 */
	for (i = m->m_dim - 1; i >= 0; i--) {
		quasi_fnv(m->m_min[i], val);
		quasi_fnv(m->m_max[i], val);
	}

	/*
	 * hash the first 16 elements
	 */
	vp = m->m_table;
	for (i = 0; ((i < m->m_size) && (i < 16)); i++) {
		val = hashvalue(vp++, val);
	}

	/*
	 * hash 10 more elements if they exist
	 */
	i = 16;
	if (i < m->m_size) {
		vp = (VALUE *)&m->m_table[i];
		skip = (m->m_size / 11) + 1;
		while (i < m->m_size) {
			val = hashvalue(vp, val);
			i += skip;
			vp += skip;
		}
	}
	return val;
}


/*
 * Return a trivial hash value for an object.
 */
static QCKHASH
objhash(OBJECT *op, QCKHASH val)
{
	int i;

	quasi_fnv(op->o_actions->oa_index, val);

	i = op->o_actions->oa_count;
	while (--i >= 0)
		val = hashvalue(&op->o_table[i], val);
	return val;
}


/*