Chocolate Strife: A_FireSigil

I was looking at chocolate strife's source code, in p_pspr.c, function A_FireSigil() computes angle_t an as a right shift of player's pitch >> ANGLETOFINESHIFT. This shound always be 0, since pitch varies from -110 to 90... or do I miss something???

        // mega blast
    case 4:
        mo = P_SpawnPlayerMissile(player->mo, MT_SIGIL_E_SHOT);
        mo->health = -1;
        if(!linetarget)
        {
            an = player->pitch >> ANGLETOFINESHIFT;
            mo->momz += FixedMul(finesine[an], mo->info->speed); 
        }
        break;

It looks like the code mistakenly assumes that 'pitch' is an angle_t. If that was the case it would make sense to do a right shift. But as it isn't, that's wrong.
Whether that's a Chocolate Strife bug or just accurate Vanilla behavior, I'm not sure.

At the very least we probably shouldn't be doing bitshifts of negative numbers as that's platform dependent behaviour.

fraggle said:

At the very least we probably shouldn't be doing bitshifts of negative numbers as that's platform dependent behaviour.

Yes, it's a common error to assume that >>1 is the same as /2
(Think about -1 as an integer).

In Java, shifting a negative integer to the right is defined:

8 >> 1 = 4
-8 >> 1 = -4
-8 >>> 1 = 2147483644

>> is ishr, while >>> is iushr.

ishr

Both value1 and value2 must be of type int. The values are popped
from the operand stack. An int result is calculated by shifting
value1 right by s bit positions, with sign extension, where s is the
value of the low 5 bits of value2. The result is pushed onto the
operand stack.

You could always have this in C:

#include <stdint.h>
#include <stdio.h>
#include <signal.h>
#include <stdlib.h>
#include <inttypes.h>

int32_t shiftRight(int32_t __v, int32_t __sh)
{
    // Negative and above size is undefined
    if (__sh < INT32_C(0) || __sh > INT32_C(31))
    {
        fprintf(stderr, "Invalid shift amount: %"PRId32"\n", __sh);
        exit(EXIT_FAILURE);
        return 0;
    }
    
    // Positive uses standard shift
    else if (__v >= INT32_C(0))
        return __v >> __sh;
    
    // Negative requires sign extension
    else
        return (((uint32_t)__v) >> ((uint32_t)__sh)) |
            (UINT32_C(0xFFFFFFFF) << (UINT32_C(32) - __sh));
}

int main(int __argc, char** __argv)
{
    int32_t v[2];
    int i;
    
    // Not enough arguments
    if (__argc <= 2)
    {
        fprintf(stderr, "Usage: %s decimal_value decimal_shift\n", __argv[0]);
        return EXIT_FAILURE;
    }
    
    // Decode integers
    for (i = 1; i <= 2; i++)
        if (sscanf(__argv[i], "%"PRId32, &v[i - 1]) == EOF)
        {
            fprintf(stderr, "The argument '%s' is not a decimal integer.\n",
                __argv[i]);
            return EXIT_FAILURE;
        }
    
    // Show the result
    fprintf(stdout, "%3"PRId32" >> %2"PRId32": %"PRId32"\n",
        v[0], v[1], shiftRight(v[0], v[1]));
    
    // Ok
    return EXIT_SUCCESS;
}

Chocolate Doom isn't written in Java. Your proposed solution is excessively overcomplicated.

fraggle said:

...Whether that's a Chocolate Strife bug or just accurate Vanilla behavior, I'm not sure...

As in almost all of the times our thoroughness has been questioned, we implemented the code dutifully. Examine the below. Feel free to change it, but be sure that you are not altering the behavior. The treatment of >> on x86 must be fully maintained by any replacement logic used.

cseg01:0002785D loc_2785D:                              ; CODE XREF: A_FireSigil+41j
cseg01:0002785D                                         ; DATA XREF: cseg01:off_27650o
cseg01:0002785D                 mov     edx, 54h ; 'T'  ; jumptable 000276A5 case 4
cseg01:00027862                 mov     eax, [esi+player_t.mo] ; a1
cseg01:00027864
cseg01:00027864 loc_27864:
cseg01:00027864                 call    P_SpawnPlayerMissile
cseg01:00027869                 mov     edx, linetarget
cseg01:0002786F                 mov     ecx, eax
cseg01:00027871                 mov     [eax+mobj_t.health], 0FFFFFFFFh
cseg01:00027878                 test    edx, edx
cseg01:0002787A                 jnz     short loc_27898 ; default
cseg01:0002787C                 mov     eax, [esi+player_t.pitch]
cseg01:0002787F                 shr     eax, 19
cseg01:00027882                 mov     ebx, finesine[eax*4]
cseg01:00027889                 mov     eax, [ecx+mobj_t.info]
cseg01:0002788C                 mov     eax, [eax+mobjinfo_t.speed]
cseg01:0002788F                 imul    ebx
cseg01:00027891                 shrd    eax, edx, 10h
cseg01:00027895                 add     [ecx+mobj_t.momz], eax
cseg01:00027898
cseg01:00027898 loc_27898:                              ; CODE XREF: A_FireSigil+3Bj
cseg01:00027898                                         ; A_FireSigil+216j
cseg01:00027898                 pop     ebp             ; default
cseg01:00027899                 pop     edi
cseg01:0002789A                 pop     esi
cseg01:0002789B                 pop     ecx
cseg01:0002789C                 pop     ebx
cseg01:0002789D                 retn

    case 4:
      v7 = (mobj_t *)P_SpawnPlayerMissile((mobj_t *)v2->mo, MT_SIGIL_E_SHOT);
      v26 = linetarget;
      v7->health = -1;
      if ( !v26 )
        v7->momz += (unsigned __int64)(finesine[(unsigned int)v2->pitch >> 19] * *(_DWORD *)(v7->info + 64)) >> 16;
      break;

Quasar said:

        v7->momz += (unsigned __int64)(finesine[(unsigned int)v2->pitch >> 19] * *(_DWORD *)(v7->info + 64)) >> 16;

So, this correctly translates to

mo->momz += 0;

right?

fabian said:

So, this correctly translates to

mo->momz += 0;

right?

No, it translates to

mo->momz += FixedMul(finesine[0], mo->info->speed)

finesine[0] does not equal 0

jval said:

finesine[0] does not equal 0

Oh, indeed it's 25. o_O

fabian said:

So, this correctly translates to

mo->momz += 0;

right?

Don't know where you're getting that idea that it will be constant zero. The range of player_t::pitch is from +90 to -110. In the case of a negative number, shr is logical shift right. -110 is 11111111111111111111111110010010 binary; shr 19 on that value results in 1111111111111 binary, or 8191 decimal.

This is why I sounded irritated in my initial post. Please fully understand what you are doing, at a machine instruction level, before you mess with this stuff.

Sorry, I was previously confused about the right shifts - in this case shr is definitely what is wanted.

Quasar said:

Don't know where you're getting that idea that it will be constant zero. The range of player_t::pitch is from +90 to -110. In the case of a negative number, shr is logical shift right. -110 is 11111111111111111111111110010010 binary; shr 19 on that value results in 1111111111111 binary, or 8191 decimal.

Okay, but I think you did make a mistake. Here's the line in question again:

            an = player->pitch >> ANGLETOFINESHIFT;

'an' is an angle_t (unsigned int) and player->pitch is a signed int. This compares to the line you quote, which is:

        v7->momz += (unsigned __int64)(finesine[(unsigned int)v2->pitch >> 19] * *(_DWORD *)(v7->info + 64)) >> 16;

But notice the (unsigned int) cast binds to v2->pitch, not the whole resulting expression. So what you really mean is:

            an = (unsigned int) player->pitch >> ANGLETOFINESHIFT;

Just to be sure I checked out the gcc disassembly and sure enough:

    case 4:
        mo = P_SpawnPlayerMissile(player->mo, MT_SIGIL_E_SHOT);
        mo->health = -1;
        if(!linetarget)
        {
            an = player->pitch >> ANGLETOFINESHIFT;
    10b6:       8b 43 58                mov    0x58(%rbx),%eax
            mo->momz += FixedMul(finesine[an], mo->info->speed); 
    10b9:       c1 f8 13                sar    $0x13,%eax
    10bc:       8b 3c 85 00 00 00 00    mov    0x0(,%rax,4),%edi
    10c3:       e8 00 00 00 00          callq  10c8 
    10c8:       41 01 c4                add    %eax,%r12d
    10cb:       44 89 65 78             mov    %r12d,0x78(%rbp)
    10cf:       e9 4e ff ff ff          jmpq   1022 
    10d4:       0f 1f 40 00             nopl   0x0(%rax)
        mo->target = player->mo;
        break;

sar is arithmetic shift right, which differs from shr in how it handles shifts of signed numbers.

Right shifting a signed value is undefined and different compilers seem to behave differently - gcc applies a sar while Clang uses shr I believe. It may be that MSVC does the same as Clang so the bug was missed.

Does code generation change for that specific shift if `an` were to become signed?

Right shift is undefined on negative signed integers because representation of a negative value must be one of the following (and only one):

• Two's complement (-14 == 0xFFF2)
  
• One's complement (-14 == 0xFFF1)
  
• Upper most bit is the sign bit (-14 = 0x800E)
  

Anyone would probably have an easy time to find at least one statement in C/C++ based source ports which rely on a two's complement number system.

Literally no computer hardware exists nowadays that doesn't use two's complement arithmetic. Please stop trying to derail the thread.

On PowerPC, GCC and clang generate the same code (more or less) when it comes to a signed value being right shifted. When signed it performs srawi (Shift Right Algebraic Word Immediate), which is a sign extended shift. Casting pitch to unsigned results in rlwinm (Rotate Left Word Immediate then Mask Insert), which with the given operands results in effectively a zero-extended right shift.

GCC: ** = Removed loading of the pitch value from the structure in memory.

            an = player->pitch >> ANGLETOFINESHIFT;
--- snipped** ---
    27fc:       7c 00 9e 70     srawi   r0,r0,19

            an = (unsigned int)player->pitch >> ANGLETOFINESHIFT;
--- snipped** ---
    27fc:       54 00 6c fe     rlwinm  r0,r0,13,19,31

Clang:

            an = player->pitch >> ANGLETOFINESHIFT;
    2040:       7c 63 9e 70     srawi   r3,r3,19

            an = (unsigned int)player->pitch >> ANGLETOFINESHIFT;
    2040:       54 65 6c fe     rlwinm  r5,r3,13,19,31

GCC at least appears to be consistent across two platforms.

-----

fraggle said:

Literally no computer hardware exists nowadays that doesn't use two's complement arithmetic. Please stop trying to derail the thread.

If you believe I am trying to derail threads, you are incorrect. If I was purposefully derailing a thread I would not be talking about the C standard at all and would be talking about stuff completely way off topic such as the names of colors used in the pixels of FLAT19.

Two's complement is pretty much a defacto standard, however businesses prefer to use ancient hardware because upgrading is "too expensive".

Quasar said:

Don't know where you're getting that idea that it will be constant zero. The range of player_t::pitch is from +90 to -110. In the case of a negative number, shr is logical shift right. -110 is 11111111111111111111111110010010 binary; shr 19 on that value results in 1111111111111 binary, or 8191 decimal.

First and last items of finesine table, so elegant o_O

fraggle said:

Sorry, I was previously confused about the right shifts - in this case shr is definitely what is wanted.

Okay, but I think you did make a mistake. Here's the line in question again:

            an = player->pitch >> ANGLETOFINESHIFT;

'an' is an angle_t (unsigned int) and player->pitch is a signed int. This compares to the line you quote, which is:

        v7->momz += (unsigned __int64)(finesine[(unsigned int)v2->pitch >> 19] * *(_DWORD *)(v7->info + 64)) >> 16;

But notice the (unsigned int) cast binds to v2->pitch, not the whole resulting expression. So what you really mean is:

            an = (unsigned int) player->pitch >> ANGLETOFINESHIFT;

Just to be sure I checked out the gcc disassembly and sure enough:

    case 4:
        mo = P_SpawnPlayerMissile(player->mo, MT_SIGIL_E_SHOT);
        mo->health = -1;
        if(!linetarget)
        {
            an = player->pitch >> ANGLETOFINESHIFT;
    10b6:       8b 43 58                mov    0x58(%rbx),%eax
            mo->momz += FixedMul(finesine[an], mo->info->speed); 
    10b9:       c1 f8 13                sar    $0x13,%eax
    10bc:       8b 3c 85 00 00 00 00    mov    0x0(,%rax,4),%edi
    10c3:       e8 00 00 00 00          callq  10c8 <A_FireSigil+0x148>
    10c8:       41 01 c4                add    %eax,%r12d
    10cb:       44 89 65 78             mov    %r12d,0x78(%rbp)
    10cf:       e9 4e ff ff ff          jmpq   1022 <A_FireSigil+0xa2>
    10d4:       0f 1f 40 00             nopl   0x0(%rax)
        mo->target = player->mo;
        break;

sar is arithmetic shift right, which differs from shr in how it handles shifts of signed numbers.

Right shifting a signed value is undefined and different compilers seem to behave differently - gcc applies a sar while Clang uses shr I believe. It may be that MSVC does the same as Clang so the bug was missed.

Yeah I was afraid that might be the case. As long as we can make sure we get logical right shift behavior, it'll match the original executable. What's the portable way to do that? Is an unsigned int cast all that's necessary, or is that itself undefined behavior as well?

I think the unsigned cast is all that's needed. The undefined / implementation defined behaviour goes away once you switch to unsigned.

Just a note that I finally got around to pushing a fix for this one, along with a rash of more recent findings.

What about using division instead of right shift to get predictable results? Would " / (1 << ANGLETOFINESHIFT)" be enough?

fraggle said:

Right shifting a signed value is undefined and different compilers seem to behave differently - gcc applies a sar while Clang uses shr I believe. It may be that MSVC does the same as Clang so the bug was missed.

MSVC has always been capable of shifting negative numbers and I bet there's tons of code out there that actually use signed shifts.

I still wonder why this is undefined. Computer hardware has been capable of doing this right since nearly forever.

This looks like a typical problem of some committee being unwilling to write a good standard. And some idiot will always manage to break stuff because of that.

Graf Zahl said:

Computer hardware has been capable of doing this right since nearly forever.

Yes, I've never encountered a compiler that gets this wrong. It's not exactly rocket science. If it's unsigned then use Logic Shift Right, else if it's signed then use Arithmetic Shift Right.
In all honesty it has to be a pretty buggy compiler to get this wrong.

jeff-d said:

Yes, I've never encountered a compiler that gets this wrong. It's not exactly rocket science. If it's unsigned then use Logic Shift Right, else if it's signed then use Arithmetic Shift Right.
In all honesty it has to be a pretty buggy compiler to get this wrong.

If it's undefined in the standard (and that's the point: it is) then there is no right way. Although from a human POV I can't think of any other intention you would have than the obvious.

Jon said:

If it's undefined in the standard (and that's the point: it is) then there is no right way.

The real question should be: Why IS it undefined? I cannot see any reason for this other than the typical issues with design committees and their general unwillingness to make a standard robust.

If C were designed by committee, it would be enforcing a model that doesn't match current hardware.

It's undefined pretty much because C was intended to be a straight-forward compilation to assembly. There are sometimes multiple ways to interpret it, but compilers generally pick an obvious translation based on what would be done if programming directly in assembly.

This means very different CPU architectures would have very different behavior on the same compiled code, but it still makes writing compilers easier.

That entire reasoning sounds utterly backwards and may have been valid 20-30 years ago, but I think these days reliability and reproducability of what certain code does is 10x more important. Sad that these people do not acknowledge that.

Graf Zahl said:

That entire reasoning sounds utterly backwards and may have been valid 20-30 years ago, but I think these days reliability and reproducability of what certain code does is 10x more important. Sad that these people do not acknowledge that.

Seconded. I can't believe that this hasn't been hammered out in the standards yet.

The C standard has done more to hold back programming than it ever did to advance it. The total lack of security; taking until 1999 to even have types of a guaranteed size (which are still optional to implement... ie, int16_t may not exist in stdint.h if the CPU doesn't support word-sized units); HUGE gaping holes in the standard that are labeled as undefined or implementation defined behavior where there is an obvious way that it "ought" to work, which are only there because of the bizarre ideal that it is necessary to allow for performance concerns on platforms that don't exist any more.

Now I'm not saying C++ is any better. It adds a dozen new layers of features on top without fixing any of the C problems. Anything that's undefined in C is pretty much always still also undefined in C++.

Quasar said:

ie, int16_t may not exist in stdint.h if the CPU doesn't support word-sized units);

Fortunately, this probably being one of the things where such a compiler/platform would probably be rejected by the developers, because it'd just break too much code.

which are only there because of the bizarre ideal that it is necessary to allow for performance concerns on platforms that don't exist any more.

Bizarre indeed. It's quite obvious that these standards are being held back by very old-school programmers who somehow have lost touch with reality.

Another matter that reall irks me is that despite having a standard for how floating point is supposed to work on hardware, there's still glaring differences in how the math functions are implemented. Each compiler's library yields slightly different results, and many compilers default to a model that's not precise, preferring aggressive but unsafe optimizations.

And that, although it is definitely possible with all current architectures to get identical results. All you have to do is bring along your own math functions instead of using the compiler provided ones. (sigh...)

Graf Zahl said:

I still wonder why this is undefined. Computer hardware has been capable of doing this right since nearly forever.

This looks like a typical problem of some committee being unwilling to write a good standard. And some idiot will always manage to break stuff because of that.

It pretty much stems from compilers for old systems that are still in use today but you would really not know about it since it is so niche. It is probably for banking software or similar which is only being maintained and not replaced because it has worked for the past 35 years. The C comittee does not want to break compatibility with the way compilers have been doing it for said systems.

That's still idiotic and can be handled with a compile option.
But as things go this undefined-ness is not just kept for old features, they still add it to new features making the entire language standard one big mess.