memxor.c

   1 /* memxor.c
   2
   3    Copyright (C) 2010, 2014 Niels Möller
   4
   5    This file is part of GNU Nettle.
   6
   7    GNU Nettle is free software: you can redistribute it and/or
   8    modify it under the terms of either:
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at your
  12        option) any later version.
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at your
  18        option) any later version.
  19
  20    or both in parallel, as here.
  21
  22    GNU Nettle is distributed in the hope that it will be useful,
  23    but WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see http://www.gnu.org/licenses/.
  30 */
  31
  32 /* Implementation inspired by memcmp in glibc, contributed to the FSF
  33    by Torbjorn Granlund.
  34  */
  35
  36 #if HAVE_CONFIG_H
  37 # include "config.h"
  38 #endif
  39
  40 #include <assert.h>
  41 #include <limits.h>
  42
  43 #include "memxor.h"
  44 #include "memxor-internal.h"
  45
  46 #define WORD_T_THRESH 16
  47
  48 /* XOR word-aligned areas. n is the number of words, not bytes. */
  49 static void
  50 memxor_common_alignment (word_t *dst, const word_t *src, size_t n)
  51 {
  52   /* FIXME: Require n > 0? */
  53   /* FIXME: Unroll four times, like memcmp? Probably not worth the
  54      effort. */
  55
  56   if (n & 1)
  57     {
  58       n--;
  59       dst[n] ^= src[n];
  60     }
  61   while (n >= 2)
  62     {
  63       n -= 2;
  64       dst[n+1] ^= src[n+1];
  65       dst[n] ^= src[n];
  66     }
  67 }
  68
  69 /* XOR *un-aligned* src-area onto aligned dst area. n is number of
  70    words, not bytes. Assumes we can read complete words at the start
  71    and end of the src operand. */
  72 static void
  73 memxor_different_alignment (word_t *dst, const unsigned char *src, size_t n)
  74 {
  75   int shl, shr;
  76   const word_t *src_word;
  77   unsigned offset = ALIGN_OFFSET (src);
  78   word_t s0, s1;
  79
  80   assert (n > 0);
  81   shl = CHAR_BIT * offset;
  82   shr = CHAR_BIT * (sizeof(word_t) - offset);
  83
  84   src_word = (const word_t *) ((uintptr_t) src & -sizeof(word_t));
  85
  86   /* Read top offset bytes, in native byte order. */
  87   READ_PARTIAL (s0, (unsigned char *) &src_word[n], offset);
  88 #ifdef WORDS_BIGENDIAN
  89   s0 <<= shr; /* FIXME: Eliminate this shift? */
  90 #endif
  91
  92   /* Do n-1 regular iterations */
  93   if (n & 1)
  94     s1 = s0;
  95   else
  96     {
  97       n--;
  98       s1 = src_word[n];
  99       dst[n] ^= MERGE (s1, shl, s0, shr);
 100     }
 101
 102   assert (n & 1);
 103   while (n > 2)
 104     {
 105       n -= 2;
 106       s0 = src_word[n+1];
 107       dst[n+1] ^= MERGE(s0, shl, s1, shr);
 108       s1 = src_word[n]; /* FIXME: Overread on last iteration */
 109       dst[n] ^= MERGE(s1, shl, s0, shr);
 110     }
 111   assert (n == 1);
 112   /* Read low wordsize - offset bytes */
 113   READ_PARTIAL (s0, src, sizeof(word_t) - offset);
 114 #ifndef WORDS_BIGENDIAN
 115   s0 <<= shl; /* FIXME: eliminate shift? */
 116 #endif /* !WORDS_BIGENDIAN */
 117
 118   dst[0] ^= MERGE(s0, shl, s1, shr);
 119 }
 120
 121 /* Performance, Intel SU1400 (x86_64): 0.25 cycles/byte aligned, 0.45
 122    cycles/byte unaligned. */
 123
 124 /* XOR LEN bytes starting at SRCADDR onto DESTADDR. Result undefined
 125    if the source overlaps with the destination. Return DESTADDR. */
 126 void *
 127 memxor(void *dst_in, const void *src_in, size_t n)
 128 {
 129   unsigned char *dst = dst_in;
 130   const unsigned char *src = src_in;
 131
 132   if (n >= WORD_T_THRESH)
 133     {
 134       unsigned i;
 135       unsigned offset;
 136       size_t nwords;
 137       /* There are at least some bytes to compare.  No need to test
 138          for N == 0 in this alignment loop.  */
 139       for (i = ALIGN_OFFSET(dst + n); i > 0; i--)
 140         {
 141           n--;
 142           dst[n] ^= src[n];
 143         }
 144       offset = ALIGN_OFFSET(src + n);
 145       nwords = n / sizeof (word_t);
 146       n %= sizeof (word_t);
 147
 148       if (offset)
 149         memxor_different_alignment ((word_t *) (dst+n), src+n, nwords);
 150       else
 151         memxor_common_alignment ((word_t *) (dst+n),
 152                                  (const word_t *) (src+n), nwords);
 153     }
 154   while (n > 0)
 155     {
 156       n--;
 157       dst[n] ^= src[n];
 158     }
 159
 160   return dst;
 161 }