Re: [PATCH 0/4] Refactor and expand string functions.

[Nathan McSween <nwmcsween@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1528 bytes --]

On 2/3/2013 4:12 PM, Nathan McSween wrote:
> memchr - refactor
> memcmp - word-at-a-time
> memset - refactor
> strcmp - word-at-a-time
> strlcpy - refactor and always terminate string
> strlen - refactor
> strncmp - word-at-a-time
>
> A simple wc -l on asm lines for changed files gives:
> 91 new_memchr.s
> 106 musl_memchr.s
> 65 new_memcmp.s
> 32 musl_memcmp.s
> 118 new_memset.s
> 121 musl_memset.s
> 64 new_strcmp.s
> 26 musl_strcmp.s
> 98 new_strlcpy.s
> 124 musl_strlcpy.s
> 55 new_strlen.s
> 55 musl_strlen.s
> 66 new_strncmp.s
> 45 musl_strncmp.s
>
> Bikeshed over inline documentation welcome.
>
> Nathan McSween (4):
>    Internal: Add word.h - word-at-a-time fns / macros
>    String: refactor to utilize word.h and optimize
>    String: expand to word-at-a-time
>    String: refactor to utilize word.h and always terminate string
>
>   src/internal/word.h  | 39 ++++++++++++++++++++++++++++++++++++
>   src/string/memchr.c  | 42 ++++++++++++++++++++++-----------------
>   src/string/memcmp.c  | 38 +++++++++++++++++++++++++++++++----
>   src/string/memset.c  | 39 +++++++++++++++++++++---------------
>   src/string/strcmp.c  | 35 +++++++++++++++++++++++++++++---
>   src/string/strlcpy.c | 56 ++++++++++++++++++++++++++++++----------------------
>   src/string/strlen.c  | 29 +++++++++++++++------------
>   src/string/strncmp.c | 36 ++++++++++++++++++++++++++++-----
>   8 files changed, 231 insertions(+), 83 deletions(-)
>   create mode 100644 src/internal/word.h
>
Attached are files of the functions changed.

[-- Attachment #2: memchr.c --]
[-- Type: text/plain, Size: 630 bytes --]

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "word.h"

/**
 * memchr - Word sized c standard memchr.
 * @s: Source
 * @c: Character
 * @n: Max size of @s
 */
void *memchr(const void *s, int c, size_t n)
{
	const unsigned char *cs = (const unsigned char *)s;
	const size_t *w;

	c = (unsigned char)c;

	for (; (uintptr_t)cs % sizeof(size_t); cs++, n--) {
		if (!n) return NULL;
		if (*cs == c) return (void *)cs;
	}

	for (w = (const size_t *)cs; !word_has_char(*w, c); w++, n--)
		if (!n) return NULL;
	for (cs = (const unsigned char *)w; *cs != c; cs++, n--)
		if (!n) return NULL;

	return (void *)cs;
}

[-- Attachment #3: memcmp.c --]
[-- Type: text/plain, Size: 837 bytes --]

#include <stddef.h>
#include <string.h>
#include "word.h"

/**
 * memcmp - Word sized c standard memcmp.
 * @s: Source
 * @c: Comparative
 * @n: Max size of @s
 */
int memcmp(const void *s, const void *c, size_t n)
{
	const unsigned char *cs = (const unsigned char *)s;
	const unsigned char *cc = (const unsigned char *)c;
	const size_t *ws, *wc;


	if ((uintptr_t)cs % sizeof(size_t) != (uintptr_t)cc % sizeof(size_t))
		goto misaligned;

	for (; (uintptr_t)cs % sizeof(size_t); cs++, cc++, n--) {
		if (!n) return 0;
		if (*cs == *cc) goto misaligned;
	}

	for (ws = (const size_t *)cs, wc = (const size_t *)cc
	     ; *ws == *wc && n
	     ; ws++, wc++, n -= sizeof(size_t));

	cs = (const unsigned char *)ws;
	cc = (const unsigned char *)wc;

misaligned:
	for(; *cs == *cc; cs++, cc++, n--)
		if (!n) return 0;

	return *cs - *cc;
}

[-- Attachment #4: memset.c --]
[-- Type: text/plain, Size: 608 bytes --]

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "word.h"

/**
 * memset - Word sized c standard memset.
 * @d: Destination
 * @c: Charater to set
 * @n: Max size to set to @c in @d
 */
void *memset(void *d, int c, size_t n)
{
	unsigned char *cd = (unsigned char *)d;
	const size_t wc = WORD_LSB_ONE * (unsigned char)c;
	size_t *wd;

	c = (unsigned char)c;

	for (; (uintptr_t)cd % sizeof(size_t); *cd++ = c, n--)
		if (!n) return d;

	for (wd = (size_t *)cd; n >= sizeof(size_t)
	     ; *wd++ = wc, n -= sizeof(size_t));
	for (cd = (unsigned char *)wd; n; *cd++ = c, n--);

	return d;
}

[-- Attachment #5: strcmp.c --]
[-- Type: text/plain, Size: 801 bytes --]

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "word.h"

/**
 * strcmp - Word sized c standard strcmp.
 * @c: Comparative
 * @s: Source
 */
#undef strcmp
int strcmp(const char *c, const char *s)
{
	const size_t *wc, *ws;

	if ((uintptr_t)c % sizeof(size_t) != (uintptr_t)s % sizeof(size_t))
		goto misaligned;

	for (; (uintptr_t)c % sizeof(size_t); c++, s++) {
		if (*c != *s || !*c || !*s)
			return *(const unsigned char *)c
			        - *(const unsigned char *)s;
	}

	for (wc = (const size_t *)c, ws = (const size_t *)s
	     ; (!word_has_zero(*wc) || !word_has_zero(*ws)) && *wc == *ws
	     ; wc++, ws++);

	c = (const char *)wc;
	s = (const char *)ws;

misaligned:
	for(; *c == *s && *c && *s; c++, s++);

	return *(const unsigned char *)c - *(const unsigned char *)s;
}

[-- Attachment #6: strlcpy.c --]
[-- Type: text/plain, Size: 795 bytes --]

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "word.h"

/**
 * strlcpy - Word sized bsd strlcpy.
 * @d: Destination
 * @s: Source
 * @n: Max @s
 */
size_t strlcpy(char *d, const char *s, size_t n)
{
	char *z = d;
	size_t *wd;
	const size_t *ws;

	/* A byte for nul */
	if (!n--) goto terminate;

	if ((uintptr_t)d % sizeof(size_t) != (uintptr_t)s % sizeof(size_t))
		goto misaligned;

	for (; (uintptr_t)s % sizeof(size_t); *d++ = *s++, n--)
		if (!*s || !n) goto terminate;

	for (wd = (size_t *)d, ws= (const size_t *)s
	     ; !word_has_zero(*ws) && n >= sizeof(size_t)
	     ; *wd = *ws, wd++, ws++, n -= sizeof(size_t))

	d = (char *)wd;
	s = (const char *)ws;

misaligned:
	for (; (*d = *s) && n; d++, s++, n--);
terminate:
	*d = '\0';

	return d - z + strlen(s);
}

[-- Attachment #7: strlen.c --]
[-- Type: text/plain, Size: 393 bytes --]

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "word.h"

/**
 * strlen - Word sized c standard strlen.
 * @s: Source
 */
size_t strlen(const char *s)
{
	const char *z = s;
	const size_t *w;

	for (; (uintptr_t)s % sizeof(size_t); s++)
		if (!*s) return s - z;

	for (w = (const size_t *)s; !word_has_zero(*w); w++);
	for (s = (const char *)w; *s; s++);

	return s - z;
}

[-- Attachment #8: strncmp.c --]
[-- Type: text/plain, Size: 800 bytes --]

#include <stdint.h>
#include <string.h>
#include "word.h"

/**
 * strncmp - Word sized c standard strncmp.
 * @c: Comparative
 * @s: Source
 * @n: Max size of @s
 */
int strncmp(const char *c, const char *s, size_t n)
{
	const size_t *wc, *ws;

	if ((uintptr_t)c % sizeof(size_t) != (uintptr_t)s % sizeof(size_t))
		goto misaligned;

	for (; (uintptr_t)c % sizeof(size_t); c++, s++, n--) {
		if (*c != *s || !*c || !*s || !n)
			return *(const unsigned char *)c
				- *(const unsigned char *)s;
	}

	for (wc = (const size_t *)c, ws = (const size_t *)s
	     ; !word_has_zero(*wc) || !word_has_zero(*ws)
	     ; wc++, ws++);

	c = (const char *)wc;
	s = (const char *)ws;

misaligned:
	for(; *c == *s && *c && *s && n; c++, s++, n--);

	return *(const unsigned char *)c - *(const unsigned char *)s;
}

[-- Attachment #9: word.h --]
[-- Type: text/plain, Size: 825 bytes --]

/**
 * _INTERNAL_WORD_H - various word size functions / macros
 */
#ifndef _MYOSIN_WORD_H
#define _MYOSIN_WORD_H

#include <stddef.h>
#include <stdint.h>

/**
 * WORD_LSB_ONE - Set low bit of each byte on arch word size to one.
 */
#define WORD_LSB_ONE ((size_t)-1 / (unsigned char)-1)

/**
 * WORD_MSB_ONE - Set high bit of each byte on arch word size to one.
 */
#define WORD_MSB_ONE (WORD_LSB_ONE * ((unsigned char)-1 / 2 + 1))

/**
 * word_has_zero - Word has a zero character
 * @w: Word
 */
static inline char word_has_zero(size_t w)
{
	return !!((w - WORD_LSB_ONE) & (~w & WORD_MSB_ONE));
}

/**
 * word_has_char - Word has a character
 * @w: Word
 */
static inline char word_has_char(size_t w, char c)
{
	return !!((w - WORD_LSB_ONE)
		  & ((~w & WORD_MSB_ONE)^(WORD_LSB_ONE * c)));
}

#endif /* !_INTERNAL_WORD_H */