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, % +Shift, +Width, ?Word, ?Bits, ?Rest 31 bits/4, % +ShiftWidthPair, ?Word, ?Bits, ?Rest 32 bits/3, % +ShiftWidthPair, ?Word, ?Bits 33 bit_fields/3, % +Fields,+Shift,+Int 34 bit_fields/4, % +Fields,+Shift,+Int0,-Int 35 rbit/3, % +Shift:integer,+Int,?Reverse 36 xdigit_weights_and_bytes/2, % ?Weights:list(integer), ?Bytes:list(integer) 37 xbytes//1 % ?Bytes 38 ]). 39:- use_module(library(dcg/basics)). 40:- use_module(library(clpfd)). 41 42%! bits(+Shift, +Width, ?Word, ?Bits, ?Rest) is semidet. 43%! bits(+ShiftWidthPair, ?Word, ?Bits, ?Rest) is semidet. 44%! bits(+ShiftWidthPair, ?Word, ?Bits) is semidet. 45% 46% Unifies Bits within a Word using Shift and Width. All arguments are 47% integers treated as words of arbitrary bit-width. 48% 49% The implementation uses relational integer arithmetic, i.e. CLP(FD). 50% Hence allows for forward and backward transformations from Word to 51% Bits and vice versa. Integer Word applies a Shift and bit Width mask 52% to integer Bits. Bits is always a smaller integer. Decomposes the 53% problem into shifting and masking. Treats these operations 54% separately. 55% 56% @arg Width of Bits from Word after Shift. Width of zero always 57% fails. 58 59bits(Shift, Width, Word, Bits, Rest) :- 60 Mask #= (1 << Width - 1) << Shift, 61 Bits0 #= Word /\ Mask, 62 Rest #= Word xor Bits0, 63 Word #= Bits0 /\ Mask \/ Rest, 64 Bits #= Bits0 // (1 << Shift), 65 Bits0 #= Bits << Shift. 66 67bits(Shift-Width, Word, Bits, Rest) :- bits(Shift, Width, Word, Bits, Rest). 68 69bits(Shift-Width, Word, Bits) :- bits(Shift, Width, Word, Bits, _Rest).
The predicates are semi-deterministic. They can fail. Failure occurs when the bit-field Width integers do not sum to Shift.
92bit_fields([], 0, _Int). 93bit_fields([Value:Width|Rest], Shift, Int) :- 94 Shift_ is Shift - Width, 95 Value is (Int >> Shift_) /\ ((1 << Width) - 1), 96 bit_fields(Rest, Shift_, Int). 97 98bit_fields([], 0, Int, Int). 99bit_fields([Value:Width|Rest], Shift, Int0, Int) :- 100 Shift_ is Shift - Width, 101 Int_ is Int0 \/ ((Value /\ ((1 << Width) - 1)) << Shift_), 102 bit_fields(Rest, Shift_, Int_, Int).
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.
117rbit(Shift, Int, Reverse) :- rbit(Shift, Int, 0, _Int, Reverse). 118 119rbit(0, Int, Reverse, Int, Reverse) :- !. 120rbit(Shift, Int0, Reverse0, Int, Reverse) :- 121 succ(Shift_, Shift), 122 Reverse_ is (Reverse0 << 1) \/ (Int0 /\ 1), 123 Int_ is Int0 >> 1, 124 rbit(Shift_, Int_, Reverse_, Int, Reverse).
Examples:
?- xdigit_weights_and_bytes([10, 11, 12, 13], Bytes). Bytes = [171, 205]. ?- xdigit_weights_and_bytes(Weights, [171, 205]). Weights = [10, 11, 12, 13].
This predicate is semidet, meaning it can succeed or fail depending on the input. The elements of the Weights list must be in the range 0..15, and the elements of the Bytes list must be in the range 0..255. The length of the Weights and Bytes lists must differ by a factor of two for the conversion to succeed. Two hexadecimal digit weights correspond to one byte.
150xdigit_weights_and_bytes([], []). 151xdigit_weights_and_bytes([H1, H2|T0], [H|T]) :- 152 H #= (H1 << 4) \/ H2, % Perform the inverse operations; convert back from a byte to weights. % Extract the high and low nibbles. H1 #= H >> 4, H2 #= H /\ 16'f, % Ensure that the weights are valid for hexadecimal digits. % H1 and H2 must be in the range 0..15 otherwise the conversion fails. H1 in 16'0..16'f, H2 in 16'0..16'f, xdigit_weights_and_bytes(T0, T).
This predicate is semidet, meaning it can succeed or fail depending on the input. The elements of the Bytes list must be in the range 0..255.
174xbytes(Bytes) --> 175 { nonvar(Bytes), !, xdigit_weights_and_bytes(Weights, Bytes) 176 }, 177 xdigits(Weights). 178xbytes(Bytes) --> 179 xdigits(Weights), 180 { xdigit_weights_and_bytes(Weights, Bytes) 181 }