On 18/12/2021 20:59, BGB wrote:
> On 12/18/2021 11:26 AM, David Brown wrote:

>> Compilers are free to change load and store orders on the assumption
>> that the current thread of execution is the only thing that ever sees
>> the accesses, unless you specifically say otherwise (with "volatile",
>> atomics, or other methods).  More extreme movements are usually only
>> done at higher levels of optimisation.  But if the code does not work
>> correctly at -O2, you can be pretty confident that your code is wrong.
>> Compiler bugs are not unheard of, of course, but user-code bugs are a
>> /lot/ more common!
>>
>
> This code is single threaded.
>
> The code in question depends on the use of misaligned and overlapping
> loads and stores. As a result, changing the relative load/store order
> will change the visible results.
>

Compilers assume you follow the rules for alignments - and then
overlapping cannot possibly occur (for types smaller than the maximum
alignment sizes). I don't think there is any way to construct objects
that overlap while remaining within the strict rules of C (by which I
mean, without invoking behaviour that is not defined by the standards.
Particular compilers might support it, however).

>
> I was trying to use pointers declared as:
>   __attribute__((__may_alias__)) __attribute__((aligned(1)))
>
> But, this did not work in GCC.

No, it will not. "may_alias" does not change alignment rules or allow
overlapping. And the "aligned" attribute is for /increasing/ alignment,
not reducing it. You might have better luck using a struct with the
"packed" attribute - that's the only way in gcc to work with unaligned
data in a fully defined way, I believe.

>
> However, 'volatile' did give the expected behavior.

"volatile" tells the compiler to make the access you gave, regardless of
anything else, and can be used to force unaligned reads and writes
(amongst other things).

>
> The above did work in Clang, however as far as I can tell it is behaving
> the same in this case as it did for volatile.
>
>
> One can also use a bunch of 8 and 16 byte memcpy operations, but as
> noted, this is slower than using 'volatile'.
>

>
>
> For the "generic" fallback, "getu32_le()" and friends can fall back to
> something like:
>   ((ptr)[0]|((ptr)[1]<<8)|((ptr)[2]<<16)|((ptr)[3]<<24))
>
> But, this results in a fairly massive drop in performance with MSVC.
>
> However, interestingly, GCC sees much less of a performance impact with
> this case.
>
>

I recommend playing in <https://godbolt.org> and trying different
combinations here - you can quickly compare the generated results for
different compilers, flags, and code.

>
> This sort of hackery may make a pretty big difference in the speed of an
> LZ decoder...
>

MitchAlsup wrote:
> On Friday, December 17, 2021 at 2:42:25 PM UTC-6, Terje Mathisen wrote:
>> I'll typically load 32 or 64 bits surrounding the target are, swap the
>> bytes if there's an endian change, then use regular shift & mask ops to
>> get at what I need.
> <
> We teach compilers to recognize << followed by >> and convert it into
> EXT instructions.
> We teach compilers to recognize & followed by << followed by &~
> followed by | and convert it into INS instructions (when appropriate).

I love those compiler micro-optimizations, they remove the need for
inline asm to handle these things.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Sunday, December 19, 2021 at 1:37:41 PM UTC-6, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Friday, December 17, 2021 at 2:42:25 PM UTC-6, Terje Mathisen wrote:
> >> I'll typically load 32 or 64 bits surrounding the target are, swap the
> >> bytes if there's an endian change, then use regular shift & mask ops to
> >> get at what I need.
> > <
> > We teach compilers to recognize << followed by >> and convert it into
> > EXT instructions.
> > We teach compilers to recognize & followed by << followed by &~
> > followed by | and convert it into INS instructions (when appropriate).
<
> I love those compiler micro-optimizations, they remove the need for
> inline asm to handle these things.
<
No reason to change the language or library interfaces to access easy
to identify idioms. I modified the M88K compiler to do these in 1984.
All it takes it recognizing a slightly more complicated pattern when
selecting code to be emitted. They typically, also, take a minor amount
of pressure off the register allocator.
<
> Terje
>
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On 12/19/2021 6:51 AM, David Brown wrote:
> On 18/12/2021 20:59, BGB wrote:
>> On 12/18/2021 11:26 AM, David Brown wrote:
>
>>> Compilers are free to change load and store orders on the assumption
>>> that the current thread of execution is the only thing that ever sees
>>> the accesses, unless you specifically say otherwise (with "volatile",
>>> atomics, or other methods).  More extreme movements are usually only
>>> done at higher levels of optimisation.  But if the code does not work
>>> correctly at -O2, you can be pretty confident that your code is wrong.
>>> Compiler bugs are not unheard of, of course, but user-code bugs are a
>>> /lot/ more common!
>>>
>>
>> This code is single threaded.
>>
>> The code in question depends on the use of misaligned and overlapping
>> loads and stores. As a result, changing the relative load/store order
>> will change the visible results.
>>
>
> Compilers assume you follow the rules for alignments - and then
> overlapping cannot possibly occur (for types smaller than the maximum
> alignment sizes). I don't think there is any way to construct objects
> that overlap while remaining within the strict rules of C (by which I
> mean, without invoking behaviour that is not defined by the standards.
> Particular compilers might support it, however).
>

The goal in this case was seeing what would work in the various compilers.

>>
>> I was trying to use pointers declared as:
>>   __attribute__((__may_alias__)) __attribute__((aligned(1)))
>>
>> But, this did not work in GCC.
>
> No, it will not. "may_alias" does not change alignment rules or allow
> overlapping. And the "aligned" attribute is for /increasing/ alignment,
> not reducing it. You might have better luck using a struct with the
> "packed" attribute - that's the only way in gcc to work with unaligned
> data in a fully defined way, I believe.
>

There is also the "memcpy" option, say:
inline uint32_t getu32_le(void *ptr)
{ uint32_t v;
memcpy(&v, ptr, 4);
return(v);
}

However, despite memcpy and inline being (often) essentially free in
GCC, the end result still ended up roughly 20% slower.

I guess maybe one could use a packed struct like, say:
typedef struct ui32ps_s __attribute__((packed)) {
uint32_t v;
}ui32ps_t;

#define getu32_le(ptr) (((ui32ps_t *)(ptr))->v)

Haven't tried this yet.

The attempt to use 'aligned(1)' was to see if it would behave like
'__unaligned' in some other compilers, but GCC has neither '__unaligned'
nor '__packed', ...

In BGBCC, I followed a rule similar to MSVC, in that either __unaligned
or __packed may allow for unaligned pointers (they are treated as
equivalent in this case); otherwise pointers are assumed to be natively
aligned.
This mostly effects things like whether the compiler is allowed to use
'MOV.X' operations in BJX2, since (unlike other loads/stores) MOV.X
imposes an 8B alignment restriction (*).

*: Mostly because allowing a freely aligned 128-bit load/store would
have a significant adverse effect on the cost of the L1 D$.

Namely one can imagine that each 128-bit L1 line is effectively divided
in half, and one uses a pair of these half-lines to implement an
unaligned load/store (selecting/inserting 64 bits from anywhere within
the 128-bit pair). In this case, the MOV.X operation simply skips this
select/insert stage and operates more directly on the pair of half-lines.

Loads will sign or zero extend the value as requested. Stores will copy
the high-order bits (for insert) from the 'select' results. A new pair
of half-lines will be generated by "reinserting" this 64-bit value back
in at the target pair (which retain any unchanged bits from the select
pair).

In cases where an unaligned 128b load/store is needed, it can be
implemented using a pair of MOV.Q instructions.

By extension, alignment is imposed in a few other areas (Reg: HW, ABI):
SP: 8, 16
PC: 2/4*, 2/4*, (*: 4 is required for inter-ISA branches with RVX)
GBR: 8, 16
TBR: 8, 16

>>
>> However, 'volatile' did give the expected behavior.
>
> "volatile" tells the compiler to make the access you gave, regardless of
> anything else, and can be used to force unaligned reads and writes
> (amongst other things).
>

Yeah.

Volatile seemed to be the winner in these tests.

>>
>> The above did work in Clang, however as far as I can tell it is behaving
>> the same in this case as it did for volatile.
>>
>>
>> One can also use a bunch of 8 and 16 byte memcpy operations, but as
>> noted, this is slower than using 'volatile'.
>>
>
>>
>>
>> For the "generic" fallback, "getu32_le()" and friends can fall back to
>> something like:
>>   ((ptr)[0]|((ptr)[1]<<8)|((ptr)[2]<<16)|((ptr)[3]<<24))
>>
>> But, this results in a fairly massive drop in performance with MSVC.
>>
>> However, interestingly, GCC sees much less of a performance impact with
>> this case.
>>
>>
>
> I recommend playing in <https://godbolt.org> and trying different
> combinations here - you can quickly compare the generated results for
> different compilers, flags, and code.
>

When I looked at it before, GCC was able to transform this pattern into
a plain memory load. MSVC does not seem to do this.

Still leaves an open mystery though of why it would be slower (in GCC)
than the use of 'volatile' or 'memcpy', since it should otherwise be
expected to be the same in this case.

But, in any case, the hit is a lot smaller than the one MSVC takes here.

>>
>> This sort of hackery may make a pretty big difference in the speed of an
>> LZ decoder...
>>
>

On 12/16/2021 11:28 PM, Thomas Koenig wrote:
> Ir. Hj. Othman bin Hj. Ahmad <othmana@gmail.com> schrieb:
>
>> HLL is very poor in bit manipulations. Better use a library for
>> these bit manipulations, so less need for optimization.
>
> Not really - calling a library function has a _lot_ of overhead,
> and what goes on in the library is hidden from the compiler. It is
> usually preferred for the compiler to emit highly optimized code.
>
> These days, compilers will might even recognize some standard
> idioms for certain bit manipulations and use a corresponding
> machine instruction, if available.

A compiler I used to use (it was for Fortran, but this functionality is
not Fortran specific) had a pseudo function named "Bits". It looked
like a function that accepted three arguments, a variable name and a
starting bit number and number of bits, both of which could be a
constant or an integer variable. One of its unique properties is that
it could also be used on the left hand side of an assignment statement.

This feature led to very clear, concise code, that the compiler didn't
have to go through a complex algorithms to recognize, and would generate
optimal, inline code. There was sort of a pragma that could optionally
generate checking code for out of range combinations of length and
starting bit number.

So, for example, the source code to move two bits starting at bit 3 of
variable B to starting at bit 4 of variable A would be

Bits (A, 2, 4) = Bits (B, 2, 3)

I always liked this feature, and used it a fair amount.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Monday, December 20, 2021 at 10:46:40 AM UTC-6, Stephen Fuld wrote:
> On 12/16/2021 11:28 PM, Thomas Koenig wrote:
> > Ir. Hj. Othman bin Hj. Ahmad <oth...@gmail.com> schrieb:
> >
> >> HLL is very poor in bit manipulations. Better use a library for
> >> these bit manipulations, so less need for optimization.
> >
> > Not really - calling a library function has a _lot_ of overhead,
> > and what goes on in the library is hidden from the compiler. It is
> > usually preferred for the compiler to emit highly optimized code.
> >
> > These days, compilers will might even recognize some standard
> > idioms for certain bit manipulations and use a corresponding
> > machine instruction, if available.
> A compiler I used to use (it was for Fortran, but this functionality is
> not Fortran specific) had a pseudo function named "Bits". It looked
> like a function that accepted three arguments, a variable name and a
> starting bit number and number of bits, both of which could be a
> constant or an integer variable. One of its unique properties is that
> it could also be used on the left hand side of an assignment statement.
>
> This feature led to very clear, concise code, that the compiler didn't
> have to go through a complex algorithms to recognize, and would generate
> optimal, inline code. There was sort of a pragma that could optionally
> generate checking code for out of range combinations of length and
> starting bit number.
>
> So, for example, the source code to move two bits starting at bit 3 of
> variable B to starting at bit 4 of variable A would be
>
> Bits (A, 2, 4) = Bits (B, 2, 3)
<
A more livable syntax might be:
<
A<2:4> = B<2:3>
>
> I always liked this feature, and used it a fair amount.
>
>
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

"Stephen Fuld" wrote in message news:spqc1d$oio$1@dont-email.me...

> A compiler I used to use (it was for Fortran, but this functionality is
> not Fortran specific) had a pseudo function named "Bits". It looked
> like a function that accepted three arguments, a variable name and a
> starting bit number and number of bits, both of which could be a
> constant or an integer variable. One of its unique properties is that
> it could also be used on the left hand side of an assignment statement.

> This feature led to very clear, concise code, that the compiler didn't
> have to go through a complex algorithms to recognize, and would generate
> optimal, inline code. There was sort of a pragma that could optionally
> generate checking code for out of range combinations of length and
> starting bit number.

> So, for example, the source code to move two bits starting at bit 3 of
> variable B to starting at bit 4 of variable A would be

> Bits (A, 2, 4) = Bits (B, 2, 3)

> I always liked this feature, and used it a fair amount.

Compare
https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
which are both elemental.

On 12/20/2021 9:25 AM, MitchAlsup wrote:
> On Monday, December 20, 2021 at 10:46:40 AM UTC-6, Stephen Fuld wrote:
>> On 12/16/2021 11:28 PM, Thomas Koenig wrote:
>>> Ir. Hj. Othman bin Hj. Ahmad <oth...@gmail.com> schrieb:
>>>
>>>> HLL is very poor in bit manipulations. Better use a library for
>>>> these bit manipulations, so less need for optimization.
>>>
>>> Not really - calling a library function has a _lot_ of overhead,
>>> and what goes on in the library is hidden from the compiler. It is
>>> usually preferred for the compiler to emit highly optimized code.
>>>
>>> These days, compilers will might even recognize some standard
>>> idioms for certain bit manipulations and use a corresponding
>>> machine instruction, if available.
>> A compiler I used to use (it was for Fortran, but this functionality is
>> not Fortran specific) had a pseudo function named "Bits". It looked
>> like a function that accepted three arguments, a variable name and a
>> starting bit number and number of bits, both of which could be a
>> constant or an integer variable. One of its unique properties is that
>> it could also be used on the left hand side of an assignment statement.
>>
>> This feature led to very clear, concise code, that the compiler didn't
>> have to go through a complex algorithms to recognize, and would generate
>> optimal, inline code. There was sort of a pragma that could optionally
>> generate checking code for out of range combinations of length and
>> starting bit number.
>>
>> So, for example, the source code to move two bits starting at bit 3 of
>> variable B to starting at bit 4 of variable A would be
>>
>> Bits (A, 2, 4) = Bits (B, 2, 3)
> <
> A more livable syntax might be:
> <
> A<2:4> = B<2:3>

I have no problem with that. The main point is to eliminate the need
for specifying some sequence of several shift and mask operations in the
source code. Both your suggestion and mine are clearer and less error
prone for the programmer.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On 12/20/2021 10:21 AM, James Van Buskirk wrote:
> "Stephen Fuld"  wrote in message news:spqc1d$oio$1@dont-email.me...
>> A compiler I used to use (it was for Fortran, but this functionality
>> is not Fortran specific) had a pseudo function named "Bits".  It
>> looked like a function that accepted three arguments, a variable name
>> and a starting bit number and number of bits, both of which could be a
>> constant or an integer variable.  One of its unique properties is that
>> it could also be used on the left hand side of an assignment statement.
>
>> This feature led to very clear, concise code, that the compiler didn't
>> have to go through a complex algorithms to recognize, and would
>> generate optimal, inline code.  There was sort of a pragma that could
>> optionally generate checking code for out of range combinations of
>> length and starting bit number.
>
>> So, for example, the source code to move two bits starting at bit 3 of
>> variable B to starting at bit 4 of variable A would be
>
>> Bits (A, 2, 4) = Bits (B, 2, 3)
>
>> I always liked this feature, and used it a fair amount.
>
> Compare
> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
> which are both elemental.

They seem essentially equivalent. It says that these came in with
Fortran 90. The compiler I was referring to had its roots in a
predecessor with a different name that dated back to at least the early
1970s. I am glad the idea became standardized.

I guess I should ask the question that given that C is probably used for
bit manipulation stuff at least as much as Fortran, how come the C
standard didn't pick up some equivalent?

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Monday, December 20, 2021 at 1:12:54 PM UTC-6, Stephen Fuld wrote:
> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
> > "Stephen Fuld" wrote in message news:spqc1d$oio$1...@dont-email.me...
> >> A compiler I used to use (it was for Fortran, but this functionality
> >> is not Fortran specific) had a pseudo function named "Bits". It
> >> looked like a function that accepted three arguments, a variable name
> >> and a starting bit number and number of bits, both of which could be a
> >> constant or an integer variable. One of its unique properties is that
> >> it could also be used on the left hand side of an assignment statement.
> >
> >> This feature led to very clear, concise code, that the compiler didn't
> >> have to go through a complex algorithms to recognize, and would
> >> generate optimal, inline code. There was sort of a pragma that could
> >> optionally generate checking code for out of range combinations of
> >> length and starting bit number.
> >
> >> So, for example, the source code to move two bits starting at bit 3 of
> >> variable B to starting at bit 4 of variable A would be
> >
> >> Bits (A, 2, 4) = Bits (B, 2, 3)
> >
> >> I always liked this feature, and used it a fair amount.
> >
> > Compare
> > https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
> > https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
> > which are both elemental.
> They seem essentially equivalent. It says that these came in with
> Fortran 90. The compiler I was referring to had its roots in a
> predecessor with a different name that dated back to at least the early
> 1970s. I am glad the idea became standardized.
>
> I guess I should ask the question that given that C is probably used for
> bit manipulation stuff at least as much as Fortran, how come the C
> standard didn't pick up some equivalent?
<
{Sarcasm mode=on}
<
Having a straightforward way to succinctly express the requirement is
<ahem> Not 'C'.
<
{Sarcasm mode=stays on}........
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

On 2021-12-20, MitchAlsup wrote:
> On Monday, December 20, 2021 at 1:12:54 PM UTC-6, Stephen Fuld wrote:
>> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
>>> "Stephen Fuld" wrote in message news:spqc1d$oio$1...@dont-email.me...
>>>> A compiler I used to use (it was for Fortran, but this functionality
>>>> is not Fortran specific) had a pseudo function named "Bits". It
>>>> looked like a function that accepted three arguments, a variable name
>>>> and a starting bit number and number of bits, both of which could be a
>>>> constant or an integer variable. One of its unique properties is that
>>>> it could also be used on the left hand side of an assignment statement.
>>>
>>>> This feature led to very clear, concise code, that the compiler didn't
>>>> have to go through a complex algorithms to recognize, and would
>>>> generate optimal, inline code. There was sort of a pragma that could
>>>> optionally generate checking code for out of range combinations of
>>>> length and starting bit number.
>>>
>>>> So, for example, the source code to move two bits starting at bit 3 of
>>>> variable B to starting at bit 4 of variable A would be
>>>
>>>> Bits (A, 2, 4) = Bits (B, 2, 3)
>>>
>>>> I always liked this feature, and used it a fair amount.
>>>
>>> Compare
>>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
>>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
>>> which are both elemental.
>> They seem essentially equivalent. It says that these came in with
>> Fortran 90. The compiler I was referring to had its roots in a
>> predecessor with a different name that dated back to at least the early
>> 1970s. I am glad the idea became standardized.
>>
>> I guess I should ask the question that given that C is probably used for
>> bit manipulation stuff at least as much as Fortran, how come the C
>> standard didn't pick up some equivalent?
> <
> {Sarcasm mode=on}
> <
> Having a straightforward way to succinctly express the requirement is
> <ahem> Not 'C'.
> <
> {Sarcasm mode=stays on}........

How about this quick hack in C++... ;-)

It compiles to bit field instructions on ARM:
https://godbolt.org/z/78K3s1cs1

#include <cstring>

// Helper struct.
template <unsigned POS, unsigned LEN, typename T>
struct ipos_helper {
T _1 : POS;
T x : LEN;
};

// Extract bit field.
template <unsigned POS, unsigned LEN, typename T>
T ipos(T x) {
ipos_helper<POS, LEN, T> helper;
static_assert(sizeof(helper) >= sizeof(T));
std::memcpy(&helper, &x, sizeof(T));
return helper.x;
}

unsigned test(unsigned num) {
return ipos<4, 9>(num);
}

/Marcus

MitchAlsup wrote:
> On Monday, December 20, 2021 at 1:12:54 PM UTC-6, Stephen Fuld wrote:
>> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
>>> Compare
>>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
>>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
>>> which are both elemental.
>> They seem essentially equivalent. It says that these came in with
>> Fortran 90. The compiler I was referring to had its roots in a
>> predecessor with a different name that dated back to at least the early
>> 1970s. I am glad the idea became standardized.
>>
>> I guess I should ask the question that given that C is probably used for
>> bit manipulation stuff at least as much as Fortran, how come the C
>> standard didn't pick up some equivalent?
> <
> {Sarcasm mode=on}
> <
> Having a straightforward way to succinctly express the requirement is
> <ahem> Not 'C'.
> <
> {Sarcasm mode=stays on}........

My guess would be that since this effectively requires a fixed bit
ordering within bytes/words, and we already had cpus numbering the bits
from the top as well as up from the bottom, this one was a non-starter
since it would penalize at least one of the alternatives?

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Mo 20 Dez 2021 at 08:46, Stephen Fuld <sfuld@alumni.cmu.edu.invalid> wrote:

> A compiler I used to use (it was for Fortran, but this functionality is
> not Fortran specific) had a pseudo function named "Bits". It looked
> like a function that accepted three arguments, a variable name and a
> starting bit number and number of bits, both of which could be a
> constant or an integer variable. One of its unique properties is that
> it could also be used on the left hand side of an assignment statement.
>
> This feature led to very clear, concise code, that the compiler didn't
> have to go through a complex algorithms to recognize, and would generate
> optimal, inline code. There was sort of a pragma that could optionally
> generate checking code for out of range combinations of length and
> starting bit number.
>
> So, for example, the source code to move two bits starting at bit 3 of
> variable B to starting at bit 4 of variable A would be
>
> Bits (A, 2, 4) = Bits (B, 2, 3)
>
> I always liked this feature, and used it a fair amount.

This reminds me of the ldb and dpb functions in Common Lisp:
(http://www.lispworks.com/documentation/HyperSpec/Body/f_dpb.htm
http://www.lispworks.com/documentation/HyperSpec/Body/f_ldb.htm)

'Andreas

On 12/21/2021 3:01 AM, Terje Mathisen wrote:
> MitchAlsup wrote:
>> On Monday, December 20, 2021 at 1:12:54 PM UTC-6, Stephen Fuld wrote:
>>> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
>>>> Compare
>>>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
>>>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
>>>> which are both elemental.
>>> They seem essentially equivalent. It says that these came in with
>>> Fortran 90. The compiler I was referring to had its roots in a
>>> predecessor with a different name that dated back to at least the early
>>> 1970s. I am glad the idea became standardized.
>>>
>>> I guess I should ask the question that given that C is probably used for
>>> bit manipulation stuff at least as much as Fortran, how come the C
>>> standard didn't pick up some equivalent?
>> <
>> {Sarcasm mode=on}
>> <
>> Having a straightforward way to succinctly express the requirement is
>> <ahem> Not 'C'.
>> <
>> {Sarcasm mode=stays on}........
>
> My guess would be that since this effectively requires a fixed bit
> ordering within bytes/words, and we already had cpus numbering the bits
> from the top as well as up from the bottom, this one was a non-starter
> since it would penalize at least one of the alternatives?

Could be. I think there are two issues here. Big/little where the
actual order in memory is different, and numbering conventions, where
only the names change. Coding a sequence of shifts and masks is also
not portable to big/little endian designs, etc. so this is no different.

As for the numbering conventions, one could have the compiler be
sensitive to different ordering conventions and change the meaning of
the arguments appropriately depending upon target architecture. This
would make coding for any particular architecture consistent with that
architecture's conventions, but probably doesn't help portability, and I
am not sure it is a good idea. But I am not sure that "hiding" the
differences under a sequence of shifts and masks is any better.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

Stephen Fuld wrote:
> On 12/21/2021 3:01 AM, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> On Monday, December 20, 2021 at 1:12:54 PM UTC-6, Stephen Fuld wrote:
>>>> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
>>>>> Compare
>>>>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
>>>>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
>>>>> which are both elemental.
>>>> They seem essentially equivalent. It says that these came in with
>>>> Fortran 90. The compiler I was referring to had its roots in a
>>>> predecessor with a different name that dated back to at least the early
>>>> 1970s. I am glad the idea became standardized.
>>>>
>>>> I guess I should ask the question that given that C is probably used
>>>> for
>>>> bit manipulation stuff at least as much as Fortran, how come the C
>>>> standard didn't pick up some equivalent?
>>> <
>>> {Sarcasm mode=on}
>>> <
>>> Having a straightforward way to succinctly express the requirement is
>>> <ahem> Not 'C'.
>>> <
>>> {Sarcasm mode=stays on}........
>>
>> My guess would be that since this effectively requires a fixed bit
>> ordering within bytes/words, and we already had cpus numbering the
>> bits from the top as well as up from the bottom, this one was a
>> non-starter since it would penalize at least one of the alternatives?
>
> Could be. I think there are two issues here. Big/little where the
> actual order in memory is different, and numbering conventions, where
> only the names change. Coding a sequence of shifts and masks is also
> not portable to big/little endian designs, etc. so this is no different.
>
> As for the numbering conventions, one could have the compiler be
> sensitive to different ordering conventions and change the meaning of
> the arguments appropriately depending upon target architecture. This
> would make coding for any particular architecture consistent with that
> architecture's conventions, but probably doesn't help portability, and I
> am not sure it is a good idea. But I am not sure that "hiding" the
> differences under a sequence of shifts and masks is any better.

In C the order in which bit fields in a struct are concatenated
is implementation dependent. It matters for unions.

In Verilog I think almost everything is little endian except,
strangely, the order of bit fields in a struct which is big endian.
(I find it strange because it is such a glaring wart that you'd think
someone would have noticed it during the language design phase.)

On Tuesday, December 21, 2021 at 10:44:04 AM UTC-6, EricP wrote:
> Stephen Fuld wrote:
> > On 12/21/2021 3:01 AM, Terje Mathisen wrote:
> >> MitchAlsup wrote:
> >>> On Monday, December 20, 2021 at 1:12:54 PM UTC-6, Stephen Fuld wrote:
> >>>> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
> >>>>> Compare
> >>>>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
> >>>>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
> >>>>> which are both elemental.
> >>>> They seem essentially equivalent. It says that these came in with
> >>>> Fortran 90. The compiler I was referring to had its roots in a
> >>>> predecessor with a different name that dated back to at least the early
> >>>> 1970s. I am glad the idea became standardized.
> >>>>
> >>>> I guess I should ask the question that given that C is probably used
> >>>> for
> >>>> bit manipulation stuff at least as much as Fortran, how come the C
> >>>> standard didn't pick up some equivalent?
> >>> <
> >>> {Sarcasm mode=on}
> >>> <
> >>> Having a straightforward way to succinctly express the requirement is
> >>> <ahem> Not 'C'.
> >>> <
> >>> {Sarcasm mode=stays on}........
> >>
> >> My guess would be that since this effectively requires a fixed bit
> >> ordering within bytes/words, and we already had cpus numbering the
> >> bits from the top as well as up from the bottom, this one was a
> >> non-starter since it would penalize at least one of the alternatives?
> >
> > Could be. I think there are two issues here. Big/little where the
> > actual order in memory is different, and numbering conventions, where
> > only the names change. Coding a sequence of shifts and masks is also
> > not portable to big/little endian designs, etc. so this is no different.
> >
> > As for the numbering conventions, one could have the compiler be
> > sensitive to different ordering conventions and change the meaning of
> > the arguments appropriately depending upon target architecture. This
> > would make coding for any particular architecture consistent with that
> > architecture's conventions, but probably doesn't help portability, and I
> > am not sure it is a good idea. But I am not sure that "hiding" the
> > differences under a sequence of shifts and masks is any better.
> In C the order in which bit fields in a struct are concatenated
> is implementation dependent. It matters for unions.
>
> In Verilog I think almost everything is little endian except,
> strangely, the order of bit fields in a struct which is big endian.
> (I find it strange because it is such a glaring wart that you'd think
> someone would have noticed it during the language design phase.)
<
Verilog is biEndian (or Endian Free).
<
One can write:
<
a[3:5] = b[5:3];
<
And the bits are reversed !
<
In Verilog bits are just wires (most of the time), wires can be taken in any order:
<
a[3:12] = (b[5:3],b[6:12]);
<
Which reverses 3 bits and copies 6 more. It really helps just to think of them as wires
and assignment as a wiring order.

MitchAlsup wrote:
> On Tuesday, December 21, 2021 at 10:44:04 AM UTC-6, EricP wrote:
>>
>> In Verilog I think almost everything is little endian except,
>> strangely, the order of bit fields in a struct which is big endian.
>> (I find it strange because it is such a glaring wart that you'd think
>> someone would have noticed it during the language design phase.)
> <
> Verilog is biEndian (or Endian Free).
> <
> One can write:
> <
> a[3:5] = b[5:3];
> <
> And the bits are reversed !
> <
> In Verilog bits are just wires (most of the time), wires can be taken in any order:
> <
> a[3:12] = (b[5:3],b[6:12]);
> <
> Which reverses 3 bits and copies 6 more. It really helps just to think of them as wires
> and assignment as a wiring order.

Certain things are hardwired to behave little endian.

Yes for a single field you can declare that the bits are named
from left-low to right-high, or left-high to right-low,
which is endian neutral.

However I got the impression that if you actually tried to use
big endian ordering that certain things would behave anomalously.
e.g. while bits may be named in big endian high to low order,
array elements are always numbered in little endian low to high order.
A unioned array the lowest index always accesses the lsb of an overlay,
irrespective of naming of element bits.

For example

typedef union packed
{
bit [0:7] vecA[10:1]; // 10 big endian bytes
bit vecB[80]; // 80 bits numbered [79:0]
} MyUnion;

that the lsb of vecA[1][7:7] would overlay the lsb of vecB[0].

Also while the fields of a struct are packed in left to right or
big endian order, the whole of a struct or union can be accessed
as a bit field with range [n-1:0] which is little endian order.

It looks to me that since the language shows a preference for
little endian that one should stick to it to avoid gotcha's.
And just watch out for the order of struct field packing.

On Tuesday, December 21, 2021 at 1:55:17 PM UTC-6, EricP wrote:
> MitchAlsup wrote:
> > On Tuesday, December 21, 2021 at 10:44:04 AM UTC-6, EricP wrote:
> >>
> >> In Verilog I think almost everything is little endian except,
> >> strangely, the order of bit fields in a struct which is big endian.
> >> (I find it strange because it is such a glaring wart that you'd think
> >> someone would have noticed it during the language design phase.)
> > <
> > Verilog is biEndian (or Endian Free).
> > <
> > One can write:
> > <
> > a[3:5] = b[5:3];
> > <
> > And the bits are reversed !
> > <
> > In Verilog bits are just wires (most of the time), wires can be taken in any order:
> > <
> > a[3:12] = (b[5:3],b[6:12]);
> > <
> > Which reverses 3 bits and copies 6 more. It really helps just to think of them as wires
> > and assignment as a wiring order.
> Certain things are hardwired to behave little endian.
>
> Yes for a single field you can declare that the bits are named
> from left-low to right-high, or left-high to right-low,
> which is endian neutral.
>
> However I got the impression that if you actually tried to use
> big endian ordering that certain things would behave anomalously.
> e.g. while bits may be named in big endian high to low order,
> array elements are always numbered in little endian low to high order.
> A unioned array the lowest index always accesses the lsb of an overlay,
> irrespective of naming of element bits.
>
> For example
>
> typedef union packed
> {
> bit [0:7] vecA[10:1]; // 10 big endian bytes
> bit vecB[80]; // 80 bits numbered [79:0]
> } MyUnion;
>
> that the lsb of vecA[1][7:7] would overlay the lsb of vecB[0].
>
> Also while the fields of a struct are packed in left to right or
> big endian order, the whole of a struct or union can be accessed
> as a bit field with range [n-1:0] which is little endian order.
>
> It looks to me that since the language shows a preference for
> little endian that one should stick to it to avoid gotcha's.
> And just watch out for the order of struct field packing.
<
Perhaps it is best said that Verilog is Endian neutral,
and that some things are more naturally expressed in Little Endian.

MitchAlsup wrote:
> On Tuesday, December 21, 2021 at 1:55:17 PM UTC-6, EricP wrote:
>> MitchAlsup wrote:
>>> On Tuesday, December 21, 2021 at 10:44:04 AM UTC-6, EricP wrote:
>>>> In Verilog I think almost everything is little endian except,
>>>> strangely, the order of bit fields in a struct which is big endian.
>>>> (I find it strange because it is such a glaring wart that you'd think
>>>> someone would have noticed it during the language design phase.)
>>> <
>>> Verilog is biEndian (or Endian Free).
>>> <
>>> One can write:
>>> <
>>> a[3:5] = b[5:3];
>>> <
>>> And the bits are reversed !
>>> <
>>> In Verilog bits are just wires (most of the time), wires can be taken in any order:
>>> <
>>> a[3:12] = (b[5:3],b[6:12]);
>>> <
>>> Which reverses 3 bits and copies 6 more. It really helps just to think of them as wires
>>> and assignment as a wiring order.
>> Certain things are hardwired to behave little endian.
>>
>> Yes for a single field you can declare that the bits are named
>> from left-low to right-high, or left-high to right-low,
>> which is endian neutral.
>>
>> However I got the impression that if you actually tried to use
>> big endian ordering that certain things would behave anomalously.
>> e.g. while bits may be named in big endian high to low order,
>> array elements are always numbered in little endian low to high order.
>> A unioned array the lowest index always accesses the lsb of an overlay,
>> irrespective of naming of element bits.
>>
>> For example
>>
>> typedef union packed
>> {
>> bit [0:7] vecA[10:1]; // 10 big endian bytes
>> bit vecB[80]; // 80 bits numbered [79:0]
>> } MyUnion;
>>
>> that the lsb of vecA[1][7:7] would overlay the lsb of vecB[0].
>>
>> Also while the fields of a struct are packed in left to right or
>> big endian order, the whole of a struct or union can be accessed
>> as a bit field with range [n-1:0] which is little endian order.
>>
>> It looks to me that since the language shows a preference for
>> little endian that one should stick to it to avoid gotcha's.
>> And just watch out for the order of struct field packing.
> <
> Perhaps it is best said that Verilog is Endian neutral,
> and that some things are more naturally expressed in Little Endian.

A more straight forward example:
a 16 bit halfword unioned onto a 2 byte array.
In Verilog array[0] overlays the least significant byte of the word as it
does on a little endian machine, irrespective of how the bits are numbered.

With LE bit numbering a bit address trivially chops into a
byte/halfword/word array index and bit offsett, to denote the same bit.
With BE bit numbering a bit address selects different bits
depending on whether it is a byte or half or word array index.
That is where the potential gotcha's creep in.

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:

> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
>
>> "Stephen Fuld" wrote in message news:spqc1d$oio$1@dont-email.me...
>>
>>> A compiler I used to use (it was for Fortran, but this
>>> functionality is not Fortran specific) had a pseudo function named
>>> "Bits". It looked like a function that accepted three arguments,
>>> a variable name and a starting bit number and number of bits, both
>>> of which could be a constant or an integer variable. One of its
>>> unique properties is that it could also be used on the left hand
>>> side of an assignment statement.
>>>
>>> This feature led to very clear, concise code, that the compiler
>>> didn't have to go through a complex algorithms to recognize, and
>>> would generate optimal, inline code. There was sort of a pragma
>>> that could optionally generate checking code for out of range
>>> combinations of length and starting bit number.
>>>
>>> So, for example, the source code to move two bits starting at bit
>>> 3 of variable B to starting at bit 4 of variable A would be
>>>
>>> Bits (A, 2, 4) = Bits (B, 2, 3)
>>>
>>> I always liked this feature, and used it a fair amount.
>>
>> Compare
>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
>> which are both elemental.
>
> They seem essentially equivalent. It says that these came in with
> Fortran 90. The compiler I was referring to had its roots in a
> predecessor with a different name that dated back to at least the
> early 1970s. I am glad the idea became standardized.
>
> I guess I should ask the question that given that C is probably used
> for bit manipulation stuff at least as much as Fortran, how come the
> C standard didn't pick up some equivalent?

Not necessarily an answer but an observation: in C no new language
feature is needed, because C has the C preprocessor. It isn't hard
to write a macro that does the necessary shifting and masking (and
these days compilers are mostly smart enough to recognize the common
patterns and translate them efficiently and in machine-specific
ways).

On 12/22/2021 12:24 PM, Tim Rentsch wrote:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>
>> On 12/20/2021 10:21 AM, James Van Buskirk wrote:
>>
>>> "Stephen Fuld" wrote in message news:spqc1d$oio$1@dont-email.me...
>>>
>>>> A compiler I used to use (it was for Fortran, but this
>>>> functionality is not Fortran specific) had a pseudo function named
>>>> "Bits". It looked like a function that accepted three arguments,
>>>> a variable name and a starting bit number and number of bits, both
>>>> of which could be a constant or an integer variable. One of its
>>>> unique properties is that it could also be used on the left hand
>>>> side of an assignment statement.
>>>>
>>>> This feature led to very clear, concise code, that the compiler
>>>> didn't have to go through a complex algorithms to recognize, and
>>>> would generate optimal, inline code. There was sort of a pragma
>>>> that could optionally generate checking code for out of range
>>>> combinations of length and starting bit number.
>>>>
>>>> So, for example, the source code to move two bits starting at bit
>>>> 3 of variable B to starting at bit 4 of variable A would be
>>>>
>>>> Bits (A, 2, 4) = Bits (B, 2, 3)
>>>>
>>>> I always liked this feature, and used it a fair amount.
>>>
>>> Compare
>>> https://gcc.gnu.org/onlinedocs/gfortran/IBITS.html#IBITS
>>> https://gcc.gnu.org/onlinedocs/gfortran/MVBITS.html#MVBITS
>>> which are both elemental.
>>
>> They seem essentially equivalent. It says that these came in with
>> Fortran 90. The compiler I was referring to had its roots in a
>> predecessor with a different name that dated back to at least the
>> early 1970s. I am glad the idea became standardized.
>>
>> I guess I should ask the question that given that C is probably used
>> for bit manipulation stuff at least as much as Fortran, how come the
>> C standard didn't pick up some equivalent?
>
> Not necessarily an answer but an observation: in C no new language
> feature is needed, because C has the C preprocessor. It isn't hard
> to write a macro that does the necessary shifting and masking (and
> these days compilers are mostly smart enough to recognize the common
> patterns and translate them efficiently and in machine-specific
> ways).

While you are right, of course, about the preprocessor, I guess it comes
down to me having a different philosophy of language design, than what
Mitch expressed in his (sarcastic) comment.

> Having a straightforward way to succinctly express the requirement is
> <ahem> Not 'C'.

The problem with the preprocessor approach is that everyone will code
their own macro, possibly with different syntax, so I have to learn what
you did, then if I move to a different project, what they did etc. That
is the beauty of a standard. (Unless you are talking about having the
preprocessor macro standardized.)

Compare with, for example, integer division. It is part of the
standard, even though fairly rarely used. If bit field extraction and
insertion are reasonably well used (and I am guessing they are - at
least as much as they are used in Fortran, though probably less than
division), then I feel they should be standardized to ease the
programmer's job.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

Le 23/12/2021 à 18:07, Stephen Fuld a écrit :
> Compare with, for example, integer division.  It is part of the
> standard, even though fairly rarely used.

Sorry, I'm not sure I got it? Integer division is rarely used in C? Can
you elaborate?

> If bit field extraction and
> insertion are reasonably well used (and I am guessing they are - at
> least as much as they are used in Fortran, though probably less than
> division), then I feel they should be standardized to ease the
> programmer's job.

It's probably up for debate, of course, like any new "feature" that
could be added to C. For instance, stdint was added to C99... but this
was a bit different: integer widths were mostly implementation-defined
before that. Standardizing things that are commonly used and rely on
implementation-defined stuff makes sense.

But "bit manipulation" in general is something that can be implemented,
off the top of my head, in a portable way, using existing operators,
without risking incorrect behavior if you use them properly. So adding
bit manipulation functions to the standard would not add tremendous
value. Sure it would marginally help developers, but as far as I've
seen, the process of adding a new feature in the C standard usually
implies that it can't be done portably otherwise. Again, extracting bits
can be done portably as far as I see it. (Don't hesitate to prove me
wrong with an example!)

On Thursday, December 23, 2021 at 1:08:39 PM UTC-6, Guillaume wrote:
> Le 23/12/2021 à 18:07, Stephen Fuld a écrit :
> > Compare with, for example, integer division. It is part of the
> > standard, even though fairly rarely used.
> Sorry, I'm not sure I got it? Integer division is rarely used in C? Can
> you elaborate?
> > If bit field extraction and
> > insertion are reasonably well used (and I am guessing they are - at
> > least as much as they are used in Fortran, though probably less than
> > division), then I feel they should be standardized to ease the
> > programmer's job.
> It's probably up for debate, of course, like any new "feature" that
> could be added to C. For instance, stdint was added to C99... but this
> was a bit different: integer widths were mostly implementation-defined
> before that. Standardizing things that are commonly used and rely on
> implementation-defined stuff makes sense.
>
> But "bit manipulation" in general is something that can be implemented,
> off the top of my head, in a portable way, using existing operators,
> without risking incorrect behavior if you use them properly. So adding
> bit manipulation functions to the standard would not add tremendous
> value. Sure it would marginally help developers, but as far as I've
> seen, the process of adding a new feature in the C standard usually
> implies that it can't be done portably otherwise. Again, extracting bits
> can be done portably as far as I see it. (Don't hesitate to prove me
> wrong with an example!)
<
We have to separate this into two (2) categories: static bit fields which
C already has, and dynamic bit fields which C does not have.
<
Thus, we have already taught the compilers how to recognize these patterns
and generate bit field codes. Static pattern recognition is easier than dynamic;
but if you can recognize the dynamic cases, you automatically recognize the
static. I first did this in 1983 for DENELCORE and I believe that others got there
before I did.
<
The only benefit to developers would be some kind of syntactic sugar to make
bit fields easier to specify::
<
a<3:17> = b<9:23>;
<
Macros seem to fail in that they cannot do syntactic sugar things.

MitchAlsup <MitchAlsup@aol.com> schrieb:

> The only benefit to developers would be some kind of syntactic sugar to make
> bit fields easier to specify::
><
> a<3:17> = b<9:23>;
><
> Macros seem to fail in that they cannot do syntactic sugar things.

Macros in C can be used either for syntactic sugar or for syntactic
cyanide.

The original Bourne shell is an example. I'll leave it up to
the reader to decide if the C source code

IF wdval==NL
THEN IF flg&NLFLG
THEN wdval=';'; chkpr(NL);
FI
ELIF i==0 ANDF (flg&MTFLG)==0
THEN synbad();
FI

is the former or the latter.

Le 23/12/2021 à 20:37, MitchAlsup a écrit :
> The only benefit to developers would be some kind of syntactic sugar to make
> bit fields easier to specify::
> <
> a<3:17> = b<9:23>;

Oh, I perfectly get that, and I agree this notation would be quite nice.

> Macros seem to fail in that they cannot do syntactic sugar things.

Not this kind, indeed. But the whole question regarding the standard is,
is it really worth it to make additions to it just for some syntactic
sugar? This is not the spirit of C.

But in that same vein, I would have a number of other notations I would
like to have in C. A lot more than just this. Thing is, who knows where
that would lead the language.