source: trunk/lib/carryQ.h @ 784

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

Add _ci_co and _co modes

File size: 8.2 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
8#ifndef SIMD_CARRY_Q
9#include "block_carry.h"
10
11
12#define CarryQtype CarryType *
13
14#define CarryDeclare(name, count)\
15CarryType name[count];\
16
17#define CarryInit(name, count)\
18for (int j=0; j < count; j++) name[j] = Carry0
19
20static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype cq, int carryno) {
21 BitBlock rslt;
22 advance_with_carry(strm, cq[carryno], rslt);
23 return rslt;
24}
25
26static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype cq, int carryno) {
27 BitBlock rslt;
28 cq[carryno] = Carry0;
29 advance_with_carry(strm, cq[carryno], rslt);
30 return rslt;
31}
32
33static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, int carryno) {
34 BitBlock sum;
35 adc128(strm1, strm2, cq[carryno], sum);
36 return sum;
37}
38
39static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, int carryno) {
40 BitBlock sum;
41 cq[carryno] = Carry0;
42 adc128(strm1, strm2, cq[carryno], sum);
43 return sum;
44}
45
46static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, int carryno) {
47 BitBlock diff;
48 sbb128(strm1, strm2, cq[carryno], diff);
49 return diff;
50}
51
52static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype cq, int carryno) {
53 BitBlock diff;
54 cq[carryno] = Carry0;
55 sbb128(strm1, strm2, cq[carryno], diff);
56 return diff;
57}
58
59static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, int carryno) {
60 BitBlock markers1;
61 adc128(markers0, charclass, cq[carryno], markers1);
62 return simd_andc(markers1, charclass);
63}
64
65static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype cq, int carryno) {
66 BitBlock markers1;
67 cq[carryno] = Carry0;
68 adc128(markers0, charclass, cq[carryno], markers1);
69 return simd_andc(markers1, charclass);
70}
71
72static inline bool CarryTest(CarryQtype cq, int carryno, int carry_count) {
73  CarryType c1 = cq[carryno];
74  int i;
75  for (i = carryno + 1; i < carryno + carry_count; i++) {
76    c1 = carry_or(c1, cq[i]);
77  }
78  return test_carry(c1);
79}
80
81static inline void CarryDequeueEnqueue(CarryQtype cq, int carryno, int carry_count) {
82  // Given carryin queue with carry_count carries starting from carryno are 0,
83  // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
84  // Nothing to do when the queues are the same!
85  return;
86}
87
88static inline void CarryQ_Adjust(CarryQtype cq, int carry_count) {
89  // Adjust the carryQ so that carries enqueued are readied for dequeiing.
90  // Nothing to do with indexed queues.
91  return;
92}
93
94static inline void CarryCombine(CarryQtype cq, CarryQtype local_cq, int carryno, int carry_count) {
95  int i;
96  for (i = 0; i < carry_count; i++) {
97    cq[carryno+i] = carry_or(cq[carryno+i], local_cq[i]);
98  }
99}
100#endif
101#ifdef SIMD_CARRY_Q
102
103#define CarryQtype SIMD_type
104
105#define CarryDeclare(name, count)\
106  CarryQtype name
107
108#define CarryInit(name, count)\
109  name = simd_const_1(0)
110
111SIMD_type carryQ_ci_mask = sisd_from_int(1);
112SIMD_type carryQ_co_mask = sisd_slli(carryQ_ci_mask, 127);
113
114#define carryQ_adc128_ci_co(x, y, carryQ,  sum) \
115do{ \
116  SIMD_type gen = simd_and(x, y); \
117  SIMD_type prop = simd_or(x, y); \
118  SIMD_type partial = simd_add_64(simd_add_64(x, y), simd_and(carryQ, carryQ_ci_mask)); \
119  carryQ = simd_srli_64(carryQ, 1); \
120  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64); \
121  sum = simd_add_64(c1, partial); \
122  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_andc(prop, sum)), carryQ_co_mask)); \
123} while(0)
124
125#define carryQ_adc128_co(x, y, carryQ,  sum) \
126do{ \
127  SIMD_type gen = simd_and(x, y); \
128  SIMD_type prop = simd_or(x, y); \
129  SIMD_type partial = simd_add_64(x, y); \
130  carryQ = simd_srli_64(carryQ, 1); \
131  SIMD_type c1 = sisd_slli(simd_srli_64(simd_or(gen, simd_andc(prop, partial)), 63), 64); \
132  sum = simd_add_64(c1, partial); \
133  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_andc(prop, sum)), carryQ_co_mask)); \
134} while(0)
135
136#define carryQ_sbb128_ci_co(x, y, carryQ, difference) \
137do {\
138  SIMD_type gen = simd_andc(y, x); \
139  SIMD_type prop = simd_not(simd_xor(x, y)); \
140  SIMD_type partial = simd_sub_64(simd_sub_64(x, y), simd_and(carryQ, carryQ_ci_mask)); \
141  carryQ = simd_srli_64(carryQ, 1); \
142  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64); \
143  difference = simd_sub_64(partial, b1); \
144  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_and(prop, difference)), carryQ_co_mask)); \
145}while(0)
146
147#define carryQ_sbb128_co(x, y, carryQ, difference) \
148do {\
149  SIMD_type gen = simd_andc(y, x); \
150  SIMD_type prop = simd_not(simd_xor(x, y)); \
151  SIMD_type partial = simd_sub_64(x, y); \
152  carryQ = simd_srli_64(carryQ, 1); \
153  SIMD_type b1 = sisd_slli(simd_srli_64(simd_or(gen, simd_and(prop, partial)), 63), 64); \
154  difference = simd_sub_64(partial, b1); \
155  carryQ = simd_or(carryQ, simd_and(simd_or(gen, simd_and(prop, difference)), carryQ_co_mask)); \
156}while(0)
157
158#define carryQ_advance_with_carry_ci_co(cursor, carryQ, rslt)\
159do {\
160  SIMD_type carry_out = simd_and(cursor, carryQ_co_mask);\
161  SIMD_type carry_in = simd_and(carryQ, carryQ_ci_mask);\
162  carryQ = simd_or(simd_srli_64(carryQ, 1), carry_out); \
163  SIMD_type shift_out = simd_srli_64(cursor, 63);\
164  SIMD_type low_bits = simd_mergel_64(shift_out, carry_in);\
165  rslt = simd_or(simd_add_64(cursor, cursor), low_bits);\
166} while(0)
167
168#define carryQ_advance_with_carry_co(cursor, carryQ, rslt)\
169do {\
170  SIMD_type carry_out = simd_and(cursor, carryQ_co_mask);\
171  carryQ = simd_or(simd_srli_64(carryQ, 1), carry_out); \
172  SIMD_type shift_out = simd_srli_64(cursor, 63);\
173  SIMD_type low_bits = simd_mergel_64(shift_out, simd_const_1(0));\
174  rslt = simd_or(simd_add_64(cursor, cursor), low_bits);\
175} while(0)
176
177static inline BitBlock BitBlock_advance_ci_co(BitBlock strm, CarryQtype & cq, int carryno) {
178 BitBlock rslt;
179 carryQ_advance_with_carry_ci_co(strm, cq, rslt);
180 return rslt;
181}
182
183static inline BitBlock BitBlock_advance_co(BitBlock strm, CarryQtype & cq, int carryno) {
184 BitBlock rslt;
185 carryQ_advance_with_carry_co(strm, cq, rslt);
186 return rslt;
187}
188
189static inline BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
190 BitBlock sum;
191 carryQ_adc128_ci_co(strm1, strm2, cq, sum);
192 return sum;
193}
194
195static inline BitBlock BitBlock_add_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
196 BitBlock sum;
197 carryQ_adc128_co(strm1, strm2, cq, sum);
198 return sum;
199}
200
201static inline BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
202 BitBlock diff;
203 carryQ_sbb128_ci_co(strm1, strm2, cq, diff);
204 return diff;
205}
206
207static inline BitBlock BitBlock_sub_co(BitBlock strm1, BitBlock strm2, CarryQtype & cq, int carryno) {
208 BitBlock diff;
209 carryQ_sbb128_co(strm1, strm2, cq, diff);
210 return diff;
211}
212
213static inline BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, int carryno) {
214 BitBlock markers1;
215 carryQ_adc128_ci_co(markers0, charclass, cq, markers1);
216 return simd_andc(markers1, charclass);
217}
218
219static inline BitBlock BitBlock_scanthru_co(BitBlock markers0, BitBlock charclass, CarryQtype & cq, int carryno) {
220 BitBlock markers1;
221 carryQ_adc128_co(markers0, charclass, cq, markers1);
222 return simd_andc(markers1, charclass);
223}
224
225typedef union {SIMD_type bitblock; uint64_t int64[2];} BitBlock_int64;
226
227static inline bool CarryTest(CarryQtype cq, int carryno, int carry_count) {
228  BitBlock_int64 t;
229  t.bitblock = cq;
230  uint64_t carryQ_top_N_mask = ((1 << carry_count) -1);
231  return t.int64[0] & carryQ_top_N_mask;
232}
233
234static inline void CarryDequeueEnqueue(CarryQtype & cq, int carryno, int carry_count) {
235  // Given carryin queue with carry_count carries starting from carryno are 0,
236  // ensure that the carryout queue has carry_count carries starting from carryno set to 0.
237  cq = sisd_srli(cq, carry_count);
238}
239
240static inline void CarryCombine(CarryQtype & cq, CarryQtype local_cq, int carryno, int carry_count) {
241  cq = simd_or(cq, local_cq);
242}
243
244static inline void CarryQ_Adjust(CarryQtype & cq, int carry_count) {
245  // Adjust the carryQ so that carries enqueued are readied for dequeiing.
246  cq = sisd_srli(cq, (128-carry_count));
247}
248
249
250#endif
Note: See TracBrowser for help on using the repository browser.