Return to hash.c CVS log

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

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

1.1       benno       1: /*     $Id$ */
                      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:
                     24: #include "extern.h"
                     25: #include "md4.h"
                     26:
                     27: /*
                     28:  * A fast 32-bit hash.
                     29:  * Described in Tridgell's "Efficient Algorithms for Sorting and
                     30:  * Synchronization" thesis and the "Rolling checksum" document.
                     31:  */
                     32: uint32_t
                     33: hash_fast(const void *buf, size_t len)
                     34: {
1.2     ! benno      35:        size_t                   i = 0;
        !            36:        uint32_t                 a = 0, /* part of a(k, l) */
        !            37:                                 b = 0; /* b(k, l) */
        !            38:        const signed char       *dat = buf;
1.1       benno      39:
                     40:        if (len > 4)
                     41:                for ( ; i < len - 4; i += 4) {
                     42:                        b += 4 * (a + dat[i]) +
1.2     ! benno      43:                            3 * dat[i + 1] +
        !            44:                            2 * dat[i + 2] +
        !            45:                            dat[i + 3];
1.1       benno      46:                        a += dat[i + 0] +
1.2     ! benno      47:                            dat[i + 1] +
        !            48:                            dat[i + 2] +
        !            49:                            dat[i + 3];
1.1       benno      50:                }
                     51:
                     52:        for ( ; i < len; i++) {
                     53:                a += dat[i];
                     54:                b += a;
                     55:        }
                     56:
                     57:        /* s(k, l) = (eps % M) + 2^16 b(k, l) % M */
                     58:
                     59:        return (a & 0xffff) + (b << 16);
                     60: }
                     61:
                     62: /*
                     63:  * Slow MD4-based hash with trailing seed.
                     64:  */
                     65: void
                     66: hash_slow(const void *buf, size_t len,
                     67:        unsigned char *md, const struct sess *sess)
                     68: {
                     69:        MD4_CTX          ctx;
                     70:        int32_t          seed = htole32(sess->seed);
                     71:
                     72:        MD4_Init(&ctx);
                     73:        MD4_Update(&ctx, buf, len);
                     74:        MD4_Update(&ctx, (unsigned char *)&seed, sizeof(int32_t));
                     75:        MD4_Final(md, &ctx);
                     76: }
                     77:
                     78: /*
                     79:  * Hash an entire file.
                     80:  * This is similar to hash_slow() except the seed is hashed at the end
                     81:  * of the sequence, not the beginning.
                     82:  */
                     83: void
                     84: hash_file(const void *buf, size_t len,
                     85:        unsigned char *md, const struct sess *sess)
                     86: {
                     87:        MD4_CTX          ctx;
                     88:        int32_t          seed = htole32(sess->seed);
                     89:
                     90:        MD4_Init(&ctx);
                     91:        MD4_Update(&ctx, (unsigned char *)&seed, sizeof(int32_t));
                     92:        MD4_Update(&ctx, buf, len);
                     93:        MD4_Final(md, &ctx);
                     94: }