111 typedef typename Logic::EltW EltW;
114 explicit Routing(
const Logic& l) : l_(l) {}
119 void shift(
size_t logn,
const bitW amount[],
size_t k, T B[],
120 size_t n,
const T A[],
const T& defaultA,
121 size_t unroll)
const {
122 std::vector<T> tmp(n);
123 for (
size_t i = 0; i < n; ++i) {
139 size_t target_nrounds = ceildiv(logn, unroll);
141 while (target_nrounds > 0) {
142 size_t consumed = ceildiv(l, target_nrounds);
146 size_t shift = size_t(1) << l;
147 shift_step(consumed, &amount[l], n, k, tmp.data(), shift, defaultA);
150 check(l == 0,
"l==0");
152 for (
size_t i = 0; i < k; ++i) {
164 void unshift(
size_t logn,
const bitW amount[],
size_t n, T A[],
165 size_t k,
const T B[],
const T& defaultB,
166 size_t unroll)
const {
168 for (
size_t i = 0; i < n; ++i) {
177 size_t target_nrounds = ceildiv(logn, unroll);
178 while (target_nrounds > 0) {
179 size_t consumed = ceildiv((logn - l), target_nrounds);
182 size_t shift = size_t(1) << l;
183 unshift_step(consumed, &amount[l], n, k, A, shift, defaultB);
187 proofs::check(l == logn,
"l==logn");
190 template <
class T,
size_t LOGN>
191 void shift(
const typename Logic::template bitvec<LOGN>& amount,
size_t k,
192 T B[],
size_t n,
const T A[],
const T& defaultA,
193 size_t unroll)
const {
194 shift(LOGN, &amount[0], k, B, n, A, defaultA, unroll);
197 template <
class T,
size_t LOGN>
198 void unshift(
const typename Logic::template bitvec<LOGN>& amount,
size_t n,
199 T A[],
size_t k,
const T B[],
const T& defaultB,
200 size_t unroll)
const {
201 unshift(LOGN, &amount[0], n, A, k, B, defaultB, unroll);
206 void shift_step(
size_t logc,
const bitW amount[],
size_t n,
size_t k,
207 T tmp[],
size_t shift,
const T& defaultA)
const {
209 size_t c = size_t(1) << logc;
212 std::vector<bitW> amount_is(c);
213 std::vector<bitW> ibits(logc);
214 for (
size_t i = 0; i < c; ++i) {
215 L.bits(logc, ibits.data(), i);
216 amount_is[i] = L.eq(logc, ibits.data(), amount);
219 really_shift(c, amount_is.data(), n, k, tmp, shift, defaultA);
223 void unshift_step(
size_t logc,
const bitW amount[],
size_t n,
224 size_t k, T A[],
size_t shift,
225 const T& defaultB)
const {
227 size_t c = size_t(1) << logc;
230 std::vector<bitW> amount_is(c);
231 std::vector<bitW> ibits(logc);
232 for (
size_t i = 0; i < c; ++i) {
233 L.bits(logc, ibits.data(), i);
234 amount_is[i] = L.eq(logc, ibits.data(), amount);
237 really_unshift(c, amount_is.data(), n, k, A, shift, defaultB);
240 void really_shift(
size_t c,
const bitW amount_is[],
size_t n,
size_t k,
241 EltW tmp[],
size_t shift,
const EltW& defaultA)
const {
243 for (
size_t i = 0; i < n && i < k + shift; ++i) {
244 auto f = [&](
size_t j) {
245 if (i + j * shift < n) {
246 return L.lmul(&amount_is[j], tmp[i + j * shift]);
248 return L.lmul(&amount_is[j], defaultA);
252 tmp[i] = L.add(0, c, f);
256 void really_unshift(
size_t c,
const bitW amount_is[],
size_t n,
size_t k,
257 EltW A[],
size_t shift,
const EltW& defaultB)
const {
259 for (
size_t i = std::min(n, k + c * shift); i-- > 0;) {
260 auto f = [&](
size_t j) {
261 if (i >= j * shift) {
262 return L.lmul(&amount_is[j], A[i - j * shift]);
264 return L.lmul(&amount_is[j], defaultB);
268 A[i] = L.add(0, c, f);
272 void really_shift(
size_t c,
const bitW amount_is[],
size_t n,
size_t k,
273 bitW tmp[],
size_t shift,
const bitW& defaultA)
const {
275 for (
size_t i = 0; i < n && i < k + shift; ++i) {
277 for (
size_t j = 0; j < c; ++j) {
278 if (i + j * shift < n) {
279 r = L.lor_exclusive(&r, L.land(&amount_is[j], tmp[i + j * shift]));
281 r = L.lor_exclusive(&r, L.land(&amount_is[j], defaultA));
288 void really_unshift(
size_t c,
const bitW amount_is[],
size_t n,
size_t k,
289 bitW A[],
size_t shift,
const bitW& defaultB)
const {
291 for (
size_t i = std::min(n, k + c * shift); i-- > 0;) {
293 for (
size_t j = 0; j < c; ++j) {
294 if (i >= j * shift) {
295 r = L.lor_exclusive(&r, L.land(&amount_is[j], A[i - j * shift]));
297 r = L.lor_exclusive(&r, L.land(&amount_is[j], defaultB));
305 void really_shift(
size_t c,
const bitW amount_is[],
size_t n,
size_t k,
306 typename Logic::template bitvec<W> tmp[],
size_t shift,
307 const typename Logic::template bitvec<W>& defaultA)
const {
309 for (
size_t i = 0; i < n && i < k + shift; ++i) {
310 for (
size_t w = 0; w < W; ++w) {
312 for (
size_t j = 0; j < c; ++j) {
313 if (i + j * shift < n) {
314 r = L.lor_exclusive(&r,
315 L.land(&amount_is[j], tmp[i + j * shift][w]));
317 r = L.lor_exclusive(&r, L.land(&amount_is[j], defaultA[w]));
327 size_t c,
const bitW amount_is[],
size_t n,
size_t k,
328 typename Logic::template bitvec<W> A[],
size_t shift,
329 const typename Logic::template bitvec<W>& defaultB)
const {
331 for (
size_t i = std::min(n, k + c * shift); i-- > 0;) {
332 for (
size_t w = 0; w < W; ++w) {
334 for (
size_t j = 0; j < c; ++j) {
335 if (i >= j * shift) {
336 r = L.lor_exclusive(&r, L.land(&amount_is[j], A[i - j * shift][w]));
338 r = L.lor_exclusive(&r, L.land(&amount_is[j], defaultB[w]));
1.15.0