Hash Function HSH 11/13 Source Code Library

Article

Organization

Home » Linoleum Source Code » Hash Function HSH 11/13 » Source Code Library

Scope

This is the source code of the Hash Function HSH 11/13 library, implemented in the Linoleum programming language.

Author

Herbert Glarner

Source Code

(Hash Generator "HSH.txt" 1.1 - Copyright 2006 Herbert Glarner)

(*****************************************************************************)

    (=========================================================================)
    (   Copyright Herbert Glarner [2006]
        Mail: herbert.glarner@bluewin.ch

        Free usage granted for all purposes, including commercial, provided
        that above credits are given.

        Suggestions for performance improvement welcome.
        No liability for any damage usage may cause.   )
    (=========================================================================)


    (=========================================================================)
    (Takes a bitstream input of arbitrary length and generates a hash key from
    it.

    The new algorithm distributes very well, i.e. for different inputs it
    generates a practically uniform distribution along the allowed range, as
    you would expect from a random number generator. This reduces hash
    collisions to an absolute minimum.

    Mapping of 173,528 english words, all in 7 bit ASCII, converted to a bit
    stream with symbol lengths 8 bits, mapped into a hash range of 10 bits,
    i.e. 0...1023, has an average expectancy of 173,528 / 1024 = 169 entries
    {collisions} per hash value. For the 10 LSB of the generated 32-bit key
    minimum was 127 entries, maximum was 224. A graph with the detailled
    distribution can be found on http://herbert.wikispaces.com/HSH.
    )

    (=========================================================================)


    (=========================================================================)
    (Routines summary:
        Name of routine                 Short description)
    (-------------------------------------------------------------------------)
    (   PUBLIC ROUTINES:
            Hsh Create                  Telling about PSW, LSW and EOS

        INTERNAL ROUTINES:
            None
    )
    (=========================================================================)


    (=========================================================================)
    (Memory requirements:
        0 variables.
    )
    (=========================================================================)


    (=========================================================================)
    (Version history:
        11 Jul 2006: 1.0 Released
        15 Jul 2006: 1.1 Released. The hash function accepts the bitwidth as
                     an argument now and does not assume byte processing
                     anymore. If your keys consist of a number of complete 
                     units, use B = 32. If your key consists of a series of
                     bytes, use B = 8 etc.
    )
    (=========================================================================)


(*****************************************************************************)
"libraries"


(*****************************************************************************)
"directors"
        program name = { HSH };
        unit = 32;

(*****************************************************************************)
"constants"                             (Convention: "HSH ...", UPPER CASE)

    (=========================================================================)
    (Error codes)
    (-------------------------------------------------------------------------)
        HSH ERR NONE = 0;               (No error)
    (-------------------------------------------------------------------------)
    (From 'Hsh Init')

    (=========================================================================)

    (=========================================================================)
    (Initial State of the hasher)
    (-------------------------------------------------------------------------)
        HSH START = 40 49 0F DBh;   (pi as per IEEE-754, SngPrec, Big Endian)
                                    (0100 0000 0100 1001 0000 1111 1101 1011)
        (Other good values are: c0c0c0c0h, 03030303h, 00000001h. Do not use 0
        or FFFFFFFFh. Recommendation is to leave the value as it is.)
    (-------------------------------------------------------------------------)
    (From 'Hsh Init')

    (=========================================================================)

(*****************************************************************************)
"variables"                             (Convention: "hsh ...", lower case)



(*****************************************************************************)
"workspace"                             (Convention: "hsh ...", lower case)

    (None)

(*****************************************************************************)
"programme"                             (Convention: "Hsh ...", Mixed case)

    (=========================================================================)
    (This is a library only, it can not be run stand-alone. See "HSH Test.txt"
    for a test setup.)
    (-------------------------------------------------------------------------)
        end;
    (=========================================================================)

(*****************************************************************************)
"Hsh Create"

    (=========================================================================)
    (Creates a 32-bit hash value from the provided key of arbitrary length.)
    (-------------------------------------------------------------------------)
    (Input:     D:  Address of bitstream to be hashed = key. The bits are
                    assumed to be left-aligned at D. If there are more than 32
                    bits, the following units are used, again first using the
                    MSBs of those units. To obtain a lexicographical left-
                    aligned bitstream, you may want to use the library 'Bst',
                    although this is no requirement.
                A:  Number of units at 32 bits each the key consists of:
                    1 for one unit. This is not neccessarily the number of
                    characters. If you process bytes in units, then the
                    number to use is {NumCharsInKey+3}\4.
                B:  Bitwidth of /one/ symbol of your keys. E.g.: if your keys
                    consist of a series of ANSI characters, use 8 = each ANSI
                    character is 8 bits wide.
                    NOTE: For performance reasons, the value is is not checked.
                    However, the allowed range is 0 < B <= 32.                    
    Output:     E:  32-bit hash value. All bits have the same quality: if you
                    need less bits, either rightshift the LSBs out, or mask out
                    the unneeded MSBs.

    All registers except E unchanged.
    Can not cause errors. Terminates with 'leave': don't query 'ok' or 'failed'.
    )
    (-------------------------------------------------------------------------)
        A -->; B -->; C -->; D -->;
    (-------------------------------------------------------------------------)
    (In D is the current unit with bits belonging to the key. We use this
    register only as address reference. In C is the state 1 of the hasher.
    Initially, this is a constant. E is initialized with the first unit,
    later on additional units are mixed it, as long as there are. Ultimately,
    it holds the resulting hash. A is the argument telling how many units there 
    are.)
        C = HSH START;              (State 1 starts with a constant)
        E = 0;                      (State 2 starts the first unit)
        B -;                        (Width of symbol - 1)
    "Hsh Create Repeater"
        B -->;
        E # [D];                    (Xoring in the unit's content)
    "Hsh Create Mix"
        C <@ 11;                    (Shifting by prime number pair < 16)
        E <@ 13;
        E # C;                      (Xoring the 2 states)
        E <@ C;                     (These two shifts are mod 32)
        C <@ E;
        B ^ Hsh Create Mix;         (More than 7 doesn't increase quality much)
    (Feed in the next unit, if any)
        D +;                        (Address next unit)
        <-- B;
        A ^ Hsh Create Repeater;    (Repeat until no more units)
    (-------------------------------------------------------------------------)
    ("Hsh Create Exit OK")
        <-- D; <-- C; <-- B; <-- A;
        leave;
    (=========================================================================)

(*****************************************************************************)

Linoleum Syntax Highlighting produced with LSH (© 2007 by Herbert Glarner)