c_cpp/etc/calc/quickhash.c

   1 /*
   2  * quickhash - quickly hash a calc value using a quasi Fowler/Noll/Vo hash
   3  *
   4  * Copyright (C) 1999-2007  Landon Curt Noll
   5  *
   6  * Calc is open software; you can redistribute it and/or modify it under
   7  * the terms of the version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * Calc is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  13  * Public License for more details.
  14  *
  15  * A copy of version 2.1 of the GNU Lesser General Public License is
  16  * distributed with calc under the filename COPYING-LGPL.  You should have
  17  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  18  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  *
  20  * @(#) $Revision: 30.1 $
  21  * @(#) $Id: quickhash.c,v 30.1 2007/03/16 11:09:46 chongo Exp $
  22  * @(#) $Source: /usr/local/src/bin/calc/RCS/quickhash.c,v $
  23  *
  24  * Under source code control:   1995/03/04 11:34:23
  25  * File existed as early as:    1995
  26  *
  27  * chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  28  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  29  */
  30
  31 /*
  32  * NOTE: This file does not contain a hash interface.  It is used by
  33  *       associative arrays and other internal processes.
  34  */
  35
  36
  37 #include "value.h"
  38 #include "zrand.h"
  39 #include "zrandom.h"
  40
  41 /*
  42  * forward declarations
  43  */
  44 S_FUNC QCKHASH assochash(ASSOC *ap, QCKHASH val);
  45 S_FUNC QCKHASH listhash(LIST *lp, QCKHASH val);
  46 S_FUNC QCKHASH mathash(MATRIX *m, QCKHASH val);
  47 S_FUNC QCKHASH objhash(OBJECT *op, QCKHASH val);
  48 S_FUNC QCKHASH randhash(RAND *r, QCKHASH val);
  49 S_FUNC QCKHASH randomhash(RANDOM *state, QCKHASH val);
  50 S_FUNC QCKHASH config_hash(CONFIG *cfg, QCKHASH val);
  51 S_FUNC QCKHASH fnv_strhash(char *ch, QCKHASH val);
  52 S_FUNC QCKHASH fnv_STRhash(STRING *str, QCKHASH val);
  53 S_FUNC QCKHASH fnv_fullhash(FULL *v, LEN len, QCKHASH val);
  54 S_FUNC QCKHASH fnv_zhash(ZVALUE z, QCKHASH val);
  55 S_FUNC QCKHASH hash_hash(HASH *hash, QCKHASH val);
  56 S_FUNC QCKHASH blk_hash(BLOCK *blk, QCKHASH val);
  57
  58
  59 /*
  60  * quasi_fnv - quasi Fowler/Noll/Vo-0 32 bit hash
  61  *
  62  * The basis of this hash algorithm was taken from an idea sent
  63  * as reviewer comments to the IEEE POSIX P1003.2 committee by:
  64  *
  65  *      Phong Vo (http://www.research.att.com/info/kpv/)
  66  *      Glenn Fowler (http://www.research.att.com/~gsf/)
  67  *
  68  * In a subsequent ballot round:
  69  *
  70  *      Landon Curt Noll (http://www.isthe.com/chongo/)
  71  *
  72  * improved on their algorithm.  Some people tried this hash
  73  * and found that it worked rather well.  In an EMail message
  74  * to Landon, they named it ``Fowler/Noll/Vo'' or the FNV hash.
  75  *
  76  * FNV hashes are architected to be fast while maintaining a low
  77  * collision rate. The FNV speed allows one to quickly hash lots
  78  * of data while maintaining a reasonable collision rate.  See:
  79  *
  80  *      http://www.isthe.com/chongo/tech/comp/fnv/index.html
  81  *
  82  * for more details as well as other forms of the FNV hash.
  83  *
  84  * given:
  85  *      x       the value to hash (must not be longer than 32 bits)
  86  *      val     previous QCKHASH value
  87  *
  88  * returns:
  89  *      the next 32 bit QCKHASH
  90  *
  91  * Example:
  92  *      QCKHASH val;
  93  *      int x;
  94  *
  95  *      quasi_fnv(x, val);
  96  *
  97  * NOTE: The (x) argument may be an expression such as something with
  98  *       a ++ or --.  The macro must only use (x) once.
  99  *
 100  * NOTE: The (val) argument just be a lvalue / something to which
 101  *       a value can be assigned.
 102  *
 103  * The careful observer will note that (x) need not be a simple
 104  * octet.  This is not a bug, but a feature.  The FNV hash was
 105  * designed to operate on octets, not abstract objects such
 106  * as associations, file descriptors and PRNG states.
 107  * You will also notice that we sometimes add values directly
 108  * to the (val) hash state.  This is a simulation of hashing
 109  * a variable type.
 110  *
 111  * The Fowler/Noll/Vo hash does a very good job in producing
 112  * a 32 bit hash arrays of octets in a short amount of time.
 113  * It is not bad for hashing calc data as well.  So doing a
 114  * quick and dirty job of hashing on a part of a calc value
 115  * is all that calc really needs.
 116  *
 117  * The core of the of the FNV hash has been adopted as the calc
 118  * quick hash with the provision that it operates on 32 bit
 119  * objects instead of octets.  For calc's internal purposes,
 120  * this is sufficent.  For general FNV hashing, this is not
 121  * recommended.
 122  *
 123  * It has been observed that gcc, when using -O, -O2, -O3 or
 124  * better on an AMD or AMD-like processor (such as i686) will
 125  * produce slightly faster code when using the shift/add
 126  * expression than when performing a multiply with a constant.
 127  */
 128 #if defined(NO_HASH_CPU_OPTIMIZATION)
 129 #define quasi_fnv(x,val) \
 130     ((val) = (((QCKHASH)(val)*(QCKHASH)16777619) ^ ((QCKHASH)(x))))
 131 #else
 132 #define quasi_fnv(x,val) ( \
 133     ((val) += (((QCKHASH)(val)<<1) + ((QCKHASH)(val)<<4) + \
 134                ((QCKHASH)(val)<<7) + ((QCKHASH)(val)<<8) + \
 135                ((QCKHASH)(val)<<24))), \
 136     ((val) ^= (QCKHASH)(x)) \
 137 )
 138 #endif
 139
 140
 141 /*
 142  * fnv_qhash - compute the next Fowler/Noll/Vo hash given a NUMBER
 143  *
 144  * given:
 145  *      q       pointer to a NUMBER
 146  *      val     previous QCKHASH value
 147  *
 148  * returns:
 149  *      the next 32 bit QCKHASH
 150  */
 151 #define fnv_qhash(q,val) \
 152   (qisint(q) ? fnv_zhash((q)->num, (val)) : \
 153    fnv_zhash((q)->num, fnv_zhash((q)->den, (val))))
 154
 155
 156 /*
 157  * fnv_chash - compute the next Fowler/Noll/Vo hash given a COMPLEX
 158  *
 159  * given:
 160  *      c       pointer to a COMPLEX
 161  *      val     previous QCKHASH value
 162  *
 163  * returns:
 164  *      the next 32 bit QCKHASH
 165  */
 166 #define fnv_chash(c,val) \
 167   (cisreal(c) ? fnv_qhash((c)->real, (val)) : \
 168    fnv_qhash((c)->real, fnv_qhash((c)->imag, (val))))
 169
 170
 171 /*
 172  * hashvalue - calculate a hash value for a value.
 173  *
 174  * The hash does not have to be a perfect one, it is only used for
 175  * making associations faster.
 176  *
 177  * given:
 178  *      vp      pointer to a VALUE
 179  *      val     previous QCKHASH value
 180  *
 181  * returns:
 182  *      next QCKHASH value
 183  */
 184 QCKHASH
 185 hashvalue(VALUE *vp, QCKHASH val)
 186 {
 187         switch (vp->v_type) {
 188         case V_INT:
 189                 val += V_NUM;
 190                 return quasi_fnv(vp->v_int, val);
 191         case V_NUM:
 192                 return fnv_qhash(vp->v_num, val);
 193         case V_COM:
 194                 return fnv_chash(vp->v_com, val);
 195         case V_STR:
 196                 return fnv_STRhash(vp->v_str, val);
 197         case V_NULL:
 198                 return val;
 199         case V_OBJ:
 200                 return objhash(vp->v_obj, val);
 201         case V_LIST:
 202                 return listhash(vp->v_list, val);
 203         case V_ASSOC:
 204                 return assochash(vp->v_assoc, val);
 205         case V_MAT:
 206                 return mathash(vp->v_mat, val);
 207         case V_FILE:
 208                 val += V_FILE;
 209                 return quasi_fnv(vp->v_file, val);
 210         case V_RAND:
 211                 return randhash(vp->v_rand, val);
 212         case V_RANDOM:
 213                 return randomhash(vp->v_random, val);
 214         case V_CONFIG:
 215                 return config_hash(vp->v_config, val);
 216         case V_HASH:
 217                 return hash_hash(vp->v_hash, val);
 218         case V_BLOCK:
 219                 return blk_hash(vp->v_block, val);
 220         case V_OCTET:
 221                 val += V_OCTET;
 222                 return quasi_fnv((int)*vp->v_octet, val);
 223         case V_NBLOCK:
 224                 return blk_hash(vp->v_nblock->blk, val);
 225         default:
 226                 math_error("Hashing unknown value");
 227                 /*NOTREACHED*/
 228         }
 229         return (QCKHASH)0;
 230 }
 231
 232
 233 /*
 234  * Return a trivial hash value for an association.
 235  */
 236 S_FUNC QCKHASH
 237 assochash(ASSOC *ap, QCKHASH val)
 238 {
 239         /*
 240          * XXX - maybe we should hash the first few and last few values???
 241          *       Perhaps we should hash associations in a different but
 242          *       fast way?
 243          */
 244         val += V_ASSOC;
 245         return quasi_fnv(ap->a_count, val);
 246 }
 247
 248
 249 /*
 250  * Return a trivial hash value for a list.
 251  */
 252 S_FUNC QCKHASH
 253 listhash(LIST *lp, QCKHASH val)
 254 {
 255         /*
 256          * hash small lists
 257          */
 258         switch (lp->l_count) {
 259         case 0:
 260                 /* empty list hashes to just V_LIST */
 261                 return V_LIST+val;
 262         case 1:
 263                 /* single element list hashes just that element */
 264                 return hashvalue(&lp->l_first->e_value, V_LIST+val);
 265         }
 266
 267         /*
 268          * multi element list hashes the first and last elements
 269          */
 270         return hashvalue(&lp->l_first->e_value,
 271                          hashvalue(&lp->l_last->e_value, V_LIST+val));
 272 }
 273
 274
 275 /*
 276  * Return a trivial hash value for a matrix.
 277  */
 278 S_FUNC QCKHASH
 279 mathash(MATRIX *m, QCKHASH val)
 280 {
 281         long skip;
 282         long i;
 283         VALUE *vp;
 284
 285         /*
 286          * hash size parts of the matrix
 287          */
 288         val += V_MAT;
 289         quasi_fnv(m->m_dim, val);
 290         quasi_fnv(m->m_size, val);
 291
 292         /*
 293          * hash the matrix index bounds
 294          */
 295         for (i = m->m_dim - 1; i >= 0; i--) {
 296                 quasi_fnv(m->m_min[i], val);
 297                 quasi_fnv(m->m_max[i], val);
 298         }
 299
 300         /*
 301          * hash the first 16 elements
 302          */
 303         vp = m->m_table;
 304         for (i = 0; ((i < m->m_size) && (i < 16)); i++) {
 305                 val = hashvalue(vp++, val);
 306         }
 307
 308         /*
 309          * hash 10 more elements if they exist
 310          */
 311         i = 16;
 312         if (i < m->m_size) {
 313                 vp = (VALUE *)&m->m_table[i];
 314                 skip = (m->m_size / 11) + 1;
 315                 while (i < m->m_size) {
 316                         val = hashvalue(vp, val);
 317                         i += skip;
 318                         vp += skip;
 319                 }
 320         }
 321         return val;
 322 }
 323
 324
 325 /*
 326  * Return a trivial hash value for an object.
 327  */
 328 S_FUNC QCKHASH
 329 objhash(OBJECT *op, QCKHASH val)
 330 {
 331         int i;
 332
 333         quasi_fnv(op->o_actions->oa_index, val);
 334
 335         i = op->o_actions->oa_count;
 336         while (--i >= 0)
 337                 val = hashvalue(&op->o_table[i], val);
 338         return val;
 339 }
 340
 341
 342 /*
 343  * randhash - return a trivial hash for an s100 state
 344  *
 345  * given:
 346  *      state - state to hash
 347  *
 348  * returns:
 349  *      trivial hash integer
 350  */
 351 S_FUNC QCKHASH
 352 randhash(RAND *r, QCKHASH val)
 353 {
 354         /*
 355          * hash the RAND state
 356          */
 357         if (!r->seeded) {
 358                 /* unseeded state hashes to V_RAND */
 359                 return V_RAND+val;
 360         } else {
 361                 /* hash control values */
 362                 val += V_RAND;
 363                 quasi_fnv(r->j, val);
 364                 quasi_fnv(r->k, val);
 365                 quasi_fnv(r->bits, val);
 366                 quasi_fnv(r->need_to_skip, val);
 367
 368                 /* hash the state arrays */
 369                 return fnv_fullhash(&r->buffer[0], SLEN+SCNT+SHUFLEN, val);
 370         }
 371 }
 372
 373
 374 /*
 375  * randomhash - return a trivial hash for a Blum state
 376  *
 377  * given:
 378  *      state - state to hash
 379  *
 380  * returns:
 381  *      trivial hash integer
 382  */
 383 S_FUNC QCKHASH
 384 randomhash(RANDOM *state, QCKHASH val)
 385 {
 386         /*
 387          * unseeded RANDOM state hashes to V_RANDOM
 388          */
 389         if (!state->seeded) {
 390                 return V_RANDOM+val;
 391         }
 392
 393         /*
 394          * hash a seeded RANDOM state
 395          */
 396         val += V_RANDOM;
 397         quasi_fnv(state->buffer+state->bits, val);
 398         if (state->r.v != NULL) {
 399                 val = fnv_zhash(state->r, val);
 400         }
 401         if (state->n.v != NULL) {
 402                 val = fnv_zhash(state->n, val);
 403         }
 404         return val;
 405 }
 406
 407
 408 /*
 409  * config_hash - return a trivial hash for a configuration state
 410  */
 411 S_FUNC QCKHASH
 412 config_hash(CONFIG *cfg, QCKHASH val)
 413 {
 414         USB32 value;            /* value to hash from hash elements */
 415
 416         /*
 417          * build up a scalar value
 418          *
 419          * We will rotate a value left 5 bits and xor in each scalar element
 420          */
 421         value = cfg->outmode;
 422         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->outmode);
 423         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->outmode2);
 424         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->outdigits);
 425         /* epsilon is handeled out of order */
 426         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->epsilonprec);
 427         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->traceflags);
 428         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->maxprint);
 429         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->mul2);
 430         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->sq2);
 431         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->pow2);
 432         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->redc2);
 433         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->tilde_ok);
 434         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->tab_ok);
 435         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->quomod);
 436         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->quo);
 437         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->mod);
 438         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->sqrt);
 439         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->appr);
 440         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->cfappr);
 441         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->cfsim);
 442         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->outround);
 443         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->round);
 444         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->leadzero);
 445         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->fullzero);
 446         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->maxscancount);
 447         /* prompt1 is handeled out of order */
 448         /* prompt2 is handeled out of order */
 449         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->blkmaxprint);
 450         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->blkverbose);
 451         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->blkbase);
 452         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->blkfmt);
 453         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->calc_debug);
 454         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->resource_debug);
 455         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->user_debug);
 456         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->verbose_quit);
 457         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->ctrl_d);
 458         /* program is handeled out of order */
 459         /* basename is handeled out of order */
 460         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->windows);
 461         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->cygwin);
 462         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->compile_custom);
 463         if (cfg->allow_custom != NULL && *(cfg->allow_custom)) {
 464                 value = (((value>>5) | (value<<27)) ^ (USB32)TRUE);
 465         } else {
 466                 value = (((value>>5) | (value<<27)) ^ (USB32)FALSE);
 467         }
 468         /* version is handeled out of order */
 469
 470         /*
 471          * hash the built up scalar
 472          */
 473         val += V_CONFIG;
 474         quasi_fnv(value, val);
 475
 476         /*
 477          * hash the strings and pointers if possible
 478          */
 479         if (cfg->prompt1) {
 480                 val = fnv_strhash(cfg->prompt1, val);
 481         }
 482         if (cfg->prompt2) {
 483                 val = fnv_strhash(cfg->prompt2, val);
 484         }
 485         if (cfg->program) {
 486                 val = fnv_strhash(cfg->program, val);
 487         }
 488         if (cfg->base_name) {
 489                 val = fnv_strhash(cfg->base_name, val);
 490         }
 491         if (cfg->version) {
 492                 val = fnv_strhash(cfg->version, val);
 493         }
 494         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->baseb);
 495         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->redecl_warn);
 496         value = (((value>>5) | (value<<27)) ^ (USB32)cfg->dupvar_warn);
 497
 498         /*
 499          * hash the epsilon if possible
 500          */
 501         if (cfg->epsilon) {
 502                 val = fnv_qhash(cfg->epsilon, val);
 503         }
 504         return val;
 505 }
 506
 507
 508 /*
 509  * fnv_strhash - Fowler/Noll/Vo 32 bit hash of a null-terminated string
 510  *
 511  * given:
 512  *      ch      the start of the string to hash
 513  *      val     initial hash value
 514  *
 515  * returns:
 516  *      a 32 bit QCKHASH value
 517  */
 518 S_FUNC QCKHASH
 519 fnv_strhash(char *ch, QCKHASH val)
 520 {
 521         /*
 522          * hash each character in the string
 523          */
 524         while (*ch) {
 525                 quasi_fnv(*ch++, val);
 526         }
 527         return val;
 528 }
 529
 530 /*
 531  * fnv_STRhash - Fowler/Noll/Vo 32 bit hash of a STRING
 532  *
 533  * given:
 534  *      str     the string to hash
 535  *      val     initial hash value
 536  *
 537  * returns:
 538  *      a 32 bit QCKHASH value
 539  */
 540 S_FUNC QCKHASH
 541 fnv_STRhash(STRING *str, QCKHASH val)
 542 {
 543         char *ch;
 544         long n;
 545
 546         ch = str->s_str;
 547         n = str->s_len;
 548
 549         /*
 550          * hash each character in the string
 551          */
 552         while (n-- > 0) {
 553                 quasi_fnv(*ch++, val);
 554         }
 555         return val;
 556 }
 557
 558
 559 /*
 560  * fnv_fullhash - Fowler/Noll/Vo 32 bit hash of an array of HALFs
 561  *
 562  * given:
 563  *      v       an array of FULLs
 564  *      len     length of buffer FULLs
 565  *      val     initial hash value
 566  *
 567  * returns:
 568  *      a 32 bit QCKHASH value
 569  */
 570 S_FUNC QCKHASH
 571 fnv_fullhash(FULL *v, LEN len, QCKHASH val)
 572 {
 573         /*
 574          * hash each character in the string
 575          */
 576         while (len-- > 0) {
 577                 quasi_fnv(*v++, val);
 578         }
 579         return val;
 580 }
 581
 582
 583 /*
 584  * fnv_zhash - Fowler/Noll/Vo 32 bit hash of ZVALUE
 585  *
 586  * given:
 587  *      z       a ZVALUE
 588  *      val     initial hash value
 589  *
 590  * returns:
 591  *      a 32 bit QCKHASH value
 592  */
 593 S_FUNC QCKHASH
 594 fnv_zhash(ZVALUE z, QCKHASH val)
 595 {
 596         LEN n;
 597         HALF *hp;
 598 #if BASEB == 16
 599         FULL f;
 600 #endif
 601
 602         /*
 603          * hash the sign
 604          */
 605         val += V_NUM;
 606         quasi_fnv(z.sign, val);
 607
 608         n = z.len;
 609         hp = z.v;
 610
 611 #if BASEB == 16
 612         while (n > 1) {
 613                 f = (FULL) *hp++;
 614                 f |= (FULL) *hp++ << BASEB;
 615                 quasi_fnv(f, val);
 616                 n -= 2;
 617         }
 618         if (n) {
 619                 quasi_fnv(*hp, val);
 620         }
 621 #else
 622         while (n--  > 0) {
 623                 quasi_fnv(*hp, val);
 624                 ++hp;
 625         }
 626 #endif
 627         return val;
 628 }
 629
 630
 631 /*
 632  * hash_hash - Fowler/Noll/Vo 32 bit hash of a block
 633  *
 634  * given:
 635  *      hash    the HASH to quickhash
 636  *      val     initial hash value
 637  *
 638  * returns:
 639  *      a 32 bit QCKHASH value
 640  */
 641 S_FUNC QCKHASH
 642 hash_hash(HASH *hash, QCKHASH val)
 643 {
 644         int i;
 645
 646         /*
 647          * hash each USB8 in the BLOCK
 648          */
 649         for (i=0; i < hash->unionsize; ++i) {
 650                 quasi_fnv(hash->h_union.data[i], val);
 651         }
 652         return val;
 653 }
 654
 655
 656 /*
 657  * blk_hash - Fowler/Noll/Vo 32 bit hash of a block
 658  *
 659  * given:
 660  *      blk     the BLOCK to hash
 661  *      val     initial hash value
 662  *
 663  * returns:
 664  *      a 32 bit QCKHASH value
 665  */
 666 S_FUNC QCKHASH
 667 blk_hash(BLOCK *blk, QCKHASH val)
 668 {
 669         int i;
 670
 671         if (blk == NULL)                /* block has no data */
 672                 return val;
 673
 674         /*
 675          * hash each USB8 in the BLOCK
 676          */
 677         if (blk->datalen > 0) {
 678                 for (i=0; i < blk->datalen; ++i) {
 679                         quasi_fnv(blk->data[i], val);
 680                 }
 681         }
 682         return val;
 683 }