Page 1 of 1
Wishlist Item
Posted: 22 May 2020 2:58
by choibakk
Hi Thomas, tried to email you but could not directly. Since you helped me with external functions [in an eallier support post for those that are looking] (to overcome a multiplication overflow when the overflow is desired) I have added a few more functions to my external "C" DLL, which makes me love VP even more--seriously. So a wish list predicate if you get the chance sometime in the future:
In "pfc\memory\bit.cl" you have:
Code: Select all
predicates
trailingZeroBits : (unsigned Value) -> unsigned Count.
% @short Calculating the number of consecutive low-order zeros
% @end
which is exactly what I needed, but it only supports unsigned, so I was using trailingZeroBits on the LOW/HI 32 bits and using mkUnsigned64 to put it back together to handle 64-bit unsigned integers. It would be great to have a 64 bit version of trailingZeroBits. In the interim, I added the following to my external "C" DLL for performance:
unsigned char APIENTRY Ls1b(UINT64 bits, UINT64* bitsOut, unsigned char* index)
{
unsigned long uint64 = 0;
unsigned char result = _BitScanForward64(&uint64, bits);
*index = (unsigned char)uint64;
if(bitsOut!=nullptr)
*bitsOut = bits ^ (1ULL << *index);
return result;
}
PS: The _BitScanForward64 is the relevant function and is a compiler intrinsic function in Visual Studio C++.
Thanks for all your hard work!
Re: Wishlist Item
Posted: 22 May 2020 15:15
by Martin Meyer
Hi choibakk,
Wikipedia gives instructions how you can code a
trailingZeroBits/1-> function for 64 bits:
Code: Select all
constants
m1 : unsigned64 = 0x5555555555555555.
m2 : unsigned64 = 0x3333333333333333.
m4 : unsigned64 = 0x0F0F0F0F0F0F0F0F.
class predicates
bitCount64 : (unsigned64 Value) -> unsigned64 Count.
clauses
bitCount64(Value) = Counter5 ** 0x7F :-
Counter0 = Value - (Value >> 1 ** m1),
Counter1 = (Counter0 ** m2) + (Counter0 >> 2 ** m2),
Counter2 = Counter1 + (Counter1 >> 4) ** m4,
Counter3 = Counter2 + (Counter2 >> 8),
Counter4 = Counter3 + (Counter3 >> 16),
Counter5 = Counter4 + (Counter4 >> 32).
class predicates
trailingZeroBits64 : (unsigned64 Value) -> unsigned64 Count.
clauses
trailingZeroBits64(Value) = if 0 = Value then sizeBitsOf(unsigned64) else bitCount64(Value - 1 ** ~~Value) end if.
Re: Wishlist Item
Posted: 22 May 2020 17:26
by Martin Meyer
I recommend however that you keep using the old style syntax for bitwise and boolean operators in build 905. The new syntax has an
issue in 64bit mode which affects
bitCount64/1->. For example try this in 32bit and 64bit modes:
Code: Select all
constants
m1 : unsigned64 = 0x5555555555555555.
m2 : unsigned64 = 0x3333333333333333.
m4 : unsigned64 = 0x0F0F0F0F0F0F0F0F.
%---
class predicates
bitCount64 : (unsigned64 Value) -> unsigned64 Count.
clauses
bitCount64(Value) = Counter5 ** 0x7F :-
Counter0 = Value - (Value >> 1 ** m1),
Counter1 = (Counter0 ** m2) + (Counter0 >> 2 ** m2),
Counter2 = Counter1 + (Counter1 >> 4) ** m4,
Counter3 = Counter2 + (Counter2 >> 8),
Counter4 = Counter3 + (Counter3 >> 16),
Counter5 = Counter4 + (Counter4 >> 32).
class predicates
trailingZeroBits64 : (unsigned64 Value) -> unsigned64 Count.
clauses
trailingZeroBits64(Value) = if Value = 0 then sizeBitsOf(unsigned64) else bitCount64(Value - 1 ** ~~Value) end if.
%---
class predicates
bitCount64_old : (unsigned64 Value) -> unsigned64 NumberOfOneBits.
clauses
bitCount64_old(Value) = bit::bitAnd(Counter5, 0x7F) :-
Counter0 = Value - bit::bitAnd(bit::bitRight(Value, 1), m1),
Counter1 = bit::bitAnd(Counter0, m2) + bit::bitAnd(bit::bitRight(Counter0, 2), m2),
Counter2 = bit::bitAnd(Counter1 + bit::bitRight(Counter1, 4), m4),
Counter3 = Counter2 + bit::bitRight(Counter2, 8),
Counter4 = Counter3 + bit::bitRight(Counter3, 16),
Counter5 = Counter4 + bit::bitRight(Counter4, 32).
class predicates
trailingZeroBits64_old : (unsigned64 Value) -> unsigned64 NumberOfTrailingZeroBits.
clauses
trailingZeroBits64_old(Value) =
if Value = 0 then sizeBitsOf(unsigned64) else bitCount64_old(bit::bitAnd(Value - 1, bit::bitNot(Value))) end if.
%---
clauses
run() :-
One = hasDomain(unsigned64, 1),
ShiftLeft = hasDomain(unsigned64, 3),
Value = bit::bitLeft(One, ShiftLeft),
stdIO::writeF('new: 0x%X -> %d\n', Value, trailingZeroBits64(Value)),
stdIO::writeF('old: 0x%X -> %d\n', Value, trailingZeroBits64_old(Value)).
Re: Wishlist Item
Posted: 26 May 2020 15:53
by Thomas Linder Puls
It is not a problem to add such a predicate. But I wonder whether the result should be an unsigned64 or an unsigned (clearly the number is at most 64, so it will easily fit into an unsigned)?
Re: Wishlist Item
Posted: 26 May 2020 21:39
by Martin Meyer
In my class
bitAddOn I give all bit counts type
positive or in some cases
positiveOptional. For example I have
Code: Select all
predicates
getLowBitPos64 : (unsigned64 X) -> positiveOptional BitPosition.
% @short Returns the position of the lowest 1-bit
% @end
where a result of
-1 means that there is no 1-bit in
X, i.e.
X is zero.
Re: Wishlist Item
Posted: 2 Jun 2020 8:28
by Thomas Linder Puls
Visual Prolog 9 build 906:
trailingZeroBits64 has been added to
bit, and bit counts has been changes to
positive
Code: Select all
predicates
bitCount : (unsigned Value) -> positive Count.
bitCount64 : (unsigned64 Value) -> positive Count.
% @short Returns the number of non-zero bits
% @end
predicates
isPow2 : (unsigned Value) determ.
% @short Successful if only one bit is set to 1
% @end
predicates
trailingZeroBits : (unsigned Value) -> positive Count.
trailingZeroBits64 : (unsigned64 Value) -> positive Count.
% @short Calculating the number of consecutive low-order zeros
% @end
Re: Wishlist Item
Posted: 19 Jun 2020 23:14
by choibakk
Wow, thank you!