Hi,
After trying to implement memcmp for big endian I realized that its
exactly whats needed.
As on big endian we could just load them into register and directly
compare them as ordering is same then for little endian we could just
first use bswap for big-endian case.
Following expansion should be close to optimal on architectures that
have unaligned loads. It isn't worth do it without these as emulating
them bloats implementation size, so its better do libcall.
I was surprised when I checked how it expands pattern
if (memcmp(x,y,n))
that it optimizes byteswap away, expansion of that looks like best
possible.
It could be improved on other platforms. First is that I ignore 16bit
operations as they tend to be slow. Instead I do an overlapping load
of maximal size. I could add table of expansion without overlap and see
whats faster.
For generic memcmp assemly could be made shorter as gcc duplicates
tails. For first 8 bytes I use fact that its likely so I start with
converting them, assembly of memcmp(x,y,23) is following.
movq (%rdi), %rax
movq (%rsi), %rdx
.here:
bswap %rax
bswap %rdx
cmpq %rdx, %rax
je .L22
.L20:
cmpq %rax, %rdx
.L21:
sbbl %eax, %eax
andl $2, %eax
subl $1, %eax
ret
.L22:
movq 8(%rdi), %rax
movq 8(%rsi), %rdx
cmpq %rdx, %rax
je .L15
bswap %rdx
bswap %rax
jmp .L20
...
You could save space by changing that into
movq 8(%rdi), %rax
movq 8(%rsi), %rdx
cmpq %rdx, %rax
jne .here
movq 15(%rdi), %rax
movq 15(%rsi), %rdx
cmpq %rdx, %rax
jne .here
xor %rax, %rax
ret
Also there is bug that you duplicate comparison:
cmpq %rdx, %rax
je .L22
.L20:
cmpq %rax, %rdx
Comments?
#include <string.h>
#include <stdint.h>
#undef memcmp
#define memcmp(x, y, n) (__builtin_constant_p (n) && n < 64 ? __memcmp_inline
(x, y, n) \
: memcmp (x, y, n))
#define LOAD8(x) (*((uint8_t *) (x)))
#define LOAD32(x) (*((uint32_t *) (x)))
#define LOAD64(x) (*((uint64_t *) (x)))
#define CHECK(tp, n)
#if __BYTE_ORDER == __LITTLE_ENDIAN
# define SWAP32(x) __builtin_bswap32 (LOAD32 (x))
# define SWAP64(x) __builtin_bswap64 (LOAD64 (x))
#else
# define SWAP32(x) LOAD32 (x)
# define SWAP64(x) LOAD64 (x)
#endif
#define __ARCH_64BIT 1
static __always_inline
int
check (uint64_t x, uint64_t y)
{
if (x == y)
return 0;
if (x > y)
return 1;
return -1;
}
static __always_inline
int
check_nonzero (uint64_t x, uint64_t y)
{
if (x > y)
return 1;
return -1;
}
static __always_inline
int
__memcmp_inline (void *x, void *y, size_t n)
{
#define CHECK1 if (LOAD8 (x + i) - LOAD8 (y + i)) \
return check_nonzero (LOAD8 (x + i), LOAD8 (y + i)); i = i + 1;
#define CHECK4 if (i == 0 ? SWAP32 (x + i) - SWAP32 (y + i)\
: LOAD32 (x + i) - LOAD32 (y + i)) \
return check_nonzero (SWAP32 (x + i), SWAP32 (y + i)); i = i + 4;
#define CHECK8 if (i == 0 ? SWAP64 (x + i) - SWAP64 (y + i)\
: LOAD64 (x + i) - LOAD64 (y + i)) \
return check_nonzero (SWAP64 (x + i), SWAP64 (y + i)); i = i + 8;
#define CHECK1FINAL(o) return check (LOAD8 (x + i + o), LOAD8 (y + i + o));
#define CHECK4FINAL(o) return check (SWAP32 (x + i + o), SWAP32 (y + i + o));
#define CHECK8FINAL(o) return check (SWAP64 (x + i + o), SWAP64 (y + i + o));
#if __ARCH_64BIT == 0
# undef CHECK8
# undef CHECK8FINAL
# define CHECK8 CHECK4 CHECK4
# define CHECK8FINAL(o) CHECK4 CHECK4FINAL (o)
#endif
#define LOOP if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 }
long i = 0;
switch (n % 8)
{
case 0:
if (n == 0)
return 0;
LOOP; CHECK8FINAL (0);
case 1:
LOOP CHECK1FINAL (0);
case 2:
if (n == 2)
{
CHECK1 CHECK1FINAL (0);
}
LOOP CHECK4FINAL (-2);
case 3:
if (n == 3)
{
CHECK1 CHECK1 CHECK1FINAL (0);
}
LOOP CHECK4FINAL (-1);
case 4:
LOOP CHECK4FINAL (0);
case 5:
if (n == 5)
{
CHECK4 CHECK1FINAL (0);
}
#if __ARCH_64BIT
LOOP CHECK8FINAL (-3);
#else
LOOP CHECK4 CHECK1FINAL (0);
#endif
case 6:
if (n == 6)
{
CHECK4 CHECK4FINAL (-2);
}
LOOP CHECK8FINAL (-2);
case 7:
if (n == 7)
{
CHECK4 CHECK4FINAL (-1);
}
LOOP CHECK8FINAL (-1);
}
}
int
memcmp1 (char *x, char *y)
{
return memcmp (x, y, 1);
}
int
memcmp10 (char *x, char *y)
{
return memcmp (x, y, 10);
}
int
memcmp20 (char *x, char *y)
{
return memcmp (x, y, 20);
}
int
memcmp30 (char *x, char *y)
{
return memcmp (x, y, 30);
}
int
memeq1 (char *x, char *y)
{
return memcmp (x, y, 1) != 0;
}
int
memeq10 (char *x, char *y)
{
return memcmp (x, y, 10) != 0;
}
int
memeq20 (char *x, char *y)
{
return memcmp (x, y, 20) != 0;
}
int
memeq30 (char *x, char *y)
{
return memcmp (x, y, 30) != 0;
}
