1 /*-
2 * Copyright 2009 Colin Percival
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * This file was originally written by Colin Percival as part of the Tarsnap
27 * online backup system.
28 */
29 #include "cpusupport.h"
30 #ifdef CPUSUPPORT_X86_SSE2
31
32 #include <emmintrin.h>
33 #include <stdint.h>
34
35 #include "sysendian.h"
36
37 #include "crypto_scrypt_smix_sse2.h"
38
39 static void blkcpy(void *, const void *, size_t);
40 static void blkxor(void *, const void *, size_t);
41 static void salsa20_8(__m128i *);
42 static void blockmix_salsa8(const __m128i *, __m128i *, __m128i *, size_t);
43 static uint64_t integerify(const void *, size_t);
44
45 static void
blkcpy(void * dest,const void * src,size_t len)46 blkcpy(void * dest, const void * src, size_t len)
47 {
48 __m128i * D = dest;
49 const __m128i * S = src;
50 size_t L = len / 16;
51 size_t i;
52
53 for (i = 0; i < L; i++)
54 D[i] = S[i];
55 }
56
57 static void
blkxor(void * dest,const void * src,size_t len)58 blkxor(void * dest, const void * src, size_t len)
59 {
60 __m128i * D = dest;
61 const __m128i * S = src;
62 size_t L = len / 16;
63 size_t i;
64
65 for (i = 0; i < L; i++)
66 D[i] = _mm_xor_si128(D[i], S[i]);
67 }
68
69 /**
70 * salsa20_8(B):
71 * Apply the salsa20/8 core to the provided block.
72 */
73 static void
salsa20_8(__m128i B[4])74 salsa20_8(__m128i B[4])
75 {
76 __m128i X0, X1, X2, X3;
77 __m128i T;
78 size_t i;
79
80 X0 = B[0];
81 X1 = B[1];
82 X2 = B[2];
83 X3 = B[3];
84
85 for (i = 0; i < 8; i += 2) {
86 /* Operate on "columns". */
87 T = _mm_add_epi32(X0, X3);
88 X1 = _mm_xor_si128(X1, _mm_slli_epi32(T, 7));
89 X1 = _mm_xor_si128(X1, _mm_srli_epi32(T, 25));
90 T = _mm_add_epi32(X1, X0);
91 X2 = _mm_xor_si128(X2, _mm_slli_epi32(T, 9));
92 X2 = _mm_xor_si128(X2, _mm_srli_epi32(T, 23));
93 T = _mm_add_epi32(X2, X1);
94 X3 = _mm_xor_si128(X3, _mm_slli_epi32(T, 13));
95 X3 = _mm_xor_si128(X3, _mm_srli_epi32(T, 19));
96 T = _mm_add_epi32(X3, X2);
97 X0 = _mm_xor_si128(X0, _mm_slli_epi32(T, 18));
98 X0 = _mm_xor_si128(X0, _mm_srli_epi32(T, 14));
99
100 /* Rearrange data. */
101 X1 = _mm_shuffle_epi32(X1, 0x93);
102 X2 = _mm_shuffle_epi32(X2, 0x4E);
103 X3 = _mm_shuffle_epi32(X3, 0x39);
104
105 /* Operate on "rows". */
106 T = _mm_add_epi32(X0, X1);
107 X3 = _mm_xor_si128(X3, _mm_slli_epi32(T, 7));
108 X3 = _mm_xor_si128(X3, _mm_srli_epi32(T, 25));
109 T = _mm_add_epi32(X3, X0);
110 X2 = _mm_xor_si128(X2, _mm_slli_epi32(T, 9));
111 X2 = _mm_xor_si128(X2, _mm_srli_epi32(T, 23));
112 T = _mm_add_epi32(X2, X3);
113 X1 = _mm_xor_si128(X1, _mm_slli_epi32(T, 13));
114 X1 = _mm_xor_si128(X1, _mm_srli_epi32(T, 19));
115 T = _mm_add_epi32(X1, X2);
116 X0 = _mm_xor_si128(X0, _mm_slli_epi32(T, 18));
117 X0 = _mm_xor_si128(X0, _mm_srli_epi32(T, 14));
118
119 /* Rearrange data. */
120 X1 = _mm_shuffle_epi32(X1, 0x39);
121 X2 = _mm_shuffle_epi32(X2, 0x4E);
122 X3 = _mm_shuffle_epi32(X3, 0x93);
123 }
124
125 B[0] = _mm_add_epi32(B[0], X0);
126 B[1] = _mm_add_epi32(B[1], X1);
127 B[2] = _mm_add_epi32(B[2], X2);
128 B[3] = _mm_add_epi32(B[3], X3);
129 }
130
131 /**
132 * blockmix_salsa8(Bin, Bout, X, r):
133 * Compute Bout = BlockMix_{salsa20/8, r}(Bin). The input Bin must be 128r
134 * bytes in length; the output Bout must also be the same size. The
135 * temporary space X must be 64 bytes.
136 */
137 static void
blockmix_salsa8(const __m128i * Bin,__m128i * Bout,__m128i * X,size_t r)138 blockmix_salsa8(const __m128i * Bin, __m128i * Bout, __m128i * X, size_t r)
139 {
140 size_t i;
141
142 /* 1: X <-- B_{2r - 1} */
143 blkcpy(X, &Bin[8 * r - 4], 64);
144
145 /* 2: for i = 0 to 2r - 1 do */
146 for (i = 0; i < r; i++) {
147 /* 3: X <-- H(X \xor B_i) */
148 blkxor(X, &Bin[i * 8], 64);
149 salsa20_8(X);
150
151 /* 4: Y_i <-- X */
152 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
153 blkcpy(&Bout[i * 4], X, 64);
154
155 /* 3: X <-- H(X \xor B_i) */
156 blkxor(X, &Bin[i * 8 + 4], 64);
157 salsa20_8(X);
158
159 /* 4: Y_i <-- X */
160 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
161 blkcpy(&Bout[(r + i) * 4], X, 64);
162 }
163 }
164
165 /**
166 * integerify(B, r):
167 * Return the result of parsing B_{2r-1} as a little-endian integer.
168 * Note that B's layout is permuted compared to the generic implementation.
169 */
170 static uint64_t
integerify(const void * B,size_t r)171 integerify(const void * B, size_t r)
172 {
173 const uint32_t * X = (const void *)((uintptr_t)(B) + (2 * r - 1) * 64);
174
175 return (((uint64_t)(X[13]) << 32) + X[0]);
176 }
177
178 /**
179 * crypto_scrypt_smix_sse2(B, r, N, V, XY):
180 * Compute B = SMix_r(B, N). The input B must be 128r bytes in length;
181 * the temporary storage V must be 128rN bytes in length; the temporary
182 * storage XY must be 256r + 64 bytes in length. The value N must be a
183 * power of 2 greater than 1. The arrays B, V, and XY must be aligned to a
184 * multiple of 64 bytes.
185 *
186 * Use SSE2 instructions.
187 */
188 void
crypto_scrypt_smix_sse2(uint8_t * B,size_t r,uint64_t N,void * V,void * XY)189 crypto_scrypt_smix_sse2(uint8_t * B, size_t r, uint64_t N, void * V, void * XY)
190 {
191 __m128i * X = XY;
192 __m128i * Y = (void *)((uintptr_t)(XY) + 128 * r);
193 __m128i * Z = (void *)((uintptr_t)(XY) + 256 * r);
194 uint32_t * X32 = (void *)X;
195 uint64_t i, j;
196 size_t k;
197
198 /* 1: X <-- B */
199 for (k = 0; k < 2 * r; k++) {
200 for (i = 0; i < 16; i++) {
201 X32[k * 16 + i] =
202 le32dec(&B[(k * 16 + (i * 5 % 16)) * 4]);
203 }
204 }
205
206 /* 2: for i = 0 to N - 1 do */
207 for (i = 0; i < N; i += 2) {
208 /* 3: V_i <-- X */
209 blkcpy((void *)((uintptr_t)(V) + i * 128 * r), X, 128 * r);
210
211 /* 4: X <-- H(X) */
212 blockmix_salsa8(X, Y, Z, r);
213
214 /* 3: V_i <-- X */
215 blkcpy((void *)((uintptr_t)(V) + (i + 1) * 128 * r),
216 Y, 128 * r);
217
218 /* 4: X <-- H(X) */
219 blockmix_salsa8(Y, X, Z, r);
220 }
221
222 /* 6: for i = 0 to N - 1 do */
223 for (i = 0; i < N; i += 2) {
224 /* 7: j <-- Integerify(X) mod N */
225 j = integerify(X, r) & (N - 1);
226
227 /* 8: X <-- H(X \xor V_j) */
228 blkxor(X, (void *)((uintptr_t)(V) + j * 128 * r), 128 * r);
229 blockmix_salsa8(X, Y, Z, r);
230
231 /* 7: j <-- Integerify(X) mod N */
232 j = integerify(Y, r) & (N - 1);
233
234 /* 8: X <-- H(X \xor V_j) */
235 blkxor(Y, (void *)((uintptr_t)(V) + j * 128 * r), 128 * r);
236 blockmix_salsa8(Y, X, Z, r);
237 }
238
239 /* 10: B' <-- X */
240 for (k = 0; k < 2 * r; k++) {
241 for (i = 0; i < 16; i++) {
242 le32enc(&B[(k * 16 + (i * 5 % 16)) * 4],
243 X32[k * 16 + i]);
244 }
245 }
246 }
247
248 #endif /* CPUSUPPORT_X86_SSE2 */
249