I have a data structure in one of my applications which is an array of 32 bytes.

So basically 256 bits.

The code needs to check if all bits are empty or if all bits are full. So basically all clear or all set.

Currently this data structure uses an additional counter of 1 byte to smartly keep track of when a bit is set or cleared individually and it acts upon it's conclusion =D
(secret code =D)

So basically this code uses 1 branch to check the counter, and sometimes it does a little decrementing and sometimes a little incrementing.

So the code itself is pretty efficient.

There is ofcourse a slight little "problem" / "inefficiency" with this technique it consumes 1 additional byte.

So 1 out of 33 bytes. Maybe there are other implicit penalties where this 33 data structure is misaligned because of this 33 byte structure.

So reducing this structure to just 32 bytes could not only safe memory but it might also increase performance a little bit, to maybe a lot ?

So at least memory wise this would give a 3% reduction of memory consumption.

Performance wise I don't know.

Currently checking 256 bits with code with be much worse.

Possibilities:

1. Check each bit individually, this would be pretty stupid and slow.
2. Check each byte, so 32 comparisons, still pretty slow.
3. Check each word, so 16 comparisons, a bit better.
4. Check each longword, so 8 comparisons, a lot better but still slow.
5. Check each quadword, so 4 comparisons, only applicable in 64 bit application.

On some systems 64 bit integer compare can still take two clock cycles.

Is there something better and faster ?

Is there a 128 bit compare in a single clock or two ?

Is there a 256 bit compare in a single clock or two ?

Just wondering ! ;)

Anyway in case such an instruction would exist for example:

if Are256BitsClear( DataStructure )

if Are256BitsSet( DataStructure )

then the counter could most likely/ofcourse be removed =D
and the data structure would be a nice 32 byte fit and a bit more efficient.

Perhaps it might even make sense to use 4 comparisons if the alignment somehow gives it more performance then the overhead of 4 comparisons lol.

Bye,
Skybuck.

I was just scanning the internet/googling it and I came across this, which is a pretty neat trick to start with lol:

https://github.com/holiman/uint256/blob/master/uint256.go

Particularly this code, written in go, I have never programmed in go but I can still read/understand some of it:

// Cmp compares z and x and returns:
//
// -1 if z < x
// 0 if z == x
// +1 if z > x
//
func (z *Int) Cmp(x *Int) (r int) {
// z < x <=> z - x < 0 i.e. when subtraction overflows.
d0, carry := bits.Sub64(z[0], x[0], 0)
d1, carry := bits.Sub64(z[1], x[1], carry)
d2, carry := bits.Sub64(z[2], x[2], carry)
d3, carry := bits.Sub64(z[3], x[3], carry)
if carry == 1 {
return -1
}
if d0|d1|d2|d3 == 0 {
return 0
}
return 1
}

The interesting part is in:

if d0|d1|d2|d3 == 0 {

Apperently what this code does is it retrieves 4x64 bit quantities.

OR-s them together.

And then checks the result of that with a single branch.

So at the assembler/instruction/compiler generated code level this would probably result in something like:
mov register1, 64 bits from array[0]
mov register2, 64 bits from array[1]
mov register3, 64 bits from array[2]
mov register4, 64 bits from array[3]
or register1, register2
or register1, register3
or register1, register4
jump if zero/jump if not zero.

Something like that, so this could be pretty efficient ! at least "branch times" are avoided/costly comparisons.
The jump zero flag instruction could also be pretty efficient, even more efficient than a cmp, because the or instruction may already have set it.

The only slight downside to this would be 7 extra instructions taking up some instruction cache.

All in all not to bad for a first google ! ;) This might be quite quick actually ! LOL and might be worth it.

And the nicest part about it is it doesn't require any special assembler or avx or mmx or sse instructions... hmmmm...

(And ofcourse the compiler has to be slightly efficient at generating this exact assembler code, but it can probably do that ! ;) maybe it has even some more tricks
up it's sleeve.)

Can you do better than this though ? Wondering...

Bye,
Skybuck.

This would make a fine implementation for Are256BitsClear.

This leaves Are256BitsSet still to be implemented...

Hmm can the same trick be done for AllSet ?

Probably with AND and checking for FF also decimally known as 255 :)

So for Are256BitsSet this code may work:

mov register1, 64 bits from array[0]
mov register2, 64 bits from array[1]
mov register3, 64 bits from array[2]
mov register4, 64 bits from array[3]
and register1, register2
and register1, register3
and register1, register4

jump if zero/jump if not zero.

^ Not sure about the jump if not zero instruction... this would probably be invalid.

It needs to be 255 or nothing at all.

My initially thought was to maybe negate it or something, turn 255 specific to zero somehow...

Maybe subtract 255 from it to see if it's zero... if not then it's not full.

Hmmm ?

Bye for now,
Skybuck.

skybuck2000 <skybuck2000@hotmail.com> writes:
>The code needs to check if all bits are empty or if all bits
>are full. So basically all clear or all set.

I'd set up two constant arrays, kinda like

uint32_t const f = 0xffffffff;
uint32_t const a0[ 8 ]={ 0, 0, 0, 0, 0, 0, 0, 0, };
uint32_t const a1[ 8 ]={ f, f, f, f, f, f, f, f, };

, and then use memcmp with those arrays:

if( !memcmp( ( void * )&x, ( void * )&a0, sizeof( x )))
puts( "x is all zero" );

. And only do more work /if/ I then learned that
this was too slow.

I found it fun to scan the internet to see if there is anybody that has/needs these same methods.

I came across unity documentation:

https://docs.unity3d.com/Packages/com.unity.render-pipelines.core@7.2/api/UnityEngine.Rendering.BitArray256.html

Describing

allTrue

True if all bits are 1.
Declaration

public bool allTrue { get; }

and it took a while to find the exact source code but it's here:

https://github.com/needle-mirror/com.unity.render-pipelines.core/blob/master/Runtime/Utilities/BitArray.cs

public bool allTrue => data1 == ulong.MaxValue && data2 == ulong.MaxValue && data3 == ulong.MaxValue && data4 == ulong.MaxValue;

from this class to give it a bit more context:
/// <summary>
/// Bit array of size 256.
/// </summary>
[Serializable]
[System.Diagnostics.DebuggerDisplay("{this.GetType().Name} {humanizedData}")]
public struct BitArray256 : IBitArray
{
[SerializeField]
ulong data1;
[SerializeField]
ulong data2;
[SerializeField]
ulong data3;
[SerializeField]
ulong data4;

/// <summary>Number of elements in the bit array.</summary>
public uint capacity => 256u;
/// <summary>True if all bits are 0.</summary>
public bool allFalse => data1 == 0uL && data2 == 0uL && data3 == 0uL && data4 == 0uL;
/// <summary>True if all bits are 1.</summary>
public bool allTrue => data1 == ulong.MaxValue && data2 == ulong.MaxValue && data3 == ulong.MaxValue && data4 == ulong.MaxValue;
/// <summary>Returns the bit array in a human readable form.</summary>

So let's go back to this code:

public bool allTrue => data1 == ulong.MaxValue && data2 == ulong.MaxValue && data3 == ulong.MaxValue && data4 == ulong.MaxValue;

It's a bit funny to see both solutions for allFalse and AllTrue the naming is nice, in my case you could think of it as AllEmpty and AllFull hint hint about secret code lol.

Anyway

At least the allFalse code could be written a bit more efficient HAHA ! =D
as already explored.

But can the allTrue code be written more efficient as well ? I think so...

At least the and's could be done on the data itself

(data1 && data2 && data3 && data4) == ulong.MaxValue
3's and's
1 comparison to max value.

Bye for now,
Skybuck.

I have created a "professional" github page, so you guys can download the example source code properly and quickly using GIT and don't have to hassle with newsgroup crappy messaging formats:

TData and TLink optimization project

https://github.com/SkybuckFlying/TDataTLinkOptimizationProject

The aim of the project is to:

Optimize the IsEmpty and IsFull routines for TData and TLink.
Optimize the Empty and Full routines for TData and TLink.
Implement WIN64 platform support by implementing BitSet and BitReset.

YES BABY ! =D It's 2021 ! Time to start sharing code a little bit more professionally and effectively and actually good usuable.

However in case you don't know how to use GIT and still want to have a look at the source code then I will post it here anyway,

we can also discuss further ideas for optimization on newsgroups, I am particularly interested in any high speed assembler assistence for x86 and/or x64 instruction set !

unit UnitTDataTLink;

{

TestProgram/Optimization Project for TData and TLink

version 0.02 created on 29 october 2021 by Skybuck Flying

TData contains an array of 32 bytes, in other words 256 bits.
TLink contains an array of 256 pointers.

The mission of this project is to optimize the IsEmpty and IsFull functions
to run as fast as possible on modern x86/x64 processors.

Bonus would be to optimize Empty and Full routines, however beware
the TLink structure uses special pointer values for empty and full.

The verification routines do not need to be optimized and should not
be optimized and are only there to verify any optimized code.

I will sure this code in github for easy downloading and uploading.

Would be cool to get some help with optimizing this code.

The original code used a mCount : byte; member to optimize the code
however this increases the TData structure to 33 bytes which could
be causing misalignment and consumes 3% more memory.

The TLink structure would also fit better if mCount is illiminated.

Both structures contained a mCount : byte variable and have been removed.

Now the same functionality to check for empty and full should be implemented
with as fast as code as possible without using any extra member fields
for the structures to keep them memory efficient like this.

Perhaps these link functions can be optimized with AVX-512 or so ?

}

{

version 0.03 created on 29 october 2021 by Skybuck Flying

Console program turned into multi-device-application project for
multi-platform support.

Project and Source files seperated into seperate folders to avoid
file clutter.

Only WIN32 platform currently implemented.

Other platforms possible thanks to multi-device-project/applicaation.

For some reason it was not possible to add platforms to a console project.

So I modified code so it can work with a multi-device-application, this
added a lot of platforms.

WIN64 platform support is desired !

The rest would be a bonus !

}

interface

uses
Classes; // for TStrings

type
TData = packed record
mData : packed array[0..31] of byte;

procedure Empty;
procedure Full;

function IsEmpty : boolean;
function IsFull : boolean;

// debug routines
function VerifyIsEmpty : boolean;
function VerifyIsFull : boolean;
function VerifyOne : boolean;
function VerifyRandomButOne : boolean;
procedure VerifyAll;
end;

TLink = packed record
mLink : packed array[0..255] of pointer;

procedure Empty;
procedure Full;

function IsEmpty : boolean;
function IsFull : boolean;

// debug routines
function VerifyIsEmpty : boolean;
function VerifyIsFull : boolean;
function VerifyOne : boolean;
function VerifyRandomButOne : boolean;
procedure VerifyAll;
end;

procedure MainTestProgram( ParaOutput : TStrings );

implementation

uses
SysUtils; // for IntToStr

const
ConstDataTestLoops = 1000000; // one million ! =D
ConstLinkTestLoops = 100000; // one hundred thousand ! =D

var
const_empty : pointer;
const_full : pointer;

var
vOutput : TStrings;

procedure OutputMessage( ParaString : string );
begin
vOutput.Add( ParaString );
end;

// only works on win32 platform, need win64 platform versions !

{$ifdef WIN32}
// unlocked versions (multi-threading-unsafe)
procedure BitReset( ParaMemory : pointer; ParaBitIndex : integer );
asm
btr [eax], edx
end;

procedure BitSet( ParaMemory : pointer; ParaBitIndex : integer );
asm
bts [eax], edx
end;

// locked versions (multi-threading-safe)
procedure LockedBitReset( ParaMemory : pointer; ParaBitIndex : integer );
asm
LOCK btr [eax], edx
end;

procedure LockedBitSet( ParaMemory : pointer; ParaBitIndex : integer );
asm
LOCK bts [eax], edx
end;
{$endif}

{$ifdef WIN64}
// unlocked versions (multi-threading-unsafe)
// optimize me ?
procedure BitReset( ParaMemory : pointer; ParaBitIndex : integer );
begin
// to be implemented
ERROR NOT IMPLEMENTED
end;

procedure BitSet( ParaMemory : pointer; ParaBitIndex : integer );
begin
// to be implemented
ERROR NOT IMPLEMENTED
end;

// not really required for this test program but would be nice to have a 64 bit version of this as well.
procedure LockedBitReset( ParaMemory : pointer; ParaBitIndex : integer );
begin

end;

procedure LockedBitSet( ParaMemory : pointer; ParaBitIndex : integer );
begin

end;
{$endif}

{$ifdef WIN32}
procedure TData.Empty;
type
TUInt32Array = packed array[0..7] of UInt32;
begin
TUInt32Array(mData)[0] := 0;
TUInt32Array(mData)[1] := 0;
TUInt32Array(mData)[2] := 0;
TUInt32Array(mData)[3] := 0;
TUInt32Array(mData)[4] := 0;
TUInt32Array(mData)[5] := 0;
TUInt32Array(mData)[6] := 0;
TUInt32Array(mData)[7] := 0;
end;
{$endif}

{$ifdef WIN64}
procedure TData.Empty;
type
TUInt64Array = packed array[0..3] of UInt64;
begin
TUInt64Array(mData)[0] := 0;
TUInt64Array(mData)[1] := 0;
TUInt64Array(mData)[2] := 0;
TUInt64Array(mData)[3] := 0;
end;
{$endif}

{$ifdef WIN32}
procedure TData.Full;
type
TUInt32Array = packed array[0..7] of longword;
begin
// 11223344
TUInt32Array(mData)[0] := $FFFFFFFF;
TUInt32Array(mData)[1] := $FFFFFFFF;
TUInt32Array(mData)[2] := $FFFFFFFF;
TUInt32Array(mData)[3] := $FFFFFFFF;
TUInt32Array(mData)[4] := $FFFFFFFF;
TUInt32Array(mData)[5] := $FFFFFFFF;
TUInt32Array(mData)[6] := $FFFFFFFF;
TUInt32Array(mData)[7] := $FFFFFFFF;
end;
{$endif}

{$ifdef WIN64}
procedure TData.Full;
type
TUInt64Array = packed array[0..3] of UInt64;
begin
// 1122334455667788
TUInt64Array(mData)[0] := $FFFFFFFFFFFFFFFF;
TUInt64Array(mData)[1] := $FFFFFFFFFFFFFFFF;
TUInt64Array(mData)[2] := $FFFFFFFFFFFFFFFF;
TUInt64Array(mData)[3] := $FFFFFFFFFFFFFFFF;
end;
{$endif}

{$ifdef WIN32}
function TData.IsEmpty : boolean;
type
TUInt32Array = packed array[0..7] of longword;
var
vResult : longword;
begin
result := False;

vResult :=
TUInt32Array(mData)[0] or
TUInt32Array(mData)[1] or
TUInt32Array(mData)[2] or
TUInt32Array(mData)[3] or
TUInt32Array(mData)[4] or
TUInt32Array(mData)[5] or
TUInt32Array(mData)[6] or
TUInt32Array(mData)[7];

if vResult = 0 then
begin
result := True;
end;
end;
{$endif}

{$ifdef WIN64}
function TData.IsEmpty : boolean;
type
TUInt64Array = packed array[0..3] of UInt64;
var
vResult : UInt64;
begin
result := False;

vResult :=
TUInt64Array(mData)[0] or
TUInt64Array(mData)[1] or
TUInt64Array(mData)[2] or
TUInt64Array(mData)[3];

if vResult = 0 then
begin
result := True;
end;
end;
{$endif}

{$ifdef WIN32}
function TData.IsFull : boolean;
type
TUInt32Array = packed array[0..7] of longword;
var
vResult : UInt64;
begin
result := False;

vResult :=
TUInt32Array(mData)[0] and
TUInt32Array(mData)[1] and
TUInt32Array(mData)[2] and
TUInt32Array(mData)[3] and
TUInt32Array(mData)[4] and
TUInt32Array(mData)[5] and
TUInt32Array(mData)[6] and
TUInt32Array(mData)[7];

// 11223344
if vResult = $FFFFFFFF then
begin
result := True;
end;
end;
{$endif}

{$ifdef WIN64}
function TData.IsFull : boolean;
type
TUInt64Array = packed array[0..3] of UInt64;
var
vResult : UInt64;
begin
result := False;

vResult :=
TUInt64Array(mData)[0] and
TUInt64Array(mData)[1] and
TUInt64Array(mData)[2] and
TUInt64Array(mData)[3];

// 1122334455667788
if vResult = $FFFFFFFFFFFFFFFF then
begin
result := True;
end;
end;
{$endif}

// TData verification routines

function TData.VerifyIsEmpty : boolean;
var
vIndex : integer;
begin
result := True;
for vIndex := 0 to 31 do
begin
if mData[vIndex] <> 0 then
begin
result := False;
end;
end;
end;

Groovy hepcat Stefan Ram was jivin' in comp.lang.c on Fri, 29 Oct 2021
12:19 pm. It's a cool scene! Dig it.

> skybuck2000 <skybuck2000@hotmail.com> writes:
>>The code needs to check if all bits are empty or if all bits
>>are full. So basically all clear or all set.
>
> I'd set up two constant arrays, kinda like
>
> uint32_t const f = 0xffffffff;
> uint32_t const a0[ 8 ]={ 0, 0, 0, 0, 0, 0, 0, 0, };
> uint32_t const a1[ 8 ]={ f, f, f, f, f, f, f, f, };
>
> , and then use memcmp with those arrays:
>
> if( !memcmp( ( void * )&x, ( void * )&a0, sizeof( x )))
> puts( "x is all zero" );
>
> . And only do more work /if/ I then learned that
> this was too slow.

Here's a more flexible (but untested) way:

#define ALL_CLEAR 1
#define ALL_SET 2

unsigned all_bits_clear_or_set(unsigned char *data, size_t n)
{ unsigned clrset = 3;
size_t i;

for(i = 0; i < n; i++)
{
if((unsigned char)~0U == data[i])
{
clrset ^= ALL_SET;
break;
}
}

for(i = 0; i < n; i++)
{
if(0 == data[i])
{
clrset ^= ALL_CLEAR;
break;
}
}

return clrset;
}

sometype calling_function(some paramlist)
{ unsigned clrset;

/* some code */
clrset = all_bits_clear_or_set(somedata, size_of_somedata_in_bytes);
if(clrset & ALL_CLEAR)
{
/* All bits are clear. */
}
else if(clrset & ALL_SET)
{
/* All bits are set. */
}
/* some more code */
}

That's a more general solution, allowing for data of other sizes to be
tested. I like to write flexible, reuseable code. :)

--

----- Dig the NEW and IMPROVED news sig!! -----

-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!

Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> writes:

> Groovy hepcat Stefan Ram was jivin' in comp.lang.c on Fri, 29 Oct 2021
> 12:19 pm. It's a cool scene! Dig it.
>
>> skybuck2000 <skybuck2000@hotmail.com> writes:
>>>The code needs to check if all bits are empty or if all bits
>>>are full. So basically all clear or all set.
>>
>> I'd set up two constant arrays, kinda like
>>
>> uint32_t const f = 0xffffffff;
>> uint32_t const a0[ 8 ]={ 0, 0, 0, 0, 0, 0, 0, 0, };
>> uint32_t const a1[ 8 ]={ f, f, f, f, f, f, f, f, };
>>
>> , and then use memcmp with those arrays:
>>
>> if( !memcmp( ( void * )&x, ( void * )&a0, sizeof( x )))
>> puts( "x is all zero" );
>>
>> . And only do more work /if/ I then learned that
>> this was too slow.
>
> Here's a more flexible (but untested) way:
>
> #define ALL_CLEAR 1
> #define ALL_SET 2
>
> unsigned all_bits_clear_or_set(unsigned char *data, size_t n)
> {
> unsigned clrset = 3;
> size_t i;
>
> for(i = 0; i < n; i++)
> {
> if((unsigned char)~0U == data[i])
> {
> clrset ^= ALL_SET;
> break;
> }
> }

Logically, this is a while loop. I see of a lot of for loops being used
this way. Is there an active anti-while campaign I've missed?

> for(i = 0; i < n; i++)
> {
> if(0 == data[i])
> {
> clrset ^= ALL_CLEAR;
> break;
> }
> }

Ditto.

size_t i = 0;
while (i < n && data[1] != 0) i++;
clrset ^= (i < n ? ALL_CLEAR : 0);

> return clrset;
> }

But this does not solve the problem. The OP wanted a test for all bits
in all bytes, not all bits in at least one byte.

--
Ben.

What about this:

template<bool Set>
bool test256( char *p )
{ uint64_t *p64 = (uint64_t *)p;
if constexpr( Set )
return p64[0] == -1 && !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
else
return p64[0] == 0 && !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
}

Or if the testing-parameter is variable:

bool test256( char *p, bool set )
{ uint64_t *p64 = (uint64_t *)p;
return !(p64[0] + set) && !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
}

Am 03.11.2021 um 21:09 schrieb Bonita Montero:
> Or if the testing-parameter is variable:
>
> bool test256( char *p, bool set )
> {
>     uint64_t *p64 = (uint64_t *)p;
>     return !(p64[0] + set) && !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
Or more efficient:
return !(p64[0] + set) & !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
> }

In assembly:

movzx rax, dl
add rax, [rcx]
setz al
mov rdx, [rcx]
xor rdx, [rcx + 8]
xor rdx, [rcx + 16]
xor rdx, [rcx + 24]
setz dl
and al, dl
ret

rcx is the pointer to the memory block with 256 bits and dl
if either 0 or 1, depending if the bits should be all 0 or 1.

Am 03.11.2021 um 21:25 schrieb Bonita Montero:
> In assembly:
>
>     movzx    rax, dl
>     add      rax, [rcx]
>     setz     al
>     mov      rdx, [rcx]
>     xor      rdx, [rcx + 8]
>     xor      rdx, [rcx + 16]
>     xor      rdx, [rcx + 24]
>     setz     dl
>     and      al, dl
>     ret
>
> rcx is the pointer to the memory block with 256 bits and dl
> if either 0 or 1, depending if the bits should be all 0 or 1.

Can anyone beat this ?
I tested the above code on my Linux-machine:

#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;

extern "C"
bool test256( char const *p, bool f );

int main()
{ char mem[256 / 8] = { 0 };
auto start = high_resolution_clock::now();
for( size_t i = 100'000'000; i; --i )
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false ),
test256( mem, false );
double ns = (int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1.0e9;
cout << ns << endl;
}

And each iteration is about 1.1ns, i.e 4.4 clock cycles.

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 03.11.2021 um 21:25 schrieb Bonita Montero:
>> In assembly:
>>     movzx    rax, dl
>>     add      rax, [rcx]
>>     setz     al
>>     mov      rdx, [rcx]
>>     xor      rdx, [rcx + 8]
>>     xor      rdx, [rcx + 16]
>>     xor      rdx, [rcx + 24]
>>     setz     dl
>>     and      al, dl
>>     ret
>> rcx is the pointer to the memory block with 256 bits and dl
>> if either 0 or 1, depending if the bits should be all 0 or 1.
>
> Can anyone beat this ?

But I don't think the code is correct:

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

bool test256(char *p, bool set)
{
uint64_t *p64 = (uint64_t *)p;
return !(p64[0] + set) & !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
}

int main(void)
{
char b[32] = {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
printf("%d\n", test256(b, true));
}

prints 1.

In addition, there is undefined behaviour if the pointer p is not
correctly aligned for uint64_t.

--
Ben.

You're right, but this works:

bool test256( char *p, bool set )
{ uint64_t *p64 = (uint64_t *)p;
return !(p64[0] + set) & !(p64[1] + set) & !(p64[2] + set) & !(p64[3] +
set);
}

Bonita Montero <Bonita.Montero@gmail.com> writes:

> You're right, but this works:
>
> bool test256( char *p, bool set )
> {
> uint64_t *p64 = (uint64_t *)p;

This is undefined id p is not properly aligned for uint64_t.

> return !(p64[0] + set) & !(p64[1] + set) & !(p64[2] + set) & !(p64[3] + set);
> }
>

--
Ben.

Am 04.11.2021 um 17:58 schrieb Bonita Montero:
> You're right, but this works:
>
> bool test256( char *p, bool set )
> {
>     uint64_t *p64 = (uint64_t *)p;
>     return !(p64[0] + set) & !(p64[1] + set) & !(p64[2] + set) &
> !(p64[3] + set);
> }

This is the assembly-variant (MSVC):

PUBLIC ?test256@@YA_NPEBD_N@Z

_TEXT SEGMENT
?test256@@YA_NPEBD_N@Z PROC
movzx rdx, dl
mov r8, [rcx]
add r8, rdx
setz al
mov r8, [rcx + 8]
add r8, rdx
setz ah
and al, ah
mov r8, [rcx + 16]
add r8, rdx
setz ah
and al, ah
mov r8, [rcx + 24]
add r8, rdx
setz ah
and al, ah
ret
?test256@@YA_NPEBD_N@Z ENDP
_TEXT ENDS
END

rcx is p, dl is set, r8 is volatile.

Am 04.11.2021 um 18:13 schrieb Ben Bacarisse:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> You're right, but this works:
>>
>> bool test256( char *p, bool set )
>> {
>> uint64_t *p64 = (uint64_t *)p;
>
> This is undefined id p is not properly aligned for uint64_t.

Doesn't matter on x86-computers, they're even optimized in a way that
unaligned accesses that don't cross page-bounaries have no performance
-penalty.

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 04.11.2021 um 18:13 schrieb Ben Bacarisse:
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> You're right, but this works:
>>>
>>> bool test256( char *p, bool set )
>>> {
>>> uint64_t *p64 = (uint64_t *)p;
>>
>> This is undefined [if] p is not properly aligned for uint64_t.
>
> Doesn't matter on x86-computers, they're even optimized in a way that
> unaligned accesses that don't cross page-bounaries have no performance
> -penalty.

I think it helps to point out when code is not portable.

--
Ben.

Bonita Montero <Bonita.Montero@gmail.com> writes:
>Am 04.11.2021 um 18:13 schrieb Ben Bacarisse:
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> You're right, but this works:
>>>
>>> bool test256( char *p, bool set )
>>> {
>>> uint64_t *p64 = (uint64_t *)p;
>>
>> This is undefined id p is not properly aligned for uint64_t.
>
>Doesn't matter on x86-computers, they're even optimized in a way that
>unaligned accesses that don't cross page-bounaries have no performance
>-penalty.
>

It is, of course, possible to implement the entire test256
function with three instructions on x86. Exercise left
to the student, but hint: AVX.

Am 04.11.2021 um 18:27 schrieb Ben Bacarisse:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> Am 04.11.2021 um 18:13 schrieb Ben Bacarisse:
>>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>>
>>>> You're right, but this works:
>>>>
>>>> bool test256( char *p, bool set )
>>>> {
>>>> uint64_t *p64 = (uint64_t *)p;
>>>
>>> This is undefined [if] p is not properly aligned for uint64_t.
>>
>> Doesn't matter on x86-computers, they're even optimized in a way that
>> unaligned accesses that don't cross page-bounaries have no performance
>> -penalty.
>
> I think it helps to point out when code is not portable.

Doesn't matter.

On 04/11/2021 11:37, Ben Bacarisse wrote:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> Am 03.11.2021 um 21:25 schrieb Bonita Montero:
>>> In assembly:
>>>     movzx    rax, dl
>>>     add      rax, [rcx]
>>>     setz     al
>>>     mov      rdx, [rcx]
>>>     xor      rdx, [rcx + 8]
>>>     xor      rdx, [rcx + 16]
>>>     xor      rdx, [rcx + 24]
>>>     setz     dl
>>>     and      al, dl
>>>     ret
>>> rcx is the pointer to the memory block with 256 bits and dl
>>> if either 0 or 1, depending if the bits should be all 0 or 1.
>>
>> Can anyone beat this ?
>
> But I don't think the code is correct:
>
> #include <stdio.h>
> #include <stdbool.h>
> #include <stdint.h>
>
> bool test256(char *p, bool set)
> {
> uint64_t *p64 = (uint64_t *)p;
> return !(p64[0] + set) & !(p64[0] ^ p64[1] ^ p64[2] ^ p64[3]);
> }
>
> int main(void)
> {
> char b[32] = {
> -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
> };
> printf("%d\n", test256(b, true));
> }
>
> prints 1.
>
> In addition, there is undefined behaviour if the pointer p is not
> correctly aligned for uint64_t.

I had a similar solution (not posted*) based on operations between
64-bit elements.

It came with a note that it required the 32-byte array to be
64-bit-aligned. And where performance is important, as appeared to be
the case in the OP, then that should be the case; the caller should
ensure it.

(* Lost now but something like:

if ((p[0] | p[1] | p[2] | p[3]) == 0) return 1;
if ((p[0] & p[1] & p[2] & p[3]) == -1) return 1;
return 0;
)

On 11/4/2021 6:13 PM, Bonita Montero wrote:
> Am 04.11.2021 um 17:58 schrieb Bonita Montero:
>> You're right, but this works:
>>
>> bool test256( char *p, bool set )
>> {
>>      uint64_t *p64 = (uint64_t *)p;
>>      return !(p64[0] + set) & !(p64[1] + set) & !(p64[2] + set) &
>> !(p64[3] + set);
>> }
>
> This is the assembly-variant (MSVC):
>
> PUBLIC ?test256@@YA_NPEBD_N@Z
>
> _TEXT SEGMENT
> ?test256@@YA_NPEBD_N@Z PROC
>     movzx    rdx, dl
>     mov      r8, [rcx]
>     add      r8, rdx
>     setz     al
>     mov      r8, [rcx + 8]
>     add      r8, rdx
>     setz     ah
>     and      al, ah
>     mov      r8, [rcx + 16]
>     add      r8, rdx
>     setz     ah
>     and      al, ah
>     mov      r8, [rcx + 24]
>     add      r8, rdx
>     setz     ah
>     and      al, ah
>     ret
> ?test256@@YA_NPEBD_N@Z ENDP
> _TEXT ENDS
> END
>
> rcx is p, dl is set, r8 is volatile.

This may leave ah nonzero on ret

Am 04.11.2021 um 19:28 schrieb Manfred:
> On 11/4/2021 6:13 PM, Bonita Montero wrote:
>> Am 04.11.2021 um 17:58 schrieb Bonita Montero:
>>> You're right, but this works:
>>>
>>> bool test256( char *p, bool set )
>>> {
>>>      uint64_t *p64 = (uint64_t *)p;
>>>      return !(p64[0] + set) & !(p64[1] + set) & !(p64[2] + set) &
>>> !(p64[3] + set);
>>> }
>>
>> This is the assembly-variant (MSVC):
>>
>> PUBLIC ?test256@@YA_NPEBD_N@Z
>>
>> _TEXT SEGMENT
>> ?test256@@YA_NPEBD_N@Z PROC
>>      movzx    rdx, dl
>>      mov      r8, [rcx]
>>      add      r8, rdx
>>      setz     al
>>      mov      r8, [rcx + 8]
>>      add      r8, rdx
>>      setz     ah
>>      and      al, ah
>>      mov      r8, [rcx + 16]
>>      add      r8, rdx
>>      setz     ah
>>      and      al, ah
>>      mov      r8, [rcx + 24]
>>      add      r8, rdx
>>      setz     ah
>>      and      al, ah
>>      ret
>> ?test256@@YA_NPEBD_N@Z ENDP
>> _TEXT ENDS
>> END
>>
>> rcx is p, dl is set, r8 is volatile.
>
> This may leave ah nonzero on ret

A bool-return is a single byte returned in al.

On 11/4/2021 8:29 PM, Bonita Montero wrote:
> Am 04.11.2021 um 19:28 schrieb Manfred:
>> On 11/4/2021 6:13 PM, Bonita Montero wrote:
>>> Am 04.11.2021 um 17:58 schrieb Bonita Montero:
>>>> You're right, but this works:
>>>>
>>>> bool test256( char *p, bool set )
>>>> {
>>>>      uint64_t *p64 = (uint64_t *)p;
>>>>      return !(p64[0] + set) & !(p64[1] + set) & !(p64[2] + set) &
>>>> !(p64[3] + set);
>>>> }
>>>
>>> This is the assembly-variant (MSVC):
>>>
>>> PUBLIC ?test256@@YA_NPEBD_N@Z
>>>
>>> _TEXT SEGMENT
>>> ?test256@@YA_NPEBD_N@Z PROC
>>>      movzx    rdx, dl
>>>      mov      r8, [rcx]
>>>      add      r8, rdx
>>>      setz     al
>>>      mov      r8, [rcx + 8]
>>>      add      r8, rdx
>>>      setz     ah
>>>      and      al, ah
>>>      mov      r8, [rcx + 16]
>>>      add      r8, rdx
>>>      setz     ah
>>>      and      al, ah
>>>      mov      r8, [rcx + 24]
>>>      add      r8, rdx
>>>      setz     ah
>>>      and      al, ah
>>>      ret
>>> ?test256@@YA_NPEBD_N@Z ENDP
>>> _TEXT ENDS
>>> END
>>>
>>> rcx is p, dl is set, r8 is volatile.
>>
>> This may leave ah nonzero on ret
>
> A bool-return is a single byte returned in al.
>
>

But the assembler doesn't know that