src/fnvhash.s

   1 /*
   2  * charybdis: a slightly useful ircd.
   3  * fnvhash.s: x86-optimised FNV hashing implementation
   4  *
   5  * Copyright (c) 2006 charybdis development team
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions are
   9  * met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright notice,
  12  *    this list of conditions and the following disclaimer.
  13  *
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * 3. The name of the author may not be used to endorse or promote products
  19  *    derived from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  23  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24  * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  25  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  26  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  29  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  30  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  * $Id: fnvhash.s 2725 2006-11-09 23:43:35Z jilles $
  34  */
  35
  36 /* Safely moves hashv from %edx to %eax and returns back to the calling parent. */
  37 fnv_out:
  38         movzbl  12(%ebp), %ecx
  39         movl    -4(%ebp), %eax
  40         movl    %eax, %edx
  41         shrl    %cl, %edx
  42         movl    12(%ebp), %eax
  43         xorl    $2, %eax
  44         decl    %eax
  45         andl    -4(%ebp), %eax
  46         xorl    %edx, %eax
  47         movl    %eax, -4(%ebp)
  48         movl    -4(%ebp), %eax
  49         leave
  50         ret
  51
  52 /*
  53  * Capitalizes the contents of %eax and adds it to the hashv in %edx.
  54  * Returns hashv in register %eax.
  55  *     - nenolod
  56  */
  57 .globl fnv_hash_upper
  58         .type   fnv_hash_upper, @function
  59 fnv_hash_upper:
  60         pushl   %ebp
  61         movl    %esp, %ebp
  62         subl    $4, %esp
  63         movl    $-2128831035, -4(%ebp)          /* u_int32_t h = FNV1_32_INIT */
  64 .eat_data_upper:                                /* while loop construct */
  65         movl    8(%ebp), %eax                   /* move value of *s to %eax */
  66         cmpb    $0, (%eax)                      /* is eax == 0? */
  67         jne     .hash_capitalized               /* if no, then capitalize and hash */
  68         jmp     fnv_out                         /* if yes, then exit out of the loop */
  69 .hash_capitalized:
  70         movl    8(%ebp), %eax
  71         movzbl  (%eax), %eax                    /* increment s (%eax) */
  72         movzbl  ToUpperTab(%eax), %edx          /* hashv ^= ToUpperTab(%eax) */
  73         leal    -4(%ebp), %eax
  74         xorl    %edx, (%eax)                    /* hashv = 0 */
  75         incl    8(%ebp)
  76         movl    -4(%ebp), %eax
  77         imull   $16777619, %eax, %eax           /* FNV1_32_PRIME */
  78         movl    %eax, -4(%ebp)                  /* add this byte to hashv, and */
  79         jmp     .eat_data_upper                 /*   go back for more...       */
  80
  81 /*
  82  * Hashes (no case change) the contents of %eax and adds it to the hashv in %edx.
  83  * Returns hashv in register %eax.
  84  *     - nenolod
  85  */
  86 .globl fnv_hash
  87         .type   fnv_hash, @function
  88 fnv_hash:
  89         pushl   %ebp
  90         movl    %esp, %ebp
  91         subl    $4, %esp
  92         movl    $-2128831035, -4(%ebp)          /* u_int32_t h = FNV1_32_INIT */
  93 .eat_data:                                      /* again, the while loop construct */
  94         movl    8(%ebp), %eax                   /* move value of *s to eax */
  95         cmpb    $0, (%eax)                      /* is eax == 0? */
  96         jne     .hash_lowercase                 /* if not, jump to .hash_lowercase */
  97         jmp     fnv_out                         /* otherwise, jump to fnv_out */
  98 .hash_lowercase:
  99         movl    8(%ebp), %eax
 100         movzbl  (%eax), %edx
 101         leal    -4(%ebp), %eax
 102         xorl    %edx, (%eax)
 103         incl    8(%ebp)                         /* h << 1 */
 104         movl    -4(%ebp), %eax
 105         imull   $16777619, %eax, %eax           /* FNV1_32_PRIME */
 106         movl    %eax, -4(%ebp)                  /* add this byte to hashv, then */
 107         jmp     .eat_data                       /*   check for more...          */
 108
 109 /*
 110  * Hashes (no case change) the contents of %eax and adds it to the hashv in %edx.
 111  * Returns hashv in register %eax.
 112  *
 113  * Bounds checking is performed.
 114  *     - nenolod
 115  */
 116 .globl fnv_hash_len
 117         .type   fnv_hash_len, @function
 118 fnv_hash_len:
 119         pushl   %ebp
 120         movl    %esp, %ebp
 121         subl    $8, %esp
 122         movl    $-2128831035, -4(%ebp)
 123         movl    16(%ebp), %eax
 124         addl    8(%ebp), %eax
 125         movl    %eax, -8(%ebp)
 126 .eat_data_len:
 127         movl    8(%ebp), %eax
 128         cmpb    $0, (%eax)
 129         je      fnv_out
 130         movl    8(%ebp), %eax
 131         cmpl    -8(%ebp), %eax
 132         jb      .hash_lowercase_len
 133         jmp     fnv_out
 134 .hash_lowercase_len:
 135         movl    8(%ebp), %eax
 136         movzbl  (%eax), %edx
 137         leal    -4(%ebp), %eax
 138         xorl    %edx, (%eax)
 139         incl    8(%ebp)
 140         movl    -4(%ebp), %eax
 141         imull   $16777619, %eax, %eax           /* FNV1_32_PRIME */
 142         movl    %eax, -4(%ebp)
 143         jmp     .eat_data_len
 144
 145 /*
 146  * Hashes (no case change) the contents of %eax and adds it to the hashv in %edx.
 147  * Returns hashv in register %eax.
 148  *
 149  * Bounds checking is performed.
 150  *     - nenolod
 151  */
 152 .globl fnv_hash_upper_len
 153         .type   fnv_hash_upper_len, @function
 154 fnv_hash_upper_len:
 155         pushl   %ebp
 156         movl    %esp, %ebp
 157         subl    $8, %esp
 158         movl    $-2128831035, -4(%ebp)
 159         movl    16(%ebp), %eax
 160         addl    8(%ebp), %eax
 161         movl    %eax, -8(%ebp)
 162 .eat_upper_len:
 163         movl    8(%ebp), %eax
 164         cmpb    $0, (%eax)
 165         je      fnv_out
 166         movl    8(%ebp), %eax
 167         cmpl    -8(%ebp), %eax
 168         jb      .hash_uppercase_len
 169         jmp     fnv_out
 170 .hash_uppercase_len:
 171         movl    8(%ebp), %eax
 172         movzbl  (%eax), %eax
 173         movzbl  ToUpperTab(%eax), %edx
 174         leal    -4(%ebp), %eax
 175         xorl    %edx, (%eax)
 176         incl    8(%ebp)
 177         movl    -4(%ebp), %eax
 178         imull   $16777619, %eax, %eax           /* FNV1_32_PRIME */
 179         movl    %eax, -4(%ebp)
 180         jmp     .eat_upper_len