hash.c revision 1.1
1/* $Id: hash.c,v 1.1 2019/02/10 23:18:28 benno 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 "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 */ 32uint32_t 33hash_fast(const void *buf, size_t len) 34{ 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; 39 40 if (len > 4) 41 for ( ; i < len - 4; i += 4) { 42 b += 4 * (a + dat[i]) + 43 3 * dat[i + 1] + 44 2 * dat[i + 2] + 45 dat[i + 3]; 46 a += dat[i + 0] + 47 dat[i + 1] + 48 dat[i + 2] + 49 dat[i + 3]; 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 */ 65void 66hash_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 */ 83void 84hash_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} 95