Routing<Logic>

Header: circuits/logic/routing.h

Routing builds circuits that shift an array by a variable number of positions, where the shift amount is itself a bit-vector on wires. Two directions are supported:

• shift — computes B[i] = A[i + amount];
• unshift — the “inverse” — writes A[i + amount] = B[i].

A and B may have different lengths; elements out of range are filled with a caller-supplied default.

Template parameter

template <class Logic>
class Routing {
 public:
  typedef typename Logic::BitW bitW;
  typedef typename Logic::EltW EltW;
 
  explicit Routing(const Logic& l);
};

Works with both backends. The element type T is a per-method template parameter, so the same Routing instance can route EltW, bitW, or bitvec<W> arrays.

shift

template <class T>
void shift(size_t logn, const bitW amount[/*logn*/],
           size_t k, T B[/*k*/],
           size_t n, const T A[/*n*/],
           const T& defaultA,
           size_t unroll) const;
 
template <class T, size_t LOGN>
void shift(const typename Logic::template bitvec<LOGN>& amount,
           size_t k, T B[/*k*/],
           size_t n, const T A[/*n*/],
           const T& defaultA,
           size_t unroll) const;

• amount — little-endian logn-bit wire representation of the shift.
• A, n — source array and its length.
• B, k — destination array and its length.
• defaultA — value written to B[i] whenever A[i + amount] would be out of range.
• unroll — number of amount bits consumed per round (see below).

After the call, B[i] == A[i + amount] with out-of-range reads replaced by defaultA.

unshift

template <class T>
void unshift(size_t logn, const bitW amount[/*logn*/],
             size_t n, T A[/*n*/],
             size_t k, const T B[/*k*/],
             const T& defaultB,
             size_t unroll) const;

Sets A[i + amount] = B[i] for 0 ≤ i < k. Positions in A not reached by any i are filled with defaultB.

Supported element types

The implementation specializes on the element type:

Any other T must be converted to one of those first.

The unroll parameter

unroll is the number of bits of amount consumed per barrel-shifter round. It trades circuit depth for wire count:

• unroll = 1 — one bit per round, deepest and narrowest circuit.
• Larger unroll — fewer, wider rounds.

The implementation evenly distributes bits across ⌈logn / unroll⌉ rounds rather than using unroll flat, so e.g. logn = 11, unroll = 7 gives two rounds of 6 + 5 bits instead of 7 + 4.

Asymptotic shape

Iterating “backward from logn” (the default) yields an O(n log k) circuit when only the first k outputs are needed, rather than O(n log n).

Worked example

Barrel-shift a 32-bit value by a 5-bit amount, producing a 32-bit result, with one bit consumed per round:

using BitW = typename Logic::BitW;
 
Routing<Logic> R(L);
typename Logic::v32 a = /* source */;
typename Logic::v32 b;                 // destination (uninitialized)
typename Logic::template bitvec<5> amt = /* shift amount */;
 
R.shift(amt, /*k=*/32, b.data(),
        /*n=*/32, a.data(),
        /*defaultA=*/L.bit(0),
        /*unroll=*/1);