hash.c revision 1.3
1/* $Id: hash.c,v 1.3 2019/02/13 05:41:35 tb Exp $ */ 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 <openssl/md4.h> 25 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 */ 33uint32_t 34hash_fast(const void *buf, size_t len) 35{ 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; 40 41 if (len > 4) 42 for ( ; i < len - 4; i += 4) { 43 b += 4 * (a + dat[i]) + 44 3 * dat[i + 1] + 45 2 * dat[i + 2] + 46 dat[i + 3]; 47 a += dat[i + 0] + 48 dat[i + 1] + 49 dat[i + 2] + 50 dat[i + 3]; 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 */ 66void 67hash_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 */ 84void 85hash_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} 96