Return to hash.c CVS log

Up to [local] / src / usr.bin / rsync

Annotation of src/usr.bin/rsync/hash.c, Revision 1.4

1.4     ! claudio     1: /*     $OpenBSD: hash.c,v 1.3 2019/02/13 05:41:35 tb Exp $ */
1.1       benno       2: /*
                      3:  * Copyright (c) 2019 Kristaps Dzonsons <kristaps@bsd.lv>
                      4:  *
                      5:  * Permission to use, copy, modify, and distribute this software for any
                      6:  * purpose with or without fee is hereby granted, provided that the above
                      7:  * copyright notice and this permission notice appear in all copies.
                      8:  *
                      9:  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
                     10:  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
                     11:  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
                     12:  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
                     13:  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
                     14:  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
                     15:  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
                     16:  */
                     17: #include <sys/types.h>
                     18:
                     19: #include <assert.h>
                     20: #include <endian.h>
                     21: #include <stdint.h>
                     22: #include <stdlib.h>
                     23:
1.3       tb         24: #include <openssl/md4.h>
                     25:
1.1       benno      26: #include "extern.h"
                     27:
                     28: /*
                     29:  * A fast 32-bit hash.
                     30:  * Described in Tridgell's "Efficient Algorithms for Sorting and
                     31:  * Synchronization" thesis and the "Rolling checksum" document.
                     32:  */
                     33: uint32_t
                     34: hash_fast(const void *buf, size_t len)
                     35: {
1.2       benno      36:        size_t                   i = 0;
                     37:        uint32_t                 a = 0, /* part of a(k, l) */
                     38:                                 b = 0; /* b(k, l) */
                     39:        const signed char       *dat = buf;
1.1       benno      40:
                     41:        if (len > 4)
                     42:                for ( ; i < len - 4; i += 4) {
                     43:                        b += 4 * (a + dat[i]) +
1.2       benno      44:                            3 * dat[i + 1] +
                     45:                            2 * dat[i + 2] +
                     46:                            dat[i + 3];
1.1       benno      47:                        a += dat[i + 0] +
1.2       benno      48:                            dat[i + 1] +
                     49:                            dat[i + 2] +
                     50:                            dat[i + 3];
1.1       benno      51:                }
                     52:
                     53:        for ( ; i < len; i++) {
                     54:                a += dat[i];
                     55:                b += a;
                     56:        }
                     57:
                     58:        /* s(k, l) = (eps % M) + 2^16 b(k, l) % M */
                     59:
                     60:        return (a & 0xffff) + (b << 16);
                     61: }
                     62:
                     63: /*
                     64:  * Slow MD4-based hash with trailing seed.
                     65:  */
                     66: void
                     67: hash_slow(const void *buf, size_t len,
                     68:        unsigned char *md, const struct sess *sess)
                     69: {
                     70:        MD4_CTX          ctx;
                     71:        int32_t          seed = htole32(sess->seed);
                     72:
                     73:        MD4_Init(&ctx);
                     74:        MD4_Update(&ctx, buf, len);
                     75:        MD4_Update(&ctx, (unsigned char *)&seed, sizeof(int32_t));
                     76:        MD4_Final(md, &ctx);
                     77: }
                     78:
                     79: /*
                     80:  * Hash an entire file.
                     81:  * This is similar to hash_slow() except the seed is hashed at the end
                     82:  * of the sequence, not the beginning.
                     83:  */
                     84: void
                     85: hash_file(const void *buf, size_t len,
                     86:        unsigned char *md, const struct sess *sess)
                     87: {
                     88:        MD4_CTX          ctx;
                     89:        int32_t          seed = htole32(sess->seed);
                     90:
                     91:        MD4_Init(&ctx);
                     92:        MD4_Update(&ctx, (unsigned char *)&seed, sizeof(int32_t));
                     93:        MD4_Update(&ctx, buf, len);
                     94:        MD4_Final(md, &ctx);
                     95: }