memxor.c 3.52 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1 2
/* memxor.c

3
   Copyright (C) 2010, 2014 Niels Möller
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or
   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at your
       option) any later version.

   or

     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at your
       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see http://www.gnu.org/licenses/.
*/
31

Niels Möller's avatar
Niels Möller committed
32 33
/* Implementation inspired by memcmp in glibc, contributed to the FSF
   by Torbjorn Granlund.
34
 */
Niels Möller's avatar
Niels Möller committed
35

36
#if HAVE_CONFIG_H
37
# include "config.h"
38 39
#endif

40 41
#include <limits.h>

Niels Möller's avatar
Niels Möller committed
42
#include "memxor.h"
43
#include "memxor-internal.h"
44 45 46 47 48 49 50

#define WORD_T_THRESH 16

/* XOR word-aligned areas. n is the number of words, not bytes. */
static void
memxor_common_alignment (word_t *dst, const word_t *src, size_t n)
{
Niels Möller's avatar
Niels Möller committed
51 52 53
  /* FIXME: Require n > 0? */
  /* FIXME: Unroll four times, like memcmp? Probably not worth the
     effort. */
54

Niels Möller's avatar
Niels Möller committed
55
  if (n & 1)
56
    {
Niels Möller's avatar
Niels Möller committed
57
      n--;
Niels Möller's avatar
Niels Möller committed
58
      dst[n] ^= src[n];
Niels Möller's avatar
Niels Möller committed
59
    }
Niels Möller's avatar
Niels Möller committed
60
  while (n >= 2)
Niels Möller's avatar
Niels Möller committed
61
    {
Niels Möller's avatar
Niels Möller committed
62 63 64
      n -= 2;
      dst[n+1] ^= src[n+1];
      dst[n] ^= src[n];
65 66 67
    }
}

Niels Möller's avatar
Niels Möller committed
68
/* XOR *un-aligned* src-area onto aligned dst area. n is number of
69 70 71
   words, not bytes. Assumes we can read complete words at the start
   and end of the src operand. */
static void
72
memxor_different_alignment (word_t *dst, const char *src, size_t n)
73 74 75 76 77 78 79 80 81
{
  int shl, shr;
  const word_t *src_word;
  unsigned offset = ALIGN_OFFSET (src);
  word_t s0, s1;

  shl = CHAR_BIT * offset;
  shr = CHAR_BIT * (sizeof(word_t) - offset);

82
  src_word = (const word_t *) ((uintptr_t) src & -sizeof(word_t));
83

Niels Möller's avatar
Niels Möller committed
84
  if (n & 1)
85
    {
Niels Möller's avatar
Niels Möller committed
86 87 88 89
      n--;
      s1 = src_word[n];
      s0 = src_word[n+1]; /* FIXME: Overread */
      dst[n] ^= MERGE (s1, shl, s0, shr);
90
    }
Niels Möller's avatar
Niels Möller committed
91 92
  else
    s1 = src_word[n]; /* FIXME: Overread */
93

Niels Möller's avatar
Niels Möller committed
94
  while (n > 0)
95
    {
Niels Möller's avatar
Niels Möller committed
96 97 98 99 100
      n -= 2;
      s0 = src_word[n+1];
      dst[n+1] ^= MERGE(s0, shl, s1, shr);
      s1 = src_word[n]; /* FIXME: Overread on last iteration */
      dst[n] ^= MERGE(s1, shl, s0, shr);
101 102 103
    }
}

Niels Möller's avatar
Niels Möller committed
104 105 106
/* Performance, Intel SU1400 (x86_64): 0.25 cycles/byte aligned, 0.45
   cycles/byte unaligned. */

107 108
/* XOR LEN bytes starting at SRCADDR onto DESTADDR. Result undefined
   if the source overlaps with the destination. Return DESTADDR. */
109 110
void *
memxor(void *dst_in, const void *src_in, size_t n)
111
{
112 113
  char *dst = dst_in;
  const char *src = src_in;
114 115 116

  if (n >= WORD_T_THRESH)
    {
Niels Möller's avatar
Niels Möller committed
117 118 119
      unsigned i;
      unsigned offset;
      size_t nwords;
120 121
      /* There are at least some bytes to compare.  No need to test
	 for N == 0 in this alignment loop.  */
Niels Möller's avatar
Niels Möller committed
122
      for (i = ALIGN_OFFSET(dst + n); i > 0; i--)
123 124
	{
	  n--;
Niels Möller's avatar
Niels Möller committed
125
	  dst[n] ^= src[n];
126
	}
Niels Möller's avatar
Niels Möller committed
127 128 129
      offset = ALIGN_OFFSET(src + n);
      nwords = n / sizeof (word_t);
      n %= sizeof (word_t);
130

Niels Möller's avatar
Niels Möller committed
131 132 133 134 135 136 137 138 139 140
      if (offset)
	memxor_different_alignment ((word_t *) (dst+n), (src+n), nwords);
      else
	memxor_common_alignment ((word_t *) (dst+n),
				 (const word_t *) (src+n), nwords);
    }
  while (n > 0)
    {
      n--;
      dst[n] ^= src[n];
141 142
    }

Niels Möller's avatar
Niels Möller committed
143
  return dst;
144
}