[J-u-boot.git] / lib / xxhash.c

// SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
/*
 * xxHash - Extremely Fast Hash algorithm
 * Copyright (C) 2012-2016, Yann Collet.
 *
 * You can contact the author at:
 * - xxHash homepage: http://cyan4973.github.io/xxHash/
 * - xxHash source repository: https://github.com/Cyan4973/xxHash
 */

#include <asm/unaligned.h>
#include <linux/errno.h>
#include <linux/compiler.h>
#include <linux/kernel.h>
#include <linux/compat.h>
#include <linux/string.h>
#include <linux/xxhash.h>

/*-*************************************
 * Macros
 **************************************/
#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
#define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))

#ifdef __LITTLE_ENDIAN
# define XXH_CPU_LITTLE_ENDIAN 1
#else
# define XXH_CPU_LITTLE_ENDIAN 0
#endif

/*-*************************************
 * Constants
 **************************************/
static const uint32_t PRIME32_1 = 2654435761U;
static const uint32_t PRIME32_2 = 2246822519U;
static const uint32_t PRIME32_3 = 3266489917U;
static const uint32_t PRIME32_4 =  668265263U;
static const uint32_t PRIME32_5 =  374761393U;

static const uint64_t PRIME64_1 = 11400714785074694791ULL;
static const uint64_t PRIME64_2 = 14029467366897019727ULL;
static const uint64_t PRIME64_3 =  1609587929392839161ULL;
static const uint64_t PRIME64_4 =  9650029242287828579ULL;
static const uint64_t PRIME64_5 =  2870177450012600261ULL;

/*-**************************
 *  Utils
 ***************************/
void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)
{
	memcpy(dst, src, sizeof(*dst));
}
EXPORT_SYMBOL(xxh32_copy_state);

void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
{
	memcpy(dst, src, sizeof(*dst));
}
EXPORT_SYMBOL(xxh64_copy_state);

/*-***************************
 * Simple Hash Functions
 ****************************/
static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
{
	seed += input * PRIME32_2;
	seed = xxh_rotl32(seed, 13);
	seed *= PRIME32_1;
	return seed;
}

uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
{
	const uint8_t *p = (const uint8_t *)input;
	const uint8_t *b_end = p + len;
	uint32_t h32;

	if (len >= 16) {
		const uint8_t *const limit = b_end - 16;
		uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
		uint32_t v2 = seed + PRIME32_2;
		uint32_t v3 = seed + 0;
		uint32_t v4 = seed - PRIME32_1;

		do {
			v1 = xxh32_round(v1, get_unaligned_le32(p));
			p += 4;
			v2 = xxh32_round(v2, get_unaligned_le32(p));
			p += 4;
			v3 = xxh32_round(v3, get_unaligned_le32(p));
			p += 4;
			v4 = xxh32_round(v4, get_unaligned_le32(p));
			p += 4;
		} while (p <= limit);

		h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
			xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
	} else {
		h32 = seed + PRIME32_5;
	}

	h32 += (uint32_t)len;

	while (p + 4 <= b_end) {
		h32 += get_unaligned_le32(p) * PRIME32_3;
		h32 = xxh_rotl32(h32, 17) * PRIME32_4;
		p += 4;
	}

	while (p < b_end) {
		h32 += (*p) * PRIME32_5;
		h32 = xxh_rotl32(h32, 11) * PRIME32_1;
		p++;
	}

	h32 ^= h32 >> 15;
	h32 *= PRIME32_2;
	h32 ^= h32 >> 13;
	h32 *= PRIME32_3;
	h32 ^= h32 >> 16;

	return h32;
}
EXPORT_SYMBOL(xxh32);

static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
{
	acc += input * PRIME64_2;
	acc = xxh_rotl64(acc, 31);
	acc *= PRIME64_1;
	return acc;
}

static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
{
	val = xxh64_round(0, val);
	acc ^= val;
	acc = acc * PRIME64_1 + PRIME64_4;
	return acc;
}

uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
{
	const uint8_t *p = (const uint8_t *)input;
	const uint8_t *const b_end = p + len;
	uint64_t h64;

	if (len >= 32) {
		const uint8_t *const limit = b_end - 32;
		uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
		uint64_t v2 = seed + PRIME64_2;
		uint64_t v3 = seed + 0;
		uint64_t v4 = seed - PRIME64_1;

		do {
			v1 = xxh64_round(v1, get_unaligned_le64(p));
			p += 8;
			v2 = xxh64_round(v2, get_unaligned_le64(p));
			p += 8;
			v3 = xxh64_round(v3, get_unaligned_le64(p));
			p += 8;
			v4 = xxh64_round(v4, get_unaligned_le64(p));
			p += 8;
		} while (p <= limit);

		h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
			xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
		h64 = xxh64_merge_round(h64, v1);
		h64 = xxh64_merge_round(h64, v2);
		h64 = xxh64_merge_round(h64, v3);
		h64 = xxh64_merge_round(h64, v4);

	} else {
		h64  = seed + PRIME64_5;
	}

	h64 += (uint64_t)len;

	while (p + 8 <= b_end) {
		const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));

		h64 ^= k1;
		h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
		p += 8;
	}

	if (p + 4 <= b_end) {
		h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
		h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
		p += 4;
	}

	while (p < b_end) {
		h64 ^= (*p) * PRIME64_5;
		h64 = xxh_rotl64(h64, 11) * PRIME64_1;
		p++;
	}

	h64 ^= h64 >> 33;
	h64 *= PRIME64_2;
	h64 ^= h64 >> 29;
	h64 *= PRIME64_3;
	h64 ^= h64 >> 32;

	return h64;
}
EXPORT_SYMBOL(xxh64);

/*-**************************************************
 * Advanced Hash Functions
 ***************************************************/
void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
{
	/* use a local state for memcpy() to avoid strict-aliasing warnings */
	struct xxh32_state state;

	memset(&state, 0, sizeof(state));
	state.v1 = seed + PRIME32_1 + PRIME32_2;
	state.v2 = seed + PRIME32_2;
	state.v3 = seed + 0;
	state.v4 = seed - PRIME32_1;
	memcpy(statePtr, &state, sizeof(state));
}
EXPORT_SYMBOL(xxh32_reset);

void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
{
	/* use a local state for memcpy() to avoid strict-aliasing warnings */
	struct xxh64_state state;

	memset(&state, 0, sizeof(state));
	state.v1 = seed + PRIME64_1 + PRIME64_2;
	state.v2 = seed + PRIME64_2;
	state.v3 = seed + 0;
	state.v4 = seed - PRIME64_1;
	memcpy(statePtr, &state, sizeof(state));
}
EXPORT_SYMBOL(xxh64_reset);

int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
{
	const uint8_t *p = (const uint8_t *)input;
	const uint8_t *const b_end = p + len;

	if (input == NULL)
		return -EINVAL;

	state->total_len_32 += (uint32_t)len;
	state->large_len |= (len >= 16) | (state->total_len_32 >= 16);

	if (state->memsize + len < 16) { /* fill in tmp buffer */
		memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
		state->memsize += (uint32_t)len;
		return 0;
	}

	if (state->memsize) { /* some data left from previous update */
		const uint32_t *p32 = state->mem32;

		memcpy((uint8_t *)(state->mem32) + state->memsize, input,
			16 - state->memsize);

		state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
		p32++;
		state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
		p32++;
		state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
		p32++;
		state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
		p32++;

		p += 16-state->memsize;
		state->memsize = 0;
	}

	if (p <= b_end - 16) {
		const uint8_t *const limit = b_end - 16;
		uint32_t v1 = state->v1;
		uint32_t v2 = state->v2;
		uint32_t v3 = state->v3;
		uint32_t v4 = state->v4;

		do {
			v1 = xxh32_round(v1, get_unaligned_le32(p));
			p += 4;
			v2 = xxh32_round(v2, get_unaligned_le32(p));
			p += 4;
			v3 = xxh32_round(v3, get_unaligned_le32(p));
			p += 4;
			v4 = xxh32_round(v4, get_unaligned_le32(p));
			p += 4;
		} while (p <= limit);

		state->v1 = v1;
		state->v2 = v2;
		state->v3 = v3;
		state->v4 = v4;
	}

	if (p < b_end) {
		memcpy(state->mem32, p, (size_t)(b_end-p));
		state->memsize = (uint32_t)(b_end-p);
	}

	return 0;
}
EXPORT_SYMBOL(xxh32_update);

uint32_t xxh32_digest(const struct xxh32_state *state)
{
	const uint8_t *p = (const uint8_t *)state->mem32;
	const uint8_t *const b_end = (const uint8_t *)(state->mem32) +
		state->memsize;
	uint32_t h32;

	if (state->large_len) {
		h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
			xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
	} else {
		h32 = state->v3 /* == seed */ + PRIME32_5;
	}

	h32 += state->total_len_32;

	while (p + 4 <= b_end) {
		h32 += get_unaligned_le32(p) * PRIME32_3;
		h32 = xxh_rotl32(h32, 17) * PRIME32_4;
		p += 4;
	}

	while (p < b_end) {
		h32 += (*p) * PRIME32_5;
		h32 = xxh_rotl32(h32, 11) * PRIME32_1;
		p++;
	}

	h32 ^= h32 >> 15;
	h32 *= PRIME32_2;
	h32 ^= h32 >> 13;
	h32 *= PRIME32_3;
	h32 ^= h32 >> 16;

	return h32;
}
EXPORT_SYMBOL(xxh32_digest);

int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
{
	const uint8_t *p = (const uint8_t *)input;
	const uint8_t *const b_end = p + len;

	if (input == NULL)
		return -EINVAL;

	state->total_len += len;

	if (state->memsize + len < 32) { /* fill in tmp buffer */
		memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
		state->memsize += (uint32_t)len;
		return 0;
	}

	if (state->memsize) { /* tmp buffer is full */
		uint64_t *p64 = state->mem64;

		memcpy(((uint8_t *)p64) + state->memsize, input,
			32 - state->memsize);

		state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
		p64++;
		state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
		p64++;
		state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
		p64++;
		state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));

		p += 32 - state->memsize;
		state->memsize = 0;
	}

	if (p + 32 <= b_end) {
		const uint8_t *const limit = b_end - 32;
		uint64_t v1 = state->v1;
		uint64_t v2 = state->v2;
		uint64_t v3 = state->v3;
		uint64_t v4 = state->v4;

		do {
			v1 = xxh64_round(v1, get_unaligned_le64(p));
			p += 8;
			v2 = xxh64_round(v2, get_unaligned_le64(p));
			p += 8;
			v3 = xxh64_round(v3, get_unaligned_le64(p));
			p += 8;
			v4 = xxh64_round(v4, get_unaligned_le64(p));
			p += 8;
		} while (p <= limit);

		state->v1 = v1;
		state->v2 = v2;
		state->v3 = v3;
		state->v4 = v4;
	}

	if (p < b_end) {
		memcpy(state->mem64, p, (size_t)(b_end-p));
		state->memsize = (uint32_t)(b_end - p);
	}

	return 0;
}
EXPORT_SYMBOL(xxh64_update);

uint64_t xxh64_digest(const struct xxh64_state *state)
{
	const uint8_t *p = (const uint8_t *)state->mem64;
	const uint8_t *const b_end = (const uint8_t *)state->mem64 +
		state->memsize;
	uint64_t h64;

	if (state->total_len >= 32) {
		const uint64_t v1 = state->v1;
		const uint64_t v2 = state->v2;
		const uint64_t v3 = state->v3;
		const uint64_t v4 = state->v4;

		h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
			xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
		h64 = xxh64_merge_round(h64, v1);
		h64 = xxh64_merge_round(h64, v2);
		h64 = xxh64_merge_round(h64, v3);
		h64 = xxh64_merge_round(h64, v4);
	} else {
		h64  = state->v3 + PRIME64_5;
	}

	h64 += (uint64_t)state->total_len;

	while (p + 8 <= b_end) {
		const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));

		h64 ^= k1;
		h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
		p += 8;
	}

	if (p + 4 <= b_end) {
		h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
		h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
		p += 4;
	}

	while (p < b_end) {
		h64 ^= (*p) * PRIME64_5;
		h64 = xxh_rotl64(h64, 11) * PRIME64_1;
		p++;
	}

	h64 ^= h64 >> 33;
	h64 *= PRIME64_2;
	h64 ^= h64 >> 29;
	h64 *= PRIME64_3;
	h64 ^= h64 >> 32;

	return h64;
}
EXPORT_SYMBOL(xxh64_digest);
Commit	Line	Data
83a486b6 MB	1	// SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
	2	/*
	3	* xxHash - Extremely Fast Hash algorithm
	4	* Copyright (C) 2012-2016, Yann Collet.
	5	*
	6	* You can contact the author at:
	7	* - xxHash homepage: http://cyan4973.github.io/xxHash/
	8	* - xxHash source repository: https://github.com/Cyan4973/xxHash
	9	*/
	10
	11	#include <asm/unaligned.h>
	12	#include <linux/errno.h>
	13	#include <linux/compiler.h>
	14	#include <linux/kernel.h>
	15	#include <linux/compat.h>
	16	#include <linux/string.h>
	17	#include <linux/xxhash.h>
	18
	19	/-************************************
	20	* Macros
	21	**************************************/
	22	#define xxh_rotl32(x, r) ((x << r) \| (x >> (32 - r)))
	23	#define xxh_rotl64(x, r) ((x << r) \| (x >> (64 - r)))
	24
	25	#ifdef __LITTLE_ENDIAN
	26	# define XXH_CPU_LITTLE_ENDIAN 1
	27	#else
	28	# define XXH_CPU_LITTLE_ENDIAN 0
	29	#endif
	30
	31	/-************************************
	32	* Constants
	33	**************************************/
	34	static const uint32_t PRIME32_1 = 2654435761U;
	35	static const uint32_t PRIME32_2 = 2246822519U;
	36	static const uint32_t PRIME32_3 = 3266489917U;
	37	static const uint32_t PRIME32_4 = 668265263U;
	38	static const uint32_t PRIME32_5 = 374761393U;
	39
	40	static const uint64_t PRIME64_1 = 11400714785074694791ULL;
	41	static const uint64_t PRIME64_2 = 14029467366897019727ULL;
	42	static const uint64_t PRIME64_3 = 1609587929392839161ULL;
	43	static const uint64_t PRIME64_4 = 9650029242287828579ULL;
	44	static const uint64_t PRIME64_5 = 2870177450012600261ULL;
	45
	46	/-*************************
	47	* Utils
	48	***************************/
	49	void xxh32_copy_state(struct xxh32_state dst, const struct xxh32_state src)
	50	{
	51	memcpy(dst, src, sizeof(*dst));
	52	}
	53	EXPORT_SYMBOL(xxh32_copy_state);
	54
	55	void xxh64_copy_state(struct xxh64_state dst, const struct xxh64_state src)
	56	{
	57	memcpy(dst, src, sizeof(*dst));
	58	}
	59	EXPORT_SYMBOL(xxh64_copy_state);
	60
	61	/-**************************
	62	* Simple Hash Functions
	63	****************************/
	64	static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
65	{
66	seed += input * PRIME32_2;
67	seed = xxh_rotl32(seed, 13);
68	seed *= PRIME32_1;
69	return seed;
70	}
71
72	uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
73	{
74	const uint8_t p = (const uint8_t )input;
75	const uint8_t *b_end = p + len;
76	uint32_t h32;
77
78	if (len >= 16) {
79	const uint8_t *const limit = b_end - 16;
80	uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
81	uint32_t v2 = seed + PRIME32_2;
82	uint32_t v3 = seed + 0;
83	uint32_t v4 = seed - PRIME32_1;
84
85	do {
86	v1 = xxh32_round(v1, get_unaligned_le32(p));
87	p += 4;
88	v2 = xxh32_round(v2, get_unaligned_le32(p));
89	p += 4;
90	v3 = xxh32_round(v3, get_unaligned_le32(p));
91	p += 4;
92	v4 = xxh32_round(v4, get_unaligned_le32(p));
93	p += 4;
94	} while (p <= limit);
95
96	h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
97	xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
98	} else {
99	h32 = seed + PRIME32_5;
100	}
101
102	h32 += (uint32_t)len;
103
104	while (p + 4 <= b_end) {
105	h32 += get_unaligned_le32(p) * PRIME32_3;
106	h32 = xxh_rotl32(h32, 17) * PRIME32_4;
107	p += 4;
108	}
109
110	while (p < b_end) {
111	h32 += (p) PRIME32_5;
112	h32 = xxh_rotl32(h32, 11) * PRIME32_1;
113	p++;
114	}
115
116	h32 ^= h32 >> 15;
117	h32 *= PRIME32_2;
118	h32 ^= h32 >> 13;
119	h32 *= PRIME32_3;
120	h32 ^= h32 >> 16;
121
122	return h32;
123	}
124	EXPORT_SYMBOL(xxh32);
125
126	static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
127	{
128	acc += input * PRIME64_2;
129	acc = xxh_rotl64(acc, 31);
130	acc *= PRIME64_1;
131	return acc;
132	}
133
134	static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
135	{
136	val = xxh64_round(0, val);
137	acc ^= val;
138	acc = acc * PRIME64_1 + PRIME64_4;
139	return acc;
140	}
141
142	uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
143	{
144	const uint8_t p = (const uint8_t )input;
145	const uint8_t *const b_end = p + len;
146	uint64_t h64;
147
148	if (len >= 32) {
149	const uint8_t *const limit = b_end - 32;
150	uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
151	uint64_t v2 = seed + PRIME64_2;
152	uint64_t v3 = seed + 0;
153	uint64_t v4 = seed - PRIME64_1;
154
155	do {
156	v1 = xxh64_round(v1, get_unaligned_le64(p));
157	p += 8;
158	v2 = xxh64_round(v2, get_unaligned_le64(p));
159	p += 8;
160	v3 = xxh64_round(v3, get_unaligned_le64(p));
161	p += 8;
162	v4 = xxh64_round(v4, get_unaligned_le64(p));
163	p += 8;
164	} while (p <= limit);
165
166	h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
167	xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
168	h64 = xxh64_merge_round(h64, v1);
169	h64 = xxh64_merge_round(h64, v2);
170	h64 = xxh64_merge_round(h64, v3);
171	h64 = xxh64_merge_round(h64, v4);
172
173	} else {
174	h64 = seed + PRIME64_5;
175	}
176
177	h64 += (uint64_t)len;
178
179	while (p + 8 <= b_end) {
180	const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
181
182	h64 ^= k1;
183	h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
184	p += 8;
185	}
186
187	if (p + 4 <= b_end) {
188	h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
189	h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
190	p += 4;
191	}
192
193	while (p < b_end) {
194	h64 ^= (p) PRIME64_5;
195	h64 = xxh_rotl64(h64, 11) * PRIME64_1;
196	p++;
197	}
198
199	h64 ^= h64 >> 33;
200	h64 *= PRIME64_2;
201	h64 ^= h64 >> 29;
202	h64 *= PRIME64_3;
203	h64 ^= h64 >> 32;
204
205	return h64;
206	}
207	EXPORT_SYMBOL(xxh64);
208
209	/-*************************************************
210	* Advanced Hash Functions
211	***************************************************/
212	void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
213	{
214	/* use a local state for memcpy() to avoid strict-aliasing warnings */
215	struct xxh32_state state;
216
217	memset(&state, 0, sizeof(state));
218	state.v1 = seed + PRIME32_1 + PRIME32_2;
219	state.v2 = seed + PRIME32_2;
220	state.v3 = seed + 0;
221	state.v4 = seed - PRIME32_1;
222	memcpy(statePtr, &state, sizeof(state));
223	}
224	EXPORT_SYMBOL(xxh32_reset);
225
226	void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
227	{
228	/* use a local state for memcpy() to avoid strict-aliasing warnings */
229	struct xxh64_state state;
230
231	memset(&state, 0, sizeof(state));
232	state.v1 = seed + PRIME64_1 + PRIME64_2;
233	state.v2 = seed + PRIME64_2;
234	state.v3 = seed + 0;
235	state.v4 = seed - PRIME64_1;
236	memcpy(statePtr, &state, sizeof(state));
237	}
238	EXPORT_SYMBOL(xxh64_reset);
239
240	int xxh32_update(struct xxh32_state state, const void input, const size_t len)
241	{
242	const uint8_t p = (const uint8_t )input;
243	const uint8_t *const b_end = p + len;
244
245	if (input == NULL)
246	return -EINVAL;
247
248	state->total_len_32 += (uint32_t)len;
249	state->large_len \|= (len >= 16) \| (state->total_len_32 >= 16);
250
251	if (state->memsize + len < 16) { /* fill in tmp buffer */
252	memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
253	state->memsize += (uint32_t)len;
254	return 0;
255	}
256
257	if (state->memsize) { /* some data left from previous update */
258	const uint32_t *p32 = state->mem32;
259
260	memcpy((uint8_t *)(state->mem32) + state->memsize, input,
261	16 - state->memsize);
262
263	state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
264	p32++;
265	state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
266	p32++;
267	state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
268	p32++;
269	state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
270	p32++;
271
272	p += 16-state->memsize;
273	state->memsize = 0;
274	}
275
276	if (p <= b_end - 16) {
277	const uint8_t *const limit = b_end - 16;
278	uint32_t v1 = state->v1;
279	uint32_t v2 = state->v2;
280	uint32_t v3 = state->v3;
281	uint32_t v4 = state->v4;
282
283	do {
284	v1 = xxh32_round(v1, get_unaligned_le32(p));
285	p += 4;
286	v2 = xxh32_round(v2, get_unaligned_le32(p));
287	p += 4;
288	v3 = xxh32_round(v3, get_unaligned_le32(p));
289	p += 4;
290	v4 = xxh32_round(v4, get_unaligned_le32(p));
291	p += 4;
292	} while (p <= limit);
293
294	state->v1 = v1;
295	state->v2 = v2;
296	state->v3 = v3;
297	state->v4 = v4;
298	}
299
300	if (p < b_end) {
301	memcpy(state->mem32, p, (size_t)(b_end-p));
302	state->memsize = (uint32_t)(b_end-p);
303	}
304
305	return 0;
306	}
307	EXPORT_SYMBOL(xxh32_update);
308
309	uint32_t xxh32_digest(const struct xxh32_state *state)
310	{
311	const uint8_t p = (const uint8_t )state->mem32;
312	const uint8_t const b_end = (const uint8_t )(state->mem32) +
313	state->memsize;
314	uint32_t h32;
315
316	if (state->large_len) {
317	h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
318	xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
319	} else {
320	h32 = state->v3 /* == seed */ + PRIME32_5;
321	}
322
323	h32 += state->total_len_32;
324
325	while (p + 4 <= b_end) {
326	h32 += get_unaligned_le32(p) * PRIME32_3;
327	h32 = xxh_rotl32(h32, 17) * PRIME32_4;
328	p += 4;
329	}
330
331	while (p < b_end) {
332	h32 += (p) PRIME32_5;
333	h32 = xxh_rotl32(h32, 11) * PRIME32_1;
334	p++;
335	}
336
337	h32 ^= h32 >> 15;
338	h32 *= PRIME32_2;
339	h32 ^= h32 >> 13;
340	h32 *= PRIME32_3;
341	h32 ^= h32 >> 16;
342
343	return h32;
344	}
345	EXPORT_SYMBOL(xxh32_digest);
346
347	int xxh64_update(struct xxh64_state state, const void input, const size_t len)
348	{
349	const uint8_t p = (const uint8_t )input;
350	const uint8_t *const b_end = p + len;
351
352	if (input == NULL)
353	return -EINVAL;
354
355	state->total_len += len;
356
357	if (state->memsize + len < 32) { /* fill in tmp buffer */
358	memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
359	state->memsize += (uint32_t)len;
360	return 0;
361	}
362
363	if (state->memsize) { /* tmp buffer is full */
364	uint64_t *p64 = state->mem64;
365
366	memcpy(((uint8_t *)p64) + state->memsize, input,
367	32 - state->memsize);
368
369	state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
370	p64++;
371	state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
372	p64++;
373	state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
374	p64++;
375	state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));
376
377	p += 32 - state->memsize;
378	state->memsize = 0;
379	}
380
381	if (p + 32 <= b_end) {
382	const uint8_t *const limit = b_end - 32;
383	uint64_t v1 = state->v1;
384	uint64_t v2 = state->v2;
385	uint64_t v3 = state->v3;
386	uint64_t v4 = state->v4;
387
388	do {
389	v1 = xxh64_round(v1, get_unaligned_le64(p));
390	p += 8;
391	v2 = xxh64_round(v2, get_unaligned_le64(p));
392	p += 8;
393	v3 = xxh64_round(v3, get_unaligned_le64(p));
394	p += 8;
395	v4 = xxh64_round(v4, get_unaligned_le64(p));
396	p += 8;
397	} while (p <= limit);
398
399	state->v1 = v1;
400	state->v2 = v2;
401	state->v3 = v3;
402	state->v4 = v4;
403	}
404
405	if (p < b_end) {
406	memcpy(state->mem64, p, (size_t)(b_end-p));
407	state->memsize = (uint32_t)(b_end - p);
408	}
409
410	return 0;
411	}
412	EXPORT_SYMBOL(xxh64_update);
413
414	uint64_t xxh64_digest(const struct xxh64_state *state)
415	{
416	const uint8_t p = (const uint8_t )state->mem64;
417	const uint8_t const b_end = (const uint8_t )state->mem64 +
418	state->memsize;
419	uint64_t h64;
420
421	if (state->total_len >= 32) {
422	const uint64_t v1 = state->v1;
423	const uint64_t v2 = state->v2;
424	const uint64_t v3 = state->v3;
425	const uint64_t v4 = state->v4;
426
427	h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
428	xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
429	h64 = xxh64_merge_round(h64, v1);
430	h64 = xxh64_merge_round(h64, v2);
431	h64 = xxh64_merge_round(h64, v3);
432	h64 = xxh64_merge_round(h64, v4);
433	} else {
434	h64 = state->v3 + PRIME64_5;
435	}
436
437	h64 += (uint64_t)state->total_len;
438
439	while (p + 8 <= b_end) {
440	const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
441
442	h64 ^= k1;
443	h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
444	p += 8;
445	}
446
447	if (p + 4 <= b_end) {
448	h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
449	h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
450	p += 4;
451	}
452
453	while (p < b_end) {
454	h64 ^= (p) PRIME64_5;
455	h64 = xxh_rotl64(h64, 11) * PRIME64_1;
456	p++;
457	}
458
459	h64 ^= h64 >> 33;
460	h64 *= PRIME64_2;
461	h64 ^= h64 >> 29;
462	h64 *= PRIME64_3;
463	h64 ^= h64 >> 32;
464
465	return h64;
466	}
467	EXPORT_SYMBOL(xxh64_digest);