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