source: trunk/lib/carryQ.h @ 1075

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

scantofirst implementation

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