Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Equivalent unary operators for BSF and BSR
43 views
Skip to first unread message
Rick C. Hodgin
Jul 29, 2017, 6:27:11 PM7/29/17
to
Are there C language operator equivalents of the feature given by
Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
reverse)? They return the bit position of the lowest (BSF) or
highest (BSR) set bit (a bit with a 1 in it).
BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
If not, I propose new unary operators:
?<< for BSF, as it scans up to find the first 1 bit
>>? for BSR, as it scans down to find the first 1 bit
Sample usage:
// BSF equivalent operator usage: bits = x?<<;
// BSR equivalent operator usage: bits = >>?x;
unsigned int lowest_bit(unsigned int x)
{
unsigned int bits;
// Equivalent of:
// bits = x?<<;
_asm {
bsf eax,x
mov bits,eax
}
// Return indicates the lowest bit position that has a 1
return(bits);
}
unsigned int highest_bit(unsigned int x)
{
unsigned int bits;
// Equivalent of:
// bits = >>?x;
_asm {
bsr eax,x
mov bits,eax
}
// Return indicates the highest bit position that has a 1
return(bits);
}
int main(int argc, char* argv[])
{
unsigned int i;
// Display the bit position of each of these values (1 << i)
for (i = 0; i < 32; i++)
printf("Highest bit in %u = %u\n", 1 << i,
highest_bit(1 << i));
return 0;
}
Thank you,
Rick C. Hodgin
Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
reverse)? They return the bit position of the lowest (BSF) or
highest (BSR) set bit (a bit with a 1 in it).
BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
If not, I propose new unary operators:
?<< for BSF, as it scans up to find the first 1 bit
>>? for BSR, as it scans down to find the first 1 bit
Sample usage:
// BSF equivalent operator usage: bits = x?<<;
// BSR equivalent operator usage: bits = >>?x;
unsigned int lowest_bit(unsigned int x)
{
unsigned int bits;
// Equivalent of:
// bits = x?<<;
_asm {
bsf eax,x
mov bits,eax
}
// Return indicates the lowest bit position that has a 1
return(bits);
}
unsigned int highest_bit(unsigned int x)
{
unsigned int bits;
// Equivalent of:
// bits = >>?x;
_asm {
bsr eax,x
mov bits,eax
}
// Return indicates the highest bit position that has a 1
return(bits);
}
int main(int argc, char* argv[])
{
unsigned int i;
// Display the bit position of each of these values (1 << i)
for (i = 0; i < 32; i++)
printf("Highest bit in %u = %u\n", 1 << i,
highest_bit(1 << i));
return 0;
}
Thank you,
Rick C. Hodgin
David Brown
Jul 29, 2017, 7:29:34 PM7/29/17
to
On 30/07/17 00:26, Rick C. Hodgin wrote:
> Are there C language operator equivalents of the feature given by
> Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
> reverse)? They return the bit position of the lowest (BSF) or
> highest (BSR) set bit (a bit with a 1 in it).
>
> BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
> BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
>
> If not, I propose new unary operators:
>
> ?<< for BSF, as it scans up to find the first 1 bit
> >>? for BSR, as it scans down to find the first 1 bit
>
Why not just have functions to do the job? An operator does not give
> Are there C language operator equivalents of the feature given by
> Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
> reverse)? They return the bit position of the lowest (BSF) or
> highest (BSR) set bit (a bit with a 1 in it).
>
> BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
> BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
>
> If not, I propose new unary operators:
>
> ?<< for BSF, as it scans up to find the first 1 bit
> >>? for BSR, as it scans down to find the first 1 bit
>
you any advantages here - it's just some cryptic symbols instead of a
nice named function.
If you want to propose that there should be functions like "ffs", "clz",
"ctz" (find first zero, count leading zeros, count trailing zeros) in
the standard library, then that would be fair enough. A common
implementation could be done in straight C, and an implementation could
use optimal implementations with bsf and bsr instructions on an x86
target. (Most processors have something similar - see the Wikipedia
page for examples.)
In the meantime, many compilers have extensions or built-ins that
implement these functions.
<https://en.wikipedia.org/wiki/Find_first_set>
If your compile supports a better inline assembly syntax, you can use
that to define the function. In gcc, you could use this as the
equivalent to your "lowest_bit" function:
static inline __attribute__((const, always_inline))
int bsf(unsigned int x) {
unsigned int b;
asm("bsf %[b], %[x]" : [b] "=r" (b) : [x] "r" (x));
return b;
}
Some might say it is a little ugly and hard to comprehend (and few would
deny that), but it's the kind of thing you write once then hide away in
a header somewhere rather than in application code. And it lets you use
"bsf" optimally - no extra mov, ret, call, etc.
Scott Lurndal
Jul 31, 2017, 8:25:56 AM7/31/17
to
"Rick C. Hodgin" <rick.c...@gmail.com> writes:
>Are there C language operator equivalents of the feature given by
>Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
>reverse)? They return the bit position of the lowest (BSF) or
>highest (BSR) set bit (a bit with a 1 in it).
>
> BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
> BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
>
$ info gcc --index-search=__builtin_ffs
>Are there C language operator equivalents of the feature given by
>Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
>reverse)? They return the bit position of the lowest (BSF) or
>highest (BSR) set bit (a bit with a 1 in it).
>
> BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
> BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
>
$ info gcc --index-search=__builtin_clz
David Brown
Jul 31, 2017, 8:36:19 AM7/31/17
to
builtins in gcc are certainly useful references for Rick here, but the
best that can be said of "info" is that some people have got used to it
enough to find it useful. Web links will more helpful to most people:
<https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fclz>
<https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fctz>
<https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fffs>
Rick C. Hodgin
Jul 31, 2017, 8:36:31 AM7/31/17
to
__builtin_clz() here:
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
Scott Lurndal
Jul 31, 2017, 10:41:53 AM7/31/17
to
David Brown <david...@hesbynett.no> writes:
>On 31/07/17 14:25, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> Are there C language operator equivalents of the feature given by
>>> Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
>>> reverse)? They return the bit position of the lowest (BSF) or
>>> highest (BSR) set bit (a bit with a 1 in it).
>>>
>>> BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
>>> BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
>>>
>>
>> $ info gcc --index-search=__builtin_ffs
>> $ info gcc --index-search=__builtin_clz
>>
>
>That is a fine mixture between useful and useless information. These
>builtins in gcc are certainly useful references for Rick here, but the
>best that can be said of "info" is that some people have got used to it
>enough to find it useful.
I can't disagree - I find 'info' almost useless. Give me a flat man
>On 31/07/17 14:25, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> Are there C language operator equivalents of the feature given by
>>> Intel's x86 instructions BSF (bit scan forward) and BSR (bit scan
>>> reverse)? They return the bit position of the lowest (BSF) or
>>> highest (BSR) set bit (a bit with a 1 in it).
>>>
>>> BSF: https://c9x.me/x86/html/file_module_x86_id_19.html
>>> BSR: https://c9x.me/x86/html/file_module_x86_id_20.html
>>>
>>
>> $ info gcc --index-search=__builtin_ffs
>> $ info gcc --index-search=__builtin_clz
>>
>
>That is a fine mixture between useful and useless information. These
>builtins in gcc are certainly useful references for Rick here, but the
>best that can be said of "info" is that some people have got used to it
>enough to find it useful.
page anyday.
David Brown
Jul 31, 2017, 10:59:03 AM7/31/17
to
files (they are also handy for referencing the exact version of gcc - I
have a dozen or so different versions on my system, for various
targets). But the web page versions are great for references like this.
Scott Lurndal
Jul 31, 2017, 11:02:55 AM7/31/17
to
A simple shell function.
Rick C. Hodgin
Aug 1, 2017, 10:35:48 AM8/1/17
to
On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
> It would work with repeated code on a consistent cadence:
A proper implementation that works in Visual Studio 2015:
#include <stdlib.h>
#include <stdio.h>
char switchdefault[] = "switch default";
char switch0[] = "switch 0";
char switch1[] = "switch 1";
char switch2[] = "switch 2";
char switch3[] = "switch 3";
char switch4[] = "switch 4";
char switch5[] = "switch 5";
char switch6[] = "switch 6";
char switch7[] = "switch 7";
int main(int argc, char* argv[])
{
unsigned char x, lnI;
char* tptr;
// Loop for testing all possible values
for (lnI = 0; lnI < 8; lnI++)
{
if (lnI == 0) x = 0;
else x = 1 << (lnI - 1);
_asm {
movzx edx, byte ptr x
shr edx,4
movzx ebx, byte ptr x
and ebx,0xf
// 5-bytes for each jmp DWORD below
lea edx, [edx*4 + edx]
add edx, offset high_00
jmp edx
high_00:
jmp DWORD ptr test_low_nibble // No bits
jmp DWORD ptr switch_statement_4 // 0001
jmp DWORD ptr switch_statement_5 // 001x
jmp DWORD ptr switch_statement_5 // 001x
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
test_low_nibble:
// 5-bytes for each jmp DWORD below
lea ebx, [ebx*4 + ebx]
add ebx, offset low_00
jmp ebx
low_00:
jmp DWORD ptr switch_statement_default // No bits
jmp DWORD ptr switch_statement_0 // 0001
jmp DWORD ptr switch_statement_1 // 001x
jmp DWORD ptr switch_statement_1 // 001x
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
switch_statement_default:
mov tptr,offset switchdefault
jmp done
switch_statement_0:
mov tptr,offset switch0
jmp done
switch_statement_1:
mov tptr,offset switch1
jmp done
switch_statement_2:
mov tptr,offset switch2
jmp done
switch_statement_3:
mov tptr,offset switch3
jmp done
switch_statement_4:
mov tptr,offset switch4
jmp done
switch_statement_5:
mov tptr,offset switch5
jmp done
switch_statement_6:
mov tptr,offset switch6
jmp done
switch_statement_7:
mov tptr,offset switch7
done:
}
printf("%s\n", tptr);
}
return 0;
}
A minor extension would allow a WORD or DWORD or QWORD value to be
utilized. In this way, at each use the custom lookup table required
for that switch () statement usage would be derived. And if you
simply needed the value, a function could be used when the BSR and
BSF instructions are not available.
> It would work with repeated code on a consistent cadence:
A proper implementation that works in Visual Studio 2015:
#include <stdlib.h>
#include <stdio.h>
char switchdefault[] = "switch default";
char switch0[] = "switch 0";
char switch1[] = "switch 1";
char switch2[] = "switch 2";
char switch3[] = "switch 3";
char switch4[] = "switch 4";
char switch5[] = "switch 5";
char switch6[] = "switch 6";
char switch7[] = "switch 7";
int main(int argc, char* argv[])
{
char* tptr;
// Loop for testing all possible values
for (lnI = 0; lnI < 8; lnI++)
{
if (lnI == 0) x = 0;
else x = 1 << (lnI - 1);
_asm {
movzx edx, byte ptr x
shr edx,4
movzx ebx, byte ptr x
and ebx,0xf
// 5-bytes for each jmp DWORD below
lea edx, [edx*4 + edx]
add edx, offset high_00
jmp edx
high_00:
jmp DWORD ptr test_low_nibble // No bits
jmp DWORD ptr switch_statement_4 // 0001
jmp DWORD ptr switch_statement_5 // 001x
jmp DWORD ptr switch_statement_5 // 001x
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_6 // 01xx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
jmp DWORD ptr switch_statement_7 // 1xxx
test_low_nibble:
// 5-bytes for each jmp DWORD below
lea ebx, [ebx*4 + ebx]
add ebx, offset low_00
jmp ebx
low_00:
jmp DWORD ptr switch_statement_default // No bits
jmp DWORD ptr switch_statement_0 // 0001
jmp DWORD ptr switch_statement_1 // 001x
jmp DWORD ptr switch_statement_1 // 001x
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_2 // 01xx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
jmp DWORD ptr switch_statement_3 // 1xxx
switch_statement_default:
mov tptr,offset switchdefault
jmp done
switch_statement_0:
mov tptr,offset switch0
jmp done
switch_statement_1:
mov tptr,offset switch1
jmp done
switch_statement_2:
mov tptr,offset switch2
jmp done
switch_statement_3:
mov tptr,offset switch3
jmp done
switch_statement_4:
mov tptr,offset switch4
jmp done
switch_statement_5:
mov tptr,offset switch5
jmp done
switch_statement_6:
mov tptr,offset switch6
jmp done
switch_statement_7:
mov tptr,offset switch7
done:
}
printf("%s\n", tptr);
}
return 0;
}
A minor extension would allow a WORD or DWORD or QWORD value to be
utilized. In this way, at each use the custom lookup table required
for that switch () statement usage would be derived. And if you
simply needed the value, a function could be used when the BSR and
BSF instructions are not available.
Scott Lurndal
Aug 1, 2017, 11:10:10 AM8/1/17
to
"Rick C. Hodgin" <rick.c...@gmail.com> writes:
>On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>> It would work with repeated code on a consistent cadence:
>
>A proper implementation that works in Visual Studio 2015:
>
<100+ lines elided>
>> It would work with repeated code on a consistent cadence:
>
>A proper implementation that works in Visual Studio 2015:
>
Just use __builtin_ffs/__builtin_clz and let the compiler deal
with architectures that don't have instruction sequences that
handle the operation.
If you're not using a compiler that offers such builtins, I'm sorry.
Here's a number of algorithms to find the least significant set bit.
http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear
Note that AArch64 has a Count Leading Zeros instruction, which handles
the BSR. BSF can be accomplished in two instructions - RBIT and CLZ.
Note also that CLZ can count leading ones by simply inverting the
register first.
Rick C. Hodgin
Aug 1, 2017, 11:17:51 AM8/1/17
to
On 8/1/2017 11:09 AM, Scott Lurndal wrote:
> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>> It would work with repeated code on a consistent cadence:
>>
>> A proper implementation that works in Visual Studio 2015:
>>
> <100+ lines elided>
>
> Just use __builtin_ffs/__builtin_clz and let the compiler deal
> with architectures that don't have instruction sequences that
> handle the operation.
I don't use GCC compilers. You'll note the example I gave was using
> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>> It would work with repeated code on a consistent cadence:
>>
>> A proper implementation that works in Visual Studio 2015:
>>
> <100+ lines elided>
>
> Just use __builtin_ffs/__builtin_clz and let the compiler deal
> with architectures that don't have instruction sequences that
> handle the operation.
Visual Studio 2015.
> If you're not using a compiler that offers such builtins, I'm sorry.
general in any compiler that supports inline assembly as well.
> Here's a number of algorithms to find the least significant set bit.
>
> http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear
>
> Note that AArch64 has a Count Leading Zeros instruction, which handles
> the BSR. BSF can be accomplished in two instructions - RBIT and CLZ.
>
> Note also that CLZ can count leading ones by simply inverting the
> register first.
Scott Lurndal
Aug 1, 2017, 11:23:57 AM8/1/17
to
"Rick C. Hodgin" <rick.c...@gmail.com> writes:
>On 8/1/2017 11:09 AM, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>>> It would work with repeated code on a consistent cadence:
>>>
>>> A proper implementation that works in Visual Studio 2015:
>>>
>> <100+ lines elided>
>>
>> Just use __builtin_ffs/__builtin_clz and let the compiler deal
>> with architectures that don't have instruction sequences that
>> handle the operation.
>
>I don't use GCC compilers. You'll note the example I gave was using
>Visual Studio 2015.
https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx
>On 8/1/2017 11:09 AM, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>>> It would work with repeated code on a consistent cadence:
>>>
>>> A proper implementation that works in Visual Studio 2015:
>>>
>> <100+ lines elided>
>>
>> Just use __builtin_ffs/__builtin_clz and let the compiler deal
>> with architectures that don't have instruction sequences that
>> handle the operation.
>
>I don't use GCC compilers. You'll note the example I gave was using
>Visual Studio 2015.
>
>> If you're not using a compiler that offers such builtins, I'm sorry.
>
>I'm working on algorithms I can use for CAlive, but they will work in
>general in any compiler that supports inline assembly as well.
Given that the assembler format varies by compiler/OS, I doubt that
>> If you're not using a compiler that offers such builtins, I'm sorry.
>
>I'm working on algorithms I can use for CAlive, but they will work in
>general in any compiler that supports inline assembly as well.
highly.
David Brown
Aug 1, 2017, 11:27:15 AM8/1/17
to
On 01/08/17 17:17, Rick C. Hodgin wrote:
> On 8/1/2017 11:09 AM, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>>> It would work with repeated code on a consistent cadence:
>>>
>>> A proper implementation that works in Visual Studio 2015:
>>>
>> <100+ lines elided>
>>
>> Just use __builtin_ffs/__builtin_clz and let the compiler deal
>> with architectures that don't have instruction sequences that
>> handle the operation.
>
> I don't use GCC compilers. You'll note the example I gave was using
> Visual Studio 2015.
Visual Studio has equivalent functions _BitScanForward, _BitScanReverse,
> On 8/1/2017 11:09 AM, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>>> It would work with repeated code on a consistent cadence:
>>>
>>> A proper implementation that works in Visual Studio 2015:
>>>
>> <100+ lines elided>
>>
>> Just use __builtin_ffs/__builtin_clz and let the compiler deal
>> with architectures that don't have instruction sequences that
>> handle the operation.
>
> I don't use GCC compilers. You'll note the example I gave was using
> Visual Studio 2015.
__lzcnt, etc. I don't know the details - but they are on the Wikipedia
page I posted previously.
Rick C. Hodgin
Aug 1, 2017, 11:28:09 AM8/1/17
to
machines of interest apart from the ARM world. And the code could
be modified in principle for ARM CPUs as well.
The point is, it's an algorithm that will work when BSF and BSR
are not available. And the design of the algorithm is sound.
It would be the way compilers could implement the >>? and ?<<
unary operators for performing this scan-bit operation. And
with some additional compiler logic, the same form could be
used for the granularity operators >>> and <<<.
Scott Lurndal
Aug 1, 2017, 11:34:46 AM8/1/17
to
"Rick C. Hodgin" <rick.c...@gmail.com> writes:
>On 8/1/2017 11:23 AM, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> On 8/1/2017 11:09 AM, Scott Lurndal wrote:
>>>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>>>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>>>>> It would work with repeated code on a consistent cadence:
>>>>>
>>>>> A proper implementation that works in Visual Studio 2015:
>>>>>
>>>> <100+ lines elided>
>>>>
>>>> Just use __builtin_ffs/__builtin_clz and let the compiler deal
>>>> with architectures that don't have instruction sequences that
>>>> handle the operation.
>>>
>>> I don't use GCC compilers. You'll note the example I gave was using
>>> Visual Studio 2015.
>>
>> https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx
>>>
>>>> If you're not using a compiler that offers such builtins, I'm sorry.
>>>
>>> I'm working on algorithms I can use for CAlive, but they will work in
>>> general in any compiler that supports inline assembly as well.
>>
>> Given that the assembler format varies by compiler/OS, I doubt that
>> highly.
>
>It will work on x86, and can be extended to x64. Those are the
>machines of interest apart from the ARM world. And the code could
>be modified in principle for ARM CPUs as well.
>
>The point is, it's an algorithm that will work when BSF and BSR
The algorithms on the bithacks page are much more space and
>On 8/1/2017 11:23 AM, Scott Lurndal wrote:
>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>> On 8/1/2017 11:09 AM, Scott Lurndal wrote:
>>>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>>>> On 8/1/2017 9:25 AM, Rick C. Hodgin wrote:
>>>>>> It would work with repeated code on a consistent cadence:
>>>>>
>>>>> A proper implementation that works in Visual Studio 2015:
>>>>>
>>>> <100+ lines elided>
>>>>
>>>> Just use __builtin_ffs/__builtin_clz and let the compiler deal
>>>> with architectures that don't have instruction sequences that
>>>> handle the operation.
>>>
>>> I don't use GCC compilers. You'll note the example I gave was using
>>> Visual Studio 2015.
>>
>> https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx
>>>
>>>> If you're not using a compiler that offers such builtins, I'm sorry.
>>>
>>> I'm working on algorithms I can use for CAlive, but they will work in
>>> general in any compiler that supports inline assembly as well.
>>
>> Given that the assembler format varies by compiler/OS, I doubt that
>> highly.
>
>It will work on x86, and can be extended to x64. Those are the
>machines of interest apart from the ARM world. And the code could
>be modified in principle for ARM CPUs as well.
>
>The point is, it's an algorithm that will work when BSF and BSR
time efficient that your algorithm.
And given that you're only claiming support for x86_32 and x86_64,
both of which have always and will always have the appropriate
instructions, this seems to be a pointless exercise.
Rick C. Hodgin
Aug 1, 2017, 11:40:07 AM8/1/17
to
On 8/1/2017 11:34 AM, Scott Lurndal wrote:
> The algorithms on the bithacks page are much more space and
> time efficient that your algorithm...
> The algorithms on the bithacks page are much more space and
I desire to add these features as new fundamental operators, Scott.
In addition to the bit-scan algorithms, also granularity, which will
range the bit positions into areas of interest, such as byte, word,
dword, qword, or other custom values.
In addition, I am writing my own compiler, Scott. I am able to
originate these ideas and these algorithms from that which I possess
within myself. I share that knowledge and experience here, and I
welcome any optimizations people have. This is my first toss at
the dart board on this algorithm. It's much easier to edit than
it is to create.+
For my areas of interest (x86, x64, and ARM), I think the bit-scan
assembly instructions are sufficient, and some code like what I
posted can be used for cases of granularity. In short, all of
these features can now be added as new operators in CAlive, so
they don't require built-ins, but introduce them as first-class
language citizens.
Rick C. Hodgin
Aug 1, 2017, 1:06:10 PM8/1/17
to
On 8/1/2017 11:34 AM, Scott Lurndal wrote:
> The algorithms on the bithacks page are much more space and
> time efficient that your algorithm.
I took a look at those algorithms. Which one(s) would you suggest for
> time efficient that your algorithm.
use on the bit-scan forward and reverse algorithms?
http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear
Is it the ZerosOnRightLinear algorithm? It yields this code:
27: // unsigned int v; // input to count trailing zero bits
28: int c; // output: c will count v's trailing zero bits,
29: // so if v is 1101000 (base 2), then c will be 3
30:
31:
32: if (v)
00C71000 8B 44 24 04 mov eax,dword ptr [v]
00C71004 85 C0 test eax,eax
00C71006 74 14 je testme+1Ch (0C7101Ch)
33: {
34: v = (v ^ (v - 1)) >> 1; // Set v's trailing 0s
// to 1s and zero rest
00C71008 8D 48 FF lea ecx,[eax-1]
00C7100B 33 C8 xor ecx,eax
35: for (c = 0; v; c++)
00C7100D B8 00 00 00 00 mov eax,0
00C71012 D1 E9 shr ecx,1
00C71014 74 0B je testme+21h (0C71021h)
00C71016 40 inc eax
36: v >>= 1;
00C71017 D1 E9 shr ecx,1
00C71019 75 FB jne testme+16h (0C71016h)
43: }
00C7101B C3 ret
37:
38: } else {
39: c = CHAR_BIT * sizeof(v);
00C7101C B8 20 00 00 00 mov eax,20h
40: }
41:
42: return(c);
00C71021 C3 ret
That code has multiple branches within it for the for-loop. It also
has two branch dependencies based on bitwise shift operations.
I don't know if it would be more efficient than the code I had,
though it would require fewer code bytes.
My algorithm may be larger, but it only takes two branches to get
through it, plus some minor overhead in each nibble, and I'm sure
some of that could be optimized with some thought.
Scott Lurndal
Aug 1, 2017, 1:35:29 PM8/1/17
to
"Rick C. Hodgin" <rick.c...@gmail.com> writes:
>On 8/1/2017 11:34 AM, Scott Lurndal wrote:
>> The algorithms on the bithacks page are much more space and
>> time efficient that your algorithm.
>
>I took a look at those algorithms. Which one(s) would you suggest for
>use on the bit-scan forward and reverse algorithms?
benchmark them.
>> The algorithms on the bithacks page are much more space and
>> time efficient that your algorithm.
>
>I took a look at those algorithms. Which one(s) would you suggest for
>use on the bit-scan forward and reverse algorithms?
Rick C. Hodgin
Aug 1, 2017, 1:43:30 PM8/1/17
to
benchmark them in the time between if you'd like, and I'll be happy
to read your results.
David Brown
Aug 1, 2017, 1:59:27 PM8/1/17
to
On 01/08/17 19:05, Rick C. Hodgin wrote:
> On 8/1/2017 11:34 AM, Scott Lurndal wrote:
>> The algorithms on the bithacks page are much more space and
>> time efficient that your algorithm.
>
> I took a look at those algorithms. Which one(s) would you suggest for
> use on the bit-scan forward and reverse algorithms?
>
None of them.
> On 8/1/2017 11:34 AM, Scott Lurndal wrote:
>> The algorithms on the bithacks page are much more space and
>> time efficient that your algorithm.
>
> I took a look at those algorithms. Which one(s) would you suggest for
> use on the bit-scan forward and reverse algorithms?
>
As Scott pointed out, all the platforms that interest you have hardware
instructions for the job. If you are using existing compilers, use
their intrinsics. If you are writing your own compiler, implement
intrinsics, functions, operators, etc., using these instructions.
Rick C. Hodgin
Aug 1, 2017, 2:22:02 PM8/1/17
to
same thing my algorithm does. Mine scans down from msb to lsb and
reports the position of the largest bit set in the value.
The algorithm you posted scans up counting zeros.
Do you have one which scans down and reports the position of the
most significant bit set in the value?
Scott Lurndal
Aug 1, 2017, 2:34:17 PM8/1/17
to
"Rick C. Hodgin" <rick.c...@gmail.com> writes:
>On 8/1/2017 1:43 PM, Rick C. Hodgin wrote:
>> On 8/1/2017 1:35 PM, Scott Lurndal wrote:
>>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>>> On 8/1/2017 11:34 AM, Scott Lurndal wrote:
>>>>> The algorithms on the bithacks page are much more space and
>>>>> time efficient that your algorithm.
>>>>
>>>> I took a look at those algorithms. Which one(s) would you suggest for
>>>> use on the bit-scan forward and reverse algorithms?
>>>
>>> benchmark them.
>>
>> I will. It's a low priority item. You're free to go ahead and
>> benchmark them in the time between if you'd like, and I'll be happy
>> to read your results.
>
>It occurred to me. That algorithm you suggested does not do the
>same thing my algorithm does. Mine scans down from msb to lsb and
>reports the position of the largest bit set in the value.
>
>The algorithm you posted scans up counting zeros.
>
>Do you have one which scans down and reports the position of the
>most significant bit set in the value?
If you have the count of leading zeros, determining the bit position
>On 8/1/2017 1:43 PM, Rick C. Hodgin wrote:
>> On 8/1/2017 1:35 PM, Scott Lurndal wrote:
>>> "Rick C. Hodgin" <rick.c...@gmail.com> writes:
>>>> On 8/1/2017 11:34 AM, Scott Lurndal wrote:
>>>>> The algorithms on the bithacks page are much more space and
>>>>> time efficient that your algorithm.
>>>>
>>>> I took a look at those algorithms. Which one(s) would you suggest for
>>>> use on the bit-scan forward and reverse algorithms?
>>>
>>> benchmark them.
>>
>> I will. It's a low priority item. You're free to go ahead and
>> benchmark them in the time between if you'd like, and I'll be happy
>> to read your results.
>
>It occurred to me. That algorithm you suggested does not do the
>same thing my algorithm does. Mine scans down from msb to lsb and
>reports the position of the largest bit set in the value.
>
>The algorithm you posted scans up counting zeros.
>
>Do you have one which scans down and reports the position of the
>most significant bit set in the value?
of the MSb is a simple subtract.
Rick C. Hodgin
Aug 1, 2017, 2:39:17 PM8/1/17
to
http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear
Only trailing zeros.
Rick C. Hodgin
Aug 1, 2017, 2:47:28 PM8/1/17
to
with a srand(0) seed. The BSR assembly opcode version gave 1.879 on
100M iterations, and my algorithm gave 2.927.
BSR = 53.2M function calls per second
Mine = 34.2M function calls per second
Rick C. Hodgin
Aug 1, 2017, 9:17:14 PM8/1/17
to
performance than my first algorithm:
int result;
// If the value's non-zero, return bit position (if any)
if (v != 0)
{
// Iterate through each bit
for (result = 7; result >= 0; result--, v <<= 1)
{
// Is this bit on?
if ((v & 0x80) != 0)
return(result); // Yes
}
// If we get here, no set bit was found
}
return(-1);
When extended out to processing full 32-bits, this algorithm targets
about 50% the speed of native BSR, and is the best solution I've been
able to create, which is a register-optimized version reducing the
score above from 1.879 to 1.772.
In using the function you specified for _BitScanReverse() in Visual
Studio 2015 produced an identical result to the non-register-
optimized BSR function. It reveals use of BSR:
91: int result;
92:
93: _BitScanReverse((DWORD*)&lnResult, v);
00A11061 0F BD 44 24 08 bsr eax,dword ptr [esp+8]
00A11066 89 04 24 mov dword ptr [esp],eax
94: return(result);
0 new messages