/* -*- Mode:Text -*- */
#ifndef lint
static char Rcs_Id[] =
    "$Id: hash.c,v 1.12 91/07/11 19:52:07 geoff Exp $";
#endif

/*
 * hash.c - a simple hash function for ispell
 *
 * Pace Willisson, 1983
 *
 * Copyright 1987, 1988, 1989, by Geoff Kuenning, Manhattan Beach, CA
 * Permission for non-profit use is hereby granted.
 * All other rights reserved.
 * See "version.h" for a more complete copyright notice.
 */

/*
 * $Log:	hash.c,v $
 * Revision 1.12  91/07/11  19:52:07  geoff
 * Remove the include of stdio.h, since ispell.h now does this.
 * 
 * Revision 1.11  91/01/27  00:43:34  geoff
 * Replace the old hashing algorithm with a new one based on that developed
 * by Ian Dall.  (The difference between Ian's algorithm and mine is twofold:
 * he shifted by 3, while I found 5 to be better, and I do the shift in a
 * single C statement while he did it in 1-bit steps).
 * 
 * Revision 1.10  90/12/31  00:59:13  geoff
 * Reformat to follow a consistent convention throughout ispell
 * 
 * Revision 1.9  89/06/09  15:53:05  geoff
 * Add support for the internal "character" type, ichar_t.
 * 
 * Revision 1.8  89/04/28  01:08:41  geoff
 * Change Header to Id;  nobody cares about my pathnames.
 * 
 * Revision 1.7  89/04/03  01:55:17  geoff
 * Add support for string characters.
 * 
 * Revision 1.6  88/12/26  02:25:50  geoff
 * Add a copyright notice.
 * 
 * Revision 1.5  88/04/30  22:12:23  geoff
 * Fix some lint complaints.
 * 
 * Revision 1.4  88/02/20  23:11:22  geoff
 * If CAPITALIZATION is enabled, force all strings to uppercase while
 * hashing them.
 * 
 * Revision 1.3  87/03/27  17:20:36  geoff
 * Do the final modulus calculation with a long to avoid overflows.
 * 
 * Revision 1.2  87/01/17  13:11:39  geoff
 * Add RCS ID keywords
 * 
 */

#include "config.h"
#include "ispell.h"

/*
 * The following hash algorithm is due to Ian Dall, with slight modifications
 * by Geoff Kuenning to reflect the results of testing with the English
 * dictionaries actually distributed with ispell.
 */
#define HASHSHIFT   5

#ifdef CAPITALIZATION
#define HASHUPPER(c)	mytoupper(c)
#else /* CAPITALIZATION */
#define HASHUPPER(c)	c
#endif /* CAPITALIZATION */

hash (s, hashtblsize)
    register ichar_t *	s;
    register		hashtblsize;
    {
    register long	h = 0;
    register int	i;

#ifdef ICHAR_IS_CHAR
    for (i = 4;  i--  &&  *s != 0;  )
	h = (h << 8) | HASHUPPER (*s++);
#else /* ICHAR_IS_CHAR */
    for (i = 2;  i--  &&  *s != 0;  )
	h = (h << 16) | HASHUPPER (*s++);
#endif /* ICHAR_IS_CHAR */
    while (*s != 0)
	{
	/*
	 * We have to do circular shifts the hard way, since C doesn't
	 * have them even though the hardware probably does.  Oh, well.
	 */
	h = (h << HASHSHIFT)
	  | ((h >> (32 - HASHSHIFT)) & ((1 << HASHSHIFT) - 1));
	h ^= HASHUPPER (*s++);
	}
    return (unsigned long) h % hashtblsize;
    }
