source: trunk/lib/carryQ.h @ 1212

Last change on this file since 1212 was 1212, checked in by cameron, 8 years ago

Bitblock_advance32 versions

File size: 29.7 KB
Line 
1//
2// carryQ.h
3// Robert D. Cameron
4// April 8, 2011 - Merged with AVX version; add BitBlock_scantofirst
5// Dec. 5, 2010 - first queuing implementation
6// November 29, 2010 - first version without actual queueing.
7//
8
9#ifdef CARRYQ_AVX
10#define bitblock_adc adc256
11#define bitblock_sbb sbb256
12#define bitblock_advance_with_carry advance_with_carry256
13#else
14#define bitblock_adc adc128
15#define bitblock_sbb sbb128
16#define bitblock_advance_with_carry advance_with_carry
17#endif
18
19
20#ifndef CARRY_Q_H
21#define CARRY_Q_H
22
23#ifdef SIMD_CARRY_Q
24#define CARRY_Q
25#define CarryQtype SIMD_type
26#endif
27
28#ifdef ADC64_CARRY_Q
29#define CARRY_Q
30#define CarryQtype uint64_t
31#endif
32
33#ifdef CARRY_Q
34static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
35
36static inline BitBlock BitBlock_advance_ci(BitBlock strm, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
37
38static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
39
40static inline BitBlock BitBlock_advance(BitBlock strm) __attribute__ ((always_inline));
41
42static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
43
44static inline BitBlock BitBlock_add_ci(BitBlock strm1, BitBlock strm2, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
45
46static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
47
48static inline BitBlock BitBlock_add(BitBlock strm1, BitBlock strm2) __attribute__ ((always_inline));
49
50static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
51
52static inline BitBlock BitBlock_sub_ci(BitBlock strm1, BitBlock strm2, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
53
54static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
55
56static inline BitBlock BitBlock_sub(BitBlock strm1, BitBlock strm2) __attribute__ ((always_inline));
57
58static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
59
60static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
61
62static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
63
64static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass) __attribute__ ((always_inline));
65
66static inline BitBlock BitBlock_scanto_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
67
68static inline BitBlock BitBlock_scanto_ci(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
69
70static inline BitBlock BitBlock_scanto_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
71
72static inline BitBlock BitBlock_scanto(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask) __attribute__ ((always_inline));
73
74static inline BitBlock BitBlock_scantofirst(BitBlock charclass, CarryQtype & cq, const int carryno) __attribute__ ((always_inline));
75
76static inline bool CarryTest(CarryQtype & cq, const int carryno, const int carry_count) __attribute__ ((always_inline));
77
78static inline void CarryDequeueEnqueue(CarryQtype & cq, const int carryno, const int carry_count) __attribute__ ((always_inline));
79
80static inline void CarryQ_Adjust(CarryQtype & cq, const int carry_count) __attribute__ ((always_inline));
81
82static inline void CarryCombine(CarryQtype & cq, CarryQtype & local_cq, const int carryno, const int carry_count) __attribute__ ((always_inline));
83
84#endif
85
86
87#ifndef CARRY_Q
88#ifdef CARRYQ_AVX
89#include "block_carry_avx.h"
90#else
91#include "block_carry.h"
92#endif
93
94#define CarryQtype CarryType *
95
96#define CarryDeclare(name, count)\
97CarryType name[count];\
98
99#define CarryInit(name, count)\
100for (int j=0; j < count; j++) name[j] = Carry0
101
102static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
103
104static inline BitBlock BitBlock_advance_ci(BitBlock strm, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
105
106static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
107
108static inline BitBlock BitBlock_advance(BitBlock strm) __attribute__ ((always_inline));
109
110static inline BitBlock BitBlock_advance32_ci_co(BitBlock strm, uint32_t & pending32) __attribute__ ((always_inline));
111
112static inline BitBlock BitBlock_advance32_ci(BitBlock strm, uint32_t & pending32) __attribute__ ((always_inline));
113
114static inline BitBlock BitBlock_advance32_co(BitBlock strm, uint32_t & pending32) __attribute__ ((always_inline));
115
116static inline BitBlock BitBlock_advance32(BitBlock strm) __attribute__ ((always_inline));
117
118static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
119
120static inline BitBlock BitBlock_add_ci(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
121
122static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
123
124static inline BitBlock BitBlock_add(BitBlock strm1, BitBlock strm2) __attribute__ ((always_inline));
125
126static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
127
128static inline BitBlock BitBlock_sub_ci(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
129
130static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
131
132static inline BitBlock BitBlock_sub(BitBlock strm1, BitBlock strm2) __attribute__ ((always_inline));
133
134static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
135
136static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
137
138static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
139
140static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass) __attribute__ ((always_inline));
141
142static inline BitBlock BitBlock_scanto_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
143
144static inline BitBlock BitBlock_scanto_ci(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
145
146static inline BitBlock BitBlock_scanto_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
147
148static inline BitBlock BitBlock_scanto(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask) __attribute__ ((always_inline));
149
150static inline BitBlock BitBlock_scantofirst(BitBlock charclass, CarryQtype cq, const int carryno) __attribute__ ((always_inline));
151
152static inline bool CarryTest(CarryQtype cq, const int carryno, const int carry_count) __attribute__ ((always_inline));
153
154static inline void CarryDequeueEnqueue(CarryQtype cq, const int carryno, const int carry_count) __attribute__ ((always_inline));
155
156static inline void CarryQ_Adjust(CarryQtype cq, const int carry_count) __attribute__ ((always_inline));
157
158static inline void CarryCombine(CarryQtype cq, CarryQtype local_cq, const int carryno, const int carry_count) __attribute__ ((always_inline));
159
160
161static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype cq, const int carryno) {
162        BitBlock rslt;
163        bitblock_advance_with_carry(strm, cq[carryno], rslt);
164        return rslt;
165}
166
167static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype cq, const int carryno) {
168        BitBlock rslt;
169        cq[carryno] = Carry0;
170        bitblock_advance_with_carry(strm, cq[carryno], rslt);
171        return rslt;
172}
173
174static inline BitBlock BitBlock_advance_ci(BitBlock strm, CarryQtype cq, const int carryno) {
175        BitBlock rslt;
176        CarryType c = cq[carryno];
177        bitblock_advance_with_carry(strm, c, rslt);
178        return rslt;
179}
180
181static inline BitBlock BitBlock_advance(BitBlock strm) {
182        return sisd_slli(strm, 1);
183}
184
185static inline BitBlock BitBlock_advance32_ci_co(BitBlock strm, uint32_t & pending32){
186        uint32_t temp = pending32;
187        pending32 = sisd_to_int(sisd_srli(strm,96));
188        return simd_or(sisd_slli(strm, 32), sisd_from_int(temp));
189}
190
191static inline BitBlock BitBlock_advance32_ci(BitBlock strm, uint32_t & pending32) {
192        return simd_or(sisd_slli(strm, 32), sisd_from_int(pending32));
193}
194
195static inline BitBlock BitBlock_advance32_co(BitBlock strm, uint32_t & pending32) {
196        pending32 = sisd_to_int(sisd_srli(strm,96));
197        return sisd_slli(strm, 32);
198}
199
200static inline BitBlock BitBlock_advance32(BitBlock strm) {
201        return sisd_slli(strm, 32);
202}
203
204
205
206
207static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) {
208        BitBlock sum;
209        bitblock_adc(strm1, strm2, cq[carryno], sum);
210        return sum;
211}
212
213static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) {
214        BitBlock sum;
215        cq[carryno] = Carry0;
216        bitblock_adc(strm1, strm2, cq[carryno], sum);
217        return sum;
218}
219
220static inline BitBlock BitBlock_add_ci(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) {
221        BitBlock sum;
222        CarryType c = cq[carryno];
223        bitblock_adc(strm1, strm2, c, sum);
224        return sum;
225}
226
227static inline BitBlock BitBlock_add(BitBlock strm1, BitBlock strm2) {
228        BitBlock sum;
229        CarryType c = Carry0;
230        bitblock_adc(strm1, strm2, c, sum);
231        return sum;
232}
233
234static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) {
235        BitBlock diff;
236        bitblock_sbb(strm1, strm2, cq[carryno], diff);
237        return diff;
238}
239
240static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) {
241        BitBlock diff;
242        cq[carryno] = Carry0;
243        bitblock_sbb(strm1, strm2, cq[carryno], diff);
244        return diff;
245}
246
247static inline BitBlock BitBlock_sub_ci(BitBlock strm1, BitBlock strm2, CarryQtype cq, const int carryno) {
248        BitBlock diff;
249        CarryType c = cq[carryno];
250        bitblock_sbb(strm1, strm2, c, diff);
251        return diff;
252}
253
254static inline BitBlock BitBlock_sub(BitBlock strm1, BitBlock strm2) {
255        BitBlock diff;
256        CarryType c = Carry0;
257        bitblock_sbb(strm1, strm2, c, diff);
258        return diff;
259}
260
261static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) {
262        BitBlock markers1;
263        bitblock_adc(markers0, charclass, cq[carryno], markers1);
264        return simd_andc(markers1, charclass);
265}
266
267static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) {
268        BitBlock markers1;
269        cq[carryno] = Carry0;
270        bitblock_adc(markers0, charclass, cq[carryno], markers1);
271        return simd_andc(markers1, charclass);
272}
273
274static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) {
275        BitBlock markers1;
276        CarryType c = cq[carryno];
277        bitblock_adc(markers0, charclass, c, markers1);
278        return simd_andc(markers1, charclass);
279}
280
281static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass) {
282        BitBlock markers1;
283        CarryType c = Carry0;
284        bitblock_adc(markers0, charclass, c, markers1);
285        return simd_andc(markers1, charclass);
286}
287
288static inline BitBlock BitBlock_scanto_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) {
289        BitBlock markers1;
290        bitblock_adc(markers0, simd_not(charclass), cq[carryno], markers1);
291        return simd_and(markers1, charclass);
292}
293
294static inline BitBlock BitBlock_scanto_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, const int carryno) {
295        BitBlock markers1;
296        cq[carryno] = Carry0;
297        bitblock_adc(markers0, simd_not(charclass), cq[carryno], markers1);
298        return simd_and(markers1, charclass);
299}
300
301static inline BitBlock BitBlock_scanto_ci(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask, CarryQtype cq, const int carryno) {
302        BitBlock markers1;
303        CarryType c = cq[carryno];
304        BitBlock scanclass = simd_andc(EOF_mask, charclass);
305        bitblock_adc(markers0, scanclass, c, markers1);
306        return simd_andc(markers1, scanclass);
307}
308
309static inline BitBlock BitBlock_scanto(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask) {
310        BitBlock markers1;
311        CarryType c = Carry0;
312        BitBlock scanclass = simd_andc(EOF_mask, charclass);
313        bitblock_adc(markers0, scanclass, c, markers1);
314        return simd_andc(markers1, scanclass);
315}
316
317/* Scan to the first occurrence of an item in a charclass, set
318   the carry once the first occurrence has been found, after
319   which the returned BitBlock will always be zero.  */
320
321static inline BitBlock BitBlock_scantofirst(BitBlock charclass, CarryQtype cq, const int carryno) {
322        BitBlock marker;
323        CarryType c = carry_flip(cq[carryno]);
324        bitblock_adc(simd_const_1(0), simd_not(charclass), c, marker);
325        cq[carryno] = carry_flip(c);
326        return simd_and(marker, charclass);
327}
328
329
330static inline bool CarryTest(CarryQtype cq, const int carryno, const int carry_count) {
331  CarryType c1 = cq[carryno];
332  int i;
333  for (i = carryno + 1; i < carryno + carry_count; i++) {
334    c1 = carry_or(c1, cq[i]);
335  }
336  return test_carry(c1);
337}
338
339static inline void CarryDequeueEnqueue(CarryQtype cq, const int carryno, const int carry_count) {
340  // Given carryin queue with carry_count carries starting from carryno are 0,
341  // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
342  // Nothing to do when the queues are the same!
343  return;
344}
345
346static inline void CarryQ_Adjust(CarryQtype cq, const int carry_count) {
347  // Adjust the carryQ so that carries enqueued are readied for dequeiing.
348  // Nothing to do with indexed queues.
349  return;
350}
351
352static inline void CarryCombine(CarryQtype cq, CarryQtype local_cq, const int carryno, const int carry_count) {
353  int i;
354  for (i = 0; i < carry_count; i++) {
355    cq[carryno+i] = carry_or(cq[carryno+i], local_cq[i]);
356  }
357}
358#endif
359#ifdef SIMD_CARRY_Q
360
361#define CarryDeclare(name, count)\
362  CarryQtype name
363
364#define CarryInit(name, count)\
365  name = simd_const_1(0)
366
367SIMD_type carryQ_ci_mask = sisd_from_int(1);
368SIMD_type carryQ_co_mask = sisd_slli(carryQ_ci_mask, 127);
369
370static inline BitBlock BitBlock_advance_ci_co(BitBlock cursor, CarryQtype & carryQ, const int carryno) {
371  SIMD_type carry_out = simd_and(cursor, carryQ_co_mask);
372  SIMD_type carry_in = simd_and(carryQ, carryQ_ci_mask);
373  carryQ = simd_or(simd_srli_64(carryQ, 1), carry_out);
374  SIMD_type shift_out = simd_srli_64(cursor, 63);
375  SIMD_type low_bits = simd_mergel_64(shift_out, carry_in);
376  return simd_or(simd_add_64(cursor, cursor), low_bits);
377}
378
379static inline BitBlock BitBlock_advance_co(BitBlock cursor, CarryQtype & carryQ, const int carryno) {
380  SIMD_type carry_out = simd_and(cursor, carryQ_co_mask);
381  carryQ = simd_or(simd_srli_64(carryQ, 1), carry_out);
382  SIMD_type shift_out = simd_srli_64(cursor, 63);
383  SIMD_type low_bits = simd_mergel_64(shift_out, simd_const_1(0));
384  return simd_or(simd_add_64(cursor, cursor), low_bits);
385}
386
387static inline BitBlock BitBlock_advance_ci(BitBlock cursor, CarryQtype & carryQ, const int carryno) {
388  SIMD_type carry_in = simd_and(carryQ, carryQ_ci_mask);
389  carryQ = simd_srli_64(carryQ, 1);
390  SIMD_type shift_out = simd_srli_64(cursor, 63);
391  SIMD_type low_bits = simd_mergel_64(shift_out, carry_in);
392  return simd_or(simd_add_64(cursor, cursor), low_bits);
393}
394
395static inline BitBlock BitBlock_advance(BitBlock cursor) {
396  return sisd_slli(cursor, 1);
397}
398
399
400static inline BitBlock BitBlock_add_ci_co(BitBlock x, BitBlock y, CarryQtype & carryQ, const int carryno) {
401  BitBlock sum;
402  SIMD_type gen = simd_and(x, y);
403  SIMD_type prop = simd_or(x, y);
404  SIMD_type partial = simd_add_64(simd_add_64(x, y), simd_and(carryQ, carryQ_ci_mask));
405  carryQ = simd_srli_64(carryQ, 1);
406  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64);
407  sum = simd_add_64(c1, partial);
408  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_andc(prop, sum)), carryQ_co_mask));
409  return sum;
410}
411
412static inline BitBlock BitBlock_add_co(BitBlock x, BitBlock y, CarryQtype & carryQ, const int carryno) {
413  BitBlock sum;
414  SIMD_type gen = simd_and(x, y);
415  SIMD_type prop = simd_or(x, y);
416  SIMD_type partial = simd_add_64(x, y);
417  carryQ = simd_srli_64(carryQ, 1);
418  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64);
419  sum = simd_add_64(c1, partial);
420  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_andc(prop, sum)), carryQ_co_mask));
421  return sum;
422}
423
424static inline BitBlock BitBlock_add_ci(BitBlock x, BitBlock y, CarryQtype & carryQ, const int carryno) {
425  BitBlock sum;
426  SIMD_type gen = simd_and(x, y);
427  SIMD_type prop = simd_or(x, y);
428  SIMD_type partial = simd_add_64(simd_add_64(x, y), simd_and(carryQ, carryQ_ci_mask));
429  carryQ = simd_srli_64(carryQ, 1);
430  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64);
431  sum = simd_add_64(c1, partial);
432  return sum;
433}
434
435static inline BitBlock BitBlock_add(BitBlock x, BitBlock y) {
436  return simd_add_128(x, y);
437}
438
439static inline BitBlock BitBlock_sub_ci_co(BitBlock x, BitBlock y, CarryQtype & carryQ, const int carryno) {
440  BitBlock diff;
441  SIMD_type gen = simd_andc(y, x);
442  SIMD_type prop = simd_not(simd_xor(x, y));
443  SIMD_type partial = simd_sub_64(simd_sub_64(x, y), simd_and(carryQ, carryQ_ci_mask));
444  carryQ = simd_srli_64(carryQ, 1);
445  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64);
446  diff = simd_sub_64(partial, b1);
447  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_and(prop, diff)), carryQ_co_mask));
448  return diff;
449}
450
451static inline BitBlock BitBlock_sub_co(BitBlock x, BitBlock y, CarryQtype & carryQ, const int carryno) {
452  BitBlock diff;
453  SIMD_type gen = simd_andc(y, x);
454  SIMD_type prop = simd_not(simd_xor(x, y));
455  SIMD_type partial = simd_sub_64(x, y);
456  carryQ = simd_srli_64(carryQ, 1);
457  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64);
458  diff = simd_sub_64(partial, b1);
459  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_and(prop, diff)), carryQ_co_mask));
460  return diff;
461}
462
463static inline BitBlock BitBlock_sub_ci(BitBlock x, BitBlock y, CarryQtype & carryQ, const int carryno) {
464  BitBlock diff;
465  SIMD_type gen = simd_andc(y, x);
466  SIMD_type prop = simd_not(simd_xor(x, y));
467  SIMD_type partial = simd_sub_64(simd_sub_64(x, y), simd_and(carryQ, carryQ_ci_mask));
468  carryQ = simd_srli_64(carryQ, 1);
469  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64);
470  diff = simd_sub_64(partial, b1);
471  return diff;
472}
473
474static inline BitBlock BitBlock_sub(BitBlock x, BitBlock y) {
475  BitBlock diff;
476  SIMD_type gen = simd_andc(y, x);
477  SIMD_type prop = simd_not(simd_xor(x, y));
478  SIMD_type partial = simd_sub_64(x, y);
479  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64);
480  diff = simd_sub_64(partial, b1);
481  return diff;
482}
483
484typedef union {SIMD_type bitblock; uint64_t int64[2];} BitBlock_int64;
485
486static inline bool CarryTest(CarryQtype & cq, const int carryno, const int carry_count) {
487  BitBlock_int64 t;
488  t.bitblock = cq;
489  uint64_t carryQ_top_N_mask = ((1 << carry_count) -1);
490  return t.int64[0] & carryQ_top_N_mask;
491}
492
493static inline void CarryDequeueEnqueue(CarryQtype & cq, const int carryno, const int carry_count) {
494  // Given carryin queue with carry_count carries starting from carryno are 0,
495  // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
496  cq = sisd_srli(cq, carry_count);
497}
498
499static inline void CarryCombine(CarryQtype & cq, CarryQtype & local_cq, const int carryno, const int carry_count) {
500  cq = simd_or(cq, local_cq);
501}
502
503static inline void CarryQ_Adjust(CarryQtype & cq, const int carry_count) {
504  // Adjust the carryQ so that carries enqueued are readied for dequeiing.
505  cq = sisd_srli(cq, (128-carry_count));
506}
507
508
509#endif
510
511#ifdef ADC64_CARRY_Q
512
513//
514// CarryQueue implementation using 64-bit integer queues.
515// A single 64-bit integer holds both the input and output
516// carries, with bits moving right-to-left.   Thus the
517// high bit in the queue is always the next carry to be
518// dequeued; a newly enqueued carry is always inserted as
519// the low bit.
520//
521// The two typical operations for dequeueing and enqueueing
522// carryies from/to a CarryQueue cq are the following.
523// 1.  Dequeueing:  add(cq, cq)
524//     The high carry bit is dequeued and sets the processor
525//     carry flag to be used as a carry-in variable in the
526//     following bitblock operation.   This also shifts cq
527//     right one position, making room for enqueuing a new carry.
528// 2.  Enqueueing:  adc($0, cq)
529//     The carry out value of an operation as recorded in the
530//     processor carry flag is enqueued by adding it in to the
531//     low bit position of cq (this bit will have been cleared
532//     by the dequeue operation.
533
534#define CarryDeclare(name, count)\
535CarryQtype name
536
537#define CarryInit(name, count)\
538name = 0
539
540typedef union {SIMD_type bitblock; uint64_t int64[2];} BitBlock_int64;
541
542
543static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype & carryQ, const int carryno) {
544        BitBlock_int64 x, z;
545        x.bitblock = strm;
546        __asm__  __volatile__ ("add %[cq], %[cq]\n\t"
547                                                   "adc %[z1], %[z1]\n\t"
548                                                   "adc %[z2], %[z2]\n\t"
549                                                   "adc $0, %[cq]\n\t"
550                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1]), [cq] "=r" (carryQ)
551                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
552                                                   "[cq]" (carryQ)
553                                                   : "cc");
554        return z.bitblock;
555}
556
557static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype & carryQ, const int carryno) {
558        BitBlock_int64 x, z;
559        x.bitblock = strm;
560        __asm__  __volatile__ ("add %[cq], %[cq]\n\t"
561                                                   "add %[z1], %[z1]\n\t"
562                                                   "adc %[z2], %[z2]\n\t"
563                                                   "adc $0, %[cq]\n\t"
564                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1]), [cq] "=r" (carryQ)
565                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
566                                                   "[cq]" (carryQ)
567                                                   : "cc");
568        return z.bitblock;
569}
570
571static inline BitBlock BitBlock_advance_ci(BitBlock strm, CarryQtype & carryQ, const int carryno) {
572        BitBlock_int64 x, z;
573        x.bitblock = strm;
574        __asm__  __volatile__ ("add %[cq], %[cq]\n\t"
575                                                   "adc %[z1], %[z1]\n\t"
576                                                   "adc %[z2], %[z2]\n\t"
577                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1]), [cq] "=r" (carryQ)
578                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
579                                                   "[cq]" (carryQ)
580                                                   : "cc");
581        return z.bitblock;
582}
583
584static inline BitBlock BitBlock_advance(BitBlock strm) {
585        BitBlock_int64 x, z;
586        x.bitblock = strm;
587        __asm__  __volatile__ ("add %[z1], %[z1]\n\t"
588                                                   "adc %[z2], %[z2]\n\t"
589                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1])
590                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1])
591                                                   : "cc");
592        return z.bitblock;
593}
594
595
596static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
597        BitBlock_int64 rslt, x, y;
598        x.bitblock = strm1;
599        y.bitblock = strm2;
600        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
601                                                  "adc %[e1], %[z1]\n\t"
602                                                  "adc %[e2], %[z2]\n\t"
603                                                  "adc $0, %[cq]\n\t"
604                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
605                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
606                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
607                                                  "[cq]" (carryQ)
608                                                  : "cc");
609        return rslt.bitblock;
610}
611
612static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
613        BitBlock_int64 rslt, x, y;
614        x.bitblock = strm1;
615        y.bitblock = strm2;
616        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
617                                                  "add %[e1], %[z1]\n\t"
618                                                  "adc %[e2], %[z2]\n\t"
619                                                  "adc $0, %[cq]\n\t"
620                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
621                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
622                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
623                                                  "[cq]" (carryQ)
624                                                  : "cc");
625        return rslt.bitblock;
626}
627
628static inline BitBlock BitBlock_add_ci(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
629        BitBlock_int64 rslt, x, y;
630        x.bitblock = strm1;
631        y.bitblock = strm2;
632        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
633                                                  "adc %[e1], %[z1]\n\t"
634                                                  "adc %[e2], %[z2]\n\t"
635                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
636                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
637                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
638                                                  "[cq]" (carryQ)
639                                                  : "cc");
640        return rslt.bitblock;
641}
642
643static inline BitBlock BitBlock_add(BitBlock strm1, BitBlock strm2) {
644        BitBlock_int64 rslt, x, y;
645        x.bitblock = strm1;
646        y.bitblock = strm2;
647        __asm__ __volatile__ ("add %[e1], %[z1]\n\t"
648                                                  "adc %[e2], %[z2]\n\t"
649                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1])
650                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
651                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1])
652                                                  : "cc");
653        return rslt.bitblock;
654}
655
656
657
658static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
659        BitBlock_int64 rslt, x, y;
660        x.bitblock = strm1;
661        y.bitblock = strm2;
662        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
663                                                  "sbb %[e1], %[z1]\n\t"
664                                                  "sbb %[e2], %[z2]\n\t"
665                                                  "adc $0, %[cq]\n\t"
666                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
667                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
668                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
669                                                  "[cq]" (carryQ)
670                                                  : "cc");
671        return rslt.bitblock;
672}
673
674
675static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
676        BitBlock_int64 rslt, x, y;
677        x.bitblock = strm1;
678        y.bitblock = strm2;
679        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
680                                                  "sub %[e1], %[z1]\n\t"
681                                                  "sbb %[e2], %[z2]\n\t"
682                                                  "adc $0, %[cq]\n\t"
683                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
684                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
685                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
686                                                  "[cq]" (carryQ)
687                                                  : "cc");
688        return rslt.bitblock;
689}
690
691
692static inline BitBlock BitBlock_sub_ci(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
693        BitBlock_int64 rslt, x, y;
694        x.bitblock = strm1;
695        y.bitblock = strm2;
696        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
697                                                  "sbb %[e1], %[z1]\n\t"
698                                                  "sbb %[e2], %[z2]\n\t"
699                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
700                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
701                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
702                                                  "[cq]" (carryQ)
703                                                  : "cc");
704        return rslt.bitblock;
705}
706
707
708static inline BitBlock BitBlock_sub(BitBlock strm1, BitBlock strm2) {
709        BitBlock_int64 rslt, x, y;
710        x.bitblock = strm1;
711        y.bitblock = strm2;
712        __asm__ __volatile__ ("sub %[e1], %[z1]\n\t"
713                                                  "sbb %[e2], %[z2]\n\t"
714                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1])
715                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
716                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1])
717                                                  : "cc");
718        return rslt.bitblock;
719}
720
721
722
723static inline bool CarryTest(CarryQtype & cq, const int carryno, const int carry_count) {
724//         print_general_register_64("cq", cq);
725        uint64_t carryQ_top_N_mask = ~(0xFFFFFFFFFFFFFFFFULL >> carry_count);
726        return (cq & carryQ_top_N_mask) != 0;
727}
728
729static inline void CarryDequeueEnqueue(CarryQtype & cq, const int carryno, const int carry_count) {
730        // Given carryin queue with carry_count carries starting from carryno are 0,
731        // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
732        cq <<= carry_count;
733}
734
735static inline void CarryCombine(CarryQtype & cq, CarryQtype & local_cq, const int carryno, const int carry_count) {
736        cq |= local_cq;
737}
738
739static inline void CarryQ_Adjust(CarryQtype & cq, int total_carries) {
740        // Adjust the carryQ so that carries enqueued are readied for dequeiing.
741        cq <<= (64-total_carries);
742}
743
744
745#endif
746
747#ifdef CARRY_Q
748static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
749        return simd_andc(BitBlock_add_ci_co(markers0, charclass, cq, carryno), charclass);
750}
751
752static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
753        return simd_andc(BitBlock_add_co(markers0, charclass, cq, carryno), charclass);
754}
755
756static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
757        return simd_andc(BitBlock_add_ci(markers0, charclass, cq, carryno), charclass);
758}
759
760static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass) {
761        return simd_andc(BitBlock_add(markers0, charclass), charclass);
762}
763
764static inline BitBlock BitBlock_scanto_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
765        return simd_and(BitBlock_add_ci_co(markers0, simd_not(charclass), cq, carryno), charclass);
766}
767
768static inline BitBlock BitBlock_scanto_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
769        return simd_and(BitBlock_add_co(markers0, simd_not(charclass), cq, carryno), charclass);
770}
771
772static inline BitBlock BitBlock_scanto_ci(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask, CarryQtype & cq, const int carryno) {
773        BitBlock scanclass = simd_andc(EOF_mask, charclass);
774        return simd_andc(BitBlock_add_ci(markers0, scanclass, cq, carryno), scanclass);
775}
776
777static inline BitBlock BitBlock_scanto(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask) {
778        BitBlock scanclass = simd_andc(EOF_mask, charclass);
779        return simd_andc(BitBlock_add(markers0, scanclass), scanclass);
780}
781
782static inline BitBlock BitBlock_scantofirst(BitBlock charclass, CarryQtype & cq, const int carryno) {
783printf("Not yet implemented: scantofirst\n");
784}
785
786
787#endif
788
789#endif
790
Note: See TracBrowser for help on using the repository browser.