Countdown using unsigned in C

[jahboater]

Interesting. Does anyone have a C23 compiler? Because I think that is a breaking change.

For example this:

Code: Select all

int main()
{
    char a = 10;
    auto b = a;

    printf("sizeof a is %lu\n", sizeof(a));
    printf("sizeof b is %lu\n", sizeof(b));
}

creates b as an int with size 4 but surely if type inference is happening it would have to be char of size 1.

gcc -std=gnu2x prints:

Code: Select all

sizeof a is 1
sizeof b is 1

That's GCC version 13.2
The format for size_t is %zu by the way.

[Heater]

But not on my MacBook Pro:

Code: Select all

✗ gcc    -std=gnu2x -Wall -Wextra test.c
test.c:6:10: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
    auto b = a;
    ~~~~ ^
1 warning generated.
✗ ./a.out                               
sizeof a is 1
sizeof b is 4

Neither with clang.

[jahboater]

But not on my MacBook Pro:

Code: Select all

✗ gcc    -std=gnu2x -Wall -Wextra test.c
test.c:6:10: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
    auto b = a;
    ~~~~ ^
1 warning generated.
✗ ./a.out                               
sizeof a is 1
sizeof b is 4

Neither with clang.

What version is your GCC compiler? (gcc -v)
Mine is 13.2

[Heater]

Shoot. Turns out I have never installed GCC on my MacBook. The sneaky, devious machine runs clang instead:

Code: Select all

✗ gcc -v
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.5 (clang-1205.0.22.9)
Target: arm64-apple-darwin22.2.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

Anyway, pretty radical for the C standards guys to make such a breaking change.

[jahboater]

Anyway, pretty radical for the C standards guys to make such a breaking change.

Indeed.

But I have not used "auto" as a storage class specifier since I stopped using B, over 40 years ago
C++ "reused" the auto keyword some years ago.

[dsyleixa123]

as to auto, C++ does it this way, similar to old gcc ISO C, IIUC:

Code: Select all

#include <iostream>
using namespace std;

int main()
{
    char a = 10;
    auto b = a;

    cout<<"sizeof a is " << sizeof(a) << endl;
    cout<<"sizeof b is " << sizeof(b) << endl;

    auto c = 10;
    cout<<"BUT: sizeof c is " << sizeof(c) << endl;

}

Code: Select all

sizeof a is 1
sizeof b is 1
BUT: sizeof c is 4

OTOH, Apple always is high walls and holy gardens...

[jahboater]

Code: Select all

sizeof a is 1
sizeof b is 1
BUT: sizeof c is 4

Yes, that seems right.
Same as C.

[jojopi]

Because I think that is a breaking change.

Implicit int was actually removed in C99, so you have had two decades of mandatory diagnostics if you were using auto without a type.

GCC's diagnostic is not very good, however. It says "warning: type defaults to int" instead of "warning: ISO requires explicit type".

[ejolson]

Does that work if the array is zero length ?
I suspect not for various reasons

'Counting down to 0' in the problem statement implies a non zero length array, doesn't it?

I'll check with the head of the legal department and dog treats what down to 0 actually means.

When it's known the array length is non-zero, as in this case, it's a reasonable optimization to skip the first test. Does the optimizing compiler not omit the first test automatically with the original code? In fact, I'm a little surprised it doesn't unroll the loop entirely when there are only 3 or 4 entries.

Given the program

Code: Select all

#include <stdio.h>

int main(){
    static const char *x[]={ "bark","meow","woof","scratch" };
    for(size_t n=sizeof(x)/sizeof(x[0])-1;;--n){
        printf("%s ",x[n]);
        if(!n) break;
    }
    printf("\n");
}

after compiling with

Code: Select all

$ gcc -O3 -g -o rev4 rev4.c

the output from objdump -S is

Code: Select all

int main(){
 6c0:   a9be7bfd        stp     x29, x30, [sp, #-32]!
    static const char *x[]={ "bark","meow","woof","scratch" };
    for(size_t n=sizeof(x)/sizeof(x[0])-1;;--n){
        printf("%s ",x[n]);
 6c4:   90000001        adrp    x1, 0 <__abi_tag-0x278>
 6c8:   9121c021        add     x1, x1, #0x870
int main(){
 6cc:   910003fd        mov     x29, sp
 6d0:   f9000bf3        str     x19, [sp, #16]
        printf("%s ",x[n]);
 6d4:   90000013        adrp    x19, 0 <__abi_tag-0x278>
 6d8:   9121e273        add     x19, x19, #0x878
 6dc:   aa1303e0        mov     x0, x19
 6e0:   97ffffe4        bl      670 <printf@plt>
 6e4:   aa1303e0        mov     x0, x19
 6e8:   90000001        adrp    x1, 0 <__abi_tag-0x278>
 6ec:   91220021        add     x1, x1, #0x880
 6f0:   97ffffe0        bl      670 <printf@plt>
 6f4:   aa1303e0        mov     x0, x19
 6f8:   90000001        adrp    x1, 0 <__abi_tag-0x278>
 6fc:   91222021        add     x1, x1, #0x888
 700:   97ffffdc        bl      670 <printf@plt>
 704:   90000001        adrp    x1, 0 <__abi_tag-0x278>
 708:   91224021        add     x1, x1, #0x890
 70c:   aa1303e0        mov     x0, x19
 710:   97ffffd8        bl      670 <printf@plt>
        if(!n) break;
    }
    printf("\n");
 714:   52800140        mov     w0, #0xa                        // #10
 718:   97ffffda        bl      680 <putchar@plt>
}
 71c:   f9400bf3        ldr     x19, [sp, #16]
 720:   52800000        mov     w0, #0x0                        // #0
 724:   a8c27bfd        ldp     x29, x30, [sp], #32
 728:   d65f03c0        ret

This shows GCC version 12.2.0 unrolls the loop.

When the loop reads

Code: Select all

    for(size_t n=sizeof(x)/sizeof(x[0]);n;){
        --n;
        printf("%s ",x[n]);
    }

or

Code: Select all

    for(size_t n=sizeof(x)/sizeof(x[0]);n-->0;){
        printf("%s ",x[n]);
    }

or

Code: Select all

    for(size_t n=sizeof(x)/sizeof(x[0]);n>0;--n){
        printf("%s ",x[n-1]);
    }

the generated code is the same.

Moreover, after stripping the debug symbols the binaries are exactly the same size.

Code: Select all

$ strip rev?
$ ls -l rev?
-rwxr-xr-x 1 ejolson users 67592 Sep 16 21:06 rev1
-rwxr-xr-x 1 ejolson users 67592 Sep 16 21:06 rev2
-rwxr-xr-x 1 ejolson users 67592 Sep 16 21:06 rev3
-rwxr-xr-x 1 ejolson users 67592 Sep 16 21:06 rev4

Weirdly, however, the md5sums are different.

Code: Select all

$ md5sum rev?
15b1afb0dfbfc389dc974ec62808430a  rev1
ad12e40dd89409117a45ab9e9b486a8a  rev2
20657d43a5f43dcf4df62b226ca5ae58  rev3
d8071e3dbb3658222b872bf5fd87e074  rev4

Why are the md5sums different?

[ejolson]

Why are the md5sums different?

As shown by

Code: Select all

$ od -x rev1 >rev1.x
$ od -x rev4 >rev4.x
$ diff rev1.x rev4.x
39,40c39,40
< 0001140 4e47 0055 4b33 6659 12f5 c6bf 8930 7dc2
< 0001160 0541 447f 6b5f a086 0004 0000 0010 0000
---
> 0001140 4e47 0055 f571 c86c c694 9691 ee79 f98e
> 0001160 6e21 bbde 230a 3a86 0004 0000 0010 0000

the differences are very small.

[ejolson]

Why are the md5sums different?

As shown by

Code: Select all

$ od -x rev1 >rev1.x
$ od -x rev4 >rev4.x
$ diff rev1.x rev4.x
39,40c39,40
< 0001140 4e47 0055 4b33 6659 12f5 c6bf 8930 7dc2
< 0001160 0541 447f 6b5f a086 0004 0000 0010 0000
---
> 0001140 4e47 0055 f571 c86c c694 9691 ee79 f98e
> 0001160 6e21 bbde 230a 3a86 0004 0000 0010 0000

the differences are very small.

The same happens with clang.

Code: Select all

$ make
clang -O3 -g -o rev1 rev1.c
clang -O3 -g -o rev2 rev2.c
clang -O3 -g -o rev3 rev3.c
clang -O3 -g -o rev4 rev4.c
$ strip rev?
$ for i in rev?; do od -x $i >$i.x; done
$ diff rev1.x rev2.x
39,40c39,40
< 0001140 4e47 0055 771e 909b 4d31 65ad 0270 a3b7
< 0001160 c49c b579 6a7a 4eb4 0004 0000 0010 0000
---
> 0001140 4e47 0055 2339 4fdc 1fcb 4d59 4aa5 8c4c
> 0001160 001a 69c2 f979 0aff 0004 0000 0010 0000

I find it interesting that the differences are in exactly the same place. Fido's been barking for the last hour about telemetry, but I think the real problem is lack of dog treats.

[jojopi]

Code: Select all

diff -u <(readelf -a rev1) <(readelf -a rev2)
[…]
-    Build ID: 6c9201a82f0f2c08fd2e3d80cd95f3834ddb3247
+    Build ID: 5d64da06e6acbfb0c3503b0d32fc8aefcd2787ea

The Build ID is a sha1sum of something, and I think its main use is to verify whether a coredump belongs to a specific binary.

In this case it differs because the debug info was different, even though that was later stripped. If you compile without -g (and use the same source file name) I think you should get identical results.

[ejolson]

Code: Select all

diff -u <(readelf -a rev1) <(readelf -a rev2)
[…]
-    Build ID: 6c9201a82f0f2c08fd2e3d80cd95f3834ddb3247
+    Build ID: 5d64da06e6acbfb0c3503b0d32fc8aefcd2787ea

The Build ID is a sha1sum of something, and I think its main use is to verify whether a coredump belongs to a specific binary.

In this case it differs because the debug info was different, even though that was later stripped. If you compile without -g (and use the same source file name) I think you should get identical results.

Thank you! I'll check that.

[dbrion1]

What happens if one counts down with a step which is different of 1 (ex:step == 2; beginning at odd number say 23, 21, 19 ...1;
termination condition is not n == 0 -index never reaches zero-)

[radiolistener]

What happens if one counts down with a step which is different of 1 (ex:step == 2; beginning at odd number say 23, 21, 19 ...1;
termination condition is not n == 0 -index never reaches zero-)

if you use unsigned int and using step 2 and value 1, the result will be 1 - 2 = UINT_MAX - (2-1) = UINT_MAX - 1

[dbrion1]

if you use unsigned int and using step 2 and value 1, the result will be 1 - 2 = UINT_MAX - (2-1) = UINT_MAX - 1

Well, with size_t type, and an arbitrary STEP (but for last indice ==1) result will be SIZE_MAX - (STEP - 1) as the value for loop termination; More generally, ivalue for loop iteration will be SIZE _MAX - (STEP - LAST_INDEX)

https://stackoverflow.com/questions/225 ... -of-size-t

[ejolson]

if you use unsigned int and using step 2 and value 1, the result will be 1 - 2 = UINT_MAX - (2-1) = UINT_MAX - 1

Well, with size_t type, and an arbitrary STEP (but for last indice ==1) result will be MAX_SIZE - (STEP - 1) as the value for loop termination; More generally, ivalue for loop iteration will be MAX_SIZE - (STEP - LAST_INDEX)

Instead, how about

Code: Select all

    for(unsigned int n=23;n<=23;n-=2){
        printf("%d ",n);
    }
    printf("\n");

That doesn't depend on MAX_SIZE and the test makes sure the value of n is in a sensible range which may be safer when it's used for indexing. Even so, the dog developer still doesn't like letting the hardware wrap around. I think it throws an exception on the BARK™ when running Fido Basic.

[Heater]

Yeah but then we are back to using int to index the array which does not work for large arrays that need size_t indices.

[ejolson]

Yeah but then we are back to using int to index the array which does not work for large arrays that need size_t indices.

In my opinion the reason unsigned should be used for indexing is because the C compiler will remove sanity checks on the range of signed integer values when the optimizer is turned on.

[dbrion1]

Instead, how about

Code: Select all

for(unsigned int n=23;n<=23;n-=2){
printf("%d ",n);
}
printf("\n");

That doesn't depend on MAX_SIZE and the test makes sure the value of n is in a sensible range which may be safer when it's used for indexing. Even so, the dog developer still doesn't like letting the hardware wrap around. I think it throws an exception on the BARK™ when running Fido Basic.

Well, I did not like this solution...(sensible ranges may become ... tiny ranges according to Moore's law; one just has to wait 30/40 more years)... and playing with underflows seems rather funny...

[Heater]

We don't need to wait decades for Moore's law.

The int is only able to get to 2 billion or so, the unsigned int 4 billion or so. That is not even enough to number every human on the planet. It's tiny.

[jahboater]

Yeah but then we are back to using int to index the array which does not work for large arrays that need size_t indices.

In my opinion the reason unsigned should be used for indexing is because the C compiler will remove sanity checks on the range of signed integer values when the optimizer is turned on.

size_t is always unsigned ...

Optimizer exploitation of signed integer overflow undefined behavior is a thing of the past now (with C23).

[tttapa]

Optimizer exploitation of signed integer overflow undefined behavior is a thing of the past now (with C23).

This is not correct.
C23 only defines the representation of signed integers to be two's complement. Signed integer overflow is still undefined behavior.

Note that the modulo 2ⁿ behavior of unsigned integers sometimes comes at a performance cost. Here's an example from Bzip where using 32-bit unsigned integers as array indices caused a significant slowdown on 64-bit machines: https://youtu.be/yG1OZ69H_-o?t=2358

[jahboater]

Optimizer exploitation of signed integer overflow undefined behavior is a thing of the past now (with C23).

C23 only defines the representation of signed integers to be two's complement. Signed integer overflow is still undefined behavior.

Where did you see this?
I searched annex J.2 and could not see it (but I may have missed it, there is so much there now!)

Now that there is only one single representation of signed integers, then overflow can only happen in one way ...

[tttapa]

Where did you see this?
I searched annex J.2 and could not see it (but I may have missed it, there is so much there now!)

C23 did not alter 6.5.5 which states:

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not
mathematically defined or not in the range of representable values for its type), the behavior is
undefined.

Now that there is only one single representation of signed integers, then overflow can only happen in one way ...

Ever since two's complement machines took over, not defining integer overflow has been a matter of optimization, not of representation. See e.g. the link I posted in my previous reply.