apps/plugins/lib/jhash.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (C) 2006 Bob Jenkins
  11  * http://burtleburtle.net/bob/c/lookup3.c
  12  *
  13  * This program is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU General Public License
  15  * as published by the Free Software Foundation; either version 2
  16  * of the License, or (at your option) any later version.
  17  *
  18  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19  * KIND, either express or implied.
  20  *
  21  ****************************************************************************/
  22 /*
  23 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  24
  25 These are functions for producing 32-bit hashes for hash table lookup.
  26 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  27 are externally useful functions.  Routines to test the hash are included
  28 if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  29 the public domain.  It has no warranty.
  30
  31 You probably want to use hashlittle().  hashlittle() and hashbig()
  32 hash byte arrays.  hashlittle() is is faster than hashbig() on
  33 little-endian machines.  Intel and AMD are little-endian machines.
  34 On second thought, you probably want hashlittle2(), which is identical to
  35 hashlittle() except it returns two 32-bit hashes for the price of one.
  36 You could implement hashbig2() if you wanted but I haven't bothered here.
  37
  38 If you want to find a hash of, say, exactly 7 integers, do
  39 a = i1;  b = i2;  c = i3;
  40 mix(a,b,c);
  41 a += i4; b += i5; c += i6;
  42 mix(a,b,c);
  43 a += i7;
  44 final(a,b,c);
  45 then use c as the hash value.  If you have a variable length array of
  46 4-byte integers to hash, use hashword().  If you have a byte array (like
  47 a character string), use hashlittle().  If you have several byte arrays, or
  48 a mix of things, see the comments above hashlittle().
  49
  50 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
  51 then mix those integers.  This is fast (you can do a lot more thorough
  52 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
  53 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
  54 */
  55
  56 #include "jhash.h"
  57
  58 /*
  59 * My best guess at if you are big-endian or little-endian.  This may
  60 * need adjustment.
  61 */
  62 #if defined(ROCKBOX_LITTLE_ENDIAN)
  63 # define HASH_LITTLE_ENDIAN 1
  64 # define HASH_BIG_ENDIAN 0
  65 #elif defined(ROCKBOX_BIG_ENDIAN)
  66 # define HASH_LITTLE_ENDIAN 0
  67 # define HASH_BIG_ENDIAN 1
  68 #else
  69 # define HASH_LITTLE_ENDIAN 0
  70 # define HASH_BIG_ENDIAN 0
  71 #endif
  72
  73 #define hashsize(n) ((uint32_t)1<<(n))
  74 #define hashmask(n) (hashsize(n)-1)
  75 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
  76
  77 /*
  78
  79 mix -- mix 3 32-bit values reversibly.
  80
  81 This is reversible, so any information in (a,b,c) before mix() is
  82 still in (a,b,c) after mix().
  83
  84 If four pairs of (a,b,c) inputs are run through mix(), or through
  85 mix() in reverse, there are at least 32 bits of the output that
  86 are sometimes the same for one pair and different for another pair.
  87 This was tested for:
  88 * pairs that differed by one bit, by two bits, in any combination
  89   of top bits of (a,b,c), or in any combination of bottom bits of
  90   (a,b,c).
  91 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  92   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  93   is commonly produced by subtraction) look like a single 1-bit
  94   difference.
  95 * the base values were pseudorandom, all zero but one bit set, or
  96   all zero plus a counter that starts at zero.
  97
  98 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
  99 satisfy this are
 100   4  6  8 16 19  4
 101   9 15  3 18 27 15
 102  14  9  3  7 17  3
 103 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
 104 for "differ" defined as + with a one-bit base and a two-bit delta.  I
 105 used http://burtleburtle.net/bob/hash/avalanche.html to choose
 106 the operations, constants, and arrangements of the variables.
 107
 108 This does not achieve avalanche.  There are input bits of (a,b,c)
 109 that fail to affect some output bits of (a,b,c), especially of a.  The
 110 most thoroughly mixed value is c, but it doesn't really even achieve
 111 avalanche in c.
 112
 113 This allows some parallelism.  Read-after-writes are good at doubling
 114 the number of bits affected, so the goal of mixing pulls in the opposite
 115 direction as the goal of parallelism.  I did what I could.  Rotates
 116 seem to cost as much as shifts on every machine I could lay my hands
 117 on, and rotates are much kinder to the top and bottom bits, so I used
 118 rotates.
 119 */
 120 #define mix(a,b,c) \
 121 { \
 122     a -= c;  a ^= rot(c, 4);  c += b; \
 123     b -= a;  b ^= rot(a, 6);  a += c; \
 124     c -= b;  c ^= rot(b, 8);  b += a; \
 125     a -= c;  a ^= rot(c,16);  c += b; \
 126     b -= a;  b ^= rot(a,19);  a += c; \
 127     c -= b;  c ^= rot(b, 4);  b += a; \
 128 }
 129
 130 /*
 131 final -- final mixing of 3 32-bit values (a,b,c) into c
 132
 133 Pairs of (a,b,c) values differing in only a few bits will usually
 134 produce values of c that look totally different.  This was tested for
 135 * pairs that differed by one bit, by two bits, in any combination
 136   of top bits of (a,b,c), or in any combination of bottom bits of
 137 (a,b,c).
 138 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 139   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 140   is commonly produced by subtraction) look like a single 1-bit
 141   difference.
 142 * the base values were pseudorandom, all zero but one bit set, or
 143   all zero plus a counter that starts at zero.
 144
 145 These constants passed:
 146  14 11 25 16  4 14 24
 147  12 14 25 16  4 14 24
 148 and these came close:
 149   4  8 15 26  3 22 24
 150  10  8 15 26  3 22 24
 151  11  8 15 26  3 22 24
 152 */
 153 #define final(a,b,c) \
 154 { \
 155     c ^= b; c -= rot(b,14); \
 156     a ^= c; a -= rot(c,11); \
 157     b ^= a; b -= rot(a,25); \
 158     c ^= b; c -= rot(b,16); \
 159     a ^= c; a -= rot(c,4);  \
 160     b ^= a; b -= rot(a,14); \
 161     c ^= b; c -= rot(b,24); \
 162 }
 163
 164 /*
 165   k:       pointer to the key, an array of uint32_t
 166   length:  number of elements in the key
 167   initval: an initialization value
 168   returns the 32-bit hash
 169 */
 170 uint32_t hashw(const uint32_t *k, size_t length, uint32_t  initval)
 171 {
 172     uint32_t a, b, c;
 173
 174     /* Set up the internal state */
 175     a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
 176
 177     /* handle most of the key */
 178     while (length > 3)
 179     {
 180         a += k[0];
 181         b += k[1];
 182         c += k[2];
 183         mix(a,b,c);
 184         length -= 3;
 185         k += 3;
 186     }
 187
 188     /* handle the last 3 uint32_t's */
 189     switch(length) /* all the case statements fall through */
 190     {
 191     case 3:
 192         c+=k[2];
 193     case 2:
 194         b+=k[1];
 195     case 1:
 196         a+=k[0];
 197         final(a,b,c);
 198     case 0:     /* case 0: nothing left to add */
 199         break;
 200     }
 201     /* report the result */
 202     return c;
 203 }
 204
 205
 206 /*
 207 hashw2() -- same as hashw(), but take two seeds and return two
 208 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
 209 both be initialized with seeds.  If you pass in (*pb)==0, the output
 210 (*pc) will be the same as the return value from hashword().
 211   k:      pointer to the key, an array of uint32_t
 212   length: number of elements in the key
 213   pc, pb: pointers to primary and secondary initial values, also used to store
 214           the hash results.
 215 */
 216 void hashw2 (const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb)
 217 {
 218     uint32_t a,b,c;
 219
 220     /* Set up the internal state */
 221     a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
 222     c += *pb;
 223
 224     /* handle most of the key */
 225     while (length > 3)
 226     {
 227         a += k[0];
 228         b += k[1];
 229         c += k[2];
 230         mix(a,b,c);
 231         length -= 3;
 232         k += 3;
 233     }
 234
 235     /* handle the last 3 uint32_t's */
 236     switch(length) /* all the case statements fall through */
 237     {
 238     case 3:
 239         c+=k[2];
 240     case 2:
 241         b+=k[1];
 242     case 1:
 243         a+=k[0];
 244         final(a,b,c);
 245     case 0: /* case 0: nothing left to add */
 246         break;
 247     }
 248     /* report the result */
 249     *pc=c; *pb=b;
 250 }
 251
 252
 253 /*
 254 hashs() -- hash a variable-length key into a 32-bit value
 255   k:       pointer to the key, an array of bytes
 256   length:  number of elements in the key
 257   initval: an initialization value
 258   returns the 32-bit hash
 259 Returns a 32-bit value.  Every bit of the key affects every bit of
 260 the return value.  Two keys differing by one or two bits will have
 261 totally different hash values.
 262
 263 The best hash table sizes are powers of 2.  There is no need to do
 264 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 265 use a bitmask.  For example, if you need only 10 bits, do
 266 h = (h & hashmask(10));
 267 In which case, the hash table should have hashsize(10) elements.
 268
 269 If you are hashing n strings (uint8_t **)k, do it like this:
 270 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
 271
 272 By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 273 code any way you wish, private, educational, or commercial.  It's free.
 274
 275 Use for hash table lookup, or anything where one collision in 2^^32 is
 276 acceptable.  Do NOT use for cryptographic purposes.
 277 */
 278
 279 uint32_t hashs( const void *key, size_t length, uint32_t initval)
 280 {
 281     uint32_t a,b,c; /* internal state */
 282     union { const void *ptr; size_t i; } u;/* needed for Mac Powerbook G4 */
 283
 284     /* Set up the internal state */
 285     a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
 286
 287     u.ptr = key;
 288 #if HASH_LITTLE_ENDIAN
 289     if ((u.i & 0x3) == 0) {
 290         const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 291
 292         /* all but last block: aligned reads and affect 32 bits of (a,b,c) */
 293         while (length > 12)
 294         {
 295             a += k[0];
 296             b += k[1];
 297             c += k[2];
 298             mix(a,b,c);
 299             length -= 12;
 300             k += 3;
 301         }
 302
 303 /* handle the last (probably partial) block */
 304         switch(length)
 305         {
 306         case 12:
 307             c += k[2];
 308             b += k[1];
 309             a += k[0];
 310             break;
 311         case 11:
 312             c += k[2] & 0xffffff;
 313             b += k[1];
 314             a += k[0];
 315             break;
 316         case 10:
 317             c += k[2] & 0xffff;
 318             b += k[1];
 319             a += k[0];
 320             break;
 321         case 9:
 322             c += k[2] & 0xff;
 323             b += k[1];
 324             a += k[0];
 325             break;
 326         case 8:
 327             b += k[1];
 328             a += k[0];
 329             break;
 330         case 7:
 331             b += k[1] & 0xffffff;
 332             a += k[0];
 333             break;
 334         case 6:
 335             b += k[1] & 0xffff;
 336             a += k[0];
 337             break;
 338         case 5:
 339             b += k[1] & 0xff;
 340             a += k[0];
 341             break;
 342         case 4:
 343             a += k[0];
 344             break;
 345         case 3:
 346             a += k[0] & 0xffffff;
 347             break;
 348         case 2 :
 349             a += k[0] & 0xffff;
 350             break;
 351         case 1:
 352             a += k[0] & 0xff;
 353             break;
 354         case 0:
 355             return c; /* zero length strings require no mixing */
 356         }
 357
 358     } else if ((u.i & 0x1) == 0) {
 359         const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
 360         const uint8_t  *k8;
 361
 362     /* all but last block: aligned reads and different mixing */
 363         while (length > 12)
 364         {
 365             a += k[0] + (((uint32_t)k[1])<<16);
 366             b += k[2] + (((uint32_t)k[3])<<16);
 367             c += k[4] + (((uint32_t)k[5])<<16);
 368             mix(a,b,c);
 369             length -= 12;
 370             k += 6;
 371         }
 372
 373         /* handle the last (probably partial) block */
 374         k8 = (const uint8_t *)k;
 375         switch(length)
 376         {
 377         case 12:
 378             c += k[4] + (((uint32_t)k[5])<<16);
 379             b += k[2] + (((uint32_t)k[3])<<16);
 380             a += k[0] + (((uint32_t)k[1])<<16);
 381             break;
 382         case 11:
 383             c += ((uint32_t)k8[10])<<16; /* fall through */
 384         case 10:
 385             c += k[4];
 386             b += k[2] + (((uint32_t)k[3])<<16);
 387             a += k[0] + (((uint32_t)k[1])<<16);
 388             break;
 389         case 9:
 390             c += k8[8]; /* fall through */
 391         case 8:
 392             b += k[2] + (((uint32_t)k[3])<<16);
 393             a += k[0] + (((uint32_t)k[1])<<16);
 394             break;
 395         case 7:
 396             b += ((uint32_t)k8[6])<<16; /* fall through */
 397         case 6:
 398             b += k[2];
 399             a += k[0] + (((uint32_t)k[1])<<16);
 400             break;
 401         case 5:
 402             b += k8[4]; /* fall through */
 403         case 4:
 404             a += k[0] + (((uint32_t)k[1])<<16);
 405             break;
 406         case 3:
 407             a += ((uint32_t)k8[2])<<16;      /* fall through */
 408         case 2:
 409             a += k[0];
 410             break;
 411         case 1:
 412             a += k8[0];
 413             break;
 414         case 0:
 415             return c; /* zero length requires no mixing */
 416         }
 417
 418     } else
 419 #endif
 420     { /* need to read the key one byte at a time */
 421         const uint8_t *k = (const uint8_t *)key;
 422
 423         /* all but the last block: affect some 32 bits of (a,b,c) */
 424         while (length > 12)
 425         {
 426             a += k[0];
 427             a += ((uint32_t)k[1])<<8;
 428             a += ((uint32_t)k[2])<<16;
 429             a += ((uint32_t)k[3])<<24;
 430             b += k[4];
 431             b += ((uint32_t)k[5])<<8;
 432             b += ((uint32_t)k[6])<<16;
 433             b += ((uint32_t)k[7])<<24;
 434             c += k[8];
 435             c += ((uint32_t)k[9])<<8;
 436             c += ((uint32_t)k[10])<<16;
 437             c += ((uint32_t)k[11])<<24;
 438             mix(a,b,c);
 439             length -= 12;
 440             k += 12;
 441         }
 442
 443         /* last block: affect all 32 bits of (c) */
 444         switch(length) /* all the case statements fall through */
 445         {
 446         case 12:
 447             c += ((uint32_t)k[11])<<24;
 448         case 11:
 449             c += ((uint32_t)k[10])<<16;
 450         case 10:
 451             c += ((uint32_t)k[9])<<8;
 452         case 9:
 453             c += k[8];
 454         case 8:
 455             b += ((uint32_t)k[7])<<24;
 456         case 7:
 457             b += ((uint32_t)k[6])<<16;
 458         case 6:
 459             b += ((uint32_t)k[5])<<8;
 460         case 5:
 461             b += k[4];
 462         case 4:
 463             a += ((uint32_t)k[3])<<24;
 464         case 3:
 465             a += ((uint32_t)k[2])<<16;
 466         case 2:
 467             a += ((uint32_t)k[1])<<8;
 468         case 1:
 469             a +=k [0];
 470             break;
 471         case 0:
 472             return c;
 473         }
 474     }
 475
 476     final(a,b,c);
 477     return c;
 478 }
 479
 480
 481 /*
 482 hashs2: return 2 32-bit hash values
 483   k:       pointer to the key, an array of bytes
 484   length: number of elements in the key
 485   pc, pb: pointers to primary and secondary initial values, also used to store
 486           the hash results.
 487 * This is identical to hashlittle(), except it returns two 32-bit hash
 488 * values instead of just one.  This is good enough for hash table
 489 * lookup with 2^^64 buckets, or if you want a second hash if you're not
 490 * happy with the first, or if you want a probably-unique 64-bit ID for
 491 * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
 492 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
 493 */
 494 void hashs2(const void *key, size_t length, uint32_t *pc, uint32_t *pb)
 495 {
 496     uint32_t a, b, c; /* internal state */
 497     union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
 498
 499     /* Set up the internal state */
 500     a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
 501     c += *pb;
 502
 503     u.ptr = key;
 504 #if HASH_LITTLE_ENDIAN
 505     if (((u.i & 0x3) == 0)) {
 506         const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
 507
 508         /* all but last block: aligned reads and affect 32 bits of (a,b,c) */
 509         while (length > 12)
 510         {
 511             a += k[0];
 512             b += k[1];
 513             c += k[2];
 514             mix(a,b,c);
 515             length -= 12;
 516             k += 3;
 517         }
 518
 519 /* handle the last (probably partial) block */
 520         switch(length)
 521         {
 522         case 12:
 523             c += k[2];
 524             b += k[1];
 525             a += k[0];
 526             break;
 527         case 11:
 528             c += k[2] & 0xffffff;
 529             b += k[1];
 530             a += k[0];
 531             break;
 532         case 10:
 533             c += k[2] & 0xffff;
 534             b += k[1];
 535             a += k[0];
 536             break;
 537         case 9:
 538             c += k[2] & 0xff;
 539             b += k[1];
 540             a += k[0];
 541             break;
 542         case 8:
 543             b += k[1];
 544             a += k[0];
 545             break;
 546         case 7:
 547             b += k[1] & 0xffffff;
 548             a += k[0];
 549             break;
 550         case 6:
 551             b += k[1] & 0xffff;
 552             a += k[0];
 553             break;
 554         case 5:
 555             b += k[1] & 0xff;
 556             a += k[0];
 557             break;
 558         case 4:
 559             a += k[0];
 560             break;
 561         case 3:
 562             a += k[0] & 0xffffff;
 563             break;
 564         case 2:
 565             a += k[0] & 0xffff;
 566             break;
 567         case 1:
 568             a += k[0] & 0xff;
 569             break;
 570         case 0:
 571             *pc=c;
 572             *pb=b;
 573             return; /* zero length strings require no mixing */
 574         }
 575     } else if (((u.i & 0x1) == 0)) {
 576         const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
 577         const uint8_t  *k8;
 578
 579         /* all but last block: aligned reads and different mixing */
 580         while (length > 12)
 581         {
 582             a += k[0] + (((uint32_t)k[1])<<16);
 583             b += k[2] + (((uint32_t)k[3])<<16);
 584             c += k[4] + (((uint32_t)k[5])<<16);
 585             mix(a,b,c);
 586             length -= 12;
 587             k += 6;
 588         }
 589
 590         /* handle the last (probably partial) block */
 591         k8 = (const uint8_t *)k;
 592         switch(length)
 593         {
 594         case 12:
 595             c += k[4] + (((uint32_t)k[5])<<16);
 596             b += k[2] + (((uint32_t)k[3])<<16);
 597             a += k[0] + (((uint32_t)k[1])<<16);
 598             break;
 599         case 11:
 600             c += ((uint32_t)k8[10])<<16; /* fall through */
 601         case 10:
 602             c += k[4];
 603             b += k[2] + (((uint32_t)k[3])<<16);
 604             a += k[0] + (((uint32_t)k[1])<<16);
 605             break;
 606         case 9:
 607             c += k8[8]; /* fall through */
 608         case 8:
 609             b += k[2] + (((uint32_t)k[3])<<16);
 610             a += k[0] + (((uint32_t)k[1])<<16);
 611             break;
 612         case 7:
 613             b += ((uint32_t)k8[6])<<16; /* fall through */
 614         case 6:
 615             b += k[2];
 616             a += k[0] + (((uint32_t)k[1])<<16);
 617             break;
 618         case 5:
 619             b += k8[4]; /* fall through */
 620         case 4:
 621             a += k[0] + (((uint32_t)k[1])<<16);
 622             break;
 623         case 3:
 624             a += ((uint32_t)k8[2])<<16; /* fall through */
 625         case 2:
 626             a += k[0];
 627             break;
 628         case 1:
 629             a += k8[0];
 630             break;
 631         case 0:
 632             *pc=c;
 633             *pb=b;
 634             return; /* zero length strings require no mixing */
 635         }
 636     } else
 637 #endif
 638     { /* need to read the key one byte at a time */
 639         const uint8_t *k = (const uint8_t *)key;
 640
 641         /* all but the last block: affect some 32 bits of (a,b,c) */
 642         while (length > 12)
 643         {
 644             a += k[0];
 645             a += ((uint32_t)k[1])<<8;
 646             a += ((uint32_t)k[2])<<16;
 647             a += ((uint32_t)k[3])<<24;
 648             b += k[4];
 649             b += ((uint32_t)k[5])<<8;
 650             b += ((uint32_t)k[6])<<16;
 651             b += ((uint32_t)k[7])<<24;
 652             c += k[8];
 653             c += ((uint32_t)k[9])<<8;
 654             c += ((uint32_t)k[10])<<16;
 655             c += ((uint32_t)k[11])<<24;
 656             mix(a,b,c);
 657             length -= 12;
 658             k += 12;
 659         }
 660
 661         /* last block: affect all 32 bits of (c) */
 662         switch(length) /* all the case statements fall through */
 663         {
 664         case 12:
 665             c += ((uint32_t)k[11]) << 24;
 666         case 11:
 667             c += ((uint32_t)k[10]) << 16;
 668         case 10:
 669             c += ((uint32_t)k[9]) << 8;
 670         case 9:
 671             c += k[8];
 672         case 8:
 673             b += ((uint32_t)k[7]) << 24;
 674         case 7:
 675             b += ((uint32_t)k[6]) << 16;
 676         case 6:
 677             b += ((uint32_t)k[5]) << 8;
 678         case 5:
 679             b += k[4];
 680         case 4:
 681             a += ((uint32_t)k[3]) << 24;
 682         case 3:
 683             a += ((uint32_t)k[2]) << 16;
 684         case 2:
 685             a += ((uint32_t)k[1]) << 8;
 686         case 1:
 687             a += k[0];
 688             break;
 689         case 0:
 690             *pc=c;
 691             *pb=b;
 692             return; /* zero length strings require no mixing */
 693         }
 694     }
 695
 696     final(a,b,c);
 697     *pc=c;
 698     *pb=b;
 699 }