Discussions related to Visual Prolog
choibakk
Active Member
Posts: 35
Joined: 5 Sep 2019 19:30

Wishlist Item

Unread post 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!
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Wishlist Item

Unread post 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.
Regards Martin
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Wishlist Item

Unread post 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)).
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Wishlist Item

Unread post 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)?
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Wishlist Item

Unread post 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.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Wishlist Item

Unread post 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
Regards Thomas Linder Puls
PDC
choibakk
Active Member
Posts: 35
Joined: 5 Sep 2019 19:30

Re: Wishlist Item

Unread post by choibakk »

Wow, thank you!
Post Reply