memxor.c

   1 /* memxor.c
   2  *
   3  */
   4
   5 /* nettle, low-level cryptographics library
   6  *
   7  * Copyright (C) 1991, 1993, 1995 Free Software Foundation, Inc.
   8  * Copyright (C) 2010 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  23  * MA 02111-1301, USA.
  24  */
  25
  26 /* Implementation inspired by memcmp in glibc, contributed to the FSF
  27    by Torbjorn Granlund.
  28  */
  29
  30 #if HAVE_CONFIG_H
  31 # include "config.h"
  32 #endif
  33
  34 #include <limits.h>
  35
  36 #include "memxor.h"
  37
  38 typedef unsigned long int word_t;
  39
  40 #if SIZEOF_LONG & (SIZEOF_LONG - 1)
  41 #error Word size must be a power of two
  42 #endif
  43
  44 #define ALIGN_OFFSET(p) ((uintptr_t) (p) % sizeof(word_t))
  45
  46 #ifndef WORDS_BIGENDIAN
  47 #define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  48 #else
  49 #define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  50 #endif
  51
  52 #define WORD_T_THRESH 16
  53
  54 /* XOR word-aligned areas. n is the number of words, not bytes. */
  55 static void
  56 memxor_common_alignment (word_t *dst, const word_t *src, size_t n)
  57 {
  58   /* FIXME: Require n > 0? */
  59   /* FIXME: Unroll four times, like memcmp? Probably not worth the
  60      effort. */
  61
  62   if (n & 1)
  63     {
  64       *dst++ ^= *src++;
  65       n--;
  66     }
  67   for (; n >= 2; dst += 2, src += 2, n -= 2)
  68     {
  69       dst[0] ^= src[0];
  70       dst[1] ^= src[1];
  71     }
  72 }
  73
  74 /* XOR *un-aligned* src-area onto aligned dst area. n is number of
  75    words, not bytes. Assumes we can read complete words at the start
  76    and end of the src operand. */
  77 static void
  78 memxor_different_alignment (word_t *dst, const uint8_t *src, size_t n)
  79 {
  80   size_t i;
  81   int shl, shr;
  82   const word_t *src_word;
  83   unsigned offset = ALIGN_OFFSET (src);
  84   word_t s0, s1;
  85
  86   shl = CHAR_BIT * offset;
  87   shr = CHAR_BIT * (sizeof(word_t) - offset);
  88
  89   src_word = (const word_t *) ((uintptr_t) src & -SIZEOF_LONG);
  90
  91   /* FIXME: Unroll four times, like memcmp? */
  92   i = n & 1;
  93   s0 = src_word[i];
  94   if (i)
  95     {
  96       s1 = src_word[0];
  97       dst[0] ^= MERGE (s1, shl, s0, shr);
  98     }
  99
 100   for (; i < n; i += 2)
 101     {
 102       s1 = src_word[i+1];
 103       dst[i] ^= MERGE(s0, shl, s1, shr);
 104       s0 = src_word[i+2];
 105       dst[i+1] ^= MERGE(s1, shl, s0, shr);
 106     }
 107 }
 108
 109 /* Performance, Intel SU1400 (x86_64): 0.25 cycles/byte aligned, 0.45
 110    cycles/byte unaligned. */
 111
 112 /* XOR LEN bytes starting at SRCADDR onto DESTADDR. Result undefined
 113    if the source overlaps with the destination. Return DESTADDR. */
 114 uint8_t *
 115 memxor(uint8_t *dst, const uint8_t *src, size_t n)
 116 {
 117   uint8_t *orig_dst = dst;
 118
 119   if (n >= WORD_T_THRESH)
 120     {
 121       /* There are at least some bytes to compare.  No need to test
 122          for N == 0 in this alignment loop.  */
 123       while (ALIGN_OFFSET (dst))
 124         {
 125           *dst++ ^= *src++;
 126           n--;
 127         }
 128       if (ALIGN_OFFSET (src))
 129         memxor_different_alignment ((word_t *) dst, src, n / sizeof(word_t));
 130       else
 131         memxor_common_alignment ((word_t *) dst, (const word_t *) src, n / sizeof(word_t));
 132
 133       dst += n & -SIZEOF_LONG;
 134       src += n & -SIZEOF_LONG;
 135       n = n & (SIZEOF_LONG - 1);
 136     }
 137   for (; n > 0; n--)
 138     *dst++ ^= *src++;
 139
 140   return orig_dst;
 141 }
 142
 143
 144 /* XOR word-aligned areas. n is the number of words, not bytes. */
 145 static void
 146 memxor3_common_alignment (word_t *dst,
 147                           const word_t *a, const word_t *b, size_t n)
 148 {
 149   /* FIXME: Require n > 0? */
 150   while (n-- > 0)
 151     dst[n] = a[n] ^ b[n];
 152 }
 153
 154 static void
 155 memxor3_different_alignment_b (word_t *dst,
 156                                const word_t *a, const uint8_t *b, unsigned offset, size_t n)
 157 {
 158   int shl, shr;
 159   const word_t *b_word;
 160
 161   word_t s0, s1;
 162
 163   shl = CHAR_BIT * offset;
 164   shr = CHAR_BIT * (sizeof(word_t) - offset);
 165
 166   b_word = (const word_t *) ((uintptr_t) b & -SIZEOF_LONG);
 167
 168   if (n & 1)
 169     {
 170       n--;
 171       s1 = b_word[n];
 172       s0 = b_word[n+1];
 173       dst[n] = a[n] ^ MERGE (s1, shl, s0, shr);
 174     }
 175   else
 176     s1 = b_word[n];
 177
 178   while (n > 0)
 179     {
 180       n -= 2;
 181       s0 = b_word[n+1];
 182       dst[n+1] = a[n+1] ^ MERGE(s0, shl, s1, shr);
 183       s1 = b_word[n];
 184       dst[n] = a[n] ^ MERGE(s1, shl, s0, shr);
 185     }
 186 }
 187
 188 static void
 189 memxor3_different_alignment_ab (word_t *dst,
 190                                 const uint8_t *a, const uint8_t *b,
 191                                 unsigned offset, size_t n)
 192 {
 193   int shl, shr;
 194   const word_t *a_word;
 195   const word_t *b_word;
 196
 197   word_t s0, s1;
 198
 199   shl = CHAR_BIT * offset;
 200   shr = CHAR_BIT * (sizeof(word_t) - offset);
 201
 202   a_word = (const word_t *) ((uintptr_t) a & -SIZEOF_LONG);
 203   b_word = (const word_t *) ((uintptr_t) b & -SIZEOF_LONG);
 204
 205   if (n & 1)
 206     {
 207       n--;
 208       s1 = a_word[n] ^ b_word[n];
 209       s0 = a_word[n+1] ^ b_word[n+1];
 210       dst[n] = MERGE (s1, shl, s0, shr);
 211     }
 212   else
 213     s1 = a_word[n] ^ b_word[n];
 214
 215   while (n > 0)
 216     {
 217       n -= 2;
 218       s0 = a_word[n+1] ^ b_word[n+1];
 219       dst[n+1] = MERGE(s0, shl, s1, shr);
 220       s1 = a_word[n] ^ b_word[n];
 221       dst[n] = MERGE(s1, shl, s0, shr);
 222     }
 223 }
 224
 225 static void
 226 memxor3_different_alignment_all (word_t *dst,
 227                                  const uint8_t *a, const uint8_t *b,
 228                                  unsigned a_offset, unsigned b_offset,
 229                                  size_t n)
 230 {
 231   int al, ar, bl, br;
 232   const word_t *a_word;
 233   const word_t *b_word;
 234
 235   word_t a0, a1, b0, b1;
 236
 237   al = CHAR_BIT * a_offset;
 238   ar = CHAR_BIT * (sizeof(word_t) - a_offset);
 239   bl = CHAR_BIT * b_offset;
 240   br = CHAR_BIT * (sizeof(word_t) - b_offset);
 241
 242   a_word = (const word_t *) ((uintptr_t) a & -SIZEOF_LONG);
 243   b_word = (const word_t *) ((uintptr_t) b & -SIZEOF_LONG);
 244
 245   if (n & 1)
 246     {
 247       n--;
 248       a1 = a_word[n]; a0 = a_word[n+1];
 249       b1 = b_word[n]; b0 = b_word[n+1];
 250
 251       dst[n] = MERGE (a1, al, a0, ar) ^ MERGE (b1, bl, b0, br);
 252     }
 253   else
 254     {
 255       a1 = a_word[n];
 256       b1 = b_word[n];
 257     }
 258
 259   while (n > 0)
 260     {
 261       n -= 2;
 262       a0 = a_word[n+1]; b0 = b_word[n+1];
 263       dst[n+1] = MERGE(a0, al, a1, ar) ^ MERGE(b0, bl, b1, br);
 264       a1 = a_word[n]; b1 = b_word[n];
 265       dst[n] = MERGE(a1, al, a0, ar) ^ MERGE(b1, bl, b0, br);
 266     }
 267 }
 268
 269 /* Current implementation processes data in descending order, to
 270    support overlapping operation with one of the sources overlapping
 271    the start of the destination area. This feature is used only
 272    internally by cbc decrypt, and it is not advertised or documented
 273    to nettle users. */
 274 uint8_t *
 275 memxor3(uint8_t *dst, const uint8_t *a, const uint8_t *b, size_t n)
 276 {
 277   if (n >= WORD_T_THRESH)
 278     {
 279       unsigned i;
 280       unsigned a_offset;
 281       unsigned b_offset;
 282       size_t nwords;
 283
 284       for (i = ALIGN_OFFSET(dst + n); i > 0; i--)
 285         {
 286           n--;
 287           dst[n] = a[n] ^ b[n];
 288         }
 289
 290       a_offset = ALIGN_OFFSET(a + n);
 291       b_offset = ALIGN_OFFSET(b + n);
 292
 293       nwords = n / sizeof (word_t);
 294       n %= sizeof (word_t);
 295
 296       if (a_offset == b_offset)
 297         {
 298           if (!a_offset)
 299             memxor3_common_alignment((word_t *) (dst + n),
 300                                      (const word_t *) (a + n),
 301                                      (const word_t *) (b + n), nwords);
 302           else
 303             memxor3_different_alignment_ab((word_t *) (dst + n),
 304                                            a + n, b + n, a_offset,
 305                                            nwords);
 306         }
 307       else if (!a_offset)
 308         memxor3_different_alignment_b((word_t *) (dst + n),
 309                                       (const word_t *) (a + n), b + n,
 310                                       b_offset, nwords);
 311       else if (!b_offset)
 312         memxor3_different_alignment_b((word_t *) (dst + n),
 313                                       (const word_t *) (b + n), a + n,
 314                                       a_offset, nwords);
 315       else
 316         memxor3_different_alignment_all((word_t *) (dst + n), a + n, b + n,
 317                                         a_offset, b_offset, nwords);
 318
 319     }
 320   while (n-- > 0)
 321     dst[n] = a[n] ^ b[n];
 322
 323   return dst;
 324 }