Memcmp<Logic>

Header: circuits/logic/memcmp.h

In-circuit equivalent of memcmp for arrays of bytes, where each byte is a Logic::v8 (8 single-bit wires).

template <class Logic>
class Memcmp {
 public:
  using BitW = typename Logic::BitW;
  using v8   = typename Logic::v8;
 
  explicit Memcmp(const Logic& l);
 
  BitW lt (size_t n, const v8 A[/*n*/], const v8 B[/*n*/]) const;  // A < B
  BitW leq(size_t n, const v8 A[/*n*/], const v8 B[/*n*/]) const;  // A <= B
};

Semantics

A and B are arrays of n bytes interpreted as big-endian multi-byte integers: A[0] is the most significant byte. The comparison is therefore lexicographic / unsigned-integer style.

Internally, Memcmp flattens the n bytes into an 8n-bit little-endian array (reversing byte order and leaving the intra-byte bit order intact) and delegates to Logic::lt / Logic::leq. All the heavy lifting lives in Logic; this class exists only to marshal the bits into the right order.

Complexity

Linear in n in both wires and terms — Memcmp::lt forwards to Logic::lt(8n, …), which runs a balanced-tree recursion of depth O(log n).

Example

Memcmp<Logic> M(L);
typename Logic::v8 A[32], B[32];
// … populate A and B …
auto A_lt_B = M.lt(32, A, B);
L.assert1(A_lt_B);        // prove A < B