GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/hash/siphash.c Lines: 0 63 0.0 %
Date: 2017-11-13 Branches: 0 12 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: siphash.c,v 1.6 2017/04/12 17:41:49 deraadt Exp $ */
2
3
/*-
4
 * Copyright (c) 2013 Andre Oppermann <andre@FreeBSD.org>
5
 * All rights reserved.
6
 *
7
 * Redistribution and use in source and binary forms, with or without
8
 * modification, are permitted provided that the following conditions
9
 * are met:
10
 * 1. Redistributions of source code must retain the above copyright
11
 *    notice, this list of conditions and the following disclaimer.
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in the
14
 *    documentation and/or other materials provided with the distribution.
15
 * 3. The name of the author may not be used to endorse or promote
16
 *    products derived from this software without specific prior written
17
 *    permission.
18
 *
19
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29
 * SUCH DAMAGE.
30
 */
31
32
/*
33
 * SipHash is a family of PRFs SipHash-c-d where the integer parameters c and d
34
 * are the number of compression rounds and the number of finalization rounds.
35
 * A compression round is identical to a finalization round and this round
36
 * function is called SipRound.  Given a 128-bit key k and a (possibly empty)
37
 * byte string m, SipHash-c-d returns a 64-bit value SipHash-c-d(k; m).
38
 *
39
 * Implemented from the paper "SipHash: a fast short-input PRF", 2012.09.18,
40
 * by Jean-Philippe Aumasson and Daniel J. Bernstein,
41
 * Permanent Document ID b9a943a805fbfc6fde808af9fc0ecdfa
42
 * https://131002.net/siphash/siphash.pdf
43
 * https://131002.net/siphash/
44
 */
45
46
#include <sys/types.h>
47
#include <sys/endian.h>
48
49
#include <string.h>
50
#include <siphash.h>
51
52
static void	SipHash_CRounds(SIPHASH_CTX *, int);
53
static void	SipHash_Rounds(SIPHASH_CTX *, int);
54
55
void
56
SipHash_Init(SIPHASH_CTX *ctx, const SIPHASH_KEY *key)
57
{
58
	uint64_t k0, k1;
59
60
	k0 = le64toh(key->k0);
61
	k1 = le64toh(key->k1);
62
63
	ctx->v[0] = 0x736f6d6570736575ULL ^ k0;
64
	ctx->v[1] = 0x646f72616e646f6dULL ^ k1;
65
	ctx->v[2] = 0x6c7967656e657261ULL ^ k0;
66
	ctx->v[3] = 0x7465646279746573ULL ^ k1;
67
68
	memset(ctx->buf, 0, sizeof(ctx->buf));
69
	ctx->bytes = 0;
70
}
71
DEF_WEAK(SipHash_Init);
72
73
void
74
SipHash_Update(SIPHASH_CTX *ctx, int rc, int rf, const void *src, size_t len)
75
{
76
	const uint8_t *ptr = src;
77
	size_t left, used;
78
79
	if (len == 0)
80
		return;
81
82
	used = ctx->bytes % sizeof(ctx->buf);
83
	ctx->bytes += len;
84
85
	if (used > 0) {
86
		left = sizeof(ctx->buf) - used;
87
88
		if (len >= left) {
89
			memcpy(&ctx->buf[used], ptr, left);
90
			SipHash_CRounds(ctx, rc);
91
			len -= left;
92
			ptr += left;
93
		} else {
94
			memcpy(&ctx->buf[used], ptr, len);
95
			return;
96
		}
97
	}
98
99
	while (len >= sizeof(ctx->buf)) {
100
		memcpy(ctx->buf, ptr, sizeof(ctx->buf));
101
		SipHash_CRounds(ctx, rc);
102
		len -= sizeof(ctx->buf);
103
		ptr += sizeof(ctx->buf);
104
	}
105
106
	if (len > 0)
107
		memcpy(&ctx->buf[used], ptr, len);
108
}
109
DEF_WEAK(SipHash_Update);
110
111
void
112
SipHash_Final(void *dst, SIPHASH_CTX *ctx, int rc, int rf)
113
{
114
	uint64_t r;
115
116
	r = htole64(SipHash_End(ctx, rc, rf));
117
	memcpy(dst, &r, sizeof r);
118
}
119
DEF_WEAK(SipHash_Final);
120
121
uint64_t
122
SipHash_End(SIPHASH_CTX *ctx, int rc, int rf)
123
{
124
	uint64_t r;
125
	size_t left, used;
126
127
	used = ctx->bytes % sizeof(ctx->buf);
128
	left = sizeof(ctx->buf) - used;
129
	memset(&ctx->buf[used], 0, left - 1);
130
	ctx->buf[7] = ctx->bytes;
131
132
	SipHash_CRounds(ctx, rc);
133
	ctx->v[2] ^= 0xff;
134
	SipHash_Rounds(ctx, rf);
135
136
	r = (ctx->v[0] ^ ctx->v[1]) ^ (ctx->v[2] ^ ctx->v[3]);
137
	explicit_bzero(ctx, sizeof(*ctx));
138
	return (r);
139
}
140
DEF_WEAK(SipHash_End);
141
142
uint64_t
143
SipHash(const SIPHASH_KEY *key, int rc, int rf, const void *src, size_t len)
144
{
145
	SIPHASH_CTX ctx;
146
147
	SipHash_Init(&ctx, key);
148
	SipHash_Update(&ctx, rc, rf, src, len);
149
	return (SipHash_End(&ctx, rc, rf));
150
}
151
DEF_WEAK(SipHash);
152
153
#define SIP_ROTL(x, b) ((x) << (b)) | ( (x) >> (64 - (b)))
154
155
static void
156
SipHash_Rounds(SIPHASH_CTX *ctx, int rounds)
157
{
158
	while (rounds--) {
159
		ctx->v[0] += ctx->v[1];
160
		ctx->v[2] += ctx->v[3];
161
		ctx->v[1] = SIP_ROTL(ctx->v[1], 13);
162
		ctx->v[3] = SIP_ROTL(ctx->v[3], 16);
163
164
		ctx->v[1] ^= ctx->v[0];
165
		ctx->v[3] ^= ctx->v[2];
166
		ctx->v[0] = SIP_ROTL(ctx->v[0], 32);
167
168
		ctx->v[2] += ctx->v[1];
169
		ctx->v[0] += ctx->v[3];
170
		ctx->v[1] = SIP_ROTL(ctx->v[1], 17);
171
		ctx->v[3] = SIP_ROTL(ctx->v[3], 21);
172
173
		ctx->v[1] ^= ctx->v[2];
174
		ctx->v[3] ^= ctx->v[0];
175
		ctx->v[2] = SIP_ROTL(ctx->v[2], 32);
176
	}
177
}
178
179
static void
180
SipHash_CRounds(SIPHASH_CTX *ctx, int rounds)
181
{
182
	uint64_t m = le64toh(*(uint64_t *)ctx->buf);
183
184
	ctx->v[3] ^= m;
185
	SipHash_Rounds(ctx, rounds);
186
	ctx->v[0] ^= m;
187
}