meta/meta-04-str-hash.f

   1 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   2 ;; UrForth level 1: self-hosting 32-bit Forth compiler
   3 ;; Metacompiler
   4 ;; Copyright (C) 2020 Ketmar Dark // Invisible Vector
   5 ;; GPLv3 ONLY
   6 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   7 ;; word name hashing
   8 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   9
  10 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  11 code: TC-STR-NAME-HASH-ELF  ( addr count -- u32hash )
  12   pop   edi
  13   xor   eax,eax
  14   jecxz .done
  15 .hashloop:
  16   ;; hash <<= 4
  17   shl   eax,4
  18   ;; hash += *key
  19   movzx edx,byte [edi]
  20   ;; upcase it (this also distorts other chars, but who cares)
  21   and   dl,0xdf
  22   add   eax,edx
  23   ;; high = hash&0xF0000000
  24   ld    edx,eax
  25   and   edx,0xf0000000
  26   ld    ebx,edx
  27   inc   edi
  28   ;; hash ^= high>>24
  29   rol   edx,8
  30   xor   eax,edx
  31   ;; hash &= ~high
  32   not   ebx   ;;xor   ebx,0xffffffff
  33   and   eax,ebx
  34   dec   ecx
  35   jr    nz,.hashloop
  36   ;;loop  .hashloop
  37 .done:
  38   ld    TOS,eax
  39   urnext
  40 endcode
  41
  42
  43 code: TC-STR-NAME-HASH-JOAAT  ( addr count -- u32hash )
  44   pop   edi
  45   xor   eax,eax
  46   jecxz .done
  47 .hashloop:
  48   ;; hash += *key
  49   movzx edx,byte [edi]
  50   ;; upcase it (this also distorts other chars, but who cares)
  51   and   dl,0xdf
  52   add   eax,edx
  53   ;; hash += hash<<10
  54   ld    edx,eax
  55   shl   eax,10
  56   add   eax,edx
  57   inc   edi
  58   ;; hash ^= hash>>6
  59   ld    edx,eax
  60   shr   eax,6
  61   xor   eax,edx
  62   dec   ecx
  63   jr    nz,.hashloop
  64   ;;loop  .hashloop
  65   ;; final permutation
  66   ;; hash += hash<<3
  67   ld    edx,eax
  68   shl   eax,3
  69   add   eax,edx
  70   ;; hash ^= hash>>11
  71   ld    edx,eax
  72   shr   eax,11
  73   xor   eax,edx
  74   ;; hash += hash<<15
  75   ld    edx,eax
  76   shl   eax,15
  77   add   eax,edx
  78 .done:
  79   ld    TOS,eax
  80   urnext
  81 endcode
  82
  83
  84 code: TC-STR-NAME-HASH-ROT  ( addr count -- u32hash )
  85   pop   edi
  86   xor   eax,eax
  87   jecxz .done
  88 .hashloop:
  89   ;; hash = lrot(hash, 4)
  90   rol   eax,4
  91   ;; hash += *key
  92   movzx edx,byte [edi]
  93   inc   edi
  94   ;; upcase it (this also distorts other chars, but who cares)
  95   and   dl,0xdf
  96   xor   eax,edx
  97   ;;add   eax,edx
  98   dec   ecx
  99   jr    nz,.hashloop
 100   ;; hash ^= (hash>>10)^(hash>>20)
 101   ld    ecx,eax
 102   shr   ecx,10
 103   ld    edx,eax
 104   shr   edx,20
 105   xor   eax,ecx
 106   xor   eax,edx
 107 .done:
 108   ld    TOS,eax
 109   urnext
 110 endcode