source: trunk/lib/carryQ.h @ 1077

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

CarryQ changes for AVX/BitBlock_scantofirst

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