1/*  File:    canny/bits.pl
    2    Author:  Roy Ratcliffe
    3    Created: Aug 15 2022
    4    Purpose: Canny Bits
    5
    6Copyright (c) 2022, Roy Ratcliffe, Northumberland, United Kingdom
    7
    8Permission is hereby granted, free of charge,  to any person obtaining a
    9copy  of  this  software  and    associated   documentation  files  (the
   10"Software"), to deal in  the   Software  without  restriction, including
   11without limitation the rights to  use,   copy,  modify,  merge, publish,
   12distribute, sublicense, and/or sell  copies  of   the  Software,  and to
   13permit persons to whom the Software is   furnished  to do so, subject to
   14the following conditions:
   15
   16    The above copyright notice and this permission notice shall be
   17    included in all copies or substantial portions of the Software.
   18
   19THE SOFTWARE IS PROVIDED "AS IS", WITHOUT  WARRANTY OF ANY KIND, EXPRESS
   20OR  IMPLIED,  INCLUDING  BUT  NOT   LIMITED    TO   THE   WARRANTIES  OF
   21MERCHANTABILITY, FITNESS FOR A PARTICULAR   PURPOSE AND NONINFRINGEMENT.
   22IN NO EVENT SHALL THE AUTHORS  OR   COPYRIGHT  HOLDERS BE LIABLE FOR ANY
   23CLAIM, DAMAGES OR OTHER LIABILITY,  WHETHER   IN  AN ACTION OF CONTRACT,
   24TORT OR OTHERWISE, ARISING FROM,  OUT  OF   OR  IN  CONNECTION  WITH THE
   25SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
   26
   27*/
   28
   29:- module(canny_bits,
   30          [ bits/5,
   31            bits/4,
   32            bits/3,
   33            bit_fields/3,                       % +Fields,+Shift,+Int
   34            bit_fields/4,                       % +Fields,+Shift,+Int0,-Int
   35            rbit/3                              % +Shift:integer,+Int,?Reverse
   36          ]).   37
   38:- use_module(library(clpfd)).   39
   40%!  bits(+Shift, +Width, ?Word, ?Bits, ?Rest) is semidet.
   41%!  bits(+ShiftWidthPair, ?Word, ?Bits, ?Rest) is semidet.
   42%!  bits(+ShiftWidthPair, ?Word, ?Bits) is semidet.
   43%
   44%   Unifies Bits within a Word using Shift  and Width. All arguments are
   45%   integers treated as words of arbitrary bit-width.
   46%
   47%   The implementation uses relational integer arithmetic, i.e. CLP(FD).
   48%   Hence allows for forward and backward   transformations from Word to
   49%   Bits and vice versa. Integer Word applies a Shift and bit Width mask
   50%   to integer Bits. Bits is always   a  smaller integer. Decomposes the
   51%   problem  into  shifting  and  masking.    Treats   these  operations
   52%   separately.
   53%
   54%   @arg Width of Bits from  Word  after   Shift.  Width  of zero always
   55%   fails.
   56
   57bits(Shift, Width, Word, Bits, Rest) :-
   58    Mask #= (1 << Width - 1) << Shift,
   59    Bits0 #= Word /\ Mask,
   60    Rest #= Word xor Bits0,
   61    Word #= Bits0 /\ Mask \/ Rest,
   62    Bits #= Bits0 // (1 << Shift),
   63    Bits0 #= Bits << Shift.
   64
   65bits(Shift-Width, Word, Bits, Rest) :- bits(Shift, Width, Word, Bits, Rest).
   66
   67bits(Shift-Width, Word, Bits) :- bits(Shift, Width, Word, Bits, _Rest).

 bit_fields(+Fields:list, +Shift:integer, +Int:integer) is semidet

 bit_fields(+Fields:list, +Shift:integer, +Int0:integer, -Int:integer) is semidet

Two versions of the predicate unify Value:Width bit fields with integers. The arity-3 version requires a bound Int from which to find unbound (or bound) values in the Fields; used to extract values from integers else check values semi-deterministically. The arity-4 version of the predicate accumulates bit-field values by OR-wise merging shifted bits from Int0 to Int.

The predicates are semi-deterministic. They can fail. Failure occurs when the bit-field Width integers do not sum to Shift.

Arguments:

Fields	- is a list of value and width terms of the form Value:Width where Width is an integer; Value is either a variable or an integer.
Shift	- is an integer number of total bits, e.g. 8 for eight-bit bytes, 16 for sixteen-bit words and so on.

   90bit_fields([], 0, _Int).
   91bit_fields([Value:Width|Rest], Shift, Int) :-
   92    Shift_ is Shift - Width,
   93    Value is (Int >> Shift_) /\ ((1 << Width) - 1),
   94    bit_fields(Rest, Shift_, Int).
   95
   96bit_fields([], 0, Int, Int).
   97bit_fields([Value:Width|Rest], Shift, Int0, Int) :-
   98    Shift_ is Shift - Width,
   99    Int_ is Int0 \/ ((Value /\ ((1 << Width) - 1)) << Shift_),
  100    bit_fields(Rest, Shift_, Int_, Int).

 rbit(+Shift:integer, +Int:integer, ?Reverse:integer) is semidet

Bit reversal over a given span of bits. The reverse bits equal the mirror image of the original; integer $1$ reversed in 16 bits becomes $8000_{16}$ for instance.

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.

  115rbit(Shift, Int, Reverse) :- rbit(Shift, Int, 0, _Int, Reverse).
  116
  117rbit(0, Int, Reverse, Int, Reverse) :- !.
  118rbit(Shift, Int0, Reverse0, Int, Reverse) :-
  119    succ(Shift_, Shift),
  120    Reverse_ is (Reverse0 << 1) \/ (Int0 /\ 1),
  121    Int_ is Int0 >> 1,
  122    rbit(Shift_, Int_, Reverse_, Int, Reverse)