memxor3.c 6.95 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
/* memxor3.c
2 3 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 31 32 33 34 35 36 37 38 39

   Copyright (C) 2010, 2014 Niels Möller

   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/.
*/

/* Implementation inspired by memcmp in glibc, contributed to the FSF
   by Torbjorn Granlund.
 */

#if HAVE_CONFIG_H
# include "config.h"
#endif

40
#include <assert.h>
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
#include <limits.h>

#include "memxor.h"
#include "memxor-internal.h"

#define WORD_T_THRESH 16

/* XOR word-aligned areas. n is the number of words, not bytes. */
static void
memxor3_common_alignment (word_t *dst,
			  const word_t *a, const word_t *b, size_t n)
{
  /* FIXME: Require n > 0? */
  if (n & 1)
    {
      n--;
      dst[n] = a[n] ^ b[n];
    }
  while (n > 0)
    {
      n -= 2;
      dst[n+1] = a[n+1] ^ b[n+1];
      dst[n] = a[n] ^ b[n];
    }
}

static void
memxor3_different_alignment_b (word_t *dst,
69 70
			       const word_t *a, const unsigned char *b,
			       unsigned offset, size_t n)
71 72 73 74 75 76
{
  int shl, shr;
  const word_t *b_word;

  word_t s0, s1;

77 78
  assert (n > 0);

79 80 81 82 83
  shl = CHAR_BIT * offset;
  shr = CHAR_BIT * (sizeof(word_t) - offset);

  b_word = (const word_t *) ((uintptr_t) b & -sizeof(word_t));

84 85 86 87 88 89
  /* Read top offset bytes, in native byte order. */
  READ_PARTIAL (s0, (unsigned char *) &b_word[n], offset);
#ifdef WORDS_BIGENDIAN
  s0 <<= shr;
#endif

90
  if (n & 1)
91 92
    s1 = s0;
  else
93 94 95 96 97 98
    {
      n--;
      s1 = b_word[n];
      dst[n] = a[n] ^ MERGE (s1, shl, s0, shr);
    }

99
  while (n > 2)
100 101 102 103 104 105 106
    {
      n -= 2;
      s0 = b_word[n+1];
      dst[n+1] = a[n+1] ^ MERGE(s0, shl, s1, shr);
      s1 = b_word[n];
      dst[n] = a[n] ^ MERGE(s1, shl, s0, shr);
    }
107 108 109 110 111 112 113 114
  assert (n == 1);
  /* Read low wordsize - offset bytes */
  READ_PARTIAL (s0, b, sizeof(word_t) - offset);
#ifndef WORDS_BIGENDIAN
  s0 <<= shl;
#endif /* !WORDS_BIGENDIAN */

  dst[0] = a[0] ^ MERGE(s0, shl, s1, shr);
115 116 117 118
}

static void
memxor3_different_alignment_ab (word_t *dst,
119
				const unsigned char *a, const unsigned char *b,
120 121 122 123 124 125
				unsigned offset, size_t n)
{
  int shl, shr;
  const word_t *a_word;
  const word_t *b_word;

126 127 128
  word_t s0, s1, t;

  assert (n > 0);
129 130 131 132 133 134 135

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

  a_word = (const word_t *) ((uintptr_t) a & -sizeof(word_t));
  b_word = (const word_t *) ((uintptr_t) b & -sizeof(word_t));

136 137 138 139 140 141 142 143
  /* Read top offset bytes, in native byte order. */
  READ_PARTIAL (s0, (unsigned char *) &a_word[n], offset);
  READ_PARTIAL (t,  (unsigned char *) &b_word[n], offset);
  s0 ^= t;
#ifdef WORDS_BIGENDIAN
  s0 <<= shr;
#endif

144
  if (n & 1)
145 146
    s1 = s0;
  else
147 148 149 150 151 152
    {
      n--;
      s1 = a_word[n] ^ b_word[n];
      dst[n] = MERGE (s1, shl, s0, shr);
    }

153
  while (n > 2)
154 155 156 157 158 159 160
    {
      n -= 2;
      s0 = a_word[n+1] ^ b_word[n+1];
      dst[n+1] = MERGE(s0, shl, s1, shr);
      s1 = a_word[n] ^ b_word[n];
      dst[n] = MERGE(s1, shl, s0, shr);
    }
161 162 163 164 165 166 167 168 169 170
  assert (n == 1);
  /* Read low wordsize - offset bytes */
  READ_PARTIAL (s0, a, sizeof(word_t) - offset);
  READ_PARTIAL (t,  b, sizeof(word_t) - offset);
  s0 ^= t;
#ifndef WORDS_BIGENDIAN
  s0 <<= shl;
#endif /* !WORDS_BIGENDIAN */

  dst[0] = MERGE(s0, shl, s1, shr);
171 172 173 174
}

static void
memxor3_different_alignment_all (word_t *dst,
175
				 const unsigned char *a, const unsigned char *b,
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
				 unsigned a_offset, unsigned b_offset,
				 size_t n)
{
  int al, ar, bl, br;
  const word_t *a_word;
  const word_t *b_word;

  word_t a0, a1, b0, b1;

  al = CHAR_BIT * a_offset;
  ar = CHAR_BIT * (sizeof(word_t) - a_offset);
  bl = CHAR_BIT * b_offset;
  br = CHAR_BIT * (sizeof(word_t) - b_offset);

  a_word = (const word_t *) ((uintptr_t) a & -sizeof(word_t));
  b_word = (const word_t *) ((uintptr_t) b & -sizeof(word_t));

193 194 195 196 197 198 199 200
  /* Read top offset bytes, in native byte order. */
  READ_PARTIAL (a0, (unsigned char *) &a_word[n], a_offset);
  READ_PARTIAL (b0, (unsigned char *) &b_word[n], b_offset);
#ifdef WORDS_BIGENDIAN
  a0 <<= ar;
  b0 <<= br;
#endif

201 202
  if (n & 1)
    {
203
      a1 = a0; b1 = b0;
204 205 206
    }
  else
    {
207
      n--;
208 209 210
      a1 = a_word[n];
      b1 = b_word[n];

211 212 213
      dst[n] = MERGE (a1, al, a0, ar) ^ MERGE (b1, bl, b0, br);
    }
  while (n > 2)
214 215 216 217 218 219 220
    {
      n -= 2;
      a0 = a_word[n+1]; b0 = b_word[n+1];
      dst[n+1] = MERGE(a0, al, a1, ar) ^ MERGE(b0, bl, b1, br);
      a1 = a_word[n]; b1 = b_word[n];
      dst[n] = MERGE(a1, al, a0, ar) ^ MERGE(b1, bl, b0, br);
    }
221 222 223 224 225 226 227 228 229 230
  assert (n == 1);
  /* Read low wordsize - offset bytes */
  READ_PARTIAL (a0, a, sizeof(word_t) - a_offset);
  READ_PARTIAL (b0, b, sizeof(word_t) - b_offset);
#ifndef WORDS_BIGENDIAN
  a0 <<= al;
  b0 <<= bl;
#endif /* !WORDS_BIGENDIAN */

  dst[0] = MERGE(a0, al, a1, ar) ^ MERGE(b0, bl, b1, br);
231 232 233 234 235 236 237 238 239 240
}

/* Current implementation processes data in descending order, to
   support overlapping operation with one of the sources overlapping
   the start of the destination area. This feature is used only
   internally by cbc decrypt, and it is not advertised or documented
   to nettle users. */
void *
memxor3(void *dst_in, const void *a_in, const void *b_in, size_t n)
{
241 242 243
  unsigned char *dst = dst_in;
  const unsigned char *a = a_in;
  const unsigned char *b = b_in;
244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292

  if (n >= WORD_T_THRESH)
    {
      unsigned i;
      unsigned a_offset;
      unsigned b_offset;
      size_t nwords;

      for (i = ALIGN_OFFSET(dst + n); i > 0; i--)
	{
	  n--;
	  dst[n] = a[n] ^ b[n];
	}

      a_offset = ALIGN_OFFSET(a + n);
      b_offset = ALIGN_OFFSET(b + n);

      nwords = n / sizeof (word_t);
      n %= sizeof (word_t);

      if (a_offset == b_offset)
	{
	  if (!a_offset)
	    memxor3_common_alignment((word_t *) (dst + n),
				     (const word_t *) (a + n),
				     (const word_t *) (b + n), nwords);
	  else
	    memxor3_different_alignment_ab((word_t *) (dst + n),
					   a + n, b + n, a_offset,
					   nwords);
	}
      else if (!a_offset)
	memxor3_different_alignment_b((word_t *) (dst + n),
				      (const word_t *) (a + n), b + n,
				      b_offset, nwords);
      else if (!b_offset)
	memxor3_different_alignment_b((word_t *) (dst + n),
				      (const word_t *) (b + n), a + n,
				      a_offset, nwords);
      else
	memxor3_different_alignment_all((word_t *) (dst + n), a + n, b + n,
					a_offset, b_offset, nwords);

    }
  while (n-- > 0)
    dst[n] = a[n] ^ b[n];

  return dst;
}