git.samba.org - gd/nettle/blob - memxor3.c

   1 /* memxor3.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 memxor3_common_alignment (word_t *dst,
  51                           const word_t *a, const word_t *b, size_t n)
  52 {
  53   /* FIXME: Require n > 0? */
  54   if (n & 1)
  55     {
  56       n--;
  57       dst[n] = a[n] ^ b[n];
  58     }
  59   while (n > 0)
  60     {
  61       n -= 2;
  62       dst[n+1] = a[n+1] ^ b[n+1];
  63       dst[n] = a[n] ^ b[n];
  64     }
  65 }
  66
  67 static void
  68 memxor3_different_alignment_b (word_t *dst,
  69                                const word_t *a, const unsigned char *b,
  70                                unsigned offset, size_t n)
  71 {
  72   int shl, shr;
  73   const word_t *b_word;
  74
  75   word_t s0, s1;
  76
  77   assert (n > 0);
  78
  79   shl = CHAR_BIT * offset;
  80   shr = CHAR_BIT * (sizeof(word_t) - offset);
  81
  82   b_word = (const word_t *) ((uintptr_t) b & -sizeof(word_t));
  83
  84   /* Read top offset bytes, in native byte order. */
  85   READ_PARTIAL (s0, (unsigned char *) &b_word[n], offset);
  86 #ifdef WORDS_BIGENDIAN
  87   s0 <<= shr;
  88 #endif
  89
  90   if (n & 1)
  91     s1 = s0;
  92   else
  93     {
  94       n--;
  95       s1 = b_word[n];
  96       dst[n] = a[n] ^ MERGE (s1, shl, s0, shr);
  97     }
  98
  99   while (n > 2)
 100     {
 101       n -= 2;
 102       s0 = b_word[n+1];
 103       dst[n+1] = a[n+1] ^ MERGE(s0, shl, s1, shr);
 104       s1 = b_word[n];
 105       dst[n] = a[n] ^ MERGE(s1, shl, s0, shr);
 106     }
 107   assert (n == 1);
 108   /* Read low wordsize - offset bytes */
 109   READ_PARTIAL (s0, b, sizeof(word_t) - offset);
 110 #ifndef WORDS_BIGENDIAN
 111   s0 <<= shl;
 112 #endif /* !WORDS_BIGENDIAN */
 113
 114   dst[0] = a[0] ^ MERGE(s0, shl, s1, shr);
 115 }
 116
 117 static void
 118 memxor3_different_alignment_ab (word_t *dst,
 119                                 const unsigned char *a, const unsigned char *b,
 120                                 unsigned offset, size_t n)
 121 {
 122   int shl, shr;
 123   const word_t *a_word;
 124   const word_t *b_word;
 125
 126   word_t s0, s1, t;
 127
 128   assert (n > 0);
 129
 130   shl = CHAR_BIT * offset;
 131   shr = CHAR_BIT * (sizeof(word_t) - offset);
 132
 133   a_word = (const word_t *) ((uintptr_t) a & -sizeof(word_t));
 134   b_word = (const word_t *) ((uintptr_t) b & -sizeof(word_t));
 135
 136   /* Read top offset bytes, in native byte order. */
 137   READ_PARTIAL (s0, (unsigned char *) &a_word[n], offset);
 138   READ_PARTIAL (t,  (unsigned char *) &b_word[n], offset);
 139   s0 ^= t;
 140 #ifdef WORDS_BIGENDIAN
 141   s0 <<= shr;
 142 #endif
 143
 144   if (n & 1)
 145     s1 = s0;
 146   else
 147     {
 148       n--;
 149       s1 = a_word[n] ^ b_word[n];
 150       dst[n] = MERGE (s1, shl, s0, shr);
 151     }
 152
 153   while (n > 2)
 154     {
 155       n -= 2;
 156       s0 = a_word[n+1] ^ b_word[n+1];
 157       dst[n+1] = MERGE(s0, shl, s1, shr);
 158       s1 = a_word[n] ^ b_word[n];
 159       dst[n] = MERGE(s1, shl, s0, shr);
 160     }
 161   assert (n == 1);
 162   /* Read low wordsize - offset bytes */
 163   READ_PARTIAL (s0, a, sizeof(word_t) - offset);
 164   READ_PARTIAL (t,  b, sizeof(word_t) - offset);
 165   s0 ^= t;
 166 #ifndef WORDS_BIGENDIAN
 167   s0 <<= shl;
 168 #endif /* !WORDS_BIGENDIAN */
 169
 170   dst[0] = MERGE(s0, shl, s1, shr);
 171 }
 172
 173 static void
 174 memxor3_different_alignment_all (word_t *dst,
 175                                  const unsigned char *a, const unsigned char *b,
 176                                  unsigned a_offset, unsigned b_offset,
 177                                  size_t n)
 178 {
 179   int al, ar, bl, br;
 180   const word_t *a_word;
 181   const word_t *b_word;
 182
 183   word_t a0, a1, b0, b1;
 184
 185   al = CHAR_BIT * a_offset;
 186   ar = CHAR_BIT * (sizeof(word_t) - a_offset);
 187   bl = CHAR_BIT * b_offset;
 188   br = CHAR_BIT * (sizeof(word_t) - b_offset);
 189
 190   a_word = (const word_t *) ((uintptr_t) a & -sizeof(word_t));
 191   b_word = (const word_t *) ((uintptr_t) b & -sizeof(word_t));
 192
 193   /* Read top offset bytes, in native byte order. */
 194   READ_PARTIAL (a0, (unsigned char *) &a_word[n], a_offset);
 195   READ_PARTIAL (b0, (unsigned char *) &b_word[n], b_offset);
 196 #ifdef WORDS_BIGENDIAN
 197   a0 <<= ar;
 198   b0 <<= br;
 199 #endif
 200
 201   if (n & 1)
 202     {
 203       a1 = a0; b1 = b0;
 204     }
 205   else
 206     {
 207       n--;
 208       a1 = a_word[n];
 209       b1 = b_word[n];
 210
 211       dst[n] = MERGE (a1, al, a0, ar) ^ MERGE (b1, bl, b0, br);
 212     }
 213   while (n > 2)
 214     {
 215       n -= 2;
 216       a0 = a_word[n+1]; b0 = b_word[n+1];
 217       dst[n+1] = MERGE(a0, al, a1, ar) ^ MERGE(b0, bl, b1, br);
 218       a1 = a_word[n]; b1 = b_word[n];
 219       dst[n] = MERGE(a1, al, a0, ar) ^ MERGE(b1, bl, b0, br);
 220     }
 221   assert (n == 1);
 222   /* Read low wordsize - offset bytes */
 223   READ_PARTIAL (a0, a, sizeof(word_t) - a_offset);
 224   READ_PARTIAL (b0, b, sizeof(word_t) - b_offset);
 225 #ifndef WORDS_BIGENDIAN
 226   a0 <<= al;
 227   b0 <<= bl;
 228 #endif /* !WORDS_BIGENDIAN */
 229
 230   dst[0] = MERGE(a0, al, a1, ar) ^ MERGE(b0, bl, b1, br);
 231 }
 232
 233 /* Current implementation processes data in descending order, to
 234    support overlapping operation with one of the sources overlapping
 235    the start of the destination area. This feature is used only
 236    internally by cbc decrypt, and it is not advertised or documented
 237    to nettle users. */
 238 void *
 239 memxor3(void *dst_in, const void *a_in, const void *b_in, size_t n)
 240 {
 241   unsigned char *dst = dst_in;
 242   const unsigned char *a = a_in;
 243   const unsigned char *b = b_in;
 244
 245   if (n >= WORD_T_THRESH)
 246     {
 247       unsigned i;
 248       unsigned a_offset;
 249       unsigned b_offset;
 250       size_t nwords;
 251
 252       for (i = ALIGN_OFFSET(dst + n); i > 0; i--)
 253         {
 254           n--;
 255           dst[n] = a[n] ^ b[n];
 256         }
 257
 258       a_offset = ALIGN_OFFSET(a + n);
 259       b_offset = ALIGN_OFFSET(b + n);
 260
 261       nwords = n / sizeof (word_t);
 262       n %= sizeof (word_t);
 263
 264       if (a_offset == b_offset)
 265         {
 266           if (!a_offset)
 267             memxor3_common_alignment((word_t *) (dst + n),
 268                                      (const word_t *) (a + n),
 269                                      (const word_t *) (b + n), nwords);
 270           else
 271             memxor3_different_alignment_ab((word_t *) (dst + n),
 272                                            a + n, b + n, a_offset,
 273                                            nwords);
 274         }
 275       else if (!a_offset)
 276         memxor3_different_alignment_b((word_t *) (dst + n),
 277                                       (const word_t *) (a + n), b + n,
 278                                       b_offset, nwords);
 279       else if (!b_offset)
 280         memxor3_different_alignment_b((word_t *) (dst + n),
 281                                       (const word_t *) (b + n), a + n,
 282                                       a_offset, nwords);
 283       else
 284         memxor3_different_alignment_all((word_t *) (dst + n), a + n, b + n,
 285                                         a_offset, b_offset, nwords);
 286
 287     }
 288   while (n-- > 0)
 289     dst[n] = a[n] ^ b[n];
 290
 291   return dst;
 292 }