source: trunk/lib/carryQ.h @ 931

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

Syntax error

File size: 25.4 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
339static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
340        return simd_andc(BitBlock_add_ci_co(markers0, charclass, cq, carryno), charclass);
341}
342
343static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
344        return simd_andc(BitBlock_add_co(markers0, charclass, cq, carryno), charclass);
345}
346
347static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
348        return simd_andc(BitBlock_add_ci(markers0, charclass, cq, carryno), charclass);
349}
350
351static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass) {
352        return simd_andc(BitBlock_add(markers0, charclass), charclass);
353}
354
355
356typedef union {SIMD_type bitblock; uint64_t int64[2];} BitBlock_int64;
357
358static inline bool CarryTest(CarryQtype & cq, const int carryno, const int carry_count) {
359  BitBlock_int64 t;
360  t.bitblock = cq;
361  uint64_t carryQ_top_N_mask = ((1 << carry_count) -1);
362  return t.int64[0] & carryQ_top_N_mask;
363}
364
365static inline void CarryDequeueEnqueue(CarryQtype & cq, const int carryno, const int carry_count) {
366  // Given carryin queue with carry_count carries starting from carryno are 0,
367  // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
368  cq = sisd_srli(cq, carry_count);
369}
370
371static inline void CarryCombine(CarryQtype & cq, CarryQtype & local_cq, const int carryno, const int carry_count) {
372  cq = simd_or(cq, local_cq);
373}
374
375static inline void CarryQ_Adjust(CarryQtype & cq, const int carry_count) {
376  // Adjust the carryQ so that carries enqueued are readied for dequeiing.
377  cq = sisd_srli(cq, (128-carry_count));
378}
379
380
381#endif
382
383#ifdef ADC64_CARRY_Q
384
385//
386// CarryQueue implementation using 64-bit integer queues.
387// A single 64-bit integer holds both the input and output
388// carries, with bits moving right-to-left.   Thus the
389// high bit in the queue is always the next carry to be
390// dequeued; a newly enqueued carry is always inserted as
391// the low bit.
392//
393// The two typical operations for dequeueing and enqueueing
394// carryies from/to a CarryQueue cq are the following.
395// 1.  Dequeueing:  add(cq, cq)
396//     The high carry bit is dequeued and sets the processor
397//     carry flag to be used as a carry-in variable in the
398//     following bitblock operation.   This also shifts cq
399//     right one position, making room for enqueuing a new carry.
400// 2.  Enqueueing:  adc($0, cq)
401//     The carry out value of an operation as recorded in the
402//     processor carry flag is enqueued by adding it in to the
403//     low bit position of cq (this bit will have been cleared
404//     by the dequeue operation.
405
406#define CarryDeclare(name, count)\
407CarryQtype name
408
409#define CarryInit(name, count)\
410name = 0
411
412typedef union {SIMD_type bitblock; uint64_t int64[2];} BitBlock_int64;
413
414
415static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype & carryQ, const int carryno) {
416        BitBlock_int64 x, z;
417        x.bitblock = strm;
418        __asm__  __volatile__ ("add %[cq], %[cq]\n\t"
419                                                   "adc %[z1], %[z1]\n\t"
420                                                   "adc %[z2], %[z2]\n\t"
421                                                   "adc $0, %[cq]\n\t"
422                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1]), [cq] "=r" (carryQ)
423                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
424                                                   "[cq]" (carryQ)
425                                                   : "cc");
426        return z.bitblock;
427}
428
429static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype & carryQ, const int carryno) {
430        BitBlock_int64 x, z;
431        x.bitblock = strm;
432        __asm__  __volatile__ ("add %[cq], %[cq]\n\t"
433                                                   "add %[z1], %[z1]\n\t"
434                                                   "adc %[z2], %[z2]\n\t"
435                                                   "adc $0, %[cq]\n\t"
436                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1]), [cq] "=r" (carryQ)
437                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
438                                                   "[cq]" (carryQ)
439                                                   : "cc");
440        return z.bitblock;
441}
442
443static inline BitBlock BitBlock_advance_ci(BitBlock strm, CarryQtype & carryQ, const int carryno) {
444        BitBlock_int64 x, z;
445        x.bitblock = strm;
446        __asm__  __volatile__ ("add %[cq], %[cq]\n\t"
447                                                   "adc %[z1], %[z1]\n\t"
448                                                   "adc %[z2], %[z2]\n\t"
449                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1]), [cq] "=r" (carryQ)
450                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
451                                                   "[cq]" (carryQ)
452                                                   : "cc");
453        return z.bitblock;
454}
455
456static inline BitBlock BitBlock_advance(BitBlock strm) {
457        BitBlock_int64 x, z;
458        x.bitblock = strm;
459        __asm__  __volatile__ ("add %[z1], %[z1]\n\t"
460                                                   "adc %[z2], %[z2]\n\t"
461                                                   : [z1] "=r" (z.int64[0]), [z2] "=r" (z.int64[1])
462                                                   : "[z1]" (x.int64[0]), "[z2]" (x.int64[1])
463                                                   : "cc");
464        return z.bitblock;
465}
466
467
468static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
469        BitBlock_int64 rslt, x, y;
470        x.bitblock = strm1;
471        y.bitblock = strm2;
472        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
473                                                  "adc %[e1], %[z1]\n\t"
474                                                  "adc %[e2], %[z2]\n\t"
475                                                  "adc $0, %[cq]\n\t"
476                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
477                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
478                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
479                                                  "[cq]" (carryQ)
480                                                  : "cc");
481        return rslt.bitblock;
482}
483
484static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
485        BitBlock_int64 rslt, x, y;
486        x.bitblock = strm1;
487        y.bitblock = strm2;
488        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
489                                                  "add %[e1], %[z1]\n\t"
490                                                  "adc %[e2], %[z2]\n\t"
491                                                  "adc $0, %[cq]\n\t"
492                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
493                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
494                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
495                                                  "[cq]" (carryQ)
496                                                  : "cc");
497        return rslt.bitblock;
498}
499
500static inline BitBlock BitBlock_add_ci(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
501        BitBlock_int64 rslt, x, y;
502        x.bitblock = strm1;
503        y.bitblock = strm2;
504        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
505                                                  "adc %[e1], %[z1]\n\t"
506                                                  "adc %[e2], %[z2]\n\t"
507                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
508                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
509                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
510                                                  "[cq]" (carryQ)
511                                                  : "cc");
512        return rslt.bitblock;
513}
514
515static inline BitBlock BitBlock_add(BitBlock strm1, BitBlock strm2) {
516        BitBlock_int64 rslt, x, y;
517        x.bitblock = strm1;
518        y.bitblock = strm2;
519        __asm__ __volatile__ ("add %[e1], %[z1]\n\t"
520                                                  "adc %[e2], %[z2]\n\t"
521                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1])
522                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
523                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1])
524                                                  : "cc");
525        return rslt.bitblock;
526}
527
528
529
530static inline BitBlock BitBlock_sub_ci_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                                                  "sbb %[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_co(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                                                  "sub %[e1], %[z1]\n\t"
553                                                  "sbb %[e2], %[z2]\n\t"
554                                                  "adc $0, %[cq]\n\t"
555                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
556                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
557                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
558                                                  "[cq]" (carryQ)
559                                                  : "cc");
560        return rslt.bitblock;
561}
562
563
564static inline BitBlock BitBlock_sub_ci(BitBlock strm1, BitBlock strm2, CarryQtype & carryQ, const int carryno) {
565        BitBlock_int64 rslt, x, y;
566        x.bitblock = strm1;
567        y.bitblock = strm2;
568        __asm__ __volatile__ ("add %[cq], %[cq]\n\t"
569                                                  "sbb %[e1], %[z1]\n\t"
570                                                  "sbb %[e2], %[z2]\n\t"
571                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1]), [cq] "=r" (carryQ)
572                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
573                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1]),
574                                                  "[cq]" (carryQ)
575                                                  : "cc");
576        return rslt.bitblock;
577}
578
579
580static inline BitBlock BitBlock_sub(BitBlock strm1, BitBlock strm2) {
581        BitBlock_int64 rslt, x, y;
582        x.bitblock = strm1;
583        y.bitblock = strm2;
584        __asm__ __volatile__ ("sub %[e1], %[z1]\n\t"
585                                                  "sbb %[e2], %[z2]\n\t"
586                                                  : [z1] "=r" (rslt.int64[0]), [z2] "=r" (rslt.int64[1])
587                                                  : "[z1]" (x.int64[0]), "[z2]" (x.int64[1]),
588                                                  [e1] "r" (y.int64[0]), [e2] "r" (y.int64[1])
589                                                  : "cc");
590        return rslt.bitblock;
591}
592
593
594
595static inline bool CarryTest(CarryQtype & cq, const int carryno, const int carry_count) {
596//         print_general_register_64("cq", cq);
597        uint64_t carryQ_top_N_mask = ~(0xFFFFFFFFFFFFFFFFULL >> carry_count);
598        return (cq & carryQ_top_N_mask) != 0;
599}
600
601static inline void CarryDequeueEnqueue(CarryQtype & cq, const int carryno, const int carry_count) {
602        // Given carryin queue with carry_count carries starting from carryno are 0,
603        // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
604        cq <<= carry_count;
605}
606
607static inline void CarryCombine(CarryQtype & cq, CarryQtype & local_cq, const int carryno, const int carry_count) {
608        cq |= local_cq;
609}
610
611static inline void CarryQ_Adjust(CarryQtype & cq, int total_carries) {
612        // Adjust the carryQ so that carries enqueued are readied for dequeiing.
613        cq <<= (64-total_carries);
614}
615
616
617#endif
618
619#ifdef CARRY_Q
620static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
621        return simd_andc(BitBlock_add_ci_co(markers0, charclass, cq, carryno), charclass);
622}
623
624static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
625        return simd_andc(BitBlock_add_co(markers0, charclass, cq, carryno), charclass);
626}
627
628static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
629        return simd_andc(BitBlock_add_ci(markers0, charclass, cq, carryno), charclass);
630}
631
632static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass) {
633        return simd_andc(BitBlock_add(markers0, charclass), charclass);
634}
635
636static inline BitBlock BitBlock_scanto_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
637        return simd_and(BitBlock_add_ci_co(markers0, simd_not(charclass), cq, carryno), charclass);
638}
639
640static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, const int carryno) {
641        return simd_and(BitBlock_add_co(markers0, simd_not(charclass), cq, carryno), charclass);
642}
643
644static inline BitBlock BitBlock_scanthru_ci(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask, CarryQtype & cq, const int carryno) {
645        return simd_and(BitBlock_add_ci(markers0, simd_and(simd_not(charclass), EOF_mask), cq, carryno), charclass);
646}
647
648static inline BitBlock BitBlock_scanthru(BitBlock markers0, BitBlock charclass, BitBlock EOF_mask) {
649        return simd_and(BitBlock_add(markers0, simd_and(simd_not(charclass), EOF_mask)), charclass);
650}
651
652
653#endif
654
655#endif
656
Note: See TracBrowser for help on using the repository browser.