source: trunk/lib/carryQ.hpp @ 2207

Last change on this file since 2207 was 2207, checked in by cameron, 7 years ago

Library support for pablo.Advance(strm, n)

File size: 8.2 KB
Line 
1#ifndef CARRYQ_HPP_
2#define CARRYQ_HPP_
3
4/*=============================================================================
5  carryQ.hpp - Pablo compiler support for carry introduction.
6  Ken Herdy, Robert D. Cameron
7  April 2012
8=============================================================================*/
9
10#include <stdint.h>
11#include <iostream>
12using namespace std;
13
14#include "bitblock.hpp"
15#include "stdio.h"
16
17///////////////////////////////////////////////////////////////////////////////
18//
19// Carry method variants.
20//
21// BitBlock_op_ci_co()  - standard block non while loop statement and in final block if ignore the carry out
22// BitBlock_op_co()     - standard block while loop and in final block while loop if ignore carry out
23// BitBlock_op_ci()             - final block non while loop statement
24// BitBlock_op()                - final while loop statement
25//
26// BitBlock_op_ci(), BitBlock_op() methods not implemented to reduce the total number of
27// methods and Pablo compiler complexity.
28//
29///////////////////////////////////////////////////////////////////////////////
30
31#define interpose32(x,y,pos) interpose32_<pos>(x,y)     
32template<uint32_t n>
33IDISA_ALWAYS_INLINE BitBlock interpose32_(BitBlock s, BitBlock s32) {
34        return simd_or(simd<32>::slli<n>(s), simd<32>::srli<32-n>(s32));
35}
36
37template<uint32_t n>
38IDISA_ALWAYS_INLINE BitBlock interpose64_(BitBlock s, BitBlock s64) {
39        return simd_or(simd<64>::slli<n>(s), simd<64>::srli<64-n>(s64));
40}
41
42// Abstract Base Class
43class ICarryQueue {
44
45        IDISA_ALWAYS_INLINE BitBlock BitBlock_advance_ci_co(BitBlock strm, BitBlock carryin, uint16_t carryno);
46        IDISA_ALWAYS_INLINE BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, BitBlock carryin, const uint16_t carryno);
47        IDISA_ALWAYS_INLINE BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, BitBlock carryin, uint16_t carryno);
48
49        IDISA_ALWAYS_INLINE BitBlock BitBlock_scantofirst(BitBlock charclass, BitBlock carryin, uint16_t carryno);
50        IDISA_ALWAYS_INLINE BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, BitBlock carryin, uint16_t carryno);
51        IDISA_ALWAYS_INLINE BitBlock BitBlock_advance32_ci_co(BitBlock strm, uint32_t pending_in, uint32_t & pending_out);
52        template <int n> IDISA_ALWAYS_INLINE BitBlock BitBlock_advance_n_(BitBlock strm, BitBlock pending_in, uint16_t pendingno);
53
54        IDISA_ALWAYS_INLINE BitBlock BitBlock_advance_then_scanthru(BitBlock markers0, BitBlock charclass, BitBlock carryin, uint16_t carryno);
55        IDISA_ALWAYS_INLINE BitBlock BitBlock_span_upto(BitBlock starts, BitBlock follows, BitBlock carryin, uint16_t carryno);
56        IDISA_ALWAYS_INLINE BitBlock BitBlock_inclusive_span(BitBlock starts, BitBlock ends, BitBlock carryin, uint16_t carryno);
57        IDISA_ALWAYS_INLINE BitBlock BitBlock_exclusive_span(BitBlock starts, BitBlock ends, BitBlock carryin, uint16_t carryno);
58
59        IDISA_ALWAYS_INLINE bool CarryTest(uint16_t carryno, uint16_t carry_count);
60        IDISA_ALWAYS_INLINE void CarryDequeueEnqueue(uint16_t carryno, uint16_t carry_count);
61        IDISA_ALWAYS_INLINE void CarryQ_Adjust(uint16_t carry_count);
62        IDISA_ALWAYS_INLINE void CarryCombine(ICarryQueue carryqueue, uint16_t carryno, uint16_t carry_count);
63
64        IDISA_ALWAYS_INLINE BitBlock get_carry_in(uint16_t carryno) const ;
65protected:
66        ICarryQueue(){};
67        ~ICarryQueue(){};
68        // helpers
69        IDISA_ALWAYS_INLINE BitBlock carry_flip(BitBlock carry) const ;
70        IDISA_ALWAYS_INLINE bool test_carry(BitBlock carry) const ;
71        IDISA_ALWAYS_INLINE BitBlock carry_or(BitBlock carry1, BitBlock carry2) const ;
72};
73
74#include <string.h>
75
76// Array of BitBlock implementation.
77template <uint16_t CarryCount, uint16_t AdvanceNCount>
78class CarryArray: public ICarryQueue{
79
80public:
81
82    #define Carry0 simd<BLOCK_SIZE>::constant<0>()
83    #define Carry1 simd<BLOCK_SIZE>::constant<1>()
84 
85        BitBlock cq[CarryCount];
86        BitBlock pending64[AdvanceNCount];
87        CarryArray()
88        {
89            memset (cq, 0, sizeof(BitBlock) * CarryCount);// size_t num )
90            memset(pending64, 0, sizeof(BitBlock) * AdvanceNCount);
91        }
92        ~CarryArray() {}
93
94        IDISA_ALWAYS_INLINE BitBlock BitBlock_advance_ci_co(BitBlock strm, BitBlock carryin, uint16_t carryno)
95        {
96                BitBlock rslt;
97                advance_with_carry(strm, carryin, cq[carryno], rslt);
98                return rslt;
99        }
100
101        IDISA_ALWAYS_INLINE BitBlock BitBlock_add_ci_co(BitBlock strm1, BitBlock strm2, BitBlock carryin, const uint16_t carryno)
102        {
103                BitBlock sum;
104                adc(strm1, strm2, carryin, cq[carryno], sum);
105                return sum;
106        }
107
108        IDISA_ALWAYS_INLINE BitBlock BitBlock_sub_ci_co(BitBlock strm1, BitBlock strm2, BitBlock carryin, uint16_t carryno)
109        {
110                BitBlock diff;
111                sbb(strm1, strm2, carryin, cq[carryno], diff);
112                return diff;
113        }
114
115        IDISA_ALWAYS_INLINE BitBlock BitBlock_scantofirst(BitBlock charclass, BitBlock carryin, uint16_t carryno)
116        {
117                BitBlock marker;
118                BitBlock c = carry_flip(carryin);
119                adc(simd<BLOCK_SIZE>::constant<0>(), simd_not(charclass), c, cq[carryno], marker);
120                cq[carryno] = carry_flip(cq[carryno]);
121                return simd_and(marker, charclass);
122        }
123
124        IDISA_ALWAYS_INLINE BitBlock BitBlock_scanthru_ci_co(BitBlock markers0, BitBlock charclass, BitBlock carryin, uint16_t carryno)
125        {
126                BitBlock markers1;
127                adc(markers0, charclass, carryin, cq[carryno], markers1);
128                return simd_andc(markers1, charclass);
129        }
130
131        IDISA_ALWAYS_INLINE BitBlock BitBlock_advance_then_scanthru(BitBlock markers0, BitBlock charclass, BitBlock carryin, uint16_t carryno)
132        {
133                BitBlock markers1;
134                //assert(!bitblock::any(simd_and(markers0, charclass)));
135                adc(markers0, simd_or(charclass, markers0), carryin, cq[carryno], markers1);
136                return simd_andc(markers1, charclass);
137        }
138
139        IDISA_ALWAYS_INLINE BitBlock BitBlock_span_upto(BitBlock starts, BitBlock follows, BitBlock carryin, uint16_t carryno)
140        {
141                BitBlock span;
142                sbb(follows, starts, carryin, cq[carryno], span);
143                return span;
144        }
145
146        IDISA_ALWAYS_INLINE BitBlock BitBlock_inclusive_span(BitBlock starts, BitBlock ends, BitBlock carryin, uint16_t carryno)
147        {
148                BitBlock span;
149                sbb(ends, starts, carryin, cq[carryno], span);
150                return simd_or(span, ends);
151        }
152
153        IDISA_ALWAYS_INLINE BitBlock BitBlock_exclusive_span(BitBlock starts, BitBlock ends, BitBlock carryin, uint16_t carryno)
154        {
155                BitBlock span;
156                sbb(ends, starts, carryin, cq[carryno], span);
157                return simd_andc(span, starts);
158        }
159
160
161        IDISA_ALWAYS_INLINE BitBlock BitBlock_advance32_ci_co(BitBlock strm, uint32_t pending_in, uint32_t & pending_out)
162        {
163                pending_out = (uint32_t) mvmd<32>::extract< (sizeof(BitBlock)/sizeof(pending_out))-1 >(strm);
164                return simd_or(simd<BLOCK_SIZE>::slli<32>(strm), mvmd<BLOCK_SIZE>::fill((uint64_t)pending_in));
165        }
166
167        template <int n> IDISA_ALWAYS_INLINE BitBlock BitBlock_advance_n_(BitBlock strm, BitBlock pending_in, uint16_t pendingno)
168        {
169                BitBlock half_block_shifted = esimd<BLOCK_SIZE/2>::mergel(strm, pending_in);
170                pending64[pendingno] = bitblock::srli<BLOCK_SIZE/2>(strm);
171                BitBlock result = simd_or(simd<BLOCK_SIZE/2>::srli<(BLOCK_SIZE/2)-n>(half_block_shifted),
172                               simd<BLOCK_SIZE/2>::slli<n>(strm));
173                return result;
174        }
175
176        IDISA_ALWAYS_INLINE bool CarryTest(uint16_t carryno, uint16_t carry_count)
177
178
179        {
180                  BitBlock c1 = cq[carryno];
181                  int ubound = carryno + carry_count;
182                  for (int i = carryno + 1; i < ubound ; i++) {
183                        c1 = carry_or(c1, cq[i]);
184                  }
185                  return test_carry(c1);
186        }
187
188        IDISA_ALWAYS_INLINE void CarryDequeueEnqueue(uint16_t carryno, uint16_t carry_count)
189        {
190                return;
191        }
192
193        IDISA_ALWAYS_INLINE void CarryQ_Adjust(uint16_t carry_count)
194        {
195                return;
196        }
197
198        IDISA_ALWAYS_INLINE void CarryCombine(ICarryQueue * carryqueue, uint16_t carryno, uint16_t carry_count)
199        {
200                  BitBlock * local_cq = ((CarryArray *)carryqueue)->cq;
201                  for (int i = 0; i < carry_count; i++) {
202                    cq[carryno+i] = carry_or(cq[carryno+i], local_cq[i]);
203                  }
204        }
205
206        IDISA_ALWAYS_INLINE BitBlock get_carry_in(uint16_t carryno) const 
207        {
208                return carry2bitblock(cq[carryno]);
209        }
210
211private:
212        // helpers
213        IDISA_ALWAYS_INLINE BitBlock carry_flip(BitBlock carry) const
214        {
215                return simd_xor(carry, Carry1);
216        }
217
218        IDISA_ALWAYS_INLINE bool test_carry(BitBlock carry) const
219        {
220                return bitblock::any(carry);
221        }
222
223        IDISA_ALWAYS_INLINE BitBlock carry_or(BitBlock carry1, BitBlock carry2) const
224        {
225                return simd_or(carry1, carry2);
226        }
227       
228#undef Carry0
229#undef Carry1
230
231};
232
233// Single bit per carry implementation.
234template <class BitBlock, uint16_t CarryCount>
235class CarryRegister: public ICarryQueue {
236
237public:
238        CarryRegister() {}
239        ~CarryRegister() {}
240
241private:
242        BitBlock cq;
243};
244
245#endif // CARRYQ_HPP_
Note: See TracBrowser for help on using the repository browser.