source: trunk/lib/carryQ.h @ 1570

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

Fix declaration of BitBlock_scanto_ci

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