1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2012 Ed Schouten <ed@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 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29#include <sys/cdefs.h>
30__FBSDID("$FreeBSD$");
31
32#include <sys/libkern.h>
33#include <sys/limits.h>
34#include <sys/param.h>
35
36/*
37 * memcchr(): find first character in buffer not matching `c'.
38 *
39 * This function performs the complement of memchr().  To provide decent
40 * performance, this function compares data from the buffer one word at
41 * a time.
42 *
43 * This code is inspired by libc's strlen(), written by Xin Li.
44 */
45
46#if LONG_BIT != 32 && LONG_BIT != 64
47#error Unsupported word size
48#endif
49
50#define	LONGPTR_MASK (sizeof(long) - 1)
51
52#define	TESTBYTE				\
53	do {					\
54		if (*p != (unsigned char)c)	\
55			goto done;		\
56		p++;				\
57	} while (0)
58
59void *
60memcchr(const void *begin, int c, size_t n)
61{
62	const unsigned long *lp;
63	const unsigned char *p, *end;
64	unsigned long word;
65
66	/* Four or eight repetitions of `c'. */
67	word = (unsigned char)c;
68	word |= word << 8;
69	word |= word << 16;
70#if LONG_BIT >= 64
71	word |= word << 32;
72#endif
73
74	/* Don't perform memory I/O when passing a zero-length buffer. */
75	if (n == 0)
76		return (NULL);
77
78	/*
79	 * First determine whether there is a character unequal to `c'
80	 * in the first word.  As this word may contain bytes before
81	 * `begin', we may execute this loop spuriously.
82	 */
83	lp = (const unsigned long *)((uintptr_t)begin & ~LONGPTR_MASK);
84	end = (const unsigned char *)begin + n;
85	if (*lp++ != word)
86		for (p = begin; p < (const unsigned char *)lp;)
87			TESTBYTE;
88
89	/* Now compare the data one word at a time. */
90	for (; (const unsigned char *)lp < end; lp++) {
91		if (*lp != word) {
92			p = (const unsigned char *)lp;
93			TESTBYTE;
94			TESTBYTE;
95			TESTBYTE;
96#if LONG_BIT >= 64
97			TESTBYTE;
98			TESTBYTE;
99			TESTBYTE;
100			TESTBYTE;
101#endif
102			goto done;
103		}
104	}
105
106	return (NULL);
107
108done:
109	/*
110	 * If the end of the buffer is not word aligned, the previous
111	 * loops may obtain an address that's beyond the end of the
112	 * buffer.
113	 */
114	if (p < end)
115		return (__DECONST(void *, p));
116	return (NULL);
117}
118