source: trunk/lib/carryQ.h @ 932

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

Syntax error

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