source: trunk/lib/carryQ.hpp @ 2128

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

scantofirst: use separated carry-in/carry-out implementation of adc

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