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!