~ubuntu-branches/ubuntu/trusty/ceph/trusty-updates
» Revision
55
: src/erasure-code/jerasure/gf-complete/src/gf_w64.c
« back to all changes in this revision
Viewing changes to src/erasure-code/jerasure/gf-complete/src/gf_w64.c
- browse files at revision 55
- compare with another revision
- download diff
- download tarball
- view history from revision 55
- Committer: Package Import Robot
- Author(s): James Page
- Date: 2014-04-09 11:14:03 UTC
- mfrom: (1.1.33)
- Revision ID: package-import@ubuntu.com-20140409111403-jlql95pa8kg1nk9a
Tags: 0.79-0ubuntu1
* New upstream release (LP: #1278466):
- d/p/modules.patch: Refreshed.
- d/ceph.install: Install all jerasure modules.
- d/p/modules.patch: Refreshed.
- d/ceph.install: Install all jerasure modules.
- files added:
- m4/ax_intel.m4
- src/erasure-code/jerasure/gf-complete
- src/erasure-code/jerasure/gf-complete/include
- src/erasure-code/jerasure/gf-complete/src
- src/erasure-code/jerasure/jerasure
- src/erasure-code/jerasure/jerasure/include
- src/erasure-code/jerasure/jerasure/src
- files removed:
- src/erasure-code/jerasure/cauchy.c
- files modified:
- .pc/modules.patch/src/erasure-code/jerasure/Makefile.am
added
removed
src/erasure-code/jerasure/gf-complete/src/gf_w64.c
1
/*
2
* GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic
3
* James S. Plank, Ethan L. Miller, Kevin M. Greenan,
4
* Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride.
5
*
6
* gf_w64.c
7
*
8
* Routines for 64-bit Galois fields
9
*/
10
11
#include "gf_int.h"
12
#include <stdio.h>
13
#include <stdlib.h>
14
15
#define GF_FIELD_WIDTH (64)
16
#define GF_FIRST_BIT (1ULL << 63)
17
18
#define GF_BASE_FIELD_WIDTH (32)
19
#define GF_BASE_FIELD_SIZE (1ULL << GF_BASE_FIELD_WIDTH)
20
#define GF_BASE_FIELD_GROUP_SIZE GF_BASE_FIELD_SIZE-1
21
22
struct gf_w64_group_data {
23
uint64_t *reduce;
24
uint64_t *shift;
25
uint64_t *memory;
26
};
27
28
struct gf_split_4_64_lazy_data {
29
uint64_t tables[16][16];
30
uint64_t last_value;
31
};
32
33
struct gf_split_8_64_lazy_data {
34
uint64_t tables[8][(1<<8)];
35
uint64_t last_value;
36
};
37
38
struct gf_split_16_64_lazy_data {
39
uint64_t tables[4][(1<<16)];
40
uint64_t last_value;
41
};
42
43
struct gf_split_8_8_data {
44
uint64_t tables[15][256][256];
45
};
46
47
static
48
inline
49
gf_val_64_t gf_w64_inverse_from_divide (gf_t *gf, gf_val_64_t a)
50
{
51
return gf->divide.w64(gf, 1, a);
52
}
53
54
#define MM_PRINT8(s, r) { uint8_t blah[16], ii; printf("%-12s", s); _mm_storeu_si128((__m128i *)blah, r); for (ii = 0; ii < 16; ii += 1) printf("%s%02x", (ii%4==0) ? " " : " ", blah[15-ii]); printf("\n"); }
55
56
static
57
inline
58
gf_val_64_t gf_w64_divide_from_inverse (gf_t *gf, gf_val_64_t a, gf_val_64_t b)
59
{
60
b = gf->inverse.w64(gf, b);
61
return gf->multiply.w64(gf, a, b);
62
}
63
64
static
65
void
66
gf_w64_multiply_region_from_single(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int
67
xor)
68
{
69
int i;
70
gf_val_64_t *s64;
71
gf_val_64_t *d64;
72
73
s64 = (gf_val_64_t *) src;
74
d64 = (gf_val_64_t *) dest;
75
76
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
77
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
78
79
if (xor) {
80
for (i = 0; i < bytes/sizeof(gf_val_64_t); i++) {
81
d64[i] ^= gf->multiply.w64(gf, val, s64[i]);
82
}
83
} else {
84
for (i = 0; i < bytes/sizeof(gf_val_64_t); i++) {
85
d64[i] = gf->multiply.w64(gf, val, s64[i]);
86
}
87
}
88
}
89
90
#if defined(INTEL_SSE4_PCLMUL)
91
static
92
void
93
gf_w64_clm_multiply_region_from_single_2(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int
94
xor)
95
{
96
gf_val_64_t *s64, *d64, *top;
97
gf_region_data rd;
98
99
__m128i a, b;
100
__m128i result, r1;
101
__m128i prim_poly;
102
__m128i w;
103
__m128i m1, m2, m3, m4;
104
gf_internal_t * h = gf->scratch;
105
106
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
107
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
108
109
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 16);
110
gf_do_initial_region_alignment(&rd);
111
112
prim_poly = _mm_set_epi32(0, 0, 0, (uint32_t)(h->prim_poly & 0xffffffffULL));
113
b = _mm_insert_epi64 (_mm_setzero_si128(), val, 0);
114
m1 = _mm_set_epi32(0, 0, 0, (uint32_t)0xffffffff);
115
m2 = _mm_slli_si128(m1, 4);
116
m2 = _mm_or_si128(m1, m2);
117
m3 = _mm_slli_si128(m1, 8);
118
m4 = _mm_slli_si128(m3, 4);
119
120
s64 = (gf_val_64_t *) rd.s_start;
121
d64 = (gf_val_64_t *) rd.d_start;
122
top = (gf_val_64_t *) rd.d_top;
123
124
if (xor) {
125
while (d64 != top) {
126
a = _mm_load_si128((__m128i *) s64);
127
result = _mm_clmulepi64_si128 (a, b, 1);
128
129
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
130
result = _mm_xor_si128 (result, w);
131
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
132
r1 = _mm_xor_si128 (result, w);
133
134
result = _mm_clmulepi64_si128 (a, b, 0);
135
136
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
137
result = _mm_xor_si128 (result, w);
138
139
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
140
result = _mm_xor_si128 (result, w);
141
142
result = _mm_unpacklo_epi64(result, r1);
143
144
r1 = _mm_load_si128((__m128i *) d64);
145
result = _mm_xor_si128(r1, result);
146
_mm_store_si128((__m128i *) d64, result);
147
d64 += 2;
148
s64 += 2;
149
}
150
} else {
151
while (d64 != top) {
152
153
a = _mm_load_si128((__m128i *) s64);
154
result = _mm_clmulepi64_si128 (a, b, 1);
155
156
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
157
result = _mm_xor_si128 (result, w);
158
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
159
r1 = _mm_xor_si128 (result, w);
160
161
result = _mm_clmulepi64_si128 (a, b, 0);
162
163
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
164
result = _mm_xor_si128 (result, w);
165
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
166
result = _mm_xor_si128 (result, w);
167
168
result = _mm_unpacklo_epi64(result, r1);
169
170
_mm_store_si128((__m128i *) d64, result);
171
d64 += 2;
172
s64 += 2;
173
}
174
}
175
gf_do_final_region_alignment(&rd);
176
}
177
#endif
178
179
#if defined(INTEL_SSE4_PCLMUL)
180
static
181
void
182
gf_w64_clm_multiply_region_from_single_4(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int
183
xor)
184
{
185
gf_val_64_t *s64, *d64, *top;
186
gf_region_data rd;
187
188
__m128i a, b;
189
__m128i result, r1;
190
__m128i prim_poly;
191
__m128i w;
192
__m128i m1, m3, m4;
193
gf_internal_t * h = gf->scratch;
194
195
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
196
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
197
198
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 16);
199
gf_do_initial_region_alignment(&rd);
200
201
prim_poly = _mm_set_epi32(0, 0, 0, (uint32_t)(h->prim_poly & 0xffffffffULL));
202
b = _mm_insert_epi64 (_mm_setzero_si128(), val, 0);
203
m1 = _mm_set_epi32(0, 0, 0, (uint32_t)0xffffffff);
204
m3 = _mm_slli_si128(m1, 8);
205
m4 = _mm_slli_si128(m3, 4);
206
207
s64 = (gf_val_64_t *) rd.s_start;
208
d64 = (gf_val_64_t *) rd.d_start;
209
top = (gf_val_64_t *) rd.d_top;
210
211
if (xor) {
212
while (d64 != top) {
213
a = _mm_load_si128((__m128i *) s64);
214
result = _mm_clmulepi64_si128 (a, b, 1);
215
216
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
217
result = _mm_xor_si128 (result, w);
218
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
219
r1 = _mm_xor_si128 (result, w);
220
221
result = _mm_clmulepi64_si128 (a, b, 0);
222
223
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
224
result = _mm_xor_si128 (result, w);
225
226
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
227
result = _mm_xor_si128 (result, w);
228
229
result = _mm_unpacklo_epi64(result, r1);
230
231
r1 = _mm_load_si128((__m128i *) d64);
232
result = _mm_xor_si128(r1, result);
233
_mm_store_si128((__m128i *) d64, result);
234
d64 += 2;
235
s64 += 2;
236
}
237
} else {
238
while (d64 != top) {
239
a = _mm_load_si128((__m128i *) s64);
240
result = _mm_clmulepi64_si128 (a, b, 1);
241
242
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
243
result = _mm_xor_si128 (result, w);
244
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
245
r1 = _mm_xor_si128 (result, w);
246
247
result = _mm_clmulepi64_si128 (a, b, 0);
248
249
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m4), prim_poly, 1);
250
result = _mm_xor_si128 (result, w);
251
w = _mm_clmulepi64_si128 (_mm_and_si128(result, m3), prim_poly, 1);
252
result = _mm_xor_si128 (result, w);
253
254
result = _mm_unpacklo_epi64(result, r1);
255
256
_mm_store_si128((__m128i *) d64, result);
257
d64 += 2;
258
s64 += 2;
259
}
260
}
261
gf_do_final_region_alignment(&rd);
262
}
263
#endif
264
265
static
266
inline
267
gf_val_64_t gf_w64_euclid (gf_t *gf, gf_val_64_t b)
268
{
269
gf_val_64_t e_i, e_im1, e_ip1;
270
gf_val_64_t d_i, d_im1, d_ip1;
271
gf_val_64_t y_i, y_im1, y_ip1;
272
gf_val_64_t c_i;
273
gf_val_64_t one = 1;
274
275
if (b == 0) return -1;
276
e_im1 = ((gf_internal_t *) (gf->scratch))->prim_poly;
277
e_i = b;
278
d_im1 = 64;
279
for (d_i = d_im1-1; ((one << d_i) & e_i) == 0; d_i--) ;
280
y_i = 1;
281
y_im1 = 0;
282
283
while (e_i != 1) {
284
285
e_ip1 = e_im1;
286
d_ip1 = d_im1;
287
c_i = 0;
288
289
while (d_ip1 >= d_i) {
290
c_i ^= (one << (d_ip1 - d_i));
291
e_ip1 ^= (e_i << (d_ip1 - d_i));
292
d_ip1--;
293
if (e_ip1 == 0) return 0;
294
while ((e_ip1 & (one << d_ip1)) == 0) d_ip1--;
295
}
296
297
y_ip1 = y_im1 ^ gf->multiply.w64(gf, c_i, y_i);
298
y_im1 = y_i;
299
y_i = y_ip1;
300
301
e_im1 = e_i;
302
d_im1 = d_i;
303
e_i = e_ip1;
304
d_i = d_ip1;
305
}
306
307
return y_i;
308
}
309
310
/* JSP: GF_MULT_SHIFT: The world's dumbest multiplication algorithm. I only
311
include it for completeness. It does have the feature that it requires no
312
extra memory.
313
*/
314
315
static
316
inline
317
gf_val_64_t
318
gf_w64_shift_multiply (gf_t *gf, gf_val_64_t a64, gf_val_64_t b64)
319
{
320
uint64_t pl, pr, ppl, ppr, i, a, bl, br, one, lbit;
321
gf_internal_t *h;
322
323
h = (gf_internal_t *) gf->scratch;
324
ppr = h->prim_poly;
325
326
/* Allen: set leading one of primitive polynomial */
327
328
ppl = 1;
329
330
a = a64;
331
bl = 0;
332
br = b64;
333
one = 1;
334
lbit = (one << 63);
335
336
pl = 0; /* Allen: left side of product */
337
pr = 0; /* Allen: right side of product */
338
339
/* Allen: unlike the corresponding functions for smaller word sizes,
340
* this loop carries out the initial carryless multiply by
341
* shifting b itself rather than simply looking at successively
342
* higher shifts of b */
343
344
for (i = 0; i < GF_FIELD_WIDTH; i++) {
345
if (a & (one << i)) {
346
pl ^= bl;
347
pr ^= br;
348
}
349
350
bl <<= 1;
351
if (br & lbit) bl ^= 1;
352
br <<= 1;
353
}
354
355
/* Allen: the name of the variable "one" is no longer descriptive at this point */
356
357
one = lbit >> 1;
358
ppl = (h->prim_poly >> 2) | one;
359
ppr = (h->prim_poly << (GF_FIELD_WIDTH-2));
360
while (one != 0) {
361
if (pl & one) {
362
pl ^= ppl;
363
pr ^= ppr;
364
}
365
one >>= 1;
366
ppr >>= 1;
367
if (ppl & 1) ppr ^= lbit;
368
ppl >>= 1;
369
}
370
return pr;
371
}
372
373
/*
374
* ELM: Use the Intel carryless multiply instruction to do very fast 64x64 multiply.
375
*/
376
377
static
378
inline
379
gf_val_64_t
380
gf_w64_clm_multiply_2 (gf_t *gf, gf_val_64_t a64, gf_val_64_t b64)
381
{
382
gf_val_64_t rv = 0;
383
384
#if defined(INTEL_SSE4_PCLMUL)
385
386
__m128i a, b;
387
__m128i result;
388
__m128i prim_poly;
389
__m128i v, w;
390
gf_internal_t * h = gf->scratch;
391
392
a = _mm_insert_epi64 (_mm_setzero_si128(), a64, 0);
393
b = _mm_insert_epi64 (a, b64, 0);
394
prim_poly = _mm_set_epi32(0, 0, 0, (uint32_t)(h->prim_poly & 0xffffffffULL));
395
/* Do the initial multiply */
396
397
result = _mm_clmulepi64_si128 (a, b, 0);
398
399
/* Mask off the high order 32 bits using subtraction of the polynomial.
400
* NOTE: this part requires that the polynomial have at least 32 leading 0 bits.
401
*/
402
403
/* Adam: We cant include the leading one in the 64 bit pclmul,
404
so we need to split up the high 8 bytes of the result into two
405
parts before we multiply them with the prim_poly.*/
406
407
v = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
408
w = _mm_clmulepi64_si128 (prim_poly, v, 0);
409
result = _mm_xor_si128 (result, w);
410
v = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
411
w = _mm_clmulepi64_si128 (prim_poly, v, 0);
412
result = _mm_xor_si128 (result, w);
413
414
rv = ((gf_val_64_t)_mm_extract_epi64(result, 0));
415
#endif
416
return rv;
417
}
418
419
static
420
inline
421
gf_val_64_t
422
gf_w64_clm_multiply_4 (gf_t *gf, gf_val_64_t a64, gf_val_64_t b64)
423
{
424
gf_val_64_t rv = 0;
425
426
#if defined(INTEL_SSE4_PCLMUL)
427
428
__m128i a, b;
429
__m128i result;
430
__m128i prim_poly;
431
__m128i v, w;
432
gf_internal_t * h = gf->scratch;
433
434
a = _mm_insert_epi64 (_mm_setzero_si128(), a64, 0);
435
b = _mm_insert_epi64 (a, b64, 0);
436
prim_poly = _mm_set_epi32(0, 0, 0, (uint32_t)(h->prim_poly & 0xffffffffULL));
437
438
/* Do the initial multiply */
439
440
result = _mm_clmulepi64_si128 (a, b, 0);
441
442
v = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
443
w = _mm_clmulepi64_si128 (prim_poly, v, 0);
444
result = _mm_xor_si128 (result, w);
445
v = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
446
w = _mm_clmulepi64_si128 (prim_poly, v, 0);
447
result = _mm_xor_si128 (result, w);
448
449
v = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
450
w = _mm_clmulepi64_si128 (prim_poly, v, 0);
451
result = _mm_xor_si128 (result, w);
452
v = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
453
w = _mm_clmulepi64_si128 (prim_poly, v, 0);
454
result = _mm_xor_si128 (result, w);
455
456
rv = ((gf_val_64_t)_mm_extract_epi64(result, 0));
457
#endif
458
return rv;
459
}
460
461
462
void
463
gf_w64_clm_multiply_region(gf_t *gf, void *src, void *dest, uint64_t val, int bytes, int xor)
464
{
465
#if defined(INTEL_SSE4_PCLMUL)
466
gf_internal_t *h;
467
uint8_t *s8, *d8, *dtop;
468
gf_region_data rd;
469
__m128i v, b, m, prim_poly, c, fr, w, result;
470
471
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
472
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
473
474
h = (gf_internal_t *) gf->scratch;
475
476
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 16);
477
gf_do_initial_region_alignment(&rd);
478
479
s8 = (uint8_t *) rd.s_start;
480
d8 = (uint8_t *) rd.d_start;
481
dtop = (uint8_t *) rd.d_top;
482
483
v = _mm_insert_epi64(_mm_setzero_si128(), val, 0);
484
m = _mm_set_epi32(0, 0, 0xffffffff, 0xffffffff);
485
prim_poly = _mm_set_epi32(0, 0, 0, (uint32_t)(h->prim_poly & 0xffffffffULL));
486
487
if (xor) {
488
while (d8 != dtop) {
489
b = _mm_load_si128((__m128i *) s8);
490
result = _mm_clmulepi64_si128 (b, v, 0);
491
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
492
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
493
result = _mm_xor_si128 (result, w);
494
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
495
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
496
fr = _mm_xor_si128 (result, w);
497
fr = _mm_and_si128 (fr, m);
498
499
result = _mm_clmulepi64_si128 (b, v, 1);
500
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
501
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
502
result = _mm_xor_si128 (result, w);
503
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
504
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
505
result = _mm_xor_si128 (result, w);
506
result = _mm_slli_si128 (result, 8);
507
fr = _mm_xor_si128 (result, fr);
508
result = _mm_load_si128((__m128i *) d8);
509
fr = _mm_xor_si128 (result, fr);
510
511
_mm_store_si128((__m128i *) d8, fr);
512
d8 += 16;
513
s8 += 16;
514
}
515
} else {
516
while (d8 < dtop) {
517
b = _mm_load_si128((__m128i *) s8);
518
result = _mm_clmulepi64_si128 (b, v, 0);
519
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
520
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
521
result = _mm_xor_si128 (result, w);
522
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
523
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
524
fr = _mm_xor_si128 (result, w);
525
fr = _mm_and_si128 (fr, m);
526
527
result = _mm_clmulepi64_si128 (b, v, 1);
528
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 0);
529
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
530
result = _mm_xor_si128 (result, w);
531
c = _mm_insert_epi32 (_mm_srli_si128 (result, 8), 0, 1);
532
w = _mm_clmulepi64_si128 (prim_poly, c, 0);
533
result = _mm_xor_si128 (result, w);
534
result = _mm_slli_si128 (result, 8);
535
fr = _mm_xor_si128 (result, fr);
536
537
_mm_store_si128((__m128i *) d8, fr);
538
d8 += 16;
539
s8 += 16;
540
}
541
}
542
gf_do_final_region_alignment(&rd);
543
#endif
544
}
545
546
void
547
gf_w64_split_4_64_lazy_multiply_region(gf_t *gf, void *src, void *dest, uint64_t val, int bytes, int xor)
548
{
549
gf_internal_t *h;
550
struct gf_split_4_64_lazy_data *ld;
551
int i, j, k;
552
uint64_t pp, v, s, *s64, *d64, *top;
553
gf_region_data rd;
554
555
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
556
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
557
558
h = (gf_internal_t *) gf->scratch;
559
pp = h->prim_poly;
560
561
ld = (struct gf_split_4_64_lazy_data *) h->private;
562
563
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 8);
564
gf_do_initial_region_alignment(&rd);
565
566
if (ld->last_value != val) {
567
v = val;
568
for (i = 0; i < 16; i++) {
569
ld->tables[i][0] = 0;
570
for (j = 1; j < 16; j <<= 1) {
571
for (k = 0; k < j; k++) {
572
ld->tables[i][k^j] = (v ^ ld->tables[i][k]);
573
}
574
v = (v & GF_FIRST_BIT) ? ((v << 1) ^ pp) : (v << 1);
575
}
576
}
577
}
578
ld->last_value = val;
579
580
s64 = (uint64_t *) rd.s_start;
581
d64 = (uint64_t *) rd.d_start;
582
top = (uint64_t *) rd.d_top;
583
584
while (d64 != top) {
585
v = (xor) ? *d64 : 0;
586
s = *s64;
587
i = 0;
588
while (s != 0) {
589
v ^= ld->tables[i][s&0xf];
590
s >>= 4;
591
i++;
592
}
593
*d64 = v;
594
d64++;
595
s64++;
596
}
597
gf_do_final_region_alignment(&rd);
598
}
599
600
static
601
inline
602
uint64_t
603
gf_w64_split_8_8_multiply (gf_t *gf, uint64_t a64, uint64_t b64)
604
{
605
uint64_t product, i, j, mask, tb;
606
gf_internal_t *h;
607
struct gf_split_8_8_data *d8;
608
609
h = (gf_internal_t *) gf->scratch;
610
d8 = (struct gf_split_8_8_data *) h->private;
611
product = 0;
612
mask = 0xff;
613
614
for (i = 0; a64 != 0; i++) {
615
tb = b64;
616
for (j = 0; tb != 0; j++) {
617
product ^= d8->tables[i+j][a64&mask][tb&mask];
618
tb >>= 8;
619
}
620
a64 >>= 8;
621
}
622
return product;
623
}
624
625
void
626
gf_w64_split_8_64_lazy_multiply_region(gf_t *gf, void *src, void *dest, uint64_t val, int bytes, int xor)
627
{
628
gf_internal_t *h;
629
struct gf_split_8_64_lazy_data *ld;
630
int i, j, k;
631
uint64_t pp, v, s, *s64, *d64, *top;
632
gf_region_data rd;
633
634
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
635
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
636
637
h = (gf_internal_t *) gf->scratch;
638
pp = h->prim_poly;
639
640
ld = (struct gf_split_8_64_lazy_data *) h->private;
641
642
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 4);
643
gf_do_initial_region_alignment(&rd);
644
645
if (ld->last_value != val) {
646
v = val;
647
for (i = 0; i < 8; i++) {
648
ld->tables[i][0] = 0;
649
for (j = 1; j < 256; j <<= 1) {
650
for (k = 0; k < j; k++) {
651
ld->tables[i][k^j] = (v ^ ld->tables[i][k]);
652
}
653
v = (v & GF_FIRST_BIT) ? ((v << 1) ^ pp) : (v << 1);
654
}
655
}
656
}
657
ld->last_value = val;
658
659
s64 = (uint64_t *) rd.s_start;
660
d64 = (uint64_t *) rd.d_start;
661
top = (uint64_t *) rd.d_top;
662
663
while (d64 != top) {
664
v = (xor) ? *d64 : 0;
665
s = *s64;
666
i = 0;
667
while (s != 0) {
668
v ^= ld->tables[i][s&0xff];
669
s >>= 8;
670
i++;
671
}
672
*d64 = v;
673
d64++;
674
s64++;
675
}
676
gf_do_final_region_alignment(&rd);
677
}
678
679
void
680
gf_w64_split_16_64_lazy_multiply_region(gf_t *gf, void *src, void *dest, uint64_t val, int bytes, int xor)
681
{
682
gf_internal_t *h;
683
struct gf_split_16_64_lazy_data *ld;
684
int i, j, k;
685
uint64_t pp, v, s, *s64, *d64, *top;
686
gf_region_data rd;
687
688
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
689
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
690
691
h = (gf_internal_t *) gf->scratch;
692
pp = h->prim_poly;
693
694
ld = (struct gf_split_16_64_lazy_data *) h->private;
695
696
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 4);
697
gf_do_initial_region_alignment(&rd);
698
699
if (ld->last_value != val) {
700
v = val;
701
for (i = 0; i < 4; i++) {
702
ld->tables[i][0] = 0;
703
for (j = 1; j < (1<<16); j <<= 1) {
704
for (k = 0; k < j; k++) {
705
ld->tables[i][k^j] = (v ^ ld->tables[i][k]);
706
}
707
v = (v & GF_FIRST_BIT) ? ((v << 1) ^ pp) : (v << 1);
708
}
709
}
710
}
711
ld->last_value = val;
712
713
s64 = (uint64_t *) rd.s_start;
714
d64 = (uint64_t *) rd.d_start;
715
top = (uint64_t *) rd.d_top;
716
717
while (d64 != top) {
718
v = (xor) ? *d64 : 0;
719
s = *s64;
720
i = 0;
721
while (s != 0) {
722
v ^= ld->tables[i][s&0xffff];
723
s >>= 16;
724
i++;
725
}
726
*d64 = v;
727
d64++;
728
s64++;
729
}
730
gf_do_final_region_alignment(&rd);
731
}
732
733
static
734
int gf_w64_shift_init(gf_t *gf)
735
{
736
gf->multiply.w64 = gf_w64_shift_multiply;
737
gf->inverse.w64 = gf_w64_euclid;
738
gf->multiply_region.w64 = gf_w64_multiply_region_from_single;
739
return 1;
740
}
741
742
static
743
int gf_w64_cfm_init(gf_t *gf)
744
{
745
gf->inverse.w64 = gf_w64_euclid;
746
gf->multiply_region.w64 = gf_w64_multiply_region_from_single;
747
748
#if defined(INTEL_SSE4_PCLMUL)
749
gf_internal_t *h;
750
751
h = (gf_internal_t *) gf->scratch;
752
753
if ((0xfffffffe00000000ULL & h->prim_poly) == 0){
754
gf->multiply.w64 = gf_w64_clm_multiply_2;
755
gf->multiply_region.w64 = gf_w64_clm_multiply_region_from_single_2;
756
}else if((0xfffe000000000000ULL & h->prim_poly) == 0){
757
gf->multiply.w64 = gf_w64_clm_multiply_4;
758
gf->multiply_region.w64 = gf_w64_clm_multiply_region_from_single_4;
759
} else {
760
return 0;
761
}
762
return 1;
763
#endif
764
765
return 0;
766
}
767
768
static
769
void
770
gf_w64_group_set_shift_tables(uint64_t *shift, uint64_t val, gf_internal_t *h)
771
{
772
int i;
773
uint64_t j;
774
uint64_t one = 1;
775
int g_s;
776
777
g_s = h->arg1;
778
shift[0] = 0;
779
780
for (i = 1; i < (1 << g_s); i <<= 1) {
781
for (j = 0; j < i; j++) shift[i|j] = shift[j]^val;
782
if (val & (one << 63)) {
783
val <<= 1;
784
val ^= h->prim_poly;
785
} else {
786
val <<= 1;
787
}
788
}
789
}
790
791
static
792
inline
793
gf_val_64_t
794
gf_w64_group_multiply(gf_t *gf, gf_val_64_t a, gf_val_64_t b)
795
{
796
uint64_t top, bot, mask, tp;
797
int g_s, g_r, lshift, rshift;
798
struct gf_w64_group_data *gd;
799
800
gf_internal_t *h = (gf_internal_t *) gf->scratch;
801
g_s = h->arg1;
802
g_r = h->arg2;
803
gd = (struct gf_w64_group_data *) h->private;
804
gf_w64_group_set_shift_tables(gd->shift, b, h);
805
806
mask = ((1 << g_s) - 1);
807
top = 0;
808
bot = gd->shift[a&mask];
809
a >>= g_s;
810
811
if (a == 0) return bot;
812
lshift = 0;
813
rshift = 64;
814
815
do { /* Shifting out is straightfoward */
816
lshift += g_s;
817
rshift -= g_s;
818
tp = gd->shift[a&mask];
819
top ^= (tp >> rshift);
820
bot ^= (tp << lshift);
821
a >>= g_s;
822
} while (a != 0);
823
824
/* Reducing is a bit gross, because I don't zero out the index bits of top.
825
The reason is that we throw top away. Even better, that last (tp >> rshift)
826
is going to be ignored, so it doesn't matter how (tp >> 64) is implemented. */
827
828
lshift = ((lshift-1) / g_r) * g_r;
829
rshift = 64 - lshift;
830
mask = (1 << g_r) - 1;
831
while (lshift >= 0) {
832
tp = gd->reduce[(top >> lshift) & mask];
833
top ^= (tp >> rshift);
834
bot ^= (tp << lshift);
835
lshift -= g_r;
836
rshift += g_r;
837
}
838
839
return bot;
840
}
841
842
static
843
void gf_w64_group_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
844
{
845
int i, fzb;
846
uint64_t a64, smask, rmask, top, bot, tp;
847
int lshift, rshift, g_s, g_r;
848
gf_region_data rd;
849
uint64_t *s64, *d64, *dtop;
850
struct gf_w64_group_data *gd;
851
gf_internal_t *h = (gf_internal_t *) gf->scratch;
852
853
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
854
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
855
856
gd = (struct gf_w64_group_data *) h->private;
857
g_s = h->arg1;
858
g_r = h->arg2;
859
gf_w64_group_set_shift_tables(gd->shift, val, h);
860
861
for (i = 63; !(val & (1ULL << i)); i--) ;
862
i += g_s;
863
864
/* i is the bit position of the first zero bit in any element of
865
gd->shift[] */
866
867
if (i > 64) i = 64;
868
869
fzb = i;
870
871
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 4);
872
873
gf_do_initial_region_alignment(&rd);
874
875
s64 = (uint64_t *) rd.s_start;
876
d64 = (uint64_t *) rd.d_start;
877
dtop = (uint64_t *) rd.d_top;
878
879
smask = (1 << g_s) - 1;
880
rmask = (1 << g_r) - 1;
881
882
while (d64 < dtop) {
883
a64 = *s64;
884
885
top = 0;
886
bot = gd->shift[a64&smask];
887
a64 >>= g_s;
888
i = fzb;
889
890
if (a64 != 0) {
891
lshift = 0;
892
rshift = 64;
893
894
do {
895
lshift += g_s;
896
rshift -= g_s;
897
tp = gd->shift[a64&smask];
898
top ^= (tp >> rshift);
899
bot ^= (tp << lshift);
900
a64 >>= g_s;
901
} while (a64 != 0);
902
i += lshift;
903
904
lshift = ((i-64-1) / g_r) * g_r;
905
rshift = 64 - lshift;
906
while (lshift >= 0) {
907
tp = gd->reduce[(top >> lshift) & rmask];
908
top ^= (tp >> rshift);
909
bot ^= (tp << lshift);
910
lshift -= g_r;
911
rshift += g_r;
912
}
913
}
914
915
if (xor) bot ^= *d64;
916
*d64 = bot;
917
d64++;
918
s64++;
919
}
920
gf_do_final_region_alignment(&rd);
921
}
922
923
static
924
inline
925
gf_val_64_t
926
gf_w64_group_s_equals_r_multiply(gf_t *gf, gf_val_64_t a, gf_val_64_t b)
927
{
928
int leftover, rs;
929
uint64_t p, l, ind, a64;
930
int bits_left;
931
int g_s;
932
933
struct gf_w64_group_data *gd;
934
gf_internal_t *h = (gf_internal_t *) gf->scratch;
935
g_s = h->arg1;
936
937
gd = (struct gf_w64_group_data *) h->private;
938
gf_w64_group_set_shift_tables(gd->shift, b, h);
939
940
leftover = 64 % g_s;
941
if (leftover == 0) leftover = g_s;
942
943
rs = 64 - leftover;
944
a64 = a;
945
ind = a64 >> rs;
946
a64 <<= leftover;
947
p = gd->shift[ind];
948
949
bits_left = rs;
950
rs = 64 - g_s;
951
952
while (bits_left > 0) {
953
bits_left -= g_s;
954
ind = a64 >> rs;
955
a64 <<= g_s;
956
l = p >> rs;
957
p = (gd->shift[ind] ^ gd->reduce[l] ^ (p << g_s));
958
}
959
return p;
960
}
961
962
static
963
void gf_w64_group_s_equals_r_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
964
{
965
int leftover, rs;
966
uint64_t p, l, ind, a64;
967
int bits_left;
968
int g_s;
969
gf_region_data rd;
970
uint64_t *s64, *d64, *top;
971
struct gf_w64_group_data *gd;
972
gf_internal_t *h = (gf_internal_t *) gf->scratch;
973
974
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
975
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
976
977
gd = (struct gf_w64_group_data *) h->private;
978
g_s = h->arg1;
979
gf_w64_group_set_shift_tables(gd->shift, val, h);
980
981
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 4);
982
gf_do_initial_region_alignment(&rd);
983
984
s64 = (uint64_t *) rd.s_start;
985
d64 = (uint64_t *) rd.d_start;
986
top = (uint64_t *) rd.d_top;
987
988
leftover = 64 % g_s;
989
if (leftover == 0) leftover = g_s;
990
991
while (d64 < top) {
992
rs = 64 - leftover;
993
a64 = *s64;
994
ind = a64 >> rs;
995
a64 <<= leftover;
996
p = gd->shift[ind];
997
998
bits_left = rs;
999
rs = 64 - g_s;
1000
1001
while (bits_left > 0) {
1002
bits_left -= g_s;
1003
ind = a64 >> rs;
1004
a64 <<= g_s;
1005
l = p >> rs;
1006
p = (gd->shift[ind] ^ gd->reduce[l] ^ (p << g_s));
1007
}
1008
if (xor) p ^= *d64;
1009
*d64 = p;
1010
d64++;
1011
s64++;
1012
}
1013
gf_do_final_region_alignment(&rd);
1014
}
1015
1016
1017
static
1018
int gf_w64_group_init(gf_t *gf)
1019
{
1020
uint64_t i, j, p, index;
1021
struct gf_w64_group_data *gd;
1022
gf_internal_t *h = (gf_internal_t *) gf->scratch;
1023
int g_r, g_s;
1024
1025
g_s = h->arg1;
1026
g_r = h->arg2;
1027
1028
gd = (struct gf_w64_group_data *) h->private;
1029
gd->shift = (uint64_t *) (&(gd->memory));
1030
gd->reduce = gd->shift + (1 << g_s);
1031
1032
gd->reduce[0] = 0;
1033
for (i = 0; i < (1 << g_r); i++) {
1034
p = 0;
1035
index = 0;
1036
for (j = 0; j < g_r; j++) {
1037
if (i & (1 << j)) {
1038
p ^= (h->prim_poly << j);
1039
index ^= (1 << j);
1040
if (j > 0) index ^= (h->prim_poly >> (64-j));
1041
}
1042
}
1043
gd->reduce[index] = p;
1044
}
1045
1046
if (g_s == g_r) {
1047
gf->multiply.w64 = gf_w64_group_s_equals_r_multiply;
1048
gf->multiply_region.w64 = gf_w64_group_s_equals_r_multiply_region;
1049
} else {
1050
gf->multiply.w64 = gf_w64_group_multiply;
1051
gf->multiply_region.w64 = gf_w64_group_multiply_region;
1052
}
1053
gf->divide.w64 = NULL;
1054
gf->inverse.w64 = gf_w64_euclid;
1055
1056
return 1;
1057
}
1058
1059
static
1060
gf_val_64_t gf_w64_extract_word(gf_t *gf, void *start, int bytes, int index)
1061
{
1062
uint64_t *r64, rv;
1063
1064
r64 = (uint64_t *) start;
1065
rv = r64[index];
1066
return rv;
1067
}
1068
1069
static
1070
gf_val_64_t gf_w64_composite_extract_word(gf_t *gf, void *start, int bytes, int index)
1071
{
1072
int sub_size;
1073
gf_internal_t *h;
1074
uint8_t *r8, *top;
1075
uint64_t a, b, *r64;
1076
gf_region_data rd;
1077
1078
h = (gf_internal_t *) gf->scratch;
1079
gf_set_region_data(&rd, gf, start, start, bytes, 0, 0, 32);
1080
r64 = (uint64_t *) start;
1081
if (r64 + index < (uint64_t *) rd.d_start) return r64[index];
1082
if (r64 + index >= (uint64_t *) rd.d_top) return r64[index];
1083
index -= (((uint64_t *) rd.d_start) - r64);
1084
r8 = (uint8_t *) rd.d_start;
1085
top = (uint8_t *) rd.d_top;
1086
sub_size = (top-r8)/2;
1087
1088
a = h->base_gf->extract_word.w32(h->base_gf, r8, sub_size, index);
1089
b = h->base_gf->extract_word.w32(h->base_gf, r8+sub_size, sub_size, index);
1090
return (a | ((uint64_t)b << 32));
1091
}
1092
1093
static
1094
gf_val_64_t gf_w64_split_extract_word(gf_t *gf, void *start, int bytes, int index)
1095
{
1096
int i;
1097
uint64_t *r64, rv;
1098
uint8_t *r8;
1099
gf_region_data rd;
1100
1101
gf_set_region_data(&rd, gf, start, start, bytes, 0, 0, 128);
1102
r64 = (uint64_t *) start;
1103
if (r64 + index < (uint64_t *) rd.d_start) return r64[index];
1104
if (r64 + index >= (uint64_t *) rd.d_top) return r64[index];
1105
index -= (((uint64_t *) rd.d_start) - r64);
1106
r8 = (uint8_t *) rd.d_start;
1107
r8 += ((index & 0xfffffff0)*8);
1108
r8 += (index & 0xf);
1109
r8 += 112;
1110
rv =0;
1111
for (i = 0; i < 8; i++) {
1112
rv <<= 8;
1113
rv |= *r8;
1114
r8 -= 16;
1115
}
1116
return rv;
1117
}
1118
1119
static
1120
inline
1121
gf_val_64_t
1122
gf_w64_bytwo_b_multiply (gf_t *gf, gf_val_64_t a, gf_val_64_t b)
1123
{
1124
uint64_t prod, pp, bmask;
1125
gf_internal_t *h;
1126
1127
h = (gf_internal_t *) gf->scratch;
1128
pp = h->prim_poly;
1129
1130
prod = 0;
1131
bmask = 0x8000000000000000ULL;
1132
1133
while (1) {
1134
if (a & 1) prod ^= b;
1135
a >>= 1;
1136
if (a == 0) return prod;
1137
if (b & bmask) {
1138
b = ((b << 1) ^ pp);
1139
} else {
1140
b <<= 1;
1141
}
1142
}
1143
}
1144
1145
static
1146
inline
1147
gf_val_64_t
1148
gf_w64_bytwo_p_multiply (gf_t *gf, gf_val_64_t a, gf_val_64_t b)
1149
{
1150
uint64_t prod, pp, pmask, amask;
1151
gf_internal_t *h;
1152
1153
h = (gf_internal_t *) gf->scratch;
1154
pp = h->prim_poly;
1155
1156
prod = 0;
1157
1158
/* changed from declare then shift to just declare.*/
1159
1160
pmask = 0x8000000000000000ULL;
1161
amask = 0x8000000000000000ULL;
1162
1163
while (amask != 0) {
1164
if (prod & pmask) {
1165
prod = ((prod << 1) ^ pp);
1166
} else {
1167
prod <<= 1;
1168
}
1169
if (a & amask) prod ^= b;
1170
amask >>= 1;
1171
}
1172
return prod;
1173
}
1174
1175
static
1176
void
1177
gf_w64_bytwo_p_nosse_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
1178
{
1179
uint64_t *s64, *d64, ta, prod, amask, pmask, pp;
1180
gf_region_data rd;
1181
gf_internal_t *h;
1182
1183
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1184
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
1185
1186
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 8);
1187
gf_do_initial_region_alignment(&rd);
1188
1189
h = (gf_internal_t *) gf->scratch;
1190
1191
s64 = (uint64_t *) rd.s_start;
1192
d64 = (uint64_t *) rd.d_start;
1193
pmask = 0x80000000;
1194
pmask <<= 32;
1195
pp = h->prim_poly;
1196
1197
if (xor) {
1198
while (s64 < (uint64_t *) rd.s_top) {
1199
prod = 0;
1200
amask = pmask;
1201
ta = *s64;
1202
while (amask != 0) {
1203
prod = (prod & pmask) ? ((prod << 1) ^ pp) : (prod << 1);
1204
if (val & amask) prod ^= ta;
1205
amask >>= 1;
1206
}
1207
*d64 ^= prod;
1208
d64++;
1209
s64++;
1210
}
1211
} else {
1212
while (s64 < (uint64_t *) rd.s_top) {
1213
prod = 0;
1214
amask = pmask;
1215
ta = *s64;
1216
while (amask != 0) {
1217
prod = (prod & pmask) ? ((prod << 1) ^ pp) : (prod << 1);
1218
if (val & amask) prod ^= ta;
1219
amask >>= 1;
1220
}
1221
*d64 = prod;
1222
d64++;
1223
s64++;
1224
}
1225
}
1226
gf_do_final_region_alignment(&rd);
1227
}
1228
1229
static
1230
void
1231
gf_w64_bytwo_b_nosse_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
1232
{
1233
uint64_t *s64, *d64, ta, tb, prod, bmask, pp;
1234
gf_region_data rd;
1235
gf_internal_t *h;
1236
1237
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1238
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
1239
1240
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 8);
1241
gf_do_initial_region_alignment(&rd);
1242
1243
h = (gf_internal_t *) gf->scratch;
1244
1245
s64 = (uint64_t *) rd.s_start;
1246
d64 = (uint64_t *) rd.d_start;
1247
bmask = 0x80000000;
1248
bmask <<= 32;
1249
pp = h->prim_poly;
1250
1251
if (xor) {
1252
while (s64 < (uint64_t *) rd.s_top) {
1253
prod = 0;
1254
tb = val;
1255
ta = *s64;
1256
while (1) {
1257
if (tb & 1) prod ^= ta;
1258
tb >>= 1;
1259
if (tb == 0) break;
1260
ta = (ta & bmask) ? ((ta << 1) ^ pp) : (ta << 1);
1261
}
1262
*d64 ^= prod;
1263
d64++;
1264
s64++;
1265
}
1266
} else {
1267
while (s64 < (uint64_t *) rd.s_top) {
1268
prod = 0;
1269
tb = val;
1270
ta = *s64;
1271
while (1) {
1272
if (tb & 1) prod ^= ta;
1273
tb >>= 1;
1274
if (tb == 0) break;
1275
ta = (ta & bmask) ? ((ta << 1) ^ pp) : (ta << 1);
1276
}
1277
*d64 = prod;
1278
d64++;
1279
s64++;
1280
}
1281
}
1282
gf_do_final_region_alignment(&rd);
1283
}
1284
1285
#define SSE_AB2(pp, m1 ,m2, va, t1, t2) {\
1286
t1 = _mm_and_si128(_mm_slli_epi64(va, 1), m1); \
1287
t2 = _mm_and_si128(va, m2); \
1288
t2 = _mm_sub_epi64 (_mm_slli_epi64(t2, 1), _mm_srli_epi64(t2, (GF_FIELD_WIDTH-1))); \
1289
va = _mm_xor_si128(t1, _mm_and_si128(t2, pp)); }
1290
1291
#define BYTWO_P_ONESTEP {\
1292
SSE_AB2(pp, m1 ,m2, prod, t1, t2); \
1293
t1 = _mm_and_si128(v, one); \
1294
t1 = _mm_sub_epi64(t1, one); \
1295
t1 = _mm_and_si128(t1, ta); \
1296
prod = _mm_xor_si128(prod, t1); \
1297
v = _mm_srli_epi64(v, 1); }
1298
1299
1300
void gf_w64_bytwo_p_sse_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
1301
{
1302
#ifdef INTEL_SSE2
1303
int i;
1304
uint8_t *s8, *d8;
1305
uint64_t vrev, one64;
1306
uint64_t amask;
1307
__m128i pp, m1, m2, ta, prod, t1, t2, tp, one, v;
1308
gf_region_data rd;
1309
gf_internal_t *h;
1310
1311
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1312
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
1313
1314
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 16);
1315
gf_do_initial_region_alignment(&rd);
1316
1317
h = (gf_internal_t *) gf->scratch;
1318
one64 = 1;
1319
vrev = 0;
1320
for (i = 0; i < 64; i++) {
1321
vrev <<= 1;
1322
if (!(val & (one64 << i))) vrev |= 1;
1323
}
1324
1325
s8 = (uint8_t *) rd.s_start;
1326
d8 = (uint8_t *) rd.d_start;
1327
1328
amask = -1;
1329
amask ^= 1;
1330
pp = _mm_set1_epi64x(h->prim_poly);
1331
m1 = _mm_set1_epi64x(amask);
1332
m2 = _mm_set1_epi64x(one64 << 63);
1333
one = _mm_set1_epi64x(1);
1334
1335
while (d8 < (uint8_t *) rd.d_top) {
1336
prod = _mm_setzero_si128();
1337
v = _mm_set1_epi64x(vrev);
1338
ta = _mm_load_si128((__m128i *) s8);
1339
tp = (!xor) ? _mm_setzero_si128() : _mm_load_si128((__m128i *) d8);
1340
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1341
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1342
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1343
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1344
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1345
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1346
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1347
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1348
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1349
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1350
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1351
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1352
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1353
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1354
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1355
BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP; BYTWO_P_ONESTEP;
1356
_mm_store_si128((__m128i *) d8, _mm_xor_si128(prod, tp));
1357
d8 += 16;
1358
s8 += 16;
1359
}
1360
gf_do_final_region_alignment(&rd);
1361
#endif
1362
}
1363
1364
#ifdef INTEL_SSE2
1365
static
1366
void
1367
gf_w64_bytwo_b_sse_region_2_xor(gf_region_data *rd)
1368
{
1369
uint64_t one64, amask;
1370
uint8_t *d8, *s8;
1371
__m128i pp, m1, m2, t1, t2, va, vb;
1372
gf_internal_t *h;
1373
1374
s8 = (uint8_t *) rd->s_start;
1375
d8 = (uint8_t *) rd->d_start;
1376
1377
h = (gf_internal_t *) rd->gf->scratch;
1378
one64 = 1;
1379
amask = -1;
1380
amask ^= 1;
1381
pp = _mm_set1_epi64x(h->prim_poly);
1382
m1 = _mm_set1_epi64x(amask);
1383
m2 = _mm_set1_epi64x(one64 << 63);
1384
1385
while (d8 < (uint8_t *) rd->d_top) {
1386
va = _mm_load_si128 ((__m128i *)(s8));
1387
SSE_AB2(pp, m1, m2, va, t1, t2);
1388
vb = _mm_load_si128 ((__m128i *)(d8));
1389
vb = _mm_xor_si128(vb, va);
1390
_mm_store_si128((__m128i *)d8, vb);
1391
d8 += 16;
1392
s8 += 16;
1393
}
1394
}
1395
#endif
1396
1397
#ifdef INTEL_SSE2
1398
static
1399
void
1400
gf_w64_bytwo_b_sse_region_2_noxor(gf_region_data *rd)
1401
{
1402
uint64_t one64, amask;
1403
uint8_t *d8, *s8;
1404
__m128i pp, m1, m2, t1, t2, va;
1405
gf_internal_t *h;
1406
1407
s8 = (uint8_t *) rd->s_start;
1408
d8 = (uint8_t *) rd->d_start;
1409
1410
h = (gf_internal_t *) rd->gf->scratch;
1411
one64 = 1;
1412
amask = -1;
1413
amask ^= 1;
1414
pp = _mm_set1_epi64x(h->prim_poly);
1415
m1 = _mm_set1_epi64x(amask);
1416
m2 = _mm_set1_epi64x(one64 << 63);
1417
1418
while (d8 < (uint8_t *) rd->d_top) {
1419
va = _mm_load_si128 ((__m128i *)(s8));
1420
SSE_AB2(pp, m1, m2, va, t1, t2);
1421
_mm_store_si128((__m128i *)d8, va);
1422
d8 += 16;
1423
s8 += 16;
1424
}
1425
}
1426
#endif
1427
1428
#ifdef INTEL_SSE2
1429
static
1430
void
1431
gf_w64_bytwo_b_sse_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
1432
{
1433
uint64_t itb, amask, one64;
1434
uint8_t *d8, *s8;
1435
__m128i pp, m1, m2, t1, t2, va, vb;
1436
gf_region_data rd;
1437
gf_internal_t *h;
1438
1439
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1440
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
1441
1442
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 16);
1443
gf_do_initial_region_alignment(&rd);
1444
1445
if (val == 2) {
1446
if (xor) {
1447
gf_w64_bytwo_b_sse_region_2_xor(&rd);
1448
} else {
1449
gf_w64_bytwo_b_sse_region_2_noxor(&rd);
1450
}
1451
gf_do_final_region_alignment(&rd);
1452
return;
1453
}
1454
1455
s8 = (uint8_t *) rd.s_start;
1456
d8 = (uint8_t *) rd.d_start;
1457
h = (gf_internal_t *) gf->scratch;
1458
1459
one64 = 1;
1460
amask = -1;
1461
amask ^= 1;
1462
pp = _mm_set1_epi64x(h->prim_poly);
1463
m1 = _mm_set1_epi64x(amask);
1464
m2 = _mm_set1_epi64x(one64 << 63);
1465
1466
while (d8 < (uint8_t *) rd.d_top) {
1467
va = _mm_load_si128 ((__m128i *)(s8));
1468
vb = (!xor) ? _mm_setzero_si128() : _mm_load_si128 ((__m128i *)(d8));
1469
itb = val;
1470
while (1) {
1471
if (itb & 1) vb = _mm_xor_si128(vb, va);
1472
itb >>= 1;
1473
if (itb == 0) break;
1474
SSE_AB2(pp, m1, m2, va, t1, t2);
1475
}
1476
_mm_store_si128((__m128i *)d8, vb);
1477
d8 += 16;
1478
s8 += 16;
1479
}
1480
1481
gf_do_final_region_alignment(&rd);
1482
}
1483
#endif
1484
1485
1486
static
1487
int gf_w64_bytwo_init(gf_t *gf)
1488
{
1489
gf_internal_t *h;
1490
1491
h = (gf_internal_t *) gf->scratch;
1492
1493
if (h->mult_type == GF_MULT_BYTWO_p) {
1494
gf->multiply.w64 = gf_w64_bytwo_p_multiply;
1495
#ifdef INTEL_SSE2
1496
if (h->region_type & GF_REGION_NOSSE)
1497
gf->multiply_region.w64 = gf_w64_bytwo_p_nosse_multiply_region;
1498
else
1499
gf->multiply_region.w64 = gf_w64_bytwo_p_sse_multiply_region;
1500
#else
1501
gf->multiply_region.w64 = gf_w64_bytwo_p_nosse_multiply_region;
1502
if(h->region_type & GF_REGION_SSE)
1503
return 0;
1504
#endif
1505
} else {
1506
gf->multiply.w64 = gf_w64_bytwo_b_multiply;
1507
#ifdef INTEL_SSE2
1508
if (h->region_type & GF_REGION_NOSSE)
1509
gf->multiply_region.w64 = gf_w64_bytwo_b_nosse_multiply_region;
1510
else
1511
gf->multiply_region.w64 = gf_w64_bytwo_b_sse_multiply_region;
1512
#else
1513
gf->multiply_region.w64 = gf_w64_bytwo_b_nosse_multiply_region;
1514
if(h->region_type & GF_REGION_SSE)
1515
return 0;
1516
#endif
1517
}
1518
gf->inverse.w64 = gf_w64_euclid;
1519
return 1;
1520
}
1521
1522
1523
static
1524
gf_val_64_t
1525
gf_w64_composite_multiply(gf_t *gf, gf_val_64_t a, gf_val_64_t b)
1526
{
1527
gf_internal_t *h = (gf_internal_t *) gf->scratch;
1528
gf_t *base_gf = h->base_gf;
1529
uint32_t b0 = b & 0x00000000ffffffff;
1530
uint32_t b1 = (b & 0xffffffff00000000) >> 32;
1531
uint32_t a0 = a & 0x00000000ffffffff;
1532
uint32_t a1 = (a & 0xffffffff00000000) >> 32;
1533
uint32_t a1b1;
1534
1535
a1b1 = base_gf->multiply.w32(base_gf, a1, b1);
1536
1537
return ((uint64_t)(base_gf->multiply.w32(base_gf, a0, b0) ^ a1b1) |
1538
((uint64_t)(base_gf->multiply.w32(base_gf, a1, b0) ^ base_gf->multiply.w32(base_gf, a0, b1) ^ base_gf->multiply.w32(base_gf, a1b1, h->prim_poly)) << 32));
1539
}
1540
1541
/*
1542
* Composite field division trick (explained in 2007 tech report)
1543
*
1544
* Compute a / b = a*b^-1, where p(x) = x^2 + sx + 1
1545
*
1546
* let c = b^-1
1547
*
1548
* c*b = (s*b1c1+b1c0+b0c1)x+(b1c1+b0c0)
1549
*
1550
* want (s*b1c1+b1c0+b0c1) = 0 and (b1c1+b0c0) = 1
1551
*
1552
* let d = b1c1 and d+1 = b0c0
1553
*
1554
* solve s*b1c1+b1c0+b0c1 = 0
1555
*
1556
* solution: d = (b1b0^-1)(b1b0^-1+b0b1^-1+s)^-1
1557
*
1558
* c0 = (d+1)b0^-1
1559
* c1 = d*b1^-1
1560
*
1561
* a / b = a * c
1562
*/
1563
1564
static
1565
gf_val_64_t
1566
gf_w64_composite_inverse(gf_t *gf, gf_val_64_t a)
1567
{
1568
gf_internal_t *h = (gf_internal_t *) gf->scratch;
1569
gf_t *base_gf = h->base_gf;
1570
uint32_t a0 = a & 0x00000000ffffffff;
1571
uint32_t a1 = (a & 0xffffffff00000000) >> 32;
1572
uint32_t c0, c1, d, tmp;
1573
uint64_t c;
1574
uint32_t a0inv, a1inv;
1575
1576
if (a0 == 0) {
1577
a1inv = base_gf->inverse.w32(base_gf, a1);
1578
c0 = base_gf->multiply.w32(base_gf, a1inv, h->prim_poly);
1579
c1 = a1inv;
1580
} else if (a1 == 0) {
1581
c0 = base_gf->inverse.w32(base_gf, a0);
1582
c1 = 0;
1583
} else {
1584
a1inv = base_gf->inverse.w32(base_gf, a1);
1585
a0inv = base_gf->inverse.w32(base_gf, a0);
1586
1587
d = base_gf->multiply.w32(base_gf, a1, a0inv);
1588
1589
tmp = (base_gf->multiply.w32(base_gf, a1, a0inv) ^ base_gf->multiply.w32(base_gf, a0, a1inv) ^ h->prim_poly);
1590
tmp = base_gf->inverse.w32(base_gf, tmp);
1591
1592
d = base_gf->multiply.w32(base_gf, d, tmp);
1593
1594
c0 = base_gf->multiply.w32(base_gf, (d^1), a0inv);
1595
c1 = base_gf->multiply.w32(base_gf, d, a1inv);
1596
}
1597
1598
c = c0 | ((uint64_t)c1 << 32);
1599
1600
return c;
1601
}
1602
1603
static
1604
void
1605
gf_w64_composite_multiply_region(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
1606
{
1607
gf_internal_t *h = (gf_internal_t *) gf->scratch;
1608
gf_t *base_gf = h->base_gf;
1609
uint32_t b0 = val & 0x00000000ffffffff;
1610
uint32_t b1 = (val & 0xffffffff00000000) >> 32;
1611
uint64_t *s64, *d64;
1612
uint64_t *top;
1613
uint64_t a0, a1, a1b1;
1614
gf_region_data rd;
1615
1616
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1617
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 8);
1618
1619
s64 = rd.s_start;
1620
d64 = rd.d_start;
1621
top = rd.d_top;
1622
1623
if (xor) {
1624
while (d64 < top) {
1625
a0 = *s64 & 0x00000000ffffffff;
1626
a1 = (*s64 & 0xffffffff00000000) >> 32;
1627
a1b1 = base_gf->multiply.w32(base_gf, a1, b1);
1628
1629
*d64 ^= ((uint64_t)(base_gf->multiply.w32(base_gf, a0, b0) ^ a1b1) |
1630
((uint64_t)(base_gf->multiply.w32(base_gf, a1, b0) ^ base_gf->multiply.w32(base_gf, a0, b1) ^ base_gf->multiply.w32(base_gf, a1b1, h->prim_poly)) << 32));
1631
s64++;
1632
d64++;
1633
}
1634
} else {
1635
while (d64 < top) {
1636
a0 = *s64 & 0x00000000ffffffff;
1637
a1 = (*s64 & 0xffffffff00000000) >> 32;
1638
a1b1 = base_gf->multiply.w32(base_gf, a1, b1);
1639
1640
*d64 = ((base_gf->multiply.w32(base_gf, a0, b0) ^ a1b1) |
1641
((uint64_t)(base_gf->multiply.w32(base_gf, a1, b0) ^ base_gf->multiply.w32(base_gf, a0, b1) ^ base_gf->multiply.w32(base_gf, a1b1, h->prim_poly)) << 32));
1642
s64++;
1643
d64++;
1644
}
1645
}
1646
}
1647
1648
static
1649
void
1650
gf_w64_composite_multiply_region_alt(gf_t *gf, void *src, void *dest, gf_val_64_t val, int bytes, int xor)
1651
{
1652
gf_internal_t *h = (gf_internal_t *) gf->scratch;
1653
gf_t *base_gf = h->base_gf;
1654
gf_val_32_t val0 = val & 0x00000000ffffffff;
1655
gf_val_32_t val1 = (val & 0xffffffff00000000) >> 32;
1656
uint8_t *slow, *shigh;
1657
uint8_t *dlow, *dhigh, *top;
1658
int sub_reg_size;
1659
gf_region_data rd;
1660
1661
if (!xor) {
1662
memset(dest, 0, bytes);
1663
}
1664
1665
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 32);
1666
gf_do_initial_region_alignment(&rd);
1667
1668
slow = (uint8_t *) rd.s_start;
1669
dlow = (uint8_t *) rd.d_start;
1670
top = (uint8_t*) rd.d_top;
1671
sub_reg_size = (top - dlow)/2;
1672
shigh = slow + sub_reg_size;
1673
dhigh = dlow + sub_reg_size;
1674
1675
base_gf->multiply_region.w32(base_gf, slow, dlow, val0, sub_reg_size, xor);
1676
base_gf->multiply_region.w32(base_gf, shigh, dlow, val1, sub_reg_size, 1);
1677
base_gf->multiply_region.w32(base_gf, slow, dhigh, val1, sub_reg_size, xor);
1678
base_gf->multiply_region.w32(base_gf, shigh, dhigh, val0, sub_reg_size, 1);
1679
base_gf->multiply_region.w32(base_gf, shigh, dhigh, base_gf->multiply.w32(base_gf, h->prim_poly, val1), sub_reg_size, 1);
1680
1681
gf_do_final_region_alignment(&rd);
1682
}
1683
1684
1685
1686
static
1687
int gf_w64_composite_init(gf_t *gf)
1688
{
1689
gf_internal_t *h = (gf_internal_t *) gf->scratch;
1690
1691
if (h->region_type & GF_REGION_ALTMAP) {
1692
gf->multiply_region.w64 = gf_w64_composite_multiply_region_alt;
1693
} else {
1694
gf->multiply_region.w64 = gf_w64_composite_multiply_region;
1695
}
1696
1697
gf->multiply.w64 = gf_w64_composite_multiply;
1698
gf->divide.w64 = NULL;
1699
gf->inverse.w64 = gf_w64_composite_inverse;
1700
1701
return 1;
1702
}
1703
1704
#ifdef INTEL_SSSE3
1705
static
1706
void
1707
gf_w64_split_4_64_lazy_sse_altmap_multiply_region(gf_t *gf, void *src, void *dest, uint64_t val, int bytes, int xor)
1708
{
1709
gf_internal_t *h;
1710
int i, j, k;
1711
uint64_t pp, v, *s64, *d64, *top;
1712
__m128i si, tables[16][8], p[8], v0, mask1;
1713
struct gf_split_4_64_lazy_data *ld;
1714
uint8_t btable[16];
1715
gf_region_data rd;
1716
1717
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1718
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
1719
1720
h = (gf_internal_t *) gf->scratch;
1721
pp = h->prim_poly;
1722
1723
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 128);
1724
gf_do_initial_region_alignment(&rd);
1725
1726
s64 = (uint64_t *) rd.s_start;
1727
d64 = (uint64_t *) rd.d_start;
1728
top = (uint64_t *) rd.d_top;
1729
1730
ld = (struct gf_split_4_64_lazy_data *) h->private;
1731
1732
v = val;
1733
for (i = 0; i < 16; i++) {
1734
ld->tables[i][0] = 0;
1735
for (j = 1; j < 16; j <<= 1) {
1736
for (k = 0; k < j; k++) {
1737
ld->tables[i][k^j] = (v ^ ld->tables[i][k]);
1738
}
1739
v = (v & GF_FIRST_BIT) ? ((v << 1) ^ pp) : (v << 1);
1740
}
1741
for (j = 0; j < 8; j++) {
1742
for (k = 0; k < 16; k++) {
1743
btable[k] = (uint8_t) ld->tables[i][k];
1744
ld->tables[i][k] >>= 8;
1745
}
1746
tables[i][j] = _mm_loadu_si128((__m128i *) btable);
1747
}
1748
}
1749
1750
mask1 = _mm_set1_epi8(0xf);
1751
1752
while (d64 != top) {
1753
1754
if (xor) {
1755
for (i = 0; i < 8; i++) p[i] = _mm_load_si128 ((__m128i *) (d64+i*2));
1756
} else {
1757
for (i = 0; i < 8; i++) p[i] = _mm_setzero_si128();
1758
}
1759
i = 0;
1760
for (k = 0; k < 8; k++) {
1761
v0 = _mm_load_si128((__m128i *) s64);
1762
/* MM_PRINT8("v", v0); */
1763
s64 += 2;
1764
1765
si = _mm_and_si128(v0, mask1);
1766
1767
for (j = 0; j < 8; j++) {
1768
p[j] = _mm_xor_si128(p[j], _mm_shuffle_epi8(tables[i][j], si));
1769
}
1770
i++;
1771
v0 = _mm_srli_epi32(v0, 4);
1772
si = _mm_and_si128(v0, mask1);
1773
for (j = 0; j < 8; j++) {
1774
p[j] = _mm_xor_si128(p[j], _mm_shuffle_epi8(tables[i][j], si));
1775
}
1776
i++;
1777
}
1778
for (i = 0; i < 8; i++) {
1779
/* MM_PRINT8("v", p[i]); */
1780
_mm_store_si128((__m128i *) d64, p[i]);
1781
d64 += 2;
1782
}
1783
}
1784
gf_do_final_region_alignment(&rd);
1785
}
1786
#endif
1787
1788
#ifdef INTEL_SSE4
1789
static
1790
void
1791
gf_w64_split_4_64_lazy_sse_multiply_region(gf_t *gf, void *src, void *dest, uint64_t val, int bytes, int xor)
1792
{
1793
gf_internal_t *h;
1794
int i, j, k;
1795
uint64_t pp, v, *s64, *d64, *top;
1796
__m128i si, tables[16][8], p[8], st[8], mask1, mask8, mask16, t1;
1797
struct gf_split_4_64_lazy_data *ld;
1798
uint8_t btable[16];
1799
gf_region_data rd;
1800
1801
if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
1802
if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
1803
1804
h = (gf_internal_t *) gf->scratch;
1805
pp = h->prim_poly;
1806
1807
gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, 128);
1808
gf_do_initial_region_alignment(&rd);
1809
1810
s64 = (uint64_t *) rd.s_start;
1811
d64 = (uint64_t *) rd.d_start;
1812
top = (uint64_t *) rd.d_top;
1813
1814
ld = (struct gf_split_4_64_lazy_data *) h->private;
1815
1816
v = val;
1817
for (i = 0; i < 16; i++) {
1818
ld->tables[i][0] = 0;
1819
for (j = 1; j < 16; j <<= 1) {
1820
for (k = 0; k < j; k++) {
1821
ld->tables[i][k^j] = (v ^ ld->tables[i][k]);
1822
}
1823
v = (v & GF_FIRST_BIT) ? ((v << 1) ^ pp) : (v << 1);
1824
}
1825
for (j = 0; j < 8; j++) {
1826
for (k = 0; k < 16; k++) {
1827
btable[k] = (uint8_t) ld->tables[i][k];
1828
ld->tables[i][k] >>= 8;
1829
}
1830
tables[i][j] = _mm_loadu_si128((__m128i *) btable);
1831
}
1832
}
1833
1834
mask1 = _mm_set1_epi8(0xf);
1835
mask8 = _mm_set1_epi16(0xff);
1836
mask16 = _mm_set1_epi32(0xffff);
1837
1838
while (d64 != top) {
1839
1840
for (i = 0; i < 8; i++) p[i] = _mm_setzero_si128();
1841
1842
for (k = 0; k < 8; k++) {
1843
st[k] = _mm_load_si128((__m128i *) s64);
1844
s64 += 2;
1845
}
1846
1847
for (k = 0; k < 4; k ++) {
1848
st[k] = _mm_shuffle_epi32(st[k], _MM_SHUFFLE(3,1,2,0));
1849
st[k+4] = _mm_shuffle_epi32(st[k+4], _MM_SHUFFLE(2,0,3,1));
1850
t1 = _mm_blend_epi16(st[k], st[k+4], 0xf0);
1851
st[k] = _mm_srli_si128(st[k], 8);
1852
st[k+4] = _mm_slli_si128(st[k+4], 8);
1853
st[k+4] = _mm_blend_epi16(st[k], st[k+4], 0xf0);
1854
st[k] = t1;
1855
}
1856
1857
/*
1858
printf("After pack pass 1\n");
1859
for (k = 0; k < 8; k++) {
1860
MM_PRINT8("v", st[k]);
1861
}
1862
printf("\n");
1863
*/
1864
1865
t1 = _mm_packus_epi32(_mm_and_si128(st[0], mask16), _mm_and_si128(st[2], mask16));
1866
st[2] = _mm_packus_epi32(_mm_srli_epi32(st[0], 16), _mm_srli_epi32(st[2], 16));
1867
st[0] = t1;
1868
t1 = _mm_packus_epi32(_mm_and_si128(st[1], mask16), _mm_and_si128(st[3], mask16));
1869
st[3] = _mm_packus_epi32(_mm_srli_epi32(st[1], 16), _mm_srli_epi32(st[3], 16));
1870
st[1] = t1;
1871
t1 = _mm_packus_epi32(_mm_and_si128(st[4], mask16), _mm_and_si128(st[6], mask16));
1872
st[6] = _mm_packus_epi32(_mm_srli_epi32(st[4], 16), _mm_srli_epi32(st[6], 16));
1873
st[4] = t1;
1874
t1 = _mm_packus_epi32(_mm_and_si128(st[5], mask16), _mm_and_si128(st[7], mask16));
1875
st[7] = _mm_packus_epi32(_mm_srli_epi32(st[5], 16), _mm_srli_epi32(st[7], 16));
1876
st[5] = t1;
1877
1878
/*
1879
printf("After pack pass 2\n");
1880
for (k = 0; k < 8; k++) {
1881
MM_PRINT8("v", st[k]);
1882
}
1883
printf("\n");
1884
*/
1885
t1 = _mm_packus_epi16(_mm_and_si128(st[0], mask8), _mm_and_si128(st[1], mask8));
1886
st[1] = _mm_packus_epi16(_mm_srli_epi16(st[0], 8), _mm_srli_epi16(st[1], 8));
1887
st[0] = t1;
1888
t1 = _mm_packus_epi16(_mm_and_si128(st[2], mask8), _mm_and_si128(st[3], mask8));
1889
st[3] = _mm_packus_epi16(_mm_srli_epi16(st[2], 8), _mm_srli_epi16(st[3], 8));
1890
st[2] = t1;
1891
t1 = _mm_packus_epi16(_mm_and_si128(st[4], mask8), _mm_and_si128(st[5], mask8));
1892
st[5] = _mm_packus_epi16(_mm_srli_epi16(st[4], 8), _mm_srli_epi16(st[5], 8));
1893
st[4] = t1;
1894
t1 = _mm_packus_epi16(_mm_and_si128(st[6], mask8), _mm_and_si128(st[7], mask8));
1895
st[7] = _mm_packus_epi16(_mm_srli_epi16(st[6], 8), _mm_srli_epi16(st[7], 8));
1896
st[6] = t1;
1897
1898
/*
1899
printf("After final pack pass 2\n");
1900
for (k = 0; k < 8; k++) {
1901
MM_PRINT8("v", st[k]);
1902
}
1903
*/
1904
i = 0;
1905
for (k = 0; k < 8; k++) {
1906
si = _mm_and_si128(st[k], mask1);
1907
1908
for (j = 0; j < 8; j++) {
1909
p[j] = _mm_xor_si128(p[j], _mm_shuffle_epi8(tables[i][j], si));
1910
}
1911
i++;
1912
st[k] = _mm_srli_epi32(st[k], 4);
1913
si = _mm_and_si128(st[k], mask1);
1914
for (j = 0; j < 8; j++) {
1915
p[j] = _mm_xor_si128(p[j], _mm_shuffle_epi8(tables[i][j], si));
1916
}
1917
i++;
1918
}
1919
1920
t1 = _mm_unpacklo_epi8(p[0], p[1]);
1921
p[1] = _mm_unpackhi_epi8(p[0], p[1]);
1922
p[0] = t1;
1923
t1 = _mm_unpacklo_epi8(p[2], p[3]);
1924
p[3] = _mm_unpackhi_epi8(p[2], p[3]);
1925
p[2] = t1;
1926
t1 = _mm_unpacklo_epi8(p[4], p[5]);
1927
p[5] = _mm_unpackhi_epi8(p[4], p[5]);
1928
p[4] = t1;
1929
t1 = _mm_unpacklo_epi8(p[6], p[7]);
1930
p[7] = _mm_unpackhi_epi8(p[6], p[7]);
1931
p[6] = t1;
1932
1933
/*
1934
printf("After unpack pass 1:\n");
1935
for (i = 0; i < 8; i++) {
1936
MM_PRINT8("v", p[i]);
1937
}
1938
*/
1939
1940
t1 = _mm_unpacklo_epi16(p[0], p[2]);
1941
p[2] = _mm_unpackhi_epi16(p[0], p[2]);
1942
p[0] = t1;
1943
t1 = _mm_unpacklo_epi16(p[1], p[3]);
1944
p[3] = _mm_unpackhi_epi16(p[1], p[3]);
1945
p[1] = t1;
1946
t1 = _mm_unpacklo_epi16(p[4], p[6]);
1947
p[6] = _mm_unpackhi_epi16(p[4], p[6]);
1948
p[4] = t1;
1949
t1 = _mm_unpacklo_epi16(p[5], p[7]);
1950
p[7] = _mm_unpackhi_epi16(p[5], p[7]);
1951
p[5] = t1;
1952
1953
/*
1954
printf("After unpack pass 2:\n");
1955
for (i = 0; i < 8; i++) {
1956
MM_PRINT8("v", p[i]);
1957
}
1958
*/
1959
1960
t1 = _mm_unpacklo_epi32(p[0], p[4]);
1961
p[4] = _mm_unpackhi_epi32(p[0], p[4]);
1962
p[0] = t1;
1963
t1 = _mm_unpacklo_epi32(p[1], p[5]);
1964
p[5] = _mm_unpackhi_epi32(p[1], p[5]);
1965
p[1] = t1;
1966
t1 = _mm_unpacklo_epi32(p[2], p[6]);
1967
p[6] = _mm_unpackhi_epi32(p[2], p[6]);
1968
p[2] = t1;
1969
t1 = _mm_unpacklo_epi32(p[3], p[7]);
1970
p[7] = _mm_unpackhi_epi32(p[3], p[7]);
1971
p[3] = t1;
1972
1973
if (xor) {
1974
for (i = 0; i < 8; i++) {
1975
t1 = _mm_load_si128((__m128i *) d64);
1976
_mm_store_si128((__m128i *) d64, _mm_xor_si128(p[i], t1));
1977
d64 += 2;
1978
}
1979
} else {
1980
for (i = 0; i < 8; i++) {
1981
_mm_store_si128((__m128i *) d64, p[i]);
1982
d64 += 2;
1983
}
1984
}
1985
1986
}
1987
1988
gf_do_final_region_alignment(&rd);
1989
}
1990
#endif
1991
1992
#define GF_MULTBY_TWO(p) (((p) & GF_FIRST_BIT) ? (((p) << 1) ^ h->prim_poly) : (p) << 1);
1993
1994
static
1995
int gf_w64_split_init(gf_t *gf)
1996
{
1997
gf_internal_t *h;
1998
struct gf_split_4_64_lazy_data *d4;
1999
struct gf_split_8_64_lazy_data *d8;
2000
struct gf_split_8_8_data *d88;
2001
struct gf_split_16_64_lazy_data *d16;
2002
uint64_t p, basep;
2003
int exp, i, j;
2004
2005
h = (gf_internal_t *) gf->scratch;
2006
2007
/* Defaults */
2008
2009
gf->multiply_region.w64 = gf_w64_multiply_region_from_single;
2010
2011
gf->multiply.w64 = gf_w64_bytwo_p_multiply;
2012
2013
#if defined(INTEL_SSE4_PCLMUL)
2014
if ((!(h->region_type & GF_REGION_NOSSE) &&
2015
(h->arg1 == 64 || h->arg2 == 64)) ||
2016
h->mult_type == GF_MULT_DEFAULT){
2017
2018
if ((0xfffffffe00000000ULL & h->prim_poly) == 0){
2019
gf->multiply.w64 = gf_w64_clm_multiply_2;
2020
gf->multiply_region.w64 = gf_w64_clm_multiply_region_from_single_2;
2021
}else if((0xfffe000000000000ULL & h->prim_poly) == 0){
2022
gf->multiply.w64 = gf_w64_clm_multiply_4;
2023
gf->multiply_region.w64 = gf_w64_clm_multiply_region_from_single_4;
2024
}else{
2025
return 0;
2026
}
2027
}
2028
#endif
2029
2030
gf->inverse.w64 = gf_w64_euclid;
2031
2032
/* Allen: set region pointers for default mult type. Single pointers are
2033
* taken care of above (explicitly for sse, implicitly for no sse). */
2034
2035
#ifdef INTEL_SSE4
2036
if (h->mult_type == GF_MULT_DEFAULT) {
2037
d4 = (struct gf_split_4_64_lazy_data *) h->private;
2038
d4->last_value = 0;
2039
gf->multiply_region.w64 = gf_w64_split_4_64_lazy_sse_multiply_region;
2040
}
2041
#else
2042
if (h->mult_type == GF_MULT_DEFAULT) {
2043
d8 = (struct gf_split_8_64_lazy_data *) h->private;
2044
d8->last_value = 0;
2045
gf->multiply_region.w64 = gf_w64_split_8_64_lazy_multiply_region;
2046
}
2047
#endif
2048
2049
if ((h->arg1 == 4 && h->arg2 == 64) || (h->arg1 == 64 && h->arg2 == 4)) {
2050
d4 = (struct gf_split_4_64_lazy_data *) h->private;
2051
d4->last_value = 0;
2052
2053
if((h->region_type & GF_REGION_ALTMAP) && (h->region_type & GF_REGION_NOSSE)) return 0;
2054
if(h->region_type & GF_REGION_ALTMAP)
2055
{
2056
#ifdef INTEL_SSSE3
2057
gf->multiply_region.w64 = gf_w64_split_4_64_lazy_sse_altmap_multiply_region;
2058
#else
2059
return 0;
2060
#endif
2061
}
2062
else //no altmap
2063
{
2064
#ifdef INTEL_SSE4
2065
if(h->region_type & GF_REGION_NOSSE)
2066
gf->multiply_region.w64 = gf_w64_split_4_64_lazy_multiply_region;
2067
else
2068
gf->multiply_region.w64 = gf_w64_split_4_64_lazy_sse_multiply_region;
2069
#else
2070
gf->multiply_region.w64 = gf_w64_split_4_64_lazy_multiply_region;
2071
if(h->region_type & GF_REGION_SSE)
2072
return 0;
2073
#endif
2074
}
2075
}
2076
if ((h->arg1 == 8 && h->arg2 == 64) || (h->arg1 == 64 && h->arg2 == 8)) {
2077
d8 = (struct gf_split_8_64_lazy_data *) h->private;
2078
d8->last_value = 0;
2079
gf->multiply_region.w64 = gf_w64_split_8_64_lazy_multiply_region;
2080
}
2081
if ((h->arg1 == 16 && h->arg2 == 64) || (h->arg1 == 64 && h->arg2 == 16)) {
2082
d16 = (struct gf_split_16_64_lazy_data *) h->private;
2083
d16->last_value = 0;
2084
gf->multiply_region.w64 = gf_w64_split_16_64_lazy_multiply_region;
2085
}
2086
if ((h->arg1 == 8 && h->arg2 == 8)) {
2087
d88 = (struct gf_split_8_8_data *) h->private;
2088
gf->multiply.w64 = gf_w64_split_8_8_multiply;
2089
2090
/* The performance of this guy sucks, so don't bother with a region op */
2091
2092
basep = 1;
2093
for (exp = 0; exp < 15; exp++) {
2094
for (j = 0; j < 256; j++) d88->tables[exp][0][j] = 0;
2095
for (i = 0; i < 256; i++) d88->tables[exp][i][0] = 0;
2096
d88->tables[exp][1][1] = basep;
2097
for (i = 2; i < 256; i++) {
2098
if (i&1) {
2099
p = d88->tables[exp][i^1][1];
2100
d88->tables[exp][i][1] = p ^ basep;
2101
} else {
2102
p = d88->tables[exp][i>>1][1];
2103
d88->tables[exp][i][1] = GF_MULTBY_TWO(p);
2104
}
2105
}
2106
for (i = 1; i < 256; i++) {
2107
p = d88->tables[exp][i][1];
2108
for (j = 1; j < 256; j++) {
2109
if (j&1) {
2110
d88->tables[exp][i][j] = d88->tables[exp][i][j^1] ^ p;
2111
} else {
2112
d88->tables[exp][i][j] = GF_MULTBY_TWO(d88->tables[exp][i][j>>1]);
2113
}
2114
}
2115
}
2116
for (i = 0; i < 8; i++) basep = GF_MULTBY_TWO(basep);
2117
}
2118
}
2119
return 1;
2120
}
2121
2122
int gf_w64_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2)
2123
{
2124
switch(mult_type)
2125
{
2126
case GF_MULT_SHIFT:
2127
return sizeof(gf_internal_t);
2128
break;
2129
case GF_MULT_CARRY_FREE:
2130
return sizeof(gf_internal_t);
2131
break;
2132
case GF_MULT_BYTWO_p:
2133
case GF_MULT_BYTWO_b:
2134
return sizeof(gf_internal_t);
2135
break;
2136
2137
case GF_MULT_DEFAULT:
2138
2139
/* Allen: set the *local* arg1 and arg2, just for scratch size purposes,
2140
* then fall through to split table scratch size code. */
2141
2142
#ifdef INTEL_SSE4
2143
arg1 = 64;
2144
arg2 = 4;
2145
#else
2146
arg1 = 64;
2147
arg2 = 8;
2148
#endif
2149
2150
case GF_MULT_SPLIT_TABLE:
2151
if (arg1 == 8 && arg2 == 8) {
2152
return sizeof(gf_internal_t) + sizeof(struct gf_split_8_8_data) + 64;
2153
}
2154
if ((arg1 == 16 && arg2 == 64) || (arg2 == 16 && arg1 == 64)) {
2155
return sizeof(gf_internal_t) + sizeof(struct gf_split_16_64_lazy_data) + 64;
2156
}
2157
if ((arg1 == 8 && arg2 == 64) || (arg2 == 8 && arg1 == 64)) {
2158
return sizeof(gf_internal_t) + sizeof(struct gf_split_8_64_lazy_data) + 64;
2159
}
2160
2161
if ((arg1 == 64 && arg2 == 4) || (arg1 == 4 && arg2 == 64)) {
2162
return sizeof(gf_internal_t) + sizeof(struct gf_split_4_64_lazy_data) + 64;
2163
}
2164
return 0;
2165
case GF_MULT_GROUP:
2166
return sizeof(gf_internal_t) + sizeof(struct gf_w64_group_data) +
2167
sizeof(uint64_t) * (1 << arg1) +
2168
sizeof(uint64_t) * (1 << arg2) + 64;
2169
break;
2170
case GF_MULT_COMPOSITE:
2171
if (arg1 == 2) return sizeof(gf_internal_t) + 64;
2172
return 0;
2173
break;
2174
default:
2175
return 0;
2176
}
2177
}
2178
2179
int gf_w64_init(gf_t *gf)
2180
{
2181
gf_internal_t *h;
2182
int no_default_flag = 0;
2183
2184
h = (gf_internal_t *) gf->scratch;
2185
2186
/* Allen: set default primitive polynomial / irreducible polynomial if needed */
2187
2188
/* Omitting the leftmost 1 as in w=32 */
2189
2190
if (h->prim_poly == 0) {
2191
if (h->mult_type == GF_MULT_COMPOSITE) {
2192
h->prim_poly = gf_composite_get_default_poly(h->base_gf);
2193
if (h->prim_poly == 0) return 0; /* This shouldn't happen */
2194
} else {
2195
h->prim_poly = 0x1b;
2196
}
2197
if (no_default_flag == 1) {
2198
fprintf(stderr,"Code contains no default irreducible polynomial for given base field\n");
2199
return 0;
2200
}
2201
}
2202
2203
gf->multiply.w64 = NULL;
2204
gf->divide.w64 = NULL;
2205
gf->inverse.w64 = NULL;
2206
gf->multiply_region.w64 = NULL;
2207
2208
switch(h->mult_type) {
2209
case GF_MULT_CARRY_FREE: if (gf_w64_cfm_init(gf) == 0) return 0; break;
2210
case GF_MULT_SHIFT: if (gf_w64_shift_init(gf) == 0) return 0; break;
2211
case GF_MULT_COMPOSITE: if (gf_w64_composite_init(gf) == 0) return 0; break;
2212
case GF_MULT_DEFAULT:
2213
case GF_MULT_SPLIT_TABLE: if (gf_w64_split_init(gf) == 0) return 0; break;
2214
case GF_MULT_GROUP: if (gf_w64_group_init(gf) == 0) return 0; break;
2215
case GF_MULT_BYTWO_p:
2216
case GF_MULT_BYTWO_b: if (gf_w64_bytwo_init(gf) == 0) return 0; break;
2217
default: return 0;
2218
}
2219
if (h->divide_type == GF_DIVIDE_EUCLID) {
2220
gf->divide.w64 = gf_w64_divide_from_inverse;
2221
gf->inverse.w64 = gf_w64_euclid;
2222
}
2223
2224
if (gf->inverse.w64 != NULL && gf->divide.w64 == NULL) {
2225
gf->divide.w64 = gf_w64_divide_from_inverse;
2226
}
2227
if (gf->inverse.w64 == NULL && gf->divide.w64 != NULL) {
2228
gf->inverse.w64 = gf_w64_inverse_from_divide;
2229
}
2230
2231
if (h->region_type == GF_REGION_CAUCHY) return 0;
2232
2233
if (h->region_type & GF_REGION_ALTMAP) {
2234
if (h->mult_type == GF_MULT_COMPOSITE) {
2235
gf->extract_word.w64 = gf_w64_composite_extract_word;
2236
} else if (h->mult_type == GF_MULT_SPLIT_TABLE) {
2237
gf->extract_word.w64 = gf_w64_split_extract_word;
2238
}
2239
} else {
2240
gf->extract_word.w64 = gf_w64_extract_word;
2241
}
2242
2243
return 1;
2244
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1