Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #123009 > unrolled thread

Recasting data as long ints and chars

Back to article view | Back to comp.lang.c

Contents

  Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-11-19 21:11 +0000
    Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-23 00:50 +0000
      Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-11-26 15:55 +0000
        Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-26 23:55 +0000
          Re: Recasting data as long ints and chars Spiros Bousbouras <spibou@gmail.com> - 2017-11-27 06:43 +0000
            Re: Recasting data as long ints and chars "Pascal J. Bourguignon" <pjb@informatimago.com> - 2017-11-27 09:26 +0100
              Re: Recasting data as long ints and chars Spiros Bousbouras <spibou@gmail.com> - 2017-11-27 08:50 +0000
              Re: Recasting data as long ints and chars "James R. Kuyper" <jameskuyper@verizon.net> - 2017-11-27 10:35 -0500
                Re: Recasting data as long ints and chars supercat@casperkitty.com - 2017-11-27 08:00 -0800
                Re: Recasting data as long ints and chars "Pascal J. Bourguignon" <pjb@informatimago.com> - 2017-11-27 23:49 +0100
                  Re: Recasting data as long ints and chars jameskuyper@verizon.net - 2017-11-27 15:56 -0800
              Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-15 12:45 -0800
            Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-27 15:08 +0000
          Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-11-27 14:55 +0000
            Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-27 15:51 +0000
              Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-11-28 17:13 +0000
                Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-29 01:07 +0000
                  Re: Recasting data as long ints and chars Spiros Bousbouras <spibou@gmail.com> - 2017-11-29 18:59 +0000
                    Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-30 00:53 +0000
                      Re: Recasting data as long ints and chars Keith Thompson <kst-u@mib.org> - 2017-11-29 17:01 -0800
                        Re: Recasting data as long ints and chars Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-11-30 11:40 +0000
                          Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-11-30 19:53 +0000
                Re: Recasting data as long ints and chars Spiros Bousbouras <spibou@gmail.com> - 2017-11-29 18:37 +0000
                  Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-11-30 22:38 +0000
                    Re: Recasting data as long ints and chars Spiros Bousbouras <spibou@gmail.com> - 2017-12-07 05:06 +0000
                      Re: Recasting data as long ints and chars supercat@casperkitty.com - 2017-12-07 07:51 -0800
                      Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2017-12-08 23:14 +0000
                        Re: Recasting data as long ints and chars supercat@casperkitty.com - 2017-12-12 16:19 -0800
                          Re: Recasting data as long ints and chars Keith Thompson <kst-u@mib.org> - 2017-12-12 17:10 -0800
                            Re: Recasting data as long ints and chars supercat@casperkitty.com - 2017-12-13 09:02 -0800
                              Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-15 12:39 -0800
                                Re: Recasting data as long ints and chars Robert Wessel <robertwessel2@yahoo.com> - 2017-12-15 17:39 -0600
                                  Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-15 15:52 -0800
                                    Re: Recasting data as long ints and chars Robert Wessel <robertwessel2@yahoo.com> - 2017-12-16 00:35 -0600
                                      Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-17 14:02 -0800
                                        Re: Recasting data as long ints and chars "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2017-12-17 15:15 -0800
                                          Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-17 18:47 -0800
                                      Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-17 14:09 -0800
                                      Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-17 14:19 -0800
                                      Re: Recasting data as long ints and chars herrmannsfeldt@gmail.com - 2017-12-17 14:45 -0800
                        Re: Recasting data as long ints and chars Spiros Bousbouras <spibou@gmail.com> - 2017-12-13 19:13 +0000
                          Re: Recasting data as long ints and chars James Harris <james.harris.1@gmail.com> - 2018-02-10 05:46 +0000

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#123632

Keith Thompson <kst-u@mib.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> Spiros Bousbouras <spibou@gmail.com> writes:
>>> On Wed, 29 Nov 2017 01:07:28 +0000
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>>>   unsigned nb = 0;
>>>>   unsigned U_ORDER = 0;
>>>> 
>>>> and loop setting
>>>> 
>>>>   (U_ORDER << CHAR_BIT) | nb++
>>>
>>> If  sizeof(unsigned) == 1    then   U_ORDER << CHAR_BIT
>>> is undefined behaviour.
>>
>> Why?
>
> Because CHAR_BIT (which would have to be at least 16) would be equal to
> the width of the left operand.

Ah, yes, thanks (and to Spiros Bousbouras).

> N1570 6.5.7p3:
<snip>

>> But that's a side issue.

Though this UB it's not an issue in the loop I was imagining (because
the loop won't run when there is only one byte), having to check that
made me spot another error: nb should be initialised 1.  I.e. I was
suggesting replacing the compile-time

  unsigned U_ORDER = 0x00010203;

with

  unsigned nb = 1;
  unsigned U_ORDER = 0;
  while (nb < sizeof U_ORDER)
      U_ORDER = (U_ORDER << CHAR_BIT) | nb++;

Of course padding bits can make this go wrong, but life is short...

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#123647

On 30/11/2017 11:40, Ben Bacarisse wrote:
> Keith Thompson <kst-u@mib.org> writes:
> 
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>> Spiros Bousbouras <spibou@gmail.com> writes:
>>>> On Wed, 29 Nov 2017 01:07:28 +0000
>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>>>>    unsigned nb = 0;
>>>>>    unsigned U_ORDER = 0;
>>>>>
>>>>> and loop setting
>>>>>
>>>>>    (U_ORDER << CHAR_BIT) | nb++
>>>>
>>>> If  sizeof(unsigned) == 1    then   U_ORDER << CHAR_BIT
>>>> is undefined behaviour.
>>>
>>> Why?
>>
>> Because CHAR_BIT (which would have to be at least 16) would be equal to
>> the width of the left operand.
> 
> Ah, yes, thanks (and to Spiros Bousbouras).
> 
>> N1570 6.5.7p3:
> <snip>
> 
>>> But that's a side issue.
> 
> Though this UB it's not an issue in the loop I was imagining (because
> the loop won't run when there is only one byte), having to check that
> made me spot another error: nb should be initialised 1.  I.e. I was
> suggesting replacing the compile-time
> 
>    unsigned U_ORDER = 0x00010203;
> 
> with
> 
>    unsigned nb = 1;
>    unsigned U_ORDER = 0;
>    while (nb < sizeof U_ORDER)
>        U_ORDER = (U_ORDER << CHAR_BIT) | nb++;
> 
> Of course padding bits can make this go wrong, but life is short...

Agreed. I think I've come to the conclusion that there is no easy way to 
do this kind of thing in most HLLs. (The split by bytes was the first 
and easy part!) No HLLs that I know of provide portable access to 
metadata about representations. And that itself is an interesting 
omission when /some/ applications do need that access.


-- 
James Harris

[toc] | [prev] | [next] | [standalone]

#123611

On Tue, 28 Nov 2017 17:13:00 +0000
James Harris <james.harris.1@gmail.com> wrote:
> But I am not sure that such an approach 
> would scale well and I wonder if there would be a more flexible way. To 
> illustrate, consider
> 
>    unsigned U_ORDER = 0x00010203;
>    unsigned char *p = (unsigned char *) &U_ORDER;
> 
> The idea would be that p[0] through p[3] would give the offsets of the 
> bytes of an unsigned int in descending order of significance, and that 
> it would work irrespective of endianness - big, little or anything else.

I'm not sure I understand. You seem to be saying that the sequence
<p[0] , p[1] , p[2] , p[3]>  gives "the offsets of the bytes of an unsigned
int in descending order of significance [...] irrespective of endianness".
But this is not correct. Imagine that  U_ORDER  is laid out in memory (moving
from lower to higher addresses) as
    0x03 0x00 0x01 0x02

Then p[0] has value 3 but the offset of the most significant byte is 1 not
3. On the other hand , if  <q[0] , q[1] , q[2] , q[3]>  is a permutation of
<0 , 1 , 2 , 3>  such that  p[q[0]] < p[q[1]] < p[q[2]] < p[q[3]]  then
<q[0] , q[1] , q[2] , q[3]>  has the property you require.

> But it has problems: it assumes sizeof(unsigned) is 4 and that CHAR_BIT 
> is 8. Hence it is not portable.
> 
> Signed ints would be harder. At least the byte with the sign would need 
> to be treated differently. That could be done with a simple mapping 
> function (possibly using xor or subtract operations) which would be 
> fine. But the code would need to adapt to how signed ints were laid out 
> in memory on different machines. And, again, that seems to be hard to do 
> portably.
> 
> I guess I am looking for a portable way for C datatypes to be treated as 
> a sequence of bytes, and hoping there would be some language support 
> (i.e. set of definitions in the C standards) for doing so.

The portable way is to access them as an array of  unsigned char .But you
want more than this ; you want an easy and portable way to obtain
arithmetical ordering properties from the individual bytes and that's what
causes complications. Do you want the solution to also work with floating
point numbers ?

> Although my 
> sort routine is not a radix sort it faces the same problems of 
> decomposing an arbitrary key into manageable chunks so I was thinking 
> that this kind of problem might have already been solved.
> 
> AIUI any C object apart from a bit field can be viewed as a sequence of 
> bytes but that only gets me part way to a portable approach to knowing 
> what is in each byte.

Perhaps it would help if you explained what the wider context is. From
what you've said so far you seem to want the usual mathematical ordering ,
at least when the usual integer types are concerned , but you're going about
it in a roundabout way where you want to access the object on a byte by
byte basis and use this to retrieve the mathematical ordering you would
get directly just by using the usual comparison operators of C.

> It seems like a simple requirement, but implementing it portably is 
> where it becomes difficult.

-- 
Who weight watches the Weight Watchers ?

[toc] | [prev] | [next] | [standalone]

#123659

On 29/11/2017 18:37, Spiros Bousbouras wrote:
> On Tue, 28 Nov 2017 17:13:00 +0000
> James Harris <james.harris.1@gmail.com> wrote:
>> But I am not sure that such an approach
>> would scale well and I wonder if there would be a more flexible way. To
>> illustrate, consider
>>
>>     unsigned U_ORDER = 0x00010203;
>>     unsigned char *p = (unsigned char *) &U_ORDER;
>>
>> The idea would be that p[0] through p[3] would give the offsets of the
>> bytes of an unsigned int in descending order of significance, and that
>> it would work irrespective of endianness - big, little or anything else.
> 
> I'm not sure I understand. You seem to be saying that the sequence
> <p[0] , p[1] , p[2] , p[3]>  gives "the offsets of the bytes of an unsigned
> int in descending order of significance [...] irrespective of endianness".
> But this is not correct. Imagine that  U_ORDER  is laid out in memory (moving
> from lower to higher addresses) as
>      0x03 0x00 0x01 0x02
> 
> Then p[0] has value 3 but the offset of the most significant byte is 1 not
> 3. On the other hand , if  <q[0] , q[1] , q[2] , q[3]>  is a permutation of
> <0 , 1 , 2 , 3>  such that  p[q[0]] < p[q[1]] < p[q[2]] < p[q[3]]  then
> <q[0] , q[1] , q[2] , q[3]>  has the property you require.

Yes, it might work for LE and BE machines but not middle-endian ones. 
However, it was not meant as a final solution but as something which 
would help illustrate the intention.

> 
>> But it has problems: it assumes sizeof(unsigned) is 4 and that CHAR_BIT
>> is 8. Hence it is not portable.
>>
>> Signed ints would be harder. At least the byte with the sign would need
>> to be treated differently. That could be done with a simple mapping
>> function (possibly using xor or subtract operations) which would be
>> fine. But the code would need to adapt to how signed ints were laid out
>> in memory on different machines. And, again, that seems to be hard to do
>> portably.
>>
>> I guess I am looking for a portable way for C datatypes to be treated as
>> a sequence of bytes, and hoping there would be some language support
>> (i.e. set of definitions in the C standards) for doing so.
> 
> The portable way is to access them as an array of  unsigned char .But you
> want more than this ; you want an easy and portable way to obtain
> arithmetical ordering properties from the individual bytes and that's what
> causes complications. Do you want the solution to also work with floating
> point numbers ?

I wasn't thinking about floats. There would be problems enough even with 
signed integers when they could be stored as 2's complement, 1's 
complement or possibly sign-and-magnitude. Even simple unsigned numbers 
are a bit of a challenge to do completely portably.

I was thinking that calling a routine for every comparison would be too 
slow but that I could avoid that by a "mapping" which made judicious use 
of operations like xor, and, sub. The sort time would be dominated by 
memory reads and writes so ALU ops shouldn't be a problem.

The sort routine has the following basic structure.

   while there are chunks left
     get info about the bit patterns of the current chunk    (A)
     iterate through the array sorting by this chunk    (B)
     recurse to sort each of the subsidiary parts
   end while

I explain that in order to point out that (B) is the inner loop and that 
calling a routine therein would probably be too slow (though I haven't 
tested it) but I could certainly call a routine in the outer loop at (A) 
without slowing the function significantly. In other words, point (A) 
could obtain values to use in ALU bit-twiddling operations in the inner 
loop at (B).

Because the sort goes through the key in chunks, it needs to get the 
chunks in the correct order - most to least significant - and needs to 
know the bit patterns therein. Or at least it needs to be able to map 
the native bit patterns to patterns that can be compared.

The chunks don't need to be bytes. In fact, the larger they are the 
better, but that can run into issues of alignment. But bytes may be a 
convenient way to think of the basic process.


> 
>> Although my
>> sort routine is not a radix sort it faces the same problems of
>> decomposing an arbitrary key into manageable chunks so I was thinking
>> that this kind of problem might have already been solved.
>>
>> AIUI any C object apart from a bit field can be viewed as a sequence of
>> bytes but that only gets me part way to a portable approach to knowing
>> what is in each byte.
> 
> Perhaps it would help if you explained what the wider context is. From
> what you've said so far you seem to want the usual mathematical ordering ,
> at least when the usual integer types are concerned , but you're going about
> it in a roundabout way where you want to access the object on a byte by
> byte basis and use this to retrieve the mathematical ordering you would
> get directly just by using the usual comparison operators of C.

Does the above pseudocode provide enough of the context? It's because 
the sort works by parts of a key that it needs to know the bit patterns 
of those parts, and to get the parts in the right order.

> 
>> It seems like a simple requirement, but implementing it portably is
>> where it becomes difficult.
> 


-- 
James Harris

[toc] | [prev] | [next] | [standalone]

#123968

On Thu, 30 Nov 2017 22:38:34 +0000
James Harris <james.harris.1@gmail.com> wrote:
> I was thinking that calling a routine for every comparison would be too 
> slow but that I could avoid that by a "mapping" which made judicious use 
> of operations like xor, and, sub. The sort time would be dominated by 
> memory reads and writes so ALU ops shouldn't be a problem.
> 
> The sort routine has the following basic structure.
> 
>    while there are chunks left
>      get info about the bit patterns of the current chunk    (A)
>      iterate through the array sorting by this chunk    (B)
>      recurse to sort each of the subsidiary parts
>    end while

I still don't understand why you need step A. Say you have

struct s1 {
    unsigned f1 ;
    long f2 ;
} ;

struct s2 {
    int f1 ;
    char f2 ;
}

struct key {
    struct s1 k1 ;
    struct s2 k2 ;
} ;

and the fields of the key from most significant to least significant are

k1.f2 , k2.f1 , k2.f2 , k1.f1 .Then the comparison function would be

int compare(struct key *key1 , struct key *key2) {
    if ((key1->k1).f2 > (key2->k1).f2) return 1 ;
    if ((key1->k1).f2 < (key2->k1).f2) return -1 ;

    if ((key1->k2).f1 > (key2->k2).f1) return 1 ;
    if ((key1->k2).f1 < (key2->k2).f1) return -1 ;

    if ((key1->k2).f2 > (key2->k2).f2) return 1 ;
    if ((key1->k2).f2 < (key2->k2).f2) return -1 ;

    if ((key1->k1).f1 > (key2->k1).f1) return 1 ;
    if ((key1->k1).f1 < (key2->k1).f1) return -1 ;

    return 0 ;
}

Why would you need to be concerned with bit patterns and endianness ?

> I explain that in order to point out that (B) is the inner loop and that 
> calling a routine therein would probably be too slow (though I haven't 
> tested it) but I could certainly call a routine in the outer loop at (A) 
> without slowing the function significantly. In other words, point (A) 
> could obtain values to use in ALU bit-twiddling operations in the inner 
> loop at (B).
> 
> Because the sort goes through the key in chunks, it needs to get the 
> chunks in the correct order - most to least significant - and needs to 
> know the bit patterns therein. Or at least it needs to be able to map 
> the native bit patterns to patterns that can be compared.
> 
> The chunks don't need to be bytes. In fact, the larger they are the 
> better, but that can run into issues of alignment.

Unless you go into explicit steps to lay out the keys in memory in some
unusual manner then they will be aligned.

> But bytes may be a 
> convenient way to think of the basic process.

[...]

> Does the above pseudocode provide enough of the context? It's because 
> the sort works by parts of a key that it needs to know the bit patterns 
> of those parts, and to get the parts in the right order.

It certainly needs to get the parts in the right order but why can't it
compare the parts directly ?

-- 
We take a pragmatic approach to how we classify languages into types like "embedded"
or "Web." Placement is based on typical use: For example, we are very impressed by
those brave souls who have written Web servers completely in assembly code, but we
don't categorize Assembly as a Web development language.
  Nick Diakopoulos and Stephen Cass
  http://spectrum.ieee.org/static/interactive-the-top-programming-languages-2016

[toc] | [prev] | [next] | [standalone]

#123987

On Wednesday, December 6, 2017 at 11:06:44 PM UTC-6, Spiros Bousbouras wrote:
> On Thu, 30 Nov 2017 22:38:34 +0000
> James Harris <james.harris.1@gmail.com> wrote:
> > The sort routine has the following basic structure.
> > 
> >    while there are chunks left
> >      get info about the bit patterns of the current chunk    (A)
> >      iterate through the array sorting by this chunk    (B)
> >      recurse to sort each of the subsidiary parts
> >    end while
> 
> I still don't understand why you need step A. Say you have
... a structure leading to the comparison function ...
> int compare(struct key *key1 , struct key *key2) {
>     if ((key1->k1).f2 > (key2->k1).f2) return 1 ;
>     if ((key1->k1).f2 < (key2->k1).f2) return -1 ;
> 
>     if ((key1->k2).f1 > (key2->k2).f1) return 1 ;
>     if ((key1->k2).f1 < (key2->k2).f1) return -1 ;
> 
>     if ((key1->k2).f2 > (key2->k2).f2) return 1 ;
>     if ((key1->k2).f2 < (key2->k2).f2) return -1 ;
> 
>     if ((key1->k1).f1 > (key2->k1).f1) return 1 ;
>     if ((key1->k1).f1 < (key2->k1).f1) return -1 ;
> 
>     return 0 ;
> }
> 
> Why would you need to be concerned with bit patterns and endianness ?

If the fields were smaller, e.g.

    struct foo {uint16_t k1,k2; };

with k1 as the primary key, then on a big-endian machine storing the struct
in a union such as:

    union compositeKey {
      struct foo {uint16_t k1,k2; };
      uint32_t asUint32;
    }

would allow elements to be compared using a uint32_t comparison rather
than having to compare the halves separately.  Even on little-endian
machines, rotating the asUint32 value by 16 bits and then doing the
comparison may be faster than doing separate checks for the primary
and secondary keys (doing things that way would likely improve performance
if many items had matching primary keys, but degrade performance if the
primary keys were mostly distinct; a programmer would likely know more
than a compiler about which distribution was more likely).

[toc] | [prev] | [next] | [standalone]

#124029

On 07/12/2017 05:06, Spiros Bousbouras wrote:
> On Thu, 30 Nov 2017 22:38:34 +0000
> James Harris <james.harris.1@gmail.com> wrote:
>> I was thinking that calling a routine for every comparison would be too
>> slow but that I could avoid that by a "mapping" which made judicious use
>> of operations like xor, and, sub. The sort time would be dominated by
>> memory reads and writes so ALU ops shouldn't be a problem.
>>
>> The sort routine has the following basic structure.
>>
>>     while there are chunks left
>>       get info about the bit patterns of the current chunk    (A)
>>       iterate through the array sorting by this chunk    (B)
>>       recurse to sort each of the subsidiary parts
>>     end while
> 
> I still don't understand why you need step A. Say you have
> 
> struct s1 {
>      unsigned f1 ;
>      long f2 ;
> } ;
> 
> struct s2 {
>      int f1 ;
>      char f2 ;
> }
> 
> struct key {
>      struct s1 k1 ;
>      struct s2 k2 ;
> } ;
> 
> and the fields of the key from most significant to least significant are
> 
> k1.f2 , k2.f1 , k2.f2 , k1.f1 .Then the comparison function would be
> 
> int compare(struct key *key1 , struct key *key2) {
>      if ((key1->k1).f2 > (key2->k1).f2) return 1 ;
>      if ((key1->k1).f2 < (key2->k1).f2) return -1 ;
> 
>      if ((key1->k2).f1 > (key2->k2).f1) return 1 ;
>      if ((key1->k2).f1 < (key2->k2).f1) return -1 ;
> 
>      if ((key1->k2).f2 > (key2->k2).f2) return 1 ;
>      if ((key1->k2).f2 < (key2->k2).f2) return -1 ;
> 
>      if ((key1->k1).f1 > (key2->k1).f1) return 1 ;
>      if ((key1->k1).f1 < (key2->k1).f1) return -1 ;
> 
>      return 0 ;
> }
> 
> Why would you need to be concerned with bit patterns and endianness ?

What you describe is a comparison sort. Mine is not like that. Rather, 
it looks at keys in chunks - similar to the way that is done in a radix 
sort.

https://en.wikipedia.org/wiki/Radix_sort

In fact, I could express the essential parts of the original query in 
terms of a radix sort, which should make it easier to understand what I 
was asking. To make a highly artificial scenario but one which 
illustrates the points, then, assume that:

* the query is about an MSD radix sort
* the MSD radix sort function uses 256 buckets for each pass, and 
therefore it examines keys a byte at a time and tallies them in an array 
which is indexed from 0 to 255
* we want to get it to sort an array of 16-bit signed ints on a machine 
where bytes are 8-bit.

The radix sort function would need to be told the offset of the 
most-significant 8-bits first, and that of the least-significant 8-bits 
second.

Question 1 is how in C portably to determine the offsets.

Question 2 is how to deal portably with the bit patterns of signed 
integers.


I accept that C might make not enough guarantees about how the bytes of 
signed integers are stored and therefore that there would be no portable 
way to do this.

> 
>> I explain that in order to point out that (B) is the inner loop and that
>> calling a routine therein would probably be too slow (though I haven't
>> tested it) but I could certainly call a routine in the outer loop at (A)
>> without slowing the function significantly. In other words, point (A)
>> could obtain values to use in ALU bit-twiddling operations in the inner
>> loop at (B).
>>
>> Because the sort goes through the key in chunks, it needs to get the
>> chunks in the correct order - most to least significant - and needs to
>> know the bit patterns therein. Or at least it needs to be able to map
>> the native bit patterns to patterns that can be compared.
>>
>> The chunks don't need to be bytes. In fact, the larger they are the
>> better, but that can run into issues of alignment.
> 
> Unless you go into explicit steps to lay out the keys in memory in some
> unusual manner then they will be aligned.

True. I might have to rewrite the sort into multiple routines - one for 
each C datatype - though it would still need to know how to adjust the 
bit patterns read from datatypes such as signed integers.

> 
>> But bytes may be a
>> convenient way to think of the basic process.
> 
> [...]
> 
>> Does the above pseudocode provide enough of the context? It's because
>> the sort works by parts of a key that it needs to know the bit patterns
>> of those parts, and to get the parts in the right order.
> 
> It certainly needs to get the parts in the right order but why can't it
> compare the parts directly ?

Please see above. Hopefully it's clearer now.


-- 
James Harris

[toc] | [prev] | [next] | [standalone]

#124256

On Friday, December 8, 2017 at 5:14:46 PM UTC-6, James Harris wrote:
> I accept that C might make not enough guarantees about how the bytes of 
> signed integers are stored and therefore that there would be no portable 
> way to do this.

The Standard makes no distinction between programs that will run
identically all conforming implementations where they do not run
afoul of translation limits (and may or may not be usable on any
actual non-contrived implementations), and those which should run
identically on all conforming implementations which are or ever
will be designed to be practical and useful (but may fail on
implementations which are contrived to be needlessly useless).

On practical implementations that support uint8_t and uint32_t,
setting a uint32_t to 0x03020100 will cause one bytes to be set to
the values 0, 1, 2, and 3, in LSB-first order.  The Standard may
not require such behavior, but the lack of a mandate almost
certainly stems from the facts that:

    1. On any kind of normal hardware, doing anything else would be
       stupid.  Since the Standard makes no effort to forbid low-quality
       implementations which are conforming but useless, it couldn't
       possibly be expected to forbid every stupid thing an obtuse
       compiler writer might do.

    2. Hardware design is outside the jurisdiction of the Standard, and
       if for some reason someone designed hardware which stores integers
       using some really weird bit ordering, having a compiler for that
       platform use such ordering might make more sense than doing anything
       else.

It would be absurd to suggest that the authors of the Standard intended to
imply that code should be regarded as "defective" if it can't handle
implementations that would arbitrarily permute the bits used to store its
integer types.

[toc] | [prev] | [next] | [standalone]

#124259

supercat@casperkitty.com writes:
[...]
> On practical implementations that support uint8_t and uint32_t,
> setting a uint32_t to 0x03020100 will cause one bytes to be set to
> the values 0, 1, 2, and 3, in LSB-first order.

I think what you mean is that the bit ordering within bytes is expected
to be the same as the bit ordering within a 32-bit word (though the
standard doesn't require that).

It's very easy to read what you wrote as an assertion that all practical
implementations are little-endian (and in fact that's how I initially
read it).

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#124292

On Tuesday, December 12, 2017 at 7:10:25 PM UTC-6, Keith Thompson wrote:
> supercat@casperkitty.com writes:
> [...]
> > On practical implementations that support uint8_t and uint32_t,
> > setting a uint32_t to 0x03020100 will cause one bytes to be set to
> > the values 0, 1, 2, and 3, in LSB-first order.
> 
> I think what you mean is that the bit ordering within bytes is expected
> to be the same as the bit ordering within a 32-bit word (though the
> standard doesn't require that).
> 
> It's very easy to read what you wrote as an assertion that all practical
> implementations are little-endian (and in fact that's how I initially
> read it).

Sorry--I meant that the LSB will receive the value 0, the byte which holds
bits 8-15 will receive the value 1, the next byte will receive the value 2,
and the final byte the value 3.  Thus, an LSB-first radix sort would work
by processing bytes at the offset which held zero, then the bytes which held
one, then two, then three.  Such an approach would work on a system using any
of the 24 possible permutations of bytes within a word, but not on one using
any of the 32!-24 other permutations of bits within a word.

[toc] | [prev] | [next] | [standalone]

#124367

On Wednesday, December 13, 2017 at 9:02:56 AM UTC-8, supe...@casperkitty.com wrote:
> On Tuesday, December 12, 2017 at 7:10:25 PM UTC-6, Keith Thompson wrote:

(snip)
> > I think what you mean is that the bit ordering within bytes is expected
> > to be the same as the bit ordering within a 32-bit word (though the
> > standard doesn't require that).

> > It's very easy to read what you wrote as an assertion that all practical
> > implementations are little-endian (and in fact that's how I initially
> > read it).

> Sorry--I meant that the LSB will receive the value 0, the byte which holds
> bits 8-15 will receive the value 1, the next byte will receive the value 2,
> and the final byte the value 3.  Thus, an LSB-first radix sort would work
> by processing bytes at the offset which held zero, then the bytes which held
> one, then two, then three.  Such an approach would work on a system using any
> of the 24 possible permutations of bytes within a word, but not on one using
> any of the 32!-24 other permutations of bits within a word.

Note that you have now applied bit numbering to data with unknown
ordering.

IBM, in the documentation for S/360, (which is big endian) uses 
big endian bit numbering order.  Yes, there are no bit addressed
operations, but you still have to read about how it works.
(There are machines with bit clear/set/test instructions, which
take a byte (or word) address, and bit within the word value.)


For S/360, the msb of a byte or register is numbered 0,
and the lsb for a (32 bit) register numbered 31.

z/Architecture extended it to 64 bits, including all the
registers.  The 32 bit register now have bits numbered 32
(for msb) and 63 (for lsb).  Even without bit addressing,
it is nice for the documentation to be consistent.

[toc] | [prev] | [next] | [standalone]

#124383

On Fri, 15 Dec 2017 12:39:35 -0800 (PST), herrmannsfeldt@gmail.com
wrote:

>On Wednesday, December 13, 2017 at 9:02:56 AM UTC-8, supe...@casperkitty.com wrote:
>> On Tuesday, December 12, 2017 at 7:10:25 PM UTC-6, Keith Thompson wrote:
>
>(snip)
>> > I think what you mean is that the bit ordering within bytes is expected
>> > to be the same as the bit ordering within a 32-bit word (though the
>> > standard doesn't require that).
>
>> > It's very easy to read what you wrote as an assertion that all practical
>> > implementations are little-endian (and in fact that's how I initially
>> > read it).
>
>> Sorry--I meant that the LSB will receive the value 0, the byte which holds
>> bits 8-15 will receive the value 1, the next byte will receive the value 2,
>> and the final byte the value 3.  Thus, an LSB-first radix sort would work
>> by processing bytes at the offset which held zero, then the bytes which held
>> one, then two, then three.  Such an approach would work on a system using any
>> of the 24 possible permutations of bytes within a word, but not on one using
>> any of the 32!-24 other permutations of bits within a word.
>
>Note that you have now applied bit numbering to data with unknown
>ordering.
>
>IBM, in the documentation for S/360, (which is big endian) uses 
>big endian bit numbering order.  Yes, there are no bit addressed
>operations, but you still have to read about how it works.
>(There are machines with bit clear/set/test instructions, which
>take a byte (or word) address, and bit within the word value.)
>
>
>For S/360, the msb of a byte or register is numbered 0,
>and the lsb for a (32 bit) register numbered 31.
>
>z/Architecture extended it to 64 bits, including all the
>registers.  The 32 bit register now have bits numbered 32
>(for msb) and 63 (for lsb).  Even without bit addressing,
>it is nice for the documentation to be consistent.


There are, however, instructions which address bits *now*.  For
example, the Find Leftmost One, and the Rotate Then And/Or/Xor
Selected Bits instructions.

Of course they use the usual S/360 bit numbering.

[toc] | [prev] | [next] | [standalone]

#124384

On Friday, December 15, 2017 at 3:39:01 PM UTC-8, robert...@yahoo.com wrote:

(snip)

> >IBM, in the documentation for S/360, (which is big endian) uses 
> >big endian bit numbering order.  Yes, there are no bit addressed
> >operations, but you still have to read about how it works.
> >(There are machines with bit clear/set/test instructions, which
> >take a byte (or word) address, and bit within the word value.)

> >For S/360, the msb of a byte or register is numbered 0,
> >and the lsb for a (32 bit) register numbered 31.

> >z/Architecture extended it to 64 bits, including all the
> >registers.  The 32 bit register now have bits numbered 32
> >(for msb) and 63 (for lsb).  Even without bit addressing,
> >it is nice for the documentation to be consistent.

> There are, however, instructions which address bits *now*.  For
> example, the Find Leftmost One, and the Rotate Then And/Or/Xor
> Selected Bits instructions.

> Of course they use the usual S/360 bit numbering.

I know though ESA/390 somewhat, but there are many more new 
instructions in z/ that I don't know.

They add them faster that I can learn about them.

I do know that there are some specifically for C programming,
that know about zero byte terminated strings. 

[toc] | [prev] | [next] | [standalone]

#124395

On Fri, 15 Dec 2017 15:52:41 -0800 (PST), herrmannsfeldt@gmail.com
wrote:

>On Friday, December 15, 2017 at 3:39:01 PM UTC-8, robert...@yahoo.com wrote:
>
>(snip)
>
>> >IBM, in the documentation for S/360, (which is big endian) uses 
>> >big endian bit numbering order.  Yes, there are no bit addressed
>> >operations, but you still have to read about how it works.
>> >(There are machines with bit clear/set/test instructions, which
>> >take a byte (or word) address, and bit within the word value.)
>
>> >For S/360, the msb of a byte or register is numbered 0,
>> >and the lsb for a (32 bit) register numbered 31.
>
>> >z/Architecture extended it to 64 bits, including all the
>> >registers.  The 32 bit register now have bits numbered 32
>> >(for msb) and 63 (for lsb).  Even without bit addressing,
>> >it is nice for the documentation to be consistent.
>
>> There are, however, instructions which address bits *now*.  For
>> example, the Find Leftmost One, and the Rotate Then And/Or/Xor
>> Selected Bits instructions.
>
>> Of course they use the usual S/360 bit numbering.
>
>I know though ESA/390 somewhat, but there are many more new 
>instructions in z/ that I don't know.
>
>They add them faster that I can learn about them.
>
>I do know that there are some specifically for C programming,
>that know about zero byte terminated strings. 


The 64-bit era has been particularly prolific.  It started with some
569 (documented) instructions on the z900, and the z14 is up to
something like 1190.

And that's not counting what are effectively hundreds of additional
instructions hidden under the Perform <Some Function> instructions,
almost most all of which postdate the z900.  The most conservative
count for Perform Floating Point Operation (PFPO), for example, yields
45 instructions.

Nor does that count include, as most of the other instructions in the
ISAs do, the many size variations in the vector instructions (for
example Vector Add, VA, is counted only as one, not five for
VAB/VAH/VAF/VAG/VAQ for the various element sizes).

And there are issues about how to count various options in many of the
new instructions. For example, many of the vector decimal instructions
have options for how signs are handled (force and input positive,
generate a x'f' instead of a x'c' for a positive sign), which are
reasonably just options.  On the other hand they also have an option
as to whether or not the condition code is set, which is getting much
closer to being a separate instruction.

For comparison, my circa 1981 S/370 Principle of Operations
(GA22-7000-7),  documents 204 instructions.  The circa 1964 S/360
manual (A22-6821-0) documents about 141.  FWIW the growth rate in the
instruction count is something like:

 1964 - 141
 1981 - 204  - 17yr, +63,  2.2%/yr
 2000 - 569  - 19yr, +365, 5.5%/yr
 2017 - 1190 - 17yr, +621, 4.4%/yr

Which implies that the explosion in the instruction count really
started with XA, not 64-bit mode.

Alternatively, estimating the current total to be nearer 1700, the
rate for the 2000-2017 interval is 6.7%/yr).  With that, I'll assume
another increase in the rate, and predict 7300 instructions in the ISA
in 2035.  (The preceding not to be taken too seriously).

[toc] | [prev] | [next] | [standalone]

#124434

On Friday, December 15, 2017 at 10:35:03 PM UTC-8, robert...@yahoo.com wrote:

(snip, I wrote)

> >They add them faster that I can learn about them.

(snip)

> The 64-bit era has been particularly prolific.  It started with some
> 569 (documented) instructions on the z900, and the z14 is up to
> something like 1190.

I have an actual paper copy of one edition of z/Architecture
Principles of Operation.  But they are available as PDF, too.

http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr009.pdf

is the 10th edition, from about 2012.

> And that's not counting what are effectively hundreds of additional
> instructions hidden under the Perform <Some Function> instructions,
> almost most all of which postdate the z900.  The most conservative
> count for Perform Floating Point Operation (PFPO), for example, yields
> 45 instructions.

(snip)

[toc] | [prev] | [next] | [standalone]

#124439

On 12/17/2017 2:02 PM, herrmannsfeldt@gmail.com wrote:
> On Friday, December 15, 2017 at 10:35:03 PM UTC-8, robert...@yahoo.com wrote:
> 
> (snip, I wrote)
> 
>>> They add them faster that I can learn about them.
> 
> (snip)
> 
>> The 64-bit era has been particularly prolific.  It started with some
>> 569 (documented) instructions on the z900, and the z14 is up to
>> something like 1190.
> 
> I have an actual paper copy of one edition of z/Architecture
> Principles of Operation.  But they are available as PDF, too.
> 
> http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr009.pdf

:^)

Imvvho, gotta love the Perform Locked Operation (PLO) instructions...

A-51 in the version you linked to

Pretty nice.

> is the 10th edition, from about 2012.
> 
>> And that's not counting what are effectively hundreds of additional
>> instructions hidden under the Perform <Some Function> instructions,
>> almost most all of which postdate the z900.  The most conservative
>> count for Perform Floating Point Operation (PFPO), for example, yields
>> 45 instructions.
> 
> (snip)
> 

[toc] | [prev] | [next] | [standalone]

#124442

On Sunday, December 17, 2017 at 3:15:24 PM UTC-8, Chris M. Thomasson wrote:

(snip, I wrote)

> > I have an actual paper copy of one edition of z/Architecture
> > Principles of Operation.  But they are available as PDF, too.

> > http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr009.pdf

> Imvvho, gotta love the Perform Locked Operation (PLO) instructions...

> A-51 in the version you linked to

The A appendix gives some examples on how to use the less obvious
instructions.

Some of my favorite are MVCIN (move inverse) which moves
(most people would call it copies) a string in reverse order.

Stories are that it is used for Hebrew text editing.

There are also CFC (Compare and Form Codeword) and UPT
(UPdate Tree) to implement a specific sort algorithm.
Stories are that these were added so that IBM could write
a faster sort program than some competitors, in part by not
announcing these instructions.  But now they are out.

MVCIN reminds me, that someone was asking why there is no C
library function to reverse (a copy of) a string?  Though
MVCIN is interesting, in that second operand addresses the end
of a string, instead of the beginning. 

[toc] | [prev] | [next] | [standalone]

#124435

On Friday, December 15, 2017 at 10:35:03 PM UTC-8, robert...@yahoo.com wrote:

(snip)

> The 64-bit era has been particularly prolific.  It started with some
> 569 (documented) instructions on the z900, and the z14 is up to
> something like 1190.

The Sept. 2017 edition is at: http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr011.pdf

1902 pages worth.  

I could load on onto my Nook, and read it that way.

[toc] | [prev] | [next] | [standalone]

#124436

On Friday, December 15, 2017 at 10:35:03 PM UTC-8, robert...@yahoo.com wrote:

(snip regarding instruction counts in S/360 successors)

> The 64-bit era has been particularly prolific.  It started with some
> 569 (documented) instructions on the z900, and the z14 is up to
> something like 1190.

In addition to instructions, other features are added, some
useful to C programmers.

One I just noticed is the "zero address detection" feature.

Some IBM systems allow fetch from page zero by user code, which
could make debugging some C programs harder.  This feature detects
some cases that might otherwise be hard to find. It should detect
most cases using a NULL pointer in C, even when the displacement
field of the instruction isn't zero. 

[toc] | [prev] | [next] | [standalone]

#124437

On Friday, December 15, 2017 at 10:35:03 PM UTC-8, robert...@yahoo.com wrote:

(snip)

> The 64-bit era has been particularly prolific.  It started with some
> 569 (documented) instructions on the z900, and the z14 is up to
> something like 1190.

And for C programmers, Search String, Move String, and Compare Logical String,
which are pretty much strlen, strcpy, and strcmp in one instruction.

(Actually, they are interruptible, so you need a conditional branch
back in case of condition code 3.)

And CUSE, Compare Until Substring Equal does most of strstr(),
though it might need the lengths of the strings first.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web