Polynomial Degree

Binary polynomials have a binary degree.

Every valid polynomial has a degree. The degree \(d\) of binary polynomial \(p\) is the power of two which holds \(p\in\left[2^d, 2^{d+1}\right)\). Note the inclusive-exclusive boundaries. For example, the degree equivalence for polynomial \(107_{16}\) \[ 2^8\leq107_{16}<2^9\equiv256\leq107_{16}<512 \] holds as true and hence has a degree of \(d=8\).

How does that translate logically? The logical expression poly_deg_ holds for all polynomials Poly of degree Deg; see predicate below. Any given polynomial cannot by definition have more than one degree; it cannot simultaneously span two \(\left[2^d, 2^{d+1}\right)\) ranges.

poly_deg_(Poly, Deg) :-
    Low is 1 << Deg,
    Low =< Poly,
    High is Low << 1,
    Poly < High.

The predicate’s term ordering matters at least for performance. It computes the lower degree boundary by shifting and then computes the higher boundary by shifting the lower boundary by one—doubling it.

A tabled implementation for poly_deg unifies Poly and Deg for degrees 8, 16, 24, 32 and 64, as follows.

:- table poly_deg/2.

poly_deg(Poly, Deg) :-
    deg(Deg),
    poly_deg_(Poly, Deg),
    !.

deg(8).
deg(16).
deg(24).
deg(32).
deg(64).

Bit Reversal

CRC calculation requires a ‘bit reversal’ operation over a given span of bits, or math \(A=({}_{0}A, \ldots, {}_{j-1}A)\) for integer \(A\) of \(j\) bits. The reverse bits equal the mirror image of the original; integer \(1\) reversed in 16 bits becomes \(8000_{16}\) for instance.

In Prolog by accumulation:

rbit(Shift, Int, Reverse) :-
    rbit_(Shift, Int, 0, _Int, Reverse).

rbit_(0, Int, Reverse, Int, Reverse) :- !.
rbit_(Shift, Int0, Reverse0, Int, Reverse) :-
    succ(Shift_, Shift),
    Reverse_ is (Reverse0 << 1) \/ (Int0 /\ 1),
    Int_ is Int0 >> 1,
    rbit_(Shift_, Int_, Reverse_, Int, Reverse).

Arity-3 rbit/3 predicate throws away the residual. Any bit values lying outside the shifting span disappear; they do not appear in the residual and the predicate discards them. The order of the sub-terms is not very important, except for failures. Placing succ first ensures that recursive shifting fails if Shift is not a positive integer; it triggers an exception if not actually an integer.

Left Carry

The implementation takes care of CRC truncation when shifting left. The same issue does not exist when shifting right. Right shifts implicitly discard the least-significant bit but not so with leftwise shifting. Shifting left in Prolog expands the integer indefinitely, not just up to the platform’s native integer size. The SWI edition of Prolog WIELEMAKER et al. (2012) utilises GNU’s multi-precision arithmetic library (GMP) to represent all numbers including integers. Integer bit-width grows to any giant size, limited only by the size of the memory available. Prolog lets integers left-shift millions of times—the result is a very large integer.

Shifting with carry is a basic arithmetic operation. CPU cores typically equip register shift with carry operations. The operation performs a bit shift and moves the overflow bit to the carry flag; subsequent machine operations test the carry bit. CRC computation requires the same operation but over arbitrary widths. A ‘shift left with carry’ using higher-level arithmetic needs a width whereas right does not. The least-significant bit automatically disappears on right-shift. Left shifting applies a mask and consequently requires a bit vector width—the degree \(Deg\) of the polynomial in the bit_left/4 predicate below. Contrast with the corresponding bit_right/3.

bit_left(Deg, Int0, Bit, Int) :-
    Bit is getbit(Int0, Deg - 1),
    Int is (Int0 << 1) /\ ((1 << Deg) - 1).

bit_right(Int0, Bit, Int) :-
    Bit is getbit(Int0, 0),
    Int is Int0 >> 1.